最近FMとかFFMとかっていう単語で平然と殴りつけてくる同僚と働くようになったのでまたコツコツと勉強してます。
こういう環境に身を置けて自分のレベルが上がる のは良い事なんだけど何返せるのかな～とか思う今日この頃です。
1. Factorization Machineとは？
前提として、詳しく正しく知りたい人は論文読んでね。
ちょっと正しい解釈かわからないですが、Factorization Machine(FM)とは「交互作用項のモデリング方法」の一つで、モデルに入れるすべての特徴量の組み合わせの交互作用を組み込むことができます。
これだけ書くと「いやいやそんなの普通に交互作用項を全通りぶっこめばいいじゃん。」って思いますが、モデルに入れる特徴（変数）の数が多くなるとこの方針では交互作用項の数が膨れ上がってしまいます。
結果、モデルで学習しないといけないパラメーターの数も同じだけ膨れ上がってしまうので、計算に果てのない時間がかかってしまいます。
この全通りの交互作用項を近似したもので代用することで、推定しないといけないパラメーターの数を減らして計算時間を短くしようというのがFMのキモの部分だと思います。
2. こんなモデル
こんなモデルになります。
パッと見た感じよく見る回帰式っぽいですが、右のvとxがごちゃっとしている部分がいつもと違います。
そしてここが、全通りの交互作用項を近似している部分です。
iは変数のインデックスを表しているので、i個の変数（特徴）から学習するモデルとなっています。
jは変数同士の組み合わせを作るために使われる表記です。
vはn*kの行列で、kはこのモデルにおいてモデラーが自分で決めるパラメーターになります。
nは変数の数なので、感覚的にとらえるとn個の変数それぞれがk個のパラメーターで重みが付くみたいなイメージでしょうか。
<・,・>の部分はドット積で、こういった形になります。（ちょっとみにくいですが、v_if *v_jfとなってます）
つまり、n*kの行列から、(i,f)の要素と(j,f)の要素を取り出して掛け合わせ、それをk個すべて行って合計した値を出すと。
なのでここで出る値は何かしらの一つの値になるわけで、この部分が交互作用項に対する重みを表現している部分になるわけです。
よって、この式における
wとvが推定できれば、すべての交互作用項を加味した状態のモデルを学習できたことになります。
そして、wの個数は投入した特徴の数nで、vの個数は特徴の数nにモデラーが決めるパラメーターkを掛けたn*kになります。
このkの値は感覚的には大量にある交互作用の情報をどのくらいの小ささに縮約させるかという値です。上記の論文の中ではp.2の終りの方に
there exists a matrix V such that W = V・V^t provided that k is sufficiently large. This shows that a FM can express any interaction matrix W if k is chosen large enough.
とあり、kが一定以上の大きさであればどんな交互作用も表現できるとしています。また、すぐその下にスパースなデータの際には複雑な交互作用を推定するのに十分な情報が無い事が多いことから小さめのkを選ぶようにとの示唆もあります。
他にもFMの良い点は、訓練データでは起きていなかった交差に対する重みが推定される事です。これは情報をk次元に押し込めているから起こる事ですね。
重みのパラメータであるvとwの推定自体はStochastic Gradient desentで行うことができます。その辺は論文読んでいただければと。
回帰をタスクとして解くときはyはそのまま使えて、分類問題を解くときにはyの正負を利用することになります。また、正則化を加えることもできます。
3. で、Rでできんの？それ。
出来ます。
libFMexeというパッケージがあるのでそいつからlibFMというC++でFMを実装したものを使うことができます。
@siero5353さんがこちらの記事を書いているのでそちらを参考にしていただければ。