Statistics and Its Interface

Volume 10 (2017)

Number 4

Spectral methods for learning discrete latent tree models

Pages: 677 – 698

DOI: https://dx.doi.org/10.4310/SII.2017.v10.n4.a11

Authors

Xiaofei Wang (Key Laboratory for Applied Statistics of MOE, School of Mathematics and Statistics, Northeast Normal University, Changchun, Jilin Province, China)

Jianhua Guo (Key Laboratory for Applied Statistics of MOE, School of Mathematics and Statistics, Northeast Normal University, Changchun, Jilin Province, China)

Lizhu Hao (Key Laboratory for Applied Statistics of MOE, School of Mathematics and Statistics, Northeast Normal University, Changchun, Jilin Province, China)

Nevin L. Zhang (Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Kowloon, Hong Kong)

Abstract

We consider the problems of structure learning and parameter estimation for discrete latent tree models. For structure learning, we introduce a concept of generalized information distance between variables based on singular values of probability matrices, and use it to build a bottom-up algorithm for structure recovery. The algorithm is proved to be consistent. Moreover, a finite sample bound is given for exact structure recovery. For parameter estimation, we suggest a novel matrix decomposition algorithm for the case when every latent variable has two states. Unlike the expectation-maximization (EM) algorithm, our algorithm can avoid trapping into a local optima. Moreover, it is proved to be consistent and a finite sample bound is also given for parameter estimation.

In both structural learning and parameter estimation, empirical results were provided to support our theoretical results. In applications to real data, we analyzed the Changchun mayor hotline data, where the underlying structures were detected for Chinese words. We demonstrated that the proposed method is efficient for discovering hierarchical structures and latent information.

Keywords

latent variables, parameter estimation, spectral distance, structural learning

2010 Mathematics Subject Classification

Primary 62H05. Secondary 62H12.

Full Text (PDF format)

Published 30 May 2017