Factorization Machines논문을 흐름대로 정리해보려고 합니다.
Abstract
1. SVM 모델과 factorization 모델의 장점을 결합한 Factorization machine을 소개한다.
2. SVM과 같이 Real Value(실수) Feature Vector를 활용한 General Predictor이다.
3. FM의 방정식은 linear time이다.
- 비선형의 SVM과 달리 dual form으로의 변환이 필요하지 않고, 어떠한 support vector의 도움없이 모델 파라미터들을 직접적으로 추정할 수 있다.
4. 다른 일반적인 추천시스템 모델은 General prediction task에 적용할 수 없을 뿐 아니라, special input을 필요로한다. 하지만 FM은 factorization model에 전문적인 지식이 없어도 쉽게 적용이 가능하다.
I. INTRODUCTION
1) FM은 SVM이 실패한 희소한 상황에서도 파라미터 추정이 가능하다.
2) FM은 linear complexity를 가진다.
3) 실수 값을 가지는 feature vector를 이용하는 general predictor이다.
- 추천시스템 이외의 다른 머신러닝 문제에서 사용할 수 있다.
** 저자들은 위의 세가지를 논문에서 계속 강조하고 있습니다.
II. PREDICTED UNDER SPARSITY
일반적인 예측 과제(common prediction task)에서는 실수값을 가지는 feature vector x로부터 target domain T (회귀 문제에서는 T = R, 분류문제에서는 {+,-})를 예측하는 것이다. 지도학습에서는 D = {(x(1),y(1)), (x(2),y(2)), ...} 처럼 training dataset가 있다고 가정한다. 이 눈문에서는 x가 매우 희소한 경우의 문제를 다룬다. vector x의 거의 모든 요소들이 0이다. 이처럼 Huge sparsity는 추천시스템의 구매내역과 같이 거래 발생의 feature vector나 bag of word와 같이text analysis의 데이터에서 많이 나타난다. huge sparsity의 한가지 문제는 큰 범주형 변수들을 다룬다는 것이다.
- 논문에서는 영화 리뷰 데이터를 예시로 보여주고 있다.
- 왼쪽의 S와 같은 형식으로 데이터셋을 나타낼 수 있다.
- 이 데이터에서 예측 과제는 특정 시간에 유저들의 평점 방식을 예측하는 것이다.
- 위의 그림은 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과 비슷하다.
III. FACTORIZATION MACHINES (FM)
A. Factorization Machine Model
1) Model Equation
- 예측해야 할 파라미터는 세개가 있다. 방정식의 왼쪽에서부터 1. W0(Global Bias) 2. Wi (i번째 wieght) 3. <Vi,Vj>
- 여기서 n은 feature 의 개수라고 생각하면 쉽다.
- 두번째 요소를 설명하면 feature vector x에 대해서 각 변수에 걸맞는 가중치 w를 학습하는 것이다. 즉 이 부분을 통해 개별 변수의 영향력을 모델링 한다.
- 세번째 요소는 선형회귀에서 상호작용 효과를 표현해주기 위해 변수들간의 곱을 변수로 추가하는 것과 비슷한 원리이다. 다만 FM은 상호작용 항의 계수를 변수간의 Latent Vector의 내적으로 사용하는 것이다. 즉 두 변수간에 Latent Vector 조합을 고려하기 때문에 변수 간 interaction을 모델링 할 수 있다.
- 아래에서 내적 부분을 더 자세히 살펴보자.
- <Vi, Vj>는 i번째 변수와 j번째 변수의 interaction(상호작용)을 모델링한다.
- FM은 개별 변수들의 가중치만을 사용하는것 뿐만 아니라 factorizing(분해)을 사용함으로써 interaction을 모델링한다.
- 뒷 부분에서 보겠지만, 이 부분이 sparsity한 상황에서도 high-order interaction의 파라미터 추청치를 가능하게 해주는 key point가 된다.
4) Computation
- FM이 어떻게 Linear complexity를 갖는지를 보여주고 있다.
- 변수 2개에 직접적으로 연관된 model parameter가 없기 때문에 pairwise interactions은 위와 같이 reformulate될 수 있는 것이다.
B. Factorization Machine as Predictors
다음과 같이 Regression, Classification, Ranking 처럼 Generalized Task를 해결할 수 있다.
C. Learning Factorization Machines
- FM의 Model parameters는 경사하강법에 의해 효과적으로 학습될 수 있다. – stochastic gradient descent(SGD)
- Y햇을 미분했을때 세타값에 따라 다음 값을 가지며 이때 Vjf*Xj는 i에 독립적이어서 미리 계산될수 있다.
- 그러므로 time complexity가 더 떨어진다.
SUMMARY
1. Factorized Interaction을 사용하여 feature vector x의 모든 가능한 interaction을 모델링한다.
2. 매우 sparse한 상황에서 interaction을 추정할 수 있다. Unobserved interaction에 대해서도 일반화할 수 있다.
3. 학습과 예측시간 모두 linear하다. Linear complexity
4. SGD를 활용한 최적화를 진행할 수 있고 다양한 loss funtion을 사용할 수 있다.
5. SVM, specialized model보다 더 나은 성능을 증명한다.