YeeKal
recsys

lambdamart 排序算法

YeeKal • •
"#recsys"

RankNet

模型就是一个函数，把特征映射为一个得分：$\hat{y}=f(x)$. 而在排序任务上，各个排序模型的设计要点是怎么把模型得分与排序关联到一起来构造损失函数。

RankNet通过比较两个文档对($U_i,U_j$)之间的得分，并通过sigmoid函数把得分映射到[0,1]来表示哪个文档更应该排在前面。并把这一关系式称为$U_i$比$U_j$更相关的概率预测值, 其中$s_i,s_j$为模型的预测得分：

真实的相关性概率定义为:

$$$$

这样就可以利用交叉熵衡量预测概率与实际概率的差异：

损失函数的梯度：

这样可以通过两辆比较得出整个排序列表，这种方法也叫做pair-wise损失。

LambdaRank

RankNet关注的是逆序对的减少，而没有对头部排序有偏向性。基于此LambdaRank在RankNet损失函数梯度的基础上增加了对头部排序的偏向因子。即把交换两个文档引起的$|\Delta NDCG|$的变化作为其中的一个因子。加入该因子的含义是，排序靠前的文档错位比排序靠后的文档错位更加重要。

$$\lambda_{i j}=\frac{\partial C\left(s_{i}-s_{j}\right)}{\partial s_{i}}=\frac{-\sigma}{1+e^{\sigma\left(s_{i}-s_{j}\right)}}\left|\Delta_{N D C G}\right| \ \text{这里只考虑$S_{ij}=1$的情况，故省略}$$

这里的损失函数梯度考虑了整个文档序的情况，故也被称为是list-wise的方法。另外该定义是直接在梯度上增加因子，而没有考虑原损失函数的具体形式，这样就把离散的NDCG评价指标纳入了损失函数。

该梯度也被称为lambda梯度(只是因为以lambda标识？)。

LambdaMart

LambdaMart把lambda梯度和树模型结合在一起，是最为流行的LTR方法。

lambda梯度的计算：对于当前排序下的文档$U_i$,计算关于文档$U_i$的所有文档对的lambda梯度：

再计算二次梯度导数：

计算第m棵树的第k个叶子节点上的值:

根据下图的步骤，由于这里使用的损失函数交叉熵，并没有直接使用负梯度进行优化，而是采用通用的用近似值代替的方法。事实上在xgboost损失函数中通过二阶泰勒展开，就可以得到没有正则项的同样的公式。

lambdamart.png

从广义上讲，lambda损失只是一种损失函数的形式，而得分$s_i$可以采用任何一种机器学习/深度学习的方法来做。因此可以说对于排序任务，如何定义损失函数是其精髓所在;另一方面，在ltr领域，把深度学习纳入进得分函数，便可以通过损失函数的设计，通过深度学习来处理排序任务。

RankLib

# lambdamart实现参考： https://github.com/lezzago/LambdaMart/blob/master/lambdamart.py

# dcg 计算 参考
def dcg(scores):
    """
        Returns the DCG value of the list of scores.
        Parameters
        ----------
        scores : list
            Contains labels in a certain ranked order

        Returns
        -------
        DCG_val: int
            This is the value of the DCG on the given scores
    """
    return np.sum([
                        (np.power(2, scores[i]) - 1) / np.log2(i + 2)
                        for i in xrange(len(scores))
                    ])

def ideal_dcg(scores):
    """
        Returns the Ideal DCG value of the list of scores.
        Parameters
        ----------
        scores : list
            Contains labels in a certain ranked order

        Returns
        -------
        Ideal_DCG_val: int
            This is the value of the Ideal DCG on the given scores
    """
    scores = [score for score in sorted(scores)[::-1]]
    return dcg(scores)

def ideal_dcg_k(scores, k):
    """
        Returns the Ideal DCG value of the list of scores and truncates to k values.
        Parameters
        ----------
        scores : list
            Contains labels in a certain ranked order
        k : int
            In the amount of values you want to only look at for computing DCG

        Returns
        -------
        Ideal_DCG_val: int
            This is the value of the Ideal DCG on the given scores
    """
    scores = [score for score in sorted(scores)[::-1]]
    return dcg_k(scores, k)

def single_dcg(scores, i, j):
    """
        Returns the DCG value at a single point.
        Parameters
        ----------
        scores : list
            Contains labels in a certain ranked order
        i : int
            This points to the ith value in scores
        j : int
            This sets the ith value in scores to be the jth rank

        Returns
        -------
        Single_DCG: int
            This is the value of the DCG at a single point
    """
    return (np.power(2, scores[i]) - 1) / np.log2(j + 2)

#  lambda梯度计算参考

z_ndcg = abs(single_dcgs[(i,j)] - single_dcgs[(i,i)] + single_dcgs[(j,i)] - single_dcgs[(j,j)]) / idcg
rho = 1 / (1 + np.exp(predicted_scores[i] - predicted_scores[j]))
rho_complement = 1.0 - rho
lambda_val = z_ndcg * rho
lambdas[i] += lambda_val
lambdas[j] -= lambda_val

w_val = rho * rho_complement * z_ndcg
w[i] += w_val
w[j] += w_val

// RankLib中LambdaMart计算梯度方式
protected void computePseudoResponses(int start, int end, int current)
    {
        ...
        //compute the lambda for each document (a.k.a "pseudo response")
        double deltaNDCG = Math.abs(changes[j][k]);
        if(deltaNDCG > 0)
        {
            double rho = 1.0 / (1 + Math.exp(modelScores[mj] - modelScores[mk]));
            double lambda = rho * deltaNDCG;
            pseudoResponses[mj] += lambda;
            pseudoResponses[mk] -= lambda;
            double delta = rho * (1.0 - rho) * deltaNDCG;
            weights[mj] += delta;
            weights[mk] += delta;
        }
        ...

    }

ref

← Back to recsys