想了解概率圖模型？你要先理解圖論的基本定義與形式

選自Dev To

作者：vaidehijoshi等

機器之心編譯

參與：蔣思源、李澤南

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

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

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

Loosey–goosey圖

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

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

樹型只不過是一種受限圖，只不過是遵循眾多規則的圖。樹型永遠是圖中的一種，但圖遠遠不止是樹。

那麼到底是什麼讓樹型有別於傘狀圖呢？

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

而通過圖，所有的這些限制好像都突然消失了。因為圖是沒有任何「根結點」、「葉節點」和「單向邊」等這些概念的，所以圖中的結點可以連接多個子結點也可以有多個父結點，路徑也可以是有向流或者無向邊。或者如果想要圖更加複雜一點，也可以採用有向流和無向邊的組合，但是本文暫時並不會關注這些複雜系統。

有向圖和無向圖

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

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

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

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

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

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

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

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

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

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

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

在數學中，圖是一種正式表徵網路的結構，其基本上是所有互連對象的集合。

事實證明，當計算機科學家將圖論應用於代碼（創造出圖數據結構或樹型演算法等）時，那些理論並沒有改變多少。所以本文描述和實現圖的術語就是在數學圖論中的確切術語。

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

因此，圖的正式數學定義即為：G=（V，E）

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

實際上上述定義式並不會失效，因為有序對（V，E）實際上是由兩組對象組成：一組結點，一組邊。

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

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

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

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

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

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

所以以上就是我們如何定義一個圖，但是在定義圖之後，我們什麼時候才能實際應用圖呢。下面我們將一起來了解一下圖的應用和計算。

超級社交圖

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

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

現在，我們使用一個更加生動的案例，以說明圖與日常的交互：社交網路。

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

那你現在能判斷微信的圖是什麼類型了么。

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

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

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

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

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

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

這裡有一些圖論相關資源：

Difference between Trees and Graphs：http://suo.im/2qN4yS

What"s the difference between the data structure Tree and Graph?：http://suo.im/1wjBzi

Applications of Graph Theory In Computer Science: An Overview：http://suo.im/4twRke

Graph Traversal：http://suo.im/2cu4oH

Data structures: Introduction to graphs（視頻）：http://suo.im/4z1QbH