论文标题
一种混合学习的傅立叶方法
A Fourier Approach to Mixture Learning
论文作者
论文摘要
我们重新审视了球形高斯人学习混合物的问题。从混合物中给定样品$ \ frac {1} {k} \ sum_ {j = 1}^{k} \ mathcal {n}（μ_j，i_d）$，目标是估算均值$μ_1，μ_2，μ_2，μ_2，\ ldots，\ ldots，μ_k\ in \ nimb a = n \ a = us}该学习问题的硬度可以通过定义为所有均值之间的最小距离的分离$δ$来衡量。 Regev and Vijayaraghavan（2017）表明，使用$δ=ω（\ sqrt {\ log k}）$分离，可以使用$ \ mathrm {poly}（k，d）$样本来学习手段k）$。这将打开低维度，其中$ d = o（\ log k）$。 在这项工作中，我们给出了一种算法，该算法有效地学习了$ d = o（\ log k/\ log \ log \ log k）$ dimensions in Eaparation $ d/\ sqrt {\ log k} $（modulo doubly doubly bolgarithmic actival action）。这种分离严格小于$ \ sqrt {\ log k} $，也被证明是必要的。除了Regev和Vijayaraghavan（2017）的结果外，我们的工作几乎降低了临界分离阈值，在该临界分离阈值中，球形高斯混合物有可能有效的参数学习。更一般而言，我们的算法在时间上运行$ \ mathrm {poly}（k）\ cdot f（d，δ，ε）$，因此在参数$ d $，$Δ$和$ε$中是固定参数可触及的。 我们的方法基于估计混合物在精心选择的频率下的傅立叶变换，并且算法及其分析都是简单而基本的。我们的积极结果很容易扩展到在分布的傅立叶光谱上轻度条件下的非高斯分布的学习混合物。
We revisit the problem of learning mixtures of spherical Gaussians. Given samples from mixture $\frac{1}{k}\sum_{j=1}^{k}\mathcal{N}(μ_j, I_d)$, the goal is to estimate the means $μ_1, μ_2, \ldots, μ_k \in \mathbb{R}^d$ up to a small error. The hardness of this learning problem can be measured by the separation $Δ$ defined as the minimum distance between all pairs of means. Regev and Vijayaraghavan (2017) showed that with $Δ= Ω(\sqrt{\log k})$ separation, the means can be learned using $\mathrm{poly}(k, d)$ samples, whereas super-polynomially many samples are required if $Δ= o(\sqrt{\log k})$ and $d = Ω(\log k)$. This leaves open the low-dimensional regime where $d = o(\log k)$. In this work, we give an algorithm that efficiently learns the means in $d = O(\log k/\log\log k)$ dimensions under separation $d/\sqrt{\log k}$ (modulo doubly logarithmic factors). This separation is strictly smaller than $\sqrt{\log k}$, and is also shown to be necessary. Along with the results of Regev and Vijayaraghavan (2017), our work almost pins down the critical separation threshold at which efficient parameter learning becomes possible for spherical Gaussian mixtures. More generally, our algorithm runs in time $\mathrm{poly}(k)\cdot f(d, Δ, ε)$, and is thus fixed-parameter tractable in parameters $d$, $Δ$ and $ε$. Our approach is based on estimating the Fourier transform of the mixture at carefully chosen frequencies, and both the algorithm and its analysis are simple and elementary. Our positive results can be easily extended to learning mixtures of non-Gaussian distributions, under a mild condition on the Fourier spectrum of the distribution.
