UC伯克利提出小批量MH测试：令MCMC方法在自编码器中更强劲

近日伯克利大学官方博客发文提出小批量 MH（Minibatch Metropolis-Hastings），即一种进行 MH 测试的新方法，该方法根据数据集规模将 MH 测试的成本从 O(N) 减少到 O(1)，它不仅对全局统计量没有要求，同时还不需要使用末端限定。伯克利大学使用新型修正分布直接将有噪声的小批估计量转换为平滑的 MH 测试分布。

我们在过去几年中经历了一次大型数据洪流，它对人工智能的兴起起到了重要作用。下面列出部分大型数据集：

• ImageNet：1400 万张图像，可用于分类和物体检测。
  
• Movielens：两千万用户对电影的评级，可用于协同过滤（collaborative filtering）。
  
• Udacity 车辆数据集：至少 223 GB，可用于自动驾驶汽车的训练。
  
• Yahoo 数据集：13.5 TB 用户-新闻交互（user-news interaction）数据集，可用于研究人类行为。
  

随机梯度下降（SGD）推动了基于这些数据集进行大型模型开发的进程。SGD 非常适合大型数据集：它仅需要使用一个固定的 minibatch 大小，就可以在整个数据集上估计损失函数的梯度值，每次遍历数据集，都能实现对模型的更新。

但是 SGD 也存在局限性。我们在构建模型时，使用数据集 x 和模型参数 θ构建损失函数 L_θ(x)，并尝试对参数θ执行梯度下降而极小化损失函数。这一便捷方法使优化变得容易，但是也容易产生多种问题，如过拟合（over-fitting）、过分敏感的系数值，以及可能较慢的收敛速度。一个更鲁棒的方法是将 θ 上的推断问题看作充分的后验推断（posterior inference），从损失函数中推断出联合分布 p(x,θ)，然后计算后验概率 p(θ|x)。这是贝叶斯建模方法，具体来说，当应用到深度模型上时，这就是贝叶斯神经网络方法。Zoubin Ghahramani 近期公布的教程讨论了该方法的优点。

模型的后验概率 p(θ|x) 对于大多数问题都是很难处理的（非封闭式）。机器学习领域有两种方法可以解决难处理后验：变分贝叶斯方法（Variational Bayesian）和马尔可夫蒙特卡罗（MCMC）方法。在变分方法中，该后验逼近于一个更简单的分布（如正态分布），并且最小化其与真正后验之间的距离。在 MCMC 方法中，该后验被近似为一个相关样本序列（点或粒子密度）。变分贝叶斯方法已经得到广泛应用，但也常常引起显著的误差。详见论文《Online but Accurate Inference for Latent Variable Models with Local Gibbs Sampling》和《Auto-Encoding Variational Bayes》。变分贝叶斯方法比直接对参数执行 SGD 的计算成本高，虽然只是一个小的常数因子，但该常数乘 1-10 天就变的很重要了。

MCMC 方法没有这样的偏差。你可以将 MCMC 粒子想象成量子力学中的粒子：你只能观察到个体实例，并且它们遵循一种任意复杂度（arbitrarily-complex）的联合分布。你可以通过多个样本推断出有用的统计数据、应用正则项等。但是 MCMC 方法在大数据集上有一个最主要的问题：除了遵循吉布斯采样（Gibbs sampling）的共轭模型中的一个重要类别以外，并没有其他有效方式能在小批量数据上进行一般 MCMC 方法所要求的 Metropolis-Hastings 测试（稍后我们将定义／复习 MH 测试）。因此研究者必须设计模型使推断变得易于处理，如受限玻尔兹曼机（RBM）使用一种分层式、无向的设计以使用吉布斯采样。近期的一个突破是，变分自编码器（VAE）使用变分方法使概率性自编码器（probabilistic auto-encoders）可以支持更通用的后验分布。但是，具备 VAE 的变分模型和其他变分模型一样，必须面对一个现实，即该模型是一个最优近似（best-fit approximation），（通常）没有对近似程度进行量化。尽管 MCMC 方法通常能提供更好的精度，但是由于缺乏高效、可扩展的 MH 测试，导致该方法近期在自编码器应用中被边缘化。

近期关于随机梯度朗格文动力学（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]，并确定以下公式是否为真：

如果该公式为真，则我们接受 θ′。反之，我们拒绝并重新使用旧的样本 θ。注意：

• 不需要归一化常数（独立于 θ 和 θ′）的知识，因为它在 p(θ′)/p(θ) 系数中可以相互抵消。这一属性十分有用，因为归一化常数可以说是令分布变得难以处理的最大原因。
  
• p(θ′) 的值越高，接受的概率越大。
  

为使该测试的工作原理更加直观，我们可以查看下图，其展示了样本逼近目标后验概率的过程。该实例来自 Max 和 Teh 2011 年的论文《Bayesian Learning via Stochastic Gradient Langevin Dynamics》。

MH 在高斯样本上的行为示例。参数是 θ∈R^2，其中 x 轴、y 轴分别代表 θ_1 和 θ_2。目标后验的轮廓显示在第四幅图中；概率质量集中在点 (0,1) 和 (1,-1) 间的对角线上（该后验依赖于高斯抽样）。上面四幅图展示了在 MCMC 链中 50 个样本、500 个样本、5000 个样本后的 MH 测试累进。在 5000 个样本之后，我们可以很清楚地看到样本集中于后验概率更高的区域。

减少 Metropolis-Hastings 数据使用

当我们将贝叶斯后验推断和大数据集放在一起会发生什么？（或许我们会对上图中的样本感兴趣，除了该后验以更多的数据点为基础。）然后，我们的目标就是使样本近似于大数据集 N 上的分布 p(θ|x_1,…,x_N)。根据贝叶斯法则，p_0(θ)p(x_1,…,x_N|θ)/p(x_1,…,x_N)，其中 p_0 为先验概率。我们还假设 x_i 与给定的θ是条件独立的。因此 MH 测试变成：

或者，采用对数和重新排列后（忽视最小运算符，此处它在技术上不是必需的），我们得到：

现在问题很明显了：计算所有的 p(x_i|θ′) 项成本高昂，而由于它依赖于θ′，我们每次抽样时必须计算所有的 p(x_i|θ′) 项。

最朴素的解决办法是应用同样的测试，但是使用小批量 b 元素：

不幸地是，这种方法无法从恰当的目标分布中抽样，详见论文《On Markov chain Monte Carlo methods for tall data》（Bardenet et al. (2017)）第 6.1 节。

更好的策略初始可令批量等于的 b 个样本点，然后估算批测试与使用全部数据相比的置信度。如果遍历 b 个数据点，并且已经发现我们提出的样本θ′远远不如当前的样本θ，我们会立刻拒绝该样本。如果θ′显著地表现更好，我们就应该接受。如果结果比较模糊，我们就需要扩大测试批量的规模，例如扩展到 2b 个元素，然后再评估测试的可信度。随后再清洗数据并不断重复该过程。之前，Korattikara et al. (2014) 和 Bardenet et al. (2014) 已经提出基于该框架的算法。

上述方法的弱点在于需要重复测试，每次扩大测试批量大小必须减少可容忍的测试误差。不幸的是，上述方法很可能会使测试批量逐渐增长到全部数据集，它们最多提供常数因子加速全部数据集上测试。

我们的贡献：小批量 Metropolis-Hastings

改变接受函数（Acceptance Function）

为了设定我们的测试，首先需要定义对数转换概率Δ：

该对数比率可分解为预样本项的和，所以当我们通过在小批量数据上的计算而逼近它的值时，我们就可以得到全部数据值外加一些噪声的无偏估计量，该逼近过程为基于中心极限定理的渐进正态过程。

应用我们 MH 测试的第一步是使用一个不同的接受函数。正如Δ项所表达的，经典的 MH 测试接受蓝线所给出的概率转换。

函数 f 和 g 作为 Metropolis-Hastings 的接受测试。给定当前样本θ和提议样本θ'，竖轴代表接受θ'的概率。

我们并不使用经典测试，而是使用 Sigmoid 函数。使用该函数的合理性可能并不那么显而易见，但是我们有一些优雅的理论解释了为什么使用这种替代函数作为 MH 的接受测试仍然能使 MCMC 方法语义正确。这些理论表明，在同等程度的假设下，样本的分布接近于目标分布。

上图为标准 logistic 随机变量的分布密度，X_log 表示沿着等价 MH 测试表达式（X_log+Δ>0）为 Sigmoid 接受函数。

我们现在的接受测试为 Sigmoid 函数。注意 Sigmoid 函数是标准 logistic 随机变量的累积分布函数，上图展示了分布密度。我们能证明在 Sigmoid 接受函数以下的 MH 测试可以变弱为是否对于一个抽样的 X_log 值，X_log+Δ>0。

新的 MH 测试

该 Logistic 函数十分优秀，但是我们不希望计算Δ，因为它依赖于所有的 P(x_i| θ′) 项。当我们使用小批量数据估计Δ时，我们就引进了一个额外的误差，即近似正态误差 X_normal。如下图所述，我们研究工作的关键成果是使用小批量的分布来估计Δ（近似高斯分布）已经非常接近所期望的分布 X_log。

我们前面得到的 logistic CDF 曲线（红色）和正态 CDF 曲线（黄色），它们的标准差为 1.7。

我们并不像以前的研究一样追求末端限定，而是使用一个附加的修正变量 X_correction 直接连接这两个分布：

小批量 MH 测试的图示。我们在右边有完整的数据测试，但是我们不能使用它，因为Δ是难以处理的。相反，我们有Δ+X_normal（左边），并且只需要添加一个修正项 X_correction。

我们希望令 LHS 和 RHS 相等，所以我们就添加了修正项 X_correction，该修正项是以 0 为均值的对称随机变量（symmetric random variable）。添加独立的随机变量将会给出一个分布为卷积被加数分布的随机变量。所以寻找正确的分布就涉及到 logistic 分布和正态分布的「解卷积」。这一过程并不是常常都能进行的，它需要满足一些条件（例如正态分布的末端必须弱于 Logistic 分布），但幸运的是基本上我们都能满足这些条件。在 UAI 2017 的论文中，我们展示了修正的分布能通过做表（tabulation）逼近本质的单精度和浮点精度。

在我们的论文中，我们同样证明了理论上的结果限定了测试误差的边界，并且实验结果表示我们的方法能令高斯混合模型的后验估计十分精确，同时它在使用 Logistic 回归对 MNIST 数字进行分类时有极高的样本效率。

上方直方图展示了用于 Metropolis-Hastings 三种基准算法和不同批量大小的关系。其中除了使用 1 百万数据点生成以外，后验分布和前面 Jupyter Notebook 中的案例是相似的。左边是我们的结果，其他两个图分别来自 Korattikara et al. (2014) 和 Bardenet et al. (2014)。我们的算法每一次迭代使用的均值是 172 个数据点。

我们希望我们的测试对于其他在大数据使用 MCMC 方法的研究者有所帮助。我们同样将该测试的开源实现版并入 UC Berkeley 所开发的 BIDMach 机器学习库。

• 测试的开源实现版：https://github.com/BIDData/BIDMach/blob/master/src/main/scala/BIDMach/updaters/MHTest.scala
  
• BIDMach 机器学习库：https://github.com/BIDData/BIDMach
  

原文地址：http://bair.berkeley.edu/blog/2017/08/02/minibatch-metropolis-hastings/