paper/

Factorization Machines (FMs)

FMs とは何か

超スパースなデータにも使える予測器. 線形分類器の拡張になっている. 基本的に回帰モデルの形をしているが、分類器としても使えるし、スコアを計算するものだと思えばランキングを予測するようにも使える. スパースでデータ量が増えても線形程度にしか時間及び空間が増えない.

手法の概要

データ \(x \in \mathbb{R}^n\) から \(y\) を予測するモデルとして

\[\hat{y} = w_0 + \langle w, x \rangle + \sum_{i < j} \langle v_i, v_j \rangle x_i x_j\]

とする (この形を 2-way FM という).

ここで

第二項までは通常の線形分類器であり、 第三項はデータの成分間の相互作用 (interaction) を表現している. \(\langle v_i, v_j\rangle\) は相互作用の為の重みである. これ自体を \(i, j\) 間の相互作用 (interaction) と呼ぶ. わざわざ一個の重み \(w_{i,j}\) として表現をしないのは、 陽に \(w_{i,j}\) を計算し保持しておくと、\(O(n^2)\) の空間が必要になるし、予測の計算も \(O(n^2)\) 掛かる. 適当な \(k\) を決めて \(V\) を持つことにすると、空間は明らかに \(O(nk)\) で済み、 後述するように予測の計算も \(O(nk)\) で済む.

データの持ち方

データの持ち方が若干特殊. 基本的に素性を何でも突っ込む (ベクトル結合).

例えば、ユーザー \(U\) と、映画 \(M\) があって、 ユーザーに関する素性 \(V\) と映画に関する素性 \(N\) があったときに、 ユーザー \(u \in U\) の映画 \(m \in M\) に対する評価値 \(y \in \mathbb{R}\) を予測することを考える. (この例は元論文にあるものを参考にしている.)

データ \(x\) (列ベクトル) を次のように作る.

これらを結合して \(|U|+|M|+\cdots\) 次元の列ベクトル \(x\) とする.

このようにしてデータ \[\mathcal{D} = \{ (x_i, y_i) \}_i\] を作る.

元論文では、この列ベクトル \((x_i)_i\) を縦に並べて大きな行列としている.

耐スパース性

FMsはデータが超スパースであることを仮定している. そのような場合、 例えばユーザー \(u_1\) の 映画 \(m_1\) に対する評価がデータに含まれないことが多い. ということは、\(u_1\) (に相当する成分) と \(m_1\) (に相当する成分) との相互作用を推定することは出来なさそうに思える. FMs が上手いのはそれを直接推定することはせず、 \(v_{u_1}\) 及び \(v_{m_1}\) を推定して、その内積を相互作用としていることである. それらは別な関係、例えば \(u_1\)\(m_2\) との関係、\(u_2\)\(m_1\) との関係などから推定出来るかもしれない.

予測の計算方法

初めに示した計算式そのままだと \(O(kn^2)\) 掛かりそうだが、式変形を施すと \(O(kn)\) で済む.

すなわち、第三項であるが (簡略のため先に二倍したものを考えると)、

これなら \(O(kn)\) で計算できる.

最適化 (学習)

微分は容易だし、好きな最適化ソルバを流用すれば良い.

\(d\)-way FM

先述した形のものは、ちょうど2つの成分の相互作用だけを見るので 2-way FM と呼ぶ. これは一般化できて、ちょうど \(d\) つ成分の相互作用を考慮する

\[\hat{y} = w_0 + \langle w, x \rangle + \sum_{i_1 < i_2 < \cdots < i_d} \left( \prod_i x_i \right) \langle v_{i_1}, v_{i_2}, \ldots v_{i_d} \rangle\]

も考えられる. これを \(d\)-way FM と呼ぶ. ここで、 \(\langle v_1,v_2,\ldots,v_d \rangle\) は 成分間の積の和で \(\sum_i \sum_k v_{i,k}\) と定める.

SVM との比較

行列分解との比較