Ten Steps of EM Suffice for Mixtures of Two Gaussians
Ten Steps of EM Suffice for Mixtures of Two Gaussians
复制标题
DOI：
--
复制
发表时间：
2016-09
期刊：
影响因子：
--
通讯作者：
C. Daskalakis;Christos Tzamos;Manolis Zampetakis
中科院分区：
文献类型：
--
作者：
C. Daskalakis;Christos Tzamos;Manolis Zampetakis
期望最大化（EM）算法是一种广泛使用的方法，用于具有潜在变量的模型中的最大似然估计。为了估计高斯人的混合物，它的迭代可以被视为K-均值聚类算法的软版本。尽管它广泛使用和应用，但对于这种方法，基本上没有已知的收敛保证。我们为两种高斯与已知协方差矩阵的混合物提供全球收敛保证。我们表明，EM的总体版本，其中算法可以从混合物中无限地访问许多样品，几何收敛于正确的平均向量，并为收敛速率提供简单的封闭形式表达式。作为一个简单的例证，我们表明，在一个维度上，在Infinity初始初始化的EM算法的十个步骤导致均值的误差估计小于1 \％的误差估计。在有限的样本制度中，我们表明，在随机初始化下，$ \ tilde {o}（d/\ epsilon^2）$样品可以将未知的向量计算为$ \ epsilon $ in Mahalanobis距离，在$ d $是尺寸。特别是，基于em的估计器的错误率为$ \ tilde {o} \ left（\ sqrt {d \ fos n} \ right）$，其中$ n $是样本的数量，这是最佳的对数因素。
The Expectation-Maximization (EM) algorithm is a widely used method for maximum likelihood estimation in models with latent variables. For estimating mixtures of Gaussians, its iteration can be viewed as a soft version of the k-means clustering algorithm. Despite its wide use and applications, there are essentially no known convergence guarantees for this method. We provide global convergence guarantees for mixtures of two Gaussians with known covariance matrices. We show that the population version of EM, where the algorithm is given access to infinitely many samples from the mixture, converges geometrically to the correct mean vectors, and provide simple, closed-form expressions for the convergence rate. As a simple illustration, we show that, in one dimension, ten steps of the EM algorithm initialized at infinity result in less than 1\% error estimation of the means. In the finite sample regime, we show that, under a random initialization, $\tilde{O}(d/\epsilon^2)$ samples suffice to compute the unknown vectors to within $\epsilon$ in Mahalanobis distance, where $d$ is the dimension. In particular, the error rate of the EM based estimator is $\tilde{O}\left(\sqrt{d \over n}\right)$ where $n$ is the number of samples, which is optimal up to logarithmic factors.