Factorization Machinesについて調べてみた

  • 87
    いいね
  • 0
    コメント
この記事は最終更新日から1年以上が経過しています。

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回試して力尽きました。
そのうち他手法との比較結果を挙げようと思います。

この投稿は 株式会社リクルートテクノロジーズ Advent Calendar 201421日目の記事です。