論文読み. 8 Field-aware Probabilistic Embedding Neural Network for CTR Prediction (RecSys 2018)

## はじめに
　`Field-aware Probabilistic Embedding Neural Network
for CTR Prediction`という論文を読んだのでまとめていきます。

## 1. 対象とするトピック
### 1.1 キーワード
　$CTR Prediction; Recommender Systems; Deep Neural Network$ [論文](https://dl.acm.org/doi/10.1145/3240323.3240396)

### 1.2 Abstract
> For Click-Through Rate (CTR) prediction, Field-aware Factorization Machines (FFM) have exhibited great effectiveness by considering field information. However, it is also observed that FFM suffers from the overfitting problem in many practical scenarios. In this paper, we propose a Field-aware Probabilistic Embedding Neural Network (FPENN) model with both good generalization ability and high accuracy. FPENN estimates the probability distribution of the
field-aware embedding rather than using the single point estimation (the maximum a posteriori estimation) to prevent overfitting. Both low-order and high-order feature interactions are considered to improve the accuracy. FPENN consists of three components, i.e., FPE component, Quadratic component and Deep component. FPE component outputs probabilistic embedding to the other two components, where various confidence levels for feature embeddings are incorporated to enhance the robustness and the accuracy. Quadratic component is designed for extracting low-order feature interactions, while Deep component aims at capturing high-order feature interactions. Experiments are conducted on two benchmark datasets, Avazu and Criteo. The results confirm that our model alleviates the overfitting problem while having a higher accuracy.
 
## 2. Theory
### 2.1 Problem Formulation
　$i$番目のデータがクリックされる確率を予測します。
<img width="581" alt="スクリーンショット 2020-04-16 15.59.36.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/f395659b-8f30-4ca9-3c36-5d328c1153f9.png">

### 2.2 Architecture of FPENN
　下図のように

- $FPE Component:$ 入力されたスパースな特徴量ベクトルを密な潜在ベクトルに埋め込む
- $Linear Component:$ 線形な関係を学習
- $Quadratic Component:$ ２次の関係を学習
- $Deep Component:$ 高次の関係を学習

します。そして、以下の式で定義される変数$z$
<img width="417" alt="スクリーンショット 2020-04-17 20.16.47.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/3fb6f141-3aab-e172-9851-6e98157f778e.png">

を用いて$y$を予測します。
<img width="120" alt="スクリーンショット 2020-04-17 20.18.37.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/1e2b7472-682e-bead-60a6-b3c3bf182749.png">


<img width="574" alt="スクリーンショット 2020-04-15 17.46.17.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/02fc80a4-e7b7-c7d3-8463-24913a4c55d0.png">

### 2.3 FPE Component　
 上述したように、`FPE Component`はデータを埋め込みます。具体的には、$x \in R^d$の特徴量を$f$個の`field`にグループ化します。そして、$i (i = 1,...,d)$番目の特徴量を行列$V_i \in R^{(f-1) \times k}$に埋め込みます。ただし、$k$は潜在ベクトルの次元数です、最終的には$d \times (f - 1) \times k$次元のテンソル$V$を出力します。

#### 2.3.1 Training
　一般の確率分布での埋め込みを直接実行して場合は、サンプリングを通じた`back-propagation`を行うことができません。そこで連続ランダム変数を決定項と基本的な確率分布の２つに分解する`reparameterization trick`を用います。これを用いることで学習が可能な要素とサンプリングで得た要素を用いて埋め込みが行えます。
<img width="625" alt="スクリーンショット 2020-04-17 20.41.59.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/0c9e3453-dfea-0efc-c642-1d7f66334809.png">

#### 2.2.2 Testing
　テストではサンプリングを行います。その際に、

- 分散の情報を利用する
- 過学習を防ぐ

ために以下二つの手法を提案しています。

##### 2.2.2.1 TS-strategy
　`Thompson Sampling`を元に、学習して得た分布からサンプルを行います。
<img width="537" alt="スクリーンショット 2020-04-17 21.07.45.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/9d5b04ab-5c6d-220a-3de8-d52c0e978969.png">

##### 2.2.2.2 UCB-strategy
　`Upper Confidence Bound`を用いて平均と分散のバランスを取ります。その結果、`suboptimal value`を回避します。
<img width="550" alt="スクリーンショット 2020-04-17 21.21.24.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/90926c55-e0cc-c478-ce7c-00cd75a6139c.png">


## 3. Experiments

### 3.1 Datasets

- Avazu
- Criteo

### 3.2 Experimental Results
#### 3.2.1 Generalization Ability

- Generalization measures the ability to predict the previously unseen data.
- We can see that the performance of our method (FPENN) drops very little as we increase training steps, while FFM under different settings drop significantly
- The probability assumption can be regarded as adding regularization to the model. As a result, the validation curve is more stable.

<img width="612" alt="スクリーンショット 2020-04-15 17.53.10.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/20a3494c-9b05-fe08-4d02-f2d4cf27db3b.png">


#### 3.2.2 Accuracy

- Compared with the second best model, FPENN gives a rise of 0.32% and 0.11% in terms of AUC.
- The reason is that our model captures both low-order and high-order feature interactions with field information.
- Moreover, the model estimates different confidence levels for the learned parameters, where parameters with low confidence levels can be corrected by combining the mean and the variance information of the distribution.


<img width="464" alt="スクリーンショット 2020-04-15 18.00.43.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/323be3f4-178b-2830-6756-11245327e2ba.png">

## References

- Weiwen Liu, Ruiming Tang, Jiajin Li, Jinkai Yu, Huifeng Guo, Xiuqiang He, Shengyu Zhang (2018). Field-aware Probabilistic Embedding Neural Network for CTR Prediction, https://dl.acm.org/doi/10.1145/3240323.3240396