【模式識别】Learning To Rank之RankBoost

RankBoost的思想比較簡單，是二進制Learning to rank的正常思路：通過構造目标分類器，使得pair之間的對象存在相對大小關系。通俗點說，把對象組成一對對的pair，比方一組排序r1>r2>r3>r4，那能夠構成pair：(r1,r2)(r1,r3),(r1,r4),(r2,r3)(r3,r4),這種pair是正值，也就是label是1。而餘下的pair如(r2,r1)的值應該是-1或0。這樣一個排序問題就被巧妙的轉換為了分類問題。近來CV界許多又用這種learning to rank的思想做識别問題（最早應該是這篇《​​Person Re-Identification by Support Vector Ranking​​》），也就是把識别轉換為排序問題再轉換為分類問題。

Pairwise的排序方法主要用RankSVM和RankBoost，這裡主要說RankBoost，總體還是一個Boost的架構：

注意其與正常Boost的不同組要是Update的時候。當然資料分布也不同。這裡能夠看出對于終于的排序值。也就是ranking score。其值是沒有實際意義的，相對的順序才有意義。比方r1和r2終于得分是10分和1分。與r1,r2終于得分是100分和1分的資訊量差別并不大，我們能得到的結論都是r1應該排在r2前面。

因為和傳統的Boost目标不一樣。求解也須要很巧妙的方法，主要在于定義分類器的Loss函數：

詳細的，因為

以及

我們能夠得到分布D的損失：

于是，目标就變成了最小化

至此，傳統的Boost線性搜尋政策已經能夠求解，但還有更巧妙的辦法。因為函數：

于是，對于是以[-1 1]範圍内的x。Z能夠近似為：

當中

。這樣直接能夠Z最小時

。此時。

于是被轉換為最大化|r|的問題。

下面是一段RankBoost的代碼：

function [ rbf ] = RankBoost( X,Y,D,T )
%RankBoost implemetation of RankBoost algoritm
%   Input:
%       X - train set.
%       Y - train labels.
%       D - distribution function over X times X, it the form of 2D matrix.
%       T - number of iteration of the boosting.
%   Output:
%       rbf - Ranking Function.

rbf = RankBoostFunc(T);
% w - the current distribution in any iteration, initilize to D
w = D;
for t=1:T
    tic;
    fprintf('RankBoost: creating the function, iteration %d out of %d\n',t,T);
    WL = getBestWeakLearner(X,Y,w);
    rbf.addWeakLearner(WL,t);
    rbf.addAlpha(WL.alpha,t);
    alpha=WL.alpha;

    %update the distribution
    %eval the weak learnler on the set of X and Y
    h=WL.eval(X);
    [hlen, ~] = size(h);
    tmph = (repmat(h,1,hlen) - repmat(h',hlen,1));
    w=w.*exp(tmph.*alpha);
    %normalize w
    w = w./sum(w(:));
    toc;
end
end      

一個比較明顯的問題是RankBoost須要維持一個很大的|X|*|X|的矩陣。程式執行十分占記憶體，常常抛出“Out of memory”的錯誤。

是以諸如

tmph = (repmat(h,1,hlen) - repmat(h',hlen,1));      

之類的操作不如換成例如以下方式：

% tmph = (repmat(h,1,hlen) - repmat(h',hlen,1));
    %w=w.*exp(tmph.*alpha);
    [rows, cols] = size(w);
    sumw = 0;
    for r=1:rows
        for c=1:cols
            w(r,c) = w(r,c)*exp((h(r)-h(c))*alpha);
            sumw = sumw + w(r,c);
        end
    end

    %normalize w
    %w = w./sum(w(:));
    w = w./sumw;