推薦系統(tǒng)與DNN的結(jié)合

??這篇博客記錄自己前段時間對基于DNN的推薦模型的學(xué)習(xí)，包括FM、FFM、DCN、PNN、AFM和XDeepFM。

FM

??全稱是Factorization Machine，分解機(jī)。FM的思想在于公式\sum_{i=1}^n\sum_{j=i+1}^nW_{ij}X_iX_j=\sum_{i=1}^n\sum_{j=i+1}^n<v_i,v_j>X_iX_j，也就是W_{ij}:=<v_i,v_j>，如何將巨大的稀疏矩陣W分解，用兩個小的矩陣的乘積來表示。所以利用FM的思想就可以對二階組合特征\sum_{i=1}^n\sum_{j=i+1}^nW_{ij}X_iX_j進(jìn)行一定的變換，變換公式如下：
\begin{align} \sum_{i=1}^n\sum_{j=i+1}^nW_{ij}X_iX_j &= \sum_{i=1}^n\sum_{j=i+1}^n<v_i,v_j>X_iX_j \\ &= \sum_{i=1}^n\sum_{j=i+1}^n\sum_{f=1}^k v_{i,f}v_{j,f}X_iX_j \\ &= \cfrac{1}{2}(\sum_{i=1}^n\sum_{j=1}^n\sum_{f=1}^k v_{i,f}v_{j,f}X_iX_j- \sum_{i=1}^n\sum_{f=1}^kv_{i,f}v_{i,f}X_iX_i) \\ &= \cfrac{1}{2}\sum_{f=1}^k((\sum_{i=1}^nv_{i,f}X_i)*(\sum_{j=1}^nv_{j,f}X_j)-\sum_{i=1}^n(v_{i,f}X_i)^2) \\ &= \cfrac{1}{2}\sum_{f=1}^k((\sum_{i=1}^nv_{i,f}X_i)^2-\sum_{i=1}^2(v_{i,f}X_i)^2) \end{align}
借助對神經(jīng)網(wǎng)絡(luò)的理解，我們可以將v_{i,f}x_i看做是輸入層的第i個值經(jīng)過神經(jīng)網(wǎng)絡(luò)后在隱層中的第f個神經(jīng)元上得到的值，此時就可以將\sum_{i=1}^nv_{i,f}X_i看作是matmul(\vec{v},\vec{x})。那么公式中的(\sum_{i=1}^nv_{i,f}X_i)^2和\sum_{i=1}^2(v_{i,f}X_i)^2就可以用下面代碼來實(shí)現(xiàn)。

sum_square_part = tf.pow(tf.matmul(x, tf.transpose(v)), 2)
square_sum_part = tf.matmul(tf.pow(x, 2), tf.pow(v, 2))

當(dāng)然也可以利用embedding的思想來理解FM，認(rèn)為\vec{v} \times \vec{x}就是將原始特征向量映射到一個新的低維空間中，用一個低維embedding向量來表示原始特征向量，此時可以利用tf.nn.embedding_lookup函數(shù)來實(shí)現(xiàn)特征向量的低維嵌入。
補(bǔ)充：tf.nn.embedding_lookup()中的核心就是gather函數(shù)，從array中取出特定的幾行數(shù)據(jù)。因此我們可以用tf.gather()或者tf.gather_nd()實(shí)現(xiàn)embedding操作，其中，tf.gather()針對一維數(shù)據(jù)，而tf.gather_nd()針對多維數(shù)據(jù)。

FFM

??FFM可以理解為考慮了field的FM，與FM最大的不同在于分解矩陣的設(shè)定。FM的二階組合特征式是\sum_{i=1}^n\sum_{j=i+1}^n<v_i,v_j>X_iX_j，而FFM的二階組合特征式是\sum_{i=1}^n\sum_{j=i+1}^n<v_{i,f_j},v_{j,f_i}>X_iX_j。也就是說，F(xiàn)M中不同特征組合時使用的隱變量是唯一的，但是FFM中不同特征組合用的隱變量是不一樣的。FM中值維護(hù)1個embedding矩陣，而FFM中要維護(hù)field個embedding矩陣（field是one hot前樣本的特征數(shù)量），也就是要維度一個3維的embedding矩陣，維度是[feature_size, embedding_size, field_size]。下面用圖表示：

FM和FFM的embedding表.png
FM和FFM帶來的改進(jìn)是給LR加入了二階組合特征，同時優(yōu)化了二階組合特征的計(jì)算和表示方式。其中，F(xiàn)M在計(jì)算上進(jìn)行了優(yōu)化，使得二階組合特征的計(jì)算復(fù)雜度由
O(kn^2)
降低到
O(kn)
；而FFM則在FM的基礎(chǔ)上對表示方式做了改進(jìn)，F(xiàn)M和FFM都對one-hot后的稀疏特征進(jìn)行了embedding操作，但是FM中每個稀疏特征只映射成1個隱變量，而FFM中每個稀疏特征都映射成field_size個隱變量，特征的表示更加多樣，對應(yīng)的二階組合方式也就更多。
??其實(shí)FM和FFM與DNN并沒有多大聯(lián)系，但是想要了解推薦模型是如何與DNN結(jié)合的話，還是需要很好的理解FM。因?yàn)镕M帶來一個很重要的思想就是將高維稀疏特征映射到低維空間中，這在于DNN的結(jié)合中是至關(guān)重要的。因?yàn)橥扑]任務(wù)中特征經(jīng)過one-hot后維度都會變得巨大，直接傳給DNN帶來的后果就是參數(shù)量爆炸，模型根本無法收斂，甚至都沒法運(yùn)行這個巨大的模型，所以后續(xù)基于DNN的推薦模型都是先對稀疏特征進(jìn)行embedding操作的。

DCN
DCN.png

??DCN，全程是Deep&Cross Network。模型有2個組成部分——Cross Network和Deep Network。顯然模型的關(guān)鍵在于Cross Network的設(shè)計(jì)（說實(shí)話，我個人認(rèn)為與DNN結(jié)合的模型一般重點(diǎn)都不在DNN的設(shè)計(jì)上，更多在于輸入特征的處理方式或者并行網(wǎng)絡(luò)的設(shè)計(jì)上）。Cross Network的核心思想是以有效的方式應(yīng)用顯式特征交叉，Cross Network由cross layer組成，每個cross layer公式是：X_{l+1}=X_0 \otimes X_l^T * W_l+b_l+X_l=f(X_l,W_l,b_l)+X_l可見Cross Network中l層的輸出X_{l+1}與X_0和l層輸入X_l相關(guān)，交叉特征的交叉程度隨著層深度的增加而增加。Cross Network的參數(shù)量是交叉層數(shù)*輸入維度*2，“2”包含了W和b。Cross layer實(shí)現(xiàn)代碼如下：

x_l = tf.tensordot(tf.matmul(x0, x_l, transpose_b=True), weights['cross_layer_%d' % l], 1) 
      + weights['cross_layer_%d' % l] + x_l

補(bǔ)充1：公式右邊最后一項(xiàng)+X_L借鑒了殘差網(wǎng)絡(luò)的思想。
補(bǔ)充2：Cross layer的實(shí)現(xiàn)可以進(jìn)行改進(jìn)。上面的實(shí)現(xiàn)代碼并沒有邏輯上的bug，但是這種實(shí)現(xiàn)方式是非常消耗計(jì)算和存儲資源的，原因就在于X_0 \otimes X_l這一步是極度浪費(fèi)計(jì)算和存儲資源的。更好的實(shí)現(xiàn)方式是將計(jì)算過程由(X_0 \otimes X_l) * W_l改為X_0 * (X_l \otimes W_l)，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=X_0%20%5Cotimes%20X_l" alt="X_0 \otimes X_l" mathimg="1">得到的是一個大的2維矩陣，而X_l \otimes W_l得到的是一個標(biāo)量。詳細(xì)的解釋看知乎上的這篇文章。

PNN
PNN.png

??PNN，全稱是Product-based Neural Network，關(guān)鍵在于提出了product layer，放在embedding層和DNN之間，對embedding后的特征向量進(jìn)行基于乘法的特征交叉操作。Product的思想來源于，CTR預(yù)估認(rèn)為特征之間的關(guān)系更多的是一種and“且”的關(guān)系，而非add“加”（個人認(rèn)為DNN中實(shí)現(xiàn)的特征交互本質(zhì)上就是add“加”）的關(guān)系。
??Product layer分為兩部分——線性部分l_z和非線性部分l_p。其中，\begin{align} & l_z=(l_z^1,l_z^2,...,l_z^{D_1}),l_z^n=W_z^n \odot Z \\ & l_p=(l_p^1,l_p^2,...,l_p^{D_1}),l_p^n=W_p^n \odot P \end{align}線性部分有：\begin{align} & l_z^n=W_z^n \odot Z=\sum_{i=1}^N \sum_{j=1}^M(W_z^n)_{i,j}Z_{i,j} \\ & Z=(Z_1,Z_2,...,Z_N) \doteq (f_1,f_1,...,f_N) \end{align} W的維度是[N,M,D_1]，所以線性部分中每個特征點(diǎn)都可以看作是embedding特征矩陣的加權(quán)和，可見上面PNN的圖中線性部分是有問題的，線性部分中每個點(diǎn)都跟所有的embedding向量有關(guān)，而不是只跟一個有關(guān)。
非線性部分則分為2種計(jì)算方式，因?yàn)镻的定義分為2種——內(nèi)積和外積。內(nèi)積也就是兩個embedding向量進(jìn)行點(diǎn)積，外積就是兩個embedding向量進(jìn)行矩陣乘法（其中一個embedding向量需要進(jìn)行轉(zhuǎn)置）。
內(nèi)積：此時P_{i,j}=<f_i,f_j>，可見P是2維對稱矩陣，W^n也可以分解成兩個向量做外積，即W^n=\theta^n \otimes (\theta^n)^T。所以l_p^n=W_p^n \odot P=\sum_{i=1}^N \sum_{j=1}^N\theta_i^n\theta_j^nf_i f_j=\sum_{i=1}^N\theta_i^nf_i \sum_{j=1}^N\theta_j^nf_j=(\sum_{i=1}^N\theta_i^nf_i)^2。假設(shè)\delta_i^n=\theta_i^nf_i，那么有l_p^n=(\sum_{i=1}^N\delta_i^n)^2。從這里的定義可以看出，如果選擇product選擇內(nèi)積，那么非線性部分中每個點(diǎn)也是跟所有的embedding向量有關(guān)，而不是只跟兩個有關(guān)，所以上圖中非線性部分也畫錯了。
外積：此時P_{i,j}=f_if_j^T，每兩個embedding特征向量左外積就可以得到一個矩陣P_{i,j}。論文中定義外積的P=\sum_{i=1}^N \sum_{j=1}^N p_{i,j}，也就是所有外積矩陣的和，然后再對這個P求加權(quán)和得到非線性部分的一個點(diǎn)?？梢娡夥e形式下非線性部分每個點(diǎn)也是跟所有embedding特征向量有關(guān)，所以確定PNN圖中product layer那一部分是錯誤的。

AFM

AFM.png

??AFM，全程是Attentional Factorization Machine，從名字就可以看出AFM是在FM的基礎(chǔ)上加上了attention機(jī)制。原始FM在進(jìn)行預(yù)測時，F(xiàn)M會讓一個特征映射成一個特定的向量，當(dāng)這個特征與其他特征做交叉時都是用相同的向量去做計(jì)算。這是不合理的，因?yàn)樘卣鰽與特征B做交叉特征時A的重要程度和特征A與特征C做交叉特征時是不一樣的。如何體現(xiàn)出這種差異性呢？除了FFM模型外，AFM中的attention機(jī)制就是做這個工作的。這里attention可以視為權(quán)重，衡量不同特征之間交互的重要程度。AFM和FM的實(shí)現(xiàn)公式對比如下：
\begin{align} y_{AFM}&=w_0+\sum_{i=1}^Nw_ix_i+P^T\sum_{i=1}^N\sum_{j=i+1}^Na_{ij}(\vec{v_i} \odot \vec{v_j})x_ix_j \\ y_{FM}&=w_0+\sum_{i=1}^Nw_ix_i+\sum_{i=1}^N\sum_{j=i+1}^N(\vec{v_i} \odot \vec{v_j})x_ix_j \end{align}
其中，
a_{ij}
就是attention值，是將交叉特征向量傳入attention網(wǎng)絡(luò)（可以理解就是一個DNN）中學(xué)到權(quán)重。
AFM中的改進(jìn)工作就是：

  1. 對原始的one-hot特征進(jìn)行embedding操作；
  2. 對embedding特征進(jìn)行兩兩交叉（相乘）并拼接得到組合特征向量；
  3. 將組合特征向量傳到attention網(wǎng)絡(luò)中學(xué)習(xí)的組合特征向量對應(yīng)的權(quán)重向量；
  4. 將組合特征向量與權(quán)重向量相乘求和就得到了二階部分的預(yù)測值。
xDeepFM

XDeepFM.png

??xDeepFM其實(shí)就是Cross Network和DeepFM結(jié)合起來，既有Cross Network中的顯示高階組合特征，又有DNN中的隱式高階組合特征。不過xDeepFM中對Cross Network做了一定的改進(jìn)，在DCN中已經(jīng)提到了cross layer的公式
x_k=x_0x_{k-1}^Tw_k+b_k+x_{k-1}
，xDeepFM利用數(shù)學(xué)歸納法證明了上述公式可以變成
x_k=\alpha^{i+1}x_0
，其中
\alpha^{i+1}=\alpha^i(x_0^Tw_{i+1}+1)
是一個標(biāo)量，但這并不意味著
x_k
與
x_0
線性相關(guān)，因?yàn)?div id="u0z1t8os" class="image-package"> x_0
的乘子
\alpha
與
x_0
有關(guān)。不過這種形式的cross network還是有一些缺陷——輸出格式受限（必須得和輸入維度相同）和特征交互是bit級別的（沒有體現(xiàn)出filed的概念）。而xDeepFM對cross network進(jìn)行了改進(jìn)，提出了CIN（Compressed Interaction Network）。下圖是CIN的網(wǎng)絡(luò)結(jié)構(gòu)：
xDeepFM結(jié)構(gòu)之CIN模塊.png

對應(yīng)的公式是
X_{h,\ast}^k=\sum_{i=1}^{H_{k-1}}\sum_{j=1}^mW_{ij}^{k,h}(X_{i,\ast}^{k-1} \odot X_{j,\ast}^0)
，此時輸入
X^0
并不是一個向量，而是矩陣，維度是
[m,\ \ast]
，m表示有輸入有m個embedding特征向量。CIN中第
k-1
層的輸出也是一個矩陣
X^{k-1}
，維度是
[H_{k-1},\ \ast]
。此時
X^0
和
X^{k-1}
并不能直接做外積，所以xDeepFM的做法是對
X^0
和
X^{k-1}
做列切分，找相應(yīng)列做外積，就可以得到一個3維的中間態(tài)矩陣。我們可以將這個中間態(tài)矩陣想象成圖片經(jīng)過CNN提取的特征圖，對每張?zhí)卣鲌D求加權(quán)和就可以得到新向量中的一個點(diǎn)，也就是將原特征圖壓縮成一個向量。如果同一張?zhí)卣鲌D進(jìn)行多次不同加權(quán)和，那么就可以得到多個向量中的點(diǎn)，這就是CIN中的壓縮過程，圖(b)展示了這一過程。CIN的另外一個改進(jìn)就是并不是只輸出最后一層的結(jié)果，而是對每一層的輸出都進(jìn)行sum pooling后，再將所有的輸出拼接成一個向量作為最終的特征，這樣就將不同階的組合特征結(jié)合起來了，具體可看圖(c)。這里挖個坑，后面再寫論文對CIN的空間和時間復(fù)雜度的分析，以此來對比和原cross network的優(yōu)劣。
2018.12.24 補(bǔ)充：看了下論文中對CIN模型的復(fù)雜度分析，主要是將CIN與相同層數(shù)的DNN進(jìn)行了比較。在空間復(fù)雜度上，CIN是
O(mTH^2)
，其中
m
是field size，
T
是層數(shù)，
H
是隱層特征數(shù)量，但是作者這里提出，當(dāng)
H、m
較大時，可以對CIN中維度是
[H, m]
的參數(shù)矩陣
W^{k,h}
進(jìn)行分解，即
W^{k,h}=U^{k,h}(V^{k,h})^T
，此時CIN的空間復(fù)雜度是
O(TH^2L+mL^2H)
，而相同層數(shù)的DNN的空間復(fù)雜度是
O(mDH+TH^2)
，CIN的空間復(fù)雜度與embedding size
D
是無關(guān)的，而DNN的空間復(fù)雜度與D是線性相關(guān)的；在時間復(fù)雜度上，CIN是
O(mDH^2T)
，而DNN是
O(mDH+H^2T)
，可見DNN的時間復(fù)雜度相對較小。綜合來看，相對于DNN，CIN在時間復(fù)雜度上有優(yōu)勢，但是在空間復(fù)雜度上是劣勢。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容