A Caltech Library Service

Learning Latent Tree Graphical Models

Choi, Myung Jin and Tan, Vincent Y. F. and Anandkumar, Animashree and Willsky, Alan S. (2011) Learning Latent Tree Graphical Models. Journal of Machine Learning Research, 12 . pp. 1771-1812. ISSN 1533-7928.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We study the problem of learning a latent tree graphical model where samples are available only from a subset of variables. We propose two consistent and computationally efficient algorithms for learning minimal latent trees, that is, trees without any redundant hidden nodes. Unlike many existing methods, the observed nodes (or variables) are not constrained to be leaf nodes. Our algorithms can be applied to both discrete and Gaussian random variables and our learned models are such that all the observed and latent variables have the same domain (state space). Our first algorithm, recursive grouping, builds the latent tree recursively by identifying sibling groups using so-called information distances. One of the main contributions of this work is our second algorithm, which we refer to as CLGrouping. CLGrouping starts with a pre-processing procedure in which a tree over the observed variables is constructed. This global step groups the observed nodes that are likely to be close to each other in the true latent tree, thereby guiding subsequent recursive grouping (or equivalent procedures such as neighbor-joining) on much smaller subsets of variables. This results in more accurate and efficient learning of latent trees. We also present regularized versions of our algorithms that learn latent tree approximations of arbitrary distributions. We compare the proposed algorithms to other methods by performing extensive numerical experiments on various latent tree graphical models such as hidden Markov models and star graphs. In addition, we demonstrate the applicability of our methods on real-world data sets by modeling the dependency structure of monthly stock returns in the S&P index and of the words in the 20 newsgroups data set.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2011 Myung Jin Choi, Vincent Y. F. Tan, Animashree Anandkumar and Alan S. Willsky. Submitted 9/10; Revised 2/11; Published 5/11. This research was supported in part by Shell International Exploration and Production, Inc. and in part by the Air Force Office of Scientific Research under Award No. FA9550-06-1-0324. This work was also supported in part by AFOSR under Grant FA9550-08-1-1080 and in part by MURI under AFOSR Grant FA9550-06-1-0324. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the author(s) and do not necessarily reflect the views of the Air Force. Vincent Tan and Animashree Anandkumar are supported by A*STAR, Singapore and by the setup funds at U.C. Irvine respectively.
Funding AgencyGrant Number
Shell International Exploration and Production, Inc.UNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-06-1-0324
Air Force Office of Scientific Research (AFOSR)FA9550-08-1-1080
Air Force Office of Scientific Research (AFOSR)FA9550-06-1-0324
Agency for Science, Technology and Research (A*STAR)UNSPECIFIED
University of California, IrvineUNSPECIFIED
Subject Keywords:graphical models, Markov random fields, hidden variables, latent tree models, structure learning
Record Number:CaltechAUTHORS:20170927-100701408
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:81875
Deposited By: Tony Diaz
Deposited On:27 Sep 2017 17:19
Last Modified:03 Oct 2019 18:48

Repository Staff Only: item control page