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