RankNet与LambdaRank

Clay*more 2021-11-10

展开全文

在使用搜索引擎的过程中，对于某一Query(或关键字)，搜索引擎会找出许多与Query相关的URL，然后根据每个URL的特征向量对该URL与主题的相关性进行打分并决定最终URL的排序，其流程如下：

这里写图片描述

排序的好坏完全取决于模型的输出，而模型又由其参数决定，因而问题转换成了如何利用带label的训练数据去获得最优的模型参数w。Ranknet提供了一种基于Pairwise的训练方法，它最早由微软研究院的Chris Burges等人在2005年ICML上的一篇论文Learning to Rank Using Gradient Descent中提出，并被应用在微软的搜索引擎Bing当中。

代价函数

对于一个排序，RankNet从各个URL的相对关系来评价排序结果的好坏，排序的效果越好，那么有错误相对关系的pair就越少。所谓错误的相对关系即如果根据模型输出 $U_{i}$ 排在 $U_{j}$ 前面，但真实label为 $U_{i}$ 的相关性小于 $U_{j}$ ，那么就记一个错误pair，RankNet就是以错误的pair最少为优化目标。对于每一个pair，我们使用交叉熵来度量其预测代价，即：

C_{i j} = - {\bar{P}}_{i j} l o g P_{i j} - (1 - {\bar{P}}_{i j}) l o g (1 - P_{i j})

化简

\begin{aligned} C_{i j} & = - \frac{1}{2} (1 + S_{i j}) l o g \frac{1}{1 + e^{- σ (s_{i} - s_{j})}} - \frac{1}{2} (1 - S_{i j}) l o g \frac{e^{- σ (s_{i} - s_{j})}}{1 + e^{- σ (s_{i} - s_{j})}} \\ = - \frac{1}{2} (1 + S_{i j}) l o g \frac{1}{1 + e^{- σ (s_{i} - s_{j})}} - \frac{1}{2} (1 - S_{i j}) [- σ (s_{i} - s_{j}) + l o g \frac{1}{1 + e^{- σ (s_{i} - s_{j})}}] \\ = \frac{1}{2} (1 - S_{i j}) σ (s_{i} - s_{j}) + l o g (1 + e^{- σ (s_{i} - s_{j})}) \end{aligned}

下图展示了 $C_{i j}$ 随 ${\bar{P}}_{i j}$ 、 $P_{i j}$ 的变化情况：
这里写图片描述

图中t表示 $s_{i} - s_{j}$ ，可以看到当 $S_{i j} = 1$ 时，模型预测的 $s_{i}$ 比 $s_{j}$ 越大，其代价越小； $S_{i j} = - 1$ 时， $s_{i}$ 比 $s_{j}$ 越小，代价越小； $S_{i j} = 0$ 时，代价的最小值在 $s_{i}$ 与 $s_{j}$ 相等处取得。该代价函数有以下特点：

当两个相关性不同的文档算出来的模型分数相同时，损失函数的值大于0，仍会对这对pair做惩罚，使他们的排序位置区分开
损失函数是一个类线性函数，可以有效减少异常样本数据对模型的影响，因此具有鲁棒性

总代价

C = \sum_{(i, j) \in I} C_{i j}

I表示所有URL pari的集合，且每个pair仅包含一次。

梯度下降迭代

我们获得了一个可微的代价函数，下面我们就可以用梯度下降法来迭代更新模型参数 $w_{k}$ 了，即

w_{k} \to w_{k} - η \frac{\partial C}{\partial w_{k}}

$η$ 为步长，代价 $C$ 沿负梯度方向变化：

Δ C = \sum_{k} \frac{\partial C}{\partial w_{k}} Δ w_{k} = \sum_{k} \frac{\partial C}{\partial w_{k}} (η \frac{\partial C}{\partial w_{k}}) = - η \sum_{k} (\frac{\partial C}{\partial w_{k}})^{2} < 0

这表明沿负梯度方向更新参数确实可以降低总代价。我们对 $\frac{\partial C}{\partial w_{k}}$ 继续分解

\frac{\partial C}{\partial w_{k}} = \sum_{(i, j) \in I} (\frac{\partial C_{i j}}{\partial s_{i}} \frac{\partial s_{i}}{\partial w_{k}} + \frac{\partial C_{i j}}{\partial s_{j}} \frac{\partial s_{j}}{\partial w_{k}})

其中

\frac{\partial C_{i j}}{\partial s_{i}} = σ (\frac{1}{2} (1 - S_{i j}) - \frac{1}{1 + e^{σ (s_{i} - s_{j})}}) = - \frac{\partial C_{i j}}{\partial s_{j}}

我们令 $λ_{i j} = \frac{\partial C_{i j}}{\partial s_{i}} = σ (\frac{1}{2} (1 - S_{i j}) - \frac{1}{1 + e^{σ (s_{i} - s_{j})}})$ ，有

\begin{aligned} \frac{\partial C}{\partial w_{k}} & = \sum_{(i, j) \in I} σ (\frac{1}{2} (1 - S_{i j}) - \frac{1}{1 + e^{σ (s_{i} - s_{j})}}) (\frac{\partial s_{i}}{\partial w_{k}} - \frac{\partial s_{j}}{\partial w_{k}}) \\ = \sum_{(i, j) \in I} λ_{i j} (\frac{\partial s_{i}}{\partial w_{k}} - \frac{\partial s_{j}}{\partial w_{k}}) \\ = \sum_{i} λ_{i} \frac{\partial s_{i}}{\partial w_{k}} \end{aligned}

下面我们来看看这个 $λ_{i}$ 是什么。前面讲过集合I中只包含label不同的URL的集合，且每个pair仅包含一次，即( $U_{i}$ , $U_{j}$ )与( $U_{j}$ , $U_{i}$ )等价。为方便起见，我们假设I中只包含( $U_{i}$ , $U_{j}$ )表示 $U_{i}$ 相关性大于 $U_{j}$ 的pair，即I中的pair均满足 $S_{i j} = 1$ ，那么

λ_{i} = \sum_{j : (i, j) \in I} λ_{i j} - \sum_{j : (j, i) \in I} λ_{i j}

这个写法是Burges的paper上的写法，我对此好久都没有理清，下面我们用一个实际的例子来看：有三个URL，其真实相关性满足 $U_{1} > U_{2} > U_{3} ，那么集合 I 中就包含$ {(1,2), (1,3), (2,3)}共三个pair

\frac{\partial C}{\partial w_{k}} = (λ_{12} \frac{\partial s_{1}}{\partial w_{k}} - λ_{12} \frac{\partial s_{2}}{\partial w_{k}}) + (λ_{13} \frac{\partial s_{1}}{\partial w_{k}} - λ_{13} \frac{\partial s_{3}}{\partial w_{k}}) + (λ_{23} \frac{\partial s_{2}}{\partial w_{k}} - λ_{23} \frac{\partial s_{3}}{\partial w_{k}})

显然 $λ_{1} = λ_{12} + λ_{13} ， λ_{2} = λ_{23} - λ_{12} ， λ_{3} = - λ_{13} - λ_{23}$ ，因此我所理解的 $λ_{i}$ 应为

λ_{i} = \sum_{j : (i, j) \in I} λ_{i j} - \sum_{k : (k, i) \in I} λ_{k i}

λ_{i}

决定着第i个URL在迭代中的移动方向和幅度，真实的排在

U_{i}

前面的URL越少，排在

U_{i}

后面的URL越多，那么文档

U_{i}

向前移动的幅度就越大(实际

λ_{i}

负的越多越向前移动)。这表明每个URL下次调序的方向和强度取决于所有同一Query的其他不同label的文档。

LambdaRank

上面我们介绍了以错误pair最少为优化目标的RankNet算法，然而许多时候仅以错误pair数来评价排序的好坏是不够的，像NDCG或者ERR等评价指标就只关注top k个结果的排序，当我们采用RankNet算法时，往往无法以这些指标为优化目标进行迭代，以下图为例：

这里写图片描述

图中每个线条表示一个URL，蓝色表示与Query相关的URL，灰色表示不相关的URL。下面我们用Error pair和NDCG分别来评估左右两个排序的好坏：

Error pair指标

对于排序1，排序错误的pair共13对，故 $c o s t = 13$ ，分别为：
(2,15)、(3,15)、(4,15)、(5,15)、(6,15)、(7,15)、(8,15)、
(9,15)、(10,15)、(11,15)、(12,15)、(13,15)、(14,15)

对于排序2，排序错误的pair共11对，故 $c o s t = 11$ ，分别为：
(1,4)、(2,4)、(3,4)
(1,10)、(2,10)、(3,10)、(5,10)、(6,10)、(7,10)、(8,10)、(9,10)

所以，从Error pair角度考虑，排序2要优于排序1
NDCG指标

排序1与排序2具有相同的 $m a x D C G @ 16$ ,

$m a x D C G @ 16 = \frac{2^{1} - 1}{l o g (1 + 1)} + \frac{2^{1} - 1}{l o g (1 + 2)} = 1.63$

对排序1，有

$D C G @ 16 = \frac{2^{1} - 1}{l o g (1 + 1)} + \frac{2^{1} - 1}{l o g (1 + 15)} = 1.25$

$N D C G @ 16 = \frac{D C G @ 16}{m a x D C G @ 16} = \frac{1.25}{1.63} = 0.767$

对排序2，有

$D C G @ 16 = \frac{2^{1} - 1}{l o g (1 + 4)} + \frac{2^{1} - 1}{l o g (1 + 10)} = 0.72$

$N D C G @ 16 = \frac{D C G @ 16}{m a x D C G @ 16} = \frac{0.72}{1.63} = 0.442$

所以，从NDCG指标来看，排序1要优于排序2。