[Paper Review] Factorization Machines

이승규·2022년 7월 17일

S. Rendle, "Factorization Machines," 2010 IEEE International Conference on Data Mining, 2010, pp. 995-1000, doi: 10.1109/ICDM.2010.127.

1. Introduction

Support Vector Machine(SVM)은 머신러닝과 데이터마이닝 분야에서 가장 인기있는 모델 중 하나이다. 그럼에도 불구하고 collaborative filtering에서는 SVM보다 standard matrix/tensor factorization model 또는 factorized parameter를 활용한 specialized model이 좋은 성능을 낸다. 그 이유는 SVM이 sparse한 데이터 환경에서 non-linear한 kernel space의 reliable parameter를 학습하지 못하기 때문이다.

본 논문에서는 Factorization Machine(FM)이라고 불리는 새로운 모델을 제안한다. FM은 SVM과 같은 general predictor로써 어떤 실수 feature vector든지 학습하여 회귀, 분류 같은 작업을 수행할 수 있다. 나아가 높은 sparsity에서도 reliable parameter를 잘 추정해내는 모델이다. SVM이 dense parametrization을 이용한 것과 달리, FM은 factorized parametrization으로 복잡한 interaction을 잡아낸다.

또한 FM의 연산을 linear time으로 줄인 방법도 소개한다. 즉 파라미터의 수에만 의존하여 연산 속도가 결정되고, 이는 기존 SVM 모델이 support vector에 의존하여 이중 연산 형태를 수행한 것보다 훨씬 빠르다.

2. Prediction Under Sparsity

대부분의 prediction task는 실수 feature vector $\mathbf{x} \in \mathbb{R}^n$ 를 타겟 도메인 $T$ 에 매핑시키는 문제로 치환할 수 있다. 예를 들어 회귀 문제이면 $T = \mathbb{R}$ , 분류 문제이면 $T = \{ +, -\}$ 가 된다. ranking task에서는 feature vector $\mathbf{x}$ 를 특정 실수값에 대응시키는 function을 모델이 학습하고 이렇게 도출된 score에 따라 feature vector를 정렬한다.

본 논문에서는 $\mathbf{x}$ 가 매우 sparse한 경우를 다룬다. 즉, 벡터 $\mathbf{x}$ 를 구성하는 대부분의 요소 $x_i$ 가 0인 상황이다. 실생활에서 feature vector가 sparse한 사례는 상품 구매 데이터나 text 분석처럼 categorical variable이 많은 도메인에서 쉽게 찾아볼 수 있다.

아래 그림은 영화 리뷰 데이터 $S$ 로부터 feature 벡터가 어떻게 만들어질 수 있는지를 보여준다. 데이터는 어떤 유저 $u \in U$ 가 영화 $i \in I$ 에 대해 $t \in \mathbb{R}$ 시점에 매긴 평점 $r \in \{ 1, 2, 3, 4, 5\}$ 로 구성되어 있으며 모델의 목표는 유저의 평점 $y$ 을 예측하는 것이다.

먼저 파란색 부분은 $|U|$ 명의 유저를 나타내기 위한 binary indicator variable vector이다. 하나의 리뷰는 한 명의 유저가 작성하기 때문에, 오직 하나의 variable만 1이 되고 나머진 0이다. 다음으로 주황색 부분은 $|I|$ 개의 영화를 나타내기 위한 vector이다. 마찬가지로 하나의 리뷰에는 한 개의 영화만 매핑되기 때문에, 오직 하나의 variable만 1이다. 노란색 부분은 유저가 과거에 리뷰를 남겼던 영화를 표현하기 위한 vector이다. 각각의 유저에 대해 variable의 총합이 1이 되도록 normalized 된 것이 특징이다. 초록색 부분은 날짜를 나타내는 부분으로, 특정 시점으로부터 몇 달이 흘렀는지를 표현한다. 마지막 갈색 부분은 유저가 직전에 리뷰를 남긴 영화를 나타내는 vector이다.

예를 들어, 두 번째 row는 A 유저가 14개월째에 NH 영화를 보고 평점 3점을 매겼다는 사실을 나타낸다. 또한 이 유저가 영화 TI, NH, SW를 봤고 NH를 보기 직전에 TI를 봤다는 것도 표현하고 있다.

3. Factorization Machines(FM)

3.1 Factorization Machine Model

저자가 제안한 degree=2인 Factorization Machine의 원리를 수식으로 표현하면 다음과 같다.

\hat{y}(\mathbf{x}) := w_0 + \sum_{i=1}^{n} {w_i x_i} + \sum_{i=1}^{n} \sum_{j=i+1}^{n} <\mathbf{v}_i , \mathbf{v}_j>x_i x_j

추정해야 할 모델 파라미터는 $w_0 \in \mathbb{R}$ , $\mathbf{w} \in \mathbb{R}^n$ , $\mathbf{V} \in \mathbb{R}^{n \times k}$ 로, $w_0$ 는 global bias, $w_i$ 는 $i$ 번째 변수에 대한 가중치이다. $\hat{w}_{i, j}:=<\mathbf{v}_i, \mathbf{v}_j>$ 는 두 벡터 $\mathbf{v}_i , \mathbf{v}_j$ 에 대한 내적 연산인데, $i$ 번째 변수와 $j$ 번째 변수 간의 interaction을 표현한다. 이를 통해 FM은 변수 간의 single, pairwise interaction을 잡아낼 수 있다.

latent vector의 차원 $k$ 가 충분히 크다면, 임의의 positive definite matrix $\mathbf{W}$ 에 대해 $\mathbf{W}=\mathbf{V} \cdot \mathbf{V}^t$ 를 만족하는 matrix $\mathbf{V}$ 가 항상 존재한다. 따라서 $k$ 만 크다면 FM은 어떤 interaction matrix $\mathbf{W}$ 도 표현할 수 있다. 그러나 sparse한 데이터 환경에서는 복잡한 interaction을 표현하기에 데이터가 부족하기 때문에 $k$ 를 제한할 수밖에 없다. 오히려 $k$ 를 줄이고 모델의 generalization을 높이는 선택을 한다.

FM은 interaction parameter간의 독립성을 깨뜨리고 factorize하여 sparse한 데이터로도 interation을 추정해내는 장점이 있다. 이는 하나의 interaction이 연관된 다른 interaction 사이의 파라미터를 추정하는데 도움을 줄 수 있다는 걸 의미한다.

연산의 시간 복잡도 측면에서도 FM은 장점을 가지고 있다. 위에서 제시한 식 형태를 보면 시간복잡도는 $O(kn^2 )$ 이다. 그러나 pairwise interaction 식을 재구성하여 다음과 같이 식을 변형할 수 있다.

\sum_{i=1}^{n} \sum_{j=i+1}^{n} <\mathbf{v}_i, \mathbf{v}_j>x_ix_j \qquad\qquad\qquad\qquad\qquad\qquad

= {1 \over 2}\sum_{i=1}^{n} \sum_{j=1}^{n} <\mathbf{v}_i, \mathbf{v}_j>x_ix_j - {1 \over 2}\sum_{i=1}^{n} <\mathbf{v}_i, \mathbf{v}_j>x_ix_j

= {1 \over 2} (\sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{f=1}^{k} v_{i,f} v_{j,f}x_ix_j - \sum_{i=1}^{n} \sum_{f=1}^{k} v_{i,f} v_{j,f}x_ix_i)\quad\;

= {1 \over 2} \sum_{f=1}^{k} ((\sum_{i=1}^{n} v_{i, f}x_i)(\sum_{j=1}^{n} v_{j,f}x_j) - \sum_{i=1}^{n} v_{i,f}^2 x_i^2)\qquad\quad\;\;

= {1 \over 2} \sum_{f=1}^{k} ((\sum_{i=1}^{n} v_{i, f}x_i)^2- \sum_{i=1}^{n} v_{i,f}^2 x_i^2)\qquad\qquad\qquad\quad\;\;\;\;

변형된 식은 $k$ 와 $n$ 에 대해 linear complexity를 가지며, 시간복잡도는 $O(kn)$ 이 된다.

나아가 $\mathbf{x}$ 의 elements 대부분이 0이기 때문에 $\sum$ 계산이 0이 아닌 elements에 대해서만 이루어지고 연산이 더 빠르게 수행된다.

3.2 Factorization Machines as Predictors

FM은 regression, binary classification, ranking 등 다양한 prediction task에 활용될 수 있다.

Regression: $\hat{y}(\mathbf{x})$ 가 곧 predictor로 활용되며, optimization criterion으로 minimal least square error를 사용할 수 있다.
Binary Classification: $\hat{y}(\mathbf{x})$ 의 부호가 곧 predictor이다. optimization criterion은 hinge loss나 logit loss를 주로 사용한다.
Ranking: $\hat{y}(\mathbf{x})$ 의 score에 따라 벡터가 정렬된다. optimization은 pairwise classification loss를 사용한다.

3.3 Learning Factorization Machines

FM의 연산이 linear한 시간 복잡도를 가지기 때문에, 모델 파라미터 $w_0$ , $\mathbf{w}$ , $\mathbf{V}$ 는 SGD와 같은 gradient descent method로 학습된다. FM 모델의 gradient는 다음과 같다.

{\partial \over \partial \theta} \hat{y}(\mathbf{x}) = \begin{cases} 1,\qquad\qquad\qquad\qquad\quad\quad\;\;\;\,\text{if }\; \theta \;\text{ is } \;w_{0}\\ x_i,\qquad \qquad\qquad\qquad\quad\quad\;\;\text{if }\; \theta \;\text{ is } \;w_{i}\\ x_i \sum_{j=1}^{n} v_{j, f}x_j - v_{i, f}x_i^2,\qquad \text{if }\; \theta \;\text{ is } \;v_{i, f} \end{cases}

식에서 $\sum_{j=1}^{n} v_{j, f}x_j$ 는 $i$ 에 무관하기 때문에 미리 계산될 수 있고, 각 gradient는 계산의 시간 복잡도는 $O(1)$ 이다. 또 sparsity 상에서도 각 파라미터 업데이트는 $O(kn)$ 만에 수행될 수 있다.

3.4 d-way Factorization Machine

앞서 제시한 2-way FM은 d-way FM으로 확장될 수 있는데, 그 식은 다음과 같다.

\hat{y}(x) := w_0 + \sum_{i=1}^{n}w_i x_i + \cdots+\sum_{l=2}^{d}\sum_{i_1=1}^n \cdots \sum_{i_l =i_{l-1}+1}^n (\prod_{j=1}^l x_{i_j} v_{i_j , f}^{(l)})

$l$ 번째 interaction의 파라미터는 PARAFAC 모델로 factorized되며, 연산의 시간 복잡도는 $O(k_d n^d)$ 이다.

3.5 Summary

정리하면, FM은 factorized interaction을 이용해 feature vector $\mathbf{x}$ 에서 각 변수 간의 interaction을 잡아낸다. 이는 high sparsity 조건에서도 잘 작동하여 관찰되지 않은 interaction을 generalize할 수 있다. 또 학습과 예측 단계의 시간 복잡도, 파라미터 수가 linear하다는 점에서 SGD optimization을 가능하게 하고 다양한 loss function을 사용할 수 있다.

Factorization Machine은 추천시스템 뿐만 아니라 분류, 회귀 문제에도 적용될 수 있다고 한다. 유저, 아이템에 대한 다양한 feature를 투입할 수 있다는 점이 큰 장점으로 보인다. FM이 발전하여 만들어진 DeepFM 논문도 읽어봐야겠다.