Factorization Machines

투빅스1617 RS·2022년 5월 25일

DeepFM은 FM Component와 Deep Component로 이루어져 있다.
본 정리는 DeepFM의 FM component 부분을 정리하기 위해 2010년 발표된 Factorization Machines 논문을 리뷰하고자 한다.

작성자: 투빅스 16기 이승주

contents
Unit 01 ㅣ Abstract
Unit 02 ㅣ Introduction
Unit 03 ㅣ Prediction under sparsity
Unit 04 ㅣ Factorization Machines
Unit 05 ㅣ FMs VS. SVMs
Unit 06 ㅣ Conclusion and works

작성자: 투빅스 16기 이승주

0. Abstract

Factorization Machine은 SVM과 Factorization Model의 장점을 합친 모델이다.
Factorization Model의 예시: Matrix Factorization, Parallel factor analysis, specialized model(SVD++, PITF or FPMC)
Real valued Feature Vector를 활용한 General Predictor이다.
Factorization Machine의 식은 linear time이다. 비선형의 SVM과 달리 dual form으로의 변환이 필요하지 않고, 어떠한 support vector의 도움없이 모델 파라미터들을 직접적으로 추정할 수 있다.
보통 추천모델은 General prediction task에 적용할 수 없을 뿐 아니라, special input data, optimization algorithm 등이 필요하지만 Factorization Machine은 어느 곳에서든 쉽게 적용 가능하다.

1. Introduction

1) FM은 general Predictor이며 high sparsity에서도 reliable parameters를 예측할 수 있다. Sparse한 상황에서 SVM은 부적절하다

2) FM은 linear complexity를 가지며 linear number of parameters이다.

3) Factorization Machine은 복잡한 interaction도 모델링하고, factorized parameterization을 사용한다.

2. Prediction Under Sparsity

일반적으로 볼 수 있는 영화 평점 데이터의 설명이다. Matrix Factorization은 user와 movie, 그리고 해당 rating만 사용한다. Factorization Machine은 더 다양하게 사용할 수 있다.

위의 그림은 S로부터 feature vectors가 어떻게 만들어질 수 있는지 예시를 보여준다.
앞에서부터 |U|는 해당 유저를 나타내는 binary indicator변수이며 |I|는 item(여기서는 어떤 영화인지)을 보여주는 binary indicator변수, yellow의 부분은 유저가 평점을 매긴 다른 영화들의 정보가 합계가 1이 되게 정규화되어 표현되고 있다.
green은 시간(여기서는 month)정보를 담고 있으며 마지막 brown은 해당 transaction의 영화 평점을 매기기 직전에 평점을 매긴 영화를 binary indicator로 담고있다.
이처럼 Matrix Factorization은 user, movie에 대한 rating만을 사용하지만, FM은 시간을 포함하여 더 다양한 feature를 포함하고 있다. Feature engineering을 한다는 점에서 SVM과 비슷하다.

타겟 데이터는 평점 데이터이며 궁극적으로 메타정보, 즉 새롭게 피쳐 엔지니어링을 한 추가 정보들을 이렇게 하나의 특성 벡터로 합쳐 최종 rating을 예측한다.

3. Factorization Machine(FM)

3.1 Linear regression

Advantage : linear calculation 𝛰(𝑛)
Disadvantage : no interactions among the features $𝑥_𝑖$

각각의 변수에 각각의 가중치를 곱해서 더하면 예측값이 나오게 하는 선형회귀 먼저 살펴보겠다.
식이 간단하기 때문에 계산이 엄청 빠르다는 장점이 있지만 각각의 변수의 interaction이 반영이 안되기 때문에 정확한 예측을 하기가 어렵다. 따라서 선형 회귀에서 상호작용의 효과를 표현해주기 위해 변수들간의 interaction까지 모두 모델링 하기위해 다음과 같은 식을 제안한다.

3.2 Factorization Machine - Equation

Interaction을 두변수의 곱으로 표현을 하고 각각의 변수들의 Interaction에 정도가 다를테니까 그 정도를 가중치로 표현을 한 것이다.

예측해야 할 파라미터는 $W_0$ (Global Bias) , $W_i$ (i번째 wieght) , $W_{ij}$ 세개이며, n은 feature 의 개수이다.
두번째 요소 $W_i$ $x_i$ 는 feature vector x에 대해서 각 변수에 걸맞는 가중치 w를 학습하 별 변수의 영향력을 모델링 한다.
세번째 요소 $W_{ij}$ $x_i$ $x_j$ 는 2-way FM (degree = 2)로 선형회귀에서 상호작용 효과를 표현해주기 위해 변수들간의 곱을 변수로 추가하는 것과 비슷한 원리이다. 다항 회귀와 매우 흡사하지만 coefficient 대신 FM은 상호작용 항의 계수를 변수간의 Latent Vector의 내적으로 사용한다는 차이가 있다. 파라미터마다 embedding vector를 만들어 내적하여 두 변수간에 Latent Vector 조합을 고려하기 때문에 변수 간 interaction을 모델링 할 수 있다. 그러나 단점은 계산량이 늘어났다는 점이다. 따라서 계산량을 줄이고자 다음과 같이 분해 가능하다.

같은 변수들끼리의 interaction은 고려하지 않겠다는 것이고,
그리고 $x_{ij}$ 나 $x_{ij}$ 는 같은 관계이기 때문에 한쪽만 계산하겠다는 것이다.
그래서 여기서 $W_{ij}$ 은 symmetric행렬이다라는 것을 알 수 있고 위와 같이 분해 가능하다.
원래는 $ℝ^{𝑛×𝑛}$ element를 $n^2$ 개를 관리를 해야하는데 분해를 통해 매트릭스 V를 활용하여 $ℝ^{𝑛×k}$ 개만 고려해주므로 k는 n보다 훨씬 작은 숫자로 설정하여 가능한 범위내에서 변수를 줄여줄 수 있다.

따라서 다음과 같이 식을 다시 표현할 수 있다.

$x_i$ : X 데이터 셋의 하나의 행 벡터(feature vector)
$w_0$ : global bias
$w_i$ : i번째 변수의 영향력을 모델화 함
$w_{ij}$ = < $v_i$ , $v_j$ >: i, j번째 변수간의 상호작용을 모델링
$v$ : factor vector

FM은 개별 변수들의 가중치만을 사용하는것 뿐만 아니라 factorizing(분해)을 사용함으로써 interaction을 모델링하므로 sparsity한 상황에서도 high-order interaction의 파라미터 추청치를 가능하게 해주는 key point가 된다.

3.3 Factoriazation Machine - computation

기존의 식에서 약간의 시그마 트릭을 이용해서 열심히 계산을 하면 연산량이 줄어드는 형태로 바꿀 수 있다. 변수 2개에 직접적으로 연관된 model parameter가 없기 때문에 pairwise interactions은 위와 같이 reformulate될 수 있는 것이다.

3.4 Factorization Machines as Predictors

FM은 regression, binary classification, ranking으로 사용가능하며 regularization term L2를 통해 과적합을 방지한다.

3.5 Learning Factorization Machines

FM의 Model parameters는 경사하강법에 의해 효과적으로 학습될 수 있다. stochastic gradient descent(SGD)
y^을 미분했을때 파라미터에 따라 다음 값을 가지며 $v_{j,f}$ * $x_j$ 는 i에 독립적이라 미리 계산된다. 그러므로 time complexity가 더 떨어진다.

3.6 d-way Factorization Machine

FM은 d-way로 일반화가 가능하다.
d-way의 경우에도 선형 시간의 계산 복잡도를 가지고 있다.

4. Conclusion

Factorized Interaction을 사용하여 feature vector x의 모든 가능한 interaction을 모델링한다.
High sparse한 상황에서 interaction을 추정할 수 있다. Unobserved interaction에 대해서도 일반화할 수 있다.
파라미터의 수, 학습과 예측시간 모두 linear하다. Linear complexity
SGD를 활용한 최적화를 진행할 수 있고 다양한 loss funtion을 사용할 수 있다.
SVM, specialized model보다 더 나은 성능을 증명한다.

DeepFM

기존의 FM과 거의 동일한 수식으로 FM Component는 계산이 가능하다.

$a^{(0)}$ 는 임베딩 층의 output이며, $e_i$ 는 i번째 특성의 임베딩, m은 특성의 수이다. $a^{(0)}$ 는 심층 신경망의 input이 되며, 일반적인 신경망의 연산을 수행한다.

H개의 hidden layer를 거친 Deep component의 output은 위와 같다.

FM + DNN = DeepFM

DeepFM은 FM Component와 Deep Component로 이루어져 있으며 각각 FM component는 Low-order를, Deep component는 High-order를 모델링하기 위해 사용된다. 두개의 Component는 서로 같은 Input과 Embedding을 공유하고 모든 파라미터는 아래의 예측 통해 동시에 학습이 진행된다(jointly training).