IR学习笔记 #09 网页排序
本文最后更新于：2022年11月28日 下午
当我们在一个小的文档库中查询时，即使 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 中，随机选取一个页面作为访问起点，随机选取其链出的页面进行访问，再对下一个页面重复上述操作。
大量重复后，统计每个结点被访问的频率，用频率近似概率后，我们可以发现访问概率较大者通常有着较多的链入，或者其链入页面也有着较大的访问概率。用公式表示就是： \[ \mathrm{Pr}\left( P_i \right) =\mathrm{Pr}\left( P_i\mid P_1 \right) \mathrm{Pr}\left( P_1 \right) +\mathrm{Pr}\left( P_i\mid P_2 \right) \mathrm{Pr}\left( P_2 \right) +\cdots +\mathrm{Pr}\left( P_i\mid P_N \right) \mathrm{Pr}\left( P_N \right) \] 其中 $( P_iP_1 ) $ 表示从编号为 1 的网页跳转到编号为 i 的网页的概率，其计算方式为： \[ \mathrm{Pr}\left( P_i\mid P_1 \right) =\begin{cases} 0\text{，如果}P_1\text{到}P_i\text{没有链入}\\ \frac{1}{m}\text{，}m\text{为}P_1\text{的链出数}\\ \end{cases} \]
矩阵表示 | Matrix Representation
令 $w_i=( P_i ) $，则 \(\boldsymbol{w}=\left[ \mathrm{Pr}\left( P_1 \right) ,\mathrm{Pr}\left( P_2 \right) ,\cdots ,\mathrm{Pr}\left( P_N \right) \right] ^T\)，再令 $_i=$，则有：
\[ w_{i}=B_i\cdot \boldsymbol{w} \]
特别地，当 i 取遍 1 到 N 的所有值后， 得到矩阵形式： \[ \boldsymbol{w}=B\cdot \boldsymbol{w} \] 其中 B 称作标准化链接矩阵，矩阵中的每个元素代表列号对应的 Page 链入行号对应的 Page 的概率，每列之和为 1。当一个页面没有链出时，这一列全为 0。
于是我们可以用迭代方法求解这个方程的稳定解 \(\boldsymbol{w}_k\)——即我们想求的访问概率向量，也就是重要度向量。只需要将 \(\boldsymbol{w}_0\) 设为全 1 向量（因为一开始随机访问到每个页面的概率都相同），不断代入即可。
阻尼迭代 | PageRank with Damping
然而，现在存在的问题是，上面的所有推导都是建立在理想状态下的，即假设所有网页组成的这个有向图是强连通的。
当 Hyperlink Graph 存在 link loops (循环陷阱)，即存在一个小的子图，只有链入没有链出，所有随机游走的用户到了这几个网页后，就如同进了黑洞一般，一直在里面“打转”，出不来了。
这样就使得当游走次数趋于无穷时，最终陷阱中结点的访问次数远大于其他结点。这样会使得计算出的 \(\boldsymbol{w}\) 向量中，陷阱外的结点访问概率都为 0。
PageRank 算法最终采用了阻尼因子（damping factor）的修正，使得进入陷阱后仍有机会跳出循环。 \[ \boldsymbol{w}_k=d\boldsymbol{w}_0+\left( 1-d \right) B\cdot \boldsymbol{w}_{k-1} \] 其中 \(\boldsymbol{w}_0\) 为全 1 向量，d 是实验确定的常数，通常取 0.15。
结合相关度 | Combined Method
有了重要度向量后，当有查询时，我们只需要先确定命中文档（至少有一个 term 与 query 相同的文档），再将其用重要度排序即可。
然而，这样做的缺点是，没有考虑到查询和文档的相关性——即，有可能一篇文档虽然有相同的 term，但主题却相去甚远。
于是，有人提出了结合 Term Weighting 和 PageRank 的方法，在确定命中文档后，利用传统的权重计算方法，计算出 query 和每个 doc 的相似度 \(s_j\)。再和重要度 \(p_j\) 线性加权算出排序指标： \[ c_j=\lambda s_j+\left( 1-\lambda \right) p_j \] 其中 \(\lambda\) 为实验确定的常数。
PageRank 算法缺点
忽略了查询，则忽略了 query 和 doc 主题相关性，导致结果的相关性降低。
没有过滤广告链接和功能链接（例如常见的分享链接）。这些链接通常没有什么实际价值，前者链接到广告页面，后者常常链接到某个社交网站首页。
对新网页不友好。因为即使是非常好的新页面也不会有很多链入，要成为一个高重要度的页面仍需要很长时间的推广。
主题敏感 PR | Topic-Sensitive PageRank
在实际的网络中，PageRank 算法还存在「主题漂移」问题，特别对于大量随意交互外链的站点，会导致搜索引擎返回主题无关结果。
同时，前面的讨论提到，PageRank 忽略了 query 的主题相关性，也导致了结果的相关性降低。同一查询词在不同语境下，语义上指向的可能是不同的主题，但 PageRank 无论如何都是返回「重要度」最高的页面。
理想情况下，应为每个用户的偏好维护一套专用的「主题重要度」向量，但面对海量用户这种方法显然不可行。所以搜索引擎一般会选择一种称为主题敏感的折中方案。
基本思想 | Basic Idea
基本假设：在 PageRank 的随机游走模型中，用户倾向于选择具有同一个主题的链出网页。
基于这个假设，可以预定义几个话题类别，例如体育、娱乐、科技等等，对于某个网页来说，对应某个主题类型都有相应的 PageRank 分值，然后想办法关联用户的话题倾向，根据用户的话题倾向排序结果。
矩阵形式 | Matrix Form
与原始的 PageRank 不同，新的算法对出度为 0 的网站加以处理以保证收敛性。引入了向量 \(\boldsymbol{d}\) 来指示某一个网页是否出度为 0，若为 0 则对应项为 1。 \[ d_{i}= \begin{cases}1 & \text { if } \operatorname{deg}(j)=0 \\ 0 & \text { otherwise }\end{cases} \]
向量 \(\boldsymbol{p}\) 来表示访问各个网页的概率均等，代替 \(\boldsymbol{w}_0\) 的写法：
\[ \boldsymbol{p}=\left[\frac{1}{n}\right]_{n \times 1} \]
两个矩阵的乘积所得的矩阵 D 表示出度为 0 的网页将以均等概率访问其他网页。与前述提到的矩阵 \(B\) 具有互补的特性，补充了在随机游走模型中，一个网页出度为 0 时的访问页面的情况。这样做使得最终矩阵的每一列之和都为 1。 \[ D=\boldsymbol{p} \times \boldsymbol{d}^{T} \] 则最终排名的计算方法为： \[ \boldsymbol{Rank} =d \boldsymbol{p} + (1-d)(B+D) \cdot \boldsymbol{Rank} \]
偏置向量 | ODP-Biasing
主题的预定义参考了 ODP (Open Directory Project) 网站，利用 ODP 中 16 个顶级分类下的 URLs 生成了 16 组偏置 PageRank 向量 (biased PageRank vectors)。
为了实现这一点，算法中采用了新的向量 \(\boldsymbol{v_j}=\boldsymbol{p}\)，针对每个主题有： \[ v_{j i}=\left\{\begin{array}{cl} \frac{1}{\left|T_{j}\right|} & i \in T_{j} \\ 0 & i \notin T_{j} \end{array}\right. \] 其中 \(T_{j}\) 表示在契合第 j 个主题的网页集合。包含在这些网页中的页面被赋予较大的跳转概率值，而其他网站则相对减少。
查询打分 | Query-Time Importance Score
此外，还需要在给定一个查询 q 的时候，估算出该查询落在某个主题 \(c_j\) 的概率。文章使用了朴素贝叶斯分类器（naive-Bayes classifier），将查询 q 中的每个 term 分词记作 \(q_i\)，利用贝叶斯公式： \[ P\left(c_{j} \mid q\right)=\frac{p\left(c_{j}\right) \cdot P\left(q \mid c_{j}\right)}{P\left(q\right)} \propto P\left(c_{j}\right) \cdot \prod_{i} P\left(q_{i} \mid c_{j}\right) \] 而 \(P\left(q_{i} \mid c_{j}\right)\) 则容易用统计的方法估计出来，对于 \(P\left(c_{j}\right)\) 则采用先验概率的方法，根据用户的查询历史（上下文）进行动态调整。
计算出了查询落在各个主题的概率后，再用这个概率对各个主题下的 Rank 向量进行线性加权，即可得到最终排序用的评分： \[ s_{q d}=\sum_{j} P\left(c_{j} \mid q^{\prime}\right) \cdot r_{j d} \]
HITS: Hyperlink-Induced Topic Search
这里再介绍一种基础的网页排序算法——基于超链接追敏的主题排序，对于一个查询，不再返回单一的网页排名，而是同时返回两个列表：
- 包含链接的 Hub 网页，收录了主题相关的权威网页链接。
- 包含内容的 Authority 网页，有着与主题相关的高质量内容。
那么，如何排序这两个列表呢？
基本假设：
- 一个好的 Hub 网页指向该主题的许多 Authority 网页。
- 一个好的 Authority 网页被许多好的 Hub 网页指向。
基于这两个假设，我们可以提出两个指标来衡量每个页面：枢纽值（Hub Scores）和权威值（Authority Scores），这两种值是互相依存、互相影响的。
- 枢纽值，指的是页面上所有出链指向页面的权威值之和。
- 权威值，指的是页面的所有入链所在的原页面的枢纽值之和。
算法步骤 | HITS Algorithm
找出 root set：根据用户 query 中的 term，在文档集中找出包含至少一个 term 的的文档，使他们构成 root set。
找出 base set：在 root set 的基础上，找出集合中网页链入或链出并且不在 root set 中的网页，并把他们加入到集合中，从而构成 base set。
计算每一个网页的枢纽值 h(x) 和权威值 a(x)，初始时，所有 h 值和 a 值均为 1。
迭代更新两个值直至收敛。为了防止两个值太大，可以在每次迭代后归一化。归一化的指标不重要，因为我们只关注相对排名。
返回两个值分别排序的列表。
HITS 算法缺点
- 尽管限制了计算对象在 base set 中，但在线计算效率还是太低，不如 PR 快。
- 主题漂移现象仍未解决。如果在集合里包含与查询主题无关的页面，且含有大量相互链接，可能会排到前列。这种现象被称为紧密链接社区现象。