Learning Mixtures of Gaussians in High Dimensions
Learning Mixtures of Gaussians in High Dimensions
复制标题
学习高维高斯的混合
DOI：
10.1145/2746539.2746616
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. Kakade
中科院分区：
文献类型：
--
作者：
Rong Ge;Qingqing Huang;S. Kakade
有效地学习高斯是统计和学习理论中的一个基本问题。在许多领域，从自然科学到社会科学，不幸的是，学习混合物的混合是一个信息理论上的困难问题：为了学习合理的准确性，在最坏情况下，所需的样本数量是高斯组件的数量。当参数从对抗性起点随机扰动。中央算法的思想包括通过利用其结构特性来消除高斯混合物的时刻张量作为Isserlis定理或Wick定理）。
Efficiently learning mixture of Gaussians is a fundamental problem in statistics and learning theory. Given samples coming from a random one out of k Gaussian distributions in Rn, the learning problem asks to estimate the means and the covariance matrices of these Gaussians. This learning problem arises in many areas ranging from the natural sciences to the social sciences, and has also found many ma- chine learning applications. Unfortunately, learning mixture of Gaussians is an information theoretically hard problem: in order to learn the parameters up to a reasonable accuracy, the number of samples required is exponential in the number of Gaussian components in the worst case. In this work, we show that provided we are in high enough dimensions, the class of Gaussian mixtures is learnable in its most general form under a smoothed analysis framework, where the parameters are randomly perturbed from an adversarial starting point. In particular, given samples from a mixture of Gaussians with randomly perturbed parameters, when n ≥ Ω(k2), we give an algorithm that learns the parameters with polynomial running time and using polynomial number of samples. The central algorithmic ideas consist of new ways to de- compose the moment tensor of the Gaussian mixture by exploiting its structural properties. The symmetries of this tensor are derived from the combinatorial structure of higher order moments of Gaussian distributions (sometimes referred to as Isserlis' theorem or Wick's theorem). We also develop new tools for bounding smallest singular values of structured random matrices, which could be useful in other smoothed analysis settings.