“概率模型與計算機視覺”
林達華
美國麻省理工學院（MIT）博士

? ?? ? 上世紀60年代,?Marvin Minsky?在MIT讓他的本科學生?Gerald Jay Sussman用一個暑假的時間完成一個有趣的Project: “link a camera to a computer and get the computer to describe what it saw”。從那時開始，特別是David Marr教授于1977年正式提出視覺計算理論，計算機視覺已經走過了四十多年的歷史。可是，從今天看來，這個已入不惑之年的學科，依然顯得如此年輕而朝氣蓬勃。

在它幾十年的發展歷程中，多種流派的方法都曾各領風騷于一時。最近二十年中，計算機視覺發展最鮮明的特征就是機器學習與概率模型的廣泛應用。在這里，我簡單回顧一下對這個領域產生了重要影響的幾個里程碑：
●?1984年：Stuart Geman和Donald Geman發表了一篇先驅性的論文：Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images. 在這篇文章里，兩位Geman先生引入了一系列對計算機視覺以后的發展具有深遠影響的概念和方法：Markov Random Field (MRF),??Gibbs Sampling，以及Maximum a Posteriori estimate (MAP estimate)。這篇論文的意義是超前于時代的，它所建立的這一系列方法直到90年代中后期才開始被廣泛關注。 ●?1991年：Matthew Turk和Alex Pentland使用Eigenface進行人臉分類。從此，以矩陣的代數分解為基礎的方法在視覺分析中被大量運用。其中有代表性的方法包括PCA, LDA，以及ICA。
●?1995年：Corinna Cortes和Vladimir Vapnik提出帶有soft margin的Support Vector Machine (SVM)以及它的Kernel版本，并用它對手寫數字進行分類。從此，SVM大受歡迎，并成為各種應用中的基準分類器。 ●?1996年：Bruno Olshausen?和David Field?提出使用Overcomplete basis對圖像進行稀疏編碼(Sparse coding)。這個方向在初期的反響并不熱烈。直到近些年，Compressed Sensing在信號處理領域成為炙手可熱的方向。Sparse coding 在這一熱潮的帶動下，成為視覺領域一個活躍的研究方向。 ●?90年代末：Graphical Model和Variational Inference逐步發展成熟。1998年，MIT出版社出版了由Michale Jordan主編的文集：Learning in Graphical Models。 這部書總結了那一時期關于Graphical Model的建模，分析和推斷的主要成果——這些成果為Graphical Model在人工智能的各個領域的應用提供了方法論基礎。進入21世紀，Graphical Model和Bayesian方法在視覺研究中的運用出現了井噴式的增長。 ●?2001年：John Lafferty和Andrew McCallum等提出Conditional Random Field (CRF)。CRF為結構化的分類和預測提供了一種通用的工具。此后，語義結構開始被運用于視覺場景分析。 ●?2003年：David Blei等提出Latent Dirichlet Allocation。2004年：Yee Whye Teh?等提出Hierarchical Dirichlet Process。各種參數化或者非參數化的Topic Model在此后不久被廣泛用于語義層面的場景分析。 ●?雖然Yahn Lecun等人在1993年已提出Convolutional Neural Network，但在vision中的應用效果一直欠佳。時至2006年，Geoffrey Hinton等人提出Deep Belief Network進行layer-wise的pretraining，應用效果取得突破性進展，其與之后Ruslan Salakhutdinov提出的Deep Boltzmann Machine重新點燃了視覺領域對于Neural Network和Boltzmann Machine的熱情。

時間進入2013年，Probabilistic Graphical Model早已成為視覺領域中一種基本的建模工具。Probabilistic?Graphical Model的研究涉及非常多的方面。 限于篇幅，在本文中，我只能簡要介紹其中幾個重要的方面，希望能為大家提供一些有用的參考。

Graphical Model的基本類型

基本的Graphical Model 可以大致分為兩個類別：貝葉斯網絡(Bayesian Network)和馬爾可夫隨機場(Markov Random Field)。它們的主要區別在于采用不同類型的圖來表達變量之間的關系：貝葉斯網絡采用有向無環圖(Directed Acyclic Graph)來表達因果關系，馬爾可夫隨機場則采用無向圖(Undirected Graph)來表達變量間的相互作用。這種結構上的區別導致了它們在建模和推斷方面的一系列微妙的差異。一般來說，貝葉斯網絡中每一個節點都對應于一個先驗概率分布或者條件概率分布，因此整體的聯合分布可以直接分解為所有單個節點所對應的分布的乘積。而對于馬爾可夫場，由于變量之間沒有明確的因果關系，它的聯合概率分布通常會表達為一系列勢函數（potential function）的乘積。通常情況下，這些乘積的積分并不等于1，因此，還要對其進行歸一化才能形成一個有效的概率分布——這一點往往在實際應用中給參數估計造成非常大的困難。

值得一提的是，貝葉斯網絡和馬爾可夫隨機場的分類主要是為了研究和學習的便利。在實際應用中所使用的模型在很多時候是它們的某種形式的結合。比如，一個馬爾可夫隨機場可以作為整體成為一個更大的貝葉斯網絡的節點，又或者，多個貝葉斯網絡可以通過馬爾可夫隨機場聯系起來。這種混合型的模型提供了更豐富的表達結構，同時也會給模型的推斷和估計帶來新的挑戰。

Graphical Model的新發展方向

在傳統的Graphical Model的應用中，模型的設計者需要在設計階段就固定整個模型的結構，比如它要使用哪些節點，它們相互之間如何關聯等等。但是，在實際問題中，選擇合適的模型結構往往是非常困難的——因為，我們在很多時候其實并不清楚數據的實際結構。為了解決這個問題，人們開始探索一種新的建立概率模型的方式——結構學習。在這種方法中，模型的結構在設計的階段并不完全固定。設計者通常只需要設定模型結構所需要遵循的約束，然后再從模型學習的過程中同時推斷出模型的實際結構。

結構學習直到今天仍然是機器學習中一個極具挑戰性的方向。結構學習并沒有固定的形式，不同的研究者往往會采取不同的途徑。比如，結構學習中一個非常重要的問題，就是如何去發現變量之間的內部關聯。對于這個問題，人們提出了多種截然不同的方法：比如，你可以先建立一個完全圖連接所有的變量，然后選擇一個子圖來描述它們的實際結構，又或者，你可以引入潛在節點(latent node)來建立變量之間的關聯。

Probabilistic Graphical Model的另外一個重要的發展方向是非參數化。與傳統的參數化方法不同，非參數化方法是一種更為靈活的建模方式——非參數化模型的大小（比如節點的數量）可以隨著數據的變化而變化。一個典型的非參數化模型就是基于狄利克萊過程(Dirichlet Process)的混合模型。這種模型引入狄利克萊過程作為部件(component)參數的先驗分布，從而允許混合體中可以有任意多個部件。這從根本上克服了傳統的有限混合模型中的一個難題，就是確定部件的數量。在近幾年的文章中，非參數化模型開始被用于特征學習。在這方面，比較有代表性的工作就是基于Hierarchical Beta Process來學習不定數量的特征。

基于Graphical Model 的統計推斷 (Inference)

完成模型的設計之后，下一步就是通過一定的算法從數據中去估計模型的參數，或推斷我們感興趣的其它未知變量的值。在貝葉斯方法中，模型的參數也通常被視為變量，它們和普通的變量并沒有根本的區別。因此，參數估計也可以被視為是統計推斷的一種特例。

除了最簡單的一些模型，統計推斷在計算上是非常困難的。一般而言，確切推斷(exact inference)的復雜度取決于模型的tree width。對于很多實際模型，這個復雜度可能隨著問題規模增長而指數增長。于是，人們退而求其次，轉而探索具有多項式復雜度的近似推斷(approximate inference)方法。

主流的近似推斷方法有三種：

(1)基于平均場逼近(mean field approximation)的variational inference。這種方法通常用于由Exponential family distribution所組成的貝葉斯網絡。其基本思想就是引入一個computationally tractable的upper bound逼近原模型的log partition function，從而有效地降低了優化的復雜度。大家所熟悉的EM算法就屬于這類型算法的一種特例。

(2)Belief propagation。這種方法最初由Judea Pearl提出用于樹狀結構的統計推斷。后來人們直接把這種算法用于帶環的模型（忽略掉它本來對樹狀結構的要求）——在很多情況下仍然取得不錯的實際效果，這就是loop belief propagation。在進一步的探索的過程中，人們發現了它與Bethe approximation的關系，并由此逐步建立起了對loopy belief propagation的理論解釋，以及刻畫出它在各種設定下的收斂條件。值得一提的是，由于Judea Pearl對人工智能和因果關系推斷方法上的根本性貢獻，他在2011年獲得了計算機科學領域的最高獎——圖靈獎。

基于message passing的方法在最近十年有很多新的發展。Martin Wainwright在2003年提出Tree-reweighted message passing，這種方法采用mixture of trees來逼近任意的graphical model，并利用mixture coefficient和edge probability之間的對偶關系建立了一種新的message passing的方法。這種方法是對belief propagation的推廣。
Jason Johnson等人在2005年建立的walk sum analysis為高斯馬爾可夫隨機場上的belief propagation提供了系統的分析方法。這種方法成功刻畫了belief propagation在高斯場上的收斂條件，也是后來提出的多種改進型的belief propagation的理論依據。Thomas Minka在他PhD期間所建立的expectation propagation也是belief propagation的在一般Graphical Model上的重要推廣。

(3)蒙特卡羅采樣(Monte Carlo sampling)。與基于優化的方法不同，蒙特卡羅方法通過對概率模型的隨機模擬運行來收集樣本，然后通過收集到的樣本來估計變量的統計特性（比如，均值）。采樣方法有三個方面的重要優點。第一，它提供了一種有嚴謹數學基礎的方法來逼近概率計算中經常出現的積分（積分計算的復雜度隨著空間維度的提高呈幾何增長）。第二，采樣過程最終獲得的是整個聯合分布的樣本集，而不僅僅是對某些參數或者變量值的最優估計。這個樣本集近似地提供了對整個分布的更全面的刻畫。比如，你可以計算任意兩個變量的相關系數。第三，它的漸近特性通常可以被嚴格證明。對于復雜的模型，由variational inference或者belief propagation所獲得的解一般并不能保證是對問題的全局最優解。在大部分情況下，甚至無法了解它和最優解的距離有多遠。如果使用采樣，只要時間足夠長，是可以任意逼近真實的分布的。而且采樣過程的復雜度往往較為容易獲得理論上的保證。

蒙特卡羅方法本身也是現代統計學中一個非常重要的分支。對它的研究在過去幾十年來一直非常活躍。在機器學習領域中，常見的采樣方法包括Gibbs Sampling, Metropolis-Hasting Sampling (M-H),??Importance Sampling, Slice Sampling, 以及Hamiltonian Monte Carlo。其中，Gibbs Sampling由于可以納入M-H方法中解釋而通常被視為M-H的特例——雖然它們最初的motivation是不一樣的。

Graphical Model以及與它相關的probabilistic inference是一個非常博大的領域，遠非本文所能涵蓋。在這篇文章中，我只能蜻蜓點水般地介紹了其中一些我較為熟悉的方面，希望能給在這方面有興趣的朋友一點參考。
---------------------------------------------------------------------
? ?? ?針對林達華老師的這篇綜述，視覺計算研究論壇（以下簡稱「SIGVC BBS」： http://www.sigvc.org/bbs）提供了一個問答環節。林達華老師針對論壇師生提出的許多問題（如概率圖模型與目前很熱的深度神經網絡的聯系和區別）一一做了詳細解答，如下所示。如果大家還有別的疑問，可繼續提問，林老師有空會給予答復。

「SIGVC BBS」：最近深度學習受到機器學習和計算機視覺領域中研究人員的高度重視。然而，感覺有關深度學習一些理論并不是太完善。在計算機視覺領域，人們開始熱衷于將其作為工具來使用。相對來講，概率圖模型已經有其完善的理論體系了。那么我們是不是也可以完全用概率圖模型這套理論來解釋深度信念網絡和深度Boltzman機？

林達華老師：從數學形式上說，Deep Network和Boltzmann machine可以看成是Graphical Model的特例。但是，目前在Graphical Model體系中所建立的方法，主要適用于分析結構較為簡單的模型。而對于有多層latent layer的模型，現有的數學工具尚不能提供非常有效的分析。在NIPS 2012會議期間，我和Ruslan進行了交流。他們目前的主要工作方向還是進一步改善算法的性能（尤其是在大規模問題上的性能），以及推廣這類模型的應用，尚未涉及深入的理論分析。

「SIGVC BBS」：基于Dirichlet過程的混合模型解決了確定組件數量的問題，這里面是否引入了其它的問題呢（比方說其它參數的確定）？除了不需要確定組件數量這一點之外，非參數化的模型還有其它哪些優勢？

林達華老師：非參數化模型確實引入了其它參數，比如concentration parameter。但是，這個參數和component的個數在實用中是有著不同的影響的。concentration parameter主要傳達的是使用者希望形成的聚類粒度。舉個簡單的例子，比如一組數據存在3個大類，每個大類中有3個相對靠近的子類。這種情況下，聚成3類或者9類都是合理的解。如果concentration parameter設得比較大，最后的結果可能形成9類，如果設得比較小，則可能形成3類。但是，如果人為地固定類數，則很可能導致不合理的結果。

需要強調的是非參數化貝葉斯方法是一個非常博大的方向，目前的研究只是處于起步階段。而Dirichlet Process mixture model只是非參數方法的一個具體應用。事實上，DP像Gauss distribution一樣，都是一種有著良好數學性質的過程（分布），但是它們在實用中都過于理想化了。目前的一個新的研究方向就是建立更為貼近實際的非參數化過程。相比于傳統參數化方法而言，非參數化方法的主要優勢是允許模型的結構在學習的過程中動態變化（而不僅僅是組件的數量），這種靈活性對于描述處于不斷變化中的數據非常重要。當然，如何在更復雜的模型中應用非參數化方法是一個比較新的課題，有很多值得進一步探索的地方。

「SIGVC BBS」：文中后面提到的結構學習是不是這兩年比較火的Structured Output Prediction呢？他們的關系如何？Structured Percepton和Structured SVM應該就是屬于這個大類嗎？結構學習的輸出是樹結構和圖結構嗎？結構學習與圖像的層次分割或者層次聚類有關系嗎？

林達華老師：Structured Prediction (e.g. Structured SVM) 其實屬于利用結構，而不是我在文中所指結構學習。在大部分Structured Prediction的應用中，結構是預先固定的（比如哪些變量要用potential聯系在一起），學習的過程其實只是優化待定的參數。盡管如此，這些工作本身是非常有價值的，在很多問題中都取得了不錯的效果。

我在文中所提到的結構學習是指連結構本身都是不固定的，需要從數據中去學習。一般情況下，學習輸出的是圖或者樹的結構（以及相關參數）。這個topic其實歷史很長了，早期的代表性工作就是chow-liu tree。這是一種利用信息量計算尋找最優樹結構來描述數據的算法。Alan Willsky的小組近幾年在這個方向取得了很多進展。但是，總體而言這個方向仍舊非常困難，大部分工作屬于探索性的，并不特別成熟。目前在Vision中的應用不是特別廣泛。但是，我相信，隨著一些方法逐步成熟，進入實用階段，它的應用前景是非常不錯的。

「SIGVC BBS」：文中提到了Convolutional Deep Network、Deep Belief Network、Deep Boltzmann Machine等近年炙手可熱的神經網絡方法。那么，神經網絡和概率圖模型是不是本質上完全是一回事，只是觀察角度和歷史發展不同？感覺它們很多地方都很相似。深度學習里RBM學習的訓練算法與概率圖模型的學習推理算法有什么聯系和區別嗎？他們的結構模型有什么聯系和區別嗎？

林達華老師：這兩類模型所使用的數學方法是非常不同的。Graphical model的很多推斷和學習方法都有很深的數學根基。通過近十幾年的努力，大家已經逐步建立起整套的方法論體系對相關算法進行分析。Deep Learning目前并沒有什么有效的分析方法。Deep learning取得很好的性能，其中很多技巧性的方法(trick)起到了重要作用。至于為什么這些trick能導致更好的性能，目前還未能有一個很好的解釋。

我個人看來，這些技巧其實是很有價值的：一方面，它們確實在實踐中提高了性能；另外一方面，它們為理論上的探索提出了問題。但是，我覺得，有效回答這些問題需要新的數學工具（新的數學分析方法），這看來不是近期內能做到的。

「SIGVC BBS」：在一些論文中看到，采樣的方法（如Gibbs采樣）也有其缺點，一個是計算量比較大（computationally intensive），另一個是收斂檢測比較難。不知道這些說法是否有道理，或者目前這些問題是否有得到解決？

林達華老師：這里提到的兩個問題確實是Sampling的兩個主要的困難。對于這些問題，過去幾十年取得了很多進展，提出了很多新的采樣方法，但是困難仍然很大。但是，采樣能提供整個分布的信息，而且有漸近(asymptotic)的理論保證。這在很多情況下是一般的optimization方法做不到的。最近有新的研究嘗試結合Sampling和Optimization，在特定問題上有一些有趣的結果——比如，George Papandreou的Perturb-and-MAP.

「SIGVC BBS」：在計算機視覺中，視覺目標跟蹤問題已經用到了動態貝葉斯網絡方法。一些最近發表的自然圖像分割方法也用到LDA（Latent Dirichlet Allocation）。在受限的理想數據條件下，這些方法都取得了較好的結果。但是，不得不承認，我們在研究和應用的過程中，在心理上首先對應用概率圖模型有所畏懼（這里除我們已經用得較多較熟悉的MRF、CRF和Dynamic Bayesian network based visual tracking—condensation之外）。主要的解釋可能有：一方面，它不象很多正則化方法那樣其細節能被自我掌握、觀測和控制；另一方面，對于一個新的問題，我們需要不停地問自己：什么樣的設計（圖）是最好的。從而，在很多情況下，我們更愿意選擇使用那些正則化方法。比如，對小規模人臉識別，我們會選擇PCA＋LAD（SVM），對大一點的規模我們會考慮“特征選擇＋adaboost”框架。就計算機視覺，能否從實踐的角度給我們一點關于使用概率圖模型的建議。另外，在計算機視覺中，什么樣的問題更適合于采用概率圖模型方法來解決。

林達華老師：首先，Graphical model和其它的方法一樣，只是一種數學工具。對于解決問題而言，最重要的是選擇合適的工具，而不一定要選看上去高深的方法。對于普通的分類問題，傳統的SVM, Boost仍不失為最有效的方法。

Graphical model通常應用在問題本身帶有多個相互聯系的變量的時候。這個時候Graphical model提供了一種表達方式讓你去表達這些聯系。我覺得并不必要去尋求最優的設計圖，事實上，沒有人知道什么樣的圖才是最優的。實踐中，我們通常是根據問題本身建立一個能比較自然地表達問題結構的圖，然后通過實驗了驗證這個圖是不是合適的。如果不合適，可以根據結果分析原因對圖做出修正。

舉個具體的例子，比如對一個比賽視頻進行分析。那么可能涉及多個變量：攝像機的角度，背景，運動員的動作等等。那么這個問題可能就設計多個未知變量的推斷，這些變量間可能存在各種聯系。這個時候，Graphical model可能就是一種合適的選擇。

值得注意的是，選擇合適的圖有時候也需要一些經驗。比如分布的選擇上要注意形成conjugate，這樣往往容易得到簡易的推斷公式。了解各種分布的特性以及它們可能對最后結果的影響也是有幫助的。

from:?http://www.sigvc.org/bbs/thread-728-1-1.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的“概率模型与计算机视觉”-林达华的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。