互聯網的出現和普及給用戶帶來了大量的信息，滿足了用戶在信息時代對信息的需求，但隨著網絡的迅速發展而帶來的網上信息量的大幅增長，使得用戶在面對大量信息時無法從中獲得對自己真正有用的那部分信息，對信息的使用效率反而降低了，形成了信息過載（informationoverload）的問題。
達觀數據解決信息過載有幾種手段：一種是搜索，在用戶有明確的信息需求時，將意圖轉換為幾個簡短的關鍵字，將關鍵字提交到相應的搜索引擎，搜索引擎從海量的信息庫中檢索出相關信息返回給客戶；另一種是推薦，根據用戶喜好推送個性化的結果。近些年來，隨著移動互聯網的興起，用戶並不一定帶著明確的意圖去瀏覽，很多時候是帶著“逛”或者打發時間的心態去瀏覽網頁或者APP，這種情境下推薦系統便是一種比較好的選擇，在理解用戶意圖和偏好的基礎上解決信息過載。
達觀數據在搜索引擎和推薦系統兩個方面都有較深的功底，並且廣受客戶青睞！本文主要先簡單介紹下推薦系統的流程框架，然後主要介紹下重排序。
1
推薦系統流程框架
從框架上看，推薦系統流程可以分為數據清洗、數據存儲、候選集生成、候選集融合規則過濾、重排序。
首先將客戶上報過來的數據進行數據清洗，檢查數據的一致性，處理無效值和缺失值等，去除髒數據，處理成格式化數據存儲到不同類型的存儲系統中。對於用戶行為日誌和推薦日誌由於隨時間積累會越來越大，一般存儲在分佈式文件系統（HDFS），即Hive表中，當需要的時候可以下載到本地進行離線分析。
對於物品信息一般存儲在MySQL中，但是對於達觀數據，越來越多的客戶導致物品信息表（item_info）越來越大，所以同時也會保存在Hive表和HBase中，Hive可以方便離線分析時操作，但實時程序讀取的時候Hive表的實時性較差，所以同時也會寫一份放在HBase中供實時程序讀取。對於各個程序模塊生成的結果，有進程同步關係的程序一般會使用Redis作為緩衝存儲，生產者會把信息寫到redis中供消費者使用。候選集生成是從用戶的歷史行為、實時行為、利用各種策略和算法生成推薦的候選集。
同時點擊反饋會根據用戶的實時操作對候選集進行實時的調整，對於部分新用戶和歷史行為不太豐富的用戶，由於候選集太小，需要一些替補策略進行補充。候選集融合規則過濾主要有兩個功能，一是對生成的候選集進行融合，提高推薦策略的覆蓋度和精度；另外還需根據產品、運營的角度確定一些人為的規則，過濾掉不符合條件的item，重排序主要是利用機器學習的模型對融合後的候選集進行重排序。
對於候選集生成和重排序兩個層次，為了效果迭代需要頻繁修改兩層，因此需要支持ABTest。為了支持高效率的迭代，我們對候選集觸發和重排序兩層進行了解耦，這兩層的結果是正交的，因此可以分別進行對比試驗，不會相互影響。同時在每一層的內部，我們會根據用戶將流量劃分為多份，支持多個策略同時在線對比，來提高推薦效果。
2
機器學習重排序
對於不同算法觸發出來的候選集，如果只是根據算法的歷史效果決定算法產生的item的位置顯得有些簡單粗暴，同時，在每個算法的內部，不同item的順序也只是簡單的由一個或者幾個因素決定，這些排序的方法只能用於第一步的初選過程，最終的排序結果需要藉助機器學習的方法，使用相關的排序模型，綜合多方面的因素來確定。
排序模型分為非線性模型和線性模型，非線性模型能較好的捕捉特徵中的非線性關係，但訓練和預測的代價相對線性模型要高一些，這也導致了非線性模型的更新週期相對要長。相較而言，線性模型對特徵的處理要求比較高，需要憑藉領域知識和經驗人工對特徵做一些先期處理，但因為線性模型簡單，在訓練和預測時效率較高。因此在更新週期上也可以做的更短，還可以結合業務做一些在線學習的嘗試。
2.1 線性模型
線性模型主要介紹邏輯迴歸（Logistic Regression），邏輯迴歸是一種廣義線性模型，雖然名字裡帶著迴歸，但它其實是一種分類算法，主要運用在二分類或多分類算法。在多分類中，有one-vs-rest(OvR)，和many-vs-many(MvM)兩種不同的分類思路，這裡主要討論預測而分類問題（某個userid是否會點擊某個itemid）。
首先將每個userid和每個itemid作為特徵，模型函數為：
m,k分別為userid和itemid的個數，α
i
,
β
j
分別為自變量U
i
,
I
j
的參數。
邏輯迴歸模型採用極大似然法對模型的參數進行估計，Cost function為：J
(
θ
)
=
Σ
n
i
=
1
y
i
∗
h
θ
(
Z
i
)
n為樣本個數，y
i
為樣本的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與傳統的Boost的區別是，每一次的計算是為了減少上一次的殘差(residual)，而為了消除殘差，我們可以在殘差減少的梯度(Gradient)方向上建立一個新的模型。所以說，在Gradient Boost中，每個新的模型的簡歷是為了使得之前模型的殘差往梯度方向減少，與傳統Boost對正確、錯誤的樣本進行加權有著很大的區別。
具體的算法為：
我們的目標是在樣本空間上，找到最優的預測函數f
∗
(
X
)
，使得X映射到y的損失函數L
(
y
,
F
(
X
)
)
達到最小，即：
損失函數的平方誤差：
假設預測函數F(X)以P={P1,P2,…} 為參數，並可以寫成若干個弱分類器相加的形式，其中P
=
{
β
m
,
α
m
}
M
0
,第m個弱分類器的表達形式為β
m
h
(
X
;
α
m
)
，其中β
m
h
(
X
;
α
m
)
表示第m棵迴歸樹，向量α
m
表示第m棵迴歸樹的參數，β
m
表示第m棵迴歸樹在預測函數中的權重：
那麼對於N個樣本點{
x
i
,
y
i
}
N
，其優化問題等價於找到參數 {
β
m
,
α
m
}
，m=0,1,2,…,M,使得：
求解歸為以下迭代過程：
1. 首先定義初始化分類器為常數ρ
，其中F
0
(
x
)
表示初始化弱分類器，常數ρ
使得初始預測損失函數達到最小值：
2. 在每次迭代中都構造一個基於迴歸樹的弱分類器，並設第m次迭代後得到的預測函數為F
m
(
x
)
，相應的預測函數為L
(
y
,
F
m
(
x
)
)
，為使預測損失函數減小得最快，第m個弱分類器β
m
h
(
X
;
α
m
)
應建立在前m-1次迭代生成的預測損失函數的梯度方向，其中−
g
m
(
x
i
)
表示第m次迭代的弱分類器的建立方向，L
(
y
i
,
F
(
x
i
)
)
表示前m-1次迭代生成的預測損失函數，表達式為L
(
y
i
,
F
(
x
i
)
)
=
(
(
y
i
−
F
(
x
i
)
)
2
)
基於求得的梯度下降方向，參數是使迴歸樹沿此方向逼近的參數值，即：
是沿此方向搜索的最優步長，即：
3. 更新每次迭代後得到的預測函數，即F
m
(
X
)
=
F
m
−
1
(
X
)
+
β
m
(
X
;
α
m
)
，若相應的預測損失函數滿足誤差收斂條件或生成的迴歸樹達到預設值M，則終止迭代。
4. 為避免過擬合現象，通常在每個弱分類器前乘上“學習速率” v
，值域為0～1，值越小，學習越保守，達到同樣精度需要的迭代次數越大，反之，學習越快速，越容易出現過擬合：
值得一提的是，GBDT天然具有的優勢是可以發現多種有區分性的特徵以及特徵組合。我們可以將GBDT和LR結合起來，具體如下：
先用已有特徵訓練GBDT模型，然後利用GBDT模型學習到的樹來構造新特徵，最後把這些新特徵加入原有特徵一起訓練模型。構造的新特徵向量是取值0/1的，向量的每個元素對應於GBDT模型中樹的葉子結點。當一個樣本點通過某棵樹最終落在這棵樹的一個葉子結點上，那麼在新特徵向量中這個葉子結點對應的元素值為1，而這棵樹的其他葉子結點對應的元素值為0。新特徵向量的長度等於GBDT模型裡所有樹包含的葉子結點數之和。
舉例說明。下面的圖中的兩棵樹是GBDT學習到的，第一棵樹有3個葉子結點，而第二棵樹有2個葉子節點。對於一個輸入樣本點x，如果它在第一棵樹最後落在其中的第二個葉子結點，而在第二棵樹裡最後落在其中的第一個葉子結點。那麼通過GBDT獲得的新特徵向量為[0, 1, 0, 1, 0]，其中向量中的前三位對應第一棵樹的3個葉子結點，後兩位對應第二棵樹的2個葉子結點。
LR雖然簡單，且訓練預測效率高，但特徵工程非常重要，現有的特徵工程實驗，主要集中在尋找到有區分度的特徵、特徵組合，折騰一圈未必會帶來效果提升。GBDT算法的特點正好可以用來發掘有區分度的特徵、特徵組合，減少特徵工程中人力成本。2014 Kaggle CTR競賽冠軍就是使用這種組合方法，筆者也是向他們學習。
References
1. Xinran He et al. Practical Lessons from Predicting Clicks on Ads at Facebook, 2014. ↩
原文發佈於微信公眾號 - 達觀數據（Datagrand_）