Sur l'apprentissage des mélanges de Gaussiens bien séparés

Nous considérons le problème d'apprendre efficacement des mélanges d'un grand nombre de Gaussiens sphériques, lorsque les composants du mélange sont bien séparés. Dans la forme la plus basique de ce problème, nous recevons des échantillons d'un mélange uniforme de k Gaussiens sphériques standard avec des moyennes μ 1,. . . , μ k ∈ ℝ d, et l'objectif est d'estimer les moyennes avec une précision δ en utilisant poly (k, d, 1/δ) échantillons. Dans ce travail, nous étudions la question suivante : quelle est la séparation minimale requise entre les moyennes pour résoudre cette tâche ? Le meilleur algorithme connu, dû à Vempala et Wang JCSS 2004, nécessite une séparation d'environ mink, d1/4. D'autre part, Moitra et Valiant FOCS 2010 ont montré qu'avec une séparation o (1), un nombre exponentiel d'échantillons est requis. Nous abordons l'écart significatif entre ces deux bornes, en montrant les résultats suivants. ; Nous montrons qu'avec une séparation o (√ (log k) ), un nombre superpolynomial d'échantillons est requis. En fait, cela est vrai même lorsque les k moyennes des Gaussiens sont choisies au hasard dans d = O (log k) dimensions. ; Nous montrons qu'avec une séparation Ω (√ (log k) ), choisie au hasard dans d = O (log k) dimensions, poly (k, d, 1/δ) échantillons suffisent. Remarquez que la borne sur la séparation est indépendante de δ. Ce résultat est basé sur un nouvel algorithme efficace de « renforcement de la précision » qui prend en entrée des estimations grossières des véritables moyennes et, en temps (et échantillons) poly (k, d, 1/δ), produit des estimations des moyennes avec une précision arbitrairement bonne δ, en supposant que la séparation entre les moyennes est Ω (min√ (log k), √d) (indépendamment de δ). L'idée de l'algorithme est de résoudre itérativement un système d'équations non linéaires « diagonalement dominant ». Nous présentons également (1) un algorithme computationnellement efficace dans d = O (1) dimensions avec seulement Ω (√d) de séparation, et (2) étendons nos résultats au cas où les composants pourraient avoir des poids et des variances différents. Ces résultats caractérisent essentiellement l'ordre optimal de séparation entre les composants nécessaire pour apprendre un mélange de k Gaussiens sphériques avec des échantillons polynomiaux.