Vi anser att problemet med att effektivt lära sig blandningar av ett stort antal sfäriska Gaussians, när komponenterna i blandningen är väl separerade. I den mest grundläggande formen av detta problem, vi ges prover från en enhetlig blandning av k standard sfäriska Gaussians med medel μ 1,. .., μ k  till R d, och målet är att uppskatta metoderna upp till noggrannhet δ med hjälp av poly(k, d, 1/δ) prover. I detta arbete studerar vi följande fråga: Vad är den minsta åtskillnad som krävs mellan medlen för att lösa denna uppgift? Den mest kända algoritmen på grund av Vempala och Wang [JCSS 2004] kräver en separation av ungefär min{k, d} 1/4. Å andra sidan visade Moitra och Valiant [FOCS 2010] att med separation o(1) krävs exponentiellt många prover. Vi tar itu med den betydande klyftan mellan dessa två gränser genom att visa följande resultat. • Vi visar att med separation o ( ε log k), superpolynomiellt många prover krävs. I själva verket håller detta även när k-medel av Gaussians plockas slumpmässigt i d = O(log k) dimensioner. • Vi visar att det är tillräckligt med prover av poly(k, d, 1/δ) med separation (t.ex. log k). Lägg märke till att den som är bunden till separationen är oberoende av δ. Detta resultat är baserat på en ny och effektiv "noggrannhet öka" algoritm som tar som indata grova uppskattningar av de verkliga medlen och i tid (och prover) poly(k, d, 1/δ) outputs uppskattningar av medlen upp till godtyckligt god noggrannhet δ förutsatt att separationen mellan medlen är  och (min{ ε log k, ε d}) (oberoende av δ). Tanken med algoritmen är att iterativt lösa ett "diagonalt dominant" system av icke-linjära ekvationer. Vi (1) presenterar också en beräkningseffektiv algoritm i d = O(1)-mått med endast separation, och (2) utvidga våra resultat till fallet att komponenter kan ha olika vikter och varianser. Dessa resultat tillsammans i huvudsak karakteriserar den optimala ordningen av separation mellan komponenter som behövs för att lära sig en blandning av k sfäriska Gaussians med polynom prover.
Å andra sidan karakteriserar REF de separationsförhållanden under vilka parameterinlärning för sfäriska GMMs kan lösas med poly(n, k, 1/δ ) prover.
On Learning Mixtures of Well-Separated Gaussians
{'venue': '2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}