LambdaLoss | Google排序学习优化框架
今天分享一篇谷歌在CIKM'18上发表的排序学习listwise损失函数优化的论文「LambdaLoss」[1]，可以认为是沿袭着微软早期代表性工作[2]的路线，即：，对learning2rank的一些模型做了一个比较系统性的一个解释框架，从排序优化度量指标(metric)的视角提出了统一的优化框架，通过EM算法，可以和家喻户晓的listwise优化方法Lambda梯度联系起来，个人觉得非常有意思。
现状
主流的排序算法中，不管是pointwise还是pairwise都不能直接优化排序度量指标，如NDCG等。在listwise中，我们通过定义「Lambda梯度」来优化排序度量指标，如LambdaRank和LambdaMART，然而Lambda梯度是一种经验性方法，缺乏理论指导。谷歌在CIKM'18上，提出了优化排序度量指标的概率模型框架，叫做「LambdaLoss」[2]，提供了一种EM算法来优化Metric驱动的损失函数。文中提到LambdaRank中的Lambda梯度在LambdaLoss框架下，能够通过定义一种良好、特殊设定的损失函数求解，提供了一定的理论指导。
传统的pointwise或pairwise损失函数是平滑的凸函数，很容易进行优化。有些工作已经证明「优化这些损失」的结果是「真正排序度量指标」的界，即实际回归或分类损失函数是排序度量指标误差(度量指标取相反数)的上界[3]，不断最小化损失函数这一上界，能够达到最小化度量指标误差的目的，这个思想和ELBO (Evidence lower bound) 如出一辙。但是这个上界粒度比较粗，因为优化不是metric指标驱动的。很自然的想法是，如何得到一种更加逼近真正排序度量指标误差的损失函数。
然而，直接优化排序指标的挑战在于，排序指标依赖于列表的排序结果，而列表的排序结果又依赖于每个物品的得分，导致排序指标曲线要么不是平坦的，要么不是连续的，即非平滑，也非凸。因此，梯度优化方法不实用，尽管有些非梯度优化方法可以用，但是时间复杂度高，难以规模化。为了规模化，目前有3种途径，
1.近似法，缺点是非凸，容易陷入局部最优； 2.将排序问题转成结构化预测问题，在该方法中排序列表当做最小单元来整体对待，损失定义为实际排序列表和最理想排序列表之间的距离，缺点是排序列表排列组合数量太大，复杂度高； 3.使用排序指标在迭代过程中不断调整样本的权重分布(回顾下WRAP就是这种，LambdaRank也属于这种，就可以看做是权重。这个方法优点是既考虑了排序指标，同时也是凸优化问题。
本文的动机之一就是探索LambdaRank中提出的Lambda梯度真正优化的损失函数是什么。文章通过提出LambdaLoss概率框架，来解释LambdaRank可以通过EM算法优化LambdaLoss得到。进一步，可以在LambdaLoss框架下，定义基于排序和得分条件下，metric-driven的损失函数。
LambdaLoss框架
假定给定文档集合下，不同文档的模型预测得分确定了一个关于所有可能排序排列组合的分布，即，其中是其中一种排序列表结果。也就是说，模型可以得到多种排序结果，而每种排序结果下，文档真实标签的似然是不同的（pairwise loss只和有关，而Lambda梯度不仅和有关，还和位置(即排序)有关）。我们将看做隐变量，则真实标签的似然关于该隐变量分布的期望如下：
我们的目标是学习排序模型来最大化该期望（可以类比EM算法中的，我们这里的是EM中的，因为我们要最大化的是文档的标签的似然值）。
则负对数似然为(考察了List-Level的损失)：
这个式子有两个核心要素，1是排序分布，2是似然。这两个核心要素取不同形式，会得到不同的损失函数。
似然不同形式：
Logistic: ，此时和没关系，只和得分之间的相对关系有关。则，，故负对数似然求和公式中可以把该似然式子提到求和的外面(和没关系)，则排序分布求和为1，可以约掉，则损失等价于Logistic Loss，，注意是参数。
generalized logistic: 。这是带指数的广义Logistic分布。此处使用了代表排序列表和(交换i和j)的NDCG值的差。下面会证明通过EM算法可以根据该式得到LambdaRank的损失函数。
借鉴上述的思想，可以得到如下「1个」文档级别的训练样本的损失函数：（我将其称为 ranking-sensitive pairwise loss）,
至于排序分布，作者举了上述LambdaLoss框架中，使用高斯分布作为排序分布时，等价于我们熟知的[4]方法，而使用Plackett-Luce作为排序分布时，等价于我们熟知的ListNet[5]算法。
使用EM算法优化上述损失：
E步：根据当前模型计算隐变量的分布. M步：固定，重新在complete数据集上最小化负对数似然，并优化模型参数。其中，完整数据集为：。目标是优化如下损失：。
C是抽样得到的所有的训练样本（每个训练样本都是文档列表级别的，由构成，也可以理解为E步会对每个原始文档集合排序()，得到的所有文档集合排序结果构成M步的训练样本），M步在C上求期望损失。
其中，
其中，是根据分布采样得到的。
更特殊的，直接使用hard assignment distribution来表示。
其中，是按照得分降序排序得到的列表。（此时EM算法和K-means中的优化方法一样，可以将K-means中E步将样本归入到某个类别簇 类比为 此处对文档列表排一个序，每种序对应一个类别，类别是隐向量；将文档按照得分降序得到唯一的序类比于K-means中将某个样本硬性(hard)的归入到一个具体的类。）
此时，可以通过推导下述负对数似然损失函数得到LambdaRank的损失函数：
E步：根据当前模型计算所有文档的得分，然后按照得分降序排序，得到排序结果。
M步：所有Complete的「文档列表」的损失简化为：
进一步，代入generalized logistic可得到：
因此，上式是LambdaRank潜在的损失函数。
作者进一步给出了定义Metric-driven Loss的方法：
LamdaLoss中一个最具吸引力的特性是，似然部分既考虑了得分，又考虑了排序。这提供了一个沟通依赖于得分的传统损失函数(e.g., pairwise loss)和依赖于排序的排序度量指标(e.g., NDCG)的桥梁。
作者给出一些常用的排序度量指标的metric-driven Loss。主要利用0-1Loss的上界为Logistic Loss这一性质。比如：Average Relevance Position指标：
，ARP是cost-based function，越小越好。此时在LambdaLoss框架下的，相应的损失函数为，:
「上述推导有2个技巧」：
1.把ranking中的position 转成形式:
作者还推导了NDCG的LambdaLoss，由于NDCG是gain-based function，故先转成Loss：
其中，，对于给定的文档列表，是个常数 (和排序无关，公式中分子只和标签有关, 分母是最优的DCG值，是个常数。所以可以直接加到损失函数中)；第二项其实就是NDCG（, ），这么定义是因为下文推导方便。
因为：，有：
同理可得，LmabdaLoss损失为：
上述问题是太大时，上界太松了。因此，作者又提出了另一种损失，利用了性质（这个性质有待证明）。最后可以推导出NDCG第二种形式的损失（「关键」）：
上式的好处在于，可以通过重新定义和来扩展出很多NDCG-like metrics的LambdaLoss。也可以用来优化binary情况下的，MRR-like metrics。
作者还推导出上述得到的LambdaRank Loss优化结果实际上是优化如下metric的上界，
可以证明，使用LambdaLoss优化该metric得到的，即：LambaLoss优化对应的度量指标误差上界比LambdaRank优化对应的度量指标误差的上界更紧，因此LambdaLoss的优化结果更逼近真实的NDCG指标。
另外，上述讨论都基于hard assignment 。作者也考虑了soft assignment，并作为下一步工作。
总结
非常有意思的文章，通过LambdaLoss框架，可以加深对Lambda梯度的理解。
可以发现lambdaRank的Lambda梯度的优化方法可以通过EM来推导。 lambdaRank有没有潜在的损失函数以及是如何和评价指标NDCG关联上的？lambdaRank的loss本质上是优化ndcg的一个较为粗糙的上界。如果纯从逼近优化ndcg的目标，文中也推导出了ndcg-loss1和ndcg-loss2的表达式，其作为NDCG度量指标误差的上界，能够比lambdaRank更紧。
最后，本篇文章中提到的LambdaLoss值得在搜索推荐等场景中尝试。
参考
[1] CIKM18: The LambdaLoss Framework for Ranking Metric Optimization：https://storage.googleapis.com/pub-tools-public-publication-data/pdf/1e34e05e5e4bf2d12f41eb9ff29ac3da9fdb4de3.pdf
[2] From RankNet to LambdaRank toLambdaMART: An Overview：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.180.634&rep=rep1&type=pdf
[3] mcrank-learning-to-rank-using-multiple-classification-and-gradient-boosting：https://papers.nips.cc/paper/3270-mcrank-learning-to-rank-using-multiple-classification-and-gradient-boosting.pdf
[4] SoftRank：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.469.3608&rep=rep1&type=pdf
[5] ListNet：https://www.microsoft.com/en-us/research/publication/learning-to-rank-from-pairwise-approach-to-listwise-approach/?from=http%3A%2F%2Fresearch.microsoft.com%2Fapps%2Fpubs%2Fdefault.aspx%3Fid%3D70428