達(dá)觀數(shù)據(jù)：推薦系統(tǒng)算法實(shí)踐之重排序
互聯(lián)網(wǎng)的出現(xiàn)和普及給用戶帶來了大量的信息，滿足了用戶在信息時(shí)代對信息的需求，但隨著網(wǎng)絡(luò)的迅速發(fā)展而帶來的網(wǎng)上信息量的大幅增長，使得用戶在面對大量信息時(shí)無法從中獲得對自己真正有用的那部分信息，對信息的使用效率反而降低了，形成了信息過載(informationoverload)的問題。
達(dá)觀數(shù)據(jù)解決信息過載有幾種手段：一種是搜索，在用戶有明確的信息需求的時(shí)候，將意圖轉(zhuǎn)換為幾個簡短的關(guān)鍵字，將關(guān)鍵字提交到相應(yīng)的搜索引擎，搜索引擎從海量的信息庫中檢索出相關(guān)信息返回給客戶;另一種是推薦，在用戶意圖不明確或者難以表達(dá)時(shí)，尤其是近些年來，隨著移動互聯(lián)網(wǎng)的興起，用戶并不一定帶著明確的意圖去瀏覽，很多時(shí)候是帶著“逛”或者打發(fā)時(shí)間的心態(tài)去瀏覽網(wǎng)頁或者APP，這種情境下解決信息過載，理解用戶意圖，根據(jù)用戶喜好推送個性化的結(jié)果，推薦系統(tǒng)便是一種比較好的選擇。本文主要先簡單介紹下推薦系統(tǒng)的流程框架，然后主要介紹下重排序。
1. 推薦系統(tǒng)流程框架
從框架上看，推薦系統(tǒng)流程可以分為數(shù)據(jù)清洗、數(shù)據(jù)存儲、候選集生成、候選集融合規(guī)則過濾、重排序。首先將客戶上報(bào)過來的數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗，檢查數(shù)據(jù)的一致性，處理無效值和缺失值等，去除臟數(shù)據(jù)，處理成格式化數(shù)據(jù)存儲到不同類型的存儲系統(tǒng)中。對于用戶行為日志和推薦日志由于隨時(shí)間積累會越來越大，一般存儲在分布式文件系統(tǒng)(HDFS)，即Hive表中，當(dāng)需要的時(shí)候可以下載到本地進(jìn)行離線分析。對于物品信息一般存儲在MySQL中，但是對于達(dá)觀數(shù)據(jù)，越來越多的客戶導(dǎo)致物品信息表(item_info)越來越大，所以同時(shí)也會保存在Hive表和HBase中，Hive可以方便離線分析時(shí)操作，但實(shí)時(shí)程序讀取的時(shí)候Hive表的實(shí)時(shí)性較差，所以同時(shí)也會寫一份放在HBase中供實(shí)時(shí)程序讀取。對于各個程序模塊生成的結(jié)果，有進(jìn)程同步關(guān)系的程序一般會使用Redis作為緩沖存儲，生產(chǎn)者會把信息寫到redis中供消費(fèi)者使用。候選集生成是從用戶的歷史行為、實(shí)時(shí)行為、利用各種策略和算法生成推薦的候選集。同時(shí)點(diǎn)擊反饋會根據(jù)用戶的實(shí)時(shí)操作對候選集進(jìn)行實(shí)時(shí)的調(diào)整，對于部分新用戶和歷史行為不太豐富的用戶，由于候選集太小，需要一些替補(bǔ)策略進(jìn)行補(bǔ)充。候選集融合規(guī)則過濾主要有兩個功能，一是對生成的候選集進(jìn)行融合，提高推薦策略的覆蓋度和精度;另外還需根據(jù)產(chǎn)品、運(yùn)營的角度確定一些人為的規(guī)則，過濾掉不符合條件的item，重排序主要是利用機(jī)器學(xué)習(xí)的模型對融合后的候選集進(jìn)行重排序。
對于候選集生成和重排序兩個層次，為了效果迭代需要頻繁修改兩層，因此需要支持ABTest。為了支持高效率的迭代，我們對候選集觸發(fā)和重排序兩層進(jìn)行了解耦，這兩層的結(jié)果是正交的，因此可以分別進(jìn)行對比試驗(yàn)，不會相互影響。同時(shí)在每一層的內(nèi)部，我們會根據(jù)用戶將流量劃分為多份，支持多個策略同時(shí)在線對比，來提高推薦效果。
2. 機(jī)器學(xué)習(xí)重排序
對于不同算法觸發(fā)出來的候選集，如果只是根據(jù)算法的歷史效果決定算法產(chǎn)生的item的位置顯得有些簡單粗暴，同時(shí)，在每個算法的內(nèi)部，不同item的順序也只是簡單的由一個或者幾個因素決定，這些排序的方法只能用于***步的初選過程，最終的排序結(jié)果需要借助機(jī)器學(xué)習(xí)的方法，使用相關(guān)的排序模型，綜合多方面的因素來確定。
排序模型分為非線性模型和線性模型，非線性模型能較好的捕捉特征中的非線性關(guān)系，但訓(xùn)練和預(yù)測的代價(jià)相對線性模型要高一些，這也導(dǎo)致了非線性模型的更新周期相對要長。相較而言，線性模型對特征的處理要求比較高，需要憑借領(lǐng)域知識和經(jīng)驗(yàn)人工對特征做一些先期處理，但因?yàn)榫€性模型簡單，在訓(xùn)練和預(yù)測時(shí)效率較高。因此在更新周期上也可以做的更短，還可以結(jié)合業(yè)務(wù)做一些在線學(xué)習(xí)的嘗試。
2.1線性模型
線性模型主要介紹邏輯回歸(Logistic Regression)，邏輯回歸是一種廣義線性模型，雖然名字里帶著回歸，但它其實(shí)是一種分類算法，主要運(yùn)用在二分類或多分類算法。在多分類中，有one-vs-rest(OvR)，和many-vs-many(MvM)兩種不同的分類思路，這里主要討論預(yù)測而分類問題(某個userid是否會點(diǎn)擊某個itemid)。
首先將每個userid和每個itemid作為特征，模型函數(shù)為：
- gz=i=1mαi*Ui+j=1kβj*Ij
- hz=11+e-g(Z)
m,k分別為userid和itemid的個數(shù)，αi, βj分別為自變量Ui，Ij的參數(shù)。
邏輯回歸模型采用極大似然法對模型的參數(shù)進(jìn)行估計(jì)，Cost function為：Jθ=i=1nyi*hθ(Zi)：
n為樣本個數(shù)，yi為樣本的label，用θ向量代替所有參數(shù)。然后是計(jì)算Cost function***化時(shí)的參數(shù)。在***化理論中，求解***化參數(shù)有很多種方法，梯度下降、隨即梯度下降、牛頓法、擬牛頓法，共軛梯度法，這里選用的是牛頓法。
牛頓法的思路很簡單，就是把泰勒展式展開到二階形式：
該式子成立當(dāng)且僅當(dāng)：
求解：
得出迭代公式：
牛頓法求根圖示：
相比較而言，牛頓法比梯度下降法更容易收斂(迭代更少次數(shù))，但在高維情況下，牛頓迭代公式是：
其中H是hessian矩陣：
hessian矩陣增加了計(jì)算的復(fù)雜性，不過一般候選集數(shù)量都不會太多，所以還可以接受。
對于點(diǎn)擊率預(yù)估而言，正負(fù)樣本嚴(yán)重不均衡，所以需要對負(fù)例做一些采樣。同時(shí)，在訓(xùn)練之前需要用TFIDF將訓(xùn)練數(shù)據(jù)轉(zhuǎn)換為列向量，這樣每一行是一個長度為m+k的列向量，再將結(jié)果作為模型輸入訓(xùn)練。
根據(jù)交叉驗(yàn)證的結(jié)果來看，precision, recall, f1-score都在0.83左右，結(jié)果算是比較可觀。
將候選集輸入模型后，得到相應(yīng)的預(yù)測概率，該概率就是將輸入值轉(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算法的一種，先介紹一個稱作AdaBoost的***的元算法。
Adaboost算法在開始的時(shí)候先為每個樣本賦一個權(quán)重值，初始的時(shí)候，每個樣本權(quán)重相同。每次迭代建立一個單層決策樹分類器(可以用任意分類器作為弱分類器，只要它比隨機(jī)猜測略好就行，不過弱分類器越簡單越好)，該分類器依據(jù)計(jì)算預(yù)測樣本的最小錯誤率選出***單層決策樹，同時(shí)增加分錯的點(diǎn)的權(quán)重，減少分對的點(diǎn)的權(quán)重，這樣使得某些點(diǎn)如果老是被分錯，那么就會被“嚴(yán)重關(guān)注”，也就被賦上一個很高的權(quán)重。然后進(jìn)行N次迭代(由用戶指定)，將會得到N個簡單的分類器(basic learner)，然后我們將它們組合起來(比如說可以對它們進(jìn)行加權(quán)、或者讓它們進(jìn)行投票等)，得到一個最終的模型。
原始的Boost算法是在算法開始的時(shí)候，為每一個樣本賦上一個權(quán)重值，初始的時(shí)候，大家都是一樣重要的。在每一步訓(xùn)練中得到的模型，會使得數(shù)據(jù)點(diǎn)的估計(jì)有對有錯，我們就在每一步結(jié)束后，增加分錯的點(diǎn)的權(quán)重，減少分對的點(diǎn)的權(quán)重，這樣使得某些點(diǎn)如果老是被分錯，那么就會被“嚴(yán)重關(guān)注”，也就被賦上一個很高的權(quán)重。然后等進(jìn)行了N次迭代(由用戶指定)，將會得到N個簡單的分類器(basic learner)，然后我們將它們組合起來(比如說可以對它們進(jìn)行加權(quán)、或者讓它們進(jìn)行投票等)，得到一個最終的模型。
而Gradient Boost與傳統(tǒng)的Boost的區(qū)別是，每一次的計(jì)算是為了減少上一次的殘差(residual)，而為了消除殘差，我們可以在殘差減少的梯度(Gradient)方向上建立一個新的模型。所以說，在Gradient Boost中，每個新的模型的簡歷是為了使得之前模型的殘差往梯度方向減少，與傳統(tǒng)Boost對正確、錯誤的樣本進(jìn)行加權(quán)有著很大的區(qū)別。
具體的算法為：
我們的目標(biāo)是在樣本空間上，找到***的預(yù)測函數(shù)f*(X)，使得X映射到y(tǒng)的損失函數(shù)L(y,F(X))達(dá)到最小，即：
損失函數(shù)的平方誤差：
假設(shè)預(yù)測函數(shù)F(X)以P={P1,P2,…} 為參數(shù)，并可以寫成若干個弱分類器相加的形式，其中P={βm,αm}0M,第m個弱分類器的表達(dá)形式為βmh(X;αm)，其中βmh(X;αm)
表示第m棵回歸樹，向量αm表示第m棵回歸樹的參數(shù)，βm表示第m棵回歸樹在預(yù)測函數(shù)中的權(quán)重：
那么對于N個樣本點(diǎn){xi,yi}N，其優(yōu)化問題等價(jià)于找到參數(shù){βm,αm}，m=0,1,2,…,M,使得：
求解歸為以下迭代過程：
1. 首先定義初始化分類器為常數(shù)ρ，其中F0(X), 表示初始化弱分類器，常數(shù)ρ，使得初始預(yù)測損失函數(shù)達(dá)到最小值：
2. 在每次迭代中都構(gòu)造一個基于回歸樹的弱分類器，并設(shè)第m次迭代后得到的預(yù)測函數(shù)為Fm(X), 相應(yīng)的預(yù)測函數(shù)為L(y, Fm(X))，為使預(yù)測損失函數(shù)減小得最快，第m個弱分類器βmh(X;αm)應(yīng)建立在前m-1次迭代生成的預(yù)測損失函數(shù)的梯度方向，其中-gm(xi)表示第m次迭代的弱分類器的建立方向，L(yi, F(xi))表示前m-1次迭代生成的預(yù)測損失函數(shù)，表達(dá)式為L(yi, F(xi))=((yi-F(xi))2):
基于求得的梯度下降方向，參數(shù)αm是使回歸樹 h(X;αm)沿此方向逼近的參數(shù)值，即：
βm是沿此方向搜索的***步長，即：
3. 更新每次迭代后得到的預(yù)測函數(shù)，即Fm(X)= Fm-1(X)+ βmh(X;αm)，若相應(yīng)的預(yù)測損失函數(shù)滿足誤差收斂條件或生成的回歸樹達(dá)到預(yù)設(shè)值M，則終止迭代。
4. 為避免過擬合現(xiàn)象，通常在每個弱分類器前乘上“學(xué)習(xí)速率”ν，值域?yàn)?～1，ν值越小，學(xué)習(xí)越保守，達(dá)到同樣精度需要的迭代次數(shù)越大，反之，學(xué)習(xí)越快速，越容易出現(xiàn)過擬合：
值得一提的是，GBDT天然具有的優(yōu)勢是可以發(fā)現(xiàn)多種有區(qū)分性的特征以及特征組合。我們可以將GBDT和LR結(jié)合起來，具體如下：
先用已有特征訓(xùn)練GBDT模型，然后利用GBDT模型學(xué)習(xí)到的樹來構(gòu)造新特征，***把這些新特征加入原有特征一起訓(xùn)練模型。構(gòu)造的新特征向量是取值0/1的，向量的每個元素對應(yīng)于GBDT模型中樹的葉子結(jié)點(diǎn)。當(dāng)一個樣本點(diǎn)通過某棵樹最終落在這棵樹的一個葉子結(jié)點(diǎn)上，那么在新特征向量中這個葉子結(jié)點(diǎn)對應(yīng)的元素值為1，而這棵樹的其他葉子結(jié)點(diǎn)對應(yīng)的元素值為0。新特征向量的長度等于GBDT模型里所有樹包含的葉子結(jié)點(diǎn)數(shù)之和。
舉例說明。下面的圖中的兩棵樹是GBDT學(xué)習(xí)到的，***棵樹有3個葉子結(jié)點(diǎn)，而第二棵樹有2個葉子節(jié)點(diǎn)。對于一個輸入樣本點(diǎn)x，如果它在***棵樹***落在其中的第二個葉子結(jié)點(diǎn)，而在第二棵樹里***落在其中的***個葉子結(jié)點(diǎn)。那么通過GBDT獲得的新特征向量為[0, 1, 0, 1, 0]，其中向量中的前三位對應(yīng)***棵樹的3個葉子結(jié)點(diǎn)，后兩位對應(yīng)第二棵樹的2個葉子結(jié)點(diǎn)。
LR雖然簡單，且訓(xùn)練預(yù)測效率高，但特征工程非常重要，現(xiàn)有的特征工程實(shí)驗(yàn)，主要集中在尋找到有區(qū)分度的特征、特征組合，折騰一圈未必會帶來效果提升。GBDT算法的特點(diǎn)正好可以用來發(fā)掘有區(qū)分度的特征、特征組合，減少特征工程中人力成本。2014 Kaggle CTR競賽冠軍就是使用這種組合方法，筆者也是向他們學(xué)習(xí)。
【本文為51CTO專欄作者“達(dá)觀數(shù)據(jù)”的原創(chuàng)稿件，轉(zhuǎn)載可通過51CTO專欄獲取聯(lián)系】
