Learning Restricted Boltzman Machines
summary
Proves bounded‑degree RBMs exactly capture order‑T binary Markov random fields, giving a sharp representational characterization; shows improper learning of general RBMs is as hard as sparse parity with noise, even with constant hidden count and degree. Gives a greedy, F(D)·poly(n) time algorithm with F(D) sample complexity ~F(D)·log n that learns ferromagnetic RBMs by maximizing a monotone, discrete influence function (a multilinear/concavity of magnetization consequence) and outputs an explicit MRF on observed nodes.
AI-written summary · about
chapters (10)
- 0:00Introduction to graphical models
- 4:36State of the art in learning
- 6:20Restricted Boltzmann machines
- 8:31Technical challenges and complexity
- 13:32Representational power and hardness
- 16:43Ferromagnetic RBMs
- 18:42Submodularity and influence
- 23:54Greedy learning algorithm
- 29:03Mathematical physics connection
- 35:09Summary and future directions
related talks
59mWhen do dependencies in your data help?
48mLearning by Local Entropy Maximization
30mComputational Barriers For Learning Some Generalized Linear Models
31mStrong Data Processing Inequalities and Estimation with Constraints
01h 01mRobustness, Stochastics, Uncertainty 1
36mTo Be (Hard) or Not Be:...
15mFundamental Limits Of Learning In Data-Driven Problems
43mCoin-Flipping in the Brain: Probabilistic Computation and Learning in the Assembly Model