Hello，大家好，歡迎來到“自由技藝”的知識小館，今天我們來聊一聊推薦算法。
在廣告、電商、信息流分發等業務場景中，推薦算法發揮著至關重要的作用，好的推薦算法能夠把用戶牢牢抓住，讓用戶的時間消耗在你推薦的內容上。當然，所推薦的內容有多少價值一般不是App所關注的，APP推薦的目的僅僅是留住用戶。騰訊副總裁孫忠懷曾在公開場合說過：“現在短視頻平臺的個性化分發實在是太強大了，你喜歡‘豬食’，你看到的就全是‘豬食’”。
經典的推薦算法主要指協同過濾（CF），在深度學習火起來之后，基于神經網絡的推薦模型層出不窮，比如 google Play 的 Wide & Deep、Youtube 的超大規模分類模型等。本文首先簡單介紹下一個完整的推薦系統組成及算法流程，接著重點介紹下主流推薦模型的一些實現細節。
0 如何搭建一個完整的推薦系統
（1）推薦系統組成
標簽系統：為了實現內容的精準推薦，首先需要用戶畫像。所謂用戶畫像，就是給用戶貼上各式各樣的標簽，比如年齡、性別、興趣、瀏覽歷史等等，這些標簽可以分為事實標簽、模型標簽、預測標簽等，另一方面，又可以按它表示的范圍分為一級標簽、二級標簽、三級標簽等。這些標簽需要從原子數據集中提取，然后再量化。原子數據集又是什么？它指的是用戶瀏覽 APP 的痕跡以及一些注冊信息等，通過消息中間件、存儲模塊（比如 kafka、Hbase）收集、存儲。
自動化標簽系統
算法庫：標簽系統生成了多維度、較豐富、較全面的用戶標簽，也就是特征，這些特征就是各種推薦算法或模型的輸入數據。
離線訓練：有了輸入數據和推薦模型還不夠，只有通過訓練，才能獲得最優的模型參數。為什么不用在線訓練呢？一是沒必要，二是會造成很大的性能開銷。
A/B 測試：推薦模型訓練好了之后，怎么評估推薦效果呢？這就用到了 A/B 測試，A/B 測試是一種常用的在線評估算法效果的方法。簡單來說，就是按一定的規則將用戶隨機分成幾組，并對不同組的用戶采用不同的算法，然后通過統計不同組用戶的各種評測指標，比如點擊率、瀏覽率、購買率等，從而比較不同算法的好壞。
實時推薦：一旦選中了最好的推薦算法，就可以部署到線上了。
冷啟動：推薦系統總體上來說，還是一種有監督的學習方法。有監督學習必然需要樣本和標簽，而在產品上線初期，系統對用戶了解很少，這時只能通過專家知識進行推薦。當系統積累了一定量的數據或者拿到用戶足夠多的反饋后，就可以訓練機器學習模型了。
（2）推薦算法流程
推薦服務的流程主要有 3 步：獲取用戶特征 -> (召回) -> 調用推薦模型 -> (粗排、精排)。
在實際應用中，物品列表規模很大，如果對所有的物品都調用模型打分，在性能上是不可接受的，因為計算耗時過長從而影響用戶體驗。
所以，一種常見的做法是將推薦列表生成分為召回和排序兩步。召回的作用是從大量的候選物品中（例如上百萬）篩選出一批用戶較可能喜歡的候選集 （一般是幾百）。排序又分為粗排和精排，粗排就是選出打分最高的那一部分物品。更進一步，對粗排得到的物品列表，可能需要人工調整，這就是精排。
1 CF（Collaborative Filtering，協同過濾）
好了，到這里我們已經對推薦系統有了宏觀上的了解了。接下來就來看看推薦算法是怎么篩選出用戶感興趣的物品的，最經典的就是協同過濾算法，分為 UserCF 和 ItemCF，簡單理解就是一句話：人以類聚，物以群分。這方面的文章很多了，這里就不展開講了，下圖給出了 UserCF 和 ItemCF 的優劣勢對比的結果。
UserCF 和 ItemCF 對比
2 MF（Matrix Factorization，矩陣分解）
現在來考慮一個給用戶推薦電影的簡單場景：假設有 m 個用戶，總的電影種類為 n. 例如，用戶 1 看過電影 1 和電影 n，并給出了評分 1.0 和 0.5，如果用戶看完電影沒給評分，也沒關系，可以用一個默認值代替。用戶 2 看過電影 2，并打出了 3.7 分。推薦的目的就是把這個 m * n 的矩陣中（用 S 表示）缺失的值給補全，具體流程如下：
CF 矩陣
首先，我們假設矩陣 S 可以分解為矩陣 P 和 Q 的乘積，
CF 矩陣分解
這樣做的物理含義就是：每個用戶或者每部電影都可以用一個長度為 k 的向量表示。
模型 一：NCF（Neural CF）
NCF 模型
上述模型中，輸入層（Input Layer）需要對用戶（User）和物品（Item）進行獨熱編碼（one-hot），矩陣 P 和 矩陣 Q 是模型中的參數。輸出層（Output Layer）是 softmax 層，神經元個數是 1. 當輸出 y 為 1 時，表示用戶 u 和 物品 i 是相關的，也就是說，物品 i 可以推薦給用戶 u；當輸出為 0 時，表示用戶 u 和 物品 i 是無關的，也就是說，物品 i 不建議推薦給用戶 u.
模型二：DCF（Deep CF）
下面要介紹的這個矩陣分解模型特別簡單粗暴，把用戶和物品的隱向量直接當作神經網絡中的參數去求解，而輸出層根據余弦相似度的結果去判斷用戶 i 和物品 j 的相似度。
DCF 模型
3 FM（Factorization machine，因子分解機）
上一章中的模型一和模型二是比較標準的 MF 模型，然而它有很多缺點：首先，每遇到一個新的業務，都需要重新搭建模型，如推導出新的參數學習算法，并在學習參數過程中調節各種參數，不能很好地復用。其次，MF 模型不能很好地利用特征工程法（ feature engineering）來完成學習任務。
模型一：FM
一般來說做推薦 CTR（Click Through Rate）預估時最簡單的思路就是將特征做線性組合（LR），傳入 sigmoid 得到一個概率值，本質上這就是一個線性模型，因為 sigmoid 是單調增函數不會改變里面的線性模型的 CTR 預測順序，因此 LR 模型效果會比較差。也就是 LR 的缺點：
- 是一個線性模型
- 每個特征對最終輸出結果獨立，需要手動特征交叉（xi*xj），比較麻煩
LR 目標函數
LR 目標函數改良版
上式是 LR 目標函數的一個簡單改良版，但是還是存在問題：只有當 xi 與 xj 均不為 0 時，二階交叉項才會生效，后面這個特征交叉項本質是和多項式核 SVM（Support Vector Machine，支持張量機）等價的。為了解決這個問題，FM 模型應運而生！
FM 目標函數
從公式來看，FM 模型就是 LR - 線性組合加上交叉項 - 特征組合。所以，從模型表達能力上來看，FM 肯定是要強于 LR 的，至少它不會比 LR 弱，當交叉項參數wij全為0的時候，整個模型就退化為普通的 LR 模型。對于有 n 個特征的模型，經過兩兩特征組合之后，維度自然而然就高了。
模型二：GBDT + FM
GBDT，全稱 Gradient Boosting Decision Tree（梯度提升決策樹），它是一個集成模型，使用多棵決策樹，每棵樹去擬合前一棵樹的殘差來得到很好的擬合效果。
由于 GBDT 是不支持高維稀疏的特征，所以設計了 GBDT + FM 的模型如圖所示：
GBDT + FM 模型
4 Wide & Deep
谷歌在 2016年發表了一篇論文“Wide & Deep Learning for Recommender Systems”，業務場景是 Google Play 基于用戶 query，推薦合適的 item，文章很短，只有 4 頁，卻產生了很大的影響。
Wide & Deep 模型
上圖模型分為兩部分：分別是左邊的 Deep 和右邊的 Wide。
模型的輸入數據包含連續特征（連續值），如年齡、已安裝的 APP 數量、已連接的會話數等和類別特征，如用戶畫像、設備類型、已安裝的 APP 和用戶可能感興趣的 APP。
Wide 模型中，將用戶已安裝的 APP 和可能感興趣的 APP 做叉積運算，然后連接到 softmax 層。
Deep 模型中，由于輸入特征維度很大，先經過嵌入層（Embedding）降維處理，然后特征聚合，經過全聯接層，最后一層也是 softmax 層。
Wide 是一個 LR（Logistic Regression）模型，它是一個線性模型，利用了交叉特征（AND），顯然具備較強的記憶能力（memorization）。
而 Deep 是一個 DNN 模型，它可以通過針對稀疏特征學習的低維密集嵌入更好地推廣到看不見的特征組合，因此幾乎不需要人工特征工程，具備較強的泛化能力（generalization）。但是當交互信息較少時，它會過擬合（overfit），學習到一些本來不存在的關聯。
5 超大規模分類問題
YouTube 在2016年發表的論文《Deep Neural Networks for YouTube Recommendations》中提出了基于深度學習的一個超大規模分類模型（Candidate Generation，類似 skip-gram，采用方法：hierarchical softmax 和 negative sample），它把召回階段建模為一個分類模型，其目標是根據上下文 C，用戶 U，從集合 V 中找到時刻 t 最可能被觀看的視頻 Wt
Youtube 超大規模多分類模型
u 代表用戶和 context 的 embedding，v 代表 video 的 embedding。深度學習的任務是從用戶觀看的歷史數據和當前上下文中學習用戶的 embedding.
用戶的觀看歷史是一個系數的、變長的視頻id序列；
用戶畫像特征：如地理位置、設備、性別、年齡、登錄狀態等連續或離散特征都被歸一化為[0,1]，和 watch vector 以及 search vector 做拼接（concat）;
example age：該特征表示視頻被上傳之后的時間;
目標函數是
watch_minutes_per_impression，而不是 ctr 的函數，主要避免 click-bait 問題
6 基于圖的隨機游走算法
二分圖模型的代表是 Personal Rank 和 Page Rank 算法，其核心思想是：建立用戶和物品之間的二分圖，如果樣本中某個用戶關聯了某個物品，那么該用戶點和物品點之間建立一條邊；對于圖中的每個點，以一定的概率 a 停留在原地，以概率 1 - a 走向與它相鄰的節點，這是一個馬爾可夫過程，經過多輪迭代之后，最終每個點的到達概率都會收斂到某個值。
二分圖模型
總結
回過頭來重新審視下推薦系統，它通常可分為兩部分：召回和排序。
協同過濾屬于召回的算法，目的是得到一個比較小的推薦列表，代表算法就是 MF 和基于神經網絡的超大規模分類模型。
而從小的推薦列表中篩選出最終的推薦列表，就需要排序。排序的前提是要給某種環境下的用戶和物品之間的匹配度打分，通常是 0 到 1 之間的一個小數。然后再取排名靠前的物品作為最終要推薦的物品，這一過程又叫做 CTR 預估。常見的排序模型有 LR、GBDT、FM 等。
一個好的推薦系統中一般存在多個模型，而每個模型的最佳效果需要工程師在實踐中摸索調試出來的，每個基礎模型又有很多改良版本，針對不同的問題效果也可能不同。所以，后續文章中，我們將繼續深入研究模型細節，并深入理解模型背后的設計思想，也歡迎讀者關注我的頭條號“自由技藝”。
