- 논문 링크(2689회 인용)
Summary
- SVM의 장점과 matrix factorization의 장점을 모아둔 factorization machines을 제안한다.
- 개별적인 변수의 latent vector뿐만 아니라 변수간의 interaction에 존재하는 latent vector도 추정한다.
- 일반적인 데이터 형태 모두를 입력값으로 넣을 수 있으며 파라미터 최적화 방법도 동일하게 gradient descent을 사용하면 된다.
- 모델 파라미터가 데이터 수에 linear하게 최적화되기 때문에 scalability을 확보한다.
Motivation
- fm은 svm의 장점을 살리면서 단점을 보완하고자 개발된 알고리즘이다.
- fm은 모든 변수들간에 interaction effect을 latent vector로 추정한다. 이를 통해 svm은 sparse 데이터에 대해 좋지 못한 성능을 보이는데 비해 fm은 sparse 데이터에도 좋은 성능을 유지할 수 있다.
- cf 문제에서 입력 데이터의 형태에 따라 다양한 알고리즘 (svd++, pitf 등)이 개발되었고 그에 따른 최적화 방법도 각자 조금씩 다르다. fm은 보다 일반적인 model equation을 제시함으로써, 이런 수고를 덜어준다.
- 또한 기존에 개발된 알고리즘은 fm을 조금 변형하여 유도됨을 보임으로써 fm의 generality을 강조한다.
Approach
Data format
fm은 일반적인 데이터 형태를 받을 수 있다고 하는데, 그러면 그 형태는 어떤지 살펴보자. 아래는 논문에서 나오는 예시다.
유저 A가 titanic 영화를 2010-01에 봤고 평점은 5점을 줬다는 데이터를 집합 $S$로 모아뒀는데, 더 다양한 feature는 아래와 같이 tabular 형태로 표현할 수 있다.
위와 같은 tabular 형태는 매우 일반적인 데이터 형태로써, svm 뿐만 아니라 일반적인 machine learning 알고리즘의 입력값으로도 들어간다. 논문에서 지적하는 것은, cf의 다양한 알고리즘이 서로 다른 입력 형태를 받기 때문에 번거롭다는 것이다. fm은 위와 같은 general predictor을 받기 때문에, 편리하고 확장이 용이하다는 장점이 있다.
Factorization machines
degree $d=2$인 fm의 model equation은 아래와 같다.
- $w_0 \in \mathbb{R}, \mathbf{w} \in \mathbb{R}^n, \mathbf{V} \in \mathbb{R}^{n \times k}$: 추정해야할 모델 파라미터이다.
- $w_0$: global bias
- 개별적인 변수 $x_i$의 effect은 $w_i$로, 변수간의 interaction은 latent vector간의 내적인 $<\mathbf{v}_i, \mathbf{v}_j>$으로 표현한다.
- 중요한 것은, $\hat{w}_{ij}$라는 하나의 값으로 추정하는게 아니라, factorize한다는 것이다.
- 변수간의 interaction을 모델링하는 부분에서, sparse data을 다루는 모델의 능력이 svm보다 낫다는 것이 논문의 주장이다.
- $<\mathbf{v}_i, \mathbf{v}_j> := \sum^k_{f=1} v_{if} \cdot v_{jf}$: latent vector간의 내적값
Parameter estimation under sparsity
fm이 어떤 면에서 svm보다 sparse data를 더 잘 모델링하는지 그 이유에 대해 살펴보자.
- 만약에 입력데이터에서 $x_1, x_2$간의 interaction을 추정하고 싶은 상황이라고 가정해보자.
- 그런데, 입력데이터에서 $x_1, x_2$가 동시에 나타난 데이터가 없을 수도 있다.
- 이런 상황에서, $x_1, x_2$의 interaction은 실제로 존재하지만 관측되지 않았을수도 있음에도 불구하고 0으로 추정된다.
- 그러나 fm은 interaction을 factorization을 통해 추정하기 때문에 이렇게 관측되지 않은 잠재 interaction의 효과에 대해서도 추정이 가능하다.
Computation
fm의 model equation을 보면 summation이 두번 들어가있고 내적까지 있으므로 시간 복잡도가 $O(kn^2)$인 것처럼 보이지만, 아래와 같이 식을 전개함으로써 시간 복잡도를 $O(kn)$까지 줄일 수 있다.
게다가 sparse 데이터는 zero 값이 많으므로 복잡도가 더 줄어들 것이다.
Factorization machines as predictors
fm은 다양한 task에 사용될 수 있다.
- regression: $\hat{y}(\mathbf{x})$가 mse loss function을 통해 최적화 된다.
- binary classification: hinge loss나 logit loss을 통해 최적화된다.
- ranking: $\hat{y}(\mathbf{x})$의 값에 따라 나열이 된다. 최적화는 입력데이터의 pairs로 진행된다.
Learning facotirzation machines
fm은 공통적으로 model equation을 가지므로 여기서 파라미터에 대한 gradient을 구하면 된다. 시간 복잡도는 앞서 $O(kn)$임을 보였다. gradient는 아래와 같다.
d-way factorization machine
2-way뿐만 아니라 일반적으로 d-way까지 확장이 가능하다.
$l$번째 interaction은 $\mathbf{V}^{(l)} \in \mathbb{R}^{n \times k_l}$의 행렬로 표현한다.
정리하면, fm이 factorization을 통해 interaction을 모델링하는 부분에서 아래의 이점을 가진다.
- 높은 sparsity을 가지는 데이터에 대해서도 interaction 추정이 가능하다. 심지어, interaction이 관측되지 않은 상황에서도 0으로 추정하지 않는다.
- 학습 시간이 데이터 수에 linear하다.
뒷부분은 fm와 svm / 다른 mf 모델을 비교하는 내용이므로 생략한다.
Results
- fm이 svm에 비해 좋은 성능을 보여준다.
- rmse가 0.91 정도인데.. 기억하기로는 mf가 0.86? 까지 나왔던 것 같아서 비교대상 모델에는 빠진 것 같다.
Conclusion
- fm이 svm에 비해 좋은 점은 1) sparse data을 잘 다룬다는 점 2) 계산 시간이 데이터의 수에 linear하다는 점 3) general model로 확장할 수 있다는 점이다.
- fm의 시간 복잡도는 $O(KN)$이고 eALS의 시간 복잡도는 $O((M+N) + |\mathcal{R}|K)$이다. fm의 복잡도가 훨씬 작은 것 같은데.. eALS가 fm에 비해 좋은 점이 무엇인지 생각해봐야겠다.
- 실험에서 다른 모델과 비교하지 않은 점이 아쉽다. 다른 모델은 0.9보다 낮게 나와서 그런 것일까..
댓글