?PaperWeekly 原創(chuàng) ·?作者 |?yancy

單位 |?字節(jié)跳動(dòng)

研究方向 |?推薦系統(tǒng)

背景

在許多場景中我們都需要模型學(xué)習(xí)到排序的能力，比如網(wǎng)頁搜索場景下我們需要根據(jù)搜索詞和文檔的相關(guān)度做排序，把更相關(guān)的文章排到前面，此時(shí)文章的相關(guān)度就是要排序的目標(biāo)。又比如在視頻推薦場景下，粗排的目標(biāo)往往是學(xué)習(xí)精排，把精排認(rèn)為更好的文章送入精排打分，此時(shí)視頻的精排打分就是要排序的目標(biāo)。Learn to Rank（LTR）要做的就是輸入一批候選（上文中的網(wǎng)頁或者視頻），算法能夠給出一種排序，使得這種排序最優(yōu)秀。本文介紹 LTR 中經(jīng)典的三種算法：RankNet、LambdaRank、LambdaMart，并介紹他們的關(guān)聯(lián)。

評(píng)價(jià)指標(biāo)

我們?nèi)绾卧u(píng)價(jià)模型給出的順序好還是壞呢？業(yè)界最常用的指標(biāo)為 NDCG，大名鼎鼎的 Softrank、LambdaMart 都是以 NDCG 為準(zhǔn)描述論文，在實(shí)踐中 NDCG 也是最為常用的指標(biāo)，下面對(duì)其進(jìn)行介紹。

首先我們那需要先計(jì)算 DCG，我們有 T 個(gè)需要排序的候選，其中 表示算法給出的第 i 個(gè)位置的 label，比如搜索場景中文章相關(guān)性分為五個(gè)檔次：非常相關(guān)、相關(guān)、中性、不相關(guān)、非常不相關(guān)，那對(duì)應(yīng)的 label 分別就是 5，4，3，2，1。對(duì)應(yīng)推薦粗排場景，可以直接使用精排的打分作為 label。分母則對(duì)位置做折算，越靠前的位置越重要。這個(gè)也比較符合直覺，我們搜索之后得到結(jié)果也是會(huì)更關(guān)注靠前的網(wǎng)頁是否能快速滿足我們的興趣，如果前面幾個(gè)結(jié)果相關(guān)性較差，我們更容易認(rèn)為算法的表現(xiàn)不盡人意。如果沒有這個(gè)分母的位置折算的話，不管算法如何排序，得到的反饋都是一樣的?？梢钥闯鋈绻惴ò逊?jǐn)?shù)更高的候選排的越靠前，DCG 也就越高。

DCG 計(jì)算出來的分?jǐn)?shù)是一個(gè)考慮位置折算的累積收益，絕對(duì)值大小 的量綱有直接的關(guān)系，我們很難通過 DCG 的絕對(duì)值來判斷算法的效果，不具備直觀性，因此引出 NDCG：我們按照 label 倒排，得到最優(yōu)的排序，計(jì)算這個(gè)排序下的 DCG，這就是我們算法能達(dá)到的最優(yōu)上限 maxDCG，用 DCG/maxDCG 就得到了最終的 NDCG 指標(biāo)，所以 NDCG 是一個(gè)介于 0-1 之間的值，值越大算法效果越好。

RankNet

從上面的計(jì)算公式可以看出 NDCG 是不可直接求導(dǎo)的，因?yàn)槠渲猩婕暗脚判蜻@種算子，這個(gè)本身就是不連續(xù)不可求導(dǎo)的，也就是論文中經(jīng)常提到的 LTR 任務(wù)是 Non-Smooth 的原因。RankNet 解決排序的思路其實(shí)是把一個(gè) list 排序的問題轉(zhuǎn)化成 list 中兩兩比較的問題，舉個(gè)例子來說比如你想買房子，給你一堆房源你很可能挑花眼，很難給出正確的排序。但是只給你兩個(gè)做比較，你就可以從價(jià)格、面積、朝向這些維度進(jìn)行比較，比較容易得出孰優(yōu)孰略的結(jié)論，如果你具備了兩兩比較的能力，那用這個(gè)能力給出整體的排序就水到渠成了。

所以 RankNet 的訓(xùn)練數(shù)據(jù)不是輸入一個(gè)一個(gè)的 list，而是輸入一個(gè)一個(gè)的 pair，比如文章（i , j）。我們也知道 i 和 j 的 label。

模型對(duì)兩個(gè)候選給出的打分為 。我們建模的目標(biāo)是一個(gè)概率，即模型認(rèn)為候選 i 比候選 j 更相關(guān)的概率：

這里注意 只是一個(gè)超參常數(shù)，并不是 sigmoid 函數(shù)，論文中使用了這種 notation，本文也進(jìn)行了保留。其實(shí)實(shí)踐中基本都是設(shè)置為 1。既然是要最大化概率，那用我們?cè)诙诸愵I(lǐng)域最熟悉的交叉熵?fù)p失：

其中 的意義為如果 i 的 label 比 j 大（i 比 j 更相關(guān)）則為 1，認(rèn)為是正例。如果 i 的 label 比 j 小為 -1，認(rèn)為是負(fù)例。如果打平則為 0。這里的 或者 就是模型輸出的 logit，可以是神經(jīng)網(wǎng)絡(luò)不過 sigmoid 輸出的最后一層 logit，也可以是簡單的 LR 的輸出，沒有任何模型上的限制。RankNet 只是在 loss 層做了修改，可以適配 pointwise 中的所有模型結(jié)構(gòu)。模型通過上述方式訓(xùn)練完成后，只需要在預(yù)測的時(shí)候得到每個(gè)文檔的 logit ，按照這個(gè)得分倒排即可。

這里既然提到了 pointwise，可以稍微拓展講一下 pointwise 算法。繼續(xù)拿上文提到的網(wǎng)頁搜索舉例子，pointwise 的思路就是不需要標(biāo)注一次搜索后網(wǎng)頁的相關(guān)性，而是根據(jù)用戶的行為決定正負(fù)例。如果一個(gè)網(wǎng)頁曝光后點(diǎn)擊就是正例，否則為負(fù)例。一般模型特征會(huì)加入 query 類和網(wǎng)頁類以及 context 特征。

最后模型輸出的是一個(gè)網(wǎng)頁會(huì)不會(huì)被點(diǎn)擊的概率，評(píng)價(jià)指標(biāo)往往是 auc、F1 這種不考慮 list 順序的指標(biāo)。按照這個(gè)概率倒排作為排序的標(biāo)準(zhǔn)。從這里可以看出 pointwise 模型并不會(huì)考慮一次搜索結(jié)果后各網(wǎng)頁之間的關(guān)系，并不是從全局的排序關(guān)系來考慮問題的，因此得到的排序結(jié)果也可能不是最優(yōu)的。而 pair-wise 和 list-wise 算法則會(huì)建模 list 各元素的相關(guān)關(guān)系。

RankNet的加速

看到這里很多讀者已經(jīng)發(fā)現(xiàn)了 rankNet 的復(fù)雜度極其高，比如需要排序的 list 有 3 個(gè)候選的時(shí)候，我們就需要兩兩拆分成 6 個(gè) pair 來訓(xùn)練。但其實(shí)我們可以做優(yōu)化，首先我們可以利用 pair loss 的對(duì)稱性減少一半的計(jì)算量。觀察我們的 loss：

這里就是簡單的推導(dǎo)和合并同類項(xiàng)，詳細(xì)的過程參考附錄。對(duì)于一個(gè) pair(i,j)，我們假設(shè) i 的相關(guān)性比 j 更強(qiáng)，也就是 ，這時(shí)候產(chǎn)生的 loss：。

如果我們把這個(gè) pair 反過來，也就是（j,i），這時(shí) 。產(chǎn)生的 loss：

所以 pair 調(diào)換順序產(chǎn)生的 loss 是完全一樣的，因此我們只需要考慮 i 比 j 更相關(guān)的 pair 即可，接下來我們對(duì)模型參數(shù)求導(dǎo)：

首先基于公式（1）求導(dǎo)：

觀察上述兩個(gè)公式，易得：

假設(shè)模型內(nèi)部用到的參數(shù)為 w，則利用鏈?zhǔn)椒▌t和公式（2）（3）得到：

我們把

402 Payment Required

這一項(xiàng)定義為 ，則有

再結(jié)合上面提到的 pair loss 對(duì)稱性，我們定義一個(gè) pair 集合：I:{i,j}，其中 ，我們只需要計(jì)算 I 集合的 loss，則：

其中 這里 的數(shù)學(xué)表達(dá)比較繞，其實(shí)說白了就是針對(duì)一個(gè)文檔 i，找出所有 label 比 i 小的文章 j，然后把這些 全部加起來。然后找到所有 label 比 i 大的文章 j，然后把這些 也全部加起來，兩部分和一減變得到了 。你可能覺得這個(gè)推導(dǎo)非常難，其實(shí)舉個(gè)只有三個(gè)文檔的例子你就懂了：

加入三篇文章 1，2，3 的 label 依次減少。記得我們前面提到的 pair loss 對(duì)稱性，我們只需要關(guān)注 i 比 j ?label 更高的 pair 即可。則 I = {(1,2),(1,3),(2,3)}，帶入公式（5）有：

這里文章 1 得分最高，所以碰到誰都可以欺負(fù)，因此 都是正的。文章 2 能欺負(fù)文章 3，但是欺負(fù)不了 1，因此 符號(hào)是正的， 符號(hào)是負(fù)的。文章 3 最弱，碰到誰都是負(fù)號(hào)。

寫到這里可能有同學(xué)會(huì)問，我們大費(fèi)周折得到這樣的合并有什么好處的，我來告訴你好處大大的，因?yàn)楹喜⒅竺總€(gè) 都只要計(jì)算一次，如果不合并的話 是不是要 bp 兩次，但是現(xiàn)在只需要 bp 一次，和 point-wise 的復(fù)雜度是一模一樣的。多出來的計(jì)算量只是在 fp 的時(shí)候計(jì)算 。

LambdaRank

基于公式（4）并利用 pair loss 對(duì)稱性，我們對(duì) w 的梯度做一定的變形：

這里可以看出來 和 肯定是異號(hào)的，當(dāng)優(yōu)化器想讓 C 減少的時(shí)候， 肯定是增加的，同時(shí) 是同等程度的減少，并且增加或者減少的幅度和 相關(guān)，如果 越小， 增加的更多。 越小表示模型認(rèn)為候選 i 比 j 差的概率更高，注意我們約定 pair 是 i 肯定是比 j 更相關(guān)的，那說明模型錯(cuò)誤的更多，這個(gè)時(shí)候把 i 和 j 分的更開是很符合我們的直覺的。

這里我們看出 表明了模型把 ij 分開的動(dòng)力有多大，因?yàn)?rankNet 僅考慮 pair 的順序，并不考慮 i 或者 j 處在的位置，比如針對(duì) NDCG 指標(biāo)，校準(zhǔn)第一二位置的亂序以及倒數(shù)一二位置的亂序得到的 NDCG gain 是完全不同的，但是 RankNet 無法感知到這兩個(gè) pair 重要性的不同。所以 LambdaRank 對(duì) 加入了一個(gè)啟發(fā)式的權(quán)重：

表示交換 ij 位置之后對(duì)于 NDCG 的影響，表示的是當(dāng)把 j 換到 i 之后 NDCG 能增加多少。 即 DCG 的分子部分：。 即 DCG 的分母部分：。如果 越大表示這個(gè) pair 校準(zhǔn)后對(duì) NDCG 的影響越大，因此增加梯度，更加拉開 ij 的差距。Paper 也證明了這樣的權(quán)重是可以直接優(yōu)化 NDCG 的。如果你用的是其他指標(biāo)，也直接把對(duì)應(yīng)指標(biāo)的變化放在這里就可以直接對(duì)指標(biāo)進(jìn)行優(yōu)化。

最后再提一句：LambdaMart 其實(shí)就是 lambdaRank 的 gbdt 樹版本。至此 RankNet 和 LambdaRank 已經(jīng)介紹完畢，可以看出這里還是用 pairwise 的思路來解決 listwise 的問題。歡迎對(duì)這兩個(gè)算法感興趣的同學(xué)在文章下面留言，大家一起進(jìn)行討論。后續(xù)我會(huì)繼續(xù)分享 softRank，直接使用概率論的思路把排序變成一個(gè)可求導(dǎo)的問題，思路非常巧妙。如果大家對(duì)一些算法特別感興趣也可以留言，我抽時(shí)間進(jìn)行研讀后來和大家進(jìn)行討論。如果本文對(duì)您有幫助，希望能不吝點(diǎn)贊、評(píng)論和分享，這是對(duì)我的最大幫助！

附錄

損失函數(shù)的推導(dǎo)：

參考文獻(xiàn)

[1]Burges, Christopher JC. "From ranknet to lambdarank to lambdamart: An overview." Learning 11, no. 23-581 (2010): 81.

[2]C.J.C. Burges, R. Ragno and Q.V. Le. Learning to Rank with Non-Smooth Cost Functions.?Advances in Neural Information Processing Systems, 2006.

特別鳴謝

感謝 TCCI 天橋腦科學(xué)研究院對(duì)于 PaperWeekly 的支持。TCCI 關(guān)注大腦探知、大腦功能和大腦健康。

更多閱讀

#投 稿?通 道#

?讓你的文字被更多人看到?

如何才能讓更多的優(yōu)質(zhì)內(nèi)容以更短路徑到達(dá)讀者群體，縮短讀者尋找優(yōu)質(zhì)內(nèi)容的成本呢？答案就是：你不認(rèn)識(shí)的人。

總有一些你不認(rèn)識(shí)的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學(xué)者和學(xué)術(shù)靈感相互碰撞，迸發(fā)出更多的可能性。?

PaperWeekly 鼓勵(lì)高校實(shí)驗(yàn)室或個(gè)人，在我們的平臺(tái)上分享各類優(yōu)質(zhì)內(nèi)容，可以是最新論文解讀，也可以是學(xué)術(shù)熱點(diǎn)剖析、科研心得或競賽經(jīng)驗(yàn)講解等。我們的目的只有一個(gè)，讓知識(shí)真正流動(dòng)起來。

📝?稿件基本要求：

? 文章確系個(gè)人原創(chuàng)作品，未曾在公開渠道發(fā)表，如為其他平臺(tái)已發(fā)表或待發(fā)表的文章，請(qǐng)明確標(biāo)注?

? 稿件建議以?markdown?格式撰寫，文中配圖以附件形式發(fā)送，要求圖片清晰，無版權(quán)問題

? PaperWeekly 尊重原作者署名權(quán)，并將為每篇被采納的原創(chuàng)首發(fā)稿件，提供業(yè)內(nèi)具有競爭力稿酬，具體依據(jù)文章閱讀量和文章質(zhì)量階梯制結(jié)算

📬?投稿通道：

? 投稿郵箱：hr@paperweekly.site?

? 來稿請(qǐng)備注即時(shí)聯(lián)系方式（微信），以便我們?cè)诟寮x用的第一時(shí)間聯(lián)系作者

? 您也可以直接添加小編微信（pwbot02）快速投稿，備注：姓名-投稿

△長按添加PaperWeekly小編

🔍

現(xiàn)在，在「知乎」也能找到我們了

進(jìn)入知乎首頁搜索「PaperWeekly」

點(diǎn)擊「關(guān)注」訂閱我們的專欄吧

·

總結(jié)

以上是生活随笔為你收集整理的排序学习（LTR）经典算法：RankNet、LambdaRank和LambdaMart的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。