題目中所說(shuō)到的四個(gè)詞語(yǔ)，都是Machine Learning以及相關(guān)領(lǐng)域中熱門(mén)的研究課題。表面看屬于不同的topic，實(shí)際上則是看待同一個(gè)問(wèn)題的不同角度。不少文章論述了它們之間的一些聯(lián)系，讓大家看到了這個(gè)世界的奇妙。

從圖說(shuō)起

這里面，最簡(jiǎn)單的一個(gè)概念就是“圖”(Graph)，它用于表示事物之間的相互聯(lián)系。每個(gè)圖有一批節(jié)點(diǎn)(Node)，每個(gè)節(jié)點(diǎn)表示一個(gè)對(duì) 象，通過(guò)一些邊(Edge)把這些點(diǎn)連在一起，表示它們之間的關(guān)系。就這么一個(gè)簡(jiǎn)單的概念，它對(duì)學(xué)術(shù)發(fā)展的意義可以說(shuō)是無(wú)可估量的。幾乎所有領(lǐng)域研究的東 西，都是存在相互聯(lián)系的，通過(guò)圖，這些聯(lián)系都具有了一個(gè)統(tǒng)一，靈活，而又強(qiáng)大的數(shù)學(xué)抽象。因此，很多領(lǐng)域的學(xué)者都對(duì)圖有著深入探討，而且某個(gè)領(lǐng)域關(guān)于圖的 研究成果，可以被其它領(lǐng)域借鑒。

矩陣表示：讓代數(shù)進(jìn)入圖的世界

在數(shù)學(xué)上，一種被普遍使用的表達(dá)就是鄰接矩陣(Adjacency Matrix)。一個(gè)有N個(gè)節(jié)點(diǎn)的圖，可以用一個(gè)N x N的矩陣G表示，G(i, j)用一個(gè)值表示第i個(gè)節(jié)點(diǎn)和第j個(gè)節(jié)點(diǎn)的聯(lián)系，通常來(lái)說(shuō)這個(gè)值越大它們關(guān)系越密切，這個(gè)值為0表示它們不存在直接聯(lián)系。這個(gè)表達(dá)，很直接，但是非常重 要，因?yàn)樗褦?shù)學(xué)上兩個(gè)非常根本的概念聯(lián)系在一起：“圖”(Graph)和“矩陣”(Matrix)。矩陣是代數(shù)學(xué)中最重要的概念，給了圖一個(gè)矩陣表達(dá)， 就建立了用代數(shù)方法研究圖的途徑。數(shù)學(xué)家們幾十年前開(kāi)始就看到了這一點(diǎn)，并且開(kāi)創(chuàng)了數(shù)學(xué)上一個(gè)重要的分支——代數(shù)圖論(Algebraic Graph Theory)。

代數(shù)圖論通過(guò)圖的矩陣表達(dá)來(lái)研究圖。熟悉線性代數(shù)的朋友知道，代數(shù)中一個(gè)很重要的概念叫做“譜”(Spectrum)。一個(gè)矩陣的很多 特性和它的譜結(jié)構(gòu)——就是它的特征值和特征向量是密切相關(guān)的。因此，當(dāng)我們獲得一個(gè)圖的矩陣表達(dá)之后，就可以通過(guò)研究這個(gè)矩陣的譜結(jié)構(gòu)來(lái)研究圖的特性。通 常，我們會(huì)分析一個(gè)圖的鄰接矩陣(Adjacency Matrix)或者拉普拉斯矩陣(Laplace Matrix)的譜——這里多說(shuō)一句，這兩種矩陣的譜結(jié)構(gòu)剛好是對(duì)稱(chēng)的。

譜：“分而治之”的代數(shù)

譜，這個(gè)詞匯似乎在不少地方出現(xiàn)過(guò)，比如我們可能更多聽(tīng)說(shuō)的頻譜，光譜，等等。究竟什么叫“譜”呢？它的概念其實(shí)并不神秘，簡(jiǎn)單地說(shuō)，譜這 個(gè)概念來(lái)自“分而治之”的策略。一個(gè)復(fù)雜的東西不好直接研究，就把它分解成簡(jiǎn)單的分量。如果我們把一個(gè)東西看成是一些分量疊加而成，那么這些分量以及它們 各自所占的比例，就叫這個(gè)東西的譜。所謂頻譜，就是把一個(gè)信號(hào)分解成多個(gè)頻率單一的分量。

矩陣的譜，就是它的特征值和特征向量，普通的線性代數(shù)課本會(huì)告訴你定義：如果A v = c v，那么c 就是A的特征值，v就叫特征向量。這僅僅是數(shù)學(xué)家發(fā)明的一種數(shù)學(xué)游戲么？——也許有些人剛學(xué)這個(gè)的時(shí)候，并一定能深入理解這么個(gè)公式代表什么。其實(shí)，這里 的譜，還是代表了一種分量結(jié)構(gòu)，它為使用“分而治之”策略來(lái)研究矩陣的作用打開(kāi)了一個(gè)重要途徑。這里我們可以把矩陣?yán)斫鉃橐粋€(gè)操作(operator)， 它的作用就是把一個(gè)向量變成另外一個(gè)向量：y = A x。對(duì)于某些向量，矩陣對(duì)它的作用很簡(jiǎn)單，A v = cv，相當(dāng)于就把這個(gè)向量v 拉長(zhǎng)了c倍。我們把這種和矩陣A能如此密切配合的向量v1, v2, ... 叫做特征向量，這個(gè)倍數(shù)c1, c2, ...叫特征值。那么來(lái)了一個(gè)新的向量x 的時(shí)候，我們就可以把x 分解為這些向量的組合，x = a1 v1 + a2 v2 + ...，那么A對(duì)x的作用就可以分解了：A x = A (a1 v1 + a2 v2 + ...) = a1 c1 v1 + a2 c2 v2 ... 所以，矩陣的譜就是用于分解一個(gè)矩陣的作用的。

這里再稍微延伸一點(diǎn)。一個(gè)向量可以看成一個(gè)關(guān)于整數(shù)的函數(shù)，就是輸入i，它返回v( i )。它可以延伸為一個(gè)連續(xù)函數(shù)（一個(gè)長(zhǎng)度無(wú)限不可數(shù)的向量，呵呵），相應(yīng)的矩陣 A 變成一個(gè)二元連續(xù)函數(shù)（面積無(wú)限大的矩陣）。這時(shí)候矩陣乘法中的求和變成了積分。同樣的，A的作用可以理解為把一個(gè)連續(xù)函數(shù)映射為另外一個(gè)連續(xù)函數(shù)，這時(shí) 候A不叫矩陣，通常被稱(chēng)為算子。對(duì)于算子，上面的譜分析方法同樣適用（從有限到無(wú)限，在數(shù)學(xué)上還需要處理一下，不多說(shuō)了）——這個(gè)就是泛函分析中的一個(gè)重 要部分——譜論（Spectral Theory）。

馬爾可夫過(guò)程——從時(shí)間的角度理解圖

回到“圖”這個(gè)題目，那么圖的譜是干什么的呢？按照上面的理解，似乎是拿來(lái)分解一個(gè)圖的。這里譜的作用還是分治，但是，不是直觀的理解為把 圖的大卸八塊，而是把要把在圖上運(yùn)行的過(guò)程分解成簡(jiǎn)單的過(guò)程的疊加。如果一個(gè)圖上每個(gè)節(jié)點(diǎn)都有一個(gè)值，那么在圖上運(yùn)行的過(guò)程就是對(duì)這些值進(jìn)行更新的過(guò)程。 一個(gè)簡(jiǎn)單，大家經(jīng)常使用的過(guò)程，就是馬爾可夫過(guò)程(Markov Process)。

學(xué)過(guò)隨機(jī)過(guò)程的朋友都了解馬爾可夫過(guò)程。概念很簡(jiǎn)單——“將來(lái)只由現(xiàn)在決定，和過(guò)去無(wú)關(guān)”。考慮一個(gè)圖，圖上每個(gè)點(diǎn)有一個(gè)值，會(huì)被不斷 更新。每個(gè)點(diǎn)通過(guò)一些邊連接到其它一些點(diǎn)上，對(duì)于每個(gè)點(diǎn)，這些邊的值都是正的，和為1。在圖上每次更新一個(gè)點(diǎn)的值，就是對(duì)和它相連接的點(diǎn)的值加權(quán)平均。如 果圖是聯(lián)通并且非周期（數(shù)學(xué)上叫各態(tài)歷經(jīng)性, ergodicity)，那么這個(gè)過(guò)程最后會(huì)收斂到一個(gè)唯一穩(wěn)定的狀態(tài)（平衡狀態(tài))。

圖上的馬爾可夫更新過(guò)程，對(duì)于很多學(xué)科有著非常重要的意義。這種數(shù)學(xué)抽象，可以用在什么地方呢？(1) Google對(duì)搜索結(jié)果的評(píng)估(PageRank)原理上依賴(lài)于這個(gè)核心過(guò)程，(2) 統(tǒng)計(jì)中一種廣泛運(yùn)用的采樣過(guò)程MCMC，其核心就是上述的轉(zhuǎn)移過(guò)程，(3) 物理上廣泛存在的擴(kuò)散過(guò)程（比如熱擴(kuò)散，流體擴(kuò)散）和上面的過(guò)程有很重要的類(lèi)比，(4) 網(wǎng)絡(luò)中的信息的某些歸納與交換過(guò)程和上述過(guò)程相同 (比如Random Gossiping)，還有很多。非常多的實(shí)際過(guò)程通過(guò)某種程度的簡(jiǎn)化和近似，都可以歸結(jié)為上述過(guò)程。因此，對(duì)上面這個(gè)核心過(guò)程的研究，對(duì)于很多現(xiàn)象的理 解有重要的意義。各個(gè)領(lǐng)域的科學(xué)家從本領(lǐng)域的角度出發(fā)研究這個(gè)過(guò)程，得出了很多實(shí)質(zhì)上一致的結(jié)論，并且很多都落在了圖的譜結(jié)構(gòu)的這個(gè)關(guān)鍵點(diǎn)上。

圖和譜在此聯(lián)姻

根據(jù)上面的定義，我們看到鄰接矩陣A其實(shí)就是這個(gè)馬爾可夫過(guò)程的轉(zhuǎn)移概率矩陣。我們把各個(gè)節(jié)點(diǎn)的值放在一起可以得到一個(gè)向量v，那么我們就 可以獲得對(duì)這個(gè)過(guò)程的代數(shù)表示， v(t+1) = A v(t)。穩(wěn)定的時(shí)候，v = A v。我們可以看到穩(wěn)定狀態(tài)就是A的一個(gè)特征向量，特征值就是1。這里譜的概念進(jìn)來(lái)了。我們把A的特征向量都列出來(lái)v1, v2, ...，它們有 A vi = ci vi。vi其實(shí)就是一種很特殊，但是很簡(jiǎn)單的狀態(tài)，對(duì)它每進(jìn)行一輪更新，所有節(jié)點(diǎn)的值就變成原來(lái)的ci倍。如果0 < ci < 1，那么，相當(dāng)于所有節(jié)點(diǎn)的值呈現(xiàn)指數(shù)衰減，直到大家都趨近于0。

一般情況下，我們開(kāi)始于一個(gè)任意一個(gè)狀態(tài)u，它的更新過(guò)程就沒(méi)那么簡(jiǎn)單了。我們用譜的方法來(lái)分析，把u分解成 u = v1 + c2 v2 + c3 v3 + ... （在數(shù)學(xué)上可以嚴(yán)格證明，對(duì)于上述的轉(zhuǎn)移概率矩陣，最大的特征值就是1，這里對(duì)應(yīng)于平衡狀態(tài)v1，其它的特征狀態(tài)v2, v3, ..., 對(duì)應(yīng)于特征值1 > c2 > c3 > ... > -1)。那么，我們可以看到，當(dāng)更新進(jìn)行了t 步之后，狀態(tài)變成 u(t) = v1 + c2^t v2 + c3^t v3 + ...，我們看到，除了代表平衡狀態(tài)的分量保持不變外，其它分量隨著t 增長(zhǎng)而指數(shù)衰減，最后，其它整個(gè)趨近于平衡狀態(tài)。

從上面的分析看到，這個(gè)過(guò)程的收斂速度，其實(shí)是和衰減得最慢的那個(gè)非平衡分量是密切相關(guān)的，它的衰減速度取決于第二大特征值c2，c2 的大小越接近于1，收斂越慢，越接近于0，收斂越快。這里，我們看到了譜的意義。第一，它幫助把一個(gè)圖上運(yùn)行的馬爾可夫過(guò)程分解為多個(gè)簡(jiǎn)單的字過(guò)程的疊 加，這里面包含一個(gè)平衡過(guò)程和多個(gè)指數(shù)衰減的非平衡過(guò)程。第二，它指出平衡狀態(tài)是對(duì)應(yīng)于最大特征值1的分量，而收斂速度主要取決于第二大特征值。

我們這里知道了第二大特征值c2對(duì)于描述這個(gè)過(guò)程是個(gè)至關(guān)重要的量，究竟是越大越好，還是越小越好呢？這要看具體解決的問(wèn)題。如果你要 設(shè)計(jì)一個(gè)采樣過(guò)程或者更新過(guò)程，那么就要追求一個(gè)小的c2，它一方面提高過(guò)程的效率，另外一方面，使得圖的結(jié)構(gòu)改變的時(shí)候，能及時(shí)收斂，從而保證過(guò)程的穩(wěn) 定。而對(duì)于網(wǎng)絡(luò)而言，小的c2有利于信息的迅速擴(kuò)散和傳播。

聚類(lèi)結(jié)構(gòu)——從空間的角度理解圖

c2的大小往往取決于圖上的聚類(lèi)結(jié)構(gòu)。如果圖上的點(diǎn)分成幾組，各自聚成一團(tuán)，缺乏組與組之間的聯(lián)系，那么這種結(jié)構(gòu)是很不利于擴(kuò)散的。在某些 情況下，甚至需要O(exp(N))的時(shí)間才能收斂。這也符合我們的直觀想象，好比兩個(gè)大水缸，它們中間的只有一根很細(xì)的水管相連，那么就需要好長(zhǎng)時(shí)間才 能達(dá)到平衡。有興趣的朋友可以就這個(gè)水缸問(wèn)題推導(dǎo)一下，這個(gè)水缸系統(tǒng)的第二大特征值和水管流量與水缸的容積的比例直接相關(guān)，隨比例增大而下降。

對(duì)于這個(gè)現(xiàn)象進(jìn)行推廣，數(shù)學(xué)上有一個(gè)重要的模型叫導(dǎo)率模型(Conductance)。具體的公式不說(shuō)了，大體思想是，節(jié)點(diǎn)集之間的導(dǎo) 通量和節(jié)點(diǎn)集大小的平均比例和第二大特征值之間存在一個(gè)單調(diào)的上下界關(guān)系。導(dǎo)率描述的是圖上的節(jié)點(diǎn)連接的空間結(jié)合，這個(gè)模型把第二特征值c2和圖的空間聚 集結(jié)構(gòu)聯(lián)系在一起了。

圖上的聚類(lèi)結(jié)構(gòu)越明顯， c2越大；反過(guò)來(lái)說(shuō)，c2越大，聚類(lèi)的結(jié)構(gòu)越明顯，(c2 = 1)時(shí)，整個(gè)圖就斷裂成非連通的兩塊或者多塊了。從這個(gè)意義上說(shuō)，c2越大，越容易對(duì)這個(gè)圖上的點(diǎn)進(jìn)行聚類(lèi)。機(jī)器學(xué)習(xí)中一個(gè)重要課題叫做聚類(lèi)，近十年來(lái)， 基于代數(shù)圖論發(fā)展出來(lái)的一種新的聚類(lèi)方法，就是利用了第二大特征值對(duì)應(yīng)的譜結(jié)構(gòu)，這種聚類(lèi)方法叫做譜聚類(lèi)(Spectral Clustering)。它在Computer Vision里面對(duì)應(yīng)于一種著名的圖像分割方法，叫做Normalized Cut。很多工作在使用這種方法。其實(shí)這種方法的成功，取決于c2的大小，也就是說(shuō)取決于我們?nèi)绾螛?gòu)造出一個(gè)利于聚類(lèi)的圖，另外c2的值本身也可以作為衡 量聚類(lèi)質(zhì)量，或者可聚類(lèi)性的標(biāo)志。遺憾的是，在paper里面，使用此方法者眾，深入探討此方法的內(nèi)在特點(diǎn)者少。

歸納起來(lái)

圖是表達(dá)事物關(guān)系和傳遞擴(kuò)散過(guò)程的重要數(shù)學(xué)抽象

圖的矩陣表達(dá)提供了使用代數(shù)方法研究圖的途徑

譜，作為一種重要的代數(shù)方法，其意義在于對(duì)復(fù)雜對(duì)象和過(guò)程進(jìn)行分解

圖上的馬爾可夫更新過(guò)程是很多實(shí)際過(guò)程的一個(gè)重要抽象

圖的譜結(jié)構(gòu)的重要意義在于通過(guò)它對(duì)馬爾可夫更新過(guò)程進(jìn)行分解分析

圖的第一特征值對(duì)應(yīng)于馬爾可夫過(guò)程的平衡狀態(tài)，第二特征值刻畫(huà)了這個(gè)過(guò)程的收斂速度（采樣的效率，擴(kuò)散和傳播速度，網(wǎng)絡(luò)的穩(wěn)定程度）。

圖的第二特征分量與節(jié)點(diǎn)的聚類(lèi)結(jié)構(gòu)密切相關(guān)。可以通過(guò)譜結(jié)構(gòu)來(lái)分析圖的聚類(lèi)結(jié)構(gòu)。

馬爾可夫過(guò)程代表了一種時(shí)間結(jié)構(gòu)，聚類(lèi)結(jié)構(gòu)代表了一種空間結(jié)構(gòu)，“譜”把它們聯(lián)系在一起了，在數(shù)學(xué)刻畫(huà)了這種時(shí)與空的深刻關(guān)系。