> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/sou-suo-tui-jian/tui-jian-suan-fa/pai-xu-suan-fa/0x03-pai-xu-suan-fa-de-duo-zhong-lei-bie.md).

# 排序算法的多种类别

## 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$$的导数.

## 参考资料

* [Learning to Rank入门小结 + 漫谈](http://www.cnblogs.com/wentingtu/archive/2012/03/13/2393993.html)
* [机器学习排序](https://blog.csdn.net/hguisu/article/details/7989489)
* [ListNet 算法简介](http://www.cnblogs.com/kemaswill/archive/2013/01/24/2875434.html)