요약
이 논문은 Support Vector Machine(SVM) 의 장점과 Factorization model들을 합친 새로운 모델Factorization Machine을 소개한다. SVM같이 FM은 real valued 피처벡터를 사용하는 모델이다. 그러나 SVM과 다른 점은 피처간 상관관계 또한 Factorized Parameter를 통해 사용한다는 것이다. 그러므로 Sparisity가 큰 데이터에서는 작동하지 못하는 SVM과는 달리 FM은 상관관계들을 추정할 수 있다. 이 논문에서 FM의 공식들이 어떻게 선형시간(Linear Time)으로 계산되어 바로 최적화가 될 수 있는지에 대해 설명한다. 따라서 비선형기법인 SVM과는 다르게 Dual form 에서의 변형이 필요없고 support vector없이 바로 모델 파라미터를 추정할 수 있다. 이 논문에서는 SVM과 FM의 Sparse 데이터에 대한 파라미터 추정의 장점간의 관계에 대해 설명한다.
반면에 Matrix Factorization Parallel factor analysis 또는 SVD++, PITF, FPMC같은 특화된 모델들 같이 다른 Factorization model들도 있다. 이러한 모델들의 단점은 일반적인 문제보다는 특별한 데이터 혹은 문제에 적합하다는 것이다. 더욱이 이 모형들의 식과 최적화 알고리즘들은 각 문제들에 대해서 파생되었기 때문에 일반적인 문제에 사용하기 더욱 어렵다. 이 논문에서는 FM이 피처벡터(input 데이터)를 지정하는 것으로 위 모델들을 따라할 수 있다. 이것은 해당문제에 전문지식이 없는 모델러도 특정문제에 FM을 사용할 수 있게 만들어준다.
1. Introduction
SVM 머신러닝과 데이터 마이닝 분야에서 인기있는 모형중 하나이다. 그럼에도 CF(Collaborative filtering)과 같은 환경(setting)에서, SVM은 중요한 모형이 아니었다. Standard matrix/tensor factorization (e.g PARAFAC) 또는 Factorized Parameter들을 사용한 특수모형들이 최고의 성능을 내었다. 이 논문에서 왜 SVM이 Sparse데이터하에서 복잡한 커널공간(non-linear)상의 Hyperplane들(reliable parameters)을 학습할 수 없는지를 볼 것이다. 반면에 Tensor factorization 모델과 특수 FM들의 단점이 (1) 일반적인 문제에 적용할 수 없다는 것에 대해 알아볼 것이다.
이 논문에서 SVM과 같이 일반적인 문제에도 적용할 수 있지만 Sparse데이터 상에서도 hyperplane(reliable parameters)를 추정할 수 있는 FM을 소개할 것이다. FM 은 모든 nested 변수들의 상관관계들(SVM에서 polynomial kernel과 비슷한) 모델링에 사용하나 SVM 과 같이 dense 파라미터들 대신에 Factorized 파라미터들을 사용한다. FM의 모형식은 선형시간으로 학습될 수 있으므로 파라미터들의 숫자에 따라 학습시간이 결정된다. 이 장점은 예측에서 Support vector와 같은 훈련데이터를 저장할 필요 없이 모형의 파라미터를 저장하면서 최적화를 가능하게 한다. 이와는 반대로 비선형 SVM은 보통 dual form으로 최적화하고 예측은 훈련데이터 (Support vectors)의 부분에 의존한다.
We also show that FMs subsume many of the most successful approaches for the task of collaborative filtering including biased MF, SVD++ [2], PITF [3] and FPMC [4]. In total, the advantages of our proposed FM are: 1) FMs allow parameter estimation under very sparse data where SVMs fail. 2) FMs have linear complexity, can be optimized in the primal and do not rely on support vectors like SVMs. We show that FMs scale to large datasets like Netflix with 100 millions of training instances. 3) FMs are a general predictor that can work with any real valued feature vector. In contrast to this, other state-ofthe-art factorization models work only on very restricted input data. We will show that just by defining the feature vectors of the input data, FMs can mimic state-of-the-art models like biased MF, SVD++, PITF or FPMC.
2. Sparse데이터상에서의 예측
가장 일반적인 예측문제는 real valued 피처벡터(메타 피처벡터와는 반대 의미 같음)로부터 Target 변수를 추정한다 지도학습에서, 각 X,Y 값을 입력해 X에 따른 Y의 파라미터를 학습한다. Ranking 문제에서는 x값에 따른 y의 score를 추정해 정렬 후 랭킹을 매기는 것으로 문제를 풀 수 있다. 여기서 Scoring 함수는 위 튜플 (x (A) , x (B) ) ∈ D (A가 B보다 높은랭크) 를 통해 학습시킬 수 있다. 이 순위를 나타내는 짝은 비대칭이기 때문에, 오직 양의 X만을 사용할 수 있다.
이 논문에서 X가 거의 0인 Sparse 데이터를 어떻게 다뤄야 하는지를 다룬다. m(x) 가 x 벡터에서 0이 아닌 데이터의 숫자라고 하자. MD 를 모든 x벡터에 대해서 m(x)의 평균이다. Event transaction(e.g 추천시스템의 구매이력)이나 text analysis(e.g bag of word 접근법)의 피처벡터들 같은데에서 큰 sparsity가 있다. 이렇게 sparsity가 큰 이유 중 하나는 큰 categorical 변수의 범위에 있다.
Ex1. 영화리뷰시스템의 transaction 데이터를 가정해보자. 시스템은 어느 유저가 한 영화를 특정시간에 어떤 평점을 매기고 있는지 기록한다. 유저와 아이템의 원소들을 아래와 같이 정의한다.
U = {Alice (A), Bob (B), Charlie (C), . . .}
I = {Titanic (TI), Notting Hill (NH), Star Wars (SW), Star Trek (ST), . . .}
데이터 S는 다음과 같다.
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)}
이 데이터를 통해 예측하려는 것은 특정시간에서 한 영화에 대한 한 유저의 평점을 예측하는 것이다. 1번 그림은 어떻게 피처벡터들을 s에서 생성하는지를 보여준다. 첫번째 U집합은 이진변수(One-Hot-Encoding), 즉 한 transaction에서 해당된 유저를 나타낸다. 항상 하나의 transaction에 하나의 유저가 있다. (u, i, t, r) ∈ S 예를 들어 유저 앨리스가 첫번째 transaction에 있다. 다음 I 또한 이진변수이고 현재 유저가 평가하고 있는 영화이다. 노란색 부분은 예전에 user가 매겼던 평점이다. 모든 평점의 합이 1이 되게 정규화(normalization)을 했다. 초록색 부분은 2009년 1월부터 시작하여 평점을 매긴 시점의 개월 수를 나타내고 있다. 마지막 갈색상자는 현재 평점을 매기고 있는 영화 바로 전 영화를 나타내는 이진변수이다.
본 논문에서는 이 평점데이터를 쓰나 FM도 SVM과 같이 추천시스템 이외의 다른 특성의 데이터들에 적용시킬 수 있다.
3. Factorization Machines
A) Factorization Machine Model
우리는 모델방정식에 대한 디테일한 부분에 대해 의논했고 어떻게 FM을 몇몇 예측문제에 적용하는지 간략하게 보여준다.
1) 모델방정식
d= 2 (2차원)상의 FM 방정식은 다음과 같이 정의된다.
학습해야 되는 모델 파라미터들은 다음과 같다.
그리고
는 k개의 두벡터의 dot product이다.
\(V_i\)안 v 은 k개의 factor들을 가지고 있는 i번째 변수를 말한다. K는 0을 포함한 자연수이며 factorization의 차원을 정의한다. 2-way FM(2차원)은 단일 독립변수와 종속변수 간 상호작용 뿐 아니라 한쌍의 독립변수조합과 종속변수간 상호작용도 잡아낸다.
\(w_0\)는 global bias를 나타냄 / \(w_i\)는 i번째 변수의 가중치 / \(w_{ij}\)는 i번째와 J번째사이의 상호작용을 나타낸다. 각 상호작용에 대해 그대로 모델에서 산출된 가중치를 그대로 쓰는 것이 아니라. FM은 이 상호작용들을 fatorizing(인수분해)하여 사용한다. 이것이 고차원에서 sparsity의 문제가 있음에도 좋은 가중치들을 낼 수 있는 키포인트이다.
2) 표현
W 행렬에는 K차원이라는 충분히 큰 두 v행렬로 구성되어있다. 이것은 FM이 K가 충분히 크다면 어느 상호작용 W도 표현할 수 있다. 그럼에도 불구하고 sparse한 환경에서는 상호작용 매트릭스 w를 추정하는데 충분한 데이터가 없기 때문에, k가 작아야 좋다. k를 제한한다는 것은 즉 르의 표현력을 줄인다는 것은 더 좋은 일반화로 이어지며 sparsity 상에서도 향상된 상호작용 matrix를 만들 수 있다.
3) Sparsity 상 파라미터 추정
Sparse 환경에서는 보통 변수간 상호작용을 i.i.d(independent and identical distribution)를 가정으로 측정할 때 데이터가 충분하지 한다. FM은 이러한 Sparse 환경에서도 변수간 상호작용을 측정할 수 있는데. 이는 이 상호작용 매트릭스들을 factorizaing 함으로써 독립성가정을 깼기 때문에 가능하다. 일반적으로 이는 하나의 상호작용에 대한 데이터가 다른 관련된 상호작용들을 측정하는데 도움을 준다는 것을 의미한다. 이 개념은 figure1.에 있는 데이터에서 더 명확히 드러난다. 우리는 Alice(A) 와 Star Trek(ST)사이의 상호작용이 target y변수(여기서는 평점)에 얼마나 가중치를 두는지 측정하고 싶다. 명백히 xA와 xST 둘 다 1인 트레이닝 데이터는 없다. 따라서 그대로 측정한다면 0이 나올지도 모른다. 그러나 <\(V_A\), \(V_{ST}\)> factorize한 상호작용 매트릭스로, 이 상황에서 둘의 상호작용을 측정할 수 있다. 먼저 Bob과 찰리는 유사한 Factor벡터(\(V_B\), \(V_C\))를 가질 것이다. 그 이유는 둘다 Star Wars (\(V_{SW}\))와 평점에 대해 비슷한 상호작용형태를 가지고 있기 때문이다. 즉 <\(V_B\), \(V_{SW}\)> 와 <\(V_C\), \(V_{SW}\)>는 유사해야 한다. 반면에 Alice(\(V_A\))는 평점에 대해 Titanic과 Star Wars 두 factor와 상호작용이 다르기 때문에 Chalie(\(V_C\))와 다른 Factor벡터를 가질 것이다. 다음은 Star Trek의 factor벡터들과 Star Wars의 factor 벡터들은 유사성을 띌것이다. 그 이유는 Bob이 두 영화와 평점 대해 유사한 상호작용을 보이고 있기 때문이다. 정리하자면, 위 내용은 Alice와 Star Trek의 dot prouduct(즉 상호작용) 은 Alice 와 Star Wars의 것과 유사하다는 결론이 나온다.
4) Computation
다음은 계산적측면에서 FM이 어떻게 적용되는지를 본다. Eq. (1)의 직관적인 계산의 복잡도는 O(k\(n^2)\)이다. 왜냐면 모든 pairwise 상호작용항들을 계산해야하기 때문이다. 그러나 계산식을 조금 손보면 선형적으로 계산시간이 줄어든다.
Proof : Pairwise 상호작용항에 대한 factorization 때문에, 직접적으로 두 변수들에 의존하는 모델 파라미터가 없다. (즉 index( I , j) 의 파라미터) 따라서 pairwise 상호작용은 다음과 같이 재 작성될 수 있다. 이를 통해 계산 k와 n의 계산 복잡도는 O(kn)으로 줄었다. 더욱이 sparsity한 환경에서 대부분의 x는 0이다. (즉 m(x) 는 작다) 그러므로 그 합들은 0이 아닌 element들에 대해서만 계산된다. 그러므로 Sparsity한 환경에서 FM의 계산은 O(k\(\bar{m}\)\(_{D}\)) 걸린다. 즉 MF 접근과 같이 일반적인 추천시스템에서는 \(\bar{m}\)\(_{D}\) = 2 이다.
B. Factorization Machines as predictors
FM은 다양한 예측문제에 적용될 수 있다. 그 중에는
● Regression : \(\hat{y}(x)\)은 죄적화의 기준(즉 D에 대한 MLE) 혹은 예측변수로서 쓰여진다.
● Binary classification : \(\hat{y}(x)\)은 hinge loss 혹은 logit loss에서 최적화의 대상이 되는 파라미터로 사용된다.
● Ranking : 벡터 x는 \(\hat{y}(x)\)의 값 순서대로 정렬되어 있으며 (\(x^{(a)}\), \(x^{(b)}\)) ∈ D의 쌍벡터들에 대해 pairwise classification loss로 최적화를 한다.
모든 케이스에서 L2 같은 정규화 텀은 보통 오버피팅을 방기하기 위해 최적화 식에 쓰여진다.
C. Learning Factorization Machines
위에서보듯 FM은 선형시간으로 계산되는 Model equation을 밝혔다. 그러므로 FM의 파라미터들(\(w_0\), w 그리고 V)은 Gradient descent 방법론들로 학습되어 질 수 있다. (예 SGD, hinge loss, logit 등) FM의 gradient는 다음과 같다.
\(\sum_{n}^{j=1}\) Vjf\(x_j\)의 합은 I와 독립적이다. 따라서 y (x)를 계산할 때 미리 계산할 수 있다. 일반적으로 각 gradient는 고정적인 시간으로 계산될 수 있다. 그리고 모든 파라미터들은 sparsity의 환경에서 O(kn)또는 O(km(x))의 시간내로 하나의 case (x,y)마다 업데이트를 하라 수 있다.
D. d-way Factorization Machine
여태껏 2-way FM 을 설명했지만 이를 일반화 시켜 d-way FM으로 정의할 수 있다.
I번째 상관관계 항에 대한 파라미터들은 PARAFAC모델의 파라미터로 Factorize를 한다.
\(\hat{y}(x)\)에 대한 계산복잡도는 O(\(k_d\)\(n^d\))이다. 그러나 lemma 3.1에서 같은 arguments들로 linear time에 계산할 수 있다.
E. Summary
FM들은 모든 feature vector들 대신에 factorized interaction들을 사용하여 feature vector x의 값사이의 모든 가능한 상관관계들을 모델링한다. 이 방식은 두가지 장점이 있다.
1) 높은 sparsity하에서도 상호작용항을 추정할 수 있다. 특히 관측되지 않은 데이터 사이의 상호작용항에도 일반화가 가능하다.
2) 예측과 학습에 대한 시간뿐 아니라 파라미터의 숫자도 선형화하였다. 이를 통해 SGD를 사용한 최적화를 가능하게 만들었으며 다양한 loss fucntion에서 최적화를 쓸 수 있게 되었다.
다음은 svm뿐 아니라 matrix, tensor 그리고 특화된 factorization 모델들과 FM 모델사이의 관계를 볼 것이다.
Reference : https://cseweb.ucsd.edu/classes/fa17/cse291-b/reading/Rendle2010FM.pdf