第五百三十三章 Marino-Vafa公式 (2 / 2)
        上述公式的求解是简单得不能再简单的事情，即：pn=Hnp0

        其中p0为虚拟读者初次浏览时访问各网页的几率分布(在佩奇和布林的原始论文中，这一几率分布被假定为是均匀分布)。

        如前所述，佩奇和布林是用虚拟用户在经过很长(理论上为无穷长)时间的漫游后访问各网页的几率分布，即limn→∞pn，来确定网页排序的。这个定义要想管用，显然要解决三个问题：

        1.极限limn→∞pn是否存在？

        2.如果极限存在，它是否与p0的选取无关？

        3.如果极限存在，并且与p0的选取无关，它作为网页排序的依据是否真的合理？

        如果这三个问题的答案都是肯定的，那么网页排序问题就算解决了。反之，哪怕只有一个问题的答案是否定的，网页排序问题也就不能算是得到满意的解决。那么实际答案如何呢？很遗憾，是后一种，而且是其中最糟糕的情形，即三个问题的答案全都是否定的。这可以由一些简单的例子看出。比方说，在只包含两个相互链接网页的迷你型互联网上，如果p0=(1，0)T，极限就不存在(因为几率分布将在(1，0)T和(0，1)T之间无穷振荡)。而存在几个互不连通(即互不链接)区域的互联网则会使极限——即便存在——与p0的选取有关(因为把p0选在不同区域内显然会导致不同极限)。至于极限存在，并且与p0的选取无关时它作为网页排序的依据是否真的合理的问题，虽然不是数学问题，答案却也是否定的，因为任何一个“悬挂网页”都能象黑洞一样，把其它网页的几率“吸收”到自己身上(因为虚拟用户一旦进入那样的网页，就会由于没有对外链接而永远停留在那里)，这显然是不合理的。这种不合理效应是如此显著，以至于在一个连通性良好的互联网上，哪怕只有一个“悬挂网页”，也足以使整个互联网的网页排序失效，可谓是“一粒老鼠屎坏了一锅粥”。

        为了解决这些问题，佩奇和布林对虚拟用户的行为进行了修正。首先，他们意识到无论真实用户还是虚拟用户，当他们访问到“悬挂网页”时，都不可能也不应该“在一棵树上吊死”，而是会自行访问其它网页。对于真实用户来说，自行访问的网页显然与各人的兴趣有关，但对于在平均意义上代表真实用户的虚拟用户来说，佩奇和布林假定它将会在整个互联网上随机选取一个网页进行访问。用数学语言来说，这相当于是把H的列向量中所有的零向量都换成e/N(其中e是所有分量都为1的列向量，N为互联网上的网页总数)。如果我们引进一个描述“悬挂网页”的指标向量(indicatorvector)a，它的第i个分量的取值视Wi是否为“悬挂网页”而定，如果是“悬挂网页”，取值为1，否则为零，并用S表示修正后的矩阵，则：S=H+aeT/N

        显然，这样定义的S矩阵的每一列的矩阵元之和都是1，从而是一个不折不扣的随机矩阵。这一修正因此而被称为随机性修正(stochasticityadjustment)。这一修正相当于剔除了“悬挂网页”，从而可以给上述第三个问题带来肯定回答(当然，这一回答没有绝对标准，可以不断改进)。不过，这一修正解决不了前两个问题。为了解决那两个问题，佩奇和布林引进了第二个修正。他们假定，虚拟用户虽然是虚拟的，但多少也有一些“性格”，不会完全死板地只访问当前网页所提供的链接。具体地说，他们假定虚拟用户在每一步都有一个小于1的几率α访问当前网页所提供的链接，同时却也有一个几率1-α不受那些链接所限，随机访问互联网上的任何一个网站。用数学语言来说(请读者自行证明)，这相当于是把上述S矩阵变成了一个新的矩阵G：G=αS+(1-α)eeT/N

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

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

        这个算法能给上述问题提供肯定答案吗？是的，它能。因为随机过程理论中有一个所谓的马尔可夫链基本定理(FualTheoremofMarkovs)，它表明在一个马尔可夫过程中，如果转移矩阵是素矩阵，那么上述前两个问题的答案就是肯定的。而随机性修正已经解决了上述第三个问题，因此所有问题就都解决了。如果我们用p表示pn的极限，则p给出的就是整个互联网的网页排序——它的每一个分量就是相应网页的访问几率，几率越大，排序就越靠前。

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

        细心的读者可能注意到了，我们还遗漏了一样东西，那就是谷歌矩阵中描述虚拟用户“性格”的那个α参数。那个参数的数值是多少呢？从理论上讲，它应该来自于对真实用户平均行为的分析，不过实际上另有一个因素对它的选取产生了很大影响，那就是Gnp0收敛于p的快慢程度。由于G是一个N×N矩阵，而N为互联网上——确切地说是被谷歌所收录的——网页的总数，在谷歌成立之初为几千万，目前为几百亿，是一个极其巨大的数字。因此G是一个超大型矩阵，甚至很可能是人类有史以来处理过的最庞大的矩阵。对于这样的矩阵，Gnp0收敛速度的快慢是关系到算法是否实用的重要因素，而这个因素恰恰与α有关。可以证明，α越小，Gnp0的收敛速度就越快。但α也不能太小，因为太小的话，“佩奇排序”中最精华的部分，即以网页间的彼此链接为基础的排序思路就被弱化了(因为这部分的贡献正比于α)，这显然是得不偿失的。因此，在α的选取上有很多折衷的考虑要做，佩奇和布林最终选择的数值是α=0.85。

        以上就是谷歌背后最重要的数学奥秘。与以往那种凭借关键词出现次数所作的排序不同，这种由所有网页的相互链接所确定的排序是不那么容易做假的，因为做假者再是把自己的网页吹得天花乱坠，如果没有真正吸引人的内容，别人不链接它，一切就还是枉然[注六]。而且“佩奇排序”还有一个重要特点，那就是它只与互联网的结构有关，而与用户具体搜索的东西无关。这意味着排序计算可以单独进行，而无需在用户键入搜索指令后才临时进行。谷歌搜索的速度之所以快捷，在很大程度上得益于此。

        谷歌成立之初跟其它一些“发迹于地下室”(one-man-in-basement)的IT公司一样寒酸：雇员只有一位(两位老板不算)，工作场所则是一位朋友的车库。但它出类拔萃的排序算法很快为它赢得了声誉。公司成立仅仅三个月，《PCMagzine》杂志就把谷歌列为了年度最佳搜索引擎。2001年，佩奇为“佩奇排序”申请到了专利，专利的发明人为佩奇，拥有者则是他和布林的母校斯坦福大学。2004年8月，谷歌成为了一家初始市值约17亿美元的上市公司。不仅公司高管在一夜间成为了亿万富翁，就连当初给过他们几十美元“赞助费”的某些同事和朋友也得到了足够终身养老所用的股票回报。作为公司摇篮的斯坦福大学则因拥有“佩奇排序”的专利而获得了180万股谷歌股票。2005年12月，斯坦福大学通过卖掉那些股票获得了3.36亿美元的巨额收益，成为美国高校因支持技术研发而获得的有史以来最巨额的收益之一。

        谷歌在短短数年间就横扫整个互联网，成为搜索引擎业的新一代霸主，佩奇和布林的那个排序算法无疑居功至伟，可以说，是数学成就了谷歌。当然，这么多年过去了，谷歌作为IT界研发能力最强的公司之一，它的网页排序方法早已有了巨大的改进，由当年单纯依靠“佩奇排序”演变为了由两百多种来自不同渠道的信息(其中包括与网页访问量有关的统计数据)综合而成的更加可靠的方法。而当年曾给佩奇和布林带来过启示的学术界，则反过来从谷歌的成功中借鉴了经验，如今一些学术机构对论文影响因子(impactfactor)的计算已采用了类似“佩奇排序”的算法。

        在本文的最后，还有一件事情在这里提一下，那就是与佩奇和布林研究排序算法几乎同时，有另外几人也相互独立地沿着类似的思路从事着研究。他们中有一位是当时在美国新泽西州工作的中国人，他的算法后来也成就了一家公司——一家中国公司。此人的名字叫做李彦宏(RobinLi)，他所成就的那家公司就是百度。这些新公司的发展极好地印证了培根(FrancisBa)的一句名言：知识就是力量。

        【本章阅读完毕，更多请搜索墨缘文学网;http://wap.mywenxue.org 阅读更多精彩小说】

更多完整内容阅读登陆

《墨缘文学网，https://wap.mywenxue.org》