達(dá)觀數(shù)據(jù)推薦系統(tǒng)算法實(shí)踐——重排序

互聯(lián)網(wǎng)的出現(xiàn)和普及給用戶帶來了大量的信息，滿足了用戶在信息時(shí)代對(duì)信息的需求，但隨著網(wǎng)絡(luò)的迅速發(fā)展而帶來的網(wǎng)上信息量的大幅增長(zhǎng)，使得用戶在面對(duì)大量信息時(shí)無法從中獲得對(duì)自己真正有用的那部分信息，對(duì)信息的使用效率反而降低了，形成了信息過載（informationoverload）的問題。

達(dá)觀數(shù)據(jù)解決信息過載有幾種手段：一種是搜索，在用戶有明確的信息需求的時(shí)候，將意圖轉(zhuǎn)換為幾個(gè)簡(jiǎn)短的關(guān)鍵字，將關(guān)鍵字提交到相應(yīng)的搜索引擎，搜索引擎從海量的信息庫中檢索出相關(guān)信息返回給客戶；另一種是推薦，在用戶意圖不明確或者難以表達(dá)時(shí)，尤其是近些年來，隨著移動(dòng)互聯(lián)網(wǎng)的興起，用戶并不一定帶著明確的意圖去瀏覽，很多時(shí)候是帶著“逛”或者打發(fā)時(shí)間的心態(tài)去瀏覽網(wǎng)頁或者APP，這種情境下解決信息過載，理解用戶意圖，根據(jù)用戶喜好推送個(gè)性化的結(jié)果，推薦系統(tǒng)便是一種比較好的選擇。達(dá)觀數(shù)據(jù)在搜索引擎和推薦系統(tǒng)兩個(gè)方面都有較深的功底，并且廣受客戶青睞！本文主要先簡(jiǎn)單介紹下推薦系統(tǒng)的流程框架，然后主要介紹下重排序。（達(dá)觀數(shù)據(jù) 孟禮斌）

推薦系統(tǒng)流程框架

從框架上看，推薦系統(tǒng)流程可以分為數(shù)據(jù)清洗、數(shù)據(jù)存儲(chǔ)、候選集生成、候選集融合規(guī)則過濾、重排序。首先將客戶上報(bào)過來的數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗，檢查數(shù)據(jù)的一致性，處理無效值和缺失值等，去除臟數(shù)據(jù)，處理成格式化數(shù)據(jù)存儲(chǔ)到不同類型的存儲(chǔ)系統(tǒng)中。對(duì)于用戶行為日志和推薦日志由于隨時(shí)間積累會(huì)越來越大，一般存儲(chǔ)在分布式文件系統(tǒng)（HDFS），即Hive表中，當(dāng)需要的時(shí)候可以下載到本地進(jìn)行離線分析。對(duì)于物品信息一般存儲(chǔ)在MySQL中，但是對(duì)于達(dá)觀數(shù)據(jù)，越來越多的客戶導(dǎo)致物品信息表（item_info）越來越大，所以同時(shí)也會(huì)保存在Hive表和HBase中，Hive可以方便離線分析時(shí)操作，但實(shí)時(shí)程序讀取的時(shí)候Hive表的實(shí)時(shí)性較差，所以同時(shí)也會(huì)寫一份放在HBase中供實(shí)時(shí)程序讀取。對(duì)于各個(gè)程序模塊生成的結(jié)果，有進(jìn)程同步關(guān)系的程序一般會(huì)使用Redis作為緩沖存儲(chǔ)，生產(chǎn)者會(huì)把信息寫到redis中供消費(fèi)者使用。候選集生成是從用戶的歷史行為、實(shí)時(shí)行為、利用各種策略和算法生成推薦的候選集。同時(shí)點(diǎn)擊反饋會(huì)根據(jù)用戶的實(shí)時(shí)操作對(duì)候選集進(jìn)行實(shí)時(shí)的調(diào)整，對(duì)于部分新用戶和歷史行為不太豐富的用戶，由于候選集太小，需要一些替補(bǔ)策略進(jìn)行補(bǔ)充。候選集融合規(guī)則過濾主要有兩個(gè)功能，一是對(duì)生成的候選集進(jìn)行融合，提高推薦策略的覆蓋度和精度；另外還需根據(jù)產(chǎn)品、運(yùn)營(yíng)的角度確定一些人為的規(guī)則，過濾掉不符合條件的item，重排序主要是利用機(jī)器學(xué)習(xí)的模型對(duì)融合后的候選集進(jìn)行重排序。（達(dá)觀數(shù)據(jù) 孟禮斌）
對(duì)于候選集生成和重排序兩個(gè)層次，為了效果迭代需要頻繁修改兩層，因此需要支持ABTest。為了支持高效率的迭代，我們對(duì)候選集觸發(fā)和重排序兩層進(jìn)行了解耦，這兩層的結(jié)果是正交的，因此可以分別進(jìn)行對(duì)比試驗(yàn)，不會(huì)相互影響。同時(shí)在每一層的內(nèi)部，我們會(huì)根據(jù)用戶將流量劃分為多份，支持多個(gè)策略同時(shí)在線對(duì)比，來提高推薦效果。

機(jī)器學(xué)習(xí)重排序
對(duì)于不同算法觸發(fā)出來的候選集，如果只是根據(jù)算法的歷史效果決定算法產(chǎn)生的item的位置顯得有些簡(jiǎn)單粗暴，同時(shí)，在每個(gè)算法的內(nèi)部，不同item的順序也只是簡(jiǎn)單的由一個(gè)或者幾個(gè)因素決定，這些排序的方法只能用于第一步的初選過程，最終的排序結(jié)果需要借助機(jī)器學(xué)習(xí)的方法，使用相關(guān)的排序模型，綜合多方面的因素來確定。
排序模型分為非線性模型和線性模型，非線性模型能較好的捕捉特征中的非線性關(guān)系，但訓(xùn)練和預(yù)測(cè)的代價(jià)相對(duì)線性模型要高一些，這也導(dǎo)致了非線性模型的更新周期相對(duì)要長(zhǎng)。相較而言，線性模型對(duì)特征的處理要求比較高，需要憑借領(lǐng)域知識(shí)和經(jīng)驗(yàn)人工對(duì)特征做一些先期處理，但因?yàn)榫€性模型簡(jiǎn)單，在訓(xùn)練和預(yù)測(cè)時(shí)效率較高。因此在更新周期上也可以做的更短，還可以結(jié)合業(yè)務(wù)做一些在線學(xué)習(xí)的嘗試。（達(dá)觀數(shù)據(jù) 孟禮斌）
2.1線性模型
線性模型主要介紹邏輯回歸（Logistic Regression），邏輯回歸是一種廣義線性模型，雖然名字里帶著回歸，但它其實(shí)是一種分類算法，主要運(yùn)用在二分類或多分類算法。在多分類中，有one-vs-rest(OvR)，和many-vs-many(MvM)兩種不同的分類思路，這里主要討論預(yù)測(cè)而分類問題（某個(gè)userid是否會(huì)點(diǎn)擊某個(gè)itemid）。
首先將每個(gè)userid和每個(gè)itemid作為特征，模型函數(shù)為：

m,k分別為userid和itemid的個(gè)數(shù)，,分別為自變量，的參數(shù)。
邏輯回歸模型采用極大似然法對(duì)模型的參數(shù)進(jìn)行估計(jì)，Cost function為：：
n為樣本個(gè)數(shù)，為樣本的label，用向量代替所有參數(shù)。然后是計(jì)算Cost function最大化時(shí)的參數(shù)。在最優(yōu)化理論中，求解最優(yōu)化參數(shù)有很多種方法，梯度下降、隨即梯度下降、牛頓法、擬牛頓法，共軛梯度法，這里選用的是牛頓法。
牛頓法的思路很簡(jiǎn)單，就是把泰勒展式展開到二階形式：

該式子成立當(dāng)且僅當(dāng)：

求解：

得出迭代公式：

牛頓法求根圖示：

相比較而言，牛頓法比梯度下降法更容易收斂（迭代更少次數(shù)），但在高維情況下，牛頓迭代公式是：
其中H是hessian矩陣：

hessian矩陣增加了計(jì)算的復(fù)雜性，不過一般候選集數(shù)量都不會(huì)太多，所以還可以接受。
對(duì)于點(diǎn)擊率預(yù)估而言，正負(fù)樣本嚴(yán)重不均衡，所以需要對(duì)負(fù)例做一些采樣。同時(shí)，在訓(xùn)練之前需要用TFIDF將訓(xùn)練數(shù)據(jù)轉(zhuǎn)換為列向量，這樣每一行是一個(gè)長(zhǎng)度為m+k的列向量，再將結(jié)果作為模型輸入訓(xùn)練，

根據(jù)交叉驗(yàn)證的結(jié)果來看，precision, recall, f1-score都在0.83左右，結(jié)果算是比較可觀。
將候選集輸入模型后，得到相應(yīng)的預(yù)測(cè)概率，該概率就是將輸入值轉(zhuǎn)化為向量后，再用logit函數(shù)歸一化道（0，1）之間的值，根據(jù)該值得到相應(yīng)的順序。（達(dá)觀數(shù)據(jù) 孟禮斌）

2.2非線性模型
非線性模型主要介紹GBDT（Gradient Boost Decision Tree），以及相應(yīng)的運(yùn)用。GBDT是一種常用的非線性模型，是Boost算法的一種，先介紹一個(gè)稱作AdaBoost的最流行的元算法。

Adaboost算法在開始的時(shí)候先為每個(gè)樣本賦一個(gè)權(quán)重值，初始的時(shí)候，每個(gè)樣本權(quán)重相同。每次迭代建立一個(gè)單層決策樹分類器（可以用任意分類器作為弱分類器，只要它比隨機(jī)猜測(cè)好略好就行不過弱分類器越簡(jiǎn)單越好），該分類器依據(jù)計(jì)算預(yù)測(cè)樣本的最小錯(cuò)誤率選出最佳單層決策樹，同時(shí)增加分錯(cuò)的點(diǎn)的權(quán)重，減少分對(duì)的點(diǎn)的權(quán)重，這樣使得某些點(diǎn)如果老是被分錯(cuò)，那么就會(huì)被“嚴(yán)重關(guān)注”，也就被賦上一個(gè)很高的權(quán)重。然后進(jìn)行N次迭代（由用戶指定），將會(huì)得到N個(gè)簡(jiǎn)單的分類器（basic learner），然后我們將它們組合起來（比如說可以對(duì)它們進(jìn)行加權(quán)、或者讓它們進(jìn)行投票等），得到一個(gè)最終的模型。

原始的Boost算法是在算法開始的時(shí)候，為每一個(gè)樣本賦上一個(gè)權(quán)重值，初始的時(shí)候，大家都是一樣重要的。在每一步訓(xùn)練中得到的模型，會(huì)使得數(shù)據(jù)點(diǎn)的估計(jì)有對(duì)有錯(cuò)，我們就在每一步結(jié)束后，增加分錯(cuò)的點(diǎn)的權(quán)重，減少分對(duì)的點(diǎn)的權(quán)重，這樣使得某些點(diǎn)如果老是被分錯(cuò)，那么就會(huì)被“嚴(yán)重關(guān)注”，也就被賦上一個(gè)很高的權(quán)重。然后等進(jìn)行了N次迭代（由用戶指定），將會(huì)得到N個(gè)簡(jiǎn)單的分類器（basic learner），然后我們將它們組合起來（比如說可以對(duì)它們進(jìn)行加權(quán)、或者讓它們進(jìn)行投票等），得到一個(gè)最終的模型。

而Gradient Boost與傳統(tǒng)的Boost的區(qū)別是，每一次的計(jì)算是為了減少上一次的殘差(residual)，而為了消除殘差，我們可以在殘差減少的梯度(Gradient)方向上建立一個(gè)新的模型。所以說，在Gradient Boost中，每個(gè)新的模型的簡(jiǎn)歷是為了使得之前模型的殘差往梯度方向減少，與傳統(tǒng)Boost對(duì)正確、錯(cuò)誤的樣本進(jìn)行加權(quán)有著很大的區(qū)別。（達(dá)觀數(shù)據(jù) 孟禮斌）
具體的算法為：

我們的目標(biāo)是在樣本空間上，找到最優(yōu)的預(yù)測(cè)函數(shù)，使得X映射到y(tǒng)的損失函數(shù)達(dá)到最小，即：

損失函數(shù)的平方誤差：

假設(shè)預(yù)測(cè)函數(shù)F(X)以P={P1,P2,…} 為參數(shù)，并可以寫成若干個(gè)弱分類器相加的形式，其中

表示第m棵回歸樹，向量αm表示第m棵回歸樹的參數(shù)，βm表示第m棵回歸樹在預(yù)測(cè)函數(shù)中的權(quán)重：

那么對(duì)于N個(gè)樣本點(diǎn)，其優(yōu)化問題等價(jià)于找到參數(shù){}，m=0,1,2,…,M,使得：

求解歸為以下迭代過程：
1. ?首先定義初始化分類器為常數(shù)，其中(X), 表示初始化弱分類器，常數(shù)，使得初始預(yù)測(cè)損失函數(shù)達(dá)到最小值：

2. ?在每次迭代中都構(gòu)造一個(gè)基于回歸樹的弱分類器，并設(shè)第m次迭代后得到的預(yù)測(cè)函數(shù)為Fm(X), 相應(yīng)的預(yù)測(cè)函數(shù)為L(zhǎng)(y,Fm(X))，為使預(yù)測(cè)損失函數(shù)減小得最快，第m個(gè)弱分類器βmh(X;αm)應(yīng)建立在前m-1次迭代生成的預(yù)測(cè)損失函數(shù)的梯度方向，其中-gm(xi)表示第m次迭代的弱分類器的建立方向，L(yi,F(xi))表示前m-1次迭代生成的預(yù)測(cè)損失函數(shù)，表達(dá)式為L(zhǎng)(yi,F(xi))=〖((y_i-F(x_i))〗^2):

基于求得的梯度下降方向，參數(shù)是使回歸樹沿此方向逼近的參數(shù)值，即：

是沿此方向搜索的最優(yōu)步長(zhǎng)，即：

3. ?更新每次迭代后得到的預(yù)測(cè)函數(shù)，即Fm(X)=F(m-1)(X)+βmh(X;αm)，若相應(yīng)的預(yù)測(cè)損失函數(shù)滿足誤差收斂條件或生成的回歸樹達(dá)到預(yù)設(shè)值M，則終止迭代。
4. ?為避免過擬合現(xiàn)象，通常在每個(gè)弱分類器前乘上“學(xué)習(xí)速率”，值域?yàn)?～1，ν值越小，學(xué)習(xí)越保守，達(dá)到同樣精度需要的迭代次數(shù)越大，反之，學(xué)習(xí)越快速，越容易出現(xiàn)過擬合：

值得一提的是，GBDT天然具有的優(yōu)勢(shì)是可以發(fā)現(xiàn)多種有區(qū)分性的特征以及特征組合。我們可以將GBDT和LR結(jié)合起來，具體如下：

先用已有特征訓(xùn)練GBDT模型，然后利用GBDT模型學(xué)習(xí)到的樹來構(gòu)造新特征，最后把這些新特征加入原有特征一起訓(xùn)練模型。構(gòu)造的新特征向量是取值0/1的，向量的每個(gè)元素對(duì)應(yīng)于GBDT模型中樹的葉子結(jié)點(diǎn)。當(dāng)一個(gè)樣本點(diǎn)通過某棵樹最終落在這棵樹的一個(gè)葉子結(jié)點(diǎn)上，那么在新特征向量中這個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)的元素值為1，而這棵樹的其他葉子結(jié)點(diǎn)對(duì)應(yīng)的元素值為0。新特征向量的長(zhǎng)度等于GBDT模型里所有樹包含的葉子結(jié)點(diǎn)數(shù)之和。

舉例說明。下面的圖中的兩棵樹是GBDT學(xué)習(xí)到的，第一棵樹有3個(gè)葉子結(jié)點(diǎn)，而第二棵樹有2個(gè)葉子節(jié)點(diǎn)。對(duì)于一個(gè)輸入樣本點(diǎn)x，如果它在第一棵樹最后落在其中的第二個(gè)葉子結(jié)點(diǎn)，而在第二棵樹里最后落在其中的第一個(gè)葉子結(jié)點(diǎn)。那么通過GBDT獲得的新特征向量為[0, 1, 0, 1, 0]，其中向量中的前三位對(duì)應(yīng)第一棵樹的3個(gè)葉子結(jié)點(diǎn)，后兩位對(duì)應(yīng)第二棵樹的2個(gè)葉子結(jié)點(diǎn)。

LR雖然簡(jiǎn)單，且訓(xùn)練預(yù)測(cè)效率高，但特征工程非常重要，現(xiàn)有的特征工程實(shí)驗(yàn)，主要集中在尋找到有區(qū)分度的特征、特征組合，折騰一圈未必會(huì)帶來效果提升。GBDT算法的特點(diǎn)正好可以用來發(fā)掘有區(qū)分度的特征、特征組合，減少特征工程中人力成本。2014 Kaggle CTR競(jìng)賽冠軍就是使用這種組合方法，筆者也是向他們學(xué)習(xí)。（達(dá)觀數(shù)據(jù) 孟禮斌）
References
Xinran He et al. Practical Lessons from Predicting Clicks on Ads at Facebook, 2014. ?