聊聊推荐系统的高阶特征交叉问题
文 | 水哥
源 | 知乎
Saying
1. DCN看起來給了我們很好的允諾，但是細細想來是有一些問題的，這里也可以參考大佬的意見
2. 高階FM的核心設計是先element-wise乘，再對embedding求和。核心優化方法是利用計算中的冗余構建遞推關系，然后使用動態規劃解決
3. 計算出現冗余的地方，動態規劃就可能出現；冗余的部分和新的信息組成遞推的時候，動態規劃就可以應用
4. DCN的形式對于交叉有點表面化，我們要的不是交叉這個概念，我們要的是確切的誰和誰交叉
FM引入了特征embedding的交叉之后，還順帶引入了另一個很自然的問題：除了二階關系，是否還有更高階的交叉存在？這些交叉應該選用什么樣的數學形式，又如何來優化？在本講中我們來探討這個問題。按照上一講提到的文章，僅僅憑借MLP是很難做到element-wise，以及內積這種交叉的。想要有高階，首先想到的還是FM自然的向高階的拓展，但是這個形式中需要優化茫茫多的參數，higher-order FM的作者抓到了計算中的冗余，巧妙地化解了指數復雜度的問題。從另一個角度，在DNN中如果能引入很自然的交叉結構，實踐起來當然也是非常便利的。鼎鼎大名的Deep&Cross Network就做了這方面的工作，可惜它給我們的，可能是夢幻泡影，這又是為何呢？
擴展簡單優化難——Higher-Order Factorization Machines（HOFM[1]）
核心觀點：高階特征的交叉形式是所有的embedding element-wise乘，再求和，乘以所有要交叉的特征。在這個計算中存在大量的冗余，通過推導遞推關系可以簡化為動態規劃求解
HOFM這篇工作發表于2016年的NIPS，作者重新思考了高階FM的問題（主要是優化的問題）。其實在原來的FM中就有一個自然的擴展，二階的特征是兩個特征乘起來，以及他們embedding的內積，那么照葫蘆畫瓢，可以設計出 階的交叉關系：
其中， 表示要進行交叉的特征索引的集合，里面的 ， ， 這些都是對應的索引。還是特征， 是對應的embedding，這些表示方法還和之前一樣。這里的交叉分為兩部分，一部分是所有涉及到的特征的連乘，而另一部分是先把所有涉及到的embedding做element-wise乘法（操作），然后再把所有元素加起來（即上面的sum函數）。這樣就得到了一個交叉單項的形式，而整體的高階FM就可以表示為：
前面的三項就和之前的FM是一樣的。這里我們用上標（m）表示這個embedding是給 階交叉使用的（因此每到一階都有一份獨立的embedding）。 是一個縮寫，實際表示的是，而 也就是 。就等價于上面的 這樣，我們就得到了高階FM的表示。
由于高階交叉求和中的每一項其實都是組合數的一項（比如4階就是從 個特征里面挑出4個來做交叉），這個計算復雜度是指數級的。直接按照這個形式去優化，forward，backward計算量都太大了。
如果把上面的交叉項用ANOVA核（這里不用關心背景知識，不影響下面的閱讀）表示的話，可以記為 ，其中求和和后面的乘都是 項。上面的表示還可以展開為：。HOFM的核心是指出這里存在一個遞推的關系：
這里表示的是單向量的關系，要注意這里 的 表示的是取第個元素操作，請不要和上面混淆了。表示除了 之外剩下的部分。
這個遞推關系用數學來表示是很難受的，我們盡量用語言來證明這個遞推：原來的表示的是從所有個特征中挑出個（稱為組合數），遍歷所有可能性，每一項算好乘加起來。如果我們把單獨拿出來，原來的組合數可以分為兩部分，一部分是不含 的，而一部分是包含的。不含 的這部分，還是從 個里面挑出 個，只是這里面沒有 ，那么這一項就是 。而包含的這部分，可以先把 提到外面去，這部分組合數因為一定包含了這個位置，那么就相當于 挑 中的一個已經固定了，剩下的其實是在中挑出 個，而且是不含 的。所以后面這一項就是 ，這樣就得到上面的遞推關系。
當有了這個遞推關系之后，就可以用動態規劃來解決接下來的問題。我們用一張表格來表示：
在這里我們保證每次計算到的最新的 都是當前向量的最后一維。假設更小的和更短的的結果已經計算好了（圖上的深色部分），那么當前所需要的結果就是該點左上角和左邊結果的融合。只要保證先從上到下，再從左到右的計算順序，就可以在 的時間復雜度內得到結果，避免了指數級的運算。在優化的過程中，梯度的傳導也是類似的。區別是從下往上，從右往左倒著回來的，這里就不再贅述了。
我們僅僅知道這里有一個很好的動態規劃的簡化是不關鍵的，而是要知道，為什么這里可以出現動態規劃？我們再次觀察，其實在 階和 階之間，不涉及新加的 的部分，算出來的結果大部分是一樣的，而且在兩邊都得各自算一遍。由于有大量的冗余計算，當我們把計算過程分解為“新的結果=冗余的計算+新的信息”的時候，就可以得到動態規劃的遞推形式。關于更多動態規劃的本質，可以參考筆者的另一篇文章（專欄）進行理解[2]
如果直接按照原來的形式來做，每一階所有的參數都是獨立的，這樣龐大的參數量還是會帶來不小的麻煩。論文中也提出了一些實踐的建議，比如可以所有階都共享embedding，只是有的地方階高，有的地方階低，節省了大量的參數。
HOFM中的高階交叉確實優化的很到位，但是這還是限定在了FM這個大框架下去做的。現在基本都使用DNN了，如果在DNN中能夠很方便的引入高階交叉，對于實踐再方便不過了。Deep&Cross Network就是這么一個工作，我們來看看，它是不是能夠很好地完成高階交叉。
天下沒有免費的午餐——Deep & Cross Network（DCN[2]）
DCN是斯坦福的學者們在2017年設計的一個新的網絡結構，其核心是一個叫做Cross Network的旁路，這一路是專門對特征進行交叉的。按照設計，這路網絡會對特征進行任意有限階交叉。其核心設計可以用下面的公式來表示：
其中， ， 分別是DNN中，輸入層和輸出層的中間結果（向量）。 為一開始的輸入特征的embedding的拼接，它會在每一個層都參與運算。就是這層要學習的權重了，這也是一個向量。結構上也可以用下面的圖來輔助理解：
這里的 對應上面的 ， 對應公式中的 。之所以要寫成上面公式的形式是因為這個公式的模塊是可以層層堆疊的。
那么DCN這樣的設計是如何進行特征交叉的呢？設想在第一層，其實就是先和 做向量外積，得到一個矩陣，然后在矩陣中，每一個元素都是原先embedding中兩個元素的乘：
當后面再乘以 的時候，其實是讓 進行篩選，選出哪些交叉項留下，繼續進行后面的運算。在第一層計算完畢之后，結果其實保留了一部分二階的embedding元素交叉，那么再往下繼續，就會有3階，4階。。。一直到網絡層數的階層。這樣，只要我的網絡有 層，我就能讓輸出帶有 階的交叉。下面的圖展示了這個過程， 出現在每一層的中間，只要產生了新的中間輸出，就要和 作用來得到下一層的結果：
高階交叉空許約
就到目前為止，一切看起來都很美好，但是看完DCN這篇文章，睡一覺，再起來，就有一個問題鉆進腦海：HOFM用了指數級的參數來優化高階交叉特征，而DCN每一層僅僅就一個向量 就把高階交叉做了，會不會太廉價了？
拋開DCN許諾的高階交叉，我們來想象一下，假設 我們可以人為指定了，需要什么樣的形式，才能完全達到挑出交叉的效果？比如就讓DCN只有一層，然后還原出FM的形式？
想要達到這個目的，必須拿出上面 矩陣的上三角或者下三角（不包含對角線）的所有元素加到一起才可以，這時候怎么解出 呢？我發現不論如何設計 其實都是做不到的（本質原因還是因為 是個向量，勢單力薄）。所以這里的交叉最后和我們見到的FM以及類似模型中的交叉已經不是一個東西了。這是我個人對DCN的最大疑問點，可能也是文章開頭大佬觀點的部分原因吧。光有交叉這個概念是不能達到工業目的的，就像我們上一講所講的。我們要的交叉甚至誰和誰交叉比較好都有詳細的門道在里面。
第二點是，當交叉變成了embedding中的一個元素的乘法，而不是原來整個embedding合起來內積的。如果后面這個不成立，就不存在embedding泛化性的保證了，那么交叉的意義還剩下多大呢？
上面這兩個問題，在xDeepFM[3]這篇文章中相當于是做了一個歸納：DCN的本質實際上是給 乘了一個系數！重新考慮這個公式，根據結合律和分配率，可以重新寫作：
結合上面的圖，括號里面的兩個向量分別是行向量和列向量，乘起來就是一個數字，也就是說，最后一層一層迭代完了，只得到一個 的倍數。你要說沒有交叉吧，系數其實還是和 有關系的，你要說有交叉吧，又不是我們FM，PNN，ONN等等網絡中講得這么回事。
這么看下來，DCN給我們的，大體上是一個空頭支票。它的交叉也不一定是我們想要的交叉，如果想要真正的交叉應該怎么做呢？
寫到這又發現寫的太多了，先鴿住，下期繼續講如何做真正的高階交叉~
下期預告
推薦系統精排之鋒（7）：xDeepFM與DCN-V2，兌現交叉的諾言
往期回顧
1.召回 粗排 精排，如何各司其職？
2.拍不完的腦袋：推薦系統打壓保送重排策略
3.簡單復讀機LR如何成為推薦系統精排之鋒？
4.召回粗排精排-級聯漏斗（上）
5.召回粗排精排-級聯漏斗（下）
6.推薦系統精排：看阿里媽媽再試線性模型
7.推薦精排之鋒：FM的一小步，泛化的一大步
7.推薦中使用FNN/PNN/ONN/NFM優化特征交叉
后臺回復關鍵詞【入群】
加入賣萌屋NLP/IR/Rec與求職討論群
后臺回復關鍵詞【頂會】
獲取ACL、CIKM等各大頂會論文集！
?
[1] Higher-Order Factorization Machines，NIPS，2016
https://proceedings.neurips.cc/paper/2016/file/158fc2ddd52ec2cf54d3c161f2dd6517-Paper.pdf
[2] 水哥：從零單排leetcode第二十五期之動態規劃（2）：動態規劃的本質是狀態壓縮
https://zhuanlan.zhihu.com/p/390344991
[3] Deep & Cross Network for Ad Click Predictions，AdKDD，2017
https://arxiv.org/pdf/1708.05123.pdf
[4] xDeepFM: Combining Explicit and Implicit Feature Interactions for Recommender Systems，KDD，2018 ?
https://arxiv.org/pdf/1803.05170.pdf
總結
以上是生活随笔為你收集整理的聊聊推荐系统的高阶特征交叉问题的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 这可能是你与 AI 大神们近距离接触的唯
- 下一篇： 算法岗面试前怎样高效刷题？