Expectation propagation in the large data limit
Expectation propagation in the large data limit
复制标题
DOI：
10.1111/rssb.12241
复制
发表时间：
2018-01-01
影响因子：
5.8
通讯作者：
Barthelme, Simon
中科院分区：
文献类型：
--
作者：
Dehaene, Guillaume;Barthelme, Simon
期望传播（EP）算法是一种非常成功的变分推理算法。EP是用于近似复杂分布的迭代算法，通常用于找到后验分布的高斯近似。在这种类型的许多应用中，EP表现非常出色。令人惊讶的是，尽管它被广泛使用，但高斯EP的理论保证很少，而且人们对它的理解也很差。为了分析EP，我们首先引入EP的一种变体：平均EP，它在较小的参数空间上操作。然后，我们考虑平均EP和EP在无限数据的限制，其中每个似然项的整体贡献很小，后验几乎是高斯的。在这个限制，我们证明了平均EP和EP的迭代是简单的：他们的行为就像牛顿算法的迭代找到一个功能的模式。我们使用这种极限行为证明，EP是渐近精确的，并获得其他见解EP的动态行为，例如，它可能会发散下穷人的初始化完全像牛顿的方法。EP算法是一个简单的陈述，但一个困难的研究。我们的研究结果将有助于进一步研究这一重要方法的理论性质。
Expectation propagation (EP) is a widely successful algorithm for variational inference. EP is an iterative algorithm used to approximate complicated distributions, typically to find a Gaussian approximation of posterior distributions. In many applications of this type, EP performs extremely well. Surprisingly, despite its widespread use, there are very few theoretical guarantees on Gaussian EP, and it is quite poorly understood. To analyse EP, we first introduce a variant of EP: averaged EP, which operates on a smaller parameter space. We then consider averaged EP and EP in the limit of infinite data, where the overall contribution of each likelihood term is small and where posteriors are almost Gaussian. In this limit, we prove that the iterations of both averaged EP and EP are simple: they behave like iterations of Newton's algorithm for finding the mode of a function. We use this limit behaviour to prove that EP is asymptotically exact, and to obtain other insights into the dynamic behaviour of EP, e.g. that it may diverge under poor initialization exactly like Newton's method. EP is a simple algorithm to state, but a difficult one to study. Our results should facilitate further research into the theoretical properties of this important method.