Bayesian Inference for Big Data with Stochastic Gradient Markov Chain Monte Carlo

我们正处于一场信息革命之中，科学和技术的进步以及成功组织和企业的日常运作越来越依赖于数据分析。推动这些进步的是大量的数据，远远超过了可用计算能力的增长。麦肯锡和《经济学人》以及其他媒体的高调报告以及EPSRC最近的ICT优先事项“迈向智能信息基础设施”强调了管理、分析和从此类大规模数据中获得有用理解的重要性。贝叶斯分析是分析数据的最成功方法之一，现在，它被广泛应用于统计科学以及机器学习等人工智能技术。与其他方法相比，贝叶斯方法具有许多吸引人的优点：从简单部分构建复杂模型的灵活性;从数据中进行完全一致的推断;自然纳入先验知识;明确的建模假设;对模型阶次和参数的不确定性进行精确推理;防止过拟合。另一方面，人们普遍认为它们在大数据集上可能太慢而无法发挥实际作用。这是因为精确的贝叶斯计算通常是棘手的，所以需要一系列更实用的近似算法，包括变分近似，序列蒙特卡罗（SMC）和马尔可夫链蒙特卡罗（MCMC）。MCMC方法可以说是最流行的一类贝叶斯计算技术，由于其灵活性，普遍适用性和渐近精确性。不幸的是，MCMC方法不能很好地扩展到大数据集，因为它们需要多次迭代来减少Monte Carlo噪声，并且每次迭代已经涉及到整个数据集的昂贵扫描。在这个项目中，我们建议为一类新的MCMC推理过程开发理论基础，该过程可以扩展到数十亿个数据项，从而释放贝叶斯方法在大数据中的优势。基本思想是在算法的每次参数更新迭代期间使用数据的一个小子集，以便可以廉价地执行许多迭代。这在算法中引入了过多的随机性，这可以通过随着迭代次数的增加将更新步长退火到零来控制。所得到的算法是MCMC和随机优化算法之间的交叉。我们最近发起了对这个过程的初步探索，我们称之为随机梯度朗之万动力学（SGLD）（Welling和Teh，ICML 2011）。我们的建议是为理解这种随机MCMC算法的理论特性奠定数学基础，并在此基础上开发更复杂的算法。我们的目标是了解算法保证收敛的条件，以及收敛的类型和速度。利用这种理解，我们的目标是开发具有更好收敛特性的算法扩展和推广，包括预处理，自适应和黎曼方法，Hamilton Monte Carlo方法，在线贝叶斯学习方法和大步长近似方法。这些算法将在真实的世界问题上进行经验验证，包括文本处理和协同过滤的大规模数据分析问题，这些问题是机器学习中的标准问题，以及来自ID Analytics的大规模数据，ID Analytics是一家对检测身份盗窃和欺诈感兴趣的合作伙伴公司。

We are in the midst of an information revolution, where advances in science and technology, as well as the day-to-day operation of successful organisations and businesses, are increasingly reliant on the analyses of data. Driving these advances is a deluge of data, which is far outstripping the increase in computational power available. The importance of managing, analysing, and deriving useful understanding from such large scale data is highlighted by high-profile reports by McKinsey and The Economist as well as other outlets, and by the EPSRC's recent ICT priority of "Towards an Intelligent Information Infrastructure".Bayesian analysis is one of the most successful family of methods for analysing data, and one now widely adopted in the statistical sciences as well as in AI technologies like machine learning. The Bayesian approach offers a number of attractive advantages over other methods: flexibility in constructing complex models from simple parts; fully coherent inferences from data; natural incorporation of prior knowledge; explicit modelling assumptions; precise reasoning of uncertainties over model order and parameters; and protection against overfitting. On the other hand, there is a general perception that they can be too slow to be practically useful on big data sets. This is because exact Bayesian computations are typically intractable, so a range of more practical approximate algorithms are needed, including variational approximations, sequential Monte Carlo (SMC) and Markov chain Monte Carlo (MCMC). MCMC methods arguably form the most popular class of Bayesian computational techniques, due to their flexibility, general applicability and asymptotic exactness. Unfortunately, MCMC methods do not scale well to big data sets, since they require many iterations to reduce Monte Carlo noise, and each iteration already involves an expensive sweep through the whole data set.In this project we propose to develop the theoretical foundations for a new class of MCMC inference procedures that can scale to billions of data items, thus unlocking the strengths of Bayesian methods for big data. The basic idea is to use a small subset of the data during each parameter update iteration of the algorithm, so that many iterations can be performed cheaply. This introduces excess stochasticity in the algorithm, which can be controlled by annealing the update step sizes towards zero as the number of iterations increases. The resulting algorithm is a cross between an MCMC and a stochastic optimization algorithm. An initial exploration of this procedure, which we call stochastic gradient Langevin dynamics (SGLD), was initiated by us recently (Welling and Teh, ICML 2011). Our proposal is to lay the mathematical foundations for understanding the theoretical properties of such stochastic MCMC algorithms, and to build on these foundations to develop more sophisticated algorithms. We aim to understand the conditions under which the algorithm is guaranteed to converge, and the type and speed of convergence. Using this understanding, we aim to develop algorithmic extensions and generalizations with better convergence properties, including preconditioning, adaptive and Riemannian methods, Hamiltonian Monte Carlo methods, Online Bayesian learning methods, and approximate methods with large step sizes. These algorithms will be empirically validated on real world problems, including large scale data analysis problems for text processing and collaborative filtering which are standard problems in machine learning, and large scale data from ID Analytics, a partner company interested in detecting identity theft and fraud.