迷你规模的Metropolis-Hastings
过去的几年里，我们经历了一场巨大的数据洪流，这在人工智能兴趣激增浪潮中扮演了关键角色。下面是部分大型数据库列表：
- ImageNet，拥有超过1400万个用于分类和对象检测的图像。
- Movielens，拥有2000万用户进行协作过滤评级的电影。
- Udacity 用于培训自动驾驶汽车的数据库（至少223GB）。
- 雅虎 用于研究人类行为的13.5 TB的用户 - 新闻互动数据库。
随机梯度下降（SGD）一直是推动这些数据集的大规模模型发展的动力。SGD非常适用于大型数据集：它仅使用固定大小的小型块来估计整个数据集上的损失函数的梯度，并在每次通过数据集时更新模型多次。
但是SGD有局限性。当我们构造一个模型，我们需要用到一个数据集为x，模型参数为θ的损失函数Lθ(x),且通过利用θ的梯度下降去将损失降到最小。这种便捷方法使得优化变得容易，但更易受各种问题的影响，包括过度拟合、超灵敏系数以及可能的慢性收敛。一个更加有效的方法是将θ的推断视为一个整体后验的推断，从而从损失a函数中得到一个联合分布p(x,θ)，进而计算其推断后验函数p(θ|x)。这是贝叶斯建模方法，特别是应用于深度模型时的贝叶斯神经网络方法。Zoubin Ghahramani最近的这个教程讨论了这种方法的一些优点。
对于大多数问题，后验函数p(θ|x)模型都是很棘手的（没有封闭形式）。机器学习有两种方法可以解决棘手的后验问题：变分贝叶斯方法和马尔可夫链蒙特卡罗 法（MCMC）。在变分法中，后验用更简单的分布（例如正态分布）来近似，并且其与真正后验的距离被最小化。在MCMC方法中，后验近似为相关样本（点或粒子密度）的序列。变贝叶斯方法已被广泛使用，但经常出现显著错误——看到这个最近与吉布斯抽样对比，也从自动编码器变（VAE）纸图。变量方法在计算上也比直接参数SGD（这是一个很小的常数因子，但是1-10天的一个小的常数可能是相当重要的）更珍贵。
MCMC方法没有这样的偏离。你可以把MCMC粒子想象成量子力学粒子：你只能观察个别情况，但是他们遵循一个任意复杂的联合分布。通过取多个样本，可以推断出有用的统计量，应用正则化条件等。但MCMC方法在大数据集上有一个优先问题：除了允许吉布斯采样的重要类共轭模型之外，还没有有效的方法根据一般的MCMC方法对minibatches数据进行Metropolis-Hastings测试（我们将立即定义/评估MH测试）。作为回应，研究人员必须设计模型来进行推理，例如 限制玻尔兹曼机器（RBM）使用分层的无向设计使Gibbs采样成为可能。在最近的突破中，VAE使用变分方法来支持概率自动编码器中的更一般的后验分布。但是对于VAE，像其他变分模型一样，人们必须忍受这样一个事实，即模型是一个最佳拟合近似值，通常不会量化近似值的近似值。虽然它们通常提供更好的精确度，但最近在自动编码器应用中MCMC方法已经被忽略，缺乏有效的可扩展MH测试。
SGD和贝叶斯模型之间的桥梁最近由 随机梯度朗之万动力学（SGLD）和随机梯度哈密尔顿蒙特卡罗（SGHMC）的论文形成。这些方法涉及对典型的SGD更新的微小变化，这些更新从概率分布产生样本，该概率分布近似于贝叶斯模型后验p(θ|x)。这些方法将SGD转换成MCMC方法，因此需要Metropolis-Hastings（MH）测试来获得准确的结果，这便是这篇博文的主题。
得益于这些发展，近来在可扩展MCMC中的兴趣已经升温，特别是在大数据集上进行通用MCMC模型所需的MH测试。通常情况下，MH测试需要扫描整个数据集，并在每次需要数据采样时应用。很明显，对于大型数据集来说，要做到这一点是棘手的。来自ICML 2014，Korattikara等人 和Bardenet等人 的两篇论文，试图降低MH测试的成本。它们都使用浓度范围，并且相对于完整的数据集扫描，都实现了恒定的因素改进。其他最近的工作提高了性能，但对限制适用性的模型做出了更强的假设，特别是对于深度网络。这些方法都不能与SGD的性能相匹配，即从小的恒定尺寸的批次数据中生成后验样本。
在这篇文章中，我们介绍了一种新的MH测试方法，将MH测试的成本相对于数据集大小从O(N)移到O(1)。它避免了全局统计的需要，也不使用尾部边界（这导致测试所需数据量的长尾分布）。相反，我们使用一种新颖的校正分布来将噪声小批量估计器的分布直接“变形”为平滑的MH测试分布。我们的方法是一种真正的“黑盒子”方法，它仅使用来自小的预期尺寸小批量的数据来提供对每个MH测试的准确度的估计。它甚至可以应用于无界数据流。它可以在现有的SGD实施中“背负”，以提供完整的后面样品（通过SGLD或SGHMC），几乎与SGD样品相同的成本。因此，完全贝叶斯神经网络建模现在可能与SGD优化大约相同的成本。
为了解释这种方法，我们回顾了MHMC模型中MH检测的作用。
马尔可夫链蒙特卡罗(MCMC)回顾
马尔可夫链
MCMC方法被设计成从难以计算的目标分布中抽样。为了生成样本，他们利用马尔可夫链，它由表示系统状态的节点和从一个状态转换到另一个状态的概率分布组成。
一个关键的概念是马尔可夫假设，它指出，在时间t + 1处于状态的概率t+1可以完全基于当前在时间t的状态来推断t。在数学上，令θt表示在时间t的马尔科夫链的当前状态t，我们有p(θt+1|θt,…,θ0)=p(θt+1|θt)。通过使用这些概率分布，我们可以对于一些大型的T生成一个样本的链
。
由于处于θ(t+1)状态的概率直接依赖于 θt，所以样本是相关的。令人惊讶的是，可以证明，在温和的假设下，在许多样本的极限内，链样本的分布接近目标分布。
对MCMC方法的全面回顾超出了本文的范围，但是马尔可夫链蒙特卡洛手册（2011）是一个很好的参考。标准的机器学习教科书如Koller＆Friedman（2009）和Murphy（2012）也涵盖了MCMC方法。
Metropolis-Hastings（MH)
Metropolis-Hastings是最通用和最强大的MCMC方法之一 。这是一个通过测试来过滤样本的方法。为了正确地定义它，设p(θ)是我们想要近似的目标分布。一般来说，从它直接取样是很难的。Metropolis-Hastings使用更简单的建议分布 q(θ ′|θ) 来生成样本。在这里，θ代表我们现有的样本链，θ ′代表提出的样本。对于简单的情况，通常使用以θ为中心的高斯提议。
如果我们只是使用高斯生成样本在我们的链中，我们不可能接近我们的目标p，因为样本将形成一个随机散点。MH测试巧妙地通过以下测试过滤样品来解决这个问题。在[0,1]中绘制一个统一的随机变量u∈[0,1]并确定以下条件是否成立：
如果属实，我们接受 θ ′。否则，我们拒绝并重新使用旧样本 θ。注意：
- 它不需要知道正规化常数（独立θ和θ ′），因为它消除了p(θ ′)/p(θ)的比率。这很重要，因为规范化常量可以说是分布变得棘手的最大原因。
• p(θ ′)的值越高，我们接受它的可能性越大。
为了更直观地了解测试的工作原理，我们从Jupyter笔记本中创建了下图，显示了样本的进展情况，以近似于目标后验。这个例子来源于Welling＆Teh（2011）。
一个混合高斯例子的MH测试的一个简单的例子。参数是θ∈R^2，x轴和y轴分别代表 θ1和θ2。目标后验的轮廓显示在第四个图上; 概率质量集中在点（0,1）(0,1)和（1，-1）之间的对角线上(1,-1)。（这个后验依赖于抽样的高斯）。图中显示了在我们的MCMC链中的50,500和5000个样本之后的MH测试的进展。在5000个样本之后，很明显我们的样本集中在后验概率较高的区域。
减少Metropolis-Hastings数据的使用
当我们考虑大数据集的贝叶斯后验推理时会发生什么？（也许我们对上图中的同一个例子感兴趣，除了后验是基于更多的数据点的。）然后我们的目标是以近似的分布p(θ|x1,…,xN)为大N采样。根据贝叶斯规则，就是
其中p0是先验的。我们还假设 xi是有条件独立给出θ。MH测试因此变成：
或者，在取对数并重新排列后（忽略最小的操作符，这在技术上是不需要的），我们得到
现在的问题是显而易见的：计算所有的p(xi |θ ′)项是很昂贵的，每次我们抽样时都必须这样做，因为它取决于θ ′。
处理这个问题的简单方法是应用相同的测试，但是改用一个b元素的小规模数集 ：
不幸的是，这不会从正确的目标分布中抽样; 参见Bardenet等人的第6.1节。（2017年）了解细节。
一个更好的策略是从同一批b点开始，然后衡量批量测试相对于使用完整数据的可信度。如果在看到b点后，我们已经知道我们提出的样本θ ′明显比我们现在的样本θ差，那么我们应该马上放弃。如果θ ′好得多，我们应该接受。如果不明确，那么我们增加我们的测试批次的大小，可能是2b 元素，然后测量测试的信念。泡，冲洗，重复。如前所述，Korattikara等人 （2014年）和Bardenet等人。（2014） 根据这个框架开发了算法。
上述方法的一个弱点是它正在重复测试，每次增加测试批量大小时都必须减少允许的测试错误。不幸的是，上面的方法也将很有可能将测试批次增加到完整的数据集，并且在加速测试完整的数据集时生成更多恒定因子。
Minibatch Metropolis-Hastings：我们的贡献
更改接受功能
为了建立我们的测试，我们首先定义日志转换概率比 Δ：
这个对数比率因子是一个单样本项的和，所以当我们通过计算一个小批量来逼近它的值时，我们得到一个无偏估计器的全数据值加上一些噪点（这是由中心极限定理渐近正态的）。
应用MH测试的第一步是使用不同的接受函数。用Δ表示，经典MH接受蓝色曲线给出概率的过渡。
函数f和g可以作为Metropolis-Hastings的验收测试。给定当前样本θ和建议样本θ ′，纵轴表示接受θ′ 的概率。
我们将使用sigmoid函数替换经典测试。可能并不明显，为什么这是允许的，但有一些优雅的理论解释了为什么使用这个替代函数作为MH的验收测试 仍然导致MCMC意义不变。即，在相同的温和的假设，样本的分布
接近目标分布。
标准物流随机变量，表示的密度X(log) 与等效MH测试表达式(X(log)+Δ>0)
与Sigmoid接受函数。
我们的验收测试现在是sigmoid函数。注意sigmoid函数是（标准）Logistic随机变量的累积分布函数 ; 上面的数字绘制密度。可以证明，在Sigmoid接受函数下进行的MH检验降低到确定采样的X(log)值是否为(X(log)+Δ>0)。
新的MH测试
这很好，但是我们不想计算 Δ，因为它取决于所有的 p(xi|θ ′)项。当我们使用小批量来估计Δ时，我们引入了一个近似正态的加法误差X(normal)。我们工作中的关键观察是Δ（近似高斯）的小规模数据集估计的分布已经非常接近期望的测试分布X(log)，如下所示。
红色是逻辑累积分布函数(CDF)（正如我们之前的）的一个图，以及正常的CDF曲线(灰色)，这对应于1.7的标准偏差。
我们不是像以前的工作那样采用尾部边界，而是用一个加法修正变量X(correction)直接连接这两个分布：
小规模数据集 MH测试图。在右边，我们有完整的数据测试，但是我们不能使用它，因为Δ是难处理的。相反，我们有 Δ+X(normal)（从左边开始），并且必须加上一个校正X（correction）。
我们希望使等式左边和右边分布相等，所以我们加入一个校正X(correction)，它是一个以0为中心的对称随机变量。加入独立的随机变量给出一个随机变量，其分布是加权的分布的卷积。因此找到校正分布涉及逻辑分布和正态分布的“反卷积”。这样做并不总是可能的，并且必须满足几个条件（例如，正态分布的结尾必须比逻辑更弱），但对我们来说却是幸运的。在我们发表在UAI 2017上的论文中，我们展示了校正分布可以通过列表近似为单精度浮点精度。
在本文中，我们也证明了包含我们测试的误差的理论结果，并且实验结果表明我们的方法导致高斯混合模型的精确后验估计，并且它在Logistic回归中也是高度样本有效的MNIST数字。
直方图显示了我们的文章中基于三种算法的Metropolis-Hastings的批量大小。后面的内容与Jupyter笔记本的前一个例子类似，只是生成了一百万个数据点。左边是我们的结果，另外两个是来自Korattikara等人。（2014）和Bardenet等人 （2014年）。我们的算法每次迭代平均使用172个数据点。注意直方图的对数尺度。
我们希望我们的测试对于那些希望在大型数据集中使用MCMC方法的其他研究人员是有用的。作为UC Berkeley开发的BIDMach机器学习库的一部分，我们还实施了一个开源版本的测试。
我感谢作者潘新蕾，陈浩宇，特别是John“The Edge”Canny对这个项目的帮助。
- 大都市黑斯廷斯的有效小批次验收测试。 Daniel Seita，潘新蕾，陈浩宇，John Canny。 人工智能中的不确定性，2017。