Learning Gaussian Graphical Models with Observed or Latent FVSs
By Ying Liu, Alan S. Willsky. 2013
26 citations recorded by the source corpus.
Gaussian Graphical Models (GGMs) or Gauss Markov random fields are widely used in many applications, and the trade-off between the modeling capacity and the efficiency of learning and inference has been an important research problem. In this paper, we study the family of GGMs with small feedback vertex sets (FVSs), where an FVS is a set of nodes whose removal breaks all the cycles. Exact inference such as computing the marginal distributions and the partition function has complexity O(k2n) using message-passing algorithms, where k is the size of the FVS, and n is the total number of nodes. We propose efficient structure learning algorithms for two cases: 1) All nodes are observed, which is useful in modeling social or flight networks where the FVS nodes often correspond to a small number of highly influential nodes, or hubs, while the rest of the networks is modeled by a tree. Regardless of the maximum degree, without knowing the full graph structure, we can exactly compute the maximum likelihood estimate with complexity O(kn2 + n2 log n) if the FVS is known or in polynomial time if the FVS is unknown but has bounded size. 2) The FVS nodes are latent variables, where structure learning is equivalent to decomposing an inverse covariance matrix (exactly or approximately) into the sum of a tree-structured matrix and a low-rank matrix. By incorporating efficient inference into the learning steps, we can obtain a learning algorithm using alternating low-rank corrections with complexity O(kn2 + n2 log n) per iteration. We perform experiments using both synthetic data as well as real data of flight delays to demonstrate the modeling capacity with FVSs of various sizes.
Subfields: Artificial Intelligence, Statistics and Probability
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Lawrence Carin
- Changyou Chen
- Qinliang Su
- Xuejun Liao
- A. Hero
- Brian Eriksson
- Zhaoshi Meng
- Chunyuan Li
In Statistics and Probability
- Changyou Chen
- Lawrence Carin
- Qinliang Su
- Xuejun Liao
- A. Hero
- Brian Eriksson
- Zhaoshi Meng
- Chunyuan Li
Citations in the corpus
- Nonlinear Statistical Learning with Truncated Gaussian Graphical Models (2016, background): “Gaussian graphical models (GGM) constitute a subset of graphical models that have found successful application in a diverse range of areas (Honorio et al., 2009; Liu & Willsky, 2013; Oh & Deasy, 2014; Meng et al., 2014; Su & Wu, 2015a;b).”
- Learning Latent Variable Gaussian Graphical Models (2014, background): “Recently, Liu & Willsky (2013) consider a computationally efficient learning algorithm for a class of conditionally tree-structured LVGGM.”