Learning Graphical Models Using Multiplicative Weights
Authors:
- Adam KlivansAKAdam Klivans
- Raghu MekaRMRaghu Meka
- 1 October 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 343-354
Abstract
We give a simple, multiplicative-weight update algorithm for learning undirected graphical models or Markov random fields (MRFs). The approach is new, and for the well-studied case of Ising models or Boltzmann machines we obtain an algorithm that uses a nearly optimal number of samples and has running time Õ(n 2 ) (where n is the dimension), subsuming and improving on all prior work. Additionally, we give the first efficient algorithm for learning Ising models over non-binary alphabets. Our main application is an algorithm for learning the structure of t-wise MRFs with nearly-optimal sample complexity (up to polynomial losses in necessary terms that depend on the weights) and running time that is n O(t) . In addition, given n O(t) samples, we can also learn the parameters of the model and generate a hypothesis that is close in statistical distance to the true MRF. All prior work runs in time n Ω(d) for graphs of bounded degree d and does not generate a hypothesis close in statistical distance even for t = 3. We observe that our runtime has the correct dependence on n and t assuming the hardness of learning sparse parities with noise. Our algorithm- the Sparsitron- is easy to implement (has only one parameter) and holds in the on-line setting. Its analysis applies a regret bound from Freund and Schapires classic Hedge algorithm. It also gives the first solution to the problem of learning sparse Generalized Linear Models (GLMs).Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Efficiently Learning Ising Models on Arbitrary Graphs2015
- Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair ProblemJournal of the ACM, 2015
- Robust Estimation of Latent Tree Graphical Models: Inferring Hidden States With Inexact ParametersIEEE Transactions on Information Theory, 2013
- Reconstruction of Markov Random Fields from Samples: Some Observations and AlgorithmsSIAM Journal on Computing, 2013
- Greedy learning of graphical models with small girth2012
- Information-Theoretic Limits of Selecting Binary Graphical Models in High DimensionsIEEE Transactions on Information Theory, 2012
- On Agnostic Learning of Parities, Monomials, and HalfspacesSIAM Journal on Computing, 2009
- Towards an Integrated Protein–Protein Interaction Network: A Relational Markov Network ApproachJournal of Computational Biology, 2006
- Factor graphs and the sum-product algorithmIEEE Transactions on Information Theory, 2001
- A Decision-Theoretic Generalization of On-Line Learning and an Application to BoostingJournal of Computer and System Sciences, 1997