排序算法的多种类别

LTR模型

Learning to Rank相关的模型可以分为三类:

pointwise
pairwise
listwise

总的来说, Pointwise和Pairwise把排序问题转换成回归, 分类问题, Lisewise把一个Query下个搜索结果组织成一个列表, 整个列表作为一个训练的样本.

Pointwise和Pairwise方法的优点是可以直接利用已有的分类和回归算法, 缺点是训练数据的group structure会被忽略. 这里的group是按Query进行划分的, 即这两种方法不会考虑每个Query下所有Doc之间的序列关系, 导致其学习目标和真实的衡量排序的目标并不一定是一致的.

Lisewise则将一个Ranking List作为一个样本来训练, 会考虑每个Query下所有Doc的序列关系.

下面分别介绍这三种类型的模型.

Pointwise

Pointwise方法的主要思想是将排序问题转化为多分类问题或者回归问题. 以多类分类为例进行说明.

对于一个Query, 与其相关的Doc集合为 $\{d_1, d_2, \cdots, d_n\}$ , 对于这 $n$ 个 $(\text{query}, d_i)$ 对, 从中抽取特征, 表示成特征向量. 至于抽取特征的方法, 在排序算法的第一篇文章中有描述.

得到特征向量之后, 就可以建立模型了. 根据标签的种类, 可以视为回归模型或分类模型.

回归模型

将Query与文档 $d_i$ 之间的相似度作为要拟合的值, 拟合出一个回归模型, 对Query和Doc之间的相似度做预测.

分类模型

将Query与文档 $d_i$ 之间的相关程度使用label表示, 如{Perfect, Excellent, Good, Fair, Bad}五个级别, 可以是是否相关二分类问题. 然后就可以训练一个分类器了.

Pointwise有一个显著的缺点, 即完全从单个文档的角度出发, 完全没有考虑文档之间的关系和先后顺序的影响, 这样产生的结果很可能是没有从实际角度出发, 导致使用起来效果较差.

Pairwise

Pairwise方法是目前比较流行的方法, 效果也非常不错. 它的主要思想是将排序问题转换为二分类问题, 具体来说是对于一个Query中的两个Doc $d_1$ 和 $d_2$ , 判断 $d_1$ 的排列顺序是否应当在 $d_2$ 之前.

对于同一条Query, 在它的所有相关文档集里, 对任两个文档, 都可以得到一个训练实例pair. 对于这个doc pair, 需要给它一个label来表示前一个doc顺序是否应当排在后一个doc之前. 这里可以使用前面单个文档的真实的与Query相关性的标注(人工方法, 日志搜索等), 例如 $d_1$ 与Query的相关类别为5(最高级别), $d_2$ 的相关类别为3, 那么这一对的真实标签就给为1, 从而得到了二元分类器训练所需的样本.

预测时, 只需要对所有pair进行分类, 便可以得到文档集的一个偏序关系, 从而实现排序.

Pairwise方法有很多模型可以实现, SVM, Boosts, NN等.

相比于Pointwise方法, Pairwise方法不再对相关度作独立假设, 它会对同一个Query里的文档集生成训练样本. 但Pairwise模型也有一些缺点:

只考虑了两个文档之间的相对先后顺序, 却没有考虑文档出现在搜索列表中的位置. 通常来说, 排在前列的搜索文档更为重要, 如果前排的文档判断错误, 产生的损失应当大于后排文档的错误, 这一点Pairwise是没有涉及到的. 应当使在搜索列表前列排错顺序付出更高的代价
不同的Query对应的文档列表的长度是不一样的, 而且之间的差距很大, 有很多的, 有很少的. 由于模型是按照文档对为样本进行的训练, 所以如果一个Query对应的文档数量很少, 其排列的正确与否对整体的结果影响不会很大, 因为大部分训练样本都是由Query-大Document集合产生的. 因此在相关文档数量很少的Query上的准确率表现会很差

Lisewise

Listwise方法相比于Pointwise, Pairwise而言, 不再将排序问题直接形式化为一个分类或者回归问题, 而是直接对文档列表的排序结果进行优化. 目前主要有两种优化方法:

直接针对Ranking评价指标进行优化
比如常用的MAP, NDCG等. 但是往往难以实现, 因为NDCG这样的评价指标通常是非平滑(连续)的, 而通用的目标函数优化方法针对的都是连续函数, 因此无法优化
优化损失函数
损失函数的构造有很多种方式:
- RankCosine使用正确排序与预测排序的分值向量之间的Cosine相似度(夹角)来表示损失函数
- ListNet使用正确排序与预测排序的排列概率分布之间的KL距离作为损失函数

以ListNet为例为例进行说明. ListNet首先把文档的排序列表转换成概率分布, 然后选取交叉熵或KL距离来衡量由模型训练出的文档排序和真正的文档排序之间的差异损失, ListNet最小化该损失函数以达到排序的目的.

把有顺序的文档列表转换成概率

对于某个Query, 假设我们有 $n$ 篇文档需要进行排序, 用 $\pi=(\pi(1),\pi(2),\cdots,\pi(n))$ , 其中 $\pi(i)$ 表示在第 $i$ 位置的文档. 再假设 $\Phi(\cdot)$ 是一个恒大于0且递增的函数, 例如线性函数 $\Phi(x)=ax,\quad x\gt 0$ 或指数函数 $\Phi(x)=\exp(x)$ . 则某种排列组合 $\pi$ 的概率为:

\begin{aligned} P_s(\pi)=\prod\limits_{j=1}^{n}\frac{\Phi(s_{\pi(j)})}{\sum\limits_{k=j}^{n}\Phi(s_{\pi(k)})} \end{aligned}

其中 $s_{\pi(j)}$ 表示排列在第 $j$ 位置的文档对应的得分. 对每个文档评价得分的方式, 就是我们要训练的模型.

上面的方法要考虑这个Query对应的所有文档的排列组合情况, 因此对应的时间复杂度为 $O(n!)$ , 为了缓解复杂度, 使用Top-K概率.

序列 $(j_1,j_2,\cdots,j_k)$ 的Top-K概率表示这些文档( $j_i$ 代表一个文档)在总共 $n$ 个文档中为前 $K$ 个的概率. 定义前 $k$ 个文档 $(j_1,j_2,\cdots,j_k)$ 的文档排序组成一个Top-K的Subgroup, $G_k$ 代表所有Top-K的Subgroup集合. 则 $G_k$ 共有 $\frac{n!}{(n-k)!}$ 中组合, 大大低于原来的 $n!$ 种组合.

序列 $(j_1,j_2,\cdots,j_k)$ 的Top-K概率为:

$P_s(g_k(j_1,j_2,\cdots,j_k))=\sum\limits_{\pi \in g_k(j_1,j_2,\cdots,j_k)}P_s(\pi)=\prod\limits_{t=1}^{k}\frac{\Phi(s_{j_t})}{\sum\limits_{l=t}^{k}\Phi(s_{j_l})}$

计算概率分布的差异值

在得到模型输出的排序之后, 与真实的文档排序对比, 我们可以使用多种方法来计算两个概率分布之间的差异值作为损失函数, ListNet采用交叉熵来计算两个概率分布之间的差异:

$H(p,q)=-\sum\limits_{x}p(x)\log q(x)$

在ListNet中, 假设 $P_{y^{(i)}}(g)$ 表示实际文档排序 $g$ 的概率, $P_{z^{(i)}}(g)$ 是模型预测得到的文档排序 $g$ 的概率, 那么这两组文档排序概率分布之间的交叉熵为:

$L(y^{(i)},z^{(i)})=-\sum\limits_{\forall{g}\in{G_k}}P_{y^{(i)}}(g)\log(P_{z^{(i)}}(g))$

最小化损失函数

使用梯度下降的方法进行优化. 取 $\Phi(x)=\exp(x)$ , 最小化上面的损失函数, 更新参数 $w$ , 迭代公式如下:

\begin{aligned} \Delta{w} &= \frac{\partial L(y^{(i)},z^{(i)}(f_w))}{\partial w} \\ &= -\sum\limits_{\forall{g}\in{G_k}}\frac{\partial P_{z^{(i)}(f_w)}(g)}{\partial w} \cdot \frac{P_{y^{(i)}}(g)}{\partial P_{z^{(i)}(f_w)}(g)} \end{aligned}

上面的两项都是可导的, 前一项是在当前参数 $w$ 下得到的每个Doc的值(模型本身), 然后由这个分数得到的当前Top-K序列 $g$ 的概率, 这个概率对模型参数 $w$ 的导数.

参考资料

上一页排序算法评价指标下一页详解Pairwise模型

最后更新于4年前