Home Page

Papers

Submissions

News

Scope

Editorial Board

Announcements

Proceedings

Open Source Software

Search

Login



RSS Feed

Hierarchical Tensor Decomposition of Latent Tree Graphical Models

Le Song, Mariya Ishteva, Ankur Parikh, Eric Xing, Haesun Park
;
JMLR W&CP 28 (3) : 334–342, 2013

Abstract

We approach the problem of estimating the parameters of a latent tree graphical model from a hierarchical tensor decomposition point of view. In this new view, the marginal probability table of the observed variables in a latent tree is treated as a tensor, and we show that: (i) the latent variables induce low rank structures in various matricizations of the tensor; (ii) this collection of low rank matricizations induce a hierarchical low rank decomposition of the tensor. Exploiting these properties, we derive an optimization problem for estimating the parameters of a latent tree graphical model, i.e., hierarchical decomposion of a tensor which minimizes the Frobenius norm of the difference between the original tensor and its decomposition. When the latent tree graphical models are correctly specified, we show that a global optimum of the optimization problem can be obtained via a recursive decomposition algorithm. This algorithm recovers previous spectral algorithms for hidden Markov models (Hsu et al., 2009; Foster et al., 2012) and latent tree graphical models (Parikh et al., 2011; Song et al., 2011) as special cases, elucidating the global objective these algorithms are optimizing for. When the latent tree graphical models are misspecified, we derive a better decomposition based on our framework, and provide approximation guarantee for this new estimator. In both synthetic and real world data, this new estimator significantly improves over the-state-of-the-art.

Related Material