1舞箍、推斷問題
基于概率圖定義的聯(lián)合概率分布压储，我們能對目標(biāo)變量的邊際分布或以某些可觀測變量為條件的條件分布進(jìn)行推斷逝她。在馬爾可夫網(wǎng)中技竟，變量的聯(lián)合分布被表示稱極大團(tuán)的勢函數(shù)的乘積，于是勺拣，給定參數(shù)θ求解某個(gè)變量x的分布奶赠，就變成對聯(lián)合分布中其他無關(guān)變量進(jìn)行積分的過程，這稱為邊際化宣脉。
概率圖模型的推斷方法大致可分為兩類车柠，第一類是精確推斷方法剔氏，希望能計(jì)算出目標(biāo)變量的邊際分布或條件分布的精確值塑猖，遺憾的是，一般情形下谈跛，此類算法的計(jì)算復(fù)雜度隨著極大團(tuán)規(guī)模的增長呈指數(shù)增長羊苟，適用范圍有限，第二類是近似推斷方法感憾，希望在較低的時(shí)間復(fù)雜度下獲得原問題的近似解蜡励，此類方法更為常用。
兩種代表性的精確推斷方法分別是變量消法和信念傳播。
而兩種代表性的近似推斷方法分別是MCMC采樣和變分推斷凉倚。
這里兼都，我們只介紹一下MCMC采樣，因?yàn)長DA中的gibbs采樣算法也是一種MCMC采樣算法的特例稽寒。
2扮碧、MCMC采樣
對于給定的概率分布p(x),我們希望能有便捷的方式生成它對應(yīng)的樣本，由于馬爾可夫鏈能夠收斂到平穩(wěn)分布杏糙，于是一個(gè)很漂亮的想法是：如果我們能構(gòu)造一個(gè)轉(zhuǎn)移矩陣偽P的馬爾可夫鏈慎王，使得該馬爾可夫鏈的平穩(wěn)分布恰好是p(x),那么我們從任何一個(gè)初始狀態(tài)x0出發(fā)沿著馬爾可夫鏈轉(zhuǎn)移，得到一個(gè)轉(zhuǎn)移序列x0宏侍，x1赖淤，x2，....xn,xn+1,如果馬爾可夫鏈在第n步已經(jīng)收斂了谅河，于是我們就得到了p(x)的樣本xn咱旱，xn+1....
好了，有了這樣的思想绷耍，我們怎么才能構(gòu)造一個(gè)轉(zhuǎn)移矩陣莽龟，使得馬爾可夫鏈最終能收斂即平穩(wěn)分布恰好是我們想要的分布p(x)呢？我們主要使用的還是我們的細(xì)致平穩(wěn)條件（Detailed Balance）锨天，再來回顧一下：
假設(shè)我們已經(jīng)又一個(gè)轉(zhuǎn)移矩陣為Q的馬爾可夫鏈(q(i,j)表示從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的概率),顯然通常情況下：
也就是細(xì)致平穩(wěn)條件不成立毯盈，所以p(x)不太可能是這個(gè)馬爾可夫鏈的平穩(wěn)分布，我們可否對馬爾可夫鏈做一個(gè)改造病袄，使得細(xì)致平穩(wěn)條件成立呢搂赋？比如我們引入一個(gè)α(i,j)，從而使得：
那么問題又來了益缠，取什么樣的α(i,j)可以使上等式成立呢脑奠？最簡單的，按照對稱性：
于是燈飾就成立了幅慌，所以有：
于是我們把原來具有轉(zhuǎn)移矩陣Q的一個(gè)很普通的馬爾可夫鏈宋欺，改造為了具有轉(zhuǎn)移矩陣Q'的馬爾可夫鏈，而Q'恰好滿足細(xì)致平穩(wěn)條件胰伍，由此馬爾可夫鏈Q(jìng)'的平穩(wěn)分布就是p(x)!
在改造Q的過程中引入的α(i,j)稱為接受率齿诞，物理意義可以理解為在原來的馬爾可夫鏈上，從狀態(tài)i以q(i,j)的概率跳轉(zhuǎn)到狀態(tài)j的時(shí)候骂租，我們以α(i,j)的概率接受這個(gè)轉(zhuǎn)移祷杈，于是得到新的馬爾可夫鏈Q(jìng)'的轉(zhuǎn)移概率q(i,j)α(i,j)。
假設(shè)我們已經(jīng)又一個(gè)轉(zhuǎn)移矩陣Q渗饮，對應(yīng)的元素為q(i,j)但汞，把上面的過程整理一下宿刮，我們就得到了如下的用于采樣概率分布p(x)的算法：
以上的MCMC算法已經(jīng)做了很漂亮的工作了，不過它有一個(gè)小問題私蕾，馬爾可夫鏈Q(jìng)在轉(zhuǎn)移的過程中接受率α(i,j)可能偏小僵缺，這樣采樣的話容易在原地踏步，拒絕大量的跳轉(zhuǎn)踩叭，這是的馬爾可夫鏈便利所有的狀態(tài)空間要花費(fèi)太長的時(shí)間谤饭，收斂到平穩(wěn)分布p(x)的速度太慢，有沒有辦法提升一些接受率呢懊纳？當(dāng)然有辦法揉抵，把α(i,j)和α(j,i)同比例放大，不打破細(xì)致平穩(wěn)條件就好了呀嗤疯，但是我們又不能無限的放大冤今，我們可以使得上面兩個(gè)數(shù)中最大的一個(gè)放大到1，這樣我們就提高了采樣中的跳轉(zhuǎn)接受率茂缚，我們?nèi)戏罢。?/p>
于是經(jīng)過這么微小的改造，我們就得到了Metropolis-Hastings算法脚囊，該算法的步驟如下：
