每天一個知識點——L2R

面試的時候，雖然做過醫療文獻搜索，也應用過L2R的相關模型，但涉及到其中的一些技術細節，都會成為我拿不下offer永遠的痛。也嘗試過去理解去背下一些知識點，終究沒有力透紙背，隨著時間又開始變得模糊，下面對相關問題進行一個總結。

一、PointWise、PairWise和ListWise

這個并不是特定的算法，而是排序模型的設計思路，主要體現在損失函數（Loss Function）以及相應的標簽標注方式和優化方法的不同。

PointWise

可以訓練一個二分類網絡： $h_{\theta }(q_{i},c_{i,j})\rightarrow y_{i,j}$ ，其中 $0\leq y_{i,j}\leq 1$ 。訓練的目標是最小化數據集中所有問題和候選句子對的交叉熵。

缺陷是雖然預測分數，但損失函數只考慮正負樣本，并不要求精確打分，正樣本內的先后關系并不在考慮范圍。

Pointwise常見算法有SVM等

PairWise

損失函數為合頁損失函數：

$L=max\{0,m-h_{\theta }(q_{i},c_{i}^{+})+h_{\theta }(q_{i},c_{i}^{-})\}$

這里m為邊界閾值，即正樣本的得分不僅要比負樣本的高，而且還要高出一定閾值范圍， $h_{\theta }(q_{i},c_{i}^{+})-h_{\theta }(q_{i},c_{i}^{-})\geq m$ 。

缺陷是對噪音更加敏感，比如一個樣本標注錯誤，會引起多個pair對錯誤，僅考慮了pair對的相對位置信息，并沒有考慮到絕對位置信息。

Pairwise常見算法有Ranking SVM、RankNet、RankBoost等。

ListWise

在訓練過程中給定提問 $q_{i}$ 和它的一系列候選句子 $C(c_{i1},c_{i2},...,c_{im})$ 和標簽? $Y(y_{i1},y_{i2},...,y_{im})$ ,歸一化的得分向量 $S$ 通過如下公式計算：

$Score_j=h_\theta(q_i,c_{ij})$

$S=softmax([Score_1,Score_2,...,Score_m])$

標簽歸一化為，

$Y=\frac{Y}{\sum_{j=1}^{m}y_{ij}}$

訓練的目標可以為最小化 $S$ 和 $Y$ 的KL散度。

Listwise常見算法有AdaRank，SoftRank，LambdaMART等

二、RankNet、LambdaRank和LambdaMart

RankNet

RankNet的訓練數據是一個個的pair對，比如文章（i,j）,然后模型對兩個候選進行打分，我們建模的目標是一個概率，即模型認為候選i比候選j更相關的概率：

$P_{ij}=\frac{1}{1+e^{-\sigma (s_i-s_j)}}$

$C=-\bar{P}_{ij}logP_{ij} - (1-\bar{P}_{ij})log(1-P_{ij})$

$\bar{P}_{ij}=\frac{1}{2}(1+s_{ij})$ , $s_{ij}\in \{-1, 0, 1\}$

LambdaRank

首先對RankNet的損失函數進行分解，得到其中的梯度，

$\begin{aligned} \frac{\partial C}{\partial \omega _k} &=\frac{\partial C}{\partial s _i}\frac{\partial s _i}{\partial \omega _k} + \frac{\partial C}{\partial s _j}\frac{\partial s _j}{\partial \omega _k} \\ &=\sigma (\frac{1}{2}(1-S_{ij}) - \frac{1}{1+e^{\sigma (s_i-s_j)}})(\frac{\partial s_i}{\partial \omega_k} - \frac{\partial s_j}{\partial \omega_k}) \\ &=\lambda _{ij}(\frac{\partial s_i}{\partial \omega_k} - \frac{\partial s_j}{\partial \omega_k}) \end{aligned}$

$\lambda _{ij}$ 可以表示梯度的強度，進一步簡化，假設對于文檔對(i,j)，都有文檔i在文檔j前面，即 $S_{ij}=1$ ,則

$\lambda _{ij}=\frac{-\sigma }{1+e^{\sigma (s_i-s_j)}}$

LambdaRank主要創新點在于不直接定義模型的損失函數再求梯度，而是通過分析RankNet排序損失函數的梯度再直接對梯度lambda進行修改。

現在將NDCG，ERR等指標引入lambda中，論文中的做法是交換兩個文檔i，j的位置，然后計算評估指標的變化情況 $|\Delta Z|$ ,把 $|\Delta Z|$ 作為lambda的因子，Z可以是NDCG等評價指標

$\lambda _{ij}=\frac{-\sigma }{1+e^{\sigma(s_i-s_j)}}|\Delta Z|$

通過梯度lambda也可以反推出LambdaRank的損失函數，如下，

$C=log(1+e^{-\sigma (o_i-o_j)})|\Delta Z|$

三、LambdaMart的實現原理

MART: Multiple Additive Regression Tree

GBDT:?Gradient Boosting Decision Tree

基于多個決策樹來預測結果；
決策樹之間通過加法模型疊加結果；
每棵決策樹都是針對之前決策樹的不足進行改進。

在這里插入圖片描述

?綜上的偽代碼可知，lambdaMart的計算經歷這樣幾個步驟

?利用訓練數據每個query的pair對情況，計算 $\lambda$ ，

$|\Delta Z|=\frac{abs(single\_dcgs[(i,j)] + single\_dcgs[(j,i)] - single\_dcgs[(i,i)] -single\_dcgs[(j,j)])}{IDCG}$

$single\_dcgs[(i,j)]=\frac{2^{scores[i]} - 1}{log_2(j + 1)}$

$rho = \frac{1}{1+e^{temp\_scores[i] - temp\_scores[j]}}$

$\lambda _i = \lambda _i + rho *|\Delta Z|$

$\lambda _j = \lambda _j - rho *|\Delta Z|$ ?

同時，計算的，還有權重參數 $\omega$ ，用于牛頓迭代法，但實際代碼中感覺沒有用到這一塊。

$w[i] = w[i] + rho *(1-rho) *|\Delta Z|$

$w[j] = w[j] + rho *(1-rho) *|\Delta Z|$

? ? ? ? 2. 以每個樣本特征為 $X$ ，以 $\lambda$ 為擬合目標 $Y$ ，構建決策樹，

$tree = DecisionTreeRegressor(max\_depth=50) \\ tree.fit(self.training\_data[:, 2:], \lambda )$

? ? ? ? 3. 然后用訓練的決策樹去預測 $X$ 的分數，將得到分數加入 $temp\_scores$ 中，

$pred = tree.predict(self.training\_data[:, 2:]) \\ predicted\_scores = predicted\_scores + self.lr * pred$

? ? ? ? 4、然后重復上面3個步驟，訓練多棵決策樹。

說到決策樹的訓練：lambdaMART采用最樸素的最小二乘法，也就是最小化平方誤差和來分裂節點：即對于某個選定的feature，選定一個值val，所有<=val的樣本分到左子節點，>val的分到右子節點。然后分別對左右兩個節點計算平方誤差和，并加在一起作為這次分裂的代價。遍歷所有feature以及所有可能的分裂點val(每個feature按值排序，每個不同的值都是可能的分裂點)，在這些分裂中找到代價最小的。

五、評價指標

NDCG

$DCG@T=\sum_{i=1}^{T}\frac{2^{l_i}-1}{log(1+i)}$

$NDCG@T=\frac{DCG@T}{maxDCG@T}$

這里計算的時候，會可能會采取兩種策略，需要注意下：

? ? ? ? 1、預測結果的分數不要，只要文檔的順序，而具體分數用文檔真實的分數，也就是分子分母計算的 $l_i$ 用的是同一套，只不過由于預測文檔的先后順序出現變動，最大分數未必會出現在第一位；

? ? ? ? 2、分子用預測分數，分母用真實分數。

另外需要注意的一點是分子分母計算面對可能并非完全一樣的樣本集。

六、參考文獻

排序學習（LTR）經典算法：RankNet、LambdaRank和LambdaMart
LambdaMART簡介-基于Ranklib源碼（Regression Tree訓練）
LambdaMART簡介-基于Ranklib源碼（lambda計算）

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/37988.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/37988.shtml
英文地址，請注明出處：http://en.pswp.cn/news/37988.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！