維拉尼演講中的高爾頓板和網(wǎng)頁排序

羅藝靈 劉曉曼 保繼光

(北京師范大學數(shù)學科學學院 100875)

維拉尼(Cedric Villani，1973—)是法國數(shù)學家，玻爾茲曼方程的非線性阻尼及收斂于平衡態(tài)的證明為他迎來了2010年的菲爾茲獎(Fields Medal).2016年，維拉尼在TED大會*TED是technology，entertainment，design的英文首字母縮寫，譯為技術、娛樂、設計.TED是美國的一家私有非盈利機構(gòu)，他們以組織了TED大會而聞名.在TED大會上，各行各業(yè)的人都可能站上演講臺，向大眾傳播他們的想法和創(chuàng)意.演講，向大眾講述了他對數(shù)學的理解，解釋了“數(shù)學為何如此性感(What’s so sexy about math?)”.

為了向觀眾展示數(shù)學隱藏在我們的整個物質(zhì)世界中，維拉尼介紹了幾個奇妙又貼近生活的數(shù)學例子，讓非數(shù)學工作者也能簡單地接受和理解.而作為數(shù)學學習者或數(shù)學工作者，我們不妨稍微深入地探索其中的高爾頓板和網(wǎng)頁排序背后的數(shù)學知識.

1 高爾頓板

高爾頓(Francis Galton，1822—1911)是英國科學家、生物統(tǒng)計學家.他是達爾文(Charles Robert Darwin，1809—1882)的表弟，深受達爾文進化論的影響.為了研究遺傳現(xiàn)象，他設計了一個釘板，即高爾頓板，利用二項分布的極限是正態(tài)分布這一原理，模擬正態(tài)分布的性質(zhì).

圖1

高爾頓板形狀如圖1，圖中的每一個黑點代表的是一顆釘子，每兩顆相鄰釘子間的距離相等.從入口處放下一顆小玻璃球，它經(jīng)過多層釘子的空隙，最終落在底部的某個空格中.

考察一個小球落入每個底部空格的概率.觀察釘板可以發(fā)現(xiàn)，第n行有n+2顆釘子，n+1個空隙，把每一行的空隙從0開始進行編號，第k行即為0，1，…，k個空.

可見，一個小球從高爾頓板下落，落入第k個空的概率是滿足二項分布的.因此，足夠多的小球通過高爾頓板(行數(shù)較多)下落后，堆積而形成的球堆輪廓近似于正態(tài)分布的密度函數(shù)曲線——高斯曲線.它的發(fā)現(xiàn)和發(fā)展與著名的德國數(shù)學家高斯(Johann Carl Friedrich Gauss，1777—1855)有著密切的聯(lián)系.

英國物理學家、數(shù)學家麥克斯韋(James Clerk Maxwell，1831—1879)基于空間幾何的不變性和幾個物理上的結(jié)論，在1860年發(fā)表了論文《氣體分子動力學的說明》[1]，導出了氣體分子速率分布.它正是一個正態(tài)分布.

在介紹麥克斯韋的推導前，先進行符號說明：容器內(nèi)粒子總數(shù)為N；建立空間直角坐標系，將粒子速度v分解到三個坐標軸方向，速度分量分別用符號x、y、z表示；dNx0表示速度分量x處于x0到x0+dx小區(qū)間的粒子數(shù)目；g(x)代表粒子在分量x方向上的速度分布函數(shù)，從而g(x)dx就表示速度分量處于任意值x附近長度為dx的小區(qū)間內(nèi)的概率.

根據(jù)各符號代表的含義，以下式子成立：

由于已將速度分解到了三個正交方向上，其任一方向上速度分量的存在和大小不會對其他方向分量的存在和大小產(chǎn)生影響，故三個正交方向上的速度分布是彼此獨立的.而三個正交方向在空間上是地位等價的，它們具有相同的速度分布函數(shù).因此，對于另外兩個分量，也有類似的公式成立：

從而，粒子速度v的三個分量處于x到x+dx，y到y(tǒng)+dy，z到z+dz區(qū)間的概率即是三個獨立事件同時發(fā)生的概率(其中F表示粒子總體速度分布函數(shù)，顯然是x、y、z的函數(shù))：

從物理上看，當容器內(nèi)系統(tǒng)處于平衡態(tài)時，容器內(nèi)各處粒子數(shù)密度相同，粒子朝著任何方向運動的概率相等.因此F與粒子速度方向無關，僅是速度大小|v|的函數(shù)，從而有等式

(1)

通過求解等式，就可以得知氣體分子的速率分布函數(shù)了.

首先注意到，若令y=z=0，則有F(|x|)=g(x)g(0)2.x的正負實際上代表著方向，而前文已經(jīng)說明F與方向無關，即是說F是一個偶函數(shù)，F(xiàn)(|x|)=F(x)=g(x)g(0)2.

對等式(1)兩邊取對數(shù)，則可知：

代入等式

經(jīng)過簡單化簡，便可知：

=lng(x)+lng(y)+lng(z)，

=lng(x)+lng(y)+lng(z).

等號兩邊對x求導，即：

從而，

由于粒子速度從-∞到+∞出現(xiàn)的概率應為1，g(x)應當滿足：

F(v)=F(|v|)=g(x)g(y)g(z)

麥克斯韋在推導的過程中僅用到“所有可能情況的總概率為1”這一個概率知識，借助對氣體分子運動的假設和簡單空間幾何知識，就推導出了氣體分子速率分布，而其分布函數(shù)恰與正態(tài)分布密度函數(shù)具有相同的形式.正態(tài)分布就像一雙自然背后的無形之手，掌控著萬物的規(guī)律.維拉尼用這個貼近每個人的生活的例子，說明了數(shù)學的強大價值.

2 網(wǎng)頁排序

維拉尼在演講中還提到，數(shù)學幫助我們超越人類的直覺.他列舉了計算機搜索作為一個例子，并以深入淺出的方式說明了其中數(shù)學扮演的角色，但數(shù)學對網(wǎng)頁搜索的幫助并不簡單.

互聯(lián)網(wǎng)中有上百億個網(wǎng)頁，使得網(wǎng)頁搜索結(jié)果的重復度很高，這給網(wǎng)頁搜索帶來了極大的挑戰(zhàn).為了應對這一挑戰(zhàn)只能對搜索結(jié)果進行排序，把用戶最有可能需要的網(wǎng)頁排在最前面.但問題是：網(wǎng)頁的水平千差萬別，用戶的喜好又不相同，搜索引擎怎么知道哪些網(wǎng)頁是用戶最可能需要的呢？

在Google主導互聯(lián)網(wǎng)搜索之前，大多數(shù)搜索引擎采用被搜索詞語在網(wǎng)頁中出現(xiàn)的頻數(shù)來決定排序.這是有一定道理的，因為用戶搜索一個詞語，通常表明對該詞語感興趣，既然如此，那該詞語在網(wǎng)頁中出現(xiàn)次數(shù)越多，就越有可能表示該網(wǎng)頁是用戶所需要的.可是按照這種方法，任何一個翻來覆去倒騰關鍵詞的網(wǎng)頁，無論其含金量多低，都會被排在前面.

面對上述問題，1996年初，Google的創(chuàng)始人，當時還是美國斯坦福大學研究生的佩奇(Lawrence Edward Page，1973—)和布林(Sergey Mikhaylovich Brin，1973—)開始對網(wǎng)頁排序問題進行研究.在他們看來，網(wǎng)頁的排序不能靠每個網(wǎng)頁自己來標榜.他們想到了學術界評判學術論文重要性的通用方法，看論文被引用的次數(shù)，放在互聯(lián)網(wǎng)上與論文引用類似的就是網(wǎng)頁的鏈接.那么通過研究網(wǎng)頁間的相互鏈接來確定排序就是PageRank網(wǎng)頁排序的思路，網(wǎng)頁的PageRank值越大其排序越靠前.具體說就是一個網(wǎng)頁被其他網(wǎng)頁鏈接得越多，它的排序就應該越靠前.不僅如此，一個網(wǎng)頁越是被排序靠前的網(wǎng)頁所鏈接，它的排序也應該越靠前.

在正式介紹PageRank排序方法前，首先闡述兩個相關的概念：

1)網(wǎng)頁i的入鏈：那些指向網(wǎng)頁i的來自于其他網(wǎng)頁的超鏈接，通常不包括來自于同一網(wǎng)站內(nèi)網(wǎng)頁的超鏈接.

2)網(wǎng)頁i的出鏈：那些從網(wǎng)頁i指向其他網(wǎng)頁的超鏈接，通常不包括指向同一站點內(nèi)網(wǎng)頁的超鏈接.

基于上面PageRank網(wǎng)頁排序的思路，我們可以知道：

從一個網(wǎng)頁指向另一個網(wǎng)頁的超鏈接是PageRank值的隱含式傳遞，網(wǎng)頁的PageRank值是由指向它的所有網(wǎng)頁所傳遞過來的PageRank值總和決定的.這樣，網(wǎng)頁i的入鏈越多，它的PageRank值可能就越高.此外，一個網(wǎng)頁指向多個其他網(wǎng)頁，那么它的PageRank值就會被它指向的多個網(wǎng)頁分享.也就是說，即使網(wǎng)頁i被一個PageRank值很高的網(wǎng)頁j所指向，如果網(wǎng)頁j的出鏈非常多，網(wǎng)頁i從網(wǎng)頁j得到的PageRank值可能因被稀釋也很小.

現(xiàn)在，我們把互聯(lián)網(wǎng)抽象成一個有向圖G=(V,E)，其中V是圖的節(jié)點集合(一個節(jié)點對應一個網(wǎng)頁)，E是圖的有向邊集合(有向邊對應超鏈接).設互聯(lián)網(wǎng)的網(wǎng)頁總數(shù)為n(即n=|V|)，上述排序規(guī)則可以用數(shù)學式子表達：

(2)

其中p(i)表示網(wǎng)頁i的PageRank值，Oj是網(wǎng)頁j出鏈的數(shù)量，(j,i)∈E表示存在網(wǎng)頁j指向網(wǎng)頁i的超鏈接.

若用列向量

P=(p(1)，p(2)，…，p(n))T

表示n個網(wǎng)頁的PageRank值，再利用矩陣A表示網(wǎng)頁之間的鏈接關系，并按如下規(guī)則為其元素賦值：

例如，下面的網(wǎng)絡鏈接結(jié)構(gòu)圖：

圖2

其對應的連接關系矩陣

這樣，網(wǎng)頁排序的表達式(2)就可以用含n個未知量的線性方程組表達

P=ATP.

(3)

從而要想得到網(wǎng)頁排序結(jié)果，即在已知矩陣A的條件下，求解向量P，如果從線性代數(shù)的角度考慮，這是一個齊次線性方程組，要不只有零解，要不有無窮解.但是由于數(shù)據(jù)的海量，這給求解過程帶來了很多麻煩.

觀察方程組(3)，可以發(fā)現(xiàn)，如果定義Pn是經(jīng)過第n次迭代得到的值，給定初值P0，則可以把方程組(3)形式簡化如下：

Pn+1=ATPn，n=0,1,2,…(其中P0是給定的)

(4)

b)如果極限存在，是否和P0的選取無關.

c)如果極限存在并且和P0選取無關，它作為網(wǎng)頁排序的依據(jù)是否合理？

假設上網(wǎng)瀏覽下一個頁面這一過程與過去瀏覽的頁面沒有關系，而僅僅依賴于當前所處的頁面，那么上網(wǎng)搜索這一過程可以看作是一個有限狀態(tài)、離散時間的馬氏過程，可用馬爾科夫鏈進行建模，這時P*就可以看成馬爾科夫鏈的一個穩(wěn)定狀態(tài)，A可以表示狀態(tài)轉(zhuǎn)移矩陣，這樣就可以轉(zhuǎn)化成馬爾科夫鏈的遍歷性和極限分布問題[2].

根據(jù)馬氏鏈的遍歷性和平穩(wěn)分布相關定理，若矩陣A是正的、隨機矩陣，上面討論的前兩個問題的答案是肯定的.正矩陣即矩陣的每個元素都是正數(shù)，隨機矩陣則要求矩陣的每一行元素和都為1，且元素都大于等于零.綜合兩者我們可以知道，要想使得我們研究的問題是肯定的，矩陣A必須滿足每個元素是正數(shù)，并且每行元素和為1，而上面例子中的網(wǎng)頁鏈接結(jié)構(gòu)圖的矩陣就不滿足(第5行全部為0)，所以要對矩陣A進行基于現(xiàn)實意義的修正.

第一步，將矩陣A修正為隨機矩陣.互聯(lián)網(wǎng)中那些沒有出鏈的網(wǎng)頁，我們稱其為懸掛網(wǎng)頁，如上面例子中的網(wǎng)頁5.當互聯(lián)網(wǎng)用戶訪問到懸掛網(wǎng)頁時，不可能在這個網(wǎng)頁上停止不前，而會自行訪問其他網(wǎng)頁.對于單個用戶來說，自行訪問的網(wǎng)頁顯然與個人的興趣有關，但是對于無數(shù)的互聯(lián)網(wǎng)用戶整體來說，自行訪問哪個網(wǎng)頁完全是隨機的.

第二步，將隨機矩陣S修正為正的隨機矩陣.互聯(lián)網(wǎng)的用戶是活生生的人，他們多少都有自己的“性格”，不會完全受當前網(wǎng)頁所限，死板地只是訪問提供的鏈接.假定虛擬用戶在每一步都有一個小于1的概率a訪問當前網(wǎng)頁所提供的鏈接，同時卻也有1-a的概率不受那些鏈接的影響，隨機地訪問其他的任何網(wǎng)頁，由此，矩陣S應當修改為

其中0

n=0,1,2,…，其中P0任意給定.

最后再用迭代求解的算法就可以求出解P*，從而實現(xiàn)排序.

然而上面的一切分析都要通過計算機程序進行實現(xiàn)，GTP0的收斂速度是關系算法是否實用的重要因素，其中a越小，收斂速度越快，但是如果a太小，PageRank網(wǎng)頁排序的現(xiàn)實意義將被弱化，佩奇和布林綜合實驗，考慮了一系列因素后，將a取為0.85.

當然，伴隨著科學技術的不斷進步，PageRank網(wǎng)頁排序算法也得到了不斷地發(fā)展.隨著時間的推進，互聯(lián)網(wǎng)成為人們生活中不可或缺的工具，網(wǎng)頁的數(shù)量也在空前的增加，這就帶來一個問題，新的網(wǎng)頁由于時間問題得不到用戶的關注，沒有太多的入鏈，即使網(wǎng)頁的質(zhì)量再高PageRank值反而很低，而那些舊網(wǎng)頁由于積累了很多的入鏈，PageRank值很高，即使內(nèi)容過時不被用戶需要卻能排在前面.Timed-PageRank算法為此應運而生.它在PageRank算法基礎上增加了一個時間維度，他的思想仍是馬氏鏈，不同之處在于Timed-PageRank不再適用常量阻尼因子，而是引入一個隨時間遞減的函數(shù)來“懲罰”那些過時的網(wǎng)頁，使得那些載有新信息高質(zhì)量的新頁面不至于由于入鏈少而排在后面.除此之外，在前面的敘述中，我們知道PageRank值由一個網(wǎng)頁向另一個網(wǎng)頁傳遞時，其值是均勻分配給所有的出鏈，基于用戶反饋的PageRank算法則把從網(wǎng)頁i到網(wǎng)頁j傳遞的PageRank值根據(jù)用戶在網(wǎng)頁上停留的時間、頁面篇幅、用戶正常的閱讀速度等進行加權(quán).這樣就根據(jù)用戶的體驗對出鏈所到達的網(wǎng)頁質(zhì)量進行了加權(quán)，更能進一步的使得用戶最需要的網(wǎng)頁排在前面，增加了網(wǎng)頁排序的可靠性.

作為當今的數(shù)學大師之一，維拉尼對數(shù)學的理解，對數(shù)學價值的認識超過了許多人.數(shù)學不僅能改善人們的生活，還曾改變?nèi)祟惖氖澜缬^；數(shù)學不僅能幫助人們認識世界，還能協(xié)助人們超越人類的直覺，探索未知.數(shù)學兼具著美、實用性和無限的商機，它值得所有人去了解和欣賞.

最后，附上維拉尼演講的網(wǎng)址，供感興趣的讀者欣賞：https://www.ted.com/talks/cedric_villani_what_s_so_sexy_about_math.