Help us understand the problem. What is going on with this article?

Factorization Machinesについて調べてみた

More than 5 years have passed since last update.

21日のアドベントカレンダーを2日遅れでお届けしております。
忘年会シーズンに入る前に調べておけばよかったと反省するばかり。二日酔いが辛い…。

気を取り直して、今回はFactorization Machines(以下、FM)について書いていきます。
1ヶ月ほど前にRecSys2014読み会で知ってから結構気になっていたで、調べてみた結果をまとめています。
FMはRendleさんが2010年にICDMに出したのが初出の様なので、割りと前から存在していたのですが、完全にノーマークでした。研究はRendleさんがほぼメインで行っている様ですが、KDD2014のNetflixが出しているまとめにも載っているので、業界的には結構有名なんだろうと思います。ノーマークだったけどorz

はじめに

協調フィルタ系のレコメンドにトレンドについては、
Collaborative Filtering(CF)
→ SVD / Matrix Factorization(MF)
→ SVD++
→ time-SVD / Pairwise Interaction Tensor Factorization(PITF) / Factorizing Personalized Markov Chains(FPMC)
という流れかなと個人的には思っていますが、time-SVDあたりからはUser-ItemのRating以外の要素を取り込む様な拡張になっています。
こういった派生系はだいたい特定のケースに特化したモデルがちらほら生まれてきて、特化したケースを一般化した汎化モデルが出てくるパターンだと思います。
FMはこの汎化モデルにあたる位置付けです。

Factorization Machinesとは?

とりあえず、SVD/MF/FMの違いをイメージで書いてみました。
 

SVD_MF_FM.png

 
FMはSVDやMFとはRatingの持ち方が異なっています。
SVDやMFは1行に1ユーザの評価データを複数格納しており、これをユーザとアイテムの特徴ベクトルをそれぞれ取り出しています。
これに対して、FMは1評価を1行で表し、取り出すのはユーザとアイテムの交互作用(pair-wise)の特徴ベクトルで、SVDやMFとは注目している対象が異なります。

FMの予測式は以下の様になります。

\hat{y}(\mathbf{x}):= w_0 + \sum_{i=i}^nw_ix_i + \sum_{i=1}^n\sum_{j=i+1}^n<\mathbf{v}_i ,\mathbf{v}_j>x_ix_j

$\mathbf{x}$は上の図のFMの図の1行に該当するので、ユーザとアイテムの両方に1が立つ感じですね。

Netflixの資料には$f(\mathbf{x})=b+w_u+w_i+\mathbf{v}^T_u\mathbf{v}_i$と書いてあるので、こちらの方がMFを知ってる人には分かりやすいかも。

$\mathbf{w}\mathbf{x}=w_u+w_i$と思ってもらえれば上の式との対応は伝わるかな。

なので、FMではユーザバイアス$w_u$、アイテムバイアス$w_i$に加えて、ユーザとアイテムの交互作用$\mathbf{v}^T_u\mathbf{v}_i$を使って予測をっているということになります。

どの辺りが汎化モデルなのか?

この相互作用を時間とかContextとかを自由に入れられます。

20141223-214246.png

引用元:http://www.slideshare.net/xamat/kdd-2014-tutorial-the-recommender-problem-revisited

上記の例では、UserとItem以外にTimeという閲覧タイミングを入れています。
こうすることで、User✕Item✕Timeの交互作用をモデルで扱うことができます。

Rendleさんの元論文では以下の様な例を挙げており、UserとItem以外を自由に入れられる、且つ幾つでも入れることができるそうです。
なので、時間だけでなく、場所や気分といったContextを入れることも可能です。

20141223-215118.png

引用元:http://www.ismll.uni-hildesheim.de/pub/pdfs/Rendle2010FM.pdf

推定方法

以下の手法で推定が可能です。

  • SGD
  • Adaptive SGD
  • ALS
  • MCMC

推定時はL2正則化を掛けて行います。

性能

Matrix Factorizationよりはやっぱりいいらしい。
KDD Cup2012のCTR予測ではRendleさん1人で挑んで2位だったとのこと。

どうやったら使えるのか?

Rendleさんお手製のlibFMというライブラリがあるので、それを使うのがおそらくベストの様です。
FMはMatrixの持ち方も変わっており、普通にRatingの行列を作ると凄い量になってしまいますが、libFMの中ではRating行列の共通部分を集約して持つようにしたりしていて、メモリ量の削減にもかなり力を入れてあります。
現状使うのであれば、libFMを使うか、libFMベースで手を入れるのが良さそうです。

実行サンプル

1回試して力尽きました。
そのうち他手法との比較結果を挙げようと思います。

wwacky
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした