蒙特卡罗方法

蒙特卡罗方法的总结，包括拒绝性采样、重要性采样等，以及马尔可夫链蒙特卡罗方法(MCMC，Markov Chain Monte Carlo), Metropolis-Hastings采样、Gibbs采样等。

给定一个概率密度函数$p(x)$，生成一组符合该分布的样本，也即采样问题。通常需要转化为一些好采样的分布（下面记作$q(x)$，比如均匀分布、正态分布等)。最直观的方法是利用均匀分布和逆变换。

逆变换法

给定随机变量$X$和其分布函数$F(x)$, 根据概率论知识，$F(X) \sim U(0,1)$, 证明只需要根据分布函数的定义即可，此处从略。

对此，根据逆变换$X \sim F^{-1}(U)$， 即可以先从标准均匀分布中你采样，之后进行逆变换即可得到最终的采样结果。

但逆变换法的弊端是，不是所有的分布函数的逆函数都有显式表达。下面介绍的及几种采样方法都不需要逆函数，直接作用在分布函数（或概率密度函数）之上。

拒绝性采样

若存在$k$, 满足$p(x) \le k q(x)$, 则可以通过先对$q(x)$进行采样得到后，生成均匀变量$U$, 当$U \le \frac{p(x)}{kq(x)}$的时候才选择性地接受采样结果，即可以得到对$p(x)$的采样结果。

下面我们证明，$P(x \vert Accept) = p(x)$, 也即拒绝性采样的结果为$p(x)$, 证明只需用到贝叶斯公式。

$P(x \vert Accept) = \frac{P(x,Accept)}{P(Accept)}$

其中,$P(x, Accept)= \frac{p(x)}{kq(x)}q(x) = \frac{p(x)}{k}$

而且，$P(Accept) = \int P(x,Accept) dx = \frac{1}{k}$

因此，$P(x \vert Accept) = p(x)$

重要性采样

很多时候需要计算$E_{p(x)} [f(x)] = \int f(x) p(x) dx$ , 比如在概率图模型中经常需要计算上述积分，朴素的方法是根据上述的拒绝行采样采样出$p(x)$计算积分，但是利用类似的思想可以直接计算出该积分表达式。

$E_{p(x)} [f(x)] = \int f(x) p(x) dx = \int f(x) \frac{p(x)}{q(x)}q(x) dx $

令$w(x) = \frac{p(x)}{q(x)}$, 称为重要性系数，则$E_{p(x)} [f(x)] = E_{q(x)}[f(x)w(x)]$

从而只需对$q(x)$进行采样即可计算上述积分。

Metropolis-Hastings采样

Metropolis-Hastings采样基于马尔可夫链，首先需要知道马尔可夫链和细致平衡和平衡条件。

对于转移矩阵$P$和概率分布$\pi$, 若$\pi_i P_{ij} = \pi_j P_{ji}$ 则称为满足细致平衡条件，显然此时一定满足平衡条件，$P \pi = \pi$.

也即细致平衡条件是比平衡条件更强的条件。

给定任意马尔可夫链的转移矩阵$Q$, 类似拒绝性采样的思想，Metropolis-Hastings采样构造了一个接受率$\alpha$，利用$\alpha$构造了一个新的转移矩阵$P$,使得$P$满足细致平衡条件所处的概率分布为$p$,也即所要采样的概率分布。

显然，$p_i Q_{ij} p_j Q_{ji} = p_j Q_{ji} p_i Q_{ij}$,令$\alpha_{ij} = p_j Q_{ji},P_{ij} = \alpha_{ij} Q_{ij}$， 则有，

$p_i P_{ij} = p_j P_{ji}$，也即构造出了一个满足细致平衡条件的马尔可夫链。

因此，只需要任意给定一个转移矩阵$Q$，然后进行上述构造得到$P$，沿着$P$不断进行转移即可得到采样结果。

Metropolis-Hastings采样算法要求尽可能提高接受率$\alpha$ ,显然对$\alpha$同比例放大相同的背熟细致平衡条件仍然满足，因此取

$\alpha_{ij} = \min ( \frac{p_j Q_{ji}}{p_i Q_{ij}},1)$,可以获得尽可能大的接受率。

Gibbs采样

对于高维联合分布的采样，可以采用Gibbs采样，原理同样基于细致平衡条件的构造。

首先考虑二维的情况，对于横坐标相同的两个点$A(x,y_1),B(x,y_2)$

观察到，$p(x,y_1)p(y_2 \vert x) = p(x)p(y_1 \vert x) p(y_2 \vert x) = p(x,y_2)p(y_1 \vert x)$

基于上述观察，如果取条件概率作为固定$x$维度上的转移概率，进行转移，则满足细致平衡条件。对于其他维度，同理。

而且容易验证，如果沿着任意一个维度的直线上的两个点都满足细致平衡条件，则空间内的任意两个点也满足细致平衡条件，证明是显然的，写成转移的形式即可。

因此按照上述的方法构造高维的马尔可夫链进行转移，每次转移固定其他$n-1$维只转移其中1个维度，直到收敛，即可得到高维联合分布的一个样本。