Learning Graphical Models Using Multiplicative Weights

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).

Authors

• Adam R. Klivans
• Raghu Meka

Keywords

• Complexity theory
• Markov processes
• Graphical models
• Algorithm design and analysis
• Computer science
• Machine learning algorithms
• Mathematical model
• Graphical Model
• Model Parameters
• General Linear Model
• Running Time
• Efficient Algorithm
• Ising Model
• Markov Random Field
• Boltzmann Machine
• Statistical Distance
• Probability Density Function
• Weight Vector
• Precise Conditions
• Monomial
• Neighboring Vertices
• Dependency Graph
• Online Manner
• Unbiased Distribution
• Markov Random Fields
• MRFs
• learning
• generalized linear models
• multiplicative weights
• sigmoid
• sparsity