讓谷歌橫空出世的世界最大矩陣

圖源：pixabay

撰文 ｜丁玖 朱慧堅（廣州南方學院）

1998年9月4日，兩個25周歲的年輕小伙拉里·佩奇(Larry Page，生于1973年3月26日)和謝爾蓋·布林（Sergey Brin，生于1973年8月21日）在加利福尼亞州舊金山灣區圣馬特奧（San Mateo）縣的城市門洛帕克（Menlo Park）提交了谷歌公司的注冊文件。這個小城僅有三萬多居民，南面的近鄰是斯坦福大學，而他們正在那里攻讀計算機科學系的博士學位。

他們創辦的這家公司，四分之一個世紀后，其“谷歌搜索”成了全球訪問量最高的兩個網站之一。佩奇和布林最初將他們開辟的新搜索引擎昵稱為“背部按摩（BackRub）”，因為該系統會檢查反向鏈接來評估網站的重要性。最終，他們將名稱改為Google，然而這是對古戈爾（googol）一詞的錯誤拼寫。古戈爾是一個巨大的數字10100（1后面跟著100個零），選擇這個數字是為了表明該搜索引擎旨在提供大量信息。不過，直到今天，全世界的網頁個數還遠遠低于這個已經超過宇宙所有原子個數的大數；或許永遠也達不到。

古戈爾由美國哥倫比亞大學數學系教授愛德華·卡斯納（Edward Kasner，1878-1955）的侄子、年僅9歲的米爾頓·西羅塔（Milton Sirotta）創造，用來表示一個難以想象的大數。卡斯納在其1940年出版的《數學與想象力》一書中推廣了古戈爾的概念，它形象地展示了大數與無窮之間的尺度，想必谷歌的創始人受此啟發，給他們的搜索引擎新生兒起了這個拼錯了一個字母的名字。順便一提，卡斯納最杰出的弟子是首屆菲爾茲獎的兩名獲獎者之一、美國數學家杰西·道格拉斯（Jesse Douglas，1897-1965）。

無論佩奇還是布林，創辦公司后都沒有待在世界名校斯坦福美麗的校園，穩穩當當地堅持到最后，以獲一紙博士證書。他們最終的學位——碩士——仍然高于年長他們18歲的比爾·蓋茨（Bill Gates，1955-）；后者入學哈佛大學讀本科兩年后毅然退學，與合作伙伴開創了微軟公司，開啟了他一生的輝煌事業。佩奇和布林共同創辦的公司——谷歌——同樣也成了本世紀全世界最著名的高科技公司之一。沒有追求學位圓滿的他們三人，后來都被選為美國國家工程院院士。

佩奇和布林都有猶太血統。兩人中，年輕半歲的布林有個數學家爸爸，佩奇的父親則是計算機科學家。布林之父米哈伊·布林（MihailBrin，1947-）是個國際知名的俄羅斯純粹數學家，專長為動力系統與黎曼幾何，本科畢業于莫斯科大學，博士導師為蘇聯動力系統大家德米特里·阿諾索夫（Dmitri Anosov（1936-2014）和阿納托爾·諾克（Anatole Katok，1944-2018）。布林教授在普林斯頓大學數學系編輯的純數學國際頂尖雜志《數學年刊》上發表過三篇論文，也出版過書籍，如與他后來的馬里蘭大學同事合著的《動力系統引論》，2015年由劍橋大學出版社推出。

小布林6歲時隨全家從蘇聯移民到美國。1990年他追隨父親的腳步跨進了馬里蘭大學，不過，父親是數學系的教授，他則在數學系和計算機科學系讀本科。三年后，他以數學與計算機科學雙專業榮譽畢業生的優異成績獲得學士學位。馬里蘭大學數學系一直引以自豪的另一個本科畢業生是菲爾茲獎獲得者查爾斯·費弗曼（Charles Fefferman，1949-），他17歲就獲得數學與物理學的雙學位，于普林斯頓大學獲得數學博士后，22歲時成為芝加哥大學的正教授；他的同門博士師弟就是另一個菲爾茲獎獲得者陶澤軒（Terence Tao，1975-）。

佩奇是個土生土長的美國人，他的父親卡爾·佩奇（Carl Page Sr.，1938-1996）是筆者之一博士母校密歇根州立大學的計算機科學教授。老佩奇博士畢業于密歇根州的首席大學、也是全美最負盛名的公立大學之一密歇根大學的計算機科學系，在其職業生涯中是美國人工智能研究的先驅之一?？上迤娼淌谟⒛暝缡?，未能像布林教授那樣目睹了兒子成長為業界巨人。

小佩奇也步了父親的后塵，一腳跨進密歇根大學的校門，父子倆成為這所被譽為“美國公立大學之母”的中西部巨無霸大學的先后校友。在父母的直接影響下，兒子6歲時就對電腦產生了興趣，因為他可以“玩弄那些散落在周圍的東西”——他父母留下的第一代個人電腦。他成為“小學里第一個用文字處理器交作業的孩子”?？梢哉f他是在電腦配件的叢林中長大的，“熟能生巧”這一中文成語可以恰如其分地形容佩奇從兒童走向青年對計算機世界的癡迷程度。后來他說：“從小我就意識到自己想發明創造。所以我對科技和商業產生了興趣。大概從12歲起，我就知道自己最終會創辦一家公司?！?/p>

在密歇根州立大學所在地東蘭辛高中畢業后，從1991年到1995年，佩奇在密歇根大學讀計算機工程，以榮譽稱號獲得工程學士學位，然后進入西部學術重鎮斯坦福大學攻讀計算機科學博士學位，在他創業元年獲得碩士學位。

在尋找論文選題時，佩奇考慮探索萬維網的數學特性，將其鏈接結構理解為一個龐大的有向圖。他的導師特里·維諾格拉德（Terry Winograd，1946-)鼓勵他繼續研究這個想法。2008年谷歌20周歲，佩奇以感恩之情回憶道：“這是我收到的最好建議?！?/p>

成功實現快速高效網頁搜索的好想法，不僅得益于有深遠眼光學術導師的好建議，還需要背景類似、志同道合、互補長短的合作伙伴，這對應用科學十分奏效。在斯坦福這個布滿才華橫溢年輕學者的校園內，同在計算機科學疆場習武的布林加入到佩奇的行列，兩人結伴開始了對網頁搜索引擎的創新研究。卓有成效的共同努力導致“網頁排序（PageRank）”這個互聯網史上具有里程碑意義的新穎概念和術語的誕生。

在英文的語義下，兩個單詞的無空格組合PageRank可以有兩層含義；其一是與實施對象相關的如上翻譯“網頁排序”，其二是“佩奇排序”，理由為Page是佩奇的姓。事實上，“PageRank”這個名字是個雙關語，既指網頁排名算法，也指其開發者佩奇。該算法最初是作為一種基于鏈接流行度對搜索結果進行排序的系統而開發的。

四分之一個世紀以來，世人盡知谷歌擁有史上最成功的搜索引擎，然而有幾人了解到是什么魔法使它進入市場后迅速走紅，又有幾人通曉引導它成功的關鍵數學為何？今天是第七個國際數學日，正是每個數學愛好者甚至數學同情者可以借機接受數學普及的好日子。筆者受中國數學會的一則通知啟發，想到谷歌矩陣這個與國際人的日常生活、學習工作、職場發展都有關系的“全世界最大的矩陣”，覺得談談它或許是向國際數學日所獻的一朵艷麗之花。

由于網頁數量龐大（目前網站總數超過13億，但只有約六分之一的網站“被積極維護”。搜索引擎索引的實際網頁數量在40億至60億之間，而搜索引擎識別的網頁數量則超過130萬億），網絡信息檢索比傳統的信息檢索更具挑戰性。在網絡信息檢索研究中，每個網頁都被表示為一個超大型有向圖中的一個節點，連接這些節點的有向邊代表頁面之間的超鏈接。

這種超鏈接結構可以通過三種信息檢索方法進行探索，第一種是“超文本誘導主題搜索”，其代表性論文是J. Kleinberg于1999年在美國計算機協會雜志上發表的Authoritative Sources in a Hyperlinked Environment（超鏈接環境中的權威來源）；第二種是“鏈接結構分析的隨機方法”；第三種是本文將重點介紹的網頁排序法，最初思想由佩奇和布林于1996年醞釀而生，他們對此的第一篇技術性文章由四人合寫，其中最后一位作者就是他們的導師維諾格拉德。這篇歷史留名的論文于1999年以斯坦福大學計算機科學系技術報告1999-0120的方式公開問世，標題是The PageRank Citation Ranking: Bringing Order to the Web（PageRank引用排名：為網絡帶來秩序）。盡管該文似乎從未在學術期刊上正式發表，迄今卻已被引用了兩萬余次?？梢姴⒎强偸窃诿踔疗诳习l表的論文才會“推動科技的進步”。

在網頁排序概念出現兩年后橫空出世的谷歌公司，一開始就在官網聲明：

網頁排序是我們軟件的核心。

又過了以驚人速度壯大發展的四年，與公司員工共舞的其尺寸大得難以想象的那個矩陣——后被人們常掛在嘴邊的“谷歌矩陣”，引發出大型通用計算程序包Matlab的開發者克利夫·莫勒（Cleve Moler，1939-）的感慨，在自己公司MathWorks的《Matlab新聞和簡訊》上撰文《世界上規模最大的矩陣計算》。

那么，這個世間最大的矩陣是怎么定義出來的？

首先，它是一個非負矩陣，即矩陣的每個元素都是非負實數，并且它也是個方陣，即行數等于列數。其次，它的每一行的所有元素加起來都等于1。這種特殊的非負矩陣有個學名，叫隨機矩陣（stochastic matrix）。在線性代數這門應用廣泛的數學學科，“非負矩陣理論”構成了一個子學科，而隨機矩陣又是其中的核心部分。可惜的是，我們的本科教科書中一般不放進這類東西。

要充分理解谷歌矩陣的定義基礎，先得從網頁排序的基本想法開始。

網頁排序的理念是：

來自重要頁面的鏈接應該比來自不太重要頁面的鏈接權重更高，并且來自任何源頁面的鏈接的重要性應該根據該源頁面鏈接到的頁面數量進行縮放。

這個創新思想是容易想得通的。多年前，當筆者之一在國內高校做有關谷歌矩陣的演講時，向聽眾如此解釋它：國家領袖網頁上的內容肯定比數學教授的網頁內容在大眾眼里更加重要，而且前者的網頁會被更多的網頁鏈接到，因此它應享有更加靠前的排名。如果采用數學語言來表達前述的意思，那么該想法是通過定義給定網頁P的合理排名r(P)來實現的。r(P)定義為：

r(P) = ∑Q∈I(P)r(Q)/|Q|，

其中I(P)是所有指向P的那些網頁組成的集合，r(Q)是網頁Q的排名，|Q|表示從網頁Q發出的鏈接數。如上表達式說明，網頁P的重要程度，首先依鏈接到它的其他網頁的多寡而定，越多越重要，且那些指向它的網頁Q越重要，則P也隨之越重要，可謂“水漲船高”；其次，若指向網頁P的某個網頁Q也指向其他網頁，則被鏈接的網頁越多，P在Q眼中的重要性相應就變低，這解釋了為何|Q|出現在分母。打個比方，如果閣下的網頁被某個名流鏈接到，不必太得意，或許該名流熱衷于社會交際，同時也鏈接了其他許多人的網頁，這樣的話你的網頁重要性并沒有因該名流的光顧而大增。

以上對單個網頁P的排名r(P)雖然定義合理，但這是一個隱式定義，因此我們借用迭代法來找到上述“不動點方程”的一個解，方法如下：

假設共有n個網頁P1,P2,...,Pn。為每個網頁分配一個初始排名r0，最公平合理的初始排名是均勻排名

r0(Pi) = 1/n，i = 1,2,…,n。

然后對k = 1,2,3,...如下操作排名迭代：

rk(Pi) = ∑Pj∈I(Pi)rk?1(Pj)/|Pj|，i = 1,2,…,n。

現在定義n階方陣P = [pij]ni,j = 1：對于i, j = 1, 2,…, n，若網頁Pi鏈接到網頁Pj，則令

pij= 1/|Pi|；

否則的話，定義pij= 0。顯見，P是非負方陣且每行元素之和等于1。換言之，P是n階隨機矩陣。此外，對于行向量

πkT= (rk(P1), rk(P2), …, rk(Pn)),

上述的迭代過程可以用矩陣乘法的形式表示：

πkT=(πk-1)TP,k = 1,2,…。

如果下列極限存在的話，佩奇和布林將極限向量

πT= limk→∞πkT

定義為網頁排序向量，而它的第i個分量πi則成為網頁Pi的排名。

可是，要使得定義不被詬病，他們需要回答兩個問題：

1.這個原始的谷歌矩陣P是否存在對應于特征值1的左特征向量πT？若πT存在，歸一化（目的讓所有分量之和變成1）后的πT是否唯一？

2.當k趨于無窮大時，迭代向量序列πkT=(πk-1)TP的極限是否存在？若存在，那么迭代收斂得多快呢？

現在用一個簡單例子說明思想?？紤]一個僅有六個網頁的微型網絡，并使用原始的谷歌矩陣。

注意到矩陣的第二行元素全為零，這是因為沒有從第二個網頁（對應的有向圖節點叫做懸空節點）發出的鏈接。所以P不是一個隨機矩陣！

為了補救，我們將第二行的每個元素加上1/6，便得到一個隨機矩陣S：

對于這個經過改造的矩陣，非負矩陣理論中最經典的一個定理派上了大用場，它以兩個德國數學家的名字命名——佩龍-佛羅貝爾尼斯定理，年輕的前者佩龍（Oskar Perron，1880-1975）于1907年對正矩陣，即每個元素均為正數的矩陣證明了它，年長的后者佛羅貝爾尼斯（Ferdinand GeorgFrobenius，1849-1917）五年后對所謂的不可約非負矩陣推廣了佩龍的結果。一個方陣稱為是可約的，意思是說，可以將它的行和列以同樣的方式重新排列，其結果矩陣的右下角是個零方陣。譬如，2階及更高階的單位矩陣是可約非負矩陣。

即便上述的隨機矩陣S是可約的，一個經典的不動點定理——布勞威爾不動點定理卻能保證，存在歸一化的非負左特征向量πT：

πT= πTS,πTe = 1。

這里按習慣用字母e代表特殊列向量(1,1,…,1)T。任意矩陣A乘以e，所得向量的各分量等于將A的那行元素加起來得到的和，故非負矩陣A為隨機矩陣當且僅當Ae = e。

遺憾的是，上例中的隨機矩陣S雖然確保了網頁排序向量πT的存在性，卻由于它是可約的（因為右下角是3階零矩陣），結果是歸一化的πT不能保證唯一且分量個個為正。如果網頁排名不唯一，至少會造成網頁排序算法迭代不收斂或計算結果混淆不清。當今各種大學排名榜五花八門，結果千奇百怪，搞得大學當局有時高興有時發愁，就是排名不唯一的后遺癥。

為解決這一棘手問題，布林和佩奇引入了S的由參數α∈(0,1)控制的一種“凸組合”擾動；例如，取α = 0.9，得到一個新矩陣：

讀者一看就知道G是一個正矩陣。此外，它繼承了S是隨機矩陣的好性質，這一點的證明簡潔而明快：

Ge=(0.9S + 0.1eeT/6)e = 0.9Se + 0.1eeTe/6

= 0.9e + 0.1(eTe)e/6 = 0.9e + 0.1(6)e/6 = 0.9e + 0.1e = e。

這樣，按照佩龍-佛羅貝爾尼斯的非負矩陣理論，G不僅存在唯一的歸一化左特征向量πT，其具體數值是

πT= (0.03721, 0.05396, 0.04151, 0.3751, 0.206, 0.2862)，

而且正因為這個網頁排序向量的所有分量均為正數，它實實在在地提供了所給微型網絡總共6個網頁的排名。更重要的是，取定初始向量π0T= (1/6, 1/6, 1/6, 1/6, 1/6, 1/6)，直接迭代法

πkT=(πk-1)TG，k = 1,2,...

計算出的歸一化向量序列{πkT}收斂到G的唯一歸一化左特征向量πT。

有了上面的具體例子墊底，我們可以敘述谷歌矩陣的一般定義及其相應的網頁排序算法。如前，假設所有的網頁為P1,P2,...,Pn，其對應的n階原始谷歌矩陣為P。選取一個固定的n維“概率向量”

v = (v1, v2, v3,…, vn)T，

即v的所有分量都是正數，并且其和等于1，即vTe = 1。

將矩陣P的所有零行替換為相同的行向量vT，得到隨機矩陣S。現在固定參數α∈(0,1)（早期谷歌公司使用過參數值α= 0.85），并將谷歌矩陣G定義為S和evT的凸組合：

G = αS + (1–α)evT。

G依然是個隨機矩陣：

Ge = [αS + (1–α)evT]e =αSe + (1–α)evTe

=αe + (1–α)(vTe)e=αe + (1–α)e = e。

更重要的是，由于S是非負矩陣，evT是正矩陣，它們的凸組合的系數小于1，這保證了G是個正矩陣。如此構造的矩陣G被稱為谷歌矩陣。

萬事俱備只欠東風，現在可以敘述（但不證明）已超過一百年歷史的佩龍-佛羅貝爾尼斯定理在正隨機矩陣時的特殊結論了。

正隨機矩陣譜定理.設A為一n階正隨機矩陣。則存在歸一化的所有分量均為正數的n維行向量πT，即

πT= πTA,πTe = 1；

滿足上述性質的πT是唯一的。此外，A的所有特征值的最大模等于1，并且1是A在復平面單位圓上的唯一特征值。更進一步，任給歸一化的n維非負初始向量π0T，迭代向量序列

πkT=(πk-1)TA =π0TAk，k = 1,2,...

收斂到πT。

譜定理告訴我們，對于佩奇和布林創造出的谷歌矩陣，上述這個被稱為“冪方法”的迭代程式總收斂到網頁排序向量。又因為谷歌矩陣規模巨大，冪方法只能是給全球有效網頁快速排名的唯一實用辦法。

收斂性問題圓滿解決后，關注谷歌用于計算網頁排序基本算法效率的讀者自然會問到“收斂得多快”的應用性問題。學過數值線性代數的人知道冪方法的收斂速率取決于矩陣所有特征值中的次大模。現在我們用矩陣特征多項式的技巧來尋找谷歌矩陣G所有的特征值。

首先，因為S是隨機矩陣，1是它的特征值，特征向量是e。記S的所有特征值為1,λ2, λ3, ··· , λn。則αS的征值為α,αλ2,αλ3, …,αλn。為方便起見，令A = αS及u = (1–α)e。則G = A + uvT。

設λ不是A的特征值。從等式λI?G = (λI?A)?uvT，運用著名的矩陣行列式引理，即若B為m階非奇異矩陣，且x和y為m維向量，則

det(B + xyT) =(1+ yTB-1x)detB，

得到G的特征多項式的表達式

det(λI?G) =[1–vT(λI?A)-1u]det(λI?A)。

由于

(λI?A)u = (1?α)(λI–αS)e = (1?α)(λ?α)e

= (λ?α)(1?α)e = (λ?α)u，

(λI?A)-1u =(λ–α)-1u，

隨即便有

1?vT(λI?A)-1u =1?(λ–α)-1vTu= (λ–α)-1[λ–(α+vTu)]。

從而得到

det(λI?G) =(λ–α)-1[λ–(α+vTu)]det(λI?A)。

因為α+vTu=α+vT(1?α)e=α+(1?α) vTe =α+(1?α)= 1，便有

det(λI?G) =(λ–α)-1(λ–1)det(λI?A)

=(λ–α)-1(λ–1)(λ–α)(λ–αλ2) (λ–αλ3)…(λ–αλn)

= (λ–1)(λ–αλ2) (λ–αλ3)…(λ–αλn)。

這就證明了下列的定理：

谷歌矩陣譜定理.谷歌矩陣G=αS + (1–α)evT的所有特征值是

1,αλ2,αλ3, …,αλn。

由于每個λi位于單位圓的內部，故

|αλi|<α < 1,i = 2,3,...,n，

因此冪方法的收斂速率取決于參數值α的大小。這個值如果取得靠近(0, 1)開區間的右端點，冪方法的迭代步伐就會慢下來；反之，若將它取得太小，甚至靠近(0, 1)的左端點，G又與折射出真實網絡世界各網頁之間“朋友關系”的S相距太遠，這樣計算雖然快了，但結果或許有不能全方位反映真實世界之危險。總之，選擇參數α的數值要顧及到準確與速度的雙重思量。

就數學而言，上面的谷歌矩陣譜定理是下面的秩-1矯正矩陣譜擾動定理的一個特殊化。這個一般結果是筆者之一20年前在一篇合作文章中證明的。

秩-1矯正矩陣譜擾動定理.設A為一n階矩陣，其特征值是λ1, λ2, ..., λn。若u和v為兩個n維向量，其中u是A對應于λ1的特征向量，則A+uvT的特征值是λ1+vTu, λ2, …, λn。

將上述定理中的A取為谷歌矩陣譜定理中的αS，u取為(1–α)e，則如前所述，A的特征值是α,αλ2,αλ3, …,αλn，且u是A對應于α的特征向量。則秩-1矯正矩陣譜擾動定理給出G =αS + (1–α)evT的第一個特征值為

λ1+vTu=α+ (1–α)vTe =α+ (1–α) = 1，

而αS的特征值αλ2,αλ3, …,αλn通通留給了G，得到谷歌矩陣譜定理的結論。

過去四分之一個世紀，PageRank 算法不僅成就了一家商業巨頭，更深刻改變了人類獲取信息的范式。盡管在今天，隨著人工智能的演進和網絡生態的更迭，傳統搜索引擎的形態正經歷劇烈的陣痛與重塑，但其背后的數學邏輯——通過矩陣刻畫關聯、用特征值尋找秩序——依然是處理海量數據的核心思想。今天正值國際數學日，回望這個“世界最大矩陣”，我們感嘆的不僅是算法帶來的便利，更是數學作為一種普適語言，在紛繁復雜的現實世界中剝離混沌、指引真理的純粹力量。