A Junction Tree Framework for Undirected Graphical Model Selection
arXiv:1304.4910
Abstract
An undirected graphical model is a joint probability distribution defined on an undirected graph G*, where the vertices in the graph index a collection of random variables and the edges encode conditional independence relationships among random variables. The undirected graphical model selection (UGMS) problem is to estimate the graph G* given observations drawn from the undirected graphical model. This paper proposes a framework for decomposing the UGMS problem into multiple subproblems over clusters and subsets of the separators in a junction tree. The junction tree is constructed using a graph that contains a superset of the edges in G*. We highlight three main properties of using junction trees for UGMS. First, different regularization parameters or different UGMS algorithms can be used to learn different parts of the graph. This is possible since the subproblems we identify can be solved independently of each other. Second, under certain conditions, a junction tree based UGMS algorithm can produce consistent results with fewer observations than the usual requirements of existing algorithms. Third, both our theoretical and experimental results show that the junction tree framework does a significantly better job at finding the weakest edges in a graph than existing methods. This property is a consequence of both the first and second properties. Finally, we note that our framework is independent of the choice of the UGMS algorithm and can be used as a wrapper around standard UGMS algorithms for more accurate graph estimation.
arXiv commentThis paper will appear in the Journal of Machine Learning Research (JMLR). See http://www.ima.umn.edu/~dvats/JunctionTreeUGMS.html for code
References in corpus (10)
- Estimating high-dimensional directed acyclic graphs with the PC-algorithm
- High-dimensional Ising model selection using -regularized logistic regression
- Latent variable graphical model selection via convex optimization
- Kernel-based Conditional Independence Test and Application in Causal Discovery
- Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation
- Stability Approach to Regularization Selection (StARS) for High Dimensional Graphical Models
- Sparse Inverse Covariance Selection via Alternating Linearization Methods
- High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion
- High-dimensional Sparse Inverse Covariance Estimation using Greedy Methods
- Finding Non-overlapping Clusters for Generalized Inference Over Graphical Models