[Recommender System] - Factorization Machine 리뷰 + code

 

 

본 포스팅은 링크의 글을 번역한 것이다. 글을 옮기면서 부족한 설명이나 내용은 Factorization Machine 원 논문의 내용을 추가하여 살을 붙여 두었다. 원 블로그의 글은 FM을 이용하여 추천 영역에서의 cold-start 문제를 해결하는 방법에 대한 짧은 설명과 코드를 함께 기술한 글이다. 블로그에서는 tffm을 이용하여 예제를 만들었지만, 현재 사용중인 라이브러리가 xlearn인 관계로, 본 포스팅에서는 xlearn을 이용한 tutorial 코드를 작성하였다. 내용은 생략하고, 코드만 궁금한 사람은 링크로 가면 된다.

 

 

---

 

 

 

데이터 분석가가 개인화 추천을 잘 수행하기 위해선, 최신 머신 러닝을 잘 적용하는 것도 중요하다. 추천 시스템에서의 가장 잘 알려진 알고리즘들이 대부분은 잘 동작한다. 하지만 알고리즘과 모델들을 조금씩 점진적으로 바꾸어 나간다면, 고객에게 더욱 좋은 추천 경험을 줄 수 있을 것이다. FM 모델은 바로 이러한 모델로, 개인화를 위해 머신 러닝을 추천 영역의 기술로 개량한 것이다. Matrix/Tensor Factorization 혹은 Polynomial regression과 같은 Generalization을 매우 잘 수행하는 알고리즘으로 입증되어 있다.

 

대부분의 추천 문제들은 (user, item, rating) 으로 이루어진 튜플셋을 데이터로 사용한다. 이 데이터들을 이용하여, CF의 다양한 방법들로 좋은 결과들을 도출할 수 있었다. 하지만 대부분의 real-world 에서는 (tags, categories, genres) 등과 같은 풍부한 메타데이터가 오히려 더 좋은 데이터셋으로 쓰인다. 그래서 이론적으로는 rating이 매겨진 튜플셋을 우선적으로 고려하지만, 실제 추천 시스템에서는 메타데이터를 고려하는 것이 더 중요하다. FM을 사용하면, 이러한 feature-rich 데이터셋을 사용하기에 좋다. 그래서 이 모델을 통하여 더 많은 extra 피처들을 모델에 집어넣을 수 있게 되었고, 변수간의 interaction(Matrix Factorization 에서의 latent product 처럼, auto generalization을 의미하는 것 같다)을 파라미터 d로써 모델링할 수 있게 되었다. 

 

 

---

 

 

 

1) Model Equation

 

먼저, degree d = 2인 Factorization Machine의 모델은 다음과 같이 정의된다. 다시 얘기하겠지만, degree가 2라는 것은 latent vector를 조합하는 후보의 수를 2개로 하겠다는 것이다.

 

 

 

이제 여기에서 추정되어져야 하는 파라미터들은 다음과 같다.

 

 

 

 

여기서부터는 기본적인 Matrix Factorization 알고리즘을 잘 이해하고 있어야 Factorization Machine을 수월하게 이해할 수 있다. 원 블로그에서는 만약 x 피처가 user와 item으로 두개의 non-zero position matrix만으로 이루어져 있다면, 정확하게 MF와 FM이 같은 수식이라고 설명해 놓았다. 이 설명이 매우 함축적이지만 중요한 설명이다. 

 

Matrix Factorization의 개념을 다시 한 번 복기해보자. User X Item을 index로 하여 rating으로 value가 채워진 Matrix R이 있다고 하자. 이를 두개의 latent vector로 분해하여 V1(u X k), V2(i X k) 로 나타낼 수 있다. 이 때 추정해야되는 변수는 global bias W0, V1 bias W_u, V2 bias W_i, latent vector W(혹은 V)이다. 이 때 k가 늘어날 수록 W의 변수가 많아지기 때문에, R^가 R에 근사할 수 있는 변수를 더 많이 계산하게 된다. 또한 W1, W2의 shape은 k가 1인 V1, V2와 동일한 shape을 가진다.

 

만약 수도코드로 표현하자면

V1 = np.random(len(User i), k), V2 = np.random(len(Item u), k) 로 선언할 수 있고, 

predict 계산시에는 V1 dot V2.transpose() 로 나타낼 수 있다. 즉 아래와 같은 equation이라는 것이다.

 

 

 

 

 

위 식을 기반으로 한다면, MF의 데이터셋은 단순히 행렬 하나로만 구성될 것이다. 이제 FM의 equation을 이해하기 위해 FM의 데이터셋을 살펴보자.

 

 

 

user와 item을 row, column index로 하는 데이터와는 구성이 약간 다르다. 위 데이터셋에서 User에 대한 sparse vector(one-hot encoding)을 x1, Item에 대한 vector를 x2, 그리고 추가적인 피처들을 x_n 이라 하자. 그리고 x1에 대한 latent vector를 V1, x_n에 대한 latent vector를 V_n이라고 할 것이다. MF와 마찬가지로, V의 row v_i는 i-th variable with k factor를 의미한다. 이제 다시 FM의 equation을 보면, 수식에 FM의 아이디어가 그대로 녹아있다는 것을 확인할 수 있다.

 

우선 y^(x)의 두번째 항을 살펴보자. MF에서는 W_u, W_i 를 구하는 반면, FM에서는 W_i X x_i를 구한다. MF에서의 두개 latent vector들의 각각의 row에 대한 고유한 bias가 FM에서도 마찬가지로 구해진 것이다. 달라진 것은 MF에서는 user, item으로 구성된 matrix의 index 마다 이를 구했지만, FM에서는 x_i 마다 이를 구한 것 뿐이다.

 

다음으로 세번째 항을 보자. 수식이 의미하는 바는, MF에서 user latent X item latent 를 통해 rating을 계산해 주었던 것을, sum(x_i latent vector X x_i+1 latent vector)로 해주겠다는 것이다. 이 수식의 아이디어는, 변수간의 latent vector 조합을 전부 고려하여 rating을 도출해내겠다는 것이다. 즉 Matrix Factorization 계열 알고리즘의 핵심 아이디어와, polynomial regression 계열 알고리즘의 핵심 아이디어를 결합했다고 볼 수 있다(Wide and Deep 알고리즘과 아이디어가 매우 유사하다. 차이점은 polynomial product를 자동으로 하는 FM이 더 간단하게 느껴진다는 것). 이렇게 함으로써 degree가 2인 FM은 모든 두 변수간의 pairwise interaction을 잡아낸다.

 

일반적으로 sparse한 환경에서는 피처간의 interaction이 매우 독립적으로 나타나는 경향이 있다. 하지만 FM을 통해 interaction을 구하면 피처간의 독립성을 깨기 때문에 매우 잘 작동한다고 한다. 이 말에 대해 예시를 들어 이해해보자. 만약 A라는 유저가 X라는 영화를 평가한 적이 없다고 하자. Polynomial product 관점의 접근이라면, A는 X를 평가한 적이 없기 때문에 interaction은 0이 나올 것이다. 하지만 Factorization을 통해 interaction을 계산하게 되면, X에 대한 잠재적인 평가를 얻어낼 수 있는 것이다. 이는 MF 계열의 모든 알고리즘의 장점이라고 할 수 있다. 조금 더 modeling 친화적인 관점에서 보자면 latent vector들의 interaction, 즉 dot product 과정은 cosine 함수와 같이 유사도를 구하는 개념이기 때문에 hidden feature간의 유사도를 평가한다고 할 수 있다.

 

 

---

 

 

2) Model complexity

 

만약 위의 equation대로 FM이 학습을 진행한다면, O(k*n^2)의 복잡도를 가질 것이다. 하지만 똑똑하게도 논문의 저자는 이를 linear time으로 줄여버렸다. 증명은 다음과 같다.

 

 

 

 

 

3) d-way Factorization Machine

 

2-way(degree = 2) FM을 위에서 살펴보았다. 이를 일반화한 d-way FM의 수식은 다음과 같다. 

 

 

 

수식은 매우 어려워 보이지만 2-way에서 확장하여 생각하기에 어렵지 않다. d-way FM 역시 마찬가지 방법으로 linear 하게 공식을 refomula 하였다. 이를 원 논문에서는 libFM 이라는 라이브러리를 직접 구현하여 제시하였고, 자세한 수학적 논의는 생략하였다.

 

 

 

---

 

 

 

4) 결론

 

FM 모델은 가능한 모든 피처간의 interaction을 full-parametrized one 대신에 사용한다. 이를 통해 매우 희소한 데이터에서도 관계를 추정할 수 있다는 것을 의미한다. 또한 SVD, SVM등의 알고리즘보다 속도나 성능 측면에서도 월등하게 좋은 알고리즘이다. 논문에서는 이에 그치지 않고 본격적인 자랑질 다른 알고리즘과의 비교를 서술하였다. 대상이 되는 알고리즘은 SVD, SVM이다.

 

 

 

5) FFM

 

FM의 variance 중에 하나인 FFM(Field aware Factorization Machine)은, FM의 order interaction의 약점을 보완한 방법이다. FM이 하나의 feature에 대해 하나의 latent vector만 갖고 있기 때문에, latent vector A,B,C 가 있다고 할 때 A-B, A-C의 영향력을 다르게 구분해주어야 하는 상황을 해결하지는 못한다. FFM은 latent vector에 차원을 하나 더 추가해서, A가 상황마다 다른 대처를 하도록 만들어준다. 얼마 전에 애플 펜슬을 산 김에, 이를 그려서 시각화 해보았다(..)

 

하나의 피처에 대응하는 FM의 latent vector 조합과는 달리, FFM은 field라는 차원을 하나 더 가지기 때문에 상황에 맞는 더욱 정교한 조합이 가능해진다. FFM이 성능적으로 조금 느리다는 것을 제외하면, 복잡한 피처를 구성하는 상황에서는 일반적으로 더 잘 동작하는 것 같다.

 

 

6) Example code

 

지금까지의 내용을 링크의 코드에서 실행해 보았다. 데이터 전처리 부분부터 공개된 자료를 찾기 힘들고 귀찮아서 그냥 타이타닉 데이터로 전처리부터 실행해보았다. tffm, libFM, fastFM 등 모두 사용해 보았지만 모듈중에서는 xlearn이 가장 간결하고 빠르다(라고 개발자가 주장하였다). 구현이 크게 어렵지 않으니, 시간이 나면 라이브러리를 코딩해보는 것도 좋을 것 같다.