達(dá)觀數(shù)據(jù)在搜索引擎和推薦系統(tǒng)兩個(gè)方面都有較深的功底，并且廣受客戶青睞！本文主要先簡(jiǎn)單介紹下推薦系統(tǒng)的流程框架，然后主要介紹下重排序。

從框架上看，推薦系統(tǒng)流程可以分為數(shù)據(jù)清洗、數(shù)據(jù)存儲(chǔ)、候選集生成、候選集融合規(guī)則過(guò)濾、重排序。

首先將客戶上報(bào)過(guò)來(lái)的數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗，檢查數(shù)據(jù)的一致性，處理無(wú)效值和缺失值等，去除臟數(shù)據(jù)，處理成格式化數(shù)據(jù)存儲(chǔ)到不同類型的存儲(chǔ)系統(tǒng)中。對(duì)于用戶行為日志和推薦日志由于隨時(shí)間積累會(huì)越來(lái)越大，一般存儲(chǔ)在分布式文件系統(tǒng)（HDFS），即Hive表中，當(dāng)需要的時(shí)候可以下載到本地進(jìn)行離線分析。

對(duì)于物品信息一般存儲(chǔ)在MySQL中，但是對(duì)于達(dá)觀數(shù)據(jù)，越來(lái)越多的客戶導(dǎo)致物品信息表（item_info）越來(lái)越大，所以同時(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ī)則過(guò)濾主要有兩個(gè)功能，一是對(duì)生成的候選集進(jìn)行融合，提高推薦策略的覆蓋度和精度；另外還需根據(jù)產(chǎn)品、運(yùn)營(yíng)的角度確定一些人為的規(guī)則，過(guò)濾掉不符合條件的item，重排序主要是利用機(jī)器學(xué)習(xí)的模型對(duì)融合后的候選集進(jìn)行重排序。

對(duì)于候選集生成和重排序兩個(gè)層次，為了效果迭代需要頻繁修改兩層，因此需要支持ABTest。為了支持高效率的迭代，我們對(duì)候選集觸發(fā)和重排序兩層進(jìn)行了解耦，這兩層的結(jié)果是正交的，因此可以分別進(jìn)行對(duì)比試驗(yàn)，不會(huì)相互影響。同時(shí)在每一層的內(nèi)部，我們會(huì)根據(jù)用戶將流量劃分為多份，支持多個(gè)策略同時(shí)在線對(duì)比，來(lái)提高推薦效果。

對(duì)于不同算法觸發(fā)出來(lái)的候選集，如果只是根據(jù)算法的歷史效果決定算法產(chǎn)生的item的位置顯得有些簡(jiǎn)單粗暴，同時(shí)，在每個(gè)算法的內(nèi)部，不同item的順序也只是簡(jiǎn)單的由一個(gè)或者幾個(gè)因素決定，這些排序的方法只能用于第一步的初選過(guò)程，最終的排序結(jié)果需要借助機(jī)器學(xué)習(xí)的方法，使用相關(guān)的排序模型，綜合多方面的因素來(lái)確定。

排序模型分為非線性模型和線性模型，非線性模型能較好的捕捉特征中的非線性關(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í)的嘗試。

2.1 線性模型

線性模型主要介紹邏輯回歸（Logistic Regression），邏輯回歸是一種廣義線性模型，雖然名字里帶著回歸，但它其實(shí)是一種分類算法，主要運(yùn)用在二分類或多分類算法。在多分類中，有one-vs-rest(OvR)，和many-vs-many(MvM)兩種不同的分類思路，這里主要討論預(yù)測(cè)而分類問(wèn)題（某個(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ù)雜性，不過(guò)一般候選集數(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)練。

將候選集輸入模型后，得到相應(yīng)的預(yù)測(cè)概率，該概率就是將輸入值轉(zhuǎn)化為向量后，再用logit函數(shù)歸一化道（0，1）之間的值，根據(jù)該值得到相應(yīng)的順序。

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è)好略好就行不過(guò)弱分類器越簡(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），然后我們將它們組合起來(lái)（比如說(shuō)可以對(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），然后我們將它們組合起來(lái)（比如說(shuō)可以對(duì)它們進(jìn)行加權(quán)、或者讓它們進(jìn)行投票等），得到一個(gè)最終的模型。

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

具體的算法為：

我們的目標(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è)弱分類器相加的形式，其中P={? ? }, 第m個(gè)弱分類器的表達(dá)形式為，其中）表示第m棵回歸樹，向量表示第m棵回歸樹的參數(shù)，表示第m棵回歸樹在預(yù)測(cè)函數(shù)中的權(quán)重：

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

求解歸為以下迭代過(guò)程：

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

2.? 在每次迭代中都構(gòu)造一個(gè)基于回歸樹的弱分類器，并設(shè)第m次迭代后得到的預(yù)測(cè)函數(shù)為（X），相應(yīng)的預(yù)測(cè)函數(shù)為L(zhǎng)(y,(X))

，為使預(yù)測(cè)損失函數(shù)減小得最快，第m個(gè)弱分類器應(yīng)建立在前m-1次迭代生成的預(yù)測(cè)損失函數(shù)的梯度方向，其中（）表示第m次迭代的弱分類器的建立方向，

L(,())

表示前m-1次迭代生成的預(yù)測(cè)損失函數(shù)，表達(dá)式為L(zhǎng)(,()) =?

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

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

3.? 更新每次迭代后得到的預(yù)測(cè)函數(shù)，即

(x) =?(x) +?

若相應(yīng)的預(yù)測(cè)損失函數(shù)滿足誤差收斂條件或生成的回歸樹達(dá)到預(yù)設(shè)值M，則終止迭代。

4.?為避免過(guò)擬合現(xiàn)象，通常在每個(gè)弱分類器前乘上“學(xué)習(xí)速率”，值域?yàn)?～1，值越小，學(xué)習(xí)越保守，達(dá)到同樣精度需要的迭代次數(shù)越大，反之，學(xué)習(xí)越快速，越容易出現(xiàn)過(guò)擬合：

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

先用已有特征訓(xùn)練GBDT模型，然后利用GBDT模型學(xué)習(xí)到的樹來(lái)構(gòu)造新特征，最后把這些新特征加入原有特征一起訓(xùn)練模型。構(gòu)造的新特征向量是取值0/1的，向量的每個(gè)元素對(duì)應(yīng)于GBDT模型中樹的葉子結(jié)點(diǎn)。當(dāng)一個(gè)樣本點(diǎn)通過(guò)某棵樹最終落在這棵樹的一個(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ù)之和。

舉例說(shuō)明。下面的圖中的兩棵樹是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)。那么通過(guò)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ì)帶來(lái)效果提升。GBDT算法的特點(diǎn)正好可以用來(lái)發(fā)掘有區(qū)分度的特征、特征組合，減少特征工程中人力成本。2014 Kaggle CTR競(jìng)賽冠軍就是使用這種組合方法，筆者也是向他們學(xué)習(xí)。

References

1.??Xinran He et al. Practical Lessons from Predicting Clicks on Ads at Facebook, 2014. ?