論文メモ 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} $$

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