Vi ger en algoritm för att lära sig en blandning av ostrukturerade distributioner. Detta problem uppstår i olika oövervakade inlärningsscenarier, till exempel i att lära sig ämnesmodeller från en corpus av dokument som spänner över flera ämnen. Vi visar hur man lär sig beståndsdelarna i en blandning av k godtyckliga fördelningar över en stor diskret domän [n] = {1, 2,..., n} och blandningen vikter, med hjälp av O(n polylog n) prover. (I ämnesmodellens inlärningsmiljö motsvarar blandningens beståndsdelar ämnesfördelningen.) Denna uppgift är information-teoretiskt omöjligt för k > 1 under den vanliga provtagningsprocessen från en blandning distribution. Det finns dock situationer (t.ex. ovannämnda ämnesmodellfall) där varje provtagningspunkt består av flera observationer från samma blandningsbeståndsdel. Detta antal observationer, som vi kallar "sampling bländare", är en avgörande parameter för problemet. Vi får de första gränserna för detta blandningslärande problem utan att införa några antaganden om blandningens beståndsdelar. Vi visar att effektivt lärande är möjligt exakt vid informations-teoretiskt minsta möjliga öppning av 2k − 1. På så sätt uppnår vi ett nästan optimalt beroende av n och optimal öppning. Medan den provstorlek som krävs av vår algoritm beror exponentiellt på k, bevisar vi att ett sådant beroende är oundvikligt när man överväger allmänna blandningar. En sekvens av verktyg bidrar till algoritmen, såsom koncentrationsresultat för slumpmässiga matriser, dimensionsreduktion, momentuppskattningar och känslighetsanalys.
Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. Ref överväga att lära sig diskreta blandningar med tanke på ett stort antal "vyer", och de hänvisar till antalet vyer som provtagningsöppningen.
Learning mixtures of arbitrary distributions over large discrete domains
{'venue': "ITCS '14", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}