[논문 리뷰] Factorization Machines

Abstract

본 논문에서는 SVM(Support Vector Machines)의 장점과 Factorization 모델을 결합한 새로운 모델 클래스인 Factorization Machines(FM) 를 소개한다. SVM과 마찬가지로 FM은 모든 실수 값 feature vector를 통해 예측을 하는 모델이다. SVM과 달리 FM은 factorized parameters(인수분해 매개변수) 를 사용하여 변수 간의 모든 상호 작용을 모델링합니다. 따라서 SVM이 작동하지 못하는 sparsity가 큰 데이터에서 FM은 상관관계를 추정할 수 있다. 본 논문은 FM의 모델 방정식이 선형 시간으로 계산되어 FM이 바로 최적화될 수 있음을 보여준다. 따라서 비선형 SVM과 달리 dual form의 변환이 필요하지 않기 때문에 support vector 없이도 모델 매개변수를 직접 추정할 수 있습니다. 본 논문에서는 Sparse한 데이터에서 파라미터 추정을 위한 SVM과 FM의 장점간의 관계에 대해 설명한다.

SVD++, PITF, FPMC같은 특수 모델들은 일반적인 예측 작업에는 적용되지 않고 특수 입력 데이터에서만 작동한다. 또한 모델 방정식과 최적화 알고리즘은 각 작업에 대해 개별적으로 도출된다. 본 논문에서는 FM이 입력 데이터(feature vectors)를 지정함으로써 이러한 모델을 모방할 수 있음을 보여준다. 따라서 FM은 factorization model에 대한 전문 지식이 없는 사용자에게도 쉽게 적용할 수 있습니다.

1. Introduction

SVM

SVM은 유명한 예측 알고리즘이지만 협업 필터링에서는 중요한 역할을 하지 못한다.

sparse한 데이터의 비선형적(complex) 커널 공간에서 reliable parameter(hyperplane: 초평면)을 학습할 수 없기 때문이다.

FM

본 논문의 FM은 매우 sparse한 데이터에서도 reliable parameter을 학습할 수 있다.

FM은 SVM의 선형커널(polynomial kernel)과 같이 모든 중천된 변수간의 상관관계를 모델링한다.

SVM과 다르게 dense parametrization가 아닌 factorized parametrization 사용한다.

FM의 모델 방정식은 선형 시간으로 계산되어 파리미터들의 숫자에 따라 학습 시간이 결정된다.

FM의 장점

Sparse data : SVM으로 학습하기 어려운 sparse한 데이터에서도 파라미터 추정이 가능하다.

Linear Complexity : 선형복잡도를 가지며 SVM과 같이 쌍대 문제(dual problem)를 다루지 않아도 된다.

General Predictor : 모든 실수 feature vector Input에 대해 잘 작동한다.

2. PREDICTION UNDER SPARSITY

본 논문은 실수 feature vector x가 매우 sparse한 상황을 다룬다.

• $m(x)$ : x에서 0이 아닌 요소의 수
• $\overline{m}_D$ : 학습 데이터 D에 속하는 모든 x에 대한 m(x)의 평균

Example 1 (영화 리뷰 시스템)

영화 리뷰 시스템은 유저(u ∈ U)가 특정 시간(t ∈ R)에 영화(i ∈ I)에 평점을 데이터(data ∈ S)에 기록한다.

U = {Alice (A), Bob (B), Charlie (C), . . .}

I = {Titanic (TI), Notting Hill (NH), Star Wars (SW), Star Trek (ST), . . .}

S = {(A, TI, 2010-1, 5),(A, NH, 2010-2, 3),(A, SW, 2010-4, 1), (B, SW, 2009-5, 4),(B, ST, 2009-8, 5), (C, TI, 2009-9, 1),(C, SW, 2009-12, 5)}

이 데이터를 통해 유저의 특정 시간에 영화에 대한 평점을 예측한다.

각 행에는 하나의 User, 하나의 Movie(item) 그리고 바로 이전에 평점을 기록한 영화를 나타내기 위해 One-Hot-Encoding을 통해 이진화를 한다.

각 행에는 모든 영화에 대한 평점의 합이 1이 되게 정규화(normalization)을 한다.

3. Factorization Machines (FM)

A. Factorization Machine Model

1. Model Equation

위의 식은 2개 특성 사이의 관계를 고려하는 2-way(2차원) Factorization machine이다.

2-way FM(2차원)은 변수간의 단일 독립변수와 종속변수 간 상호작용 뿐 아니라 한 쌍(pairwise)의 독립변수 조합과 종속변수 사이의 상호작용도 잡아낸다.

• $w_0$ : global bias
• $w_i$ : i번째 변수의 가중치
• $w_{i,j}$ : i번째 변수와 j번째 변수 사이의 상호작용
• $v_i$ : V 내부의 행을 의미하며, $v_i$는 $k$개의 factor를 지닌 i번째 변수
• $k$ : 0을 포함한 자연수이며 factorization의 차원

FM 모델은 각 상호작용에 대해 $w_{i,j}, w_{j,i}$를 그대로 사용하지 않고 이를 인수분해(factorizing)하여 사용한다. 이 부분이 sparse한 데이터임에도 불구하고 고차원의 상호작용에 대해 파라미터 추정치를 산출할 수 있는 중요한 역할을 한다.

2. Expressiveness

$W$ 행렬의 차원을 의미하는 $K$를 충분히 크다면 Positive definite matrix $W$에 대해 $W=V \cdot V^T$ 를 만족하는 $V$ 는 항상 존재한다.

FM은 충분히 큰 $k$ 가 선택되면 어떠한 Interaction Matrix $W$ 를 표현할 수 있다.

그러나 , 일반적으로 모든 복잡한 Interaction을 계산하기에는 데이터가 충분하지 않기 때문에 작은 k를 선택하여 일반화 성능을 높히고 sparse한 상황에서 향상된 상호작용 matrix를 만든다.

3. Parameter Estimation Under Sparsity

일반적으로 Sparse한 환경에서는 변수들 간의 Interaction을 직접적, 독립적으로 추정하기 위한 충분한 데이터가 없는 경우가 많다.

FM은 Sparse한 경우에도, 변수 사이의 Interaction을 추정할 수 있다. 즉, 하나의 Interaction에 연관된 데이터가 다른 Interaction을 추정하는데 도움을 준다.

예를 들어 유저 A의 아이템 B에 대한 선호도를 모른다면, 유저 A 혹은 아이템 B에 관한 다른 Interaction 들을 고려하여 삼단논법과 같이 이를 계산할 수 있게 됩니다.

4. Computation

FM의 Model Equation은 모든 pairwise 상호작용항들을 계산해야 하므로 직관적인 계산 복잡도는 $O(kn^2)$ 이다.

다음과 같은 식을 통해 FM의 Model Equation은 Linear Complexity 를 가지고 있다.

B. Factorization Machines as Predictors

Regression(회귀) : $\hat{y}(x)$은 예측변수 혹은 최적화의 기준(즉 D에 대한 MLE)으로 사용된다.

Binary classification(이항 분류) : $\hat{y}(x)$은 hinge loss 혹은 logit loss에서 최적화의 대상이 되는 파라미터로 사용된다.

Ranking : 벡터 $x$는 $\hat{y}(x)$의 값 순서대로 정렬되어 있으며 $(x^{(a)},x^{(b)}) , \in , D$의 쌍벡터들에 대해 pairwise classification loss로 최적화를 한다.

이 모든 문제에서 L2 정규화 항은 overfitting(과대적합)을 막기 위해 추가된다.

C. Learning Factorization Machines

FM은 Linear Complexity 를 가지고 있으므로 FM의 파라미터들($W_0$, $w_i$, $v_{i,f}$)은 Gradient descent 방법론들로 학습되어 질 수 있다. (예SGD, hinge loss, logit 등) FM의 gradient는 다음과 같다.

$\sum_{j=1}^nv_{i,f}x_j$ 는 i에 대해 독립적이기 때문에 미리 계산될 수 있다. 일반적으로 각각의 Gradient는 상수적 시간 $O(1)$에 계산될 수 있다. 그리고 (x, y)를 위한 모든 파라미터 업데이터는 sparcity 환경에서 $O(kn)$ 혹은 $O(km(X))$ 안에 이루어질 수 있다.

D. d-way Factorization Machine

FM은 2-way 뿐만 아니라, d-way로 일반화가 가능하다.

d-way 또한 Linear Complexity 를 가진다.

E. Summary

FM 모델은 모든 feature vector들 대신에 factorized interaction들을 사용하여 feature vector x의 값사이의 모든 가능한 상관관계들을 모델링한다. 이 방식은 두가지 장점이 있다.

• 높은 sparsity에서도 상호작용을 추정할 수 있다. 특히 관측되지 않은 데이터 사이의 상호작용항의 일반화가 가능하다.
• 예측과 학습에 대한 시간뿐 아니라 파라미터의 숫자도 선형화하였다. 이를 통해 SGD를 사용한 최적화를 가능하게 만들었으며 다양한 Loss Fucntion의 최적화를 가능하게 한다.

구현

• Paper_review/FM at master · HardenKim/Paper_review

 

---

References

• Factorization Machine - Machine Learning & Data Science
• Factorization Machines (FM) 설명 및 Tensorflow 구현
• [추천시스템][paper review][구현] Factorization Machines
• Recommender-System-with-TF2.0/FM - ZiyaoGeng

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋