第17章 蒙特卡罗方法
随机算法可大致分为Las Vegas算法和蒙特卡罗算法
- Las Vegas算法精确地返回一个正确答案或失败
- 占用随机量的计算资源
- 蒙特卡罗算法消耗固定的计算量返回具有随机大小的错误
- 增大计算量消耗能减少随机错误
蒙特卡罗采样基础
当我们需要以较小的代价近似许多项的和或某个积分时，采样是一种灵活的选择 当无法精确计算和或积分（如具有指数数量项的和），常用蒙特卡罗采样近似 蒙特卡罗采样把和或积分视作某分布下的期望，通过估计对应的平均值近似这个期望
待估计和/积分： $s=\sum\limits_{x}p(x)f(x)=E_{p}[f(x)]；s=\int p(x)f(x)dx=E_{p}[f(x)]$ 写成期望形式，其中$p$为随机变量$x$的概率分布或概率密度分布
通过从$p$中抽取$n$个样本$x^{1},…,x^{n}$近似$s$并得到一个经验平均分布 $\hat{s}{n}= \frac{1}{n}\sum\limits{i=1}^{n}f(x^{i})$
- 无偏估计$E[\hat{s}{n}]= \frac{1}{n}\sum\limits{i=1}^{n}\mathbb{E}[f(x^{i})]= \frac{1}{n}\sum\limits_{i=1}^{n}s=s$
- 由大数定律，若$x^{i}$i.i.d. $\mathop{\lim}\limits_{n\rightarrow \infty}\hat{s}_{n}=s$
- 由中心极限定理$\hat{s}{n}$的分布收敛到以均值s方差$\frac{Var[f(x)]}{n}$的正态分布；我们可以利用正态分布的累积函数估计$\hat{s}{n}$的置信区间
重要采样
蒙特卡罗方法中，对和/积分分解，确定积分中哪一部分作为概率分布$p(x)$以及哪一部分作为被积函数$f(x)$很关键
$p(x)f(x)$不存在唯一分解，总可以写成$p(x)f(x)=q(x) \frac{p(x)f(x)}{q(x)}$
考虑达到某给定精度所需样本数量，问题最初的分解不是最佳选择 最优的选择$q^{*}$可以被简单推导——最优重要采样
任意蒙特卡罗估计$\hat{s}{p}= \frac{1}{n}\sum\limits^{n}{i=1,x^{i}~p}f(x^{i})= \frac{1}{n}\sum\limits^{n}{i=1,x^{i}~q} \frac{p(x^{i})f(x^{i})}{q(x^{i})}$ 估计期望与q分布无关 重要采样的方差对q非常敏感$Var[\hat{s}{q}]=\frac{Var[\frac{p(x)f(x)}{q(x)}]}{n}$ 最小化方差：$q^{}(x)= \frac{p(x)|f(x)|}{Z}$** $Z$为归一化常数，选择合适的$Z$使$q^{}(x)$和/积分为1 **一个好的重要采样分布会把更多的权重放在被积函数$f(x)$较大的地方
对重要采样而言，任意$q$分布都是可行的，从$q^{*}$中采样往往不可行，但其他$q$可以选择
若$q$使$\frac{p(x)f(x)}{q(x)}$很大，那么估计的方差也很大 若$q(x^{i})\gg p(x^{i})|f(x^{i})|$，重要采样采到很多无用的样本（0或极小值）
有偏重要采样
优势：不需要归一化的$p$或$q$分布 $\hat{s}{BIS}= \frac{\sum\limits{i=1}^{n} \frac{p(x^{i})}{q(x^{i})}f(x^{i})}{\sum\limits_{i=1}^{n} \frac{p(x^{i})}{q(x^{i})}}=\frac{\sum\limits_{i=1}^{n} \frac{p(x^{i})}{\tilde{q}(x^{i})}f(x^{i})}{\sum\limits_{i=1}^{n} \frac{p(x^{i})}{\tilde{q}(x^{i})}}=\frac{\sum\limits_{i=1}^{n} \frac{\tilde{p}(x^{i})}{\tilde{q}(x^{i})}f(x^{i})}{\sum\limits_{i=1}^{n} \frac{\tilde{p}(x^{i})}{\tilde{q}(x^{i})}}$ 非无偏估计；渐进无偏
马尔可夫链蒙特卡罗方法MCMC
有时希望采用蒙特卡罗方法，但又没有简单的可以从目标分布中精确采用或一个好的重要采样分布，引入了MCMC
MCMC技术最标准、最一般的理论保证只适用于各状态概率不为0的模型 包含0概率状态的MCMC方法性能的理论保证只能依据不同类型的分布具体分析证明
马尔可夫链核心思想是从某个可取任意值的状态$x$出发，随时间推移，随机地反复更新状态$x$，最终$x$成为了一个从$p(x)$中抽出的接近比较一般的样本 马尔可夫链由一个随机状态$x$和一个转移分布$T(x’|x)$定义而成 $T(x’|x)$说明了给定状态$x$的情况下随机地转移到$x’$的概率
并行运行无穷多个马尔可夫链，不同马尔可夫链的所有状态都采样自某一分布$q^{t}(x)$，$t$为消耗时间数 开始时采用分布$q^{0}$来任意地初始化
考虑随机变量$x$有可数个状态，使用正整数$x$重参数化原始问题中$x$的不同状态 使用向量$v$描述概率分布$q(x=i)=v_{i}$
| 考虑更新单一的马尔可夫链，从状态$x$到新状态$x’$的概率$q^{t+1}(x’)=\sum\limits_{x}q^{t}(x)T(x’ | x)$ |
将转移算子$T$表示为随机矩阵$A$，$A$的每一列代表一个概率分布 $A_{i,j}=T(x’=i|x=j)$ $\therefore$并行运算地更新不同马尔可夫链上整个分布$v^{t}=Av^{t-1}=A^{t}v^{0}$
若对任意状态$x$到任意其他状态$x’$存在一个$t$使转移概率不为0，Perron-Frobenius定理保证了矩阵的最大特征值是实数且为1 特征值随时间呈指数变化$v^{t}=V\ diag(\lambda)^{t}V^{-1}v^{0}$导致所有不等于1的特征值都衰减为0——收敛到平稳分布（均衡分布） 收敛时：$v’=Av=v$ 若正确选择了转移算子$T$，最终的平稳分布$q$会等于所希望采样的分布$p$ 通过Gibbs采样选择$T$
离散状态马尔可夫链的多数性质可以推广到连续状态的马尔可夫链（哈里斯链）中 在宽松条件下，一个带有转移算子$T$的马尔可夫链都会收敛到不动点$q’(x’)=\mathbb{E}_{x\sim q}T(x’|x)$
马尔可夫链的磨合过程：运行马尔可夫链直到达到均衡分布的过程 马尔可夫链达到均衡分布后，可以从均匀分布中抽取无限多的样本序列
- 这些样本服从同一分布，但两个连续的样本之间会高度相关
- 间隔采样可使均衡分布的统计量估计不会被MCMC的样本间相关性干扰
欲得到完全独立的样本，可同时并行运行多个马尔可夫链 深度学习从业者常选取的马尔可夫链数目与小批量中的样本数相近，然后从这些固定的马尔可夫链集合中抽取所需要的样本 马尔可夫链的数目通常为100
马尔可夫链达到均衡分布需要混合时间，很难检测马尔可夫链是否达到平衡 概率模型所能达到的状态是变量数的指数级别，表达$v、A、A$的特征值不现实；只能运行一定量时间的马尔可夫链粗略估计是否足够，之后使用启发式方法（手动检查样本、衡量前后样本之间的相关性）判断马尔可夫链是否混合成功