Scalable Training of Mixture Models via Coresets
Scalable Training of Mixture Models via Coresets
复制标题
DOI：
--
复制
发表时间：
2011-12
期刊：
影响因子：
--
通讯作者：
Dan Feldman;Matthew Faulkner;Andreas Krause
中科院分区：
文献类型：
--
作者：
Dan Feldman;Matthew Faulkner;Andreas Krause
我们如何在海量数据集上训练统计混合模型？在本文中，我们将展示如何构建混合高斯和自然推广的核心集。核心集是数据的加权子集，这保证了拟合核心集的模型也将为原始数据集提供良好的拟合。我们表明，也许令人惊讶的是，高斯混合承认coresets的大小独立的数据集的大小。更确切地说，我们证明了一个加权的O（dk 3/e2）的数据点集足以计算一个（1 + e）-近似的最佳模型的原始n个数据点。此外，这样的coreset可以有效地构建在一个地图减少风格的计算，以及在流设置。我们的研究结果依赖于一个新的统计估计减少计算几何中的问题，以及新的复杂性结果的混合高斯。我们经验评估我们的算法在几个真实的数据集，包括在地震检测的背景下，使用加速度计在移动的手机的密度估计问题。
How can we train a statistical mixture model on a massive data set? In this paper, we show how to construct coresets for mixtures of Gaussians and natural generalizations. A coreset is a weighted subset of the data, which guarantees that models fitting the coreset will also provide a good fit for the original data set. We show that, perhaps surprisingly, Gaussian mixtures admit coresets of size independent of the size of the data set. More precisely, we prove that a weighted set of O(dk3/e2) data points suffices for computing a (1 + e)-approximation for the optimal model on the original n data points. Moreover, such coresets can be efficiently constructed in a map-reduce style computation, as well as in a streaming setting. Our results rely on a novel reduction of statistical estimation to problems in computational geometry, as well as new complexity results about mixtures of Gaussians. We empirically evaluate our algorithms on several real data sets, including a density estimation problem in the context of earthquake detection using accelerometers in mobile phones.