[科普中國]-梅特羅波利斯－黑斯廷斯算法

梅特羅波利斯－黑斯廷斯算法（英語：Metropolis–Hastings algorithm）是統(tǒng)計學(xué)與統(tǒng)計物理中的一種馬爾科夫蒙特卡洛（MCMC）方法，用于在難以直接采樣時從某一概率分布中抽取隨機樣本序列。

簡介梅特羅波利斯－黑斯廷斯算法（英語：Metropolis–Hastings algorithm）是統(tǒng)計學(xué)與統(tǒng)計物理中的一種馬爾科夫蒙特卡洛（MCMC）方法，用于在難以直接采樣時從某一概率分布中抽取隨機樣本序列。得到的序列可用于估計該概率分布或計算積分（如期望值）等。梅特羅波利斯－黑斯廷斯或其他MCMC算法一般用于從多變量（尤其是高維）分布中采樣。對于單變量分布而言，常會使用自適應(yīng)判別采樣（adaptive rejection sampling）等其他能抽取獨立樣本的方法，而不會出現(xiàn)MCMC中樣本自相關(guān)的問題。

該算法的名稱源于美國物理學(xué)家尼古拉斯·梅特羅波利斯與加拿大統(tǒng)計學(xué)家W·K·黑斯廷斯。1

算法假設(shè)為目標(biāo)概率分布。梅特羅波利斯－黑斯廷斯算法的過程為：

1.初始化：

選定初始狀態(tài)；令；

2.迭代過程:

**生成：**從某一容易抽樣的分布中隨機生成候選狀態(tài)；

**計算：**計算是否采納候選狀態(tài)的概率；

接受或拒絕：

從的均勻分布中生成隨機數(shù)；

如，則接受該狀態(tài)，并令；

如，則拒絕該狀態(tài)，并令（復(fù)制原狀態(tài)）；

**增量：**令.2

馬爾科夫蒙特卡洛馬爾科夫蒙特卡洛（英語：Markov chain Monte Carlo，MCMC）方法（含隨機游走蒙特卡洛方法）是一組用馬氏鏈從隨機分布取樣的算法，之前步驟的作為底本。步數(shù)越多，結(jié)果越好。

創(chuàng)建一個具有期望屬性的馬氏鏈并非難事，難的是如何決定通過多少步可以達到在許可誤差內(nèi)的穩(wěn)定分布。一個好的馬氏鏈具有快速混合——從開始階段迅速獲得的一個穩(wěn)定狀態(tài)——請參考馬氏鏈最大時間。

因于初始樣本，最常見的MCMC取樣只能近似得到分布。復(fù)雜的MCMC改進算法如過往耦合，但是會消耗更多的計算資源和時間。

典型用法是模擬一個隨機行走的行人來進行路徑優(yōu)化等。每一步都算作是一個狀態(tài)。而統(tǒng)計經(jīng)過次數(shù)最多的地方將在下一步中更有可能為目的地。馬氏蒙特卡洛方法是一種結(jié)合了蒙特卡羅法的解決方案。但不同于以往的蒙特卡洛integration是統(tǒng)計獨立的，MCMC中的是統(tǒng)計相關(guān)的。

本方法的相關(guān)應(yīng)用包括：貝葉斯統(tǒng)計、計算物理、計算生物以及計算語言學(xué)，此外還有Gill先生的一些著作。3

參見貝葉斯推理

本詞條內(nèi)容貢獻者為:

李嘉騫 - 博士 - 同濟大學(xué)