Factorization Machinesを今更読みました

技術

前から気になっていたのですが、読んでいなかった Factorization Machines [S. Rendle, 2010] を読みました。

論点が明確で非常に読みやすい論文でした。それだけでなく手法自体もシンプルかつ効果的で極めて良いように思いました。私が好きなタイプの手法で、もっとはやく読んでおけばよかったという気持ちです。

提案から6年経っているので、もしかしたら今はもっと良い方法があるかもしれないのですが、自分の頭を整理する意味でもメモを書いておきます。

概要

Factorization Machines (以下FM) は、組み合わせ特徴量を扱う教師あり学習のモデルです。

特徴量ごとに {k} 次元ベクトルの重みを持たせて、組み合わせ特徴量の重みを {\langle \boldsymbol{v_i}, \boldsymbol{v_j} \rangle} という内積で表現することで、組み合わせ特徴量の疎になりやすいという問題を解決しています。

学習はSGDなどのオンライン学習が利用でき、1回の更新の時間計算量が {O(kn)} です（{n} は特徴量の数）。推定も同様に {O(kn)} です。行列計算は不要です。最高！

論文では例としてレコメンデーションを挙げていますが、疎な特徴量（単語とか）を扱う任意の問題に適用可能です（もちろん疎でなくてもよいです）。SVMのように双対形式にしなくても効率的に組み合わせ特徴量を扱えるので超便利！です。

FMでレコメンデーションをする場合、ユーザとアイテムそれぞれを特徴量として持たせます。組み合わせ特徴量を使わない場合、ユーザ・アイテム間の関連を表現できないのでこのような特徴ベクトルはよくないです。

FMであれば組み合わせ特徴量を使えるのでこういう特徴ベクトルを作ることで識別（回帰）問題としてレコメンデーションを扱えるわけです。FMはレコメンデーションに特化したモデルではないのでユーザ、アイテム以外にも工夫次第でいろいろ特徴量を盛り込めるのが利点です。

手法の説明

線形モデルでは、それぞれの特徴量 {x_i} に対して重み {w_i} を持ちます。組み合わせ特徴量というのは特徴量同士の組み合わせを特徴量として扱うもので、例えば {x_i} と {x_j} に対して重み {w_{ij}} を持ちます。（ここでは2つの特徴量を組み合わせましたが3つ以上であっても構いません）

組み合わせ特徴量は、組み合わせている特徴量すべてが非ゼロでないとゼロになってしまうので、疎になりやすいという欠点があります。

FMはこの問題を解決するために、それぞれの特徴量の重みを {w_i} というスカラーと {\boldsymbol{v_i}} という {k} 次元ベクトルの2つで表現しています。

単独の特徴量 {x_i} に対する重みは {w_i} を使い、{x_i} と {x_j} の組み合わせ特徴量に対する重みは {\langle \boldsymbol{v_i}, \boldsymbol{v_j} \rangle} という内積を使います。つまり、特徴量の組み合わせに対して重みを持つと疎になってしまうので、それぞれの特徴量に対してベクトル形式の重みを持っておいて、その内積で組み合わせ特徴量の重みを表現しよう、ということです。

まとめると、FMは以下のようなモデル（論文の式(1)）になります。第3項がついている点が普通の線形モデルと違うところです。

{ \displaystyle \hat{y}(\boldsymbol{x}) := w_0 + \sum_{i=1}^n w_i x_i + \sum_{i=1}^n \sum_{j=i+1}^n \langle \boldsymbol{v_i}, \boldsymbol{v_j} \rangle x_i x_j }

で、これの計算量なのですが、式変形によって {O(kn)} であることがわかります（詳しくは論文を参照）。

また、学習はSGDなどのオンライン学習を利用することができ、それぞれの重みに対して定数時間で微分係数を計算できます（こちらも論文を参照）。特徴量の数が {kn + n + 1} 個なので1回の学習も {O(kn)} となります。

実装

実は、著者によって libFM というライブラリが提供されています。いい・・・