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