The Experts below are selected from a list of 125058 Experts worldwide ranked by ideXlab platform
Alan S Willsky - One of the best experts on this subject based on the ideXlab platform.
-
latent variable Graphical Model selection via convex optimization
Annals of Statistics, 2012Co-Authors: Venkat Chandrasekaran, Pablo A Parrilo, Alan S WillskyAbstract:Suppose we observe samples of a subset of a collection of random variables. No additional information is provided about the number of latent variables, nor of the relationship between the latent and observed variables. Is it possible to discover the number of latent components, and to learn a statistical Model over the entire collection of variables? We address this question in the setting in which the latent and observed variables are jointly Gaussian, with the conditional statistics of the observed variables conditioned on the latent variables being specified by a Graphical Model. As a first step we give natural conditions under which such latent-variable Gaussian Graphical Models are identifiable given marginal statistics of only the observed variables. Essentially these conditions require that the conditional Graphical Model among the observed variables is sparse, while the effect of the latent variables is “spread out” over most of the observed variables. Next we propose a tractable convex program based on regularized maximum-likelihood for Model selection in this latent-variable setting; the regularizer uses both the $\ell_{1}$ norm and the nuclear norm. Our Modeling framework can be viewed as a combination of dimensionality reduction (to identify latent variables) and Graphical Modeling (to capture remaining statistical structure not attributable to the latent variables), and it consistently estimates both the number of latent components and the conditional Graphical Model structure among the observed variables. These results are applicable in the high-dimensional setting in which the number of latent/observed variables grows with the number of samples of the observed variables. The geometric properties of the algebraic varieties of sparse matrices and of low-rank matrices play an important role in our analysis.
-
high dimensional gaussian Graphical Model selection walk summability and local separation criterion
Journal of Machine Learning Research, 2012Co-Authors: Animashree Anandkumar, Furong Huang, Alan S WillskyAbstract:We consider the problem of high-dimensional Gaussian Graphical Model selection. We identify a set of graphs for which an efficient estimation algorithm exists, and this algorithm is based on thresholding of empirical conditional covariances. Under a set of transparent conditions, we establish structural consistency (or sparsistency) for the proposed algorithm, when the number of samples n = Ω(Jmin-2 log p), where p is the number of variables and Jmin is the minimum (absolute) edge potential of the Graphical Model. The sufficient conditions for sparsistency are based on the notion of walk-summability of the Model and the presence of sparse local vertex separators in the underlying graph. We also derive novel non-asymptotic necessary conditions on the number of samples required for sparsistency.
-
high dimensional Graphical Model selection tractable graph families and necessary conditions
Willsky via Amy Stout, 2011Co-Authors: Animashree Anandkumar, Vincent Y F Tan, Alan S WillskyAbstract:We consider the problem of Ising and Gaussian Graphical Model selection given n i.i.d. samples from the Model. We propose an efficient threshold-based algorithm for structure estimation based on conditional mutual information thresholding. This simple local algorithm requires only low-order statistics of the data and decides whether two nodes are neighbors in the unknown graph. We identify graph families for which the proposed algorithm has low sample and computational complexities. Under some transparent assumptions, we establish that the proposed algorithm is structurally consistent (or sparsistent) when the number of samples scales as n = Ω(J-1min log p), where p is the number of nodes and Jmin is the minimum edge potential. We also develop novel non-asymptotic techniques for obtaining necessary conditions for Graphical Model selection.
-
high dimensional gaussian Graphical Model selection walk summability and local separation criterion
arXiv: Learning, 2011Co-Authors: Animashree Anandkumar, Alan S WillskyAbstract:We consider the problem of high-dimensional Gaussian Graphical Model selection. We identify a set of graphs for which an efficient estimation algorithm exists, and this algorithm is based on thresholding of empirical conditional covariances. Under a set of transparent conditions, we establish structural consistency (or sparsistency) for the proposed algorithm, when the number of samples n=omega(J_{min}^{-2} log p), where p is the number of variables and J_{min} is the minimum (absolute) edge potential of the Graphical Model. The sufficient conditions for sparsistency are based on the notion of walk-summability of the Model and the presence of sparse local vertex separators in the underlying graph. We also derive novel non-asymptotic necessary conditions on the number of samples required for sparsistency.
-
latent variable Graphical Model selection via convex optimization
Allerton Conference on Communication Control and Computing, 2010Co-Authors: Venkat Chandrasekaran, Pablo A Parrilo, Alan S WillskyAbstract:Suppose we have samples of a subset of a collection of random variables. No additional information is provided about the number of latent variables, nor of the relationship between the latent and observed variables. Is it possible to discover the number of hidden components, and to learn a statistical Model over the entire collection of variables? We address this question in the setting in which the latent and observed variables are jointly Gaussian, with the conditional statistics of the observed variables conditioned on the latent variables being specified by a Graphical Model. As a first step we give natural conditions under which such latent-variable Gaussian Graphical Models are identifiable given marginal statistics of only the observed variables. Essentially these conditions require that the conditional Graphical Model among the observed variables is sparse, while the effect of the latent variables is “spread out” over most of the observed variables. Next we propose a tractable convex program based on regularized maximum-likelihood for Model selection in this latent-variable setting; the regularizer uses both the l 1 norm and the nuclear norm. Our Modeling framework can be viewed as a combination of dimensionality reduction (to identify latent variables) and Graphical Modeling (to capture remaining statistical structure not attributable to the latent variables), and it consistently estimates both the number of hidden components and the conditional Graphical Model structure among the observed variables. These results are applicable in the high-dimensional setting in which the number of latent/observed variables grows with the number of samples of the observed variables. The geometric properties of the algebraic varieties of sparse matrices and of low-rank matrices play an important role in our analysis.
Martin J. Wainwright - One of the best experts on this subject based on the ideXlab platform.
-
Discussion: Latent variable Graphical Model selection via convex optimization
Annals of Statistics, 2012Co-Authors: Martin J. WainwrightAbstract:Discussion of "Latent variable Graphical Model selection via convex optimization" by Venkat Chandrasekaran, Pablo A. Parrilo and Alan S. Willsky [arXiv:1008.1290].
-
information theoretic limits of Graphical Model selection in high dimensions
International Symposium on Information Theory, 2008Co-Authors: Narayana Santhanam, Martin J. WainwrightAbstract:The problem of Graphical Model selection is to correctly estimate the graph structure of a Markov random field given samples from the underlying distribution. We analyze the information-theoretic limitations of this problem under high-dimensional scaling, in which the graph size p and the number of edges k (or the maximum degree d) are allowed to increase to infinity as a function of the sample size n. For pairwise binary Markov random fields, we derive both necessary and sufficient conditions on the scaling of the triplet (n, p, k) (or the triplet (n, p, d)) for asympotically reliable reocovery of the graph structure.
Venkat Chandrasekaran - One of the best experts on this subject based on the ideXlab platform.
-
latent variable Graphical Model selection via convex optimization
Annals of Statistics, 2012Co-Authors: Venkat Chandrasekaran, Pablo A Parrilo, Alan S WillskyAbstract:Suppose we observe samples of a subset of a collection of random variables. No additional information is provided about the number of latent variables, nor of the relationship between the latent and observed variables. Is it possible to discover the number of latent components, and to learn a statistical Model over the entire collection of variables? We address this question in the setting in which the latent and observed variables are jointly Gaussian, with the conditional statistics of the observed variables conditioned on the latent variables being specified by a Graphical Model. As a first step we give natural conditions under which such latent-variable Gaussian Graphical Models are identifiable given marginal statistics of only the observed variables. Essentially these conditions require that the conditional Graphical Model among the observed variables is sparse, while the effect of the latent variables is “spread out” over most of the observed variables. Next we propose a tractable convex program based on regularized maximum-likelihood for Model selection in this latent-variable setting; the regularizer uses both the $\ell_{1}$ norm and the nuclear norm. Our Modeling framework can be viewed as a combination of dimensionality reduction (to identify latent variables) and Graphical Modeling (to capture remaining statistical structure not attributable to the latent variables), and it consistently estimates both the number of latent components and the conditional Graphical Model structure among the observed variables. These results are applicable in the high-dimensional setting in which the number of latent/observed variables grows with the number of samples of the observed variables. The geometric properties of the algebraic varieties of sparse matrices and of low-rank matrices play an important role in our analysis.
-
latent variable Graphical Model selection via convex optimization
Allerton Conference on Communication Control and Computing, 2010Co-Authors: Venkat Chandrasekaran, Pablo A Parrilo, Alan S WillskyAbstract:Suppose we have samples of a subset of a collection of random variables. No additional information is provided about the number of latent variables, nor of the relationship between the latent and observed variables. Is it possible to discover the number of hidden components, and to learn a statistical Model over the entire collection of variables? We address this question in the setting in which the latent and observed variables are jointly Gaussian, with the conditional statistics of the observed variables conditioned on the latent variables being specified by a Graphical Model. As a first step we give natural conditions under which such latent-variable Gaussian Graphical Models are identifiable given marginal statistics of only the observed variables. Essentially these conditions require that the conditional Graphical Model among the observed variables is sparse, while the effect of the latent variables is “spread out” over most of the observed variables. Next we propose a tractable convex program based on regularized maximum-likelihood for Model selection in this latent-variable setting; the regularizer uses both the l 1 norm and the nuclear norm. Our Modeling framework can be viewed as a combination of dimensionality reduction (to identify latent variables) and Graphical Modeling (to capture remaining statistical structure not attributable to the latent variables), and it consistently estimates both the number of hidden components and the conditional Graphical Model structure among the observed variables. These results are applicable in the high-dimensional setting in which the number of latent/observed variables grows with the number of samples of the observed variables. The geometric properties of the algebraic varieties of sparse matrices and of low-rank matrices play an important role in our analysis.
Pablo A Parrilo - One of the best experts on this subject based on the ideXlab platform.
-
latent variable Graphical Model selection via convex optimization
Annals of Statistics, 2012Co-Authors: Venkat Chandrasekaran, Pablo A Parrilo, Alan S WillskyAbstract:Suppose we observe samples of a subset of a collection of random variables. No additional information is provided about the number of latent variables, nor of the relationship between the latent and observed variables. Is it possible to discover the number of latent components, and to learn a statistical Model over the entire collection of variables? We address this question in the setting in which the latent and observed variables are jointly Gaussian, with the conditional statistics of the observed variables conditioned on the latent variables being specified by a Graphical Model. As a first step we give natural conditions under which such latent-variable Gaussian Graphical Models are identifiable given marginal statistics of only the observed variables. Essentially these conditions require that the conditional Graphical Model among the observed variables is sparse, while the effect of the latent variables is “spread out” over most of the observed variables. Next we propose a tractable convex program based on regularized maximum-likelihood for Model selection in this latent-variable setting; the regularizer uses both the $\ell_{1}$ norm and the nuclear norm. Our Modeling framework can be viewed as a combination of dimensionality reduction (to identify latent variables) and Graphical Modeling (to capture remaining statistical structure not attributable to the latent variables), and it consistently estimates both the number of latent components and the conditional Graphical Model structure among the observed variables. These results are applicable in the high-dimensional setting in which the number of latent/observed variables grows with the number of samples of the observed variables. The geometric properties of the algebraic varieties of sparse matrices and of low-rank matrices play an important role in our analysis.
-
latent variable Graphical Model selection via convex optimization
Allerton Conference on Communication Control and Computing, 2010Co-Authors: Venkat Chandrasekaran, Pablo A Parrilo, Alan S WillskyAbstract:Suppose we have samples of a subset of a collection of random variables. No additional information is provided about the number of latent variables, nor of the relationship between the latent and observed variables. Is it possible to discover the number of hidden components, and to learn a statistical Model over the entire collection of variables? We address this question in the setting in which the latent and observed variables are jointly Gaussian, with the conditional statistics of the observed variables conditioned on the latent variables being specified by a Graphical Model. As a first step we give natural conditions under which such latent-variable Gaussian Graphical Models are identifiable given marginal statistics of only the observed variables. Essentially these conditions require that the conditional Graphical Model among the observed variables is sparse, while the effect of the latent variables is “spread out” over most of the observed variables. Next we propose a tractable convex program based on regularized maximum-likelihood for Model selection in this latent-variable setting; the regularizer uses both the l 1 norm and the nuclear norm. Our Modeling framework can be viewed as a combination of dimensionality reduction (to identify latent variables) and Graphical Modeling (to capture remaining statistical structure not attributable to the latent variables), and it consistently estimates both the number of hidden components and the conditional Graphical Model structure among the observed variables. These results are applicable in the high-dimensional setting in which the number of latent/observed variables grows with the number of samples of the observed variables. The geometric properties of the algebraic varieties of sparse matrices and of low-rank matrices play an important role in our analysis.
Shiqian Ma - One of the best experts on this subject based on the ideXlab platform.
-
Alternating direction methods for latent variable gaussian Graphical Model selection
Neural Computation, 2013Co-Authors: Shiqian MaAbstract:Chandrasekaran, Parrilo, and Willsky 2012 proposed a convex optimization problem for Graphical Model selection in the presence of unobserved variables. This convex optimization problem aims to estimate an inverse covariance matrix that can be decomposed into a sparse matrix minus a low-rank matrix from sample data. Solving this convex optimization problem is very challenging, especially for large problems. In this letter, we propose two alternating direction methods for solving this problem. The first method is to apply the classic alternating direction method of multipliers to solve the problem as a consensus problem. The second method is a proximal gradient-based alternating-direction method of multipliers. Our methods take advantage of the special structure of the problem and thus can solve large problems very efficiently. A global convergence result is established for the proposed methods. Numerical results on both synthetic data and gene expression data show that our methods usually solve problems with 1 million variables in 1 to 2 minutes and are usually 5 to 35i¾ times faster than a state-of-the-art Newton-CG proximal point algorithm.
