圖論一直是數(shù)學里十分重要的學科，其以圖為研究對象，通常用來描述某些事物之間的某種特定關系。而在機器學習的世界里，我們希望從數(shù)據(jù)中挖掘出隱含信息或模型。因此，如果我們將圖中的結點作為隨機變量，連接作為相關性關系，那么我們就能構造出圖模型，并期望解決這一問題。本文將為構造該模型提供最基礎的概念。

我們都知道機器學習里的決策樹，其可以表示為給定特征條件下類的條件概率分布。并且我們知道決策樹由結點和有向邊組成，結點又由表示特征的內(nèi)部結點和表示類的葉結點構成。而通常決策樹的學習又包括了特征的選擇、決策樹的生成和決策樹的剪枝。那么這種樹型算法又是來自哪呢?其實樹型只是圖的一個小分支，而接下來我們將進一步了解源于離散數(shù)學并十分重要的分支：圖論(graph theory)。

如果這是你***次涉足關于圖論的內(nèi)容，那么本篇文章將會給你一個清晰的概念。同時也希望本文能將圖論的思想、基本模型闡述清楚，因此不論是對以后的機器學習模型構建還是概率圖模型的理解都能提供一定的助力。

Loosey–goosey圖

當***次開始研究非線性結構時，我們需要學習它們最基礎的特征：即數(shù)據(jù)并不遵循特有的順序，至少是沒有明顯的數(shù)值關系，這一點就和我們看到的數(shù)組與鏈表一樣。正如我們所了解的，樹型結構從根結點開始，并能和其他結點相連接，也就是說一棵完整的樹可以由其子樹構成。樹由一組規(guī)則定義而成：即一個根結點可能連接或不連接到其他結點，但最終所有葉結點或內(nèi)部結點都能追溯到這個特定的位置。一些樹有更多的特定規(guī)則，如二叉搜索樹，該樹在任意時間內(nèi)每個結點都只和兩個子結點相連。而機器學習常用的決策樹就可以看成是 IF-THEN 規(guī)則的集合。即由決策樹的根結點到葉結點的每一條路徑構建一條規(guī)則，路徑上內(nèi)部結點的特征對應著規(guī)則的條件，而葉結點的類對應著規(guī)則的結論。

那我們是否能將構成樹狀的這些規(guī)則拋棄掉，不用再嚴格地遵守這些規(guī)則而生成圖(graph)。當然這樣做是不會出錯的，只是生成不了樹，也不能以樹狀的結構進行計算了。但是我們進一步能用圖進行計算或處理任務。

那么到底是什么讓樹型有別于傘狀圖呢?

首先，一棵樹只能朝一個方向傳播，即樹型是由有向邊(directed edge)構成的。每一顆樹都是由根節(jié)點開始，向下往子節(jié)點或葉節(jié)點傳播。同樣樹型的每一條路徑都是唯一的，并且路徑上的所有子結點有且僅有一個父節(jié)點。所以這種樹型結構一定不會存在循環(huán)結構或鏈路。

而通過圖，所有的這些限制好像都突然消失了。因為圖是沒有任何「根結點」、「葉節(jié)點」和「單向邊」等這些概念的，所以圖中的結點可以連接多個子結點也可以有多個父結點，路徑也可以是有向流或者無向邊?；蛘呷绻胍獔D更加復雜一點，也可以采用有向流和無向邊的組合，但是本文暫時并不會關注這些復雜系統(tǒng)。

有向圖和無向圖

現(xiàn)在我們已經(jīng)知道圖確實打破了構造樹型的所有規(guī)則。但每一個圖都必須遵守一個基本原則：即圖有且至少有一個單結點。就像樹型至少需要一個根結點才可以看作是「樹」，圖也至少需要一個單結點以便可以看作是「圖」。只有一個結點的圖通常稱為「單例圖」，基本上我們不會使用這種單例圖處理任務。

通常能進行運算處理的圖都是更復雜一些的圖，但是不要太擔心，本文所描述的圖都不會太復雜，不過有些圖真的是超級復雜的。

首先我們會探討一下很容易辨認和理解的兩種圖：有向圖(directed graphs)和無向圖(undirected graphs)。這兩種圖在圖論(graph theory)探討的問題中十分常見。

在圖中，結點和結點之間的連接并沒有確切的規(guī)則，邊(有時候也稱為鏈接)能以任何方式連接結點。

不同類型的邊或路徑對定義和識別圖時非常重要。邊的類型實際上是圖之間***、最明顯的區(qū)別之一。大多數(shù)情況下(只有一種例外)，圖會有兩種類型的邊：即具有方向或流向的邊和不具有方向或流動的邊。我們將其稱為有向邊(directed edges)和無向邊(undirected edges)。

在有向邊中，兩個結點以特定的方式連接。如下圖結點 A 連接結點 B 的方式所示，有向邊規(guī)定了兩個結點之間只有單一的方向，即只能從起始結點(origin)沿特定方向到目標結點(destination)，永遠不能反過來從目標結點到起始結點。這種類型的有向邊在圖論問題中十分常見。

現(xiàn)在，我們再介紹一下與有向邊完全不同的無向邊。在無向邊(undirected edge)里，可通過的路徑是雙向的。也即兩個結點之間的路徑是雙向互通的，起始結點和目標結點并沒有固定。

這種差異是十分重要的，因為圖中的邊確定了圖的類型。如果圖中所有的邊都是有向邊，那么該圖就是有向圖(directed graph)。如果圖所有的邊都是無向邊，那么該圖就是無向圖(undirected graph)。

以上所描述的圖看起來很有結構性，但也許我們更應該關心兩件事情：首先具體是什么條件或事件填充了圖，其次我們具體要關注圖的什么信息?

輕輕地：我們來到了圖的王國

計算機科學喜歡借鑒其他學科。具體來說是喜歡借鑒邏輯學和數(shù)學的許多概念。而圖論也是一樣，其最開始就是數(shù)學的一個分支，且以圖為研究對象，圖論經(jīng)常是研究頂點和邊組成圖的數(shù)學理論和方法。而我們所熟悉的圖數(shù)據(jù)結構或樹型算法等計算機概念實際上都來自于數(shù)學，而對圖的研究就是圖論(graph theory)。

在數(shù)學中，圖是一種正式表征網(wǎng)絡的結構，其基本上是所有互連對象的集合。

事實證明，當計算機科學家將圖論應用于代碼(創(chuàng)造出圖數(shù)據(jù)結構或樹型算法等)時，那些理論并沒有改變多少。所以本文描述和實現(xiàn)圖的術語就是在數(shù)學圖論中的確切術語。

在數(shù)學術語中，我們將圖描述為有序?qū)?ordered pairs)。還記得以前學過的函數(shù)，它的定義就是在二維坐標軸上分布的有序?qū)?x，y)集合。圖也是使用類似的定義，只不過使用圖的結點(vertices)v 和邊(edges)e 代替 x 和 y。

因此，圖的正式數(shù)學定義即為：G=(V，E)

但是問題來了，如果我們的圖有多個結點和多條邊怎么辦，實際上有多個結點通常就會有多條邊，那么這種情況又該怎么定義圖呢。

實際上上述定義式并不會失效，因為有序?qū)?V，E)實際上是由兩組對象組成：一組結點，一組邊。

現(xiàn)在廣義的圖定義變得更加有意義，但如果能有一個實例來說明的話，這個概念就會比較好理解，所以下圖是我們使用 8 個結點，12 條邊組成的一個無向圖，我們會詳細解釋該圖是如何用數(shù)學正式定義。

那么上圖那個例子到底說了些什么。

我們將有序?qū)τ洖?V，E)，但因為每一項都是一個對象，所以我們必須把這些項寫出來。V 已經(jīng)定義為八個結點的無序集，而「無序」這一概念在這里非常重要。因為圖與樹型不同，其結點沒有層次結構。因此排序并不重要，我們也不需要對它們進行排序。

我們還須將 E 定義為包含所有邊的項。同樣，邊這一對象也是無序的。原因就在于圖的邊是無向邊，它沒有固定的流向或方向，也就是沒有固定的起始節(jié)點和目標節(jié)點，所以每條邊都是無序地。

當然，無向圖的「無序」這一特性可能會引起一些疑惑，但有向圖又有什么性質(zhì)呢?下面是另一個案例，該圖是由三個結點和三條有向邊組成的有向圖。

在有向圖中，定義結點的方式和無向圖中是一樣的，但有向邊和無向邊的定義是不一樣的。在有向圖中，邊的對象定義為有序?qū)?使用圓括弧表示)，因為這種情況下，邊的方向十分重要。因為在有向圖中，邊只能是從起始結點到目標結點，所以邊必須進行排序，從而定義 E 中有序?qū)η耙粋€元素為起始結點，后一個元素為目標結點。

所以以上就是我們?nèi)绾味x一個圖，但是在定義圖之后，我們什么時候才能實際應用圖呢。下面我們將一起來了解一下圖的應用和計算。

超級社交圖

圖其實就在我們身邊，只是我們不了解而已。

事實上，你在閱讀這篇文章的時候，你就是處于一張圖中。網(wǎng)絡就是巨大的圖結構，每個終端是一個結點，而互聯(lián)網(wǎng)就是網(wǎng)絡的邊。網(wǎng)頁也是，當我們點擊網(wǎng)站并在 URL 之間來回瀏覽時，我們就是在圖中瀏覽。有的網(wǎng)頁之間是無向邊，可以在兩個網(wǎng)頁之間來回切換，而有的是有向邊，只能從一個網(wǎng)頁轉(zhuǎn)到另一個。

現(xiàn)在，我們使用一個更加生動的案例，以說明圖與日常的交互：社交網(wǎng)絡。

微信是一個龐大的社交網(wǎng)絡，它也是一種圖。如果我們能更多地去思考它實際的功能，那么我們可以更好地理解怎樣定義和確定圖的類型是什么。在微信上，如果我希望成為你的朋友，那么我需要添加你為好友，且你必須接受我的請求。在你不是我的微信好友情況下，我也會不是你的微信好友。兩個用戶之間的關系(圖中的結點和邊)是雙向的。其沒有起始節(jié)點和目標節(jié)點這一概念。

那你現(xiàn)在能判斷微信的圖是什么類型了么。

因此微信就是一種大型無向圖，用戶之間可以同時相互傳遞信息。

但另外一種社交網(wǎng)絡微博卻是有向圖，因為在用戶發(fā)布微博時，博文這一信息會在同時間點由用戶向粉絲發(fā)送，這一過程是有方向不可逆的。

在了解了圖論的基礎概念和定義表達式后，或許我們可以進一步窺探一些概率圖模型的重要思想。

機器學習的一個核心任務是從觀測到的數(shù)據(jù)中挖掘隱含的知識，而概率圖模型是實現(xiàn)這一任務的重要手段。概率圖模型巧妙地結合了圖論和概率論。從圖論的角度來說，概率圖模型就是一個包含結點與邊的圖。結點可以分為兩類：隱含結點和觀測結點。邊可以分為有向邊或無向邊。從概率論的角度來看，概率圖模型是一個概率分布，圖中的結點對應于隨機變量，邊對應于隨機變量的相關性關系。給定一個實際問題，我們通常會觀測到一些數(shù)據(jù)，并且希望能夠挖掘出隱含在數(shù)據(jù)中的知識。那么怎樣才能使用概率圖模型挖掘這些隱藏知識呢?通常情況下我們會構建一個圖：用觀測結點表示觀測到的數(shù)據(jù)，用隱含結點表示潛在的知識，用邊來描述知識與數(shù)據(jù)的相互關系，***獲得一個概率分布。給定概率分布之后，通過進行兩個任務獲取知識：即推斷 (給定觀測結點，推斷隱含結點的后驗分布)和學習 (學習概率分布的參數(shù))。

基本的圖模型可以大致分為兩個類別：貝葉斯網(wǎng)絡 (Bayesian Network) 和馬爾可夫隨機場 (Markov Random Field)。它們的主要區(qū)別在于采用不同類型的圖來表達變量之間的關系：貝葉斯網(wǎng)絡采用有向無環(huán)圖 (Directed Acyclic Graph) 來表達因果關系，馬爾可夫隨機場則采用無向圖 (Undirected Graph) 來表達變量間的相互作用。這種結構上的區(qū)別導致了它們在建模和推斷方面的一系列微妙的差異。

至此，我們已經(jīng)知道了圖論到底是什么，也知道基本有向圖和無向圖的標準定義。在文章的***，我們更是將圖論的基本概念和概率論的基本思想相結合來理解概率圖模型。但我們都知道概率圖模型十分強大與重要，所以我們也許需要進一步專門地學習這一機器學習方法。

原文：

https://dev.to/vaidehijoshi/a-gentle-introduction-to-graph-theory?utm_content=buffer6fb86&utm_medium=social&utm_source=twitter.com&utm_campaign=buffer

【本文是51CTO專欄機構機器之心的原創(chuàng)譯文，微信公眾號“機器之心( id: almosthuman2014)”】

戳這里，看該作者更多好文