LambdaLoss | Google排序学习优化框架

阿泽 Crz

发布于 2021-04-29 15:33:51

1.5K0

发布于 2021-04-29 15:33:51

文章被收录于专栏：阿泽的学习笔记阿泽的学习笔记

今天分享一篇谷歌在CIKM'18上发表的排序学习listwise损失函数优化的论文「LambdaLoss」[1]，可以认为是沿袭着微软早期代表性工作[2]的路线，即：

\text{RankNet} \rightarrow \text{LambdaRank} \rightarrow \text{LambdaMART}

，对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也属于这种，

|\Delta NDCG|

就可以看做是权重。这个方法优点是既考虑了排序指标，同时也是凸优化问题。

本文的动机之一就是探索LambdaRank中提出的Lambda梯度真正优化的损失函数是什么。文章通过提出LambdaLoss概率框架，来解释LambdaRank可以通过EM算法优化LambdaLoss得到。进一步，可以在LambdaLoss框架下，定义基于排序和得分条件下，metric-driven的损失函数。

LambdaLoss框架

假定给定文档集合下，不同文档的模型预测得分

\boldsymbol{s}=\Phi(\boldsymbol{x})

确定了一个关于所有可能排序排列组合的分布，即

p(\pi|\boldsymbol{s})

，其中

\pi

是其中一种排序列表结果。也就是说，模型

\Phi

可以得到多种排序结果，而每种排序结果下，文档真实标签

\boldsymbol{y}

的似然

p(\boldsymbol{y}|\boldsymbol{s},\pi)

是不同的（pairwise loss只和

\boldsymbol{s}

有关，而Lambda梯度不仅和

有关，还和位置(即排序)有关）。我们将

\pi

看做隐变量，则真实标签

\boldsymbol{y}

的似然关于该隐变量分布的期望如下：

p(\boldsymbol{y}|\boldsymbol{s})=\sum_{\pi \in \Pi} p(\boldsymbol{y}|\boldsymbol{s},\pi)p(\pi|\boldsymbol{s})

我们的目标是学习排序模型

\boldsymbol{s}=\Phi(\boldsymbol{x})

来最大化该期望

p(\boldsymbol{y}|\boldsymbol{s})

（可以类比EM算法中的

P(X|\Theta)

，我们这里的

\boldsymbol{y}

是EM中的

，因为我们要最大化的是文档的标签的似然值）。

则负对数似然为(考察了List-Level的损失)：

l(\boldsymbol{y},\boldsymbol{s})= -\log_2 P(\boldsymbol{y}|\boldsymbol{s})=-\log_2 \sum_{\pi \in \Pi} p(\boldsymbol{y}|\boldsymbol{s},\pi)p(\pi|\boldsymbol{s})

这个式子有两个核心要素，1是排序分布

p(\pi|\boldsymbol{s})

，2是似然

P(\boldsymbol{y}|\boldsymbol{s},\pi)

。这两个核心要素取不同形式，会得到不同的损失函数。

似然

P(\boldsymbol{y}|\boldsymbol{s},\pi)

不同形式：

Logistic:

p(y_i >y_j|s_i,s_j)=\frac{1}{1+e^{-\sigma \cdot (s_i-s_j)}}

，此时

\boldsymbol{y}

和

\pi

没关系，只和得分之间的相对关系有关。则

\forall \pi

，

P(\boldsymbol{y}|\boldsymbol{s},\pi)=P(\boldsymbol{y}|\boldsymbol{s})

，故负对数似然求和公式中可以把该似然式子提到求和的外面(和

\pi

没关系)，则排序分布求和为1，可以约掉，则损失等价于Logistic Loss，

l(\boldsymbol{y},\boldsymbol{s})=-\log_2 p(\boldsymbol{y}|\boldsymbol{s})=\sum_{y_i>y_j} \log_2(1+e^{-\sigma \cdot (s_i-s_j)})

，注意

\sigma

是参数。

generalized logistic:

p(y_i >y_j|s_i,s_j, \pi_i, \pi_j)=\frac{1}{1+e^{-\sigma \cdot (s_i-s_j)}}^{|\Delta \text{NDCG}_{ij}|}

。这是带指数的广义Logistic分布。此处使用了

|\Delta \text{NDCG}_{ij}|

代表排序列表

\pi_i

和

\pi_j

(交换i和j)的NDCG值的差。下面会证明通过EM算法可以根据该式得到LambdaRank的损失函数。借鉴上述的思想，可以得到如下「1个」文档级别的训练样本的损失函数：（我将其称为 ranking-sensitive pairwise loss）,

l(\boldsymbol{y},\boldsymbol{s})=-\sum_{y_i>y_j}\log_2 \sum_{\pi}p(y_i>y_j|s_i,s_j,\pi_i,\pi_j)p(\pi|\boldsymbol{s})

至于排序分布

p(\pi|\boldsymbol{s})

，作者举了上述LambdaLoss框架中，使用高斯分布作为排序分布时，等价于我们熟知的[4]方法，而使用Plackett-Luce作为排序分布时，等价于我们熟知的ListNet[5]算法。

使用EM算法优化上述损失：

E步：根据当前模型

\Phi^{(t)}

计算隐变量的分布

p^{(t)}(\pi|\boldsymbol{s})

M步：固定

p^{(t)}(\pi|\boldsymbol{s})

，重新在complete数据集上最小化负对数似然，并优化模型参数。其中，完整数据集为：

C=\{(\boldsymbol{y},\boldsymbol{x},\pi)|\pi \sim p^{(t)}(\pi|\boldsymbol{s}) \}

。目标是优化如下损失：

\Phi^{(t+1)}=argmin \mathcal {L}_C(\Phi)=arg min\frac{1}{|T|} \sum_{(\boldsymbol{y},\boldsymbol{x}) \in T} l_C(\boldsymbol{y},\Phi(\boldsymbol{x}))

。

C是抽样得到的所有的训练样本（每个训练样本都是文档列表级别的，由

(\boldsymbol{y},\boldsymbol{x},\pi)

构成，也可以理解为E步会对每个原始文档集合

\boldsymbol{x}

排序(

\pi

)，得到的所有文档集合排序结果构成M步的训练样本），M步在C上求期望损失。

其中，

l_C(\boldsymbol{y},\boldsymbol{s})=-\sum_{\pi}p^{(t)}(\pi|\boldsymbol{s}) \log_2 p(\boldsymbol{y}|\boldsymbol{s},\pi) \approx -\frac{1}{K} \sum_{k=1}^K \log_2 P(\boldsymbol{y}|\boldsymbol{s},\pi^{k})

其中，

\pi^{k}

是根据分布

p^{(t)}(\pi|\boldsymbol{s})

采样得到的。

更特殊的，直接使用hard assignment distribution来表示

p^{(t)}(\pi|\boldsymbol{s})

。

H(\hat{\pi}|\boldsymbol{s})=1 \ \text{and} \ H(\pi|\boldsymbol{s})=1 \ \forall \pi \neq\hat{\pi}

其中，

\hat{\pi}

是按照得分

\boldsymbol{s}

降序排序得到的列表。（此时EM算法和K-means中的优化方法一样，可以将K-means中E步将样本归入到某个类别簇类比为此处对文档列表排一个序，每种序对应一个类别，类别是隐向量；将文档按照得分降序得到唯一的序类比于K-means中将某个样本硬性(hard)的归入到一个具体的类。）

此时，可以通过推导下述负对数似然损失函数得到LambdaRank的损失函数：

l(\boldsymbol{y},\boldsymbol{s})=-\sum_{y_i>y_j}\log_2 \sum_{\pi}p(y_i>y_j|s_i,s_j,\pi_i,\pi_j)H(\pi|\boldsymbol{s})

E步：根据当前模型计算所有文档的得分，然后按照得分降序排序，得到排序结果

\hat{\pi}

。

M步：所有Complete的「文档列表」的损失简化为：

\begin{aligned} l_C(\boldsymbol{y},\boldsymbol{s})&= -\sum_{\pi}p^{(t)}(\pi|\boldsymbol{s}) \log_2 p(\boldsymbol{y}|\boldsymbol{s},\pi) \\ &= -\sum_{\pi} H(\pi|\boldsymbol{s})\log_2 p(\boldsymbol{y}|\boldsymbol{s},\pi) \\ &= -\log_2 p(\boldsymbol{y}|\boldsymbol{s}, \hat{\pi}) \end{aligned}

进一步，代入generalized logistic可得到：

\begin{aligned} l_C(\boldsymbol{y},\boldsymbol{s}) &= -\log_2 p(\boldsymbol{y}|\boldsymbol{s}, \hat{\pi}) \\ &= -\sum_{y_i>y_j} \log_2 p(y_i>y_j|s_i,s_j,\hat{\pi}_i,\hat{\pi}_j) \\ &=\sum_{y_i>y_j}|\Delta \text{NDCG}_{ij}| \log_2(1+e^{-\sigma \cdot (s_i-s_j)}) \end{aligned}

因此，上式是LambdaRank潜在的损失函数。

作者进一步给出了定义Metric-driven Loss的方法：

LamdaLoss中一个最具吸引力的特性是，似然部分

p(\boldsymbol{y}|\boldsymbol{s}, \pi)

既考虑了得分，又考虑了排序。这提供了一个沟通依赖于得分的传统损失函数(e.g., pairwise loss)和依赖于排序的排序度量指标(e.g., NDCG)的桥梁。

作者给出一些常用的排序度量指标的metric-driven Loss。主要利用0-1Loss的上界为Logistic Loss这一性质。比如：Average Relevance Position指标：

ARP=\sum_{i=1}^n y_i \cdot i

，ARP是cost-based function，越小越好。

\begin{aligned} \text{ARP}&=\sum_{i=1}^n y_i (\sum_{j=1}^n \mathcal{I}_{s_i < s_j} +1) \\ &=\sum_{i=1}^n\sum_{j=1}^n y_i \mathcal{I}_{s_i < s_j} + C_1\\ &\leq \sum_{i=1}^n\sum_j^n y_i \log_2(1+e^{-\sigma \cdot(s_i-s_j)}) + C_1 \end{aligned}

此时在LambdaLoss框架下的，相应的损失函数为，

\text{APR-LOSS1}

l(\boldsymbol{y},\boldsymbol{s})=-\sum_{i=1}^n\sum_{j=1}^n \log_2 \sum_{\pi}(\frac{1}{1+e^{-\sigma \cdot (s_i-s_j)}})^{y_i} H(\pi|\boldsymbol{s})

「上述推导有2个技巧」：

1.把ranking中的position

转成形式:

\mathcal I_{s_i<s_j}

2.把Metric转成Metric-driven loss过程中，先整理成generalized logistic形式，这个就是排序分布

p(\pi|\boldsymbol{s})

，再利用EM算法中概率排序分布取hard assignment distribution，将generalized logistic进一步改写成

\sum_{\pi} p(\pi|\boldsymbol{s}) H(\pi|\boldsymbol{s})

；再取负对数得到损失。另外文中还给出了ARP的另一种损失。

作者还推导了NDCG的LambdaLoss，由于NDCG是gain-based function，故先转成Loss：

\text{NDCG}_{\text{cost}}=\sum_{i=1}^n G_i - \sum_{i=1}^n \frac{G_i}{D_i} =\sum_{i=1}^n \frac{G_i}{D_i}(D_i-1)=\sum_{i=1}^n G_i(1-\frac{1}{D_i})

其中，

G_i=\frac{2^{y_i}-1}{max_\text{DCG}}

，对于给定的文档列表，

G_i

是个常数 (和排序无关，

G_i

公式中分子只和标签

y_i

有关, 分母是最优的DCG值，是个常数。所以可以直接加到损失函数中)；第二项其实就是NDCG（

D_i=log_2(1+i)

\text{NDCG}=\sum_{i=1}^n \frac{G_i}{D_i}

），这么定义是因为下文推导方便。

因为：

D_i − 1 = \log_2 (1 + i) − 1 ≤ i − 1

，有：

\begin{aligned} \text{NDCG}_{\text{cost}} &=\sum_{i=1}^n \frac{G_i}{D_i}(D_i-1)\\ & \leq \sum_{i=1}^n \frac{G_i}{D_i}(i-1) \\ & \leq \sum_{i=1}^n \frac{G_i}{D_i}\sum_{j=1}^n\mathcal{I}_{s_i < s_j} \\ & \leq \sum_{i=1}^n \frac{G_i}{D_i} \log_2(1+e^{-\sigma \cdot (s_i-s_j)}) \end{aligned}

同理可得，LmabdaLoss损失为：

l(\boldsymbol{y},\boldsymbol{s})=-\sum_{i=1}^n\sum_{j=1}^n \log_2 \sum_{\pi}(\frac{1}{1+e^{-\sigma \cdot (s_i-s_j)}})^{\frac{G_i}{D_i}} H(\pi|\boldsymbol{s})

上述问题是

太大时，上界太松了。因此，作者又提出了另一种损失，利用了性质（这个性质有待证明）

1-\frac{1}{D_i}=\sum_{j=1}^{i-1}|\frac{1}{D_{|i-j|}}-\frac{1}{D_{|i-j|}+1}|=\sum_{j=1}^{i-1} \delta_{ij}

。最后可以推导出NDCG第二种形式的损失（「关键」）：

l(\boldsymbol{y},\boldsymbol{s})=-\sum_{y_i>y_j} \log_2 \sum_{\pi}(\frac{1}{1+e^{-\sigma \cdot (s_i-s_j)}})^{\delta_{ij}|G_i-G_j|} H(\pi|\boldsymbol{s})

上式的好处在于，可以通过重新定义

G_i

和

D_i

来扩展出很多NDCG-like metrics的LambdaLoss。也可以用来优化binary情况下的，MRR-like metrics。

作者还推导出上述得到的LambdaRank Loss优化结果实际上是优化如下metric的上界，

\text{Metric}_{\text{LambdaRank}}=\sum_{i=1}^n G_i \sum_{j=1}^{i-1}|\frac{1}{D_i}-\frac{1}{D_j}|

可以证明，使用LambdaLoss优化该metric得到的

\text{NDCG}_{\text{cost}} \leq \text{Metric}_{\text{LambdaRank}}

，即：LambaLoss优化对应的度量指标误差上界比LambdaRank优化对应的度量指标误差的上界更紧，因此LambdaLoss的优化结果更逼近真实的NDCG指标。

另外，上述讨论都基于hard assignment

\hat{\pi}

。作者也考虑了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

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2021-04-21，如有侵权请联系 cloudcommunity@tencent.com 删除

serverless

编程算法

本文分享自阿泽的学习笔记微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

serverless

编程算法

登录后参与评论

0 条评论

热度