Factorization Machine (FM) についての私的まとめ

# 概要

Factorization Machine (FM) の性質についての確認と, 最近の研究動向の調査についてのまとめです. 以下について言及しています
- FMの特徴を従来の線形モデルなどと対比して説明
- 現在使用可能なFMの実装と, それぞれの長所短所を紹介
- 最新の研究動向についてもいくつかピックアップ

# FM の特徴
Rendle (2010)はサポートベクターマシン (SVM) などスパースなデータの学習に失敗する従来のアルゴリズムに対する代案としてFactorization Machine (FM, 分解器) を提案した. スパースなデータは, 例えばカテゴリカル変数, bag-of-word だったり, リコメンドシステムなどでよくありうる.  基本的なSVMは超分離平面で線形分離できるような分類タスクのみ良好なパフォーマンスを発揮し, 非常にスパースなデータではカーネル空間をうまく学習できないことが多い一方で, 従来スパースデータの学習に向いているとされていたテンソル分解モデル (tensor factorization model) は入力データに制約があった. 彼の提案するFMは名前の通りパラメータの行列を因数分解して表現するモデルで, そういう意味では特異値分解 (SVD) や主成分分析 (PCA) などと似ている. しかし, FM は以上に挙げた従来のモデルの問題を解決し, 以下のような長所をアピールしている.</p>
<ul>
<li><p>SVMなど既存の方法ではうまくいかないような, 非常にスパースなデータでも学習できる</p></li>
<li><p>時間計算量のオーダーが線型であり, 大きなデータにも応用しやすい</p></li>
<li><p>従来のfactorization modelと違い, データの形式に制約がない</p></li>
</ul>
<p>なお, 今回は推薦システムではなく分類タスクへの応用を念頭に置いて解説する.</p>

# 従来の多項式モデル
<p>一番簡単なFMのモデルは2つの特徴量の交差項に対する相互効果を考慮する, 2元FM (2-way FM) である. これを従来の線形モデルとの違いで比較していく. なお, ここでの説明は<a class="citation" href="#ref-juan2015Fieldaware">Juan, Zhung, and Chin (2015)</a> のスライドとほぼ同じである.</p>
<p><span class="math inline">$\boldsymbol{x}$</span> を特徴行列から取り出した <span class="math inline">$D$</span>次元の特徴ベクトルとする. FMはスパースデータを考慮しているので, カテゴリカル変数をone-hot encodingで変換して次元が大きくなった状態を想像してほしい. $\boldsymbol{x}$と正解ラベル$y$のペアのインスタンス <span class="math inline">$(\boldsymbol{x}^{(n)},y^{(n)})$</span> を考える. 従来的な線型モデルだと, <span class="math inline">$\boldsymbol{x}$</span>と同じ長さのパラメータベクトル <span class="math inline">$\boldsymbol{w}\in\mathbb{R}^{D}$</span>との内積で以下のように表現したモデルを学習させる.</p>

$$
\begin{aligned}
\phi(\boldsymbol{x},\boldsymbol{w}):= & \left\langle \boldsymbol{w},\boldsymbol{x}\right\rangle =\sum_{i=1}^{D}w_{i}x_{i}\end{aligned} \tag{1}
$$

<p>ここで <span class="math inline">$\left\langle \boldsymbol{w},\boldsymbol{x}\right\rangle$</span> とは<span class="math inline">$\boldsymbol{w},\boldsymbol{x}$</span> の内積を表す. 従来のやり方では線型モデルに相互作用項を追加するには以下のように2次多項式項を追加する.</p>

$$
\begin{aligned}
\phi_{\mathit{poly2}}(\boldsymbol{x},\boldsymbol{w}):= & \left\langle \boldsymbol{w},\boldsymbol{x}\right\rangle +\sum_{(i,j)\in C}w_{i,j}x_{i}x_{j}\end{aligned}
\tag{2}
$$

<p><span class="math inline">$C$</span> は, <span class="math inline">$\{1,\cdots,D\}$</span> までの <span class="math inline">$D$</span> 個の要素の組み合わせ全体を表す集合である. つまり, 2つの特徴 <span class="math inline">$x_{j},x_{k}$</span> の積 <span class="math inline">$x_{j}x_{k}$</span> が<span class="math inline">$D(D-1)$</span> 通りあり, それぞれに対してパラメータ <span class="math inline">$w_{j,k}$</span> を用意していることになる. ただし <span class="math inline">$D$</span> の大きさ次第では計算困難になるので, 実際には組み合わせ <span class="math inline">$C$</span> の一部だけを使う場合が多いだろう. しかし, どれを使うかの取捨選択にはやはりコストがかかる. そして, 特にデータのほとんどがカテゴリカル変数で, これらをone-hot encodingしている想定では, <span class="math inline">$D$</span> が非常に大きくなることが予想される.</p>

# FM の利点

<p>一方でFMは<a class="citation" href="#ref-rendle2010Factorization">Rendle</a> によって以下のように定義されている.</p>
<span class="math display">

$$
\begin{aligned}
\phi_{\mathit{FM2}}(\boldsymbol{x},\boldsymbol{w}):= &amp; w_0 + \left\langle \boldsymbol{w},\boldsymbol{x}\right\rangle +\sum\_{i=1}^{D}\sum\_{j=i+1}^{D}\left\langle \boldsymbol{v}\_{i},\boldsymbol{v}\_{j}\right\rangle x\_{j}x\_{j}\nonumber \\\\
= &amp; w\_0 + \left\langle \boldsymbol{w},\boldsymbol{x}\right\rangle +\sum\_{(i, j)\in C}\left\langle \boldsymbol{v}\_{i},\boldsymbol{v}\_{j}\right\rangle x\_{j}x\_{j}\end{aligned}\tag{3}
$$

</span> 
<p><span class="math inline">$\boldsymbol{v}\_{i},\boldsymbol{v}\_{j}$</span> は長さ <span class="math inline">$k$</span> のベクトルで, 関連研究では<strong>潜在ベクトル</strong> (latent vector) と呼ばれることが多い. 長さ <span class="math inline">$k$</span> は任意に決められるハイパーパラメータである.</p>

<p>多項式モデルとFMがどう違うのか比較してみる. <span class="math inline">$\hat{w}_{i,j}=\left\langle \boldsymbol{v}_{i},\boldsymbol{v}_{j}\right\rangle$</span> を$i,j$成分とするパラメータ行列を <span class="math inline">$\mathbf{W}$</span> で表すと, これに対応する FM のパラメータは, <span class="math inline">$\mathbf{V}\mathbf{V}^{\top}$</span> である (<span class="math inline">$\mathbf{W}$</span> が正定値行列という前提). <span class="math inline">$\mathbf{V}$</span> は <span class="math inline">$\boldsymbol{v}_{1}\cdots\boldsymbol{v}_{D}$</span> を積み上げた行列のことである. <span class="math display">これを$\mathbf{W}$の近似という意味で, 以降は$\hat{\mathbf{W}}$と表す.</p>
<span class="math display">

$$
\begin{aligned}
\mathbf{V}:= &amp; \begin{bmatrix}\boldsymbol{v}\_{1}^{\top}\\\\
\vdots\\\\
\boldsymbol{v}\_{D}^{\top}
\end{bmatrix},\\\\
\hat{\mathbf{W}}=\mathbf{V}\mathbf{V}^{\top}= &amp; \begin{bmatrix}\boldsymbol{v}\_{1}^{\top}\\\\
\vdots\\\\
\boldsymbol{v}\_{D}^{\top}
\end{bmatrix}\begin{bmatrix}\boldsymbol{v}\_{1} &amp; \cdots &amp; \boldsymbol{v}\_{D}\end{bmatrix}\\\\
= &amp; \begin{bmatrix}\boldsymbol{v}\_{1}^{\top}\boldsymbol{v}\_{1} &amp; \cdots &amp; \boldsymbol{v}\_{1}^{\top}\boldsymbol{v}\_{D}\\\\
\vdots &amp; \ddots &amp; \vdots\\\\
\boldsymbol{v}\_{D}^{\top}\boldsymbol{v}\_{1} &amp; \cdots &amp; \boldsymbol{v}\_{D}^{\top}\boldsymbol{v}\_{D}
\end{bmatrix}\\\\
= &amp; \begin{bmatrix}\left\langle \boldsymbol{v}\_{1},\boldsymbol{v}\_{1}\right\rangle  &amp; \cdots &amp; \left\langle \boldsymbol{v}\_{1},\boldsymbol{v}\_{D}\right\rangle \\\\
\vdots &amp; \ddots &amp; \vdots\\\\
\left\langle \boldsymbol{v}\_{D},\boldsymbol{v}\_{1}\right\rangle  &amp; \cdots &amp; \left\langle \boldsymbol{v}\_{D},\boldsymbol{v}\_{D}\right\rangle 
\end{bmatrix}\end{aligned}
$$

</span>
<p>推薦システムへの応用では, ユーザー属性・商品属性という2軸でのデータ<strong>を行列の因数分解</strong> (matrix factorization) をする, と説明される事が多い<a href="#fn1" class="footnote-ref" id="fnref1"><sup>1</sup></a>. FM も2つの特徴の相互作用効果を分解するという点でこのアイディアを受け継いでいるといえる.</p><p><a class="citation" href="#ref-rendle2010Factorization">Rendle (2010)</a> は FM の利点を3つ挙げている.</p><p>1つは, <span class="math inline">$\mathbf{W}\simeq\hat{\mathbf{W}}$</span>となる程度に <span class="math inline">$k$</span> の大きさを調整できるということである. FMを使わずに多項式モデルで相互作用をすべて表現しようとすれば, <span class="math inline">$D(D-1)/2$</span> 個のパラメータが必要になる. しかしFMでは, 例えば <span class="math inline">$k=1$</span> とすれば, FM の相互作用の係数が <span class="math inline">$v_{i}v_{j}$</span> で表現され, パラメータの数も <span class="math inline">$D(D-1)/2$</span> から <span class="math inline">$D$</span> 個に減り多項モデルよりも単純になる. 一般にFM ではパラメータ数が <span class="math inline">$Dk$</span> 個となり, <span class="math inline">$k$</span> を調整して <span class="math inline">$\mathbf{W}$</span>より小さな行列 <span class="math inline">$\mathbf{V}$</span> だけを使って相互作用を表現可能である. <span class="math inline">$k$</span> を調整することで計算量を減らせるということである (最適な <span class="math inline">$k$</span> の大きさはデータに依存するが, 少なくとも <span class="math inline">$D$</span> より大きくする意味はないはず).</p><p>2つ目は, スパースなデータへの強みである. 従来の多項式モデルでは, <span class="math inline">$w_{i,j}x_{i}x_{j}$</span> というふうに組み合わせごとに個別に交互作用パラメータを用意して学習する必要があった. しかしスパースなデータではほとんどの<span class="math inline">$x_{i}, x_{j}$</span> がゼロになり, さらにその積となるとゼロでない成分はいっそう少なくなるので実際にはほとんど計算できない. しかしFMでは <span class="math inline">$x_{i}x_{j}$</span> の交互作用の大きさを <span class="math inline">$\left\langle \boldsymbol{v}\_{i},\boldsymbol{v}\_{j}\right\rangle$</span> , つまり, <span class="math inline">$x\_{i},x\_{j}$</span> それぞれに固有なベクトルの内積で表現している. よって, 相互作用成分の片方/両方がゼロでもどこかで非ゼロな <span class="math inline">$x\_{i},x\_{j}$</span> が現れていればパラメータ <span class="math inline">$\boldsymbol{v}\_{i},\boldsymbol{v}\_{j}$</span> を学習できる. これはFMが目的の相互作用成分のないデータからも交互作用効果を間接的に学習できることを意味する. <a class="citation" href="#ref-rendle2010Factorization">Rendle (2010)</a> では, 極端にスパースなデータでもうまく学習できたという実験結果を見せている.</p>
<p>3つ目が, 計算の容易さである. 単純に考えるとFM の相互作用項部分の計算時間は <span class="math inline">$O(kD^{2})$</span> になるが, 工夫することで線形時間 <span class="math inline">$O(kD)$</span> で計算できる. なぜなら以下のように変形できるため.</p>
<span class="math display">

$$
\begin{aligned}
\sum\_{i,j}\left\langle \boldsymbol{v}\_{i},\boldsymbol{v}\_{j}\right\rangle x\_{i}x\_{j}= & \frac{1}{2}\sum\_{f=1}^{k}\left(\left(\sum\_{i=1}^{D}v\_{i,f}x\_{i}\right)^{2}-\sum\_{i=1}^{D}v\_{i,f}^{2}x\_{i}^{2}\right)\end{aligned}
$$

</span>
<p>なお, 2次多項式モデルの場合は, <span class="math inline">$O(D^{2})$</span> である<a href="#fn2" class="footnote-ref" id="fnref2"><sup>2</sup></a>.</p>

# M-way FM

<p>ここまで, 2つの値の交差項だけを考慮した 2元 FM で説明したが, 3つ以上特徴量の交差項についても拡張できる. 2-way FM が<strong>行列因数分解</strong> (matrix factorization) に対応しているなら, 3元以上の FM は, その拡張である<strong>テンソル因数分解</strong> (tensor factorization) に対応していると言える. この場合は以下のように表現できる.</p>
<span class="math display">
$$
\begin{aligned}
\phi\_{\mathit{FM}m}(\boldsymbol{x},\boldsymbol{w}):=\left\langle \boldsymbol{w},\boldsymbol{x}\right\rangle  &amp; +\sum_{C\in D^{M}}\left[\left[\prod\_{j\in C}x\_{j}\right]\sum\_{i=1}^{k}\left(\prod\_{j\in C}(\boldsymbol{v}_{j})\_{i}\right)\right]\end{aligned}
$$

</span> 
<p>ここで, <span class="math inline">$D^{M}$</span> は <span class="math inline">$M$</span> 個の <span class="math inline">$D$</span> の直積集合である. ただし, 3元以上の複雑なFMはあまり使われることがない.</p>

## 具体的な学習方法
<p><a class="citation" href="#ref-rendle2010Factorization">Rendle (2010)</a> は, 学習した <span class="math inline">$\phi_{\mathit{FM2}}(\boldsymbol{x},\boldsymbol{w})$</span> は回帰, 2値分類, ランキング予測に使えるとしている. 例えば分類タスクならば, ロジスティック損失を最適化問題を解くことになる. いずれのタスクでも, 正則化を追加するのが良いとしている. この損失関数は従来どおり SGD で学習できる. 最適化計算のオーダーは <span class="math inline">$O(kD)$</span> から <span class="math inline">$O(km(\boldsymbol{x}))$</span>の範囲となる. <span class="math inline">$m(\boldsymbol{x})$</span> は, <span class="math inline">$\boldsymbol{x}$</span>の非ゼロ要素の数である.</p>

## 発展版: Field-aware FM

追記: http://hhok777.hatenablog.com/entry/2016/10/19/204037 ここでも FMから順を追って FF
M を解説していた.

<p>FM の発展版, <strong>フィールド認識型分解機</strong> (Field-aware FM; FFM) は <a class="citation" href="#ref-FFM2012">Jahrer et al. (2012)</a> で最初に提案された<a href="#fn3" class="footnote-ref" id="fnref3"><sup>3</sup></a>. ただし当初は, <a class="citation" href="#ref-rendle2010PITF">Rendle and Schmidt-Thieme (2010)</a> による<strong>ペアワイズ相互作用テンソル因数分解</strong> (PITF) の一般化として, Factor Model と呼ばれていた. FM の発展版として位置づけられ FFM と呼ばれるようになったのは <a class="citation" href="#ref-juan2016Fieldaware">Juan et al. (2016</a>; <a class="citation" href="#ref-juan2017Fieldaware"> Juan, Lefortier, and Chapelle (2017)</a> 以降のようだ. 特に <a class="citation" href="#ref-juan2016Fieldaware">Juan et al. (2016)</a> は FFM は FM の発展型であり, 行列因数分解 (MF) と紛らわしいが別物であると強調している.</p>
<p>FFM のモチベーションはこうである. FM ではカテゴリカル変数を one-hot encoding して特徴量とするのが前提であった. このため, <strong>媒体, 広告主, 性別といった異なる属性情報がすべて一律 0/1 の値にされてしまった</strong>. 各特徴量が元はどのようなカテゴリカル変数のものだったかという情報が抜け落ちていることになる. FFM へ拡張したことで, このように, フィールドごとに特有の要因のある相互作用を表現できる.</p>
<p>具体的なモデルについて説明する. FM では 1つの特徴量ごとに 1つのベクトルパラメータ <span class="math inline">$\boldsymbol{v}$</span> が存在したが, FFM では1対1ではなく複数のベクトルパラメータを持つことができる. つまり, FM では, <span class="math inline">$x_{i}$</span>, <span class="math inline">$x_{j}$</span> の相互効果の大きさを <span class="math inline">$\left\langle \boldsymbol{v}_{i},\boldsymbol{v}_{j}\right\rangle$</span> としていたが, FFM では <span class="math inline">$i$</span> と <span class="math inline">$j$</span> に対する相互作用ではなく, 以下の式になる.<span class="math display">

$$
\begin{aligned}
\phi_{\mathit{FFM}}(\boldsymbol{w},\boldsymbol{x})=& \sum\_{i,j}\left\langle \boldsymbol{v}\_{i,f_{2}},\boldsymbol{v}\_{j,f_{1}}\right\rangle x_{i}x_{j}
\end{aligned}
$$

</span>
特徴量ごとのベクトルに新たにインデックス<span class="math inline">$f_{1},f_{2}$</span> が追加されている. <span class="math inline">$f_{1},f_{2}$</span>はそれぞれ, <span class="math inline">$i,j$</span> に対応するフィールドである. ここで, 「フィールド」と「特徴量」の違いをはっきりさせておく. フィールドというのは, one-hot encoding などで特徴量行列に変換する前の, SQL で扱うようなテーブル構造のデータの「列」で, 特徴量は計画行列に変換し, 最適化アルゴリズムで計算できる状態にした行列の列である (特徴行列の列と区別するために, field と表現していると思われる). <a href="#tab:fieldfeature" data-reference-type="ref" data-reference="tab:fieldfeature">表 1</a> は, <a class="citation" href="#ref-juan2016Fieldaware">Juan et al. (2016)</a> の例に基づいて作成した生データと, 変換後の特徴行列である<a href="#fn4" class="footnote-ref" id="fnref4"><sup>4</sup></a>.</p>
<p>
<table align="center">
<thead>
<tr class="header">
<th style="text-align: center;">ラベル</th>
<th style="text-align: center;" colspan="3">フィールド</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td style="text-align: center;">クリック</td>
<td style="text-align: center;">媒体 (Publisher)</td>
<td style="text-align: center;">広告主 (Adevertiser)</td>
<td style="text-align: center;">性別 (Genger)</td>
</tr>
<tr class="even">
<td style="text-align: center;">Yes</td>
<td style="text-align: center;">ESPN</td>
<td style="text-align: center;">Nike</td>
<td style="text-align: center;">男</td>
</tr>
<tr class="odd">
<td style="text-align: center;">No</td>
<td style="text-align: center;">ESPN</td>
<td style="text-align: center;">Nike</td>
<td style="text-align: center;">女</td>
</tr>
<tr class="even">
<td style="text-align: center;">No</td>
<td style="text-align: center;">Vogue</td>
<td style="text-align: center;">Gucci</td>
<td style="text-align: center;">男</td>
</tr>
</tbody>
</table>

<table align="center">
<thead>
<tr class="odd">
<th style="text-align: center;" >ラベル</th>
<th style="text-align: center;" colspan="2">媒体 (P)</th>
<th style="text-align: center;" colspan="2">広告主 (A)</th>
<th style="text-align: center;" colspan="2">性別 (G)</th>
</tr>
<tr class="odd">
<td style="text-align: center;">クリック</td>
<th style="text-align: center;">媒体 - ESPN</th>
<th style="text-align: center;">媒体 - Vogue</th>
<th style="text-align: center;">広告主 - Nike</th>
<th style="text-align: center;">広告主 - Gucci</th>
<th style="text-align: center;">性別 - 男</th>
<th style="text-align: center;">性別 - 女</th>
</tr>
</thead>
<tbody>
<tr class="even">
<td style="text-align: center;">Y</td>
<td style="text-align: center;">1</td>
<td style="text-align: center;">0</td>
<td style="text-align: center;">1</td>
<td style="text-align: center;">0</td>
<td style="text-align: center;">1</td>
<td style="text-align: center;">0</td>
</tr>
<tr class="odd">
<td style="text-align: center;">N</td>
<td style="text-align: center;">1</td>
<td style="text-align: center;">0</td>
<td style="text-align: center;">1</td>
<td style="text-align: center;">0</td>
<td style="text-align: center;">0</td>
<td style="text-align: center;">1</td>
</tr>
<tr class="even">
<td style="text-align: center;">N</td>
<td style="text-align: center;">0</td>
<td style="text-align: center;">1</td>
<td style="text-align: center;">0</td>
<td style="text-align: center;">1</td>
<td style="text-align: center;">1</td>
<td style="text-align: center;">0</td>
</tr>
</tbody>
</table>
<caption id="tab:fieldfeature">表1:フィールド (上) と特徴量 (下)</caption>
</p>
<p>FM では, 変換後の各列 (=特徴量) ごとにベクトル <span class="math inline">$\boldsymbol{v}$</span> を1つだけパラメータとして持っているとしていた. しかし, FFM では, 他の列 (=フィールド) ごとにパラメータを持つ. 例えば<a href="#tab:fieldfeature" data-reference-type="ref" data-reference="tab:fieldfeature">表 1</a> の場合なら, 「媒体 - ESPN」 の特徴量は, 広告主 (A) と, 性別 (G) に対応するパラメータベクトルを持つ必要がある. よって, <span class="math inline">$\{\boldsymbol{v}_{e,A},\boldsymbol{v}_{e,G}\}$</span> の2つになる. よって, フィールド数を <span class="math inline">$F$</span> とすると, パラメータの数は <span class="math inline">$Dk$</span> から <span class="math inline">$DFk$</span> になる. <a href="#tab:fieldfeature" data-reference-type="ref" data-reference="tab:fieldfeature">表 1</a> の例で全ての組み合わせを書くと, 表 <a href="#tab:interactions" data-reference-type="ref" data-reference="tab:interactions">2</a> のようになる. そのぶん FM と比べてパラメータが増えているから, オーダーは <span class="math inline">$O(\bar{D}^{2}k)$</span> へと増大している (<a href="#tab:comparison-complex" data-reference-type="ref" data-reference="tab:comparison-complex">表 3</a>).</p>
<p>
<table align="center">
<thead>
<tr class="header">
<th style="text-align: center;"></th>
<th style="text-align: center;">媒体 - ESPN</th>
<th style="text-align: center;">媒体 - Vouge</th>
<th style="text-align: center;">広告主 - Nike</th>
<th style="text-align: center;">広告主 - Gucci</th>
<th style="text-align: center;">性別 - 男</th>
<th style="text-align: center;">性別 - 女</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td style="text-align: center;">媒体 - ESPN</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{e},\boldsymbol{v}_{v}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{e},\boldsymbol{v}_{n}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{e},\boldsymbol{v}_{g}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{e},\boldsymbol{v}_{m}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{e},\boldsymbol{v}_{f}\right\rangle$</span></td>
</tr>
<tr class="even">
<td style="text-align: center;">媒体 - Vogue</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{v},\boldsymbol{v}_{n}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{v},\boldsymbol{v}_{g}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{v},\boldsymbol{v}_{m}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{v},\boldsymbol{v}_{f}\right\rangle$</span></td>
</tr>
<tr class="odd">
<td style="text-align: center;">広告主 - Nike</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{n},\boldsymbol{v}_{g}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{n},\boldsymbol{v}_{m}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{n},\boldsymbol{v}_{f}\right\rangle$</span></td>
</tr>
<tr class="even">
<td style="text-align: center;">広告主 - Gucci</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{g},\boldsymbol{v}_{m}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{g},\boldsymbol{v}_{f}\right\rangle$</span></td>
</tr>
<tr class="odd">
<td style="text-align: center;">性別 - 男</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{m},\boldsymbol{v}_{f}\right\rangle$</span></td>
</tr>
<tr class="even">
<td style="text-align: center;">性別 - 女</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
</tr>
</tbody>

</table>
<table align="center">
<thead>
<tr class="header">
<th style="text-align: center;"></th>
<th style="text-align: center;">媒体 - ESPN</th>
<th style="text-align: center;">媒体 - Vouge</th>
<th style="text-align: center;">広告主 - Nike</th>
<th style="text-align: center;">広告主 - Gucci</th>
<th style="text-align: center;">性別 - 男</th>
<th style="text-align: center;">性別 - 女</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td style="text-align: center;">媒体 - ESPN</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{e,P},\boldsymbol{v}_{v,P}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{e,A},\boldsymbol{v}_{n,P}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{e,A},\boldsymbol{v}_{g,P}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{e,G},\boldsymbol{v}_{m,P}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{e,G},\boldsymbol{v}_{f,P}\right\rangle$</span></td>
</tr>
<tr class="even">
<td style="text-align: center;">媒体 - Vogue</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{v,A},\boldsymbol{v}_{n,P}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{v,A},\boldsymbol{v}_{g,P}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{v,G},\boldsymbol{v}_{m,P}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{v,G},\boldsymbol{v}_{f,P}\right\rangle$</span></td>
</tr>
<tr class="odd">
<td style="text-align: center;">広告主 - Nike</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{n,A},\boldsymbol{v}_{g,P}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{n,G},\boldsymbol{v}_{m,P}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{n,G},\boldsymbol{v}_{f,P}\right\rangle$</span></td>
</tr>
<tr class="even">
<td style="text-align: center;">広告主 - Gucci</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{g,G},\boldsymbol{v}_{m,P}\right\rangle$</span></td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{g,G},\boldsymbol{v}_{f,P}\right\rangle$</span></td>
</tr>
<tr class="odd">
<td style="text-align: center;">性別 - 男</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;"><span class="math inline">$\left\langle \boldsymbol{v}_{m,G},\boldsymbol{v}_{f,P}\right\rangle$</span></td>
</tr>
<tr class="even">
<td style="text-align: center;">性別 - 女</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
<td style="text-align: center;">-</td>
</tr>
</tbody>
</table>
<caption id="tab:interactions" >表2: FM (上) と FFM (下) の相互作用パラメータ組み合わせ</caption>
</p>


<p>
<table align="center" label="tab:comparison-complex" >
<thead>
<tr class="header">
<th style="text-align: center;">モデル</th>
<th style="text-align: center;">パラメータ数 (次元)</th>
<th style="text-align: center;">計算時間</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td style="text-align: center;">線形</td>
<td style="text-align: center;"><span class="math inline">$D$</span></td>
<td style="text-align: center;"><span class="math inline">$O(\bar{D})$</span></td>
</tr>
<tr class="even">
<td style="text-align: center;">2次交差項</td>
<td style="text-align: center;"><span class="math inline">$D(D-1)/2$</span></td>
<td style="text-align: center;"><span class="math inline">$O(\bar{D}^{2})$</span></td>
</tr>
<tr class="odd">
<td style="text-align: center;">FM</td>
<td style="text-align: center;"><span class="math inline">$Dk$</span></td>
<td style="text-align: center;"><span class="math inline">$O(\bar{D}k)$</span></td>
</tr>
<tr class="even">
<td style="text-align: center;">FFM</td>
<td style="text-align: center;"><span class="math inline">$DFk$</span></td>
<td style="text-align: center;"><span class="math inline">$O(\bar{D}^{2}k)$</span></td>
</tr>
</tbody>
</table>
<caption  id="tab:comparison-complex>表3 各アルゴリズムの計算時間</caption>
<a class="citation" href="#ref-juan2016Fieldaware">Juan et al. (2016)</a> をもとに作成. <span class="math inline">$\bar{D}$</span> は<span class="math inline">$D$</span> 次元の特徴量のうち, 非ゼロな要素の数の平均値.
</p>

## 応用上のヒント
<p><a class="citation" href="#ref-juan2017Fieldaware">Juan, Lefortier, and Chapelle (2017)</a> の応用例では, CTR 予測についてより具体的な応用例と, いくつかのテクニックを紹介している.</p>
<ul>
<li><p>FFM は学習方法も, FM と同様にできる<a href="#fn5" class="footnote-ref" id="fnref5"><sup>5</sup></a>. なお, <a class="citation" href="#ref-juan2016Fieldaware">Juan et al. (2016)</a> は計算を効率化する工夫についても書いているが, 著者らがすでにプログラムを公開しているので, ここでは実装上の細かいテクニックの話は省略する.</p></li>
<li><p>ただし, 一方で空間計算量はロジスティック回帰より明らかに多い.</p></li>
<li><p>one-hot encoding ではなく ハッシュ変換 (<a class="citation" href="#ref-shi2009Hash" >Shi et al. 2009;</a> <a class="citation" href="#ref-weinberger2009Feature">Weinberger et al. 2009)</a>) によって次元を線形モデルと同じになるように削減している.</p></li>
<li><p><span class="math inline">$k$</span> はかなり小さくしてもうまくいったとしている. 特に FFM は計算量が多いのでこういう工夫は重要である.</p></li>
<li><p>正則化パラメータを調整するよりも, early stopping のほうが過学習 (過剰適合) の回避に効果的だったという.</p></li>
<li><p><a class="citation" href="#ref-juan2017Fieldaware">Juan, Lefortier, and Chapelle (2017)</a> の応用例では, 2次交差項を含むロジスティック回帰モデルに対して, 特に配信の少ない広告主の広告に対して CTR 予測の精度が向上していることを報告している. これは, 訓練データには現れない組み合わせの交差項が, FM ではうまく学習できるからだと著者らは考えている.</p></li>
<li><p>過去のモデルを更新する形で再学習する (warm-starting) のも有効</p></li>
<li><p>FFM (というかMF) は行列の非凸性を仮定している. よって非凸でないならば局所解に陥りうる. 最も簡単な解決方法は, 著者らがやっているように, 複数の初期値をランダムに決めて計算することである.</p></li>
<li><p>A/B テストでオンライン評価する際には, 計算時間の違いから更新頻度に差が出て不公平にならないよう, 更新タイミングを同期している. (計算の速さも重要な性能指標なので, 実用性で評価するならこの措置は不要な気がする.)</p></li>
</ul>
# FM/FFMの実装について

### オリジナル

FM, FFM ともに考案者の実装が存在する. いずれもC++で書かれており, コマンドライン上で実行する使い方だが, 研究目的で作られたものなので民間企業でよくやるようなオンライン予測のような用途を想定しておらず, 使いづらい.
- [libFM: Factorization Machine Library](http://www.libfm.org/) 
- [LIBFFM: A Library for Field-aware Factorization Machines](https://www.csie.ntu.edu.tw/~cjlin/libffm/) 

### hivemall での利用
<p>hivemall の場合は, FM, FFM はそれぞれ<code>train_fm()</code> 関数でサポートされている.それぞれ, オリジナルのlibfm/libffmに沿ってJavaで実装している.</p>

- [Factorization Machine · Hivemall User Manual](https://hivemall.incubator.apache.org/userguide/recommend/movielens_fm.html) 
- [Field-Aware Factorization Machines · Hivemall User Manual](https://hivemall.incubator.apache.org/userguide/binaryclass/criteo_ffm.html) 

<p><code>train_fm()</code>は<code>-f</code> または <code>–-factor</code> オプションでベクトルの大きさ <span class="math inline">$k$</span> を調整できる. デフォルトは2-way FMのみで, 一般化された <span class="math inline">$M$</span>-way FM は実装されていない(というかRendleらのlibfmも実装していない). <code>train_ffm()</code> 関数のオプションも<code>train_fm()</code>とほぼ同じである. FFMへの拡張にともなっていくつか増えたものとして, 例えば入力データのフィールド数を <code>–-num-field</code> で指定する必須の引数がある.</p>



# 最近の研究動向

## FM とニューラルネット
<p>ここ数年はニューラルネット (NN) あるいはディープニューラルネット (DNN) に FM を取り入れようという研究も多く見られる. そのあたりに関して, 日本語で代表的な研究がリストアップされている.</p>
https://data.gunosy.io/entry/deep-factorization-machines-2018#f-95055ec5

<p>ここによると, FMとDNNのあわせ技を提案した最初期の研究は <a class="citation" href="#ref-zhang2016Deep">Zhang, Du, and Wang (2016)</a>, <a class="citation" href="#ref-qu2016ProductBased">Qu et al. (2016)</a>, <a class="citation" href="#ref-cheng2016Wide">Cheng et al. (2016)</a>, <a class="citation" href="#ref-guo2017DeepFM">Guo et al. (2017)</a> などがあるようだ<a href="#fn6" class="footnote-ref" id="fnref6"><sup>6</sup></a>. そこで, ここで挙げられている研究を中心に調べてみる.</p>
<p>これらのうち, <a class="citation" href="#ref-zhang2016Deep">Zhang, Du, and Wang (2016)</a> はFactorization-machine-supported Neuarl Network (FNN) と, FNN を少しアレンジした Sampling-based NN (SNN)を提案している. スケールの大きなカテゴリカル変数のデータを DNN でどう学習するかという観点で, FM を embedding 層の一種としてみなして書いている (これは他の研究でも同様) ため, FM の課題を発展解決させるという文脈とは目的意識が少し外れる研究だが, ZhangらがFNNを構想したきっかけが畳み込みニューラルネット (CNN) だという記述は興味深い. 彼らはCNNの最下層が局地的な隣接するニューロンのどうしの結合層であり, 一方でFMはフィールドごとの結合を見ているため, 両者は局所的な相関関係を学習しているという類似点があることに着目している. (こういうイメージは大雑把だが, 新しいアイディアに役に立つかもしれない.)</p>
<p><a class="citation" href="#ref-guo2017DeepFM">Guo et al. (2017)</a> が提案したDeepFMは, 実質的にFMとDNNのコンポネントを並列した構造で, 最後の出力層でやっと両者を結合させることであえて低次元の組み合わせで表現できるようにしている (<a href="#fig:FeepFM">図 1</a>). これに対し, <a class="citation" href="#ref-he2017Neural">He and Chua (2017)</a> が提案した Neural FM (NFM) では, FM層 (bi-interaction polling 層と書いているが, 要するに 2-way FM) とDNNを直列にしている(<a href="#fig:NFM">図 2</a>).</p>

![DeepFM_by_Zhang2019.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/236849/618a064c-3ca2-7446-8996-9297014d8161.png)
<figcaption  id="fig:DeepFM">図 1: <a class="citation" href="#ref-guo2017DeepFM">Guo et al. (2017)</a> による DeepFM のネットワーク構造 (<a class="citation" href="#ref-zhang2019FieldAware">Zhang et al. 2019</a> より引用)</figcaption>

![NFM_by_Zhang2019.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/236849/7fa5f45d-3d37-0a50-2ddb-64baf6fe7820.png)
<figcaption id="fig:NFM">図 2: <a class="citation" href="#ref-he2017Neural">He and Chua (2017)</a> による Neural FM のネットワーク構造 (<a class="citation" href="#ref-zhang2019FieldAware">Zhang et al. 2019</a> より引用)</figcaption>

## FFM の発展
<p>さらに<a class="citation" href="#ref-zhang2019FieldAware">Zhang et al. (2019)</a> は, 既存のFMベースのネットワークの問題点を指摘し, FMではなくFFMを取り入れたField-aware Neural FM (FNFM) を提案している.</p>

![FNFM.png](https://fancsdev.qiita.com/files/77a7fb65-b030-0d24-783e-8c08ad4781d6.png)
<figcaption id="fig:FNFM">図 3: <a class="citation" href="#ref-zhang2019FieldAware">(Zhang et al. 2019)</a> による Field-aware Neural FM (FNFM) のネットワーク構造 (<a class="citation" href="#ref-zhang2019FieldAware">Zhang et al. 2019</a> より引用)</figcaption>

<p><a class="citation" href="#ref-zhang2019FieldAware">Zhang et al. (2019)</a> の実験では, FM, DCN, DeepFM, NFM, など主要な競合モデルとも比較したが, いずれも少ないエポック数のうちに過学習が発生していることが示され, ごく小さな学習率 ( .0001 とか) を設定するのが望ましいとしている.</p>
<p>ここまで紹介した研究は, Criteo, Avazu, iPinYouなどのweb広告データによるクリック予測結果をベンチマークにしているが, 当てはまりの良さの向上の観点では, それぞれ顕著な進展があるとは言えない<a href="#fn7" class="footnote-ref" id="fnref7"><sup>7</sup></a>ので, 自由度が大きすぎても学習が難しいのではないか?と思う.</p>
<p>ただし, 実験の課程でいくつか興味深い話はある.</p>
<ul>
<li><p><a class="citation" href="#ref-zhang2016Deep">Zhang, Du, and Wang (2016)</a>, <a class="citation" href="#ref-he2017Neural">He and Chua (2017)</a> によれば, ドロップアウトが汎化に重要になる. 特に <a class="citation" href="#ref-he2017Neural">He and Chua (2017)</a> は, L2 正則化よりもドロップアウトのほうがパフォーマンス向上に寄与したことを報告し, 著者らはその理由をドロップアウトは単に重みを抑制するのではなく部分モデルによるアンサンブル学習と同等のものとみなせるから, と推理している.</p></li>
</ul>
<p>以下では, FM ではなく FFM とニューラルネットの研究に着目してサーベイをしている.</p>
<p><a href="https://qiita.com/guglilac/items/6c8971d27c143e2567a4#field-aware-factorization-machines-ffm-juan-recsys2016">Field-awareなFactorization Machinesの最新動向(2019)</a></p>
<p>こちらで紹介されているものは, FFM で当初から問題とされていた過学習のしやすさをどう解決するかという研究が多く紹介されている.</p>

# 参考文献
<div id="refs" class="references">
<div id="ref-cheng2016Wide">
<p>Cheng, Heng-Tze, Mustafa Ispir, Rohan Anil, Zakaria Haque, Lichan Hong, Vihan Jain, Xiaobing Liu, et al. 2016. “Wide &amp; Deep Learning for Recommender Systems.” In <em>Proceedings of the 1st Workshop on Deep Learning for Recommender Systems - DLRS 2016</em>, 7–10. Boston, MA, USA: ACM Press. DOI: <a href="https://doi.org/10.1145/2988450.2988454">10.1145/2988450.2988454</a>.</p>
</div>
<div id="ref-Duchi:2011AdaGrad">
<p>Duchi, John, Elad Hazan, and Yoram Singer. 2011. “Adaptive Subgradient Methods for Online Learning and Stochastic Optimization.” <em>J. Mach. Learn. Res.</em> 12 (July): 2121–59. <a href="http://jmlr.org/papers/v12/duchi11a.html">http://jmlr.org/papers/v12/duchi11a.html</a>.</p>
</div>
<div id="ref-guo2017DeepFM">
<p>Guo, Huifeng, Ruiming Tang, Yunming Ye, Zhenguo Li, and Xiuqiang He. 2017. “DeepFM: A Factorization-Machine Based Neural Network for CTR Prediction.” In <em>Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence</em>, 1725–31. Melbourne, Australia: International Joint Conferences on Artificial Intelligence Organization. DOI: <a href="https://doi.org/10.24963/ijcai.2017/239">10.24963/ijcai.2017/239</a>.</p>
</div>
<div id="ref-he2017Neural">
<p>He, Xiangnan, and Tat-Seng Chua. 2017. “Neural Factorization Machines for Sparse Predictive Analytics.” In <em>Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval - SIGIR ’17</em>, 355–64. Shinjuku, Tokyo, Japan: ACM Press. DOI: <a href="https://doi.org/10.1145/3077136.3080777">10.1145/3077136.3080777</a>.</p>
</div>
<div id="ref-FFM2012">
<p>Jahrer, Michael, Andreas Töscher, Jeong-Yoon Lee, J Deng, Jacob Spoelstra, and Hang Zhang. 2012. “Ensemble of Collaborative Filtering and Feature Engineered Models for Click Through Rate Prediction.” In <em>KDDCup Workshop</em>. <a href="https://www.semanticscholar.org/paper/KDD-Cup-2012-Track-2-\%3A-Ensemble-of-Collaborative-\%E2\%80\%94-Jahrer-T\%C3\%B6scher/05a8058916e7359e52eaee081e13194efdb21484">https://www.semanticscholar.org/paper/KDD-Cup-2012-Track-2-\%3A-Ensemble-of-Collaborative-\%E2\%80\%94-Jahrer-T\%C3\%B6scher/05a8058916e7359e52eaee081e13194efdb21484</a>.</p>
</div>
<div id="ref-juan2017Fieldaware">
<p>Juan, Yuchin, Damien Lefortier, and Olivier Chapelle. 2017. “Field-Aware Factorization Machines in a Real-World Online Advertising System.” In <em>Proceedings of the 26th International Conference on World Wide Web Companion - WWW ’17 Companion</em>, 680–88. Perth, Australia: ACM Press. <a href="https://doi.org/10.1145/3041021.3054185">https://doi.org/10.1145/3041021.3054185</a>.</p>
</div>
<div id="ref-juan2016Fieldaware">
<p>Juan, Yuchin, Yong Zhuang, Wei-Sheng Chin, and Chih-Jen Lin. 2016. “Field-Aware Factorization Machines for CTR Prediction.” In <em>Proceedings of the 10th ACM Conference on Recommender Systems - RecSys ’16</em>, 43–50. Boston, Massachusetts, USA: ACM Press. DOI: <a href="https://doi.org/10.1145/2959100.2959134">10.1145/2959100.2959134</a>.</p>
</div>
<div id="ref-juan2015Fieldaware">
<p>Juan, Yuchin, Yong Zhung, and Wei-sheng Chin. 2015. “Field-Aware Factorization Machines.” <a href="http://www.csie.ntu.edu.tw/~r01922136/slides/ffm.pdf">http://www.csie.ntu.edu.tw/~r01922136/slides/ffm.pdf</a>.</p>
</div>
<div id="ref-qu2016ProductBased">
<p>Qu, Yanru, Han Cai, Kan Ren, Weinan Zhang, Yong Yu, Ying Wen, and Jun Wang. 2016. “Product-Based Neural Networks for User Response Prediction.” In <em>2016 IEEE 16th International Conference on Data Mining (ICDM)</em>, 1149–54. Barcelona, Spain: IEEE. DOI: <a href="https://doi.org/10.1109/ICDM.2016.0151">10.1109/ICDM.2016.0151</a>.</p>
</div>
<div id="ref-rendle2010Factorization">
<p>Rendle, Steffen. 2010. “Factorization Machines.” In <em>2010 IEEE International Conference on Data Mining</em>, 995–1000. Sydney, Australia: IEEE. DOI: <a href="https://doi.org/10.1109/ICDM.2010.127">10.1109/ICDM.2010.127</a>.</p>
</div>
<div id="ref-rendle2010PITF">
<p>Rendle, Steffen, and Lars Schmidt-Thieme. 2010. “Pairwise Interaction Tensor Factorization for Personalized Tag Recommendation.” In <em>Proceedings of the Third ACM International Conference on Web Search and Data Mining - WSDM ’10</em>, 81. New York, New York, USA: ACM Press. DOI: <a href="https://doi.org/10.1145/1718487.1718498">10.1145/1718487.1718498</a>.</p>
</div>
<div id="ref-shi2009Hash">
<p>Shi, Qinfeng, James Petterson, Gideon Dror, John Langford, Alex Smola, and S.V.N. Vishwanathan. 2009. “Hash Kernels for Structured Data.” <em>Jornal of Machine Learning Research</em> 10 (December): 2615–37. <a href="http://www.jmlr.org/papers/v10/shi09a.html">http://www.jmlr.org/papers/v10/shi09a.html</a>.</p>
</div>
<div id="ref-wang2017Deep">
<p>Wang, Ruoxi, Bin Fu, Gang Fu, and Mingliang Wang. 2017. “Deep &amp; Cross Network for Ad Click Predictions.” In <em>Proceedings of the ADKDD’17 on ZZZ - ADKDD’17</em>, 1–7. Halifax, NS, Canada: ACM Press. <a href="https://doi.org/10.1145/3124749.3124754">https://doi.org/10.1145/3124749.3124754</a>.</p>
</div>
<div id="ref-weinberger2009Feature">
<p>Weinberger, Kilian, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. 2009. “Feature Hashing for Large Scale Multitask Learning.” In <em>Proceedings of the 26th Annual International Conference on Machine Learning - ICML ’09</em>, 1–8. Montreal, Quebec, Canada: ACM Press. DOI: <a href="https://doi.org/10.1145/1553374.1553516">10.1145/1553374.1553516</a>.</p>
</div>
<div id="ref-zhang2019FieldAware">
<p>Zhang, Li, Weichen Shen, Jianhang Huang, Shijian Li, and Gang Pan. 2019. “Field-Aware Neural Factorization Machine for Click-Through Rate Prediction.” <em>IEEE Access</em> 7: 75032–40. DOI: <a href="https://doi.org/10.1109/ACCESS.2019.2921026">10.1109/ACCESS.2019.2921026</a>.</p>
</div>
<div id="ref-zhang2016Deep">
<p>Zhang, Weinan, Tianming Du, and Jun Wang. 2016. “Deep Learning over Multi-Field Categorical Data.” In <em>Proceedings of 38th European Conference on IR Research</em>, edited by Nicola Ferro, Fabio Crestani, Marie-Francine Moens, Josiane Mothe, Fabrizio Silvestri, Giorgio Maria Di Nunzio, Claudia Hauff, and Gianmaria Silvello, 9626:45–57. Paduva, Italy: Springer International Publishing. DOI: <a href="https://doi.org/10.1007/978-3-319-30671-1_4">10.1007/978-3-319-30671-1_4</a>.</p>
</div>
</div>
<section class="footnotes">
<hr />
<ol>
<li id="fn1"><p>この話は, <a href="https://tech-blog.fancs.com/entry/factorization-machine">https://tech-blog.fancs.com/entry/factorization-machine</a> の当該箇所が参考になる<a href="#fnref1" class="footnote-back">↩</a></p></li>
<li id="fn2"><p>より正確には, ゼロの要素は計算する必要がないため, <span class="math inline">$D$</span> を特徴量の非ゼロ成分の数の平均値 <span class="math inline">$m(\boldsymbol{x})$</span> に置き換えることができる.<a href="#fnref2" class="footnote-back">↩</a></p></li>
<li id="fn3"><p>実装は <a href="https://www.csie.ntu.edu.tw/~cjlin/libffm/">https://www.csie.ntu.edu.tw/~cjlin/libffm/</a> で公開されている.<a href="#fnref3" class="footnote-back">↩</a></p></li>
<li id="fn4"><p>ここではカテゴリカル変数のみの生データを one-hot encoding した例を挙げているが, 数値変数が含まれていても同様に扱える.<a href="#fnref4" class="footnote-back">↩</a></p></li>
<li id="fn5"><p>たとえば, <a class="citation" href="#ref-juan2016Fieldaware">Juan et al. (2016)</a> では <span class="citation" href="#ref-Duchi:2011AdaGrad">Duchi, Hazan, and Singer (2011)</a> による AdaGrad を利用している.<a href="#fnref5" class="footnote-back">↩</a></p></li>
<li id="fn6"><p>その他, <a class="citation" href="#ref-wang2017Deep">Wang et al. (2017)</a> の Deep &amp; Cross Network (DCN) は明示的に2次交差項をネットワーク構造に組み込んでいるので, <a href="#eq:polynomial2" data-reference-type="eqref" data-reference="eq:polynomial2">[eq:polynomial2]</a> のニューラルネット版と言えるかもしれない.<a href="#fnref6" class="footnote-back">↩</a></p></li>
<li id="fn7"><p>例えば, ここまでで紹介した研究では, <a class="citation" href="#ref-wang2017Deep">Wang et al. (2017)</a> によって提案された, FM ではなく2次交差項モデルと同様な構造に制約した Deep &amp; Cross NN (DCN) もよく比較対象に挙げられており, それとも大きな違いが出ていない<a href="#fnref7" class="footnote-back">↩</a></p></li>
</ol>
</section>