探索LTR框架：LambdaMART与TF-Ranking模型解析

名词解释

符号	说明
q	用户提交的查询请求
d	需要排序的文档
D	一次请求召回的待排序文档集
$x_i$	结果i的特征
s	模型计算得到的文档得分。 $s_i = score(x_i)$ ， $score(x)$ 就是我们要求解的模型。
(i,j)	文档 $d_i$ 和 $d_j$ 组成的有序pair
P	所有的文档pair集合
group	一次搜索下的N个结果成为一个group， $x_i$ 代表第i个结果，对于搜索来说， $x_i$ 可能包括相关性特征（文档title/summary/content等域的相关性特征）、doc侧特征、query侧特征。
$P_{ij}$	模型预测文档 $d_i$ 排在 $d_j$ 之前的概率
$\bar{P_{ij}}$	文档 $d_i$ 排在 $d_j$ 之前的真实概率，取值1或者0
$S_{ij}$	$d_i$ 与 $d_j$ 的真实序关系，取值范围{0, 1, -1}，分别代表 $d_i$ 的label比 $d_j$ 相同、更大、更小。

问题建模

Learning-To-Rank有pointwise/pairwise/listwise三种定义loss的方式。这里主要简介listwize方式的求解方式。

listwize相比于pointwise，区别在于样本的组织方式，训练样本以group为单位，一个group为“同一个query下的候选文档”或“同一个推荐session下的候选商品”，模型拟合的目标为每个group预测排序与真实序列（label）的近似程度，具体度量方式有NDCG/MAP/MRR等。

如同所有的监督式学习问题，我们从以下两个方面来考虑如何来建模listwize模型：

打分函数的设计，即 $f(x)$ 的设计

我们是对一个序列进行打分，还是对单个结果进行打分。在搜索和推荐的场景下，待排序的物品很多，如果打分函数的输入是一个序列，那对线上预测是不可接受的，所以打分函数最好是f(x),x是单个结果。当然对一些特殊的场合，比如一个商店每天总共只有几十个商品，要预测一个最好的排序方式，那么打分函数的打分对象可以是整个序列。
损失函数的设计，即f(x)预测出来的打分，与label的契合程度。

一个简洁的方式是对group内任意一个有序对来度量一个损失，这个损失就是预测的相对序与真实的相对序的的近似程度。考虑到每个pair对对NDCG的影响程度，为每个pair对配上一个权重，以达到优化NDCG等序列指标的目的。

按照这个思路，先引入一个打分函数 $score(x;w)$ ，即我们对某条结果的打分函数，那么我们最终要求解的也就是模型参数w。下面将 $score(x_i;w)$ 记为 $s_i$ 。

下面我们针对单个group进行分析。

对于该group内某个pair对 $(x_i, x_j)$ ， $x_i$ 比 $x_j$ 好的概率为：
$P_{ij} = P(x_i \rhd x_j) = sigmoid(s_i - s_j; \sigma)=\frac{1}{1 + \exp\bigl(-\sigma\cdot(s_i - s_j)\bigr)}$

拓展：

考虑更通用的情况， $P_{ij} = P(x_i \rhd x_j) = sigmoid(f(x_i \rhd x_j))$

上面的 $f(x_i \rhd x_j) = score(x_i) - score(x_j)$ (score(x)可以是GBDT也可以是DNN等任意模型) 是 $f(x_i \rhd x_j)$ 的表达方式的一种特例，因为你也可以把 $x_i, x_j$ 两组甚至多组特征同时输入一个模型。

在tfranking中称为Multi-Item Scoring，相应的对多item的打分函数为Groupwise Scoring Function（GSF），模仿用户在物料序列中的“先比较、再选择”的行为。

为了简化运算，我们忽略掉sigmoid函数的参数 $\sigma$ ，即另其为1，不影响后续的理解。

该pair对的损失函数为：
$L_{ij} = crossEntropy(\bar{P_{ij}}, P_{ij}) \\ =-\bar{P}_{ij}\log P_{ij} - (1 - \bar{P}_{ij})\log (1 - P_{ij}) \\ = -\bar{P}_{ij}(s_i - s_j) + \log\Bigl\{1 + \exp(s_i - s_j)\Bigr\}$

在listwize模型中，每个pair对有不同的权重。举个网页搜索的例子，假设某个query下人工标记的理想排序结果为doc1,doc2,...，doc10，label分别为5,4,4,3,3,3,2,2,2,1。doc1和doc10的相对序了是非常严重的，doc1和doc2的相对序错了也比较严重，doc9和doc10的相对序错了影响比较轻微。NDCG就是这个影响程度的量化方法。所以会在以上损失函数上乘以一个deltaNDCG。即：
$deltaNDCG(i,j)=\left |ndcg(original\ sequence)-ndcg(swap(i,j)\ sequence)\right |$

$L_{ij} = crossEntropy(\tilde{P_{ij}}, P_{ij})*deltaNDCG(i,j)$

模型学习

从损失函数到打分函数

因此可以求得目标函数对打分函数的偏导（对于softmax+交叉熵损失的形式，损失函数对打分函数的导数为预测值跟真实值的差值，这一结论可以直接运用，从而直接写出下面的结论。不熟悉的话可以自己求解一遍）：
$\frac{\partial{L_{ij}}}{\partial{s_i}} = [sigmoid(s_i - s_j)-\bar{P}_{ij}]\cdot deltaNDCG(i,j) = -\frac{\partial{L_{ij}}}{\partial{s_j}} \\$
我们定义：
$\lambda_{ij}\mathrel{\stackrel{\mbox{def}}{=}}\frac{\partial{L_{ij}}}{\partial{s_i}}$

容易得到：
$\lambda_{ij} = \frac{\partial{L_{ij}}}{\partial{s_i}}= -\frac{\partial{L_{ij}}}{\partial{s_j}}=-\lambda_{ji}$
再考虑该group所产生的的所有的pair对 $s_i$ 的偏导（记为 $\lambda_i$ ），有：
$\frac{\partial{L}}{\partial{s_i}} \mathrel{\stackrel{\mbox{def}}{=}} \lambda _{i}=\sum_{j(label(i)>label(j))}{\lambda_{ij}}-\sum_{j(label(i)<label(j))}{\lambda_{ij}}$

看到这里，我们梳理一下上面的过程，对于单个group，我们如何得到这个group的损失函数对某条结果的打分 $s_i$ 的偏导：

假设该group有N条结果，我们可以把 $\lambda_{ij}$ 写成矩阵的形式。容易看到这是一个反对称矩阵，他是以下两部分的乘积：

pair对交叉熵损失对打分函数的偏导，其实是真实pair序概率与预测pair序概率的差值，是一个N*N的反对称矩阵 $a_{ij}=-a_{ji}$ 。
pair对的deltaNDCG，代表pair对的权重，是一个对称矩阵。

而该group损失函数对每条结果的打分，即取该结果对应行的加和即可。

打分函数（即score(x)）的设计 - 引出lambdamart和tf-ranking

如果打分函数使用决策树，因为决策树不可导，只能用多颗决策树拟合梯度来完成上述的pairwise/listwise损失梯度下降的过程，再考虑二阶导，也就是xgboost，这就是lambdamart算法。在搜索的场景，排序的特征通常是低维稠密特征（百级别特征），所以比较适合用树模型，因此lambdamart使用比较广泛。
打分函数也可以是你自己构建的任何网络，比如DNN等。tf-ranking即是这样一种框架。

参考：

lambdamart论文：From RankNet to LambdaRank to LambdaMART: An Overview

tfranking论文：TF-Ranking: Scalable TensorFlow Library for Learning-to-Rank

LambdaMART 不太简短之介绍

走马观花Google TF-Ranking的源代码
 github
推荐我的开源项目 exFM c++ deepFM