xgboost(三) -- 排序模型

RankNet

RankNet是一种pairwise的排序方法，它将排序问题转换为比较 $<d_{i},d_{j}>$ 对的排序概率问题，即比较 $d_{i}$ 排在 $d_{j}$ 前面的概率。RankNet提出了一种概率损失函数来学习排序模型，并通过排序模型对文档进行排序。这里的排序模型可以是任意对参数可微的模型，如增强树、神经网络等。

模型训练完毕后模型对每个样本给出一个预测值p，然后通过计算损失函数来对模型进行调整。RankNet中定义了两个概率来分别表示预测值和标签值，分别是预测相关性概率和真实相关性概率.
一般训练数据是按查询划分的，对每个查询内部数据进行排序，RankNet通过评分函数f（x）对输入的特征向量进行评分。对于给定的查询，选择具有不同标签的文档 $D_{i}$ 和 $D_{j}$ ，并将其特征向量 $x_{i}$ 和 $x_{j}$ 输入给模型，分别计算得分 $v_{i}=f(x_{i})$ 和 $v_{j}=f(x_{j})$ ，通过sigmoid函数将两得分映射为一个学习概率，即 $D_{i}$ 比 $D_{j}$ 更相关的预测概率为

p_{ij}=p(D_i<D_j)=\frac{1}{1+e^{-σ(v_i-v_j)}}

其中 $D_i<D_j$ 表示 $D_i$ 排在 $D_j$ 前面，参数σ确定sigmoid函数形状，由此便得到了预测相关性概率。
接下来看下真实相关性概率。
每个文档对中的文档 $D_{i}$ 和 $D_{j}$ 均包含一个表征与该查询相关性的标签，如 $D_{i}$ 关于该查询的标签为非常相关， $D_{j}$ 为不相关，很明显 $D_{i}$ 比 $D_{j}$ 更相关。因此，真实相关性概率定义为

\vec{p_{ij}}=\frac{1}{2}(1+V_{ij})

如果 $D_{i}$ 比 $D_{j}$ 更相关，则 $V_{ij}=1$ ；如果 $D_{j}$ 比 $D_{i}$ 更相关，则 $V_{ij}=-1$ ；若其标签值相等，则 $V_{ij}=0$ 。
像其他pairwise方法一样，RankNet会评估所有文档对的相对关系，以错误的文档对最少作为优化目标。RankNet引入了概率的思想，优化目标转换为预测相关性概率与真实相关性概率的差距最小。RankNet采用交叉熵作为损失函数，公式如下：

loss=\vec{-p_{ij}} \log^{p_{ij}}-(1-\vec{p_{ij}})\log^{(1-p_{ij})}

将预测相关性概率公式和真实相关性概率公式代入损失函数，则有

loss=\frac{1}{2}(1-V_{ij})σ(v_{i}-v_{j})+\log(1+e^{-σ(v_i-v_j)})

当 $V_{ij}=1$ 的时候，

loss=\log(1+e^{-σ(v_i-v_j)})

当 $V_{ij}=-1$ 的时候，

loss=\log(1+e^{-σ(v_j-v_i)})

当 $V_{ij}=0$ 的时候，

loss=log2

由此可以看出，两个排序不同的文档即使评估分值相同，损失函数也会对其进行惩罚。并且如果分数与实际排名不符，则损失函数为类线性函数；如果相符，则损失函数为0。对 $v_{i}$ 和 $v_{j}$ 分别求导：

\frac{\partial{loss}}{\partial{v_{i}}}= -\frac{\partial{loss}}{\partial{v_{j}}}

以上梯度可以用于更新模型参数.

LambdaRank

RankNet主要针对文档对相对顺序关系的错误数量进行优化，而并不区分不同文档在优化时的权重。在重点关注头部排序的场景下，效果并不理想，如以NDCG作为评估指标，此时模型拟合应更关注于排序靠前的文档，但RankNet的优化目标与实际的优化目标是有偏差的，因此不能取得很好的效果，RankNet没办法以NDCG这些指标作为优化目标进行迭代。以图1为例，其表示一个给定查询的二分类有序文档集，圆形表示与查询相关的文档，正方形表示与查询不相关的文档。
对于RankNet而言，其损失函数cost通过文档对的错误数量来衡量。在图1-a中，cost为6（通过排序错误对数量计算得到）；在图1-b（经过一轮优化后）中，将排序最靠前的相关文档下调2个位置，将底部的相关文档上调3个位置，此时cost为5。但是对于像NDCG等更注重头部排序的指标，这并不是其想要的结果。图1-b中的左边箭头代表RankNet的梯度方向和幅度，右边箭头代表真正需要的梯度方向和幅度，即更关注靠前位置的文档的提升。