[論文メモ] Factorization Machines

はじめに

• 他の論文を読むために読むので、まとめは雑です。
• Factorization Machines

Introduction

• SVMがsparseなデータに対して上手くいかない理由を示す。
• tensor factorization modelの欠点として、
  • 標準的な予測問題に使えない。(予測値が実数など)
  • 個々のタスクに対して学習アルゴリズム等を設計する必要がある。
• この論文では新しい"Factorization Machine(FM)"という新しいモデルを提案する。
  • SVMのようにジェネラルな予測モデルであるがスパースなデータにも活用できる。
  • このモデルは線形の時間とパラメータで学習することができる。

Factorization machine

Factorization machine model

Model Equation

• defree $d=2$ のFMのモデルは下記の数式で表すことができる。
  • 式(1) $\hat{y}(x) := w_0 + \sum_{i=1}^n w_i x_i + \sum_{i=1}^n \sum_{j=i+1}^n x_i x_j$
• ここで学習対象となるモデルパラメータは
  • $w_0 \in R$
  • $w \in R^n$
  • $V \in R^{n \times k}$
• また$k$はハイパーパラメータ。
• $d=2$のFMは変数の単体とペアを捉えている。
  • $w_0$はバイアス
  • $w_i$ は $i$ 番目の変数の寄与度
  • $\hat{w}_{i,j}:=$ は $i$, $j$ 番目の交差項の寄与度。
    • ここで $\hat{w_{i,j}}$ を直接学習させるのではなく、$v_i$ と $v_j$ を介して計算している。次元が大きくなると組み合わせ数が膨大になり $\hat{w}_{i,j}$ を直接計算するのは難しい。特にスパースなデータでは精度が下がる。

Expressiveness

• 正定値行列 $W$ に対して$k$が十分に大きいとき、$W=V \cdot V^t$ となる$V$が存在する。
• つまり、$k$ が十分大きときにFMは任意の $W$ を表現することができる。
• しかし、スパースな状況ではデータが十分ではなく$k$を十分大きく取ることは難しい。

Parameter Estimation Under Sparsity

Computation

• 式(1)のまま計算しようとすると $O(k n^2)$ となるが、式変形することで線形の時間で計算することができる。

Factorization machine as predictor

• FMは様々な問題に適用することができる。
  • 回帰
    • 最小事情誤差を使って最適化する。
  • 2値分類
    • hinge loss や logit lossを使って最適化する。
  • ランキング
    • pairwise classification lossを使う
    • 詳しくは T. Joachims "Optimizing search engines using clickthrough data"
• どの問題でもオーバーフィッティングを防ぐためにL2正則化を行う。

Learning Factorization Machines

• $\hat{y}$の微分は$O(1)$で計算することができる。
• 全て変数の更新は$O(kn)$、またはスパースのときは$O(k m(x))$。
• 実装は LIBFM で公開されている。

d-way Factorization Machine

• ここまで紹介してきたFMは2次元だったが、簡単に$d$次元に拡張することができる。