Metropolis-Hastings采样算法在MCMC中的应用

需积分: 11 179 浏览量更新于2024-09-01 收藏 191KB PDF 举报

"Metropolis算法是Markov Chain Monte Carlo (MCMC)方法中的一种，它在统计物理和计算科学中广泛使用，特别是在处理高维概率分布的采样问题上。这个算法是由Metropolis、Rosenbluth、Rosenbluth、Teller和Teller在1953年提出的，后来被Hastings在1970年推广，形成了现在所说的Metropolis-Hastings算法。本文可能涵盖了这两个重要人物的工作，以及如何应用他们的方法来解决概率计算问题。 Metropolis算法的核心思想是通过构建一个马尔科夫链，使得在足够长的时间后，链的每个状态的访问概率与目标分布的概率成正比，从而实现对目标分布的等概率采样。在这个过程中，算法会进行一系列的随机漫步，每次尝试从当前状态转移到一个新的状态。转移的接受与否依据一个接受率函数，该函数考虑了新状态和旧状态的相对概率。描述中的"rejection algorithm"是John von Neumann提出的一种基础的模拟方法，用于从特定的概率分布中采样。这种方法简单来说就是：首先从一个容易生成的分布（通常是均匀分布）中进行采样，然后根据目标分布的概率比较判断是否接受这个样本。如果新的样本被接受，则用于生成样本的分布就起到了近似目标分布的作用；如果不接受，就继续下一次采样，直到找到一个合适的样本。在实际应用中，Metropolis算法的步骤通常包括以下几步： 1. 初始化：从一个状态开始（可以是任意状态）。 2. 提议移动：根据某个提议分布（如随机行走）生成一个新的状态。 3. 计算接受率：比较新状态和旧状态在目标分布下的概率，计算接受新状态的概率。 4. 决策：以计算出的接受率为概率接受新状态，否则保持旧状态。 5. 重复：不断执行上述步骤，形成一个马尔科夫链。 Metropolis-Hastings算法是对原始Metropolis算法的扩展，允许提议分布不对称，即新状态到旧状态的概率不一定等于旧状态到新状态的概率。这增加了算法的灵活性，使得在更复杂的情况下也能有效采样。在解决如统计物理中的粒子系统、机器学习中的参数估计、贝叶斯分析等领域的问题时，Metropolis算法及其变体是不可或缺的工具。通过大量的采样，MCMC方法能够逼近难以直接解析的复杂概率分布，从而获得其性质和参数的估计。文章中提到的背景故事，关于Stan Ulam在医院计算纸牌游戏的概率，以及John von Neumann提出的拒绝算法，都是科学史上有趣的小插曲，展示了这些统计方法的起源和早期应用。这两个故事也突显了随机抽样在解决实际问题中的价值和重要性。"

JANUARY/FEBRUARY 2000 65

T HEME ARTICLE

he story goes that Stan Ulam was in

a Los Angeles hospital recuperating

and, to stave off boredom, he tried

computing the probability of getting

a “perfect” solitaire hand. Before long, he hit on

the idea of using random sampling: Choose a

solitaire hand at random. If it is perfect, let count

= count + 1; if not, let count = count. After M sam-

ples, take count/M as the probability. The hard

part, of course, is deciding how to generate a

uniform random hand. What’s the probability dis-

tribution to draw from, and what’s the algorithm

for drawing a hand?

Somewhat later, John von Neumann provided

part of the answer, but in a different context. He

introduced the rejection algorithm for simulating

neutron transport. In brief, if you want to sample

from some speciﬁc probability distribution, sim-

ply sample from any distribution you have

handy, but keep only the good samples. (Von

Neumann discussed his approach in a letter to

Bob Richtmeyer [11 Mar. 1947] and in a later

letter to Ulam [21 May 1947]. Interestingly, the

letter to Richtmeyer contains a fairly detailed

program for the Eniac, while the one to Ulam

gives an explanation augmented by what we

would today call pseudocode.)

Since the rejection method’s invention, it has

been developed extensively and applied in a wide

variety of settings. The Metropolis Algorithm

can be formulated as an instance of the rejection

method used for generating steps in a Markov

chain. This is the approach we will take.

The rejection algorithm

First, let’s look at the setup for the rejection

algorithm itself. We want to sample from a pop-

ulation (for example, solitaire hands or neutron

trajectories) according to some probability dis-

tribution function,

, that is known in theory but

hard to sample from in practice. However, we

can easily sample from some related probability

distribution function

So we do this:

1. Use

to select a sample, x.

2. Evaluate

(x). This should be easy, once

we have x.

THE METROPOLIS ALGORITHM

The Metropolis Algorithm has been the most successful and inﬂuential of all the members of

the computational species that used to be called the “Monte Carlo Method.” Today, topics

related to this algorithm constitute an entire ﬁeld of computational science supported by a

deep theory and having applications ranging from physical simulations to the foundations

of computational complexity.

ISABEL BEICHL

NIST

FRANCIS SULLIVAN

IDA/Center for Computing Science

the Top

下载后可阅读完整内容，剩余4页未读，立即下载

Quant0xff

粉丝: 1w+
资源: 459

Metropolis-Hastings采样算法在MCMC中的应用

最新资源