Spectral Methods for Learning Multivariate Latent Tree Structure
Spectral Methods for Learning Multivariate Latent Tree Structure
复制标题
DOI：
--
复制
发表时间：
2011-07
期刊：
影响因子：
--
通讯作者：
O. Tamuz;Ce Liu;Serge J. Belongie;Ohad Shamir;A. Kalai
中科院分区：
文献类型：
--
作者：
O. Tamuz;Ce Liu;Serge J. Belongie;Ohad Shamir;A. Kalai
本文研究了多元线性树模型的结构学习问题，包括各种具有连续、离散和混合潜在变量的有向树图模型，如线性-高斯模型、隐马尔可夫模型、高斯混合模型和马尔可夫进化树。设置是这样的：我们只有树中某些观察变量的样本，我们的目标是估计树结构(即，潜在隐藏变量如何相互连接以及如何连接到观察变量的图)。我们提出了谱递归分组算法，这是一种从观察变量的独立样本中恢复树结构的有效且简单的自下而上的过程。我们精确恢复树结构的有限样本量界限揭示了对潜在联合分布的潜在统计和结构属性的某些自然依赖性。此外，我们的样本复杂性保证不依赖于观察变量的维度，使得该算法适用于许多高维设置。我们算法的核心是一个谱四元组测试，用于从二阶统计量中确定四个变量组的相对拓扑。
This work considers the problem of learning the structure of multivariate linear tree models, which include a variety of directed tree graphical models with continuous, discrete, and mixed latent variables such as linear-Gaussian models, hidden Markov models, Gaussian mixture models, and Markov evolutionary trees. The setting is one where we only have samples from certain observed variables in the tree, and our goal is to estimate the tree structure (i.e., the graph of how the underlying hidden variables are connected to each other and to the observed variables). We propose the Spectral Recursive Grouping algorithm, an efficient and simple bottom-up procedure for recovering the tree structure from independent samples of the observed variables. Our finite sample size bounds for exact recovery of the tree structure reveal certain natural dependencies on underlying statistical and structural properties of the underlying joint distribution. Furthermore, our sample complexity guarantees have no explicit dependence on the dimensionality of the observed variables, making the algorithm applicable to many high-dimensional settings. At the heart of our algorithm is a spectral quartet test for determining the relative topology of a quartet of variables from second-order statistics.