正文
近期关于随机梯度朗格文动力学（SGLD）和随机梯度汉密尔顿蒙特卡罗（SGHMC）的论文（《Bayesian Learning via Stochastic Gradient Langevin Dynamics》和《Stochastic Gradient Hamiltonian Monte Carlo》）锻造了 SGD 和贝叶斯建模之间的桥梁。这些方法包括对典型 SGD 更新的少许优化，即从近似于贝叶斯模型后验 p(θ|x) 的概率分布中生成样本。这些方法将 SGD 转换成 MCMC 方法，但是这种转换要求进行 MH 测试以获取准确结果，这也是这篇博客的主题。
由于这些发展，近期关于可扩展性 MCMC，尤其是一般 MCMC 模型所要求的在大数据集上进行的 MH 测试的相关研究兴趣正在升温。通常情况下，MH 测试需要扫描整个数据集，每需要一个数据样本的时候都需要应用该测试。对大数据集来说，这是很难做到的。Korattikara et al. 和 Bardenet et al. 的两篇 ICML 2014 论文（Austerity in MCMC Land: Cutting the Metropolis-Hastings Budget 和 Towards scaling up Markov chain Monte Carlo: an adaptive subsampling approach）试图降低 MH 测试的成本。他们都使用 concentration bound，且都获得了和完整数据集扫描相关的常数因子改进。其他相关工作改善了性能，但是模型的假设太强而限制了它的应用，尤其是对深度网络。这些方法都比不上 SGD 的性能，即从固定规模的小批数据中生成后验样本。
在本文中，我们描述了进行 MH 测试的新方法，该方法根据数据集规模将 MH 测试的成本从 O(N) 减少到 O(1)，并且没有对全局统计量的需求、不使用末端限定（将导致测试所需数据呈长尾分布）。我们使用新型修正分布（correction distribution）直接将有噪声的小批估计量「变成」平滑的 MH 测试分布。我们的方法是真正的「黑箱」法，因为它仅使用一个较小的期望批量大小为每一个 MH 测试提供精确的估计。这种方法甚至可应用到无限数据流中。
它在现有的 SGD 上可以实现「piggy-backed」，以通过 SGLD 或 SGHMC 提供完整的后验样本，其成本几乎与 SGD 样本一样。因此，现在使用和 SGD 优化相同的成本来实现完整的贝叶斯神经网络建模是可能的。我们的方法还有可能替代变分方法和 VAE，以更低的成本提供无偏后验样本。
为了解释该方法，我们来看一下 MH 测试在 MCMC 模型中的作用。
马尔可夫链蒙特卡罗方法回顾
马尔可夫链
MCMC 方法旨在从难以计算的目标分布中抽取样本。它们使用马尔可夫链生成样本，马尔可夫链包含代表状态的结点和状态之间转换的概率分布。
一个关键概念是马尔可夫假设（Markovian assumption），该假设表明在时间 t+1 处于某个状态的概率完全可以通过目前时间为 t 的状态推断出来。在数学上，θ_t 代表马尔可夫链在时间为 t 时的状态，我们可以推断出 p(θ_t+1|θ_t,…,θ_0)=p(θ_t+1|θ_t)。通过使用这些概率分布，我们能够对较大时间步 T 生成一个样本链
。
由于处于状态 θ_t+1 的概率直接依赖于 θ_t，因此二者的样本也是相互关联的。令人惊讶的是，在适当的假设条件下，通过很多样本的限制，马尔可夫链的样本分布近似于目标分布。
Metropolis-Hastings
最通用和强大的 MCMC 方法是 Metropolis-Hastings。它使用一个测试来过滤样本。为了准确定义它，我们令 p(θ) 代表我们想要逼近的目标分布。一般而言，从该分布中直接抽取样本比较困难。Metropolis-Hastings 使用一种更简单的提议分布（proposal distribution）q(θ′|θ) 来生成样本。这里，θ 代表链表当前的样本，θ′ 代表提议的样本。对于简单情况，通常使用以 θ 为均值的高斯提议（Gaussian proposal）。
如果我们仅使用高斯提议来生成样本，那么我们就无法逼近目标 p，因为这些样本会形成随机游走（random walk）。MH 测试通过使用以下测试过滤样本，聪明地解决了这一问题。设定一个统一的随机变量 u∈[0,1]，并确定以下公式是否为真：
如果该公式为真，则我们接受 θ′。反之，我们拒绝并重新使用旧的样本 θ。注意：
