论文标题
EM算法提供了用于学习良好分离高斯的学习混合物的样本 -
The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians
论文作者
论文摘要
当组件分离良好时，我们考虑了带有$ k \ geq 3 $组件的球形高斯混合模型的问题。基本的先前结果表明，$ω（\ sqrt {\ log k}）$的分离是必要且足以识别多项式样本复杂性的参数（Regev和Vijayaraghavan，2017）。在同一情况下，我们表明$ \ tilde {o}（kd/ε^2）$样品足以容纳任何$ε\ sillsim 1/k $，从而缩小了从多项式到线性的间隙，因此给出了第一个最佳样本较高的上限，用于对良好分离的高斯豪斯混合物的参数估算。我们通过证明期望最大化（EM）算法的新结果来实现这一目标：我们表明，在分离$ω（\ sqrt {\ log k}）$下，EM在本地收敛。以前的最著名保证需要$ω（\ sqrt {k}）$ shipation（Yan等，2017）。与先前的工作不同，我们的结果不假定或使用（潜在不同的）混合权重或高斯组件方差的先验知识。此外，我们的结果表明，EM的有限样本误差并不取决于非宇宙数量，例如高斯组件均值之间的成对距离。
We consider the problem of spherical Gaussian Mixture models with $k \geq 3$ components when the components are well separated. A fundamental previous result established that separation of $Ω(\sqrt{\log k})$ is necessary and sufficient for identifiability of the parameters with polynomial sample complexity (Regev and Vijayaraghavan, 2017). In the same context, we show that $\tilde{O} (kd/ε^2)$ samples suffice for any $ε\lesssim 1/k$, closing the gap from polynomial to linear, and thus giving the first optimal sample upper bound for the parameter estimation of well-separated Gaussian mixtures. We accomplish this by proving a new result for the Expectation-Maximization (EM) algorithm: we show that EM converges locally, under separation $Ω(\sqrt{\log k})$. The previous best-known guarantee required $Ω(\sqrt{k})$ separation (Yan, et al., 2017). Unlike prior work, our results do not assume or use prior knowledge of the (potentially different) mixing weights or variances of the Gaussian components. Furthermore, our results show that the finite-sample error of EM does not depend on non-universal quantities such as pairwise distances between means of Gaussian components.
