随机近似的核心：蒙特卡洛
随机近似⽅法的核⼼是蒙特卡洛⽅法，主要是⽤采样的⽅式来进⾏随机近似，来实现数值积分等⽬标。
例如我们要求函数$f(Z)$关于分布$p(Z \mid X)$的期望，从期望的定义我们知道，求期望的本质就是求积分：
\[E_{z \mid x}(f(z)) = \int_z p(z \mid x)f(z)dz\]但是这个积分往往是非常难求的， 而随机近似的方法核心就是蒙特卡洛方法， 它用采样的方法来实现数值积分的目标。
首先我们从原始分布$p(z \mid x)$中采样出$N$个样本点：
\[z^{(1)}, z^{(2)}, z^{(3)}, ..., z^{(N)} \thicksim p(z \mid x)\]然后依据大数定律，用样本均值来模拟积分的真实结果：
\[\frac{1}{N} \sum_{i=1}^{N} f(z^{(i)}) \approx \int_z p(z \mid x)f(z)dz\]如果我们直接令这个函数$f(z) = z$ ，那么通过上述⽅法求出的就是分布$p(z \mid x)$的期望。
这种基于蒙特卡洛⽅法的近似⽅法，思想上⾮常简单直观，但是其中有⼀个问题⽬前看上去⽆法跨越：那就是如果$p(z \mid x)$⽐较复杂，我们似乎很难直接从中采样出服从概率分布的⼀组样本点。
于是，为了解决这个问题，就派⽣出了两种⽅案，⼀个称之为接受—拒绝采样，⼀个称之为是重要性采样。
它们都是基于⼀个事实，那就是⽬标分布$p(z)$⽆法直接采样，而我们引⼊⼀个提议分布$q(z)$，这个分布可以是任意的，⽐如均匀分布、⾼斯分布等等，怎么好 采样就怎么来。
实践 1：接受—拒绝采样
对于⽬标分布$p(z)$，难以直接对其采样，那么我们引⼊⼀个易于采样的提议分布$q(z)$，并且寻找到⼀个常数$M$，使得对于任意的样本$z_i$， 都能够满足：$Mq(z_i) \geq p(z_i)$。
我们首先引入一个接受率参数： $\alpha = \frac{p(z^{(i)})}{Mq(z^{(i)})}$， 由于我们使得$Mq(z_i) \geq p(z_i)$， 因此这个接受率参数$\alpha$一定满足： $0 \leq \alpha \leq 1$。
假设我们要采样 N 个服从$p(z)$⽬标分布的样本点，那么采样的过程如下：
- 从提议分布$q(z)$中采样得到一个样本点$z^{(i)}$；
- 从0到1的均匀分布随机采样一个值， $u \thicksim U(0, 1)$；
- 进行判断， 如果$u \leq \frac{p(z^{(i)})}{Mq(z^{(i)})}$， 将其纳入到我们的样本集list中， 否则丢弃这个采样值$z^{(i)}$。
循环往复 N 次之后，样本集 list 中的所有的样本点，近似地就服从⽬标分布$p(z)$了。
这种采样的⽅法⾮常简单，但显然也存在着问题，那就是采样的效率⾮常依赖于提议分布$q(z)$的选择，因为只有当我们的接受率越⾼的时候，才意味着⽆效的采样次数越少，整个采样过程中丢弃的样本点就越少，采样 效率就越⾼。
而从数值上来说，只有当 $Mq(z)$越接近$p(z)$的情况下，接受率就越⾼，但是由于我们并不清楚⽬标分布$p(z)$的分布形态，因此选取⼀个好的提议分布往往是困难的。
实践 2：重要性采样
第⼆种⽅法我们称之为是重要性采样，⽤它主要是为了获取⽬标分布$p(z)$的期望。同样的， $p(z)$是⼀个我们难以直接进⾏样本采样的分布，我们引⼊⼀个适合采样的建议分布$q(z)$，下⾯我们来看看如何求得函数$f(z)$关于⽬标分布$p(z)$的期望：
\[E_{p(z)}[f(z)] = \int p(z)f(z)dz = \int \frac{p(z)}{q(z)}f(z)q(z)dz\]此时我们就可以换⼀个视⻆去看待这个问题，这个式⼦可以看做是求$\frac{p(z)}{q(z)}f(z)$这整个式⼦关于提议分布$q(z)$的期望，这个转换意义⾮常⼤，由此我们可以通过从提议分布$q(z)$中抽取⼀系列样本点，$z_i \thicksim q(z)$：
\[z_1, z_2, z_3, z_4, ..., z_N\]利用大数定律， 实现期望值的近似：
\[\frac{1}{N} \sum_{i=1}^N f(z_i)\frac{p(z_i)}{q(z_i)} \approx \int \frac{p(z)}{q(z)}f(z)q(z)dz\]如果仅仅是样本Z的期望， 那么直接让$f(z) = z$就可以了。
重要性采样的“重要”二字， 指的就是$\frac{1}{N}\sum_{i=1}^N f(z_i)\frac{p(z_i)}{q(z_i)}$中每一个$f(z_i)$所对应的权重$\frac{p(z_i)}{q(z_i)}$， 但是在重要性采样的过程中，同样涉及到提议分布的选择过程，选择一个与目标分布$p(z)$相似程度高的提议分布，是保证采样效率高的一个前提条件。
总结
上⾯介绍的两类基于蒙特卡洛的采样⽅法，其获取样本的底层逻辑是基于⼀个提议分布的随机采样，⼤多数情况下很难选择 ⼀个合适的提议分布$q(z)$，往往会造成采样的效率⾮常低，关键点就在于如何更好地获得⼀组样本，因为获取样本之后的操作都是基于⼤数定理去逼近期望，都是⼀样的了。
