Coda

論文メモ Factorization Machines

July 31, 2020

Factorization Machineは、Matrix factorizationのようなFactorization modelとSVMの両方の利点をもつ。 Matrix modelには疎な特徴を入力することができるが、予測のモデルに使うには汎用性に欠ける。 一方、SVMは、汎用的であるが、推薦システムで使われるような疎な特徴を扱うことができない。 Factorizatiom Machineは、両者の利点をそなえており、疎な任意の実数を要素にもつ特徴ベクトルを扱うことができる。 また、予測の計算量が線形であり、必要なパラメタの数も線形であるため、SVMのサポートベクタのように訓練データをモデルに持たせる必要がない。 そのために、大量の訓練データを使う学習も可能となる。

\(\boldsymbol{\mathrm{x}}\)を特徴とすると、2元(degree\(d=2\))のFactorization Machineは次の式をとる。 $$ \hat{y}(\boldsymbol{\mathrm{x}}):= w_0 \sum^n_{i=1}w_ix_i+\sum^n_{i=1}\sum^n_{j=i+1}\langle\mathcal{\mathrm{\boldsymbol{v}}}_i, \mathcal{\mathrm{\boldsymbol{v}}}_j\rangle x_ix_j $$

\(w_0 \in \mathbb{R}, \boldsymbol{\mathrm{w}} \in \mathbb{R}^n, \boldsymbol{\mathrm{V}}\in \mathbb{R}^{n\times k}\)はパラメタであり、\(\langle \cdot , \cdot \rangle\)はサイズ\(k\)のドット積を示す。

$$ \langle \mathcal{\boldsymbol{\mathrm{v}}}_i,\boldsymbol{\mathcal{\mathrm{v}}}_j \rangle :=\sum^k_{f=1}v_{i,f}\cdot v_{j, f} $$

\(k\)はハイパーパラメタであり、値が多いほど複雑なデータを学習できるが、過学習におちいりやすくなる。 \(\mathcal{\boldsymbol{\mathrm{v}}}_i\)は\(k\)個のfactorからなる\(i\)番目の変数を示す。 \(w_0\)はバイアス項であり、\(w_i\)は\(i\)番目の変数のはたらきの強さを示す。 \(\langle \mathcal{\boldsymbol{\mathrm{v}}}_i, \mathcal{\boldsymbol{\mathrm{v}}}_j\rangle\)は変数\(i, j\)の交互作用の強さを示す。 \(w_{i, j}\)のように1つのパラメタのかわりに、因数分解されたベクトルのドット積をもちいることで、疎な特徴を扱うことができる。 交互作用の項は、次のように式を変形できるため、\(O(kn)\)で計算できる。 $$ \sum^n_{i=1}\sum^n_{j=i+1}\langle \mathcal{\boldsymbol{\mathrm{v}}}_i,\mathcal{\boldsymbol{\mathrm{v}}}_j\rangle x_ix_j =\frac{1}{2}\sum^k_{f=1}\left({\left(\sum^n_{i=1}v_{i,f}x_i\right)}^2-\sum^n_{i=1}v^2_{i,f}x^2_i\right) $$

計算量が線形であるため、勾配降下法でパラメタを学習できる。 勾配は、\(w\)や\(v\)ごとに次の値をとる。 $$ \frac{\partial }{\partial \theta}\hat{y}(\mathcal{\mathrm{x}})= \begin{cases} 1,&\text{if}\ \theta = w_0\\
x_i,&\text{if}\ \theta =w_i\\
x_i\sum^n_{j=1}v_{j,f}x_j-v_{i,f}x^2_i&\text{if}\ \theta=v_{i,f} \end{cases} $$


論文はこちらからダウンロードできます。