LTR方法總結(jié)

PointWise

這種方法沒(méi)有考慮到排序的一些特征慨削，比如文檔之間的排序結(jié)果針對(duì)的是給定查詢下的文檔集合灾搏，而Pointwise方法僅僅考慮單個(gè)文檔的絕對(duì)相關(guān)度碱呼；另外境输，在排序中蔗牡，排在最前的幾個(gè)文檔對(duì)排序效果的影響非常重要，Pointwise沒(méi)有考慮這方面的影響嗅剖。

PairWise

Ranking SVM

????Ranking SVM將排序問(wèn)題轉(zhuǎn)化為分類問(wèn)題辩越，對(duì)于一個(gè)有序特征序列x1>x2>x3，任意樣本可以構(gòu)造六個(gè)序?qū)π帕福渲?x1,x2)黔攒、(x2,x3)、(x1,x3) 是正樣本强缘，(x2,x1)督惰、(x3,x1)、(x3,x2)是負(fù)樣本旅掂，然后用

SVM訓(xùn)練一個(gè)二分類器對(duì)這些新樣本進(jìn)行分類赏胚。原理非常簡(jiǎn)單，不再贅述商虐。

RankBoost

點(diǎn)對(duì)間正負(fù)樣本的構(gòu)造方法和RankingSVM相同觉阅，只不過(guò)分類方法用了Boost框架

RankBoost框架

RankNet

http://www.cnblogs.com/genyuan/p/9788294.html?????https://blog.csdn.net/u014374284/article/details/49385065

主要參考這兩篇文章整理

對(duì)于一個(gè)Query的兩個(gè)相關(guān)文檔Ui和Uj假設(shè)Ui>Uj崖疤，通過(guò)RankNet網(wǎng)絡(luò)前向計(jì)算分別得到分?jǐn)?shù)Si和Sj，那么RankNet認(rèn)為Ui>Uj的概率為： $P_{ij} \equiv P(U_i \rhd U_j) \equiv \frac{1}{1+e^{-\sigma(s_i-s_j)}}$ ①?

進(jìn)一步得到文檔對(duì)(Ui,Uj)的交叉熵?fù)p失函數(shù)： $C_{ij} = -\overline P_{ij}logP_{ij}-(1-\overline P_{ij})log(1-P_{ij})$ ②

定義Ui比Uj更靠前的概率為： $\overline{P}_{ij}=\frac{1}{2}(1+S_{ij})$ 典勇，將這個(gè)概率帶入到②中劫哼，得到 $C=\frac{1}{2}(1-S_{ij})\sigma(s_i-s_j)+log(1+e^{-\sigma(s_i-s_j)})$ ③

該損失函數(shù)是具有對(duì)稱性的，即交換i和j的的位置損失函數(shù)不變割笙。

當(dāng)Sij=1時(shí)权烧，如果Si>Sj，有： $\lim \limits_{s_i-s_j\rightarrow\infty}C=\lim \limits_{s_i-s_j\rightarrow\infty}log\left(1+e^{-\sigma(s_i-s_j)}\right)=log1=0$

反之則有： $\lim \limits_{s_i-s_j\rightarrow\infty}C=\lim \limits_{s_i-s_j\rightarrow\infty}log\left(1+e^{-\sigma(s_i-s_j)}\right)=log\left(e^{-\sigma(s_i-s_j)}\right)=-\sigma(s_i-s_j)$ 伤溉，也就是說(shuō)當(dāng)前結(jié)果和實(shí)際結(jié)果相反時(shí)般码，Si和Sj差值越小，損失函數(shù)就越小

梯度下降的迭代公式為： $w_k\rightarrow{w_k}-\eta\frac{\partial{C}}{\partial{w_k}}={w_k}-\eta\left(\frac{\partial{C}}{\partial{s_i}}\frac{\partial{s_i}}{\partial{w_k}}+\frac{\partial{C}}{\partial{s_j}}\frac{\partial{s_j}}{\partial{w_k}}\right)$

求導(dǎo)： ${\partial C_{ij} \over \partial s_i} = \sigma ({1 \over 2}(1-S_{ij})-{1\over 1+e^{\sigma(s_i-s_j)}}) = -{\partial C_{ij} \over \partial s_j}$ ④ 可知谈火，C對(duì)Si的偏導(dǎo)數(shù)和C對(duì)sj的偏導(dǎo)之和為0

令 $\lambda_{ij} = {\partial C_{ij} \over \partial s_i} = \sigma ({1 \over 2}(1-S_{ij})-{1\over 1+e^{\sigma(s_i-s_j)}})$ 則有： $\begin{align}{\partial C \over \partial w_k} &=\underset{(i,j)\in I}{\sum}\lambda_{ij}({\partial s_i \over \partial w_k}-{\partial s_j \over \partial w_k}) \\ &=\underset{i}{\sum}\lambda_i {\partial s_i \over \partial w_k}\end{align}$ ⑤

$\lambda_{ij}$ 可以看做是Ui和Uj之間的作用力侈询，如果Ui相關(guān)性大于Uj，那么Uj會(huì)給Ui一個(gè)大小為 $|\lambda_{ij}|$ 的向上的推動(dòng)力糯耍，同理Ui會(huì)給Uj一個(gè)向下的推動(dòng)力扔字。

假設(shè)集合I中只包含label不同的URL的集合，且每個(gè)pair僅包含一次温技，即Uij和Uji等價(jià)革为，假設(shè)I中只包含(Ui,Uj)切Ui相關(guān)性大于Uj，也就是I中所有序?qū)Χ紳M足Sij>1舵鳞，則有：

$\lambda_i = \underset {j:(i,j)\in I}{\sum}\lambda_{ij} - \underset {j:(j,i)\in I}{\sum}\lambda_{ij}$ ?

因?yàn)閾p失函數(shù)Cij是對(duì)稱函數(shù)震檩，根據(jù) $\lambda_{ij}$ 的公式可以看出它也是對(duì)稱函數(shù)，即 $\lambda_{ij}=\lambda_{ji}$ 蜓堕，結(jié)合④和⑤來(lái)看抛虏，即可可以理解上式

ListWise

LambdaRank

顯然，只關(guān)注pair間的正確性是不夠的套才，RankNet無(wú)法以NDCG等只關(guān)注topk排序結(jié)果的指標(biāo)為優(yōu)化目標(biāo)迂猴。

對(duì)于上圖中兩種排序結(jié)果來(lái)講，Error Pair（錯(cuò)誤序?qū)?shù)量）1比2多背伴，所以2比1效果好?

但是從NDCG的角度來(lái)衡量沸毁，NDCG1>NDCG2，1比2效果好

因此傻寂，在RankNet中得到的 $\lambda_{ij}$ 中增加一個(gè) $\Delta Z_{ij}$ 息尺， $\lambda_{ij} = {-\sigma \over 1+e^{\sigma (s_i-s_j)}}|\Delta Z_{ij}|$ $\Delta Z_{ij}$ 表示Ui和Uj交換位置后，評(píng)估指標(biāo)的變化疾掰，它可以是 $\Delta NDCG$ 搂誉。

NDCG傾向于將排名高并且相關(guān)性高的文檔更快地向上推動(dòng)，而排名地而且相關(guān)性較低的文檔較慢地向上推動(dòng)静檬。

附：NDCG計(jì)算方法

LambdaMART

MART

MART(Multiple Additive Regression Tree)又稱為GBDT(Gradient Boosting Decision Tree)炭懊。MART第t輪的學(xué)習(xí)目標(biāo)是t-1輪的殘差浪汪，由Additive可知，前t輪所有預(yù)測(cè)結(jié)果相加即是第t輪的預(yù)測(cè)結(jié)果凛虽，并用該結(jié)果計(jì)算殘差用來(lái)迭代第t+1輪」慊郑可以用如下公式表示：

$F_n(x)=\sum_{i=1}^{N}\alpha_if_i(x)$ MART使用加權(quán)求和的方式將擬合的樹(shù)結(jié)合起來(lái)凯旋，作為最后的輸出。

為什么擬合殘差可以減小誤差钉迷？

假設(shè)擬合誤差C是關(guān)于Fn的函數(shù)至非，那么根據(jù)鏈?zhǔn)角髮?dǎo)法則有：

$\delta C \approx \frac{\partial{C(F_n)}}{\partial{F_n}}\delta F_n$ ?

當(dāng)C的梯度小于0時(shí)，誤差是減小的糠聪，所以令 $\delta F_n=-\eta \frac{\partial{C}}{\partial{F_n}}$ 可以使 $\delta C <0$ 荒椭，即Fn不斷擬合誤差C的負(fù)梯度方向來(lái)減小誤差

例如當(dāng)C是最小二乘（平方和損失）函數(shù)時(shí)： $C=\frac{1}{2}(F_n-y)^2$ ，即有 $\delta F_n=-\eta \frac{\partial{C}}{\partial{F_n}}=-\eta (F_n-y)$

從泰勒展開(kāi)的角度講：

第m輪的迭代目標(biāo)是找到一顆CART樹(shù)的弱學(xué)習(xí)器 $f_m(x,a_m)$ 舰蟆，使得 $L(y, F_{m}(x)) =L(y, F_{m-1}(x)+ h(x,a_m))$ 最小趣惠，換句話說(shuō)就是讓損失函數(shù)變得更小

將上面的損失函數(shù)進(jìn)行泰勒展開(kāi)： $L(y, F_{m}(x))=L(y, F_{m-1}(x)+ f_m(x,a_m))=L(y, F_{m-1}(x))+\frac{\partial L(y, F_{m-1}(x))}{\partial F_{m-1}}f_m(x,a_m)$

保證等號(hào)左邊的取值小于等號(hào)的右邊，顯然有 $\frac{\partial L(y, F_{m-1}(x))}{\partial F_{m-1}}f_m(x,a_m)<0$

但此時(shí)弱學(xué)習(xí)器是未知的身害，因此自然的考慮到用已知的負(fù)梯度為目標(biāo)去建立這個(gè)CART樹(shù)味悄，即 $h(x,a_m)=-\frac{\partial L(y, F_{m-1}(x))}{\partial F_{m-1}}$

根據(jù)GBDT的損失函數(shù)： $L(y,F)=log(1+exp(-2yF),y \in \{-1,1\}$

它的負(fù)梯度方向是 $\tilde{y_i}=r_{im} = -\bigg[\frac{\partial L(y_i, F(x_i)))}{\partial F(x_i)}\bigg]_{F(x) = F_{m-1}(x)}=\frac{2y_i}{(1+exp(2y_iF_{m-1}(x)))}$

第m顆回歸樹(shù)對(duì)應(yīng)的葉子節(jié)點(diǎn)區(qū)域 $\gamma_{jm}, j =1,2,..., J$ ，其中J為葉子節(jié)點(diǎn)的個(gè)數(shù)塌鸯。針對(duì)每一個(gè)葉子節(jié)點(diǎn)里的樣本侍瑟，我們求出使損失函數(shù)最小，也就是擬合葉子節(jié)點(diǎn)最好的的輸出值 $\gamma_{jm}$ 如下：

$\gamma_{jm} = \underbrace{arg\; min}_{c}\sum\limits_{x_i \in R_{jm}} L(y_i,F_{m-1}(x_i) +\gamma)=\underbrace{arg\; min}_{c}\sum\limits_{x_i \in R_{jm}} log(1+exp(-2y_i(F_{m-1}(x_i)+\gamma)))$

需要注意的是：正常的CART樹(shù)葉子節(jié)點(diǎn)的權(quán)重是落到該節(jié)點(diǎn)樣本的均值丙猬，而GBDT中CART樹(shù)的輸出還有一個(gè)學(xué)習(xí)率 $\rho$ 涨颜，以下的縮寫(xiě)是說(shuō)CART樹(shù)的輸出和學(xué)習(xí)率的乘積看成了CART回歸樹(shù)的最終輸出，可以避免設(shè)置學(xué)習(xí)率茧球。所以第m輪弱學(xué)習(xí)器擬合函數(shù)如下：

$h(x,a_m)= \sum\limits_{j=1}^{J}\gamma_{jm}I(x \in R_{jm})$

從而得到強(qiáng)學(xué)習(xí)器：

$F_{m}(x) = F_{m-1}(x) + \sum\limits_{j=1}^{J}c_{jm}I(x \in R_{jm})$

LambdaMART（MART+Lambda梯度）

最后編輯于：2019.01.20 13:20:50

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末庭瑰，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子袜腥，更是在濱河造成了極大的恐慌见擦，老刑警劉巖，帶你破解...
沈念sama閱讀 218,607評(píng)論 6贊 507
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件羹令，死亡現(xiàn)場(chǎng)離奇詭異鲤屡，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)福侈，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,239評(píng)論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)酒来，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人肪凛，你說(shuō)我怎么就攤上這事堰汉×缮纾” “怎么了？”我有些...
開(kāi)封第一講書(shū)人閱讀 164,960評(píng)論 0贊 355
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵翘鸭，是天一觀的道長(zhǎng)滴铅。經(jīng)常有香客問(wèn)我，道長(zhǎng)就乓，這世上最難降的妖魔是什么汉匙？我笑而不...
開(kāi)封第一講書(shū)人閱讀 58,750評(píng)論 1贊 294
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮生蚁，結(jié)果婚禮上噩翠，老公的妹妹穿的比我還像新娘。我一直安慰自己邦投，他們只是感情好伤锚，可當(dāng)我...
茶點(diǎn)故事閱讀 67,764評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布。她就那樣靜靜地躺著志衣，像睡著了一般屯援。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上蠢涝，一...
開(kāi)封第一講書(shū)人閱讀 51,604評(píng)論 1贊 305
城市分裂傳說(shuō)
那天玄呛，我揣著相機(jī)與錄音，去河邊找鬼和二。笑死徘铝，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的惯吕。我是一名探鬼主播惕它，決...
沈念sama閱讀 40,347評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼废登！你這毒婦竟也來(lái)了淹魄？” 一聲冷哼從身側(cè)響起，我...
開(kāi)封第一講書(shū)人閱讀 39,253評(píng)論 0贊 276
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤堡距，失蹤者是張志新（化名）和其女友劉穎甲锡，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體羽戒，經(jīng)...
沈念sama閱讀 45,702評(píng)論 1贊 315
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡缤沦，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,893評(píng)論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了易稠。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片缸废。...
茶點(diǎn)故事閱讀 40,015評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出企量，到底是詐尸還是另有隱情测萎，我是刑警寧澤，帶...
沈念sama閱讀 35,734評(píng)論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布届巩，位于F島的核電站硅瞧，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏恕汇。R本人自食惡果不足惜零酪，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,352評(píng)論 3贊 330
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望拇勃。院中可真熱鬧，春花似錦孝凌、人聲如沸方咆。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 31,934評(píng)論 0贊 22
一樁弒父案蟀架，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)瓣赂。三九已至，卻和暖如春片拍，著一層夾襖步出監(jiān)牢的瞬間煌集，已是汗流浹背。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 33,052評(píng)論 1贊 270
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工捌省，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留苫纤，地道東北人。一個(gè)月前我還...
沈念sama閱讀 48,216評(píng)論 3贊 371
代替公主和親
正文我出身青樓纲缓，卻偏偏與公主長(zhǎng)得像卷拘，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子祝高，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,969評(píng)論 2贊 355