On Finding Modes of Gaussian Sum-Product Networks
summary
Shows a practical algorithm—modal EM / mean‑shift for Gaussian SPNs—that runs by propagating two arrays of per‑variable numerators and denominators up the circuit, returns a non‑decreasing update and usually converges to a mode (saddle points rare). Gives hardness results: max‑product yields only linear worst‑case guarantees for shallow SPNs and exponential inapproximability with depth, so max‑product is essentially best worst‑case. Demonstrates modal clustering on MNIST and image segmentation, observes many more modes than components, and flags open questions about mode count and location.
AI-written summary · about
chapters (12)
- 0:00Introduction to mode finding
- 1:09Defining and using modes
- 4:04Complexity and algorithms
- 6:42Gaussian leaf considerations
- 9:11Max product heuristic
- 11:45Approximation bounds
- 15:02Continuation methods
- 20:50Gaussian mean shift algorithm
- 25:11Implementation in circuits
- 29:36Practical applications
- 34:40Model complexity analysis
- 37:05Challenges and conclusion
related talks
01h 08mTutorial: Methods from Statistical Physics III
27mAlmost-Orthogonal Bases for Inner Product Polynomials
01h 06mTutorial: Methods from Statistical Physics II
01h 31mUnsupervised Learning
58mUniversality of Approximate Message Passing on Semi-random Matrices
49mAnalysis of Algorithms on Dense Matrices using Approximate Message Passing
20mInference of Probabilistic Programs with Moment-Matching Gaussian Mixtures
35mPhase Retrieval In High Dimensions: Statistical And Computational Phase Transitions