谷歌背后的数学( 四 ) _小知识

这样，佩奇和布林就找到了一个不仅含义合理，而且数学上严谨的网页排序算法，他们把这个算法称为 PageRank，不过要注意的是，虽然这个名称的直译恰好是 “网页排序”，但它实际上指的是 “佩奇排序”，因为其中的 “Page” 不是指网页，而是佩奇的名字。这个算法就是谷歌排序的数学基础，而其中的矩阵 G 则被称为谷歌矩阵 (Google matrix) 。
细心的读者可能注意到了，我们还遗漏了一样东西，那就是谷歌矩阵中描述虚拟用户 “性格” 的那个 α 参数。那个参数的数值是多少呢? 从理论上讲，它应该来自于对真实用户平均行为的分析，不过实际上另有一个因素对它的选取产生了很大影响，那就是 Gnp0 收敛于 p 的快慢程度。由于 G 是一个 N×N 矩阵，而 N 为互联网上——确切地说是被谷歌所收录的——网页的总数，在谷歌成立之初为几千万，目前为几百亿，是一个极其巨大的数字。因此 G 是一个超大型矩阵，甚至很可能是人类有史以来处理过的最庞大的矩阵。对于这样的矩阵， Gnp0 收敛速度的快慢是关系到算法是否实用的重要因素，而这个因素恰恰与 α 有关。可以证明， α 越小， Gnp0 的收敛速度就越快。但 α 也不能太小，因为太小的话， “佩奇排序” 中最精华的部分，即以网页间的彼此链接为基础的排序思路就被弱化了 (因为这部分的贡献正比于 α)，这显然是得不偿失的。因此，在 α 的选取上有很多折衷的考虑要做，佩奇和布林最终选择的数值是 α = 0.85 。
以上就是谷歌背后最重要的数学奥秘。与以往那种凭借关键词出现次数所作的排序不同，这种由所有网页的相互链接所确定的排序是不那么容易做假的，因为做假者再是把自己的网页吹得天花乱坠，如果没有真正吸引人的内容，别人不链接它，一切就还是枉然[注六] 。而且 “佩奇排序” 还有一个重要特点，那就是它只与互联网的结构有关，而与用户具体搜索的东西无关。这意味着排序计算可以单独进行，而无需在用户键入搜索指令后才临时进行。谷歌搜索的速度之所以快捷，在很大程度上得益于此。
谷歌成立之初跟其它一些 “发迹于地下室” (one-man-in-basement) 的 IT 公司一样寒酸：雇员只有一位 (两位老板不算)，工作场所则是一位朋友的车库。但它出类拔萃的排序算法很快为它赢得了声誉。公司成立仅仅三个月，《PC Magzine》杂志就把谷歌列为了年度最佳搜索引擎。2001 年，佩奇为 “佩奇排序” 申请到了专利，专利的发明人为佩奇，拥有者则是他和布林的母校斯坦福大学。2004 年 8 月，谷歌成为了一家初始市值约 17 亿美元的上市公司。不仅公司高管在一夜间成为了亿万富翁，就连当初给过他们几十美元 “赞助费” 的某些同事和朋友也得到了足够终身养老所用的股票回报。作为公司摇篮的斯坦福大学则因拥有 “佩奇排序” 的专利而获得了 180 万股谷歌股票。2005 年 12 月，斯坦福大学通过卖掉那些股票获得了 3.36 亿美元的巨额收益，成为美国高校因支持技术研发而获得的有史以来最巨额的收益之一[注七] 。
谷歌在短短数年间就横扫整个互联网，成为搜索引擎业的新一代霸主，佩奇和布林的那个排序算法无疑居功至伟，可以说，是数学成就了谷歌[补注一] 。当然，这么多年过去了，谷歌作为 IT 界研发能力最强的公司之一，它的网页排序方法早已有了巨大的改进，由当年单纯依靠 “佩奇排序” 演变为了由两百多种来自不同渠道的信息 (其中包括与网页访问量有关的统计数据) 综合而成的更加可靠的方法。而当年曾给佩奇和布林带来过启示的学术界，则反过来从谷歌的成功中借鉴了经验，如今一些学术机构对论文影响因子 (impact factor) 的计算已采用了类似 “佩奇排序” 的算法。
在本文的最后，还有一件事情在这里提一下，那就是与佩奇和布林研究排序算法几乎同时，有另外几人也相互独立地沿着类似的思路从事着研究[注八] 。他们中有一位是当时在美国新泽西州工作的中国人，他的算法后来也成就了一家公司——一家中国公司。此人的名字叫做李彦宏 (Robin Li)，他所成就的那家公司就是百度。这些新公司的发展极好地印证了培根 (Francis Bacon) 的一句名言：知识就是力量。
注释
马尔可夫过程，也称为马尔可夫链 (Markov chain)，是一类离散随机过程，它的最大特点是每一步的概率分布都只与前一步有关。而平稳马尔可夫过程则是指转移概率与步数无关的马尔可夫过程 (体现在我们的例子中，即 H 与 n 无关) 。另外要说明的是，本文在表述上不同于佩奇和布林的原始论文，后者并未使用诸如 “马尔可夫过程” 或 “马尔可夫链” 那样的术语，也并未直接运用这一领域内的定理。