---
lang: ja-jp
tags: Survey
---

# Incremental Factorization Machinesまとめてみた
- 元論文は[ここ](https://arxiv.org/abs/1607.02858)
- Kitazawaさんが作成したスライドは[ここ](https://speakerdeck.com/takuti/incremental-factorization-machines)
- まとめたのは[@moriaki3193](https://github.com/moriaki3193)

## キーワード
- *test-then-learn*スキーマ
- *incremental adaptive regularization*な正則化項の更新

## Abst.
推薦系のサービスを動かす時の困難の一つに**cold-start**と呼ばれる問題がある。
新たなユーザ・アイテムが登録されるとそれらについてのログがないために生じる問題である。
これを解決する一つの方法が、**context-aware**な推薦手法であり、近年流行している。
Factorization系の手法と**context**についての情報量のいずれも取り込むことができる手法としてFactorization Machinesが提案されている。

しかし、動的に増加し続けるユーザ・アイテムのデータをオンライン学習するための手法としては、FMはまだまだ不十分であり、オンライン性を兼ね揃えた手法としてこの論文が提案する**incremental Factorization Machines**の手法が注目される。

## Intro.
<div style='text-align: center;'>


</div>

> In the real-world applications such as e-commerce and on-
line ad, a user’s activity is not frequent, and item properties change dynamically over time. In a context of item recom- mendation, such scenario is referred to as persistent *cold-start*.

### 推薦手法としてのMFとFMs
Matrix Factorizationは潜在ベクトルを全てのユーザ・アイテムについて抽出できる。
しかし、「何も買っていない」ユーザ・「誰からも買われていない」アイテムについては意味のある推薦を行うことができないという問題を抱えている。
そのため、ID以外に補助的な特徴量を考慮することで推薦を可能にするための手法として**context-aware**な手法が存在する。
固有の情報と補助的で様々な形式の特徴量をいずれも取り入れることが可能なモデルとしてFactorization Machinesが提案され、研究者の間でよく利用されるようになった。

### FMsの拡張としてのiFM
iFMの手法はFMsをオンラインアルゴリズムへと拡張したものである。

> It should be noticed that the persistent cold-start problem is closely related to *concept drift*, a phenomenon of "the relation between the input data and the target variable changes over time in data stream"

おそらく*concept drift*とは、サービスが開発されることによって、入力されるデータと出力の対応の意味が変わるという意味を指している。
この現象に対してオンラインアルゴリズムは有効であることが`J. Gama et al. A survey on concept drift adaptation (2014)`の論文で示されている。
この調査から、Factorization Machinesの手法にオンライン性を持たせることがより現実的なモデルの構築に繋がると考えたことが提案手法の始まりのようだ。

著者によるとiFMは次のような性質を持つ。

- **Positive-only feedback**: `one-pass`(データを処理するのが一度だけで済む)オンライン学習のスキーマにより、モデルの更新が高速に行われる。
- **Incremental adaptive regularization**: 正則化項の学習が「その場」で自動的に行われる。

## 関連手法
### Incremental Matrix Factorization
:::info
iMFだよ、iFMではないから注意してね。
:::

*test-then-learn*と呼ばれるスキーマを組んで手法を評価している。
学習結果としてパラメータを更新する前に、ユーザ$u \in U$とアイテム$i \in I$の各組合せについての評価を先に行う点がこのスキーマの特徴である。
以下に*test-then-learn*のアルゴリズムについてまとめる。

* * *
* * *

> (新たに得られる)データストリームないし有限の『ポジティヴな』イベント集合を$S_{+}$
> 推薦を行う商品数を$N$, ウィンドウのサイズを$T$とおく。
>
> - **STEP 0**: モデルのパラメータを初期化
> - **STEP 1**: $S_{0} \subset S_{+}$を利用してモデルをバッチ学習
> - for $(u, i) \in S_{+} \setminus S_{0}$ do (残りのイベントタプルを利用して...)
> - **STEP 2**: 推薦と評価
> - (新たにポジティヴなフィードバックを与えた)$u$について$N$個のアイテムの推薦リストを$L$とおく
> - recall@$N$を、(新たにポジティヴなフィードバックをされた)$i$が$L$に含まれていれば$1$, そうでなければ$0$とする
> - recall@$N$/$T$を、直近$T$個のサンプルのrecall@$N$の平均値とする
> - **STEP 3**: パラメータを更新する

上記のアルゴリズムの**STEP n**はより詳細に説明すると、次のようになる。
ただし、$R \in \mathcal{R}^{|U|\times|I|}$を$2$値のレーティング行列とし、$P \in \mathcal{R}^{|U| \times k}$と$Q \in \mathcal{R}^{|I| \times k}$をそれぞれユーザ・アイテムについての$k$次元の潜在ベクトルとする。

- **STEP 1**
- 通常のMactix Factorizationのようにデータを利用して$P$と$Q$を獲得する
- **STEP 2**
- $Q \cdot \mathbf{p}_{u} \in \mathcal{R}^{|I|}$を、ポジティヴなフィードバックを与えたあるユーザ$u$について計算し、その値が$1$に近い$N$個のアイテムを抽出する
- **STEP 3**
- 次のようにして各行列の行ベクトルを更新する
- $\mathbf{p}_{u} \gets \mathbf{p}_{u} + 2\eta\left((1 - \mathbf{p}_{u}^{T}\mathbf{q}_{i})\mathbf{q}_{i}-\lambda \mathbf{p}_{u}\right)$
- $\mathbf{q}_{i} \gets \mathbf{q}_{i} + 2\eta\left((1 - \mathbf{p}_{u}^{T}\mathbf{q}_{i})\mathbf{p}_{u} - \lambda \mathbf{q}_{i}\right)$

$\lambda$は正則化項のパラメータであり、$\eta$は学習率であるとする。

<span style='font-size: 0.8rem;'>Recall@$N$を計算した意味はどこにあるのだろうか？</span>

### Factorization Machines
$n$回目の解説であり、割愛する。

## Incremental Factorization Machines
FMのアルゴリズムを基本とし、以下のような順番で手法を拡張している。
1. **General Incremental Predictor**: iMFのパラメータ更新がFMにおいても一般性を失うことなく採用できることを説明
2. **Incremental Adaptive Regularization**: 正則化項のバリデーションデータを利用した更新方法について説明し、それをiFMにおいてどのように利用するかを説明
3. **Context-aware Online Item Recommendation with Positive-only Feedback**: 問題設定に合わせた記法の導入と全体アルゴリズムの説明

* * *

:::info
Factorization Machinesの学習アルゴリズムは、以下のように表現される。

:::

### 1. General Incremental Predictor
FMsでは、$\Theta = \{w_{0}, \mathbf{w}, \mathbf{V}\}$の学習が必要となる。
上掲の**Algorithm 2**において重要なのは、**Algorithm 1**の**STEP 3**は一つのサンプルについての確率的勾配降下法であり、このアプローチが$\Theta$の更新においても活用できるという点である。
したがって、iFMでもiMFの際と同様に*test-then-learn*のスキーマを一般性を失うことなく利用できるということである。

### 2. Incremental Adaptive Regularization
パラメータが更新されるということは、新たなパラメータについても正則化を行う必要があるということである。

正則化項の*adaptive regularization*という考え方自体は、`Learning recommender systems with adaptive regularization (2012)`の論文で提案されているらしい(Rendleすごい)。


上記の$S^{'}$は、学習データとは異なる、バリデーションデータであることに注意する。
$S^{'}$を利用した正則化項の学習アルゴリズム(**Algorithm 3**)は、一般に**Algorithm 3**の「モデルのパラメータ更新」のステップの後に行われる。

しかし、*incremental*な正則化を行うことを考えた時に、ストリーミングの中で$S^{'}$は徐々に古びたものになってしまう(つまり獲得できなくなってしまうということ？)。
この問題を解決するアイディアは、ストリームから新たに獲得されるサンプル$(\mathbf{x}, y)$を*擬似的に*バリデーションサンプルとして利用し、$\Theta$を更新する前に正則化項を更新するというものである。
下図がそのアイディアを表現した図となる。


### 3. Context-aware Online Item Recommendation with Positive-only Feedback
ポジティヴなフィードバックのみを利用して追加学習のデータが構成されるので、サンプル$(\mathbf{x}, 1) \in S_{+}$において定義される損失関数は:

$$
l(\hat{y}(\mathbf{x}|\Theta), 1) = (\hat{y}(\mathbf{x}|\Theta)-1)^{2}
$$

<span style='font-size: 0.8rem;'>分類問題を直接解きにいくのもありなのか...</span>

最終的なiFMの学習フレームワークは*test-then-learn*のスキーマの以下のステップを次のように当てはめたものとなる。

- **STEP 1**: 通常のFMsと同様に、$w_{0}$, $\mathbf{w}$, $\mathbf{V}$を学習する
- **STEP 2**: 各サンプルのアイテムについて$\hat{y}(\mathbf{x}, \Theta)$を計算し、その結果が$1$に近い$N$個のアイテムを抽出する
- **STEP 3**: **$\lambda$-update** を行なった後に **$\Theta$-update** を$(\mathbf{x}, 1)$を利用して行う(更新には入力特徴量も必要となるので)

#### 実装上重要なポイント！
ユーザ・アイテム数は実世界のオンラインアプリケーションでは定数ではなく、変動しうる。
したがって、実装されるべきシステムは新しいユーザやアイテムを（今用意できている）現行のモデルに幾分かの方法で組み込む必要がある。


##### WIP 後はここをまとめるだけ
> Importantly, since the number of users and items on real-
world online applications is not constant, our systems must incorporate new users and items into a current model some- how. For example, iMF handles a new user (item) as an additional row of P (Q) (i.e. p|U|+1 for a new user, q|I|+1 for a new item obtained from Gaussian). Hence, iFMs also take the simple approach that a zero and random vector are respectively inserted into w and V as the initial parame- ters of new features. Fig. 3 depicts detection and insertion of new features in a stream of input vectors. It is notable that, beyond new users and items, adding new contextual variables is also possible in the middle of data streams.

## Impression
Factorization系の手法の嫌なところをいい感じに解消してくれている。
ところで、*learn-then-test*スキーマで途中でRecall@$N$とかを計算していた理由はなんだったのだろうか？

### 追記
Recallを計算していたのは、精度の移り変わりをきちんと評価するためだったのでは。
実際論文には、時系列に沿ったモデルの評価をプロットしたものが掲載されている。

しかし、グラフを見ている限り、だんだんと精度が落ちていってしまっている？ので、原因がモデルにあるのか、データにあるのかを改めて調査する必要がありそうだ。

* * *