論文位址
Deep & Cross Network for Ad Click Predictions
前言
這次分享一下來自Standford和google聯合發表的Deep&Cross Network，該篇文章主要工作是提出了Cross的結構來進行高階的特征組合并且引入線性時間複雜度，模型的結構與Wide&Deep類似，不同的地方主要在于在Wide&Deep中，Wide部分使用的交叉特征需要人為進行組合，需要依賴很多的先驗知識，而Cross結構則可以自動進行高階的特征組合進而優化CTR結果，下面來看一下該篇論文的内容。
Abstract
衆所周知，特征工程是機器學習任務中非常重要的一環，通常一個好的特征比模型要重要的多，但是這通知需要耗費大量的人工時間去篩選或者窮盡地去嘗試特征對。
DNN的出現使得特征自動組合成為可能，也就是說通過将特征統一放入DNN中利用DNN來自動完成高階非線性特征的拟合以及學習，但是DNN在做這種特征組合時，由于使用神經網絡組合後特征的不可見性雖然其泛化能力較好但是相應的記憶能力存在一定的缺失。
在Wide&Deep(後續會對該篇論文進行分享)中，使用了Wide的部分來增加對組合特征的記憶能力，而這仍然需要人為進行特征組合，DeepFM将wide部分的lr替換為了FM，增加了更多的二維特征交叉，而這些特征組合大部分都是二階特征組合，這是因為當組合的特征越多，特征的次元也容易形成爆炸之勢，為學習帶來了很大的難度。
DCN做的事情就是替換掉Wide而使用Cross結構進而無需人工進行特征的組合并且利用Cross層次的不同來獲得不同階的組合，利用這種結構DCN在許多任務上相比于目前的主流的結構在記憶體占用以及準确率上都取得了領先的位置。
小總結
也就說本篇文章的核心内容，就是引入了Cross結構來進行多特征的組合進而避免了人為組合的難度，但是組合特征的種類這麼多，是如何進行壓縮的呢？接下來是正文部分。
Introduction
Related word
文中主要列舉了一些特征組合方面的工作，首當其沖的是FM，其為每個特征均學習一個隐向量，特征的組合就利用兩個特征的隐向量的内積作為組合特征，這種方式有效地解決了一般的組合特征中由于稀疏性問題權重難以訓練的問題。FFM則在FM的基礎上引入了Fields的概念，每一維特征都将學習對應其餘所有Fields的隐向量，當與不同的隐向量進行交叉時選擇不同的隐向量進行向量内積。
DNN通過多層的神經網絡來學習高維的非線性特征組合，而DNN有一個問題就是當神經網絡的層數一深很容易導緻梯度消失|梯度爆炸的問題，也就導緻靠近輸入層的權重非常難以更新，這裡額外說一下ResNet，因為理論上Deep Network學習的能力至少是大于等于Shallow Network的，但是實際情況當模型深度上升性能卻迎來了下降，ResNet的做法通過引入shortcut connection來提升深層神經網絡的學習的，其結構如下：
這裡看到輸出是 F ( x ) + x F(x)+x F(x)+x，輸入是x，中間的神經網絡是相當于做了個x->F(x)的映射，通常而言，直接學習F(x)->y是比學習F(x)->y-x更困難的，是以Resnet的核心思想就是利用這樣的shortcut connection使得這幾層神經網絡學習的是輸出與輸入之間的殘差，進而簡化神經網絡的學習難度加深深層網絡的學習層數。
DNN非線性的拟合能力非常強，但是DNN進行高階非線性的組合是否就完美呢？在kaggle競賽中高排名的做法很多都是低階組合特征，而DNN的特征組合則是高度非線性的，那麼自然而然希望既可以利用DNN學習高階非線性特征的能力，又希望可以學習顯式的特征組合，Wide&Deep就是這種思想下的産物，Deep&Cross在Wide&Deep進一步簡化了特征組合的難度以及提升了效果。
Main Contributions
- 提出了一種無需人工特征組合以及暴力搜尋的可以顯示進行特征組合的Cross結構來進行有限階的特征組合。
- 随着Cross的layer層數加深組合特征的階數随之上升，即多少特征組合可控，并且在Cross結構中包含了所有可能的目前階的特征組合，描述的不是特征清楚，後面結合結構來說。
- Cross網絡并不特征占用記憶體進而可以輕松實作。
- DCN在使用差距一個資料量級特征的情況下在測試集上獲得了比DNN更優的logloss。
DCN
終于到了正文部分了，第一步，先扔DCN的網絡結構。
輸入層
輸入主要包括Continus Feature以及Category Feature，對于連續值需要經過歸一化處理，對于離散特征目前主流的做法都是經過Embedding layer将離散值轉為連續特征處理了，是以輸入到DCN中的特征是連續特征與離散特征經過處理後Concat(這裡叫stack)形成的一個長向量。
Cross network
模型整體結構與Wide&Deep類似，是以這裡重點就介紹Cross network部分，可以看到圖中Cross共有L1層，每一層的輸入如下:
X L + 1 = X 0 ∗ X L T ∗ W L + 1 + b l + 1 + X L X_{L+1} = X_0*X_L^T*W_{L+1}+b_{l+1}+X_L XL+1=X0∗XLT∗WL+1+bl+1+XL
公式中的每個參數均是一個列向量，可以看到 X L + 1 X_{L+1} XL+1等于 X L X_{L} XL增加一個 X 0 ∗ X L T ∗ W L + 1 + b l + 1 X_0*X_L^T*W_{L+1}+b_{l+1} X0∗XLT∗WL+1+bl+1項，将 X 0 ∗ X L T ∗ W L + 1 + b l + 1 X_0*X_L^T*W_{L+1}+b_{l+1} X0∗XLT∗WL+1+bl+1記為 F ( X L , W L + 1 , b L ) F(X_L,W_{L+1},b_L) F(XL,WL+1,bL)，相當于F()函數學習的就是一個殘差，這和Resnet的思想有點像。公式中，w和b均是該層的參數項，可以看到 X L + 1 X_{L+1} XL+1與 X L X_L XL的次元是一樣的，也就是說輸入經過一整個Cross network其次元是一樣的，那麼Cross network為什麼說可以學習到所有的特征組合呢？
這裡假設Cross network隻有一層，我們的特征為[a,b,c]，w參數我們以 w m n w_{mn} wmn來表示，m代表第幾層，n代表第幾位，這裡忽略biases，因為不影響我們看結果我們看一下第一層的輸出結果：
X 1 = [ w 11 ∗ ( a 2 , b a , c a ) + a , w 12 ∗ ( a b , b 2 , c b ) + b , w 13 ( a c , b c , c 2 ) + c ] X_1=[w_{11}*(a^2,ba,ca)+a,w_{12}*(ab,b^2,cb)+b,w_{13}(ac,bc,c^2)+c] X1=[w11∗(a2,ba,ca)+a,w12∗(ab,b2,cb)+b,w13(ac,bc,c2)+c]
可以看到第一層的輸出中分解開已經包含了所有的二階的特征組合方式，隻是變成了各自求和的形式，再看第二層的輸出結果，設：
t e m p = w 11 ∗ w 21 ∗ ( a 2 , b a , c a ) + a ∗ w 21 + w 12 ∗ w 22 ∗ ( a b , b 2 , c b ) + b ∗ w 22 + w 13 ∗ w 23 ∗ ( a c , b c , c 2 ) + c ∗ w 23 temp = w_{11}*w_{21}*(a^2,ba,ca)+a*w_{21}+w_{12}*w_{22}*(ab,b^2,cb)+b*w_{22}+w_{13}*w_{23}*(ac,bc,c^2)+c*w_{23} temp=w11∗w21∗(a2,ba,ca)+a∗w21+w12∗w22∗(ab,b2,cb)+b∗w22+w13∗w23∗(ac,bc,c2)+c∗w23
第二層的輸出如下：
X 2 = [ a ∗ t e m p + a , b ∗ t e m p + b , c ∗ t e m p + c ] X_2=[a*temp+a,b*temp+b,c*temp+c] X2=[a∗temp+a,b∗temp+b,c∗temp+c]
可以看到第二層中包含了所有的一階到三階的特征組合，這些特征都是以和的形成進而壓縮到了與輸入相同的次元。
以上就是Cross network獨特的地方，其通過這種形式一方面維持了次元的不變性，并且還包括了所有的特征組合可能。
參數數量分析
可以看到Cross network的參數主要是每一層的系數W以及偏置biases，假設輸入次元為d，Cross layer深度為L，那麼總的參數數量為2*L*d,深度以及輸入次元均是正比關系！！
Deep network
這裡沒什麼新意，就不展開說了。
輸出層
輸出層将Cross network以及DNN network的輸出直接進行stack操作，然後以一層全連接配接進行連接配接并使用sigmoid計算最終的pCTR。
Cross network分析
Polynomial Approximation
這部分，我沒太看明白，猜測是推導Cross的結構可以擷取到bound-degree下所有的組合吧。
Generalization of FMs
我們知道FM核心的思想就是參數共享，即不同的特征組合隻要使用了同一個特征，那麼使用的對應的隐向量也是相同的，這樣即使是不同的特征組合也可以對同一個特征的隐向量進行更新。
Cross結構繼承了FM的這一思想，具體展現在，如隻考慮 x i x_i xi與 x j x_j xj特征的組合，其在Cross後的系數是 { w k i } k = 1 l \{w_k^i\}_{k=1}^l {wki}k=1l以及 { w k j } k = 1 l \{w_k^j\}_{k=1}^l {wkj}k=1l的組合，而這些參數不僅是在具有 x i x j x_ix_j xixj時才可以更新，在擁有其他的組合時均可以進行更新。
Efficient Projection
每一層的Cross layer相當于計算了x0與 X L X_L XL的所有二階組合，假設輸入次元為d，則所有二階組合數量為 d 2 d^2 d2，再将其映射到d維，相當于再與 d 2 ∗ d d^2*d d2∗d的矩陣相乘進行降維，時間複雜度為三次方消耗，而Cross network通過分解為向量計算并加入權重矩陣将時間複雜度下降到線性級别，先看圖：
看圖，感覺完全看不出來是如何壓縮到線性時間複雜度，那麼他是怎麼壓縮的呢？很簡單。
x p = x 0 x l T w = x 0 ( x l T w ) x_p=x_0x_l^Tw=x_0(x_l^Tw) xp=x0xlTw=x0(xlTw)
由于輸入都是長度為d的向量，先計算 x l x_l xl與w的乘積得到一個标量值，再通過一個向量與标量進行乘積最終的時間複雜度就來到了O(d)，并且占用的記憶體也小的多的多，試想如果輸入次元d非常高，簡單說10000維，10000*10000*4bytes=4億bytes就是400MB的空間。
實驗
資料集
The Criteo Display Ads2 dataset is for the purpose of predicting ads click-through rate. It has 13 integer features and 26 categorical features where each category has a high cardinality.
For this dataset, an improvement of 0.001 in logloss is considered as practically significant. 這是因為在使用者數量非常多的情況下，CTR即使隻提升一點點帶來的收益都非常高。
實作細節
特征處理
論文中的DCN是基于TensorFlow搭建訓練的 ，其中Real-value通過log transform進行了轉換(不知道是不是先對數轉換再歸一化處理)，categorical feature通過Embedding進行轉換，Embedding的長度選擇經驗是 6 ∗ ( c a t e g o r i c a l c a r d i n a l i t y ) 1 / 4 6*(categorical\ cardinality)^{1/4} 6∗(categorical cardinality)1/4 ,stack後的次元為1026維。
優化方法
使用的是基于Adam優化器的SGD方法進行參數更新。batch_size為512，在DNN中使用了batch normalization在一層訓練完成後進行歸一化重新将分布拉到正态分布中。gradient clip norm was set at 100，這個參數我沒使用用，查詢到應該是防止梯度爆炸的，當累計梯度到達限定門檻值則進行截斷處理。
regularization
在防止過拟合方面，使用的是early stop，在實驗中發現L2正則以及drop out效果都不怎麼顯著。
超參數
We report results based on a grid search over the number of hidden layers, hidden layer size, initial learning rate and number of cross layers.以上就是主要進行的網格搜尋的超參數，具體範圍為：
The number of hidden layers ranged from 2 to 5, with hidden layer sizes from 32 to 1024. For DCN, the
number of cross layers3 is from 1 to 6. The initial learning rate4 was tuned from 0.0001 to 0.001 with increments of 0.0001. All experiments applied early stopping at training step 150,000, beyond
which overfitting started to occur.
後面的實驗結果我就不解釋了，還是那句，知道效果好就ok了，但是具體的應用還是需要根據場景去嘗試。
小結
這篇2017年google與stanford聯合發表的論文等于加強了16年google的wide&deep模型，Cross結構可以有效地控制多階特征的組合以及學習，但是這裡想到的問題是在将如此多的組合特征利用求和進行壓縮後學習的能力是否還強呢？即是否可以有效地學習每層的weights和biases進而幫助篩選出最有效的組合特征呢？這部分以後有機會可以進行驗證，今天的文章就到這吧，下期見。