【本节概括】本节主要讨论如何对网页进行排序，在保障语义匹配的同时确保质量？

目录

一、排序学习算法介绍

二、排序学习的一般流程

2.1 训练阶段：构建并训练排序模型

2.2 测试阶段：用模型完成新查询的排序

三、三种排序学习算法介绍

3.1 Pointwise 类排序算法

3.2 Pairwise 类排序算法

3.3 Listwise 类排序算法

四、网页权威性计算

4.1 PageRank

4.2 PageRank 的拓展模型

4.3 HITS 算法与网页角色区分

---

一、排序学习算法介绍

        对于网页内容的排序，本质上是一个学习排序器的问题。我们要根据用户的需求/偏好，把更符合需求的网页文档尽可能往前排。

        如果已知排序依据，那么可以根据已知信息的排序方法对文档进行排序；但假如不知道排序依据，那就只能根据历史记录推测。

        网络上这么多的页面，肯定不可能让人工去一个一个排序，我们需要通过用户相关性反馈，训练一个学习排序器（Ranker）来解决该问题。输入文档内容及相应查询，输出该文档合适的相对的排序位置。这是一个有监督学习问题，基于已知的排序，学习一个表示用户偏好的 Ranker，并基于 Ranker 为新网页 - 查询对给出排序。

        排序学习与传统有监督学习的区别在于

• 排序学习需要同时考虑文档内容和查询信息；
• 相较于文档的精确的得分，排序学习更关心文档之间的相对顺序。

二、排序学习的一般流程

2.1 训练阶段：构建并训练排序模型

这一阶段的目标是利用标注好的训练数据，学习出一个能计算 “查询 - 文档相关性” 的模型。

1. 准备训练数据训练数据由多组查询（queries）、对应文档（documents）及多级相关度标签（Labels）组成：

   • 每个查询对应若干文档；
   • 标签是 “多级评分”（比如图中的 4、2、1 等），代表文档与对应查询的相关程度（分数越高，相关性越强）。

2. 输入学习系统（Learning System）将上述 “查询 - 文档 - 相关度标签” 的训练数据输入学习系统，系统会基于这些数据训练模型。

3. 训练模型（最小化损失）学习系统的核心目标是最小化损失（min Loss），最终得到一个排序模型：

   • q 是查询，d 是文档，w 是模型参数；
   • 这个模型可以计算任意 “查询 - 文档对” 的相关性得分。

2.2 测试阶段：用模型完成新查询的排序

这一阶段的目标是对新查询的待排文档，输出按相关性排序的结果。

1. 准备测试数据测试数据是一个新查询 q + 待排序的文档集合（如 \(d_1、d_2、…d_n\)），这些文档的相关度是未知的（图中用 “?” 表示）。

2. 输入排序系统（Ranking System）将新查询和待排文档输入排序系统，排序系统会调用训练好的模型。

3. 输出排序结果模型会为每个 “查询 - 文档对” 计算相关性得分，最终输出带得分的文档列表），文档可依据得分从高到低排序，完成排序任务。

简言之，排序学习的流程是：用 “查询 - 文档 - 相关度” 训练数据得到模型 → 用模型计算新查询下各文档的相关性得分 → 按得分排序文档。

三、三种排序学习算法介绍

3.1 Pointwise 类排序算法

        基本假设，训练样本中的任何一个查询 - 文档对，都可以映射到一个分值或一个有序的类别（如优良中差）。相应地，给定一个查询 - 文档对，Pointwise LTR 将试图预测其分值/类别。常见的模型包括：

• 回归，将查询-文档对映射到具体分数
• 分类，将排序问题转化为一个面向有序类别的二分类/多分类问题
• 有序回归，在映射到具体分数的同时保持样本之间的有序关系

        Pointwise类排序算法可以简单且广泛地套用已有回归、分类算法。然而，其局限性也较为明显，首先，Pointwise类方法往往更为注重文档的相关度得分，而并不注 重文档之间的相关性排序；其次，不同查询所对应的文档，尤其相关文档数量不同，对损失函 数的贡献也各不相同，一定程度上影响效果。

3.2 Pairwise 类排序算法

        基本假设：同样是将排序问题转化为分类问题（二分类或三分类）。每次比较一个查询与两个文档，衡量两个文档的偏序（Partial Order）。分类器的目的在于判断哪个文档应该排在前面，对应的标签为{1, -1}或{1, 0, -1}（0表示两个文档可以并列）。

        相比于Pointwise类算法，Pairwise类排序算法通过衡量样本之间的偏序 关系，实现了从绝对相关性（分值）到相对偏序的改进。然而，Pairwise类算法也具有自己的缺陷：首先，两两成对导致样本数大为提升，计算资源开支增加；其次，Pairwise类算法仍然受样本不平衡问题的影响；最后，Pairwise类算法无法体现全局排序的合理性。

3.3 Listwise 类排序算法

        基本思路：直接面向整体排序结果进行优化，直接将排序的完整队列作为学习的对象。通常情况下，解决这一问题采用以下两种思路，直接采用某种IR指标对排序进行优化，或是直接设计面向完整排序的损失函数。

1、采用某种 IR 指标对排序进行优化

        此类方法较为直观，且可以直接优化所获得排序结果的衡量指标。然而，该类方法也面临明显的挑战，大多数排序指标，如NDCG等，因为与排序相关，属于非光滑、 不可微的函数，因此，传统的优化方法很难直接应用于该问题。

2、直接设计面向完整排序的损失函数

        将排序器所得的排序向量与标准答案的排序向量之间的余弦相似度作为目标函数。

        通常情况下，由于全局优化的作用，Listwise类排序算法可以取得相比于 Pointwise 和 Pairwise 类算法更好的效果。然而，Listwise类算法也会面临一些小的挑战，例如两个网页并列的情况。

四、网页权威性计算

        大众创造内容的时代后遗症就是内容权威性的下降，如何才能在衡量相关性的同时，确保内容的权威性。一个好的想法是大家说好才是真的好！

4.1 PageRank

        它的设计思路是将网页视作一个点，网页间的超链接视作一条边，形成一个巨大的有向图。PageRank背后的总体思路：优质网页引用或推荐的网页，一定还是优质网页。这其中总共有三重衡量标准：

• 链入链接数：单纯意义上的受欢迎程度；
• 链入链接本身是否推荐度高：欢迎本身是否具有权威性；
• 链入链接源页面的链接数：被选中的几率，体现源网页是否滥发推荐。

        PageRank的核心公式如下：

        其中：

• PR(pi)为网页pi的PageRank值
• PR(pj)为指向网页pi的某个网页pj的PageRank值
• L(pj)为网页pj发出的链接数量
• d为阻尼系数，取值在0-1之间
• N为网页总数，M(pi)为链入pi的页面集合

        在计算过程（这是一个马尔可夫过程）中，采用近似迭代算法计算PageRank值。首先给每个网页赋予一个初值，例如1/N，然后，利用之前的公式进行迭代有限次计算，得到近似结果。

        或许在这张图中可能会存在陷阱节点（只有一条指向自己的边，没有其它出边），终止节点（没有任何出边），孤立节点（没有任何入边）。但因为有 (1-d) / N 的存在，相当于以一定概率重新选择起点。

4.2 PageRank 的拓展模型

1、主题敏感 PageRank

        PageRank在衡量网页的整体权威性方面具有显著的意义，然而，用户的个性化因素却没有在PageRank中得以体现。浅显的想法是将用户偏好排序与PageRank值结合起来，另一种想法是模拟用户自己的网页浏览行为，从而计算个性化的权威性。但这样计算量极大，折中的方案是以主题为中介，为特定的主题计算相应的PageRank。

        最终，每个网站将得到一个Topicsensitive的向量，即使不属于某个Topic，网页也可以 通过PageRank获得相应的数值。 同样，用户的需求也将表示为Topic向量，两个向量的内积可以反应这一网站在用 户特定主题需求下的权威性。

2、Hilltop 算法

        Hilltop算法的基本概念之一：非从属组织网页。满足以下两种情况，将被视作从属组织网页：

• 主机IP地址的前三个字段相同，如182.61.200.X （百度）
• URL中的主域名段相同，如 XXX.ustc.edu.cn

        Hilltop算法的基本概念之二：专家页面。所谓专家页面，即与某个主题相关的高质量页面。专家页面一般通过如下启发式规则进行挑选：

• 至少包括K个出边，K由人为指定
• K个出边指向的所有页面相互之间的关系都符合“非从属组织页面”

        专家页面之外的部分被称作“目标页面集合”，即需要进行PageRank计算，判定其权威性的部分。Hilltop算法的基本流程：

1. 首先，根据用户的查询需求，选定相关的专家页面，并计算其相关性
2. 其次，遵循PageRank算法，对目标页面集合进行排序，即将专家页面的相关性得分，传递到其他的目标页面上去
3. 最后，整合最相关的专家页面和得分较高的目标页面返回给用户

        该方法能够一定程度上避免恶意添加链接的作弊行为，同时保证搜索与主 题的相关性。但结果严重依赖专家页面的搜索和确定，存在一定偏见。

4.3 HITS 算法与网页角色区分

        Hilltop算法尝试了网页角色的区分，但仍有进一步的空间。即使通过个性化或主题敏感进行了修正，但对网页的功能仍不区分。例如，专业信息站点与门户网站，在提供信息的种类上区别很大，因此，将对外链接的输出和功能视作等价不符合实际情况。

        HITS的目的是在海量网页中找到并区分与用户查询主题相关的高质量权威网页（Authority）与枢纽网页（Hub，类似中介，指向了很多高质量的权威网页）。这里有两个基本假设：

        基于先前的基本假设，HITS的计算过程如下：

1. 首先，根据关键字获取与查询最相关的少数页面，及与这些页面有链接关系的页面，作为待选集合
2. 其次，对所有网页的 a(p) 与 h(p) 进行初始化，可都设为1
3. 最后，迭代计算两个步骤，即基本假设所对应的两个公式。重复这一步，直到最终收敛为止（注意每一步中的归一化过程！），输出Authority或Hub值较高的页面。