Estimation of Graphical Models Using Generalized Covariance Matrices
Explore the structure estimation for discrete graphical models by analyzing the relationships between conditional independence and inverse covariance matrices. The extension of Gaussian graphical models, Ising models, and more is discussed, providing insights into graph structures based on covariance matrices.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses Menglong Li Ph.d of Industrial Engineering Dec 1st2016
Outline Recap: Gaussian graphical model Extend to general graphical model 1. Model setting 2. Results 3. Application Statistical results
Gaussian graphical model = Theorem: For if and only if ( , ), x N h J x 0 ij J -1 - - x x \{ , } i j i V j encodes the pairwise Markov independencies, and we can recover the graph structure by adding edges with However, the question of whether a relationship exists between conditional independence and the structure of the inverse covariance matrix in a general graph remains unresolved. J 0 ij J
How to extend? Example 1: Ising model: let the node potentials be for all and the edge potentials be for all , 2 = st ( , ) s t E s V = s ={0 1} 0.1
Continue of Example 1 The inverse of covariance matrix is This matrix is graph structured!
How to extend? Example 2:
Continue of Example 2 The inverse of covariance matrix is This matrix is not graph structured!
How to extend? Example 3: The inverse of covariance matrix is graph structured!
Continue of Example 2 Instead of consider the original graph, we consider the triangulation graph of G as right we compute the covariance matrix of the augmented random vector where the extra term is represented by the dotted edge shown (the 2-clique ) 1 3 x x ( , x x x , ,x , ) 1 3 x x 1 2 3 4 1 3 x x
Continue of Example 2 The inverse of this generalized covariance matrix takes the form If we add all the representation of power set of maximal cliques of triangulated G, compute the covariance of following vector:
Continue of Example 2 cov( (x)) Empirically, we find that the 11 11 inverse of the matrix continues to respect aspects of the graph structure: in particular, there are zeros in position , corresponding to the associated functions and whenever and do not lie within the same maximal clique ( , ) = = x x x x s s s s
Main results Theorem: Consider an arbitrary discrete graphical model of the form
Statistical results Suppose we are given n samples drawn from a discrete graphical model, i.i.d. How to recover the graph structure? Algorithm(Graphical Lasso): 1. 2. 3. This program is called graphical lasso.
Statistical results Mutual incoherence condition:
Reference Loh, P. L., & Wainwright, M. J. (2013). Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses. The Annals of Statistics, 41(6), 3022-3049.
