Identifying Mixture Models

on YouTube ↗40m

" summary

Algorithm solves source identification for a mixture of k product distributions on n binary bits (k-MixProd), recovering the k-column parameter matrix from approximate multilinear moments by reducing to a k-spike moment problem and a K-mix IID instance. Key ingredients are synthetic bits to manufacture higher moments from disjoint variable sets and a condition-number lower bound for Hadamard extensions. Requires ≥3k−3 observable bits, a separation parameter ζ for stability, and runs with sample/runtime about exp(k log k) arithmetic operations.

AI-written summary · about

" chapters (11)

1. 0:00Introduction
2. 0:35Notation
3. 6:55Lecture Plan
4. 8:24The Moment Problem
5. 12:40The Dependence Problem
6. 15:12The More Ambitious Problem
7. 17:46References
8. 19:50Identification
9. 24:02Hadamard Extension
10. 32:29Algorithm
11. 37:07Transportation distance

" related talks

• 44mMixture Models, Robustness, and Sum of Squares ProofsJerry Li · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 31mUnsupervised LearningSantosh Vempala · The Brain and Computation Boot Camp
• 29mApproximating Spherical Gaussian MixturesAnanda Suresh · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 52mLearning Mixture of Gaussians using Moment TensorRong Ge · Tensors in Computer Science and Geometry 2014
• 52mSubtractive Mixture Models: Representation and LearningAntonio Vergari · Probabilistic Circuits and Logic 2023
• 01h 06mNonparametric Bayesian Methods: Models, Algorithms, and Applications ITamara Broderick · Foundations of Machine Learning Boot Camp 2017
• 49mSpectral Algorithms for Learning Latent Variable ModelsSham Kakade · Spectral Algorithms: From Theory to Practice 2014
• 35mLearning General Gaussian Mixtures With Efficient Score MatchingVasilis Kontonis · Joint IFML/MPG Symposium 2024