谷歌搜索引擎背后的数学

2004 年 8 月， 谷歌成为了一家初始市值约 17 亿美元的上市公司。 不仅公司高管在一夜间成为了亿万富翁， 就连当初给过他们几十美元 “赞助费” 的某些同事和朋友也得到了足够终身养老所用的股票回报。 作为公司摇篮的斯坦福大学则因拥有 “佩奇排序” 的专利而获得了 180 万股谷歌股票。

2005 年 12 月， 斯坦福大学通过卖掉那些股票获得了 3.36 亿美元的巨额收益， 成为美国高校因支持技术研发而获得的有史以来最巨额的收益之一。

谷歌在短短数年间就横扫整个互联网， 成为搜索引擎业的新一代霸主， 佩奇和布林的那个排序算法无疑居功至伟， 可以说， 是数学成就了谷歌。

当然， 这么多年过去了， 谷歌作为 IT 界研发能力最强的公司之一， 它的网页排序方法早已有了巨大的改进， 由当年单纯依靠 “佩奇排序” 演变为了由 200 多种来自不同渠道的信息——其中包括与网页访问量有关的统计数据——综合而成的更加可靠的方法。

而当年曾给佩奇和布林带来过启示的学术界， 则反过来从谷歌的成功中借鉴了经验， 如今一些学术机构对论文影响因子 (impact factor) 的计算已采用了类似 “佩奇排序” 的算法。

在本文的最后， 还有一件事情在这里提一下， 那就是与佩奇和布林研究排序算法几乎同时， 有另外几人也相互独立地沿着类似的思路从事着研究。

他们中有一位是当时在美国新泽西州工作的中国人， 他的算法后来也成就了一家公司——一家中国公司。 此人的名字叫做李彦宏 (Robin Li)， 他所成就的那家公司就是百度。 这些新公司的发展极好地印证了培根 (Francis Bacon) 的一句名言： 知识就是力量。

注释

1. 马尔可夫过程， 也称为马尔可夫链 (Markov chain)， 是一类离散随机过程， 它的最大特点是每一步的转移概率分布都只与前一步有关。 而平稳马尔可夫过程则是指转移概率分布与步数无关的马尔可夫过程 (体现在我们的例子中， 即 H 与 n 无关)。 另外要说明的是， 本文在表述上不同于佩奇和布林的原始论文， 后者并未使用诸如 “马尔可夫过程” 或 “马尔可夫链” 那样的术语， 也并未直接运用这一领域内的数学定理。
2. 在更细致的分类中， 这种每一列的矩阵元之和都为 1 的随机矩阵称为左随机矩阵 (left stochastic matrix)， 以区别于每一行的矩阵元之和都等于 1 的所谓右随机矩阵 (right stochastic matrix)。 这两者在应用上基本是等价的， 区别往往只在于约定。
3. 这种几乎满足随机矩阵条件， 但有些列 (或行) 的矩阵元之和小于 1 的矩阵也有一个名称， 叫做亚随机矩阵 (substochastic matrix)。
4. 确切地说， 这种所有矩阵元都为正的矩阵不仅是素矩阵， 而且还是所谓的正矩阵 (positive matrix)。 这两者的区别是： 正矩阵要求所有矩阵元都为正， 而素矩阵只要求自己的某个正整数次幂为正矩阵。
5. 读者们想必看出来了， p 其实是矩阵 G 的本征值为 1 的本征向量， 而利用虚拟用户确定网页排序的思路其实是在用迭代法解决上述本征值问题。 在数学上可以证明， 上述本征向量是唯一的， 而且 G 的其它本征值 λ 全都满足 |λ|<1 (更准确地说， 是 |λ|≤α ——这也正是下文即将提到的 Gⁿp₀ 的收敛速度与 α 有关的原因)。
6. 当然， 这绝不意味着在网页排序上已不可能再做假。 相反， 这种做假在互联网上依然比比皆是， 比如许多广告或垃圾网页制造者用自动程序到各大论坛发贴， 建立对自己网页的链接， 以提高排序， 就是一种常见的做假手法。 为了遏制做假， 谷歌采取了很多技术手段， 并对有些做假网站采取了严厉的惩罚措施。 这种惩罚 (有时是误罚) 对于某些靠互联网吃饭的公司有毁灭性的打击力。
7. 从投资角度讲， 斯坦福大学显然是过早卖掉了股票， 否则获利将更为丰厚。 不过， 这正是美国名校的一个可贵之处， 它们虽擅长从支持技术研发中获利， 却并不唯利是图。 它们有自己的原则， 那就是不能让商业利益干扰学术研究。 为此， 它们通常不愿长时间持有特定公司的股票， 以免在无形中干扰与该公司存在竞争关系的学术研究的开展。
8. 那些研究与 “佩奇排序” 的类似仅仅在于大方向 (即都利用互联网的链接结构来决定网页排序)， 而非具体算法类似。

补注：

有些读者对 “是数学成就了谷歌” 这一说法不以为然， 认为是佩奇和布林的商业才能， 或将数学与商业结合起来的才能成就了谷歌。 这是一个见仁见智的问题， 看法不同不足为奇。 我之所以认为是数学成就了谷歌， 是因为谷歌当年胜过其它搜索引擎的地方只有算法。 除算法外， 佩奇和布林当年并无其它胜过竞争对手的手段， 包括商业手段。

如果让他们去当其它几家搜索引擎公司的老总， 用那几家公司的算法， 他们是不可能脱颖而出的； 而反过来， 如果让其它几家搜索引擎公司的老总来管理谷歌， 用谷歌的算法， 我相信谷歌依然能超越对手。 因此， 虽然谷歌后来确实用过不少出色的商业手段 (任何一家那样巨型的公司都必然有商业手段上的成功之处)， 而当年那个算法在今天的谷歌——如正文所述——则早已被更复杂的算法所取代， 但我认为谷歌制胜的根基和根源在于那个算法， 而非商业手段， 因此我说 “是数学成就了谷歌”。

注：相关网站建设技巧阅读请移步到建站教程频道。

（编辑：应用网_镇江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!