2021-09-27 1d21af6ac09030b0fa57649eb89cea30 99+ 6 m 0.9 k

From RankNet to LambdaRank to LambdaMART

1.RankNet

RankNet采用pairwise的方法进行模型训练。

loss推导

给定特定$query$下的两个文档$U_i$和$U_j$，其特征向量分别为$x_i$和$x_j$，经过RankNet进行前向计算得到对应的分数为$s_i=f(x_i)$和$s_j=f(x_j)$。用$U_i \rhd U_j$表示$U_i$比$U_j$排序更靠前。继而可以用下面的公式来表示$U_i$应该比$U_j$排序更靠前的概率：

$P_{ij} \equiv P(U_i \rhd U_j) \equiv \frac{1}{1+e^{-\sigma(s_i-s_j)}}$

定义$S_{ij} \in \{0,\pm1\}$为文档$i$和文档$j$被标记的标签之间的关联，即

$S_{ij}=\left\{ \begin{aligned} 1&& 文档i比文档j更相关\\ 0&& 文档i和文档j相关性一致\\ -1&& 文档j比文档i更相关 \end{aligned} \right.$

定义$\overline{P}_{ij}=\frac{1}{2}(1+S_{ij})$表示$U_i$应该比$U_j$排序更靠前的已知概率，则可以用交叉熵定义优化目标的损失函数：

$\begin{align*} C&=-\overline{P}_{ij}log{P_{ij}}-(1-\overline{P}_{ij})log(1-P_{ij}) \\&=\frac{1}{2}(1-S_{ij})\sigma(s_i-s_j)+log(1+e^{-\sigma(s_i-s_j)}) \end{align*}$

注意：$\sigma$是超参数

ranknet 加速

2.LambdaRank

ranket缺陷为只考虑pair的相对位置没有考虑二者在列表的整体位置

LambdaRank本质为ranknet基础上加入Listwise的指标，因此有人将LambdaRank归为listwise方法，也有归到pairwise方法

2.1 RankNet的局限

2.2 LambdaRank定义

$\begin{align*} \frac{\partial{C}}{\partial{w_k}}&=\frac{\partial{C}}{\partial{s_i}}\frac{\partial{s_i}}{\partial{w_k}}+\frac{\partial{C}}{\partial{s_j}}\frac{\partial{s_j}}{\partial{w_k}} \\&=\sigma\left(\frac{1}{2}(1-S_{ij})-\frac{1}{1+e^{\sigma(s_i-s_j)}}\right)\left(\frac{\partial{s_i}}{\partial{w_k}}-\frac{\partial{s_j}}{\partial{w_k}}\right) \\&=\lambda_{ij}\left(\frac{\partial{s_i}}{\partial{w_k}}-\frac{\partial{s_j}}{\partial{w_k}}\right) \end{align*} \\其中\lambda_{ij}=\frac{\partial{C}}{\partial{s_i}}=-\frac{\partial{C}}{\partial{s_j}}=\sigma\left(\frac{1}{2}(1-S_{ij})-\frac{1}{1+e^{\sigma(s_i-s_j)}}\right)$

上述公式可以进一步简化，即只考虑$S_{ij}=1$ （为什么可以？？？？？）

那么Lambda，$\lambda$，就是梯度

$\lambda_{ij}=\frac{-\sigma}{1+e^{\sigma(s_i-s_j)}}$

为了加强排序中前后顺序的重要性，Lambda在原基础上引入评价指标Z（如NDCG），把交换两个文档的位置引起的评价指标的变化$|\Delta Z_{ij}|$作为其中一个因子：

$\lambda_{ij}=\frac{\partial{C}}{\partial{s_i}}=\frac{-\sigma}{1+e^{\sigma(s_i-s_j)}}|\Delta Z_{ij}|$

反推出 LambdaRank 的损失函数：

$C=log(1+e^{\sigma (s_i-s_j)})|\Delta Z_{ij}|$

3.LambdaMART

属于listwise，也有说pairwise。

LambdaMART=lambda($\lambda$)+mart(gbdt)

$\lambda$就是梯度，lambdarank就是一种loss，gbdt就是模型

lambdamart说白了就是利用gbdt计算lambdarank中s，或者说将lambdarank作为gbdt的loss

gbdt，lambdamart算法流程差异在于step1

GBDT：

初始化： $f_0(x) = \mathop{\arg\min}\limits_\gamma \sum\limits_{i=1}^N L(y_i, \gamma)$
for m=1 to M:
(a). 计算负梯度： $\tilde{y}_i = -\frac{\partial L(y_i,f_{m-1}(x_i))}{\partial f_{m-1}(x_i)}, \qquad i = 1,2 \cdots N$
(b). $\left \{ R_{jm} \right\}_1^J = \mathop{\arg\min}\limits_{\left \{ R_{jm} \right\}_1^J}\sum\limits_{i=1}^N \left [\tilde{y}_i - h_m(x_i\,;\,\left \{R_{jm},b_{jm} \right\}_1^J) \right]^2$
(c). $\gamma_{jm} = \mathop{\arg\min}\limits_\gamma \sum\limits_{x_i \in R_{jm}}L(y_i,f_{m-1}(x_i)+\gamma)$
(d). $f_m(x) = f_{m-1}(x) + \sum\limits_{j=1}^J \gamma_{jm}I(x \in R_{jm})$
输出$f_M(x)$

LambdaMART: