谷歌搜索引擎背后的数学

用数学语言来说， 这相当于是把 H 的列向量中所有的零向量都换成 e/N (其中 e 是所有分量都为 1 的列向量， N 为互联网上的网页总数)。 如果我们引进一个描述 “悬挂网页” 的指标向量 (indicator vector) a， 它的第 i 个分量的取值视 Wi 是否为 “悬挂网页” 而定——如果是 “悬挂网页”， 取值为 1， 否则为 0——并用 S 表示修正后的矩阵， 则：

S = H + eaT/N

显然， 这样定义的 S 矩阵的每一列的矩阵元之和都是 1， 从而是一个不折不扣的随机矩阵。 这一修正因此而被称为随机性修正 (stochasticity adjustment)。 这一修正相当于剔除了 “悬挂网页”， 从而可以给上述第三个问题带来肯定回答 (当然， 这一回答没有绝对标准， 可以不断改进)。 不过， 这一修正解决不了前两个问题。

为了解决那两个问题， 佩奇和布林引进了第二个修正。 他们假定， 虚拟用户虽然是虚拟的， 但多少也有一些 “性格”， 不会完全受当前网页所限， 死板地只访问其所提供的链接。

具体地说， 他们假定虚拟用户在每一步都有一个小于 1 的几率 α 访问当前网页所提供的链接， 同时却也有一个几率 1-α 不受那些链接所限， 随机访问互联网上的任何一个网站。 用数学语言来说 (请读者自行证明)， 这相当于是把上述 S 矩阵变成了一个新的矩阵 G：

G = αS + (1-α)eeT/N

这个矩阵不仅是一个随机矩阵， 而且由于第二项的加盟， 它有了一个新的特点， 即所有矩阵元都为正 (请读者想一想， 这一特点的 “物理意义” 是什么？)， 这样的矩阵是所谓的素矩阵 (primitive matrix)。 这一修正因此而被称为素性修正 (primitivity adjustment)。

经过这两类修正， 网页排序的计算方法就变成了：

pn = Gnp0

这个算法能给上述问题提供肯定答案吗？ 是的， 它能。 因为随机过程理论中有一个所谓的马尔可夫链基本定理 (fundamental theorem of Markov chains)， 它表明在一个马尔可夫过程中， 如果转移矩阵是素矩阵， 那么上述前两个问题的答案就是肯定的。

而随机性修正已经解决了上述第三个问题， 因此所有问题就都解决了。 如果我们用 p 表示 pn 的极限[注五]， 则 p 给出的就是整个互联网的网页排序——它的每一个分量就是相应网页的访问几率， 几率越大， 排序就越靠前。

这样， 佩奇和布林就找到了一个不仅含义合理， 而且数学上严谨的网页排序算法， 他们把这个算法称为 PageRank， 不过要注意的是， 虽然这个名称的直译恰好是 “网页排序”， 但它实际上指的是 “佩奇排序”， 因为其中的 “Page” 不是指网页， 而是佩奇的名字。 这个算法就是谷歌排序的数学基础， 而其中的矩阵 G 则被称为谷歌矩阵 (Google matrix)。

细心的读者可能注意到了， 我们还遗漏了一样东西， 那就是谷歌矩阵中描述虚拟用户 “性格” 的那个 α 参数。 那个参数的数值是多少呢？ 从理论上讲， 它应该来自于对真实用户平均行为的分析， 不过实际上另有一个因素对它的选取产生了很大影响， 那就是 Gnp0 收敛于 p 的快慢程度。 由于 G 是一个 N×N 矩阵， 而 N 为互联网上——确切地说是被谷歌所收录的——网页的总数， 在谷歌成立之初为几千万， 目前为几百亿 (并且还在持续增加)， 是一个极其巨大的数字。

因此 G 是一个超大型矩阵， 甚至很可能是人类有史以来处理过的最庞大的矩阵。 对于这样的矩阵， Gnp0 收敛速度的快慢是关系到算法是否实用的重要因素， 而这个因素恰恰与 α 有关。 可以证明， α 越小， Gnp0 的收敛速度就越快。 但 α 也不能太小， 因为太小的话， “佩奇排序” 中最精华的部分， 即以网页间的彼此链接为基础的排序思路就被弱化了 (因为这部分的贡献正比于 α)， 这显然是得不偿失的。 因此， 在 α 的选取上有很多折衷的考虑要做， 佩奇和布林最终选择的数值是 α = 0.85。

以上就是谷歌背后最重要的数学奥秘。 与以往那种凭借关键词出现次数所作的排序不同， 这种由所有网页的相互链接所确定的排序是不那么容易做假的， 因为做假者再是把自己的网页吹得天花乱坠， 如果没有真正吸引人的内容， 别人不链接它， 一切就还是枉然。

而且 “佩奇排序” 还有一个重要特点， 那就是它只与互联网的结构有关， 而与用户具体搜索的东西无关。 这意味着排序计算可以单独进行， 而无需在用户键入搜索指令后才临时进行。 谷歌搜索的速度之所以快捷， 在很大程度上得益于此。

四. 结语

谷歌公司创始人佩奇 (左) 和布林 (右)

在本文的最后， 我们顺便介绍一点谷歌公司的历史。 佩奇和布林对谷歌算法的研究由于需要收集和分析大量网页间的相互链接， 从而离不开硬件支持。 为此， 早在研究阶段， 他们就四处奔走， 为自己的研究筹集资金和硬件。 1998 年 9 月， 他们为自己的试验系统注册了公司——即如今大名鼎鼎的谷歌公司。 但这些行为虽然近乎于创业， 他们两人当时却并无长期从商的兴趣。 1999 年， 当他们觉得打理公司干扰了自己的研究时， 甚至萌生了卖掉公司的想法。

他们的开价是 100 万美元。

与谷歌在短短几年之后的惊人身价相比， 那简直就是 “跳楼大甩卖”。 可惜当时却无人识货。 佩奇和布林在硅谷 “叫卖” 了一圈， 连一个买家都没找到。 被他们找过的公司包括了当时搜索业巨头之一的 Excite (该公司后来想必连肠子都悔青了)。 为了不让自己的心血荒废， 佩奇和布林只得将公司继续办了下去， 一直办到今天， 这就是谷歌的 “发家史”。

谷歌成立之初跟其它一些 “发迹于地下室” (one-man-in-basement) 的 IT 公司一样寒酸： 雇员只有一位 (两位老板不算)， 工作场所则是一位朋友的车库。 但它出类拔萃的排序算法很快为它赢得了声誉。 公司成立仅仅 3 个月，《PC Magzine》杂志就把谷歌列为了年度最佳搜索引擎。

2001 年， 佩奇为 “佩奇排序” 申请到了专利， 专利的发明人为佩奇， 拥有者则是他和布林的母校斯坦福大学。

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

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