CTR論文精讀(七)--DeepFM

Abstract

Learning sophisticated feature interactions behind user behaviors is critical in maximizing CTR for recommender systems. Despite great progress, existing methods seem to have a strong bias towards low- or high-order interactions, or require expertise feature engineering. In this paper, we show that it is possible to derive an end-to-end learning model that emphasizes both low- and highorder feature interactions. The proposed model, DeepFM, combines the power of factorization machines for recommendation and deep learning for feature learning in a new neural network architecture. Compared to the latest Wide & Deep model from Google, DeepFM has a shared input to its 「wide」 and 「deep」 parts, with no need of feature engineering besides raw features. Comprehensive experiments are conducted to demonstrate the effectiveness and efficiency of DeepFM over the existing models for CTR prediction, on both benchmark data and commercial data.

1. CTR預估

CTR預估數據特點：

輸入中包含類別型和連續型數據。類別型數據需要one-hot,連續型數據可以先離散化再one-hot，也可以直接保留原值
維度非常高
數據非常稀疏
特徵按照Field分組

CTR預估重點在於學習組合特徵。注意，組合特徵包括二階、三階甚至更高階的，階數越高越複雜，越不容易學習。Google的論文研究得出結論：高階和低階的組合特徵都非常重要，同時學習到這兩種組合特徵的性能要比只考慮其中一種的性能要好。

那麼關鍵問題轉化成：如何高效的提取這些組合特徵。一種辦法就是引入領域知識人工進行特徵工程。這樣做的弊端是高階組合特徵非常難提取，會耗費極大的人力。而且，有些組合特徵是隱藏在數據中的，即使是專家也不一定能提取出來，比如著名的「尿布與啤酒」問題。

在DeepFM提出之前，已有LR，FM，FFM，FNN，PNN（以及三種變體：IPNN,OPNN,PNN*）,Wide&Deep模型，這些模型在CTR或者是推薦系統中被廣泛使用。

2. 模型演進歷史

DeepFM借鑒了Google的wide & deep的做法，其本質是

將Wide & Deep 部分的wide部分由人工特徵工程+LR 轉換為FM模型，避開了人工特徵工程；
FM模型與deep part共享feature embedding。

2.1 線性模型

最開始CTR或者是推薦系統領域，一些線性模型取得了不錯的效果。比如：LR，FTRL。線性模型有個致命的缺點：無法提取高階的組合特徵。所以常用的做法是人為的加入pairwise feature interactions。即使是這樣：對於那些出現很少或者沒有出現的組合特徵以及高階組合特徵依舊無法提取。

LR最大的缺點就是無法組合特徵，依賴於人工的特徵組合，這也直接使得它表達能力受限，基本上只能處理線性可分或近似線性可分的問題。

2.2 FM模型

線性模型差強人意，直接導致了FM模型應運而生（在Kaggle上打比賽提出來的，取得了第一名的成績）。FM通過隱向量latent vector做內積來表示組合特徵，從理論上解決了低階和高階組合特徵提取的問題。但是實際應用中受限於計算複雜度，一般也就只考慮到2階交叉特徵。

後面又進行了改進，提出了FFM，增加了Field的概念。

2.3 遇上深度學習

隨著DNN在圖像、語音、NLP等領域取得突破，人們見見意識到DNN在特徵表示上的天然優勢。相繼提出了使用CNN或RNN來做CTR預估的模型。但是，CNN模型的缺點是：偏向於學習相鄰特徵的組合特徵。 RNN模型的缺點是：比較適用於有序列(時序)關係的數據。

FNN (Factorization-machine supported Neural Network) 的提出，應該算是一次非常不錯的嘗試：先使用預先訓練好的FM，得到隱向量，然後作為DNN的輸入來訓練模型。缺點在於：受限於FM預訓練的效果。隨後提出了PNN (Product-based Neural Network)，PNN為了捕獲高階組合特徵，在embedding layer和first hidden layer之間增加了一個product layer。根據product layer使用內積、外積、混合分別衍生出IPNN, OPNN, PNN*三種類型。

無論是FNN還是PNN，他們都有一個繞不過去的缺點：對於低階的組合特徵，學習到的比較少。而前面我們說過，低階特徵對於CTR也是非常重要的。

Google意識到了這個問題，為了同時學習低階和高階組合特徵，提出了Wide&Deep模型。它混合了一個線性模型（Wide part）和Deep模型(Deep part)。這兩部分模型需要不同的輸入，而Wide part部分的輸入，依舊依賴人工特徵工程。

但是，這些模型普遍都存在兩個問題：

偏向於提取低階或者高階的組合特徵。不能同時提取這兩種類型的特徵。
需要專業的領域知識來做特徵工程。

DeepFM在Wide&Deep的基礎上進行改進，成功解決了這兩個問題，並做了一些改進，其優勢/優點如下：

不需要預訓練FM得到隱向量
不需要人工特徵工程
能同時學習低階和高階的組合特徵
FM模塊和Deep模塊共享Feature Embedding部分，可以更快的訓練，以及更精確的訓練學習

3. DeepFM

DeepFM閃亮登場！

主要做法如下：

FM Component + Deep Component。FM提取低階組合特徵，Deep提取高階組合特徵。但是和Wide&Deep不同的是，DeepFM是端到端的訓練，不需要人工特徵工程。
共享feature embedding。FM和Deep共享輸入和feature embedding不但使得訓練更快，而且使得訓練更加準確。相比之下，Wide&Deep中，input vector非常大，裡麪包含了大量的人工設計的pairwise組合特徵，增加了他的計算複雜度。

DeepFM架構圖：

Figure 1: Wide & deep architecture of DeepFM. The wide and deep component share the same input raw feature vector, which enables DeepFM to learn low- and high-order feature interactions simultaneously from the input raw features.

3.1 FM Component

FM部分的輸出由兩部分組成：一個 Addition Unit，多個 內積單元。

$y_{FM} = + sum_{j_1 = 1}^{d} sum_{j_2 = j_1 + 1}^{d} x_{j_1} cdot x_{j_2}$

這裡的d是輸入one-hot之後的維度，我們一般稱之為 `feature_size`。對應的是one-hot之前的特徵維度，我們稱之為 `field_size`。

FM架構圖：

Figure 3: The architecture of DNN

Addition Unit 反映的是1階的特徵。內積單元反映的是2階的組合特徵對於預測結果的影響。

注意：

雖然公式上 $Y_{FM}$ 是所有部分都求和，是一個標量。但是從FM模塊的架構圖上我們可以看到，輸入到輸出單元的部分並不是一個標量，應該是一個向量。

實際實現中採用的是FM化簡之後的內積公式，最終的維度是：`field_size + embedding_size`（對應FM Layer中的神經元個數: Field數量 + 嵌入維度 = F + k，其中 F 為one-hot之前特徵維度，k 為embedding的特徵維度）

這裡分別展開解釋下維度的兩部分是怎麼來的，對於理解模型還是很重要的：

1. `field_size` 對應的是 `<W,X>`。

這裡的X是one-hot之後的，one-hot之後，我們認為X的每一列都是一個單獨的維度的特徵。這裡我們表達的是X的1階特徵，說白了就是單獨考慮X的每個特徵，他們對最終預測的影響是多少。是多少那？是W！W對應的就是這些維度特徵的權重。假設one-hot之後特徵數量是`feature_size`，那麼W的維度就是 `(feature_size, 1)`。

這裡 <W,X> 是把X和W每一個位置對應相乘相加。由於X是one-hot之後的，所以**相當於**是進行了一次 Embedding！X在W上進行一次嵌入，或者說是一次選擇，選擇的是W的行，按什麼選擇那，按照X中不為0的那些特徵對應的index，選擇W中 row=index 的行。

這裡解釋下Embedding:

W是一個矩陣，每一行對應X的一個維度的特徵（這裡是one-hot之後的維度，一定要注意）。W的列數為1，表示嵌入之後的維度是1。W的每一行對應一個特徵，相當於是我們拿輸入X_i作為一個index, X_i的任意一個Field i中只有1個為1，其餘的都是0。哪個位置的特徵值為1，那麼就選中W中對應的行，作為嵌入後這個Field i對應的新的特徵表示。對於每一個Field都執行這樣的操作，就選出來了X_i Embedding之後的表示。注意到，每個Field都肯定會選出且僅選出W中的某一行(想想為什麼？)，因為W的列數是固定的，每一個Field都選出W.cols作為對應的新特徵。把每個Field選出來的這些W的行，拼接起來就得到了X Embedding後的新的表示：維度是 `num(Field) * num(W.cols)`。雖然每個Field的長度可能不同，但是都是在W中選擇一行，所以選出來的長度是相同的。這也是Embedding的一個特性：雖然輸入的Field長度不同，但是Embedding之後的長度是相同的。

所以：FM模塊圖中，黑線部分是一個全連接！W就是裡面的權重。

把輸入X和W相乘就得到了輸出。至於`Addition Unit`,我們就不糾結了，這裡並沒有做什麼加法，就把他當成是反應1階特徵對輸出的影響就行了。

2. `embedding_size`

`embedding_size`對應的是 $sum_{j_1 = 1}^{d} sum_{j_2 = j_1 + 1}^{d} x_{j_1} cdot x_{j_2}$

FM論文中給出了化簡後的公式：

$sum_{i=1}^{n} sum_{j=i+1}^{n} {langle mathbf{v}_i, mathbf{v}_j angle} x_i x_j qquadqquadqquadqquadqquadqquad(1)\ = frac{1}{2} sum_{i=1}^{n} sum_{j=1}^{n} {langle mathbf{v}_i, mathbf{v}_j angle} x_i x_j - frac{1}{2} sum_{i=1}^{n} {langle mathbf{v}_i, mathbf{v}_i angle} x_i x_i qquadqquad;;(2)\ = frac{1}{2} left(sum_{i=1}^{n} sum_{j=1}^{n} sum_{f=1}^{k} v_{i,f} v_{j,f} x_i x_j - sum_{i=1}^{n} sum_{f=1}^{k} v_{i,f} v_{i,f} x_i x_i ight) qquad,(3) \ = frac{1}{2} sum_{f=1}^{k} {left lgroup left(sum_{i=1}^{n} v_{i,f} x_i ight) cdot left(sum_{j=1}^{n} v_{j,f} x_j ight) - sum_{i=1}^{n} v_{i,f}^2 x_i^2 ight group} quad;;,(4) \ = frac{1}{2} sum_{f=1}^{k} {left lgroup left(sum_{i=1}^{n} v_{i,f} x_i ight)^2 - sum_{i=1}^{n} v_{i,f}^2 x_i^2 ight group} qquadqquadqquad;;$

這裡最後的結果中是在[1,K]上的一個求和。 K就是W的列數，就是Embedding後的維度，也就是embedding_size。也就是說，在DeepFM的FM模塊中，最後沒有對結果從`[1,K]`進行求和。而是把這K個數拼接起來形成了一個K維度的向量。

FM Component總結：

1. FM模塊實現了對於1階和2階組合特徵的建模。

2. 沒有使用預訓練

3. 沒有人工特徵工程

4. embedding矩陣的大小是：特徵數量 * 嵌入維度。然後用一個index表示選擇了哪個特徵。

需要訓練的有兩部分：

1. input_vector和Addition Unit相連的全連接層，也就是1階的Embedding矩陣。

2. Sparse Feature到Dense Embedding的Embedding矩陣，中間也是全連接的，要訓練的是中間的權重矩陣，這個權重矩陣也就是隱向量V。

3.2 Deep Component

Deep Component架構圖：

Figure 3: The architecture of DNN.

Deep Component是用來學習高階組合特徵的。網路裡面黑色的線是全連接層，參數需要神經網路去學習。

由於CTR或推薦系統的數據one-hot之後特別稀疏，如果直接放入到DNN中，參數非常多，我們沒有這麼多的數據去訓練這樣一個網路。所以增加了一個Embedding層，用於降低緯度。

這裡繼續補充下Embedding層，兩個特點：

1. 儘管輸入的長度不同，但是映射後長度都是相同的.`embedding_size(k)`

2. embedding層的參數其實是全連接的Weights，是通過神經網路自己學習到的。

Embedding層的架構圖：

embedding layer表示為： $a^{(0)} = [e_1, e_2, dots, e_m]$

其中是第個 filed 的 embedding，m 是 filed 數量；然後 $a^{(0)}$ 傳遞給deep part，前饋過程如下： $a^{(l+1)} = sigma(W^{(l)}a^{(l)} + b^{(l)})$

其中是層深度，是激活函數， $a^{(l)}$ , $W^{(l)}$ , $b^{(l)}$ 分別是第層的輸出，權重和偏置。

然後得到dense real-value 特徵矢量，最後被送到sigmoid函數做CTR預測： $y_{DNN} = sigma(W^{|H|+1} cdot a^{|H|} + b^{|H|+1})$

其中是隱藏層層數值得注意的是：FM模塊和Deep模塊是共享feature embedding的（也就是V）。

好處：

1. 模型可以從最原始的特徵中，同時學習低階和高階組合特徵；

2. 不再需要人工特徵工程。Wide&Deep中低階組合特徵就是同過特徵工程得到的。

3.3 對比其他模型

模型圖：

Figure 5: The architectures of existing deep models for CTR prediction: FNN, PNN, Wide & Deep Model

3.3.1 FNN Model

FNN is a FM-initialized feedforward neural network.

FNN使用預訓練的FM來初始化DNN，然後只有Deep部分，不能學習低階組合特徵。

FNN缺點：

1. Embedding的參數受FM的影響，不一定準確；

2. 預訓練階段增加了計算複雜度，訓練效率低；

3. FNN只能學習到高階的組合特徵。模型中沒有對低階特徵建模。

3.3.2 PNN Model:

PNN：為了捕獲高階特徵。PNN在第一個隱藏層和embedding層之間，增加了一個product layer。

根據product的不同，衍生出三種PNN：IPNN，OPNN，PNN 分別對應內積、外積、兩者混合。

作者為了加快計算，採用近似計算的方法來計算內積和外積。內積：忽略一些神經元。外積：把m*k維的vector轉換成k維度的vector。由於外積丟失了較多信息，所以一般沒有內積穩定。但是內積的計算複雜度依舊非常高，原因是：product layer的輸出是要和第一個隱藏層進行全連接的。

PNN缺點：

1. 內積外積計算複雜度高。採用近似計算的方法外積沒有內積穩定；

2. product layer的輸出需要與第一個隱藏層全連接，導致計算複雜度居高不下；

3. 和FNN一樣，只能學習到高階的特徵組合。沒有對於1階和2階特徵進行建模。

3.3.3 Wide&Deep:

Wide & Deep設計的初衷是想同時學習低階和高階組合特徵，但是wide部分需要領域知識進行特徵工程。

Wide部分可以用LR來替換，這樣的話就和DeepFM差不多了。

但是DeepFM共享feature embedding 這個特性使得在反向傳播的時候，模型學習feature embedding，而後又會在前向傳播的時候影響低階和高階特徵的學習，這使得學習更加的準確。

Wide&Deep缺點：

1. 需要特徵工程提取低階組合特徵

Note:

事實上，論文已經明確指出了DeepFM相對於 Wide & Deep 的創新點：

1. 將Wide & Deep 部分的wide部分由人工特徵工程+LR 轉換為FM模型，避開了人工特徵工程；

2. FM模型與deep part共享feature embedding。並且之處共享feature embedding，使得embedding特徵得到了很好的表徵，建模能力更精細。

3.3.4 DeepFM

優點：

1. 沒有用FM去預訓練隱向量V，並用V去初始化神經網路。（相比之下FNN就需要預訓練FM來初始化DNN）；

2. FM模塊不是獨立的，是跟整個模型一起訓練學習得到的。（相比之下Wide&Deep中的Wide和Deep部分是沒有共享的）；

3. 不需要特徵工程。（相比之下Wide&Deep中的Wide部分需要特徵工程）；

4. 訓練效率高。（相比PNN沒有那麼多參數）。

總結就是：

1. 沒有預訓練（no pre-training）；

2. 共享Feature Embedding，沒有特徵工程（no feature engineering）；

3. 同時學習低階和高階組合特徵（capture both low-high-order interaction features）。

以上模型對比圖如下：

4. 實驗

4.1 實驗準備

數據集

1) Criteo Dataset

2) Company Dataset

評估指標

1) AUC (Area Under ROC)

2) Logloss (cross entropy).

模型比較

一共比較9個模型：LR, FM, FNN, PNN (three variants), Wide & Deep, and DeepFM 其中為了避開 Wide & Deep模型中wide部分的特徵工程工作，利用LR & DNN and FM & DNN進行代替。

參數設置

To evaluate the models on Criteo dataset, we follow the parameter settings in [Qu et al., 2016] for FNN and PNN:

(1)dropout: 0.5;

(2) network structure: 400-400-400;

(3) optimizer: Adam;

(4) activation function: tanh for IPNN, relu for other deep models.

To be fair, our proposed DeepFM uses the same setting. The optimizers of LR and FM are FTRL and Adam respectively, and the latent dimension of FM is 10.

表現評估

Efficiency Comparison

We compare the efficiency of different models on Criteo dataset by the following formula: $frac{training time of deep CTR model}{training time of LR}$

Figure 6: Time comparison.

DeepFM在兩個數據集上幾乎達到了最好的表現。

1) pre-training of FNN makes it less efficient;

2) Although the speed up of IPNN and PNN* on GPU is higher than the other models, they are still computationally expensive because of the inefficient inner product operations;

3) The DeepFM achieves almost the most efficient in both tests.

Effectiveness Comparison

時間結果如下表：

實驗結論：

1. 組合特徵的學習提高了CTR預估模型的性能；

2. 正確的同時學習低階和高階組合特徵，同樣可以提高CTR預估的性能；

3. 在學習低階和高階組合特徵時，使用相同的feature embedding可以提高CTR性能。

4.2 超參數建議

論文中還給出了一些參數的實驗結果，直接給出結論，大家實現的時候可以參考下。

PS: constant效果最好，就是隱藏層每一層的神經元的數量相同。

這部分實驗圖片太多，可直接參考原論文。

5. Note

對於一個基於CTR預估的推薦系統，最重要的是學習到用戶點擊行為背後隱含的特徵組合。在不同的推薦場景中，低階組合特徵或者高階組合特徵可能都會對最終的CTR產生影響。因子分解機(Factorization Machines, FM)通過對於每一維特徵的隱變數內積來提取特徵組合。最終的結果也非常好。但是，雖然理論上來講FM可以對高階特徵組合進行建模，但實際上因為計算複雜度的原因一般都只用到了二階特徵組合。那麼對於高階的特徵組合來說，我們很自然的想法，通過多層的神經網路即DNN去解決。