『IR 信息检索入门必看』#9 网页排序（简明）

访问博客查看 本文 最新内容，排版更美观ヾ(•ω•`)o 如有错误欢迎指出~

IR 信息检索系列笔记：

• IR学习笔记 #1 概论&布尔模型
• IR学习笔记 #2 统计语言模型
• IR学习笔记 #3 向量空间模型
• IR学习笔记 #4 概率模型
• IR学习笔记 #5 检索系统评价
• IR学习笔记 #6 网络信息检索
• IR学习笔记 #7 IRLbot
• IR学习笔记 #8 倒排索引模型
• IR学习笔记 #9 网页排序
• IR学习笔记 #10 查询相关反馈
• IR学习笔记 #11 问答系统
• IR课程项目-文学检索-开发文档

当我们在一个小的文档库中查询时，即使 query 很模糊，我们只要返回所有相关文档即可，甚至不需要猜测用户的查询需求。

但如果在一个大的文档集中查询时（比如谷歌），往往可以返回大量的相关文档。如果基于相关度的 ranking，往往无法区分哪些文档该呈现在最前面，甚至可能时一些低质量的网页对于某些词的词频很高，从而排在了前面。

此时我们就不能只聚焦与「相关度」，PageRank 算法通过计算一个页面的「重要度」，从而判别网页质量，得到排序。

基本思想

如何衡量「重要度」？用点击率、权威性？然而，这些数据都是爬虫无法爬取到的，同时也难以正确衡量。

科学家们从 Bibliometrics (文献计量学) 中借鉴了如下观点：

• Bibliographic coupling (引文耦合)：两篇文章具有相近的引用。
• Co-citation (协同引用)：两篇文章被大量其他文章同时引用。
• Impact factor (影响因子)：一个期刊中的文章的年平均被引次数，衡量了一个期刊的「重要度」。

例如，最权威的 SCI 往往只收录其认为重要的期刊，也只记录其中的期刊相互引用的次数。当一篇文章被 SCI 收录的文章引用时，通常也可以说明其有一定的影响力——即重要度的「传递」。

对于文献引用的可视化，我们通常称为 Citation Graph，通常是一个 Directed Acyclic Graph (有向无环图，DAG)，因为较早的文章无法修改而引用后来的文章。

在网页中，我们可以 Hyperlinks (超链接) 来类比引用，从而形成一个 Hyperlink Graph，区别是这类图中可以有环路。

从而引出网页排序的基本假设：

• The rank of a web page is higher if many pages link to it.
• Links from highly ranked pages are given greater weight than links from less highly ranked pages.

PageRank Algorithm

基于上述假设，我们很容易可以得到当前页面的链入、链出数。但是，要怎么知道链入当前页面的前序页面，其重要度是多少呢？

随机游走模型 | Random Walk Model

在一个封闭的 Hyperlink Graph 中，随机选取一个页面作为访问起点，随机选取其链出的页面进行访问，再对下一个页面重复上述操作。

大量重复后，统计每个结点被访问的频率，用频率近似概率后，我们可以发现访问概率较大者通常有着较多的链入，或者其链入页面也有着较大的访问概率。用公式表示就是：

其中 表示从编号为 1 的网页跳转到编号为 i 的网页的概率，其计算方式为：

矩阵表示 | Matrix Representation

令 ，则 ，再令 ，则有：

特别地，当 i 取遍 1 到 N 的所有值后， 得到矩阵形式：

其中 B 称作标准化链接矩阵，矩阵中的每个元素代表列号对应的 Page 链入行号对应的 Page 的概率，每列之和为 1。当一个页面没有链出时，这一列全为 0。

于是我们可以用迭代方法求解这个方程的稳定解 ——即我们想求的访问概率向量，也就是重要度向量。只需要将 设为全 1 向量（因为一开始随机访问到每个页面的概率都相同），不断代入即可。

阻尼迭代 | PageRank with Damping

然而，现在存在的问题是，上面的所有推导都是建立在理想状态下的，即假设所有网页组成的这个有向图是强连通的。

当 Hyperlink Graph 存在 link loops (循环陷阱)，即存在一个小的子图，只有链入没有链出，所有随机游走的用户到了这几个网页后，就如同进了黑洞一般，一直在里面“打转”，出不来了。

这样就使得当游走次数趋于无穷时，最终陷阱中结点的访问次数远大于其他结点。这样会使得计算出的 向量中，陷阱外的结点访问概率都为 0。

PageRank 算法最终采用了阻尼因子（damping factor）的修正，使得进入陷阱后仍有机会跳出循环。

其中 为全 1 向量，d 是实验确定的常数，通常取 0.15。

结合相关度 | Combined Method

有了重要度向量后，当有查询时，我们只需要先确定命中文档（至少有一个 term 与 query 相同的文档），再将其用重要度排序即可。

然而，这样做的缺点是，没有考虑到查询和文档的相关性——即，有可能一篇文档虽然有相同的 term，但主题却相去甚远。

于是，有人提出了结合 Term Weighting 和 PageRank 的方法，在确定命中文档后，利用传统的权重计算方法，计算出 query 和每个 doc 的相似度 。再和重要度 线性加权算出排序指标：

其中 为实验确定的常数。

PageRank 算法缺点

1. 忽略了查询，则忽略了 query 和 doc 主题相关性，导致结果的相关性降低。

2. 没有过滤广告链接和功能链接（例如常见的分享链接）。这些链接通常没有什么实际价值，前者链接到广告页面，后者常常链接到某个社交网站首页。

3. 对新网页不友好。因为即使是非常好的新页面也不会有很多链入，要成为一个高重要度的页面仍需要很长时间的推广。

主题敏感 PR | Topic-Sensitive PageRank

在实际的网络中，PageRank 算法还存在「主题漂移」问题，特别对于大量随意交互外链的站点，会导致搜索引擎返回主题无关结果。

同时，前面的讨论提到，PageRank 忽略了 query 的主题相关性，也导致了结果的相关性降低。同一查询词在不同语境下，语义上指向的可能是不同的主题，但 PageRank 无论如何都是返回「重要度」最高的页面。

理想情况下，应为每个用户的偏好维护一套专用的「主题重要度」向量，但面对海量用户这种方法显然不可行。所以搜索引擎一般会选择一种称为主题敏感的折中方案。

基本思想 | Basic Idea

基本假设：在 PageRank 的随机游走模型中，用户倾向于选择具有同一个主题的链出网页。

基于这个假设，可以预定义几个话题类别，例如体育、娱乐、科技等等，对于某个网页来说，对应某个主题类型都有相应的 PageRank 分值，然后想办法关联用户的话题倾向，根据用户的话题倾向排序结果。

矩阵形式 | Matrix Form

与原始的 PageRank 不同，新的算法对出度为 0 的网站加以处理以保证收敛性。引入了向量 来指示某一个网页是否出度为 0，若为 0 则对应项为 1。

向量 来表示访问各个网页的概率均等，代替 的写法：

两个矩阵的乘积所得的矩阵 D 表示出度为 0 的网页将以均等概率访问其他网页。与前述提到的矩阵 具有互补的特性，补充了在随机游走模型中，一个网页出度为 0 时的访问页面的情况。这样做使得最终矩阵的每一列之和都为 1。

则最终排名的计算方法为：

偏置向量 | ODP-Biasing

主题的预定义参考了 ODP (Open Directory Project) 网站，利用 ODP 中 16 个顶级分类下的 URLs 生成了 16 组偏置 PageRank 向量 (biased PageRank vectors)。

为了实现这一点，算法中采用了新的向量 ，针对每个主题有：

其中 表示在契合第 j 个主题的网页集合。包含在这些网页中的页面被赋予较大的跳转概率值，而其他网站则相对减少。

查询打分 | Query-Time Importance Score

此外，还需要在给定一个查询 q 的时候，估算出该查询落在某个主题 的概率。文章使用了朴素贝叶斯分类器（naive-Bayes classifier），将查询 q 中的每个 term 分词记作 ，利用贝叶斯公式：

而 则容易用统计的方法估计出来，对于 则采用先验概率的方法，根据用户的查询历史（上下文）进行动态调整。

计算出了查询落在各个主题的概率后，再用这个概率对各个主题下的 Rank 向量进行线性加权，即可得到最终排序用的评分：

HITS: Hyperlink-Induced Topic Search

这里再介绍一种基础的网页排序算法——基于超链接追敏的主题排序，对于一个查询，不再返回单一的网页排名，而是同时返回两个列表：

• 包含链接的 Hub 网页，收录了主题相关的权威网页链接。
• 包含内容的 Authority 网页，有着与主题相关的高质量内容。

那么，如何排序这两个列表呢？

基本假设：

• 一个好的 Hub 网页指向该主题的许多 Authority 网页。
• 一个好的 Authority 网页被许多好的 Hub 网页指向。

基于这两个假设，我们可以提出两个指标来衡量每个页面：枢纽值（Hub Scores）和权威值（Authority Scores），这两种值是互相依存、互相影响的。

• 枢纽值，指的是页面上所有出链指向页面的权威值之和。
• 权威值，指的是页面的所有入链所在的原页面的枢纽值之和。

算法步骤 | HITS Algorithm

1. 找出 root set：根据用户 query 中的 term，在文档集中找出包含至少一个 term 的的文档，使他们构成 root set。

2. 找出 base set：在 root set 的基础上，找出集合中网页链入或链出并且不在 root set 中的网页，并把他们加入到集合中，从而构成 base set。

3. 计算每一个网页的枢纽值 h(x) 和权威值 a(x)，初始时，所有 h 值和 a 值均为 1。

4. 迭代更新两个值直至收敛。为了防止两个值太大，可以在每次迭代后归一化。归一化的指标不重要，因为我们只关注相对排名。

5. 返回两个值分别排序的列表。

HITS 算法缺点

1. 尽管限制了计算对象在 base set 中，但在线计算效率还是太低，不如 PR 快。
2. 主题漂移现象仍未解决。如果在集合里包含与查询主题无关的页面，且含有大量相互链接，可能会排到前列。这种现象被称为紧密链接社区现象。