Field-aware Factorization Machines for CTR Prediction

original paper: http://www.csie.ntu.edu.tw/~cjlin/papers/ffm.pdf

概要

FMs では性別だろうが地名だろうがお構いなしに、one hot vector でエンコードしたものを並べたものを入力 $x$ として

ϕ : R^{N} \to R

ϕ (x) = b + \sum_{i} w_{i} x_{i} + \sum_{i < j} ⟨ v_{i}, v_{j} ⟩ x_{i} x_{j}

としたのだった. ここで $w_{i}$ はスカラー値で、 $v_{i}$ は適当な $k$ 次元のベクトル.

FFMs はその入力のフィールド (e.g. 性別, 地名) まで考慮しようというもの. その分パラメータは増えるが.

実装

作者等による LIBFFM がある.

この Download のとこを見ると

Warning: FFM is prone to overfitting. See README in the package before using.

という警告がある. なるほど.

FFMs

入力 $x$ の成分に関してフィールドが $F$ 個 ( $f_{1}, f_{2}, \dots, f_{F}$ ) あるとする. FMs の肝は相互作用 $⟨ v_{i}, v_{j} ⟩$ であるが、これに、相手のフィールドを考慮させる. すなわち、 $x_{i}$ に対応するベクトル $v_{i}$ に、どのフィールドへの作用かの情報を持たせる. 今まで $v_{i}$ 一個だったのを、

v_{i, 1}, \dots, v_{i, f}

と、 $F$ 個にして、

ϕ (x) = b + \sum_{i} w_{i} x_{i} + \sum_{i < j} ⟨ v_{i, f_{j}}, v_{j, f_{i}} ⟩ x_{i} x_{j}

とする. ここで $f_{j}, f_{i}$ はそれぞれ、 $x_{j}, x_{i}$ に対応するフィールド. $v_{i, f_{j}}$ は $x_{i}$ のフィールド $f_{j}$ への作用に相当する.

パラメータ数、計算量

パラメータ数は FMs が $n k$ だったのに対して $n F k$ 個になる. 計算量は FMs では素朴に実装して $O (n^{2} k)$ 、最適化して $O (n k)$ であったが、 FFMs では特に最適化は提示されておらず、 $O (n^{2} k)$ のままとなる.