讀懂概率圖模型:你需要從基本概念和參數估計開始

 2017-11-29 11:39:00.0

原標題:讀懂概率圖模型:你需要從基本概念和參數估計開始

概率圖模型是人工智能領域內一大主要研究方向。近日,Statsbot 團隊邀請數據科學家 Prasoon Goyal 在其博客上分兩部分發表了一篇有關概率圖模型的基礎性介紹文章。文章從基礎的概念開始談起,並加入了基礎的應用示例來幫助初學者理解概率圖模型的實用價值。我們對該文章進行了編譯介紹。

第一部分:基本術語和問題設定

機器學習領域內很多常見問題都涉及到對彼此相互獨立的孤立數據點進行分類。比如:預測給定圖像中是否包含汽車或狗,或預測圖像中的手寫字符是 0 到 9 中的哪一個。

事實證明,很多問題都不在上述範圍內。比如說,給定一個句子「I like machine learning」,然後標註每個詞的詞性(名詞、代詞、動詞、形容詞等)。正如這個簡單例子所表現出的那樣:我們不能通過單獨處理每個詞來解決這個任務——「learning」根據上下文的情況既可以是名詞,也可以是動詞。這個任務對很多關於文本的更爲複雜的任務非常重要,比如從一種語言到另一種語言的翻譯、文本轉語音等。

使用標準的分類模型來處理這些問題並沒有什麼顯而易見的方法。概率圖模型(PGM/probabilistic graphical model)是一種用於學習這些帶有依賴(dependency)的模型的強大框架。這篇文章是 Statsbot 團隊邀請數據科學家 Prasoon Goyal 爲這一框架編寫的一份教程。

在探討如何將概率圖模型用於機器學習問題之前,我們需要先理解 PGM 框架。概率圖模型(或簡稱圖模型)在形式上是由圖結構組成的。圖的每個節點(node)都關聯了一個隨機變量,而圖的邊(edge)則被用於編碼這些隨機變量之間的關係。

根據圖是有向的還是無向的,我們可以將圖的模式分爲兩大類——貝葉斯網絡( Bayesian network)和馬爾可夫網絡(Markov networks)。

貝葉斯網絡:有向圖模型

貝葉斯網絡的一個典型案例是所謂的「學生網絡(student network)」,它看起來像是這樣:

這個圖描述了某個學生註冊某個大學課程的設定。該圖中有 5 個隨機變量:

  • 課程的難度(Difficulty):可取兩個值,0 表示低難度,1 表示高難度

  • 學生的智力水平(Intelligence):可取兩個值,0 表示不聰明,1 表示聰明

  • 學生的評級(Grade):可取三個值,1 表示差,2 表示中,3 表示優

  • 學生的 SAT 成績(SAT):可取兩個值,0 表示低分,1 表示高分

  • 在完成該課程後學生從教授那裏所得到的推薦信的質量(Letter):可取兩個值,0 表示推薦信不好,1 表示推薦信很好

該圖中的邊編碼了這些變量之間的依賴關係。

  • 學生的 Grade 取決於課程的 Difficulty 和學生的 Intelligence;

  • 而 Grade 又反過來決定了學生能否從教授那裏得到一份好的 Letter;

  • 另外,學生的 Intelligence 除了會影響他們的 Grade,還會影響他們的 SAT 分數。

注意其中箭頭的方向表示了因果關係——Intelligence 會影響 SAT 分數,但 SAT 不會影響 Intelligence。

最後,讓我們看看與每個節點關聯的表格,它們的正式名稱是條件概率分佈(CPD/conditional probability distribution)。

1. 條件概率分佈

Difficulty 和 Intelligence 的 CPD 非常簡單,因爲這些變量並不依賴於其它任何變量。基本而言,這兩個表格編碼了這兩個變量取值爲 0 和 1 的概率。你可能已經注意到,每個表格中的值的總和都必須爲 1。

接下來看看 SAT 的 CPD。其每一行都對應於其父節點(Intelligence)可以取的值,每一列對應於 SAT 可以取的值。每個單元格都有條件概率 p(SAT=s|Intelligence=i),也就是說:給定 Intelligence 的值爲 i,則其爲 SAT 的值爲 s 的概率。

比如,我們可以看到 p(SAT=s¹|Intelligence=i¹) 是 0.8。也就是說,如果該學生的智力水平高,那麼他的 SAT 分數也很高的概率是 0.8。而 p(SAT=s⁰|Intelligence=i¹) 則表示如果該學生的智力水平高,那麼 SAT 分數很低的概率是 0.2。

注意,每一行中的值的總和爲 1。這是當然而然的,因爲當 Intelligence=i¹ 時,SAT 只能是 s⁰ 和 s¹ 中的一個,所以兩個概率之和必定爲 1。類似地,Letter 的 CPD 編碼了條件概率 p(Letter=l|Grade=g)。因爲 Grade 可以取 3 個值,所以這個表格有 3 行。

有了上面的知識,Grade 的 CPD 就很容易理解了。因爲它有兩個父節點,所以它的條件概率是這種形式:p(Grade=g|Difficulty=d,SAT=s),即當 Difficulty 爲 d 且 SAT 爲 s 時 Grade 爲 g 的概率。這個表格的每一行都對應於一對 Difficulty 和 Intelligence 值。同樣,每一行的值的總和爲 1。

貝葉斯網絡的一個基本要求是圖必須是有向無環圖(DAG/directed acyclic graph)。

馬爾可夫網絡:無向圖模型

一個馬爾可夫網絡的簡單例子:

爲了簡潔地說明,我們只探討這個抽象的圖,其中的節點 ABCDE 不像上面的例子有直接的真實案例對應。同樣,這些邊表示變量之間的相互作用。我們可以看到 A 和 B 彼此之間有直接的影響關係,而 A 和 C 之間則沒有。注意馬爾可夫網絡不需要是無環的,這一點和貝葉斯網絡不一樣。

1. 可能的用途

正如貝葉斯網絡有 CPD 一樣,馬爾可夫網絡也有用來整合節點之間的關係的表格。但是,這些表格和 CPD 之間有兩個關鍵差異。

首先,這些值不需要總和爲 1,也就是說這個表格並沒有定義一個概率分佈。它只是告訴我們值更高的配置有更高的可能性。其次,其中沒有條件關係。它與所涉及到的所有變量的聯合分佈成正比,這與 CPD 中的條件分佈不同。

這樣得到的表格被稱爲「因子(factor)」或「勢函數(potential function)」,使用希臘字母φ 表示。比如,我們可以使用下面的勢函數來描述變量 A、B 和 C 之間的關係,其中 C 是 A 和 B 的「軟」異或(XOR),也就是說:如果 A 和 B 不一樣,那麼 C 很可能爲 1;如果 A 和 B 一樣,那麼 C 很可能爲 0:

一般而言,你要爲圖中的每個極大團(maximal clique)定義一個勢函數。

圖結構和表格就可以簡潔地表示在這些隨機變量上的聯合概率分佈。

現在你可能會有一個問題:爲什麼我們需要有向圖,也需要無向圖?原因是有些問題使用有向圖表示會更加自然,比如上面提到的學生網絡,有向圖可以輕鬆描述變量之間的因果關係——學生的智力水平會影響 SAT 分數,但 SAT 分數不會影響智力水平(儘管它也許能反映學生的智力水平)。

而對於其它一些問題,比如圖像,你可能需要將每個像素都表示成一個節點。我們知道相鄰的像素互有影響,但像素之間並不存在因果關係;它們之間的相互作用是對稱的。所以我們在這樣的案例中使用無向圖模型。

問題設置

我們已經討論了圖、隨機變量和表格,你可能會想所有這些有什麼意義?我們到底想做什麼?這裏面存在機器學習嗎?數據、訓練、預測都在哪裏?這一節將給你答案。

讓我們再回到學生網絡那個例子。假設我們已經有圖結構了——我們可以根據我們對世界的知識進行創建(在機器學習中,這被稱爲領域知識(domain knowledge))。但我們沒有 CPD 表,只有它們的規模。我們確實有一些數據——來自某所大學的十個不同課程,我們有這些課程的難度的測量方法。

另外,我們還有每個課程的每個學生的數據——他們的智力水平、他們的 SAT 分數、他們得到的評級以及他們是否從教授那裏得到了好的推薦信。根據這些數據,我們可以估計 CPD 的參數。比如說,數據可能表明有高智力水平的學生往往有很好的 SAT 分數,然後我們可能會學習到:p(SAT=s¹|Intelligence=i¹) 很高。這是學習階段。我們後面會介紹我們可以如何在貝葉斯網絡和馬爾可夫網絡中執行這種參數估計。

現在,對於一個新數據點,你可以看到其中一些變量,但不是全部變量。比如,在下面給出的圖中,你可以知道一個課程的難度和學生的 SAT 分數,你想估計學生得到好的評級的概率。(現在你已經從學習階段得到了表格中的值。)

儘管我們沒有可以給我們直接提供信息的 CPD,但我們可以看到有高 SAT 分數的學生說明該學生智力水平也很可能較高;由此,如果該課程的難度很低,那麼該學生得到好評級的概率也會較高,如上圖中的紅色箭頭所示。我們可能也想同時估計多個變量的概率,比如學生同時得到好評級和好推薦信的概率?

這種有已知值的變量被稱爲顯變量(observed variable),而值未被觀察到的變量被稱爲隱變量(hidden variable 或 latent variable)。一般來說,顯變量用灰色節點表示,而隱變量則用白色節點表示,如上圖所示。我們可能想要找到一些或全部顯變量的值。

這些問題的解答類似於機器學習的其它領域——在圖模型中,這個過程被稱爲「推理(inference)」。

儘管我們使用了貝葉斯網絡來描述上述術語,但這也適用於馬爾可夫網絡。在我們深入用於學習和推理的算法之前,讓我們先形式化我們剛剛看過的思想——給定某些節點的值,我們可以得到有關其它哪些節點的信息?

條件獨立

我們剛纔探討過的圖結構實際上帶有關於這些變量的重要信息。具體來說,它們定義了這些變量之間的一組條件獨立(conditional independence),也就是這種形式的陳述——「如果觀察到 A,那麼 B 獨立於 C。」讓我們看一些例子。

在學生網絡中,讓我們假設你看到了一個有很高 SAT 分數的學生,你對她的評級怎麼看呢?正如我們之前見過的那樣,高 SAT 分數說明學生的智力水平很高,因此你可以預計評級爲優。如果該學生的 SAT 分數很低呢?在這個案例中,你可以預計評級不會很好。

現在,讓我們假設你不僅知道這個學生 SAT 分數較高,也知道她的智力水平也較高。如果 SAT 分數較高,那麼你可以預測她的評級爲優。但如果 SAT 分數較低呢?你仍然可以預計評級爲優,因爲這個學生的智能水平高,而且你可以假設她在 SAT 上表現得不夠好。因此,知道這個 SAT 分數並不能讓我們瞭解有關這個學生的智力水平的任何信息。要將其用條件獨立的方式陳述,可以說——「如果已觀察到 Intelligence,那麼 SAT 和 Grade 是獨立的。」

我們是根據這些節點在圖中的連接方式得到這個條件獨立信息的。如果這些節點的連接方式不同,那麼我們也會得到不同的條件獨立信息。

讓我們看看另一個例子。

假設你知道這個學生的智力水平高。你能對這門課程的難度有什麼瞭解呢?一無所知,對吧?現在,如果我告訴你這個學生在這門課程上得到了一個差的評級,又會怎樣呢?這說明這門課程很難,因爲我們知道一個聰明的學生得了一個差。因此我們可以這樣寫我們的條件獨立陳述——「如果未觀察到 Grade,那麼 Intelligence 和 Difficulty 是相互獨立的。」

因爲這些陳述都表達了在一定條件下兩個節點之間的獨立性,所以被稱爲條件獨立。注意這兩個例子有相反的語義——在第一個例子中,如果觀察到相連的節點則獨立性成立;第二個例子則是未觀察到相連的節點則獨立性成立。這種差異是由節點連接的方式(即箭頭的方向)造成的。

爲了行文簡潔,我們不會在這裏覆蓋所有可能的情況,但這些情況都很簡單,憑直覺就能看出來。

在馬爾可夫網絡中,我們可以使用類似的直覺,但因爲其中沒有有方向的邊(箭頭),所以其條件獨立陳述相對簡單——如果節點 A 和 B 之間沒有路徑能使得該路徑上的所有節點都被觀察到,那麼 A 和 B 就是相互獨立的。換種說法:如果在 A 和 B 之間至少有一條路徑上的所有中間節點都未被觀察到,那麼 A 和 B 就不是相互獨立的。

我們會在本博客的第二部分查看完成參數估計和推理的細節。現在讓我們看看貝葉斯網絡的應用,我們可以在其中用到我們剛學習到的條件獨立思想。

應用:三門問題

你肯定在某個電視遊戲節目中看到過這個問題的某個版本:

主持人會向你展示三扇關着的門,其中一扇門之後有一輛車,其它門後則有一些無價值的東西。你可以選擇一扇門。然後,主持人會打開剩下的兩扇門中沒有車的一扇。現在,你可以選擇是否更換選擇的門:堅持你之前選擇的那扇門,還是選擇主持人剩下的那扇關閉的門。你會更換嗎?

直覺上看,主持人似乎並沒有透露任何信息。事實證明這種直覺並不完全正確。讓我們使用我們的新工具「圖模型」來理解這個問題。

我們首先先定義一些變量:

  • D:背後有車的門

  • F:你的第一個選擇

  • H:主持人打開的門

  • I:F 是否是 D?

D、F 和 H 可取值爲 1、2 或 3;I 可取值 0 或 1。D 和 I 是未被觀察到的,而 F 是已觀察到的。在主持人打開其中一扇門之前,H 都是未被觀察到的。因此,我們使用貝葉斯網絡來解決我們的問題:

注意箭頭的方向——D 和 F 是相互獨立的,I 顯然依賴於 D 和 F,主持人選擇的門也取決於 D 和 F。目前你對 D 還一無所知。(這與學生網絡的結構類似,即知道學生的智力水平不能讓你獲得有關課程難度的任何信息。)

現在,主持人選擇了門 H 並打開了它。所以現在 H 已被觀察到。

觀察 H 不能爲我們提供任何有關 I 的信息,也就是說不能表明我們是否選擇了正確的門。我們的直覺是這樣認爲的。但是它卻向我們提供了一些有關 D 的信息!(同樣,類比一下學生網絡,如果你知道學生的智力水平高而評級差,你就能瞭解一些有關課程難度的信息。)

讓我們使用數字來看看。這些變量的 CPD 表格如下所示(這是沒觀察到任何變量的時候):

D 和 F 的表格很簡單——背後有車的門可能是這些門中的任何一扇且概率相等,我們選擇其中一扇的概率是一樣的。I 的表格是說當 D 和 F 一樣時 I=1,當 D 和 F 不一樣時 I=0。H 的表格是說如果 D 和 F 一樣,那麼主持人從另外兩扇門選擇一扇門的概率一樣;如果 D 和 F 不一樣,那麼主持人就選擇第三扇門。

現在,讓我們假設我們已經選擇了一扇門。也就是說現在已經觀察到 F,假設 F=1。那麼給定 F 時,I 和 D 的條件概率是多少?

使用這些等式,我們可以得到以下概率:

這些數字是有道理的——到目前爲止,我們選對了門的概率都是三分之一,汽車仍然有可能在任何一扇門之後且概率相等。

現在,主持人打開了 F 之外的另一扇門,所以我們觀察到了 H。假設 H=2。讓我們再計算給定了 F 和 H 時 I 和 D 的條件概率。

使用這些等式,我們可以得到以下概率:

因此,我們對 I 沒有任何額外的信息——我們第一個選擇正確的概率仍然是三分之一,我們的直覺也是如此。但是,現在車在第 3 扇門後的概率不再是三分之一,而是三分之二了。

所以如果我們更換選擇,那麼我們得到車的概率是三分之二;如果我們不換,我們得到車的概率是三分之一。

我們不使用圖模型也能得到同樣的答案,但圖模型給我們提供了一個框架,讓我們可以擴展到更大型問題。

結論

在這個概率圖模型教程中,我們瞭解了圖模型領域的一些基本術語,包括貝葉斯網絡、馬爾可夫網絡、條件概率分佈、勢函數和條件獨立。我們也探討了圖模型在三門問題上的應用。

在本博客的第二部分,我們將介紹一些用於參數估計和推理的算法以及另一個應用。

第二部分:參數估計和推理算法

在本概率圖模型教程的第一部分,Statsbot 團隊介紹了兩種類型的圖模型,即貝葉斯網絡和馬爾可夫網絡。另外還探討了圖模型的問題設定、條件獨立以及在三門問題上的應用。這一部分將介紹參數估計和推理,並還將探討另一個應用。

參數估計

1. 貝葉斯網絡

估計貝葉斯網絡的 CPD 表格中的數值很簡單,就是計算訓練數據中事件發生的次數。也就是說,如果要估計 p(SAT=s1|Intelligence=i1),我們只需要計算 SAT=s1 且 Intelligence = i1 的數據點在 Intelligence = i1 的數據點總量中所佔的比例。儘管這種方法看起來似乎是特定於這個問題的,但事實證明這樣獲得的參數能夠最大化被觀察到的數據的可能性。

2. 馬爾可夫網絡

上述計數方法對馬爾可夫網絡沒有統計學上的支持(因此會得到次優的參數)。所以我們需要使用更加複雜的技術。這些技術背後的基本思想是梯度下降——我們定義一些描述其概率分佈的參數,然後使用梯度下降來尋找能最大化被觀察數據的可能性的參數值。

最後,我們有了我們模型的參數,我們想在新數據上使用它們,也就是執行推理!

推理

圍繞推理的概率圖模型的文獻可謂汗牛充棟,原因有兩方面:

1. 推理就是我們打造這整個框架的原因——要根據我們已知的信息做出預測。

2. 推理在計算上很困難!在某些特定類型的圖中我們可以相當高效地執行推理,但一般而言圖的計算都很難。所以我們需要使用近似算法來在準確度和效率之間進行權衡。

我們可以使用推理來解答一些問題:

  • 邊際推理(marginal inference):尋找一個特定變量的概率分佈。比如,給定一個帶有變量 A、B、C 和 D 的圖,其中 A 取值 1、2 和 3,求 p(A=1)、p(A=2) 和 p(A=3)。

  • 後驗推理(posterior inference):給定某些顯變量 v_E(E 表示證據(evidence)),其取值爲 e,求某些隱藏變量 v_H 的後驗分佈 p(v_H|v_E=e)。

  • 最大後驗(MAP)推理(maximum-a-posteriori inference):給定某些顯變量 v_E,其取值爲 e,求使其它變量 v_H 有最高概率的配置。

解答這些問題本身可能就很有用,也可能被用作更大規模的任務的一部分。

接下來,我們將介紹一些用於解答這些問題的流行的算法,其中既有精準的算法,也有近似的算法。所有這些算法都既可用於貝葉斯網絡,也可用於馬爾可夫網絡。

變量消除(variable elimination)

使用條件概率的定義,我們可以將後驗分佈寫作:

我們可以怎樣計算上式中的分子和分母呢?讓我們用一個簡單的例子進行說明。考慮一個有三個變量的網絡,其聯合分佈定義如下:

假設我們想計算 p(A|B=1)。注意這意味着我們想計算 p(A=0|B=1) 和 p(A=1|B=1),這兩個值的和應該爲 1。使用上面的等式,我們可以寫:

分子是 A=0 且 B=1 的概率。我們不關心 C 的值。所以我們會把 C 的所有值都加起來。(這是由於基本概率 p(A=0, B=1, C=0) 和 p(A=0, B=1, C=1) 是互斥事件,所以它們的聯合概率 p(A=0, B=1) 就是各個概率的總和。)

所以我們將第 3 和 4 行加起來得到 p(A=0, B=1)=0.15。類似地,將第 7 和 8 行加起來得到 p(A=1, B=1)=0.40。另外,我們可以求所有包含 B=1 的行的總和來計算分母,即第 3、4、7、8 行,從而得到 p(B=1)=0.55。從而我們可以得到:

p(A=0|B=1) = 0.15 / 0.55 = 0.27

p(A=1|B=1) = 0.40 / 0.55 = 0.73

如果你仔細看看上面的計算,你可以發現我們做了一些重複的計算——將 3 和 4 行以及 7 和 8 行加了兩次。計算 p(B=1) 的更高效方法是直接將 p(A=0, B=1) 和 p(A=1, B=1) 的值加起來。這是變量消除的基本思想。

一般來說,當有很多變量時,你不僅可以使用分子的值來計算分母,而且分子本身也可能會包含重複的計算。你可以使用動態編程來高效地使用之前已計算出的值。

因爲我們一次對一個變量進行求和,從而可以消除這個變量,所以對多個變量進行求和的過程相當於逐個消除這些變量。所以我們將這個過程稱爲「變量消除」。

我們也可以相當簡單直接地將上述過程用於求解邊際推理或 MAP 推理問題。類似地,也可以容易地將上述思想推廣應用於馬爾可夫網絡。

變量消除的時間複雜度取決於圖結構以及你消除這些變量的順序。在最糟糕的情況下,時間複雜度會指數式增長。

置信度傳播(Belief Propagation)

我們剛纔看到的變量消除算法只會得到一個最終分佈。假設我們想找到所有變量的邊際分佈。除了多次運行變量消除之外,我們還有更聰明的方法。

假設你有一個圖結構了。爲了計算某個邊際,你需要對其在其它所有變量上的聯合分佈進行求和,這相當於將整個圖的信息聚合到一起。還有另一種聚合整個圖的信息的方法——每個節點都檢查其鄰近節點,然後以局部的方式近似變量的分佈。

然後,每一對相鄰節點都互相發送「消息」,這些消息中包含了其局部分佈。現在,每個節點都檢查其收到的消息,然後將它們聚合起來以更新變量的概率分佈。

在上圖中,C 聚合了來自鄰近節點 A 和 B 的信息,然後再發送一個消息給 D。然後 D 將這個消息與來自 E 和 F 的信息聚合起來。

這種方法的優點是如果你保存了你在每個節點處發送的消息,那麼將這些消息進行一次前向通過,然後再進行一次反向通過,就能讓所有節點都得到所有其它節點的信息。然後這個信息可以被用於計算所有的邊際,這是無法使用變量消除實現的。

近似推理

對於大型的圖模型來說,進行精準的推理可能極其耗時,爲此很多用於圖模型的近似推理算法被開發了出來,其中大多數都屬於下面兩類:

1. 基於採樣的近似推理

這些算法使用採樣來估計希望得到的概率。舉個簡單的例子。考慮這個場景:給定一個硬幣,你如何確定它被拋出後正面朝上的概率?最簡單的做法就是拋這個硬幣,比如拋 100 次,然後看其中正面朝上多少次。

這是一種用於估計正面朝上的概率的基於採樣的算法。對於概率圖模型領域內的更復雜的算法,你也可以使用類似的流程。基於採樣的算法還可以進一步分爲兩類。一類中的樣本是相互獨立的,比如上面拋硬幣的例子。這些算法被稱爲蒙特卡洛方法。

對於有很多變量的問題,生成高質量的獨立樣本是很困難的,因此我們就生成帶有依賴關係的樣本,也就是說每個新樣本都是隨機的,但鄰近上一個樣本。這種算法被稱爲馬爾可夫鏈蒙特卡洛(MCMC)方法,因爲這些樣本會形成一個馬爾可夫鏈(Markov chain)。一旦我們得到了樣本,我們就可以將其用於解答各種推理問題。

2. 變分法近似推理

變分法近似推理不是使用採樣,而是試圖通過分析的方式來近似所需的分佈。假設你寫出了計算相關分佈的表達式——不管這個分佈是邊際概率分佈還是後驗概率分佈。

通常這些表達式裏面有求和或積分,要精確評估是極其消耗計算資源的。要近似這些表達式,一種好方法是求解一個替代表達式,並且通過某種方法使該替代表達式接近原來的表達式。這就是變分法背後的基本思想。

當我們試圖估計一個複雜的概率分佈 p_complex 時,我們定義另一組更易於操作的概率分佈 P_simple,然後基於 P_simple 得到最接近於 p_complex 的概率分佈 p_approx。

應用:圖像去噪

現在讓我們將剛纔探討的一些思想用在真正的問題上。假設你有以下圖像:

現在假設這張圖像受到了隨機噪聲的污染,變成了有噪聲的圖像:

現在你的目標是恢復原始圖像。讓我們看看如何使用概率圖模型來實現。

首先第一步是思考哪些變量是觀察得到的,哪些變量不能觀察到,以及我們可以如何將它們連接起來構成一個圖。讓我們將有噪聲圖像中的每個像素都定義爲一個觀察到的隨機變量,並將基準圖像中的每個像素都定義爲一個未被觀察到的變量。由此,如果該圖像的大小爲 MxN,那麼觀察到的變量和未被觀察到的變量都各有 MN 個。讓我們將觀察到的變量表示爲 X_ij,未被觀察到的變量定義爲 Y_ij。每個變量都可取值 +1 或 -1(分別對應於黑色像素和白色像素)。給定觀察到的變量,我們希望找到未觀察到的變量的最有可能的值。這對應於 MAP 推理。

現在讓我們使用一些領域知識來構建圖結構。很顯然,在有噪聲圖像中的 (i,j) 位置觀察到的變量取決於在基準圖像中的 (i,j) 位置未觀察到的變量。原因是大多數時候它們是相等的。

我們還能得到什麼信息?對於基準圖像,鄰近的像素通常有一樣的值——在顏色變化的邊界不是這樣,但在每個單一顏色的區域內有這個性質。因此,如果 Y_ij 和 Y_kl 是鄰近像素,那麼我們將它們連接起來。

由此,我們得到圖結構:

其中,白色節點表示未被觀察到的變量 Y_ij,灰色節點表示觀察到的變量 X_ij。每個 X_ij 都連接到對應的 Y_ij,每個 Y_ij 都連接到它的相鄰節點。

注意這是一個馬爾可夫網絡,因爲圖像的像素之間不存在因果關係,因此這裏不適合使用貝葉斯網絡中有方向的箭頭。

我們的 MAP 推理問題可以用數學的方式寫出,如下:

這裏我們使用了最大對數似然(maximum log likelihood)計算中的一些常用的標準簡化技術。我們將使用 X 和 Y(沒有下標)來分別表示所有 X_ij 值和所有 Y_ij 值的集合。

現在,我們需要根據我們的圖結構來定義我們的聯合分佈 P(X,Y)。讓我們假設 P(X,Y) 由兩類因子組成——ϕ(X_ij, Y_ij) 和 ϕ(Y_ij,Y_kl),對應於圖中的兩類邊。接下來,我們按如下方式定義這些因子:

  • ϕ(X_ij, Y_ij) = exp(w_e X_ij Y_ij),其中 w_e 是一個大於 0 的參數。當 X_ij 和 Y_ij 相等時,這個因子取較大的值,當 X_ij 和 Y_ij 不同時就取較小的值。

  • ϕ(Y_ij, Y_kl) = exp(w_s Y_ij Y_kl),其中 w_s 也是一個大於 0 的參數。當 Y_ij 和 Y_kl 取值相等時,這個因子較大。

因此,我們的聯合分佈可由下式給出:

其中第二個求積中的 (i, j) 和 (k, l) 是相鄰的像素,Z 是一個歸一化常數。

將其插入到我們的 MAP 推理式中,可得:

注意我們已經丟棄了包含 Z 的項,因爲它不影響得到的解。

w_e 和 w_s 的值是基於基準圖像和噪聲圖像對,使用參數估計技術得到的。這個過程涉及到相當多的數學內容(儘管其最終只是在複雜函數上執行梯度下降),因此我們在此不再繼續深入了。我們假設我們已經得到了這兩個參數的值,即 w_e=8 且 w_s=10。

這個例子重點關注的是推理。有了這些參數後,我們需要求解上述 MAP 推理問題。我們可以使用置信度傳播的一種變體來實現,但事實上針對這種特定結構的圖還有一種簡單得多的算法,即迭代條件模式(ICM/iterated conditional mode)。

其基本思想是:在每個步驟選擇一個節點 Y_ij,然後檢查 Y_ij=-1 和 Y_ij=1 時 MAP 推理表達式的值,然後選擇值更高的那個。重複這個過程一定的迭代次數或直到收斂,通常就能得到相當好的結果。

你可以使用這裏的 Python 代碼來實現:https://github.com/prasoongoyal/image-denoising-mrf。

該算法返回的去噪後的圖像如下:

是不是相當好?當然,你也可以使用更加精巧的技術——既可以在圖模型內,也可以在圖模型外,從而可以得到更好的結果。但對這個例子來說,簡單的馬爾可夫網絡加上簡單的推理算法就足以得到相當好的結果了。

從定量的角度看,有噪聲圖像中有 10% 的像素與原圖像不同,而由我們的算法去噪後的圖像與原圖像僅有 0.6% 的像素差異。

需要注意,我們使用的圖是相當大的——這張圖像的尺寸是 440x300,所以節點總數接近 264 000。因此,在這樣的模型中進行精準的推理基本上是不可行的,我們用大多數算法(包括 ICM)所得到的結果都是局部最優的。

回顧

這裏我們簡要回顧一下我們在這篇分成兩部分的文章中所談到的核心概念:

  • 圖模型:圖模型是由圖結構構成的,其中節點表示隨機變量,邊表示變量之間的依賴關係。

  • 貝葉斯網絡:是有向圖模型,每個節點都有一個相關的條件概率分佈。

  • 馬爾可夫網絡:是無向圖模型,每個團都有一個相關的勢函數。

  • 條件獨立:根據圖中節點的連接方式,我們可以寫出這種形式的條件獨立陳述:「給定 Z,則 X 與 Y 相互獨立」。

  • 參數估計:根據給定的一些數據和圖結構來填充 CPD 表或計算勢函數。

  • 推理:給定一個圖模型,我們希望解答有關未被觀察的變量的問題,這些問題通常屬於以下問題範圍:邊際推理、後驗推理和 MAP 推理。

  • 在一般圖模型上的推理的計算非常困難。我們可以將推理算法分成兩大類——精準推理和近似推理。無環圖中的變量消除和置信度傳播是精準推理算法的例子。近似推理算法對大規模圖而言是必需的,而且通常屬於基於採樣的方法或變分法。

總結

在這兩部分教程中,我們解讀了概率圖模型的一些核心思想。現在你應該能夠理解:圖模型爲很多存在依賴關係的真實世界任務提供了可以解釋的建模方式。圖模型爲我們提供了一種用有原則的方式解決這些任務的方法。

在結束之前,需要指出這個教程並不完整——爲了保證內容簡潔直觀,很多細節都跳過了。要知道,關於概率圖模型的標準教科書可超過了一千頁!這個教程旨在提供一個起點,幫助初學者對這一領域產生興趣並在此基礎上使用更深度的資源進行進一步的深入學習。這裏列出了一些可以幫你更深入學習這一領域的資源:

  • Graphical Models in a Nutshell:https://ai.stanford.edu/~koller/Papers/Koller+al:SRL07.pdf

  • 圖模型教科書:《Probabilistic Graphical Models: Principles and Techniques》

  • 機器之心文章:想了解概率圖模型?你要先理解圖論的基本定義與形式

另外,在標準的機器學習教科書中應該也都會有幾章有關圖模型的內容。

原文鏈接:

Part 1:https://blog.statsbot.co/probabilistic-graphical-models-tutorial-and-solutions-e4f1d72af189

Part 2:https://blog.statsbot.co/probabilistic-graphical-models-tutorial-d855ba0107d1


文章來源:機器之心