Learning loopy graphical models with latent variables: Efficient methods and guarantees

Abstract

The problem of structure estimation in graphical models with latent variables is considered. We characterize conditions for tractable graph estimation and develop efficient methods with provable guarantees. We consider models where the underlying Markov graph is locally tree-like, and the model is in the regime of correlation decay. For the special case of the Ising model, the number of samples $n$ required for structural consistency of our method scales as $n=\Omega ({\theta }_{\min }^{-\delta \eta (\eta +1)-2}\log p)$, where p is the number of variables, ${\theta }_{\min }$ is the minimum edge potential, $\delta$ is the depth (i.e., distance from a hidden node to the nearest observed nodes), and $\eta$ is a parameter which depends on the bounds on node and edge potentials in the Ising model. Necessary conditions for structural consistency under any algorithm are derived and our method nearly matches the lower bound on sample requirements. Further, the proposed method is practical to implement and provides flexibility to control the number of latent variables and the cycle lengths in the output graph.

Published in at http://dx.doi.org/10.1214/12-AOS1070 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (12)

• High-dimensional graphs and variable selection with the Lasso
• High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression
• Latent variable graphical model selection via convex optimization
• Ising models on locally tree-like graphs
• A Spectral Algorithm for Learning Hidden Markov Models
• High-dimensional structure estimation in Ising models: Local separation criterion
• High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion
• On Learning Discrete Graphical Models Using Greedy Methods
• Spectral Methods for Learning Multivariate Latent Tree Structure
• On the girth of random Cayley graphs
• Learning nonsingular phylogenies and hidden Markov models
• Learning Latent Tree Graphical Models

Cited by in corpus (10)

• Local Tomography of Large Networks under the Low-Observability Regime
• Information Theoretic Structure Learning with Confidence
• Learning High-Dimensional Mixtures of Graphical Models
• Recovering the Graph Underlying Networked Dynamical Systems under Partial Observability: A Deep Learning Approach
• Predictive Learning on Hidden Tree-Structured Ising Models
• Learning latent causal graphs via mixture oracles
• Learning Restricted Boltzmann Machines with Sparse Latent Variables
• Learning to Sample from Censored Markov Random Fields
• Learning Restricted Boltzmann Machines with Arbitrary External Fields
• Topology Inference over Networks with Nonlinear Coupling