Markov Chain和Gibbs分布到底是什麼關係？

12-31

如題。。。主要是指在機器學習方面的應用，以及他們和信息熵有什麼關聯嗎？
除了那些聯繫他們的定理和性質之外，最好能直觀的解釋一下。

如果題主問的是Gibbs Sampling的話：

Gibbs Sampling是Metropolis Hastings演算法的一個特例。MH演算法利用了馬爾可夫鏈的細緻平衡，從而獲得了聯合分布的採樣。有了聯合分布的採樣我們就可以得到邊緣分布，而這在貝葉斯推斷中求後驗分布有重要作用。

這篇文章寫得非常好 JinZhihui: LDA-math-MCMC 和 Gibbs Sampling

Update:這篇文章有個PDF版本, 叫作《LDA數學八卦》

Markov Chain和Gibbs分布應該沒有直接關係吧。倒是Markov隨機場和Gibbs分布有很大關係，Markov Chain是有向圖結構的，而Markov隨機場是無向圖結構的（當然，Markov性質還是基本類似的）。我個人覺得Gibbs分布只是Markov隨機場的一個表示方式而已（實際情況貌似是，它們是兩個定義，然後我們應該能證明它們是一致的）。然後由Gibbs分布能夠很方便的到處Log-Linear Model（貌似印象中我看到的都叫Gibbs Measure，不知道是不是一回事呢。貌似Gibbs Measure更一般一些？）。具體鄙人不是特別清楚，就不提和信息熵什麼關聯了（不懂啊，逃23333）。

~~~~~~~~

如果lz問得時Gibbs Sampling的話。。Gibbs Sampling是Markov Chain Monte Carlo這類演算法的一個。差不多就是構造一個markov chain，它的平穩分布為參數的後驗，採樣過程最終能夠收斂到它的平穩分布。實際的Gibbs Sampling很有意思，因為實際上我們並不知道我們要得Markov Chain到底什麼樣的（如果知道的話，我們就可以直接求出平穩分布了2333），但如果迭代最後收斂了，那麼我們就知道它什麼樣的。至少迭代的不動點是滿足我們要求的一個解。Sampling過程很有意思，它很難收斂到不穩定的不動點（因為Sampling過程包含很強的隨機因素，如果某個不動點的性質不夠好，很容易發生逃逸，從而收斂到其它性質更好的不動點）。

這個過程要說和信息熵有什麼關係的話，我覺得就是已知模型條件下的條件熵是逐漸變小的。因為隨著迭代的進行，模型包含的數據信息會越來越多，在已知模型的前提下，數據的期望表示代價就會變小（也就是條件熵會變小）。所以我們能用這個來判斷迭代的收斂與否哈。這個其實對有模型的概率模型都適用，感覺來說，資訊理論和概率論似乎有某種對偶關係。

感覺亂七八糟地說了一通哈，囧。。

gibbs分布是物理上的概念吧。

gibbs sampling是一種MCMC的採樣方法，可以由馬爾科夫鏈和概率轉移矩陣的性質推出其採樣分布最終收斂於聯合分布。

Restricted Boltzmann Machines (RBM) 中的sampling in an RBM 章節提及了一些. 具體我也不是太懂.

馬爾可夫隨機場(MRF)里定義了能量函數 $En(x)$

Gibbs分布就是每個MRF的概率分布 $p(x)propto e^{-En(x)}$

MRF與Markov Chain的關係，，高維上的擴展好啦

p.s.

對Gibbs採樣，從MCMC說起的話，後一個MC(Monte Carlo)的意思是普遍意義上的隨機方法，前一個MC(Markov Chain)則是指實現這種隨機的一種具體實現。只考慮p(x)分布穩定狀態時，為滿足細緻平穩條件，需補充一個轉移概率t(x)。這相當於在原轉移方程和目標分布條件下，構造新的平穩狀態的Markov Chain。（做等價提升得到MH）

由MH到Gibbs sampling很直觀，就是在不同獨立方向i上，p(x_i|x_{-i})就能滿足detailed balance condition，所以可以直接各自獨立進化。

馬爾可夫鏈有個重要性質就是n次迭代後能夠收斂達到穩態。而馬爾可夫採樣過程就是每次根據轉移概率生成採樣矩陣最終達到穩態。普通的採樣過程有個拒絕概率，說的是本次採樣不可信。gb採樣是優化的採樣方法，使得每次採樣都被認可，提高了採樣效率。…………………… 建議先熟悉馬爾可夫性質，然後學習蒙特卡洛，採樣過程，最後再理解gb採樣。順帶說一句，真心跪拜想出蒙特卡洛方法的大牛們手機作答，真心蛋疼

這個問題問得太混亂了...

Gibbs Sampling只是MCMC的一個特例

MCMC為什麼能用，是因為proposal distribution和accept/reject機制使得其能構造出一個滿足detailed balanced的transition kernel（也就是Markov Chain裡面的transition probability matrix）。這個Markov Chain是ergodic的，他的stationary distribution剛好是我們想要的posterior distribution。然後配上Ergodic Theorem，我們就能為所欲為了。

注意Gibbs Sampler並不滿足detailed balance，他只滿足global balance。

最近組內也討論了這個問題, 說下結論.

首先介紹非時齊(time inhomogeneous)Markov Chain, 它在有多個狀態轉移矩陣Q, 各個Q的極限分布(平穩分布)一樣, 則整個Markov Chain也也具有相同的極限分布.

注意, 我們並沒有要求每個Q是ergodic的. 而整個Markov Chain仍然可以是ergodic的.

Gibbs Sampling的本質就是非時齊Markov Chain, 要採樣的隨機變數有n維, 則我們在採樣過程中會對應n個條件分布, 進而則對應n個Q.

顯然每個Q不是ergodic的, 因為它只允許隨機變數在一個維度上改變. 而整個Markov Chain是ergodic的.

上面的過程完全對應普通的Gibbs Sampling. 同時大家也思考(不是很難想清楚): collapsed Gibbs Sampling是如何對應上面概念的.

Gibbs抽樣方法是 Markov Chain Monte Carlo（MCMC）方法的一種，也是應用最為廣泛的一種。

在統計學和統計物理學中，gibbs抽樣是馬爾可夫鏈蒙特卡爾理論（MCMC）中用來獲取一系列近似等於指定多維概率分布（比如2個或者多個隨即變數的聯合概率分布）觀察樣本的演算法。

MCMC是用於構建 Markov chain隨機概率分布的抽樣的一類演算法。MCMC有很多演算法，其中比較流行的是Metropolis-Hastings Algorithm，Gibbs Sampling是Metropolis-Hastings Algorithm的一種特殊情況。

在我的理解中，Gibbs sampling是 MCMC方法的一種特例。當我們採樣幾個變數，但是不知道其聯合分布，但是知道幾個變數相互之間所有的條件分布時，我們可以用其來獲取一些近似觀察樣本。

　　關於馬爾科夫鏈可以自己看看維基百科的定義：

馬爾可夫鏈（英語：Markov chain），又稱離散時間馬可夫鏈，為狀態空間中經過從一個狀態到另一個狀態的轉換的隨機過程。該過程要求具備「無記憶」的性質：下一狀態的概率分布只能由當前狀態決定，在時間序列中它前面的事件均與之無關。這種特定類型的「無記憶性」稱作馬可夫性質。馬爾科夫鏈作為實際過程的統計模型具有許多應用。
在馬爾可夫鏈的每一步，系統根據概率分布，可以從一個狀態變到另一個狀態，也可以保持當前狀態。狀態的改變叫做過渡，與不同的狀態改變相關的概率叫做過渡概率。隨機漫步就是馬爾可夫鏈的例子。隨機漫步中每一步的狀態是在圖形中的點，每一步可以移動到任何一個相鄰的點，在這裡移動到每一個點的概率都是相同的（無論之前漫步路徑是如何的）。

　　然後我們用MCMC產生馬爾科夫鏈時，由平穩分布得

$lim_{n ightarrow infty }{p_{ij}^{(n)} } =pi _{j}$

所以當n很大時，由轉移概率和分布相同（收斂）。所以我們通過馬爾科夫鏈就可以進行採樣了。在其中我們需要知道pij，也就是轉移概率，以及我們得到的採樣是否保留的測量。

最後關於Gibbs Sampling的演算法：如果不知道分布概率，但知道幾個變數相互之間所有的條件分布，也就是後驗分布概率。我們可以根據這些後驗分布概率得到馬爾科夫鏈。然後進行sampling。

剛看到PGM裡面關於Gibbs分布的介紹，上圖的無向圖的最大團是 $phi_1(A,B,D)$ 和 $phi_2(B,C,E)$ ,Gibbs分布 $P(X)=prod_i phi_i=phi_1(A,B,D) imes phi_2(B,C,E)$