Google 矩阵

使用一款搜索引擎，我们希望搜索结果能够拥有最佳的排序，Google 为它最核心的排序算法 PageRank 申请了专利。在 PageRank 以前，排序大多依靠对搜索关键字和目标页的匹配度来进行的，这种排序方式弊端明显，尤其对于善于堆砌关键字舞弊的页面，很容易就跳到了搜索结果的首页。Larry Page 和 Sergey Brin 开始着手解决这个问题，Google 排序的继承来自于互联网上网页之间的链接关系。一张网页被其它网页引用的次数越多，可以简单地认为这样的网页越受欢迎，当然在结果列表中应该越靠前。

前面提到了目标网页被引用网页的“ 数量”，另一条重要的判定 PageRank 级别的依据则是“ 质量”。换言之，质量高的网页所引用的网页，质量往往也比较高，所以质量高的网页投票所占权重理应更高。

在用户访问某一张网页时，假设他有 q 的概率去点击网页上的链接，并且点击该网页每条链接的概率都是相等的。如果该网页有 n 条链接的话，那么点击每条链接的概率就是 1/n。

在表现网页之间链接关系时，Google 使用了矩阵。假设互联网上共有 N 个页面，那么我们可以写出一个 N×N 的矩阵，其中的元素 p_ij，如果存在从页 i 被页 j 指向的链接（为什么使用“ 被指向” 而非“ 指向”，前文已经解释了），那么 p_ij 就大于 0，反之就等于 0。同时，每一列元素的取值都除以链接数 n（前文提到了），使得各列矢量总和成为 1，行矢量则表示了各个状态之间的迁移概率，这个最大特征值为 1 的矩阵就成为了 PageRank 矩阵。

现在给出 N 为 4 的一个例子（共有 A、B、C、D 四张网页）帮助说明这个矩阵（这个例子来自于这篇文章）：

 

可以看到矩阵 L 的几个非零元素的取值：

• p₃₁=1; 表示被 A 指向的只有 C
• p₁₂=1; 表示被 B 指向的只有 A
• p₁₃=p₄₃=1/2; 表示被 C 指向的有 A 和 D
• p₁₄=p₂₄=p₃₄=1/3; 表示被 D 指向的有 A、B、C

于是，对于 A 来说，它的 PageRank 取值就可以表示为：

PR(A) = PR(B)/1 + PR(C)/2 + PR(D)/3

但这是在用户百分之百点击网页链接的情况下发生的，实际上，只有 p 概率的用户会点击网页链接，剩下 (1-p) 概率的用户会跳到无关的页面上去，而访问的页面恰好是 4 这个页面中 A 的概率只有 (1-p)/4（p 正是前文提到的“ 阻尼系数”（damping factor），Google 取 p 等于 0.85），所以：

PR(A) = (1-p)/4 + p(PR(B)/1 + PR(C)/2 + PR(D)/3)

推广到一般公式（p_i 表示第 i 张网页，L(p_j) 表示从 p_i 链出网页的数量）：

如果仅仅依赖这个公式，可以看得到每一个页面的 PageRank(p_i) 的值都和其他页面有关系，这样一来，就没有办法直接解出这个 PageRank(p_i) 的值来了。

不过，佩奇和布林想到了一个办法，有了 PageRank(p_i) 的概念以后，PageRank 矩阵就可以用一个特征向量来表示：

由上述两个公式，可以得到（其中 l(p_i,p_j) 就是前文提到过的 p_ij）：

接着给所有网页一个统一的初始权值，每次都用上面提到的 R 矩阵去乘以原始的 N×N 的矩阵，把结果这个新的矩阵继续去乘以那个 N×N 的原始矩阵，反复进行，相乘行为引起的矩阵变化越来越小，直到收敛到一个给定的值以内，停止。

这时的矩阵就包含了每个网页的 PageRank 特征向量，对于每个向量来说，它的每一个维度值去乘以该维度下的权值并累加，最终都可以转化为一个具体的 PageRank 的数字。

这就是 PageRank 计算最最基本的部分，Google 对于这种超大型矩阵相乘有自己的保密技术。截止到 2010 年，Google 索引的网页总数已经超过 5000 亿，也就是说，Google 必须解这个阶数的矩阵相乘问题，这是不是真的就是 MapReduce 之类的由来呢？

以上未特殊注明的公式截图来自于维基百科。

文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》