之前的博客：http://www.cnblogs.com/bentuwuying/p/6681943.html中簡單介紹了Learning to Rank的基本原理，也講到了Learning to Rank的幾類常用的方法：pointwise，pairwise，listwise。這篇博客就很多公司在實際中通常使用的pairwise的方法進行介紹，首先我們介紹相對簡單的 RankSVM 和 IR SVM。

1. RankSVM

RankSVM的基本思想是，將排序問題轉化為pairwise的分類問題，然后使用SVM分類模型進行學習并求解。

1.1 排序問題轉化為分類問題

對于一個query-doc pair，我們可以將其用一個feature vector表示：x。而排序函數為f(x)，我們根據f(x)的大小來決定哪個doc排在前面，哪個doc排在后面。即如果f(x_i) > f(x_j)，則x_i應該排在x_j的前面，反之亦然。可以用下面的公式表示：

理論上，f(x)可以是任意函數，為了簡單起見，我們假設其為線性函數：。

如果這個排序函數f(x)是一個線性函數，那么我們便可以將一個排序問題轉化為一個二元分類問題。理由如下：

首先，對于任意兩個feature vector?x_i和?x_j，在f(x)是線性函數的前提下，下面的關系都是存在的：

然后，便可以對x_i和?x_j的差值向量考慮二元分類問題。特別地，我們可以對其賦值一個label：

1.2 SVM模型解決排序問題

將排序問題轉化為分類問題之后，我們便可以使用常用的分類模型來進行學習，這里我們選擇了Linear SVM，同樣的，可以通過核函數的方法擴展到 Nonlinear SVM。

如下面左圖所示，是一個排序問題的例子，其中有兩組query及其相應的召回documents，其中documents的相關程度等級分為三檔。而weight vector w對應了排序函數，可以對query-doc pair進行打分和排序。

而下面右圖則展示了如何將排序問題轉化為分類問題。在同一個組內（同一個query下）的不同相關度等級的doc的feature vector可以進行組合，形成新的feature vector：x₁-x₂，x₁-x₃，x₂-x₃。同樣的，label也會被重新賦值，例如x₁-x₂，x₁-x₃，x₂-x₃這幾個feature vector的label被賦值成分類問題中的positive label。進一步，為了形成一個標準的分類問題，我們還需要有negative samples，這里我們就使用前述的幾個新的positive feature vector的反方向向量作為相應的negative samples：x₂-x₁，x₃-x₁，x₃-x₂。另外，需要注意的是，我們在組合形成新的feature vector的時候，不能使用在原始排序問題中處于相同相似度等級的兩個feature vector，也不能使用處于不同query下的兩個feature vector。

? ? ? ??

?

1.2 SVM模型的求解過程

轉化為了分類問題后，我們便可以使用SVM的通用方式進行求解。首先我們可以得到下面的優化問題：

通過將約束條件帶入進原始優化問題的松弛變量中，可以進一步轉化為非約束的優化問題：

加和的第一項代表了hinge loss，第二項代表了正則項。primal QP problem較難求解，如果使用通用的QP解決方式則費時費力，我們可以將其轉化為dual problem，得到一個易于求解的形式：

而最終求解得到相應的參數后，排序函數可以表示為：

于是，RankSVM方法求解排序問題的步驟總結起來，如下圖所示：

?

2. IR SVM

2.1 loss function的改造

上面介紹的RankSVM的基本思想是，將排序問題轉化為pairwise的分類問題，然后使用SVM分類模型進行學習并求解。所以其在學習過程中，是使用了0-1分類損失函數（雖然實際上是用的替換損失函數hinge loss）。而這個損失函數的優化目標跟Information Retrieval的Evaluation常用指標（不僅要求各個doc之間的相對序關系正確，而且尤其重視Top的doc之間的序關系）還是存在gap的。所以有研究人員對此進行了研究，通過對RankSVM中的loss function進行改造從而使得優化目標更好地與Information Retrieval問題的常用評價指標相一致。

首先，我們通過一些例子來說明RankSVM在應用到文本排序的時候遇到的一些問題，如下圖所示。

第一個問題就是，直接使用RankSVM的話，會將不同相似度等級的doc同等看待，不會加以區分。這在具體的問題中又會有兩種形式：

1）Example 1中，3 vs 2 和 3 vs 1的兩個pair，在0-1 loss function中是同等看待的，即它們其中任一對的次序的顛倒對loss function的增加大小是一樣的。而這顯然是不合理的，因為3 vs 1的次序顛倒顯然要比 3 vs 2的次序的顛倒要更加嚴重，需要給予不同的權重來區分。

2）Example 2中，ranking-1是position 1 vs position 2的兩個doc的位置顛倒了，ranking-2是position 3 vs position 4的兩個doc的位置顛倒了，這兩種情況在0-1 loss function中也是同等看待的。這顯然也是不合理的，由于IR問題中對于Top doc尤其重視，ranking-1的問題要比ranking-2的問題更加嚴重，也是需要給予不同的權重加以區分。

第二個問題是，RankSVM對于不同query下的doc pair同等看待，不會加以區分。而不同query下的doc的數目是很不一樣的。如Example 3所示，query-4的doc書目要更多，所以在訓練過程中，query-4下的各個doc pair的訓練數據對于模型的影響顯然要比query-3下的各個doc pair的影響更大，所以最終結果的模型會有bias。

IR SVM針對以上兩個問題進行了解決，它使用了cost sensitive classification，而不是0-1 classification，即對通常的hinge loss進行了改造。具體來說，它對來自不同等級的doc pair，或者來自不同query的doc pair，賦予了不同的loss weight：

1）對于Top doc，即相似度等級較高的doc所在的pair，賦予較大的loss weight。

2）對于doc數目較少的query，對其下面的doc pair賦予較大的loss weight。

2.2 IR SVM的求解過程

IR SVM的優化問題可以表示如下：

其中，代表了隸屬于第k檔grade pair的instance的loss weight值。這個值的確定有一個經驗式的方法：對隸屬于這一檔grade pair的兩個doc，隨機交換它們的排序位置，看對于NDCG@1的減少值，將所有的減少值求平均就得到了這個loss weight。可以想象，這個loss weight值越大，說明這個pair的doc對于整體評價指標的影響較大，所以訓練時候的重要程度也相應較大，這種情況一般對應著Top doc，這樣做就是使得訓練結果尤其重視Top doc的排序位置問題。反之亦然。

而這個參數則對應了query的歸一化系數。可以表示為，即該query下的doc數目的倒數，這個很好理解，如果這個query下的doc數目較少，則RankSVM訓練過程中相對重視程度會較低，這時候通過增加這個權重參數，可以適當提高這個query下的doc pair的重要程度，使得模型訓練中能夠對不同的query下的doc pair重視程度相當。

IR SVM的優化問題如下：

同樣地，也需要將其轉化為dual problem進行求解：

而最終求解得到相應的參數后，排序函數可以表示為：

于是，IR SVM方法求解排序問題的步驟總結起來，如下圖所示：

?

?

版權聲明：

?? 本文由笨兔勿應所有，發布于http://www.cnblogs.com/bentuwuying。如果轉載，請注明出處，在未經作者同意下將本文用于商業用途，將追究其法律責任。

?

轉載于:https://www.cnblogs.com/bentuwuying/p/6683832.html

總結

以上是生活随笔為你收集整理的Learning to Rank算法介绍：RankSVM 和 IR SVM的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。