RankNet
rankNet 是一种pair wise的LTR算法。该算法将排序问题转化为一对doc 谁排在前面的二分类问题。顾名思义，样本是一个doc 对，记做(i,j)。i排在前面，则label为1， 排在后面， label为0。如果二者和query的相关程度相同，那么label为0.5。
label 定义如下:
\[\overline p_{ij} = \frac{1}{2} (1+S_{ij})\]当i排在j前面时，\(s_{ij}\)为1，排在j后面时\(s_{ij}\)为-1；相关性相同时\(s_{ij}\)为0。
说完了label，下面说下预估值。 预估值就是预估i排在j前面的概率,记为\(p_{ij}\),这是通过sigmoid函数实现的。而sigmoid 作用的对象就是i和j的得分差\(s_i-s_j\)。这两个得分都是通过神经网络得来的，这也是rankNet中Net的含义。
\[p_{ij}=\frac{1}{1+e^{-\sigma(s_i-s_j)}}\]\(\sigma\)是一个标量参数，不是sigmoid函数，决定了sigmoid函数的形状。
对于一个样本对i,j来说，(i,j)和（j,i)是等价的，因为i排在j前面为真也就是j排在i前面为假,所以我们只需要考虑i排在j前面的情况,即所有样本的\(s_{ij}=1\)
有了pair的label和预估值，我们就可以定义损失函数了。RankNet的损失函数是交叉熵损失。
\[C=-\overline p_{ij}log p_{ij} - (1-\overline p_{ij})log(1-p_{ij})\]2022.03.27 补充:
也有地方把这个损失函数叫做bpr损失，其实就是pair-wise排序方法下，将pair中的正负样本得分差通过sigmoid转化为正样本排在负样本前面的概率，然后再套用交叉熵损失函数，就得到了bpr损失。
这个损失函数可以经过一系列推导，得到下面的形式。
\[C=-\overline p_{ij}log p_{ij} - (1-\overline p_{ij})log(1-p_{ij}) \\ = -\frac{1}{2} (1+S_{ij})log( \frac{1}{1+e^{-\sigma(s_i-s_j)}} )-\frac{1}{2} (1-S_{ij})log \frac{e^{-\sigma(s_i-s_j)}} {1+e^{-\sigma(s_i-s_j)}} \\ = \frac{1}{2} (1+S_{ij})log( 1+e^{-\sigma(s_i-s_j)} )-\frac{1}{2} (1-S_{ij}) (-\sigma(s_i-s_j) - log(1+e^{-\sigma(s_i-s_j)} ) ) \\ = \frac{1}{2} (1-S_{ij}) \sigma(s_i-s_j) + log( 1+e^{-\sigma(s_i-s_j)} )\]对参数求导：
\[\frac{\partial C}{\partial w_k}= \sum_{ij} \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}\\\] \[\frac{\partial C}{\partial s_i} = \frac{1}{2} (1-S_{ij})\sigma + \frac {1} {1+e^{-\sigma(s_i-s_j)} } e^{-\sigma(s_i-s_j)}(-\sigma)\\ =\sigma( \frac{1}{2} (1-S_{ij}) - \frac{1}{ 1+e^{\sigma(s_i-s_j)} }) \\\] \[\frac{\partial C}{\partial s_j} = \frac{1}{2} (1-S_{ij})(-\sigma) + \frac {1} {1+e^{-\sigma(s_i-s_j)} } e^{-\sigma(s_i-s_j)}(\sigma)\\ =(-\sigma)（\frac{1}{2} (1-S_{ij})-\frac{1}{ 1+e^{\sigma(s_i-s_j)} } ）\\\]由于所有的样本i都是排在j前面的，所以 \(s_{ij}=1\),那么
\[\frac{\partial C}{\partial s_i}=-\sigma( \frac{1}{ 1+e^{\sigma(s_i-s_j)} })\]可以看出：
\[\frac{\partial C}{\partial s_i}=-\frac{\partial C}{\partial s_j}\]记：
\[\lambda_{ij} = \frac{\partial C}{\partial s_i}\\\] \[\frac{\partial C}{\partial w_k}=\sum_{ij} \lambda_{ij} (\frac{\partial s_i}{\partial w_k} -\frac{\partial s_j}{\partial w_k})\\=\sum_{i} \lambda_{i}\frac{\partial s_i}{\partial w_k}\]其中：
\[\lambda_{i}= \sum_{j:(i,j)\in I} \lambda_{ij} - \sum_{j:(j,i)\in I} \lambda_{ij}\]最后一个等式可以用来加速RankNet。原始的RankNet是pair-wise维度的，即每个pair 更新一次参数，这样速度会很慢。但是最后一个等式将RankNet 转换为样本point-wise维度的，这样就可以进行批量更新了。 时间复杂度从\(O(n^2)\)下降到\(O(n)\)，n是query下的文档数量。
\(\lambda_i\)的物理意义:可以理解为表示文档i在query下移动的方向和力度。
即:每条文档移动的方向和趋势取决于其他包含该文档的pair对中的其他文档。
LambdaRank
RankNet优化的目标其实是减少排序错误的pair对(其实就是在优化AUC）。但是，排序更多时候更关注头部的排序是否正确。LambdaRank算法解决该问题的方式是在RankNet的梯度基础上考虑排序指标的变化。这样可以避免引入某些不连续的评价指标时梯度不好求解的问题。
\[\frac{\partial C}{\partial s_i}=-\sigma( \frac{1}{ 1+e^{\sigma(s_i-s_j)} })|\Delta NDCG|\]\(\\|\)\(\Delta NDCG\)\(\\|\) 表示交换i，j（其他顺序保持不变）之后NDCG的变化量。有研究表明，这种做法其实就是在直接优化NDCG。
NDCG也可以换做其他排序指标。
排序中常见的指标有MRR、MAP、ERR、NDCG，但是这几个指标对于模型得分来说都是不连续的，所以不方便直接使用梯度下降进行优化。
比如DCG (Discounted Cumulative Gain) 的定义如下：
对于一个query的搜索结果，
\(DCG@T=\sum_{i=1}^T \frac{2^{l_i}-1}{log(1+i)}\) T表示我们只关心top的前T个结果。\(l_i\)是第i个结果的label。一般取{0,1,2,3,4}五个相关性级别。
\[NDCG@T=\frac{DCG@T}{maxDCG@T}\]LambdaMart
LambdaMart将MART和LambdaRank.结合在一起。
MART的基础模型是评分损失的回归树。整个模型是多个回归树的线性组合。在每一步生成新的回归树时，MART的做法时去拟合损失函数关于每个样本的梯度。
以二分类时的MART 为例：
假设label为+1，-1。样本得分为F(x), 即label为+1的概率为 \(P_{+}=P(y = 1|x)\),label为-1的概率为\(P_{-}=P(y = -1|x)\)。 指示函数\(I_{+}(xi)\) 表示label是否为1， 为1时该函数为1，否则为0。\(I_{-}(xi)\) 表示label是否为-1， 为-1时该函数为1，否则为0。
使用交叉损失函数时，损失为:
\[L(y,F) = −I_{+} logP_{+}−I_{−} logP_{−}\]由于Logistic regression 建模的是 log odds（即label为1的概率除以label为-1的概率的对数）。 所以有如下等式：
\[F_N(x) =\frac{1}{2}log(\frac{P_{+}}{P_{−}})\]或者说：
\[P_{+} = \frac{1}{1+e^{-2\sigma F_N(x)}} \\ P_{-} = \frac{1}{1+e^{2\sigma F_N(x)}}\] \[\frac{1}{2}log(\frac{P_{+}}{P_{−}})\\ =\frac{1}{2} log ( \frac{ \frac{e^{2\sigma F_N(x)} } {1+e^{2\sigma F_N(x)} } } {\frac{1}{1+e^{2\sigma F_N(x)}} } )\\ =\frac{1}{2} log (e^{2\sigma F_N(x)} ) \\ =\sigma F_N(x)\]损失函数如下：
\[L(y,F_N) = log(1+e^{−2y\sigma F_N} )\]当y=1时
\[L(y,F_N) = log(1+e^{−2*1 \frac{1}{2} log \frac{P_{+}}{P_{−}} } ) \\ =log(1+e^{ - log \frac{P_{+}}{P_{−}} })\\ =log(1+ \frac{P_{-}}{P_{+}} )\\ =log( \frac{1}{P_{+}}) \\ =-log(P_{+})\]当y=-1时
\[L(y,F_N) = log(1+e^{−2*-1 \frac{1}{2} log \frac{P_{+}}{P_{−}} } ) \\ =log(1+e^{ log \frac{P_{+}}{P_{−}} })\\ =log(1+ \frac{P_{+}}{P_{-}} )\\ =log( \frac{1}{P_{-}}) \\ =-log(P_{-})\]梯度为
\[\overline y_i = -[ \frac{\partial L(y_i, F(x_i))} {\partial F(x_i)} ]_{F(x)=F_{m-1} (x)}\\ =\frac{2y_i\sigma}{1+e^{2y_i\sigma F_{m-1}(x)}}\]这个就是LambdaRank中的\(\lambda\)梯度,也是回归树要建模的label。
假设落在第m颗树的第j个叶子节点的样本集合为\(R_{jm}\)。我们需要求得使得损失最小化的叶子节点的值。
\[R_{jm}= arg min \sum_{ x_i \in R_{jm} } log (1+e^{−2y_i\sigma (F_{m-1}\ (x_i)+\lambda}) ) \\ =arg\ min\ g(\lambda)\]我们可以使用牛顿法来求\(\lambda\)。
对函数 \(g(\lambda)\)，牛顿法更新的规则如下；
\[\lambda_{n+1}=\lambda_{n}-\frac{g^{'}(\lambda_n) }{g^{''}(\lambda_n)}\]记
\[S_i(\lambda)=1+e^{-2v_i}=1+e^{−2y_i\sigma (F_{m-1}\ (x_i)+\lambda)}\] \[arg\ min\ g(\lambda)= arg\ min\ \sum_{ x_i \in R_{jm} } log S_i(\lambda)\]对\(\lambda\)求解一阶梯度和二阶梯度
\[g' = \sum_{ x_i \in R_{jm} } \frac{1}{S_i(\lambda)}(e^{-2v_i}*(-2y_i\sigma))\] \[g'' = \sum_{ x_i \in R_{jm} } \frac{-1}{S_i^2} (e^{-2v_i}*(-2y_i\sigma))^2 - \frac{2y_i\sigma}{S_i}(-2y_i\sigma)e^{-2vi}\\ =\sum_{ x_i \in R_{jm} } \frac{4}{S_i^2} y_i^2 \sigma^2 e^{-2v_i}\] \[\overline y_i = \frac{2y_i\sigma}{1+e^{2y_i\sigma F_{m-1}(x)}}\\ => g'= \sum_{ x_i \in R_{jm} } \frac{1}{S_i(\lambda)}(e^{-2v_i}*(-2y_i\sigma))\\ =\sum_{ x_i \in R_{jm} } \frac{-2y_i\sigma }{ S_i e^{2v_i}} \\ =\sum_{ x_i \in R_{jm} } \frac{-2y_i\sigma } { 1+ e^{2*y_i\sigma (F_{m-1}\ (x_i)+\lambda)} }\\ =\sum_{ x_i \in R_{jm} } -\overline y_i\] \[g'' =\sum_{ x_i \in R_{jm} } \frac{4}{S_i^2} y_i^2 \sigma^2 e^{-2v_i}\\ =\sum_{ x_i \in R_{jm} } \frac{4 y_i^2 \sigma^2 e^{2v_i} }{( 1+ e^{2v_i} )^2 }\] \[|\overline y|=\frac{2\sigma}{1+e^{2vi}}\] \[|\overline y_i|(2\sigma-|\overline y_i|) = \frac{4 \sigma^2 e^{2v_i} }{( 1+ e^{2v_i} )^2 }\] \[\lambda_{jm}=-\frac{g'}{g''}=\frac{\sum_{ x_i \in R_{jm} } \overline y_i}{\sum_{ x_i \in R_{jm}} |\overline y_i|(2\sigma-|\overline y_i|) }\]上面的推导过程和xgboost很相似，只不过这里是对一个叶子节点上的数据进行推导的，且损失函数使用的交叉熵损失。xgboost是对所有叶子节点上的数据进行推导的，且适用于所有损失函数。从这里也可以看出来，最终求得的叶子节点权重和xgboost的结果也仅仅是差了一个正则项系数。
参考：
https://zhuanlan.zhihu.com/p/52447211
https://blog.tsingjyujing.com/ml/recsys/ranknet
https://zhuanlan.zhihu.com/p/68682607
https://github.com/ChenglongChen/tensorflow-LTR
https://www.cnblogs.com/bentuwuying/p/6690836.html
http://blog.jqian.net/post/lambdamart.html
https://www.cnblogs.com/wowarsenal/p/3900359.html
https://esl.hohoweiya.xyz/10-Boosting-and-Additive-Trees/10.5-Why-Exponential-Loss/index.html
https://octopuscoder.github.io/2020/03/27/LambdaMART%E4%BB%8E%E6%94%BE%E5%BC%83%E5%88%B0%E5%85%A5%E9%97%A8/
http://dasonmo.cn/2019/02/08/from-ranknet-to-lambda-mart/
https://blog.csdn.net/huagong_adu/article/details/40710305