Learning to Rank: From Pairwise Approach to Listwise Approach

一篇老论文了, 清华和微软亚研院于 2007 年发表在 ICML 上的一篇论文, 提出了一个 Listwise 的 LTR 方法 — ListNet. 了解 LTR 任务也有一段时间了, 逐渐了解了 Pointwise 和 Pairwise 的做法, 这次也来看看 Listwise 是怎么做的.

• Introduction
• Preliminaries
• How To Do
  • Probability Models
  • Learning Method: ListNet
• Conclusion

论文基本信息:

• 论文地址：https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-2007-40.pdf

• 来源：清华, 微软亚研院

• 关键词：Search; Learning To Rank; Listwise

1. Introduction

在搜索中 Pairwise 的做法还是比较常见的. Pairwise 的目的也是学习一个打分模型, 但是训练时是通过构建相关性等级不同的 doc pair 作为样本, 以对这个 pair 的偏序关系的分类作为学习目标来优化模型的参数. 因此很多现有的分类模型可以直接作为这个打分模型. 但是 Pairwise 的形式有一些问题:

• LTR 的目标由排序转化成了分类问题 — 最小化 doc pair 分类的偏差, 这并不等价于最小化排序中的偏差;
• 计算过程是耗时的. doc pair 会比 doc 数要多很多;
• 对 doc pair 进行分类时引入了 i.i.d 假设;
• 不同 query 下的 doc 数量分布不均, 因此 pair 的分布也不均;

这对以上问题, 文中提出了一种 listwise 的方法, 以一个 ranking list 作为训练的样本来训练一个打分模型. 关键在于: 如何定义 listwise 的损失函数 --- 如何基于打分列表计算损失.. 文中将文档列表的打分转化为一个概率分布, 以计算模型预测的概率分布和真实的概率分布间的差异作为损失函数.

2. Preliminaries

形式化地描述以下问题. $Q = { q^1, q^2, \cdots , q^m }$ 表示 query 集合. 对于每个 query $q^i$ 有一个文档列表 $d^i = { d_1^i, d_2^i, \cdots, d_{n^i}^i }$, 以及每个文档的相关性得分 $y^i = { y_1^i, y_2^i, \cdots, y_{n^i}^i }$. 对于 $q^i$ 下的每个文档 $d_j^i$, 其特征为 $x_j^i = \Psi(q^i, d_j^i)$, 则一个文档列表其对应的特征列表为 $x^i = { x_1^i, x_2^i, \cdots, x_{n^i}^i }$. 因此在 listwise 中, 一个样本就是一个特征列表和对应的打分列表, 则训练集可以表示为 $\mathcal{T} = { (x^i, y^i) }_{i=1}^m$.

目的是通过 $\mathcal{T}$ 学习一个排序函数 $f$, 对于每一个 $x_j^i$, $f$ 能输出对应的分数. 对于特征列表 $x^i$, 令其输出的分数列表为 $z^i = (f(x_1^i), \cdots, f(x_{n^i}^i))$. 那么在 $\mathcal{T}$ 上的 listwise loss 可以定义为: \(\sum_{i=1}^m L(y^i, z^i)\)

3. How To Do

3.1. Probability Models

文中的做法是将打分列表转化为一个概率分布, 这样就可以把衡量两个概率分布的差异的函数作为损失函数了. 因此关键在于怎么把打分列表转化为概率分布.

将文档的排序抽象成一个排列的问题. 给定 $n$ 个待排序的对象, 并分别标识为 $1, 2, \cdots, n$. 这些对象的一个排列 $\pi$ 可以看作从一个映射, 表示为 $\pi = <\pi(1), \pi(2), \cdots, \pi(n)>$, $\pi(j)$ 表示位置 $j$ 处的对象.

作者认为排列的出现是服从某个概率分布的, 即每个排列 $\pi$ 都是有一定概率出现的, 文中把这个概率叫做 Permutation Probability. 那么如何计算之呢?

假设我们已经有一个打分函数 $f$ 了, 为每个对象预测了一个分数 $s = (s_1, s_2, \cdots, s_n)$. permutation probability 的计算是以 $s$ 为基础的: \(P_s(\pi) = \prod_{j=1}^n \frac{\phi(s_{\pi(j)})}{\sum_{k=j}^n \phi(s_{\pi(k)})}\) 其中 $\phi(\cdot)$ 是一个递增且大于 0 的函数. 文中对 $P_s(\pi)$ 是一个概率分布进行了证明, 即 $P_s(\pi) > 0$ 且 $\sum_{\pi \in \Omega_n} P_s(\pi) = 1$.

那么怎么来设计 listwise 的损失函数呢? 首先损失函数的输入是两个分数列表, 分别表示真实的每个对象的得分以及模型预测的的得分. 一种做法: 先分别计算每个分数列表对应的排列的概率分布, 再计算这两个概率分布之间的距离. 但是由于 $n$ 个对象存在 $n!$ 种排列, 这个计算是很复杂的. 因此文中提出了 Top one Probability.

Top one Probability 是针对一个对象而言的, 即给定分数列表后, 这个对象在第一的概率. 因此这个概率的计算也很显然, 即该对象排第一的所有排列的 permutation probability 之和:

但是这个看起来计算貌似也蛮复杂的, $\pi(1)=j$ 的排列有 $(n-1)!$ 种. 文中对 $P_s(j)$ 的求解进行了化简:

如果为每个待排序对象计算其 Top one probability, 则可以得到给定得分列表的情况下的 Top one 概率分布, 且该概率分布的计算复杂度是可接受的. 那么 listwise 的损失函数也就呼之欲出了:

3.2. Learning Method: ListNet

有了损失函数后, 那么只需要一个打分函数即可了, 其实就是一个神经网络, 鉴于那还是 2007 年, ListNet 是一个很简单的网络. 文中也指定了 $\phi(\cdot)$ 函数, 即指数函数, 因此 $P_s(j)$ 相当于现在我们常提到的 softmax.

4. Conclusion

终于对 Pointwise, Pairwise, Listwise 都有所了解了. 不过 listwise 在业界貌似用的不是很多, 而且这篇论文也比较老了, 不知道 listwise 是否有些新的进展. 不过目前接触到的 pairwise/listwise 方法都体现在损失函数以及输入样本的构造上, 并没有直接将多个待排序对象输入模型中, 没有显示建模待排序对象之间的信息.