羅藝靈 劉曉曼 保繼光

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

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

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

1 高爾頓板

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

圖1

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

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

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

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

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

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

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

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

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

(1)

通過求解等式，就可以得知?dú)怏w分子的速率分布函數(shù)了.

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

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

代入等式

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

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

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

等號(hào)兩邊對(duì)x求導(dǎo)，即：

從而，

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

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

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

2 網(wǎng)頁排序

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

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

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

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

在正式介紹PageRank排序方法前，首先闡述兩個(gè)相關(guān)的概念：

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

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

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

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

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

(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個(gè)網(wǎng)頁的PageRank值，再利用矩陣A表示網(wǎng)頁之間的鏈接關(guān)系，并按如下規(guī)則為其元素賦值：

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

圖2

其對(duì)應(yīng)的連接關(guān)系矩陣

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

P=ATP.

(3)

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

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

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

(4)

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

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

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

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

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

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

其中0

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

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

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

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

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

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