Learning mixtures of arbitrary gaussians
Learning mixtures of arbitrary gaussians
复制标题
学习任意高斯的混合
DOI：
10.1145/380752.380808
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
R. Kannan
中科院分区：
文献类型：
--
作者：
Sanjeev Arora;R. Kannan
高斯（或正态）分布的混合出现在各种应用领域。对于从混合样本中找到高斯分量的任务，已经提出了许多技术，例如EM算法，Dempster，Laird和Rubin~（1977）的局部搜索启发式算法。然而，已知这样的几何学在维度上需要时间指数（即，在最坏的情况下，即使当组件的数量是$2$。
本文提出了第一个算法，可证明学习的分量高斯在时间上是多项式的维度。高斯分布可以有任意形状，只要它们满足“非简并”条件，即它们的高概率区域不能“太近”。
Mixtures of gaussian (or normal) distributions arise in a variety of application areas. Many techniques have been proposed for the task of finding the component gaussians given samples from the mixture, such as the EM algorithm, a local-search heuristic from Dempster, Laird and Rubin~(1977). However, such heuristics are known to require time exponential in the dimension (i.e., number of variables) in the worst case, even when the number of components is $2$.
This paper presents the first algorithm that provably learns the component gaussians in time that is polynomial in the dimension. The gaussians may have arbitrary shape provided they satisfy a “nondegeneracy” condition, which requires their high-probability regions to be not “too close” together.