PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Latent Tree Graphical Models

Myung Jin Choi, Vincent Y. F. Tan, Animashree Anandkumar, Alan S. Willsky

arXiv:1009.2722v1stat.MLcs.IT

TL;DR

The paper studies how to learn latent tree graphical models when samples are available only for observed variables, while resolving ambiguity through minimal latent trees. It proposes recursive grouping and CLGrouping, then shows consistency, favorable complexity, and strong empirical performance across synthetic and real-world settings.

  • Problem

    Learning latent tree models from partially observed variables requires recovering hidden structure despite equivalence among models with the same observed distribution.

  • Method

    The paper proposes recursive grouping based on information distances and CLGrouping, which uses a Chow-Liu tree over observed variables to guide local latent-tree reconstruction.

  • Results

    The algorithms are structurally consistent, have sample complexity logarithmic in the number of observed variables, and show superior accuracy and computational efficiency in reported comparisons.

  • Takeaways & Limitations

    Recursive grouping suits trees with few hidden variables or smaller diameters, while CLGrouping is advantageous for trees with many hidden variables or larger diameters.

  • Takeaways & Limitations

    Recursive grouping has worst-case complexity O(m4), particularly for hidden Markov models, which can be computationally prohibitive when m is large.

Abstract

from arXiv · show

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 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) 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 datasets by modeling the dependency structure of monthly stock returns in the S&P index and of the words in the 20 newsgroups dataset.

1. Introduction

The paper addresses tractable learning of latent tree models from partially observed variables, focusing on minimal models and algorithms that remain applicable when observed nodes are internal. It introduces recursive grouping and CLGrouping, with consistency guarantees and empirical evaluation across synthetic and real-world settings.

  • Problem: Learning latent models requires determining the number of hidden variables, their structural relationships, and the parameters governing those relationships.The paper also identifies tractability, generalization, theory, and application context as algorithm-design concerns.
  • Motivation: Latent tree models represent observed and hidden variables in tree-structured graphical models, enabling straightforward and scalable inference.The paper situates these models in applications including bioinformatics and computer vision.
  • Contributions: The paper develops recursive grouping and CLGrouping using statistical information distances for discrete and Gaussian latent tree models.Recursive grouping builds the tree bottom-up by identifying sibling groups, while CLGrouping first constructs a Chow-Liu tree over observed variables to guide local reconstruction.
  • Evaluation: The algorithms receive consistency guarantees and are evaluated on models ranging from hidden Markov models to star and complete trees, as well as real-world datasets.The experiments include synthetic and real-world applications involving stock returns and document-word dependencies.
  • Identifiability: Because latent variables are unobserved, multiple models can induce the same observed distribution, motivating consistent learning of minimal latent trees without redundant hidden nodes.A hidden leaf can be added without changing the marginalized observed distribution, creating an equivalence class of models.
  • Contributions: Recursive grouping is faster for smaller-diameter graphs such as stars, whereas CLGrouping is more efficient for larger-diameter graphs such as hidden Markov models.The global preprocessing step in CLGrouping reduces the subsets handled by later reconstruction procedures.

2. Latent Tree Graphical Models

The paper formalizes latent tree graphical models, their identifiability, and the setting where only observed-node samples are available. It defines minimal tree extensions to remove redundant hidden nodes and states conditions under which the latent structure can be recovered.

  • Definitions: A latent tree has observed nodes V and hidden nodes H, with the effective depth measuring each hidden node’s distance to its closest observed node.The model is an undirected tree-structured graphical model whose nodes represent random variables.
  • Definitions: Tree-structured graphical models factorize using node marginals and edge pairwise distributions, which fully characterize the joint distribution.The model class considered includes discrete and Gaussian graphical models.
  • Learning setting: The learner observes only samples from V, and the goal is to recover the latent tree structure and parameters from those observed samples.Information distances between observed-variable pairs can be estimated from samples.
  • Minimality and identifiability: Minimal latent trees require every hidden variable to have at least three neighbors, which ensures that all leaves are observed but does not require every observed node to be a leaf.These conditions exclude redundant hidden nodes and define the identifiable tree class.
  • Minimality and identifiability: A non-minimal tree can share the same observed distribution as a minimal tree after redundant hidden variables are marginalized out.The figure illustrates non-identifiability when hidden nodes h4 and h5 have degree less than three.
  • Minimality and identifiability: For every tree-decomposable observed distribution, a minimal tree extension exists and is unique up to renaming variables or their values.For Gaussian and binary distributions with known observed marginals, the minimal extension can be recovered, and its structure is determined by observed pairwise distributions.
  • Consistency: For general discrete latent tree models, the paper proves structural consistency but does not guarantee risk consistency because parameters are subsequently estimated with EM.The two-step procedure first estimates structure and then uses EM for parameter estimation.

3. Information Distances

The paper defines information distances from pairwise distributions and shows that they form additive tree metrics for Gaussian and discrete tree-structured models. Differences between distances then identify parent-child and sibling relationships, including when observed nodes are internal.

  • Definitions: Information distances are defined from pairwise distributions for Gaussian and discrete graphical models, with a unified distance-matrix representation.For binary variables, the discrete distance reduces to a function of the correlation coefficient; symmetric discrete models admit a simpler form.
  • Additivity: Information distances are additive tree metrics for Gaussian and discrete distributions that are Markov on a tree.For every pair of vertices, the distance equals the sum of edge distances along their connecting path.
  • Additivity: Assigning each vertex pair its information distance makes the underlying tree a minimum spanning tree on the vertex set.The resulting minimum spanning tree uses the information-distance matrix as its edge-weight structure.
  • Testing Inter-Node Relationships: For three variables, Φijk := dik −djk compares their information distances and supports a test for parent-child and sibling relationships.The test distinguishes leaf-parent pairs, leaf siblings, and pairs that are neither siblings nor parent-child.
  • Testing Inter-Node Relationships: A constant Φijk equal to ±dij identifies a leaf-parent relation, while a constant value strictly between those bounds identifies two leaf siblings.When Φijk varies with k, the remaining cases distinguish other node relationships through the same distance-based test.

4. Recursive Grouping Algorithm Given Information Distances

Recursive grouping reconstructs a latent tree bottom-up by testing relationships within an active set and introducing hidden parents for sibling groups. With exact information distances, it recovers minimal latent trees correctly, but its complexity can be high for large-diameter trees.

  • Recursive Grouping: Recursive grouping repeatedly identifies family relationships, groups sibling nodes, and introduces parent nodes to build the latent tree bottom-up.The procedure allows observed variables to occur at arbitrary levels rather than restricting them to leaves.
  • Algorithm: RG initializes the active set with observed variables, computes all Φijk values, and forms a coarsest partition whose multi-node groups satisfy leaf-family relations.Singleton groups remain active, while groups without an observed parent receive a newly introduced hidden parent.
  • Algorithm: For each new hidden node, RG computes distances to other active nodes from child distances and the additive tree-metric identities.These updates provide all pairwise distances needed for the next active-set iteration.
  • Illustrative Example: RG recovers the original latent tree through successive active-set iterations in the illustrative example.The example reaches the original tree after the third iteration, with previously introduced hidden nodes participating in later iterations.
  • Guarantees: RG outputs the true latent tree correctly in time O(diam(Tp)m3) when the information-distance matrix is available.The theorem assumes Tp belongs to T≥3 and exact distances between observed nodes are known.
  • Computational Limitation: RG has worst-case complexity O(m4) for hidden Markov models, motivating a global pre-processing step to reduce complexity for large-diameter trees.The limitation arises from multiple local operations performed during recursive grouping.

5. CLGrouping Algorithm Given Information Distances

CLGrouping first constructs a Chow-Liu tree over observed variables, then reconstructs the latent tree by applying distance-based procedures to smaller node subsets. Surrogate-node and MST properties support exact recovery of minimal latent trees with lower complexity than recursive grouping alone.

  • CLGrouping procedure: CLGrouping uses a global Chow-Liu-tree preprocessing step to identify observed nodes that do not belong to the same sibling group.It then applies recursive grouping or neighbor-joining repeatedly to smaller subsets.
  • Chow-Liu preprocessing: For Gaussian and symmetric discrete models, the Chow-Liu tree equals the minimum spanning tree formed from information distances.This follows because mutual information decreases monotonically with information distance in these model classes.
  • Surrogate nodes: A hidden node’s surrogate is the observed node most strongly correlated with it, equivalently the node at minimum information distance; several nodes may share one surrogate.Observed nodes are their own surrogates, and inverse surrogate sets collect hidden nodes mapped to each observed node.
  • MST–latent-tree relationship: MST properties preserve neighboring surrogate relationships and imply that the observed-node MST can be obtained by sequentially contracting hidden–observed surrogate edges.These properties enable algorithms that transform the MST into the latent tree.
  • CLBlind and CLGrouping: CLBlind exactly recovers blind latent trees in O(m^2 log m), but only for a restricted subclass of minimal latent trees.Its blind transformation uses only the MST structure, while CLGrouping targets all minimal latent trees.
  • Correctness and complexity: CLRG exactly recovers any minimal latent tree in O(m^2 log m + |J|Δ^3(MST(V; D))), typically reducing computation relative to recursive grouping over all observed nodes.The complexity is low when the latent tree has small maximum degree and effective depth, and experiments demonstrate a significant speedup over RG.

6. Sample-Based Algorithms for Learning Latent Tree Structures

The paper extends latent-tree learning to sample-based settings by estimating information distances and relaxing recursive grouping and CLGrouping accordingly. These algorithms remain consistent, with logarithmic sample complexity in the number of observed variables for constant effective depth.

  • Distance estimation: Estimated information distances are obtained by maximum-likelihood estimates of Gaussian correlations or symmetric-discrete crossover probabilities.For both model classes, the estimated distances converge to the true distances at rate n^-1/2.
  • Relaxed RG: Relaxed RG replaces exact equality tests with thresholded tests, restricts computations to reliable short distances, and averages distance estimates for robustness.The modifications address noisy estimated distances and unreliable long-distance estimates.
  • Consistency guarantees: Relaxed RG is structurally consistent for all minimal latent trees and risk consistent for Gaussian and symmetric discrete distributions.With suitable thresholds, the result applies to structure and distribution reconstruction.
  • Sample complexity: For constant effective depth, relaxed RG has sample complexity logarithmic in m, the number of observed variables.The reconstruction error probabilities for structure and distribution can each be bounded by a desired η under the theorem's conditions.
  • Relaxed CLGrouping: CLGrouping constructs a Chow-Liu tree using estimated distances, then applies relaxed RG or NJ locally to neighborhoods around its internal nodes.The Chow-Liu tree is maximum-likelihood optimal for Gaussian and symmetric discrete distributions, with structure-learning error converging exponentially in sample size.
  • Relaxed CLGrouping: Relaxed CLRG is structurally and risk consistent under the stated distributional conditions, with logarithmic sample complexity when effective depth is constant.These guarantees parallel those established for relaxed RG.
  • Regularization: Regularized CLGrouping uses BIC to trade off empirical fit and model complexity when learning latent-tree approximations.The procedure stops when no subtree increases the BIC score or can target a specified number of hidden nodes.

7. Experimental Results

Experiments evaluate RG, NJ, CLRG, and CLNJ on synthetic latent trees and apply the methods to stock-return and newsgroup data. Performance depends strongly on tree structure, while Chow-Liu-guided methods improve accuracy or efficiency in several settings.

  • Synthetic simulations: Synthetic experiments compare RG, NJ, CLRG, and CLNJ using samples from latent trees with known structures and varying sample sizes.The simulations use Gaussian models, average performance over 200 runs, and evaluate structural and distributional reconstruction.
  • Synthetic simulations: The double star is easiest to recover, whereas the 5-complete tree is hardest; more hidden variables or greater effective depth generally increase difficulty.The comparison holds for the same number of observed variables.
  • Synthetic simulations: RG exactly recovers the double-star structure in all 200 runs with 1,000 samples, while CLGrouping performs significantly better than RG for the HMM.For the HMM, the Chow-Liu tree is closer to a chain and permits smaller local neighborhoods for subsequent grouping.
  • Synthetic simulations: CLNJ has the best structure-recovery error rate and KL divergence on the 5-complete tree, while CLRG is significantly faster than RG on HMM and 5-complete graphs.NJ is fastest overall, but CLNJ remains efficient and produces more accurate latent-tree reconstructions.
  • Synthetic simulations: Overall, RG is most accurate for trees with few hidden variables, whereas CLNJ performs best for large-diameter trees and CLGrouping methods outperform NJ and RG on multilayer trees.The authors report that multilayer latent trees are difficult for every method.
  • Real-world applications: On monthly S&P 100 stock returns, CLNJ achieves the highest log-likelihood and BIC scores, while NJ introduces more hidden variables and has lower log-likelihoods.The experiment uses monthly returns from 84 companies from 1990 to 2007.
  • Real-world applications: On the 20 Newsgroups dataset, LCM achieves the best BIC despite many parameters, but its learned models reveal little structure, cost more to learn, and may overfit.The study uses 16,242 binary samples involving 100 words and compares several latent-tree methods.
  • Real-world applications: The learned regCLRG tree contains hidden variables interpretable as topics, while words with multiple meanings appear in multiple topic-related parts of the tree.Examples include sports, computer technology, and medical topics.

8. Conclusion

The paper introduces recursive grouping and CLGrouping for learning latent trees from information distances, including regularized variants for approximating arbitrary distributions. The methods have consistency guarantees and favorable sample complexity, with performance depending on latent-tree structure.

  • Contributions: Recursive grouping identifies sibling and parent-child relationships recursively, while CLGrouping first builds a Chow-Liu tree and then applies latent-tree subroutines locally.The methods operate on information distances between observed variables, which can be estimated from samples.
  • Theoretical guarantees: The algorithms are structurally consistent and risk consistent for Gaussian and discrete symmetric distributions, with sample complexity logarithmic in the number of observed variables.These guarantees concern the proposed latent-tree learning procedures.
  • Empirical conclusions: RG performs well with few hidden variables, whereas CLGrouping performs significantly better when the latent tree contains many hidden variables.Real-world comparisons also report superior accuracy and computational efficiency for the authors' algorithms.
  • Regularization: Regularized CLGrouping learns latent-tree approximations with a given number of hidden nodes.This extends the methods beyond exact latent-tree reconstruction.

A.1 Proof of Lemma 4: Sibling Grouping

Lemma 4 characterizes sibling relationships using information-distance differences. In particular, a specific equality across all other observed nodes identifies a leaf and its parent.

  • Sibling criterion: For a leaf i with parent j, information-distance additivity makes Φ_ijk equal d_ij for every k distinct from i and j.This equality supplies the sufficient direction of the sibling-grouping criterion.
  • Contradiction argument: If i and j are not adjacent, an intermediate node or an observed node in an away subtree yields a strict inequality contradicting the equality condition.The contradiction uses positive additive information distances along the path between i and j.
  • Contradiction argument: If i is not a leaf, choosing a neighboring node or an observed node in its away subtree produces another contradiction.Thus the equality condition cannot hold unless i is a leaf attached directly to j.

A.2 Proof of Theorem 5: Correctness and Computational Complexity of RG

The proof establishes that recursive grouping correctly recovers the latent-tree subforest at every iteration and bounds its computation by O(diam(Tp)m3).

  • Correctness: Recursive grouping identifies sibling groups correctly at every iteration, so each recovered partition yields a subforest of the original latent tree.New parent nodes corresponding to partitions without observed parents represent hidden nodes in the original tree.
  • Computational complexity: O(diam(Tp)m3) bounds recursive grouping’s computational complexity.The bound follows from at most O(m3) information-distance differences per iteration and at most diam(Tp) relevant subsets initially.

A.3 Proof of Lemma 8: Properties of the MST

Lemma 8 establishes structural properties of surrogate nodes and the Chow–Liu minimum spanning tree that support latent-tree preprocessing and analysis.

  • Surrogate separation: For an edge separating distinct surrogate groups, each group lies on its corresponding side of the edge.The unique path between nodes on opposite sides crosses the separating edge.
  • Surrogate separation: The distance between observed nodes on opposite sides is at least the information distance between their surrogate nodes.The inequality combines path additivity with the definition of surrogacy.
  • MST property: The Chow–Liu tree uses the surrogate-node edge as the shortest connection between the two corresponding observed-node sides.This follows from the minimum-spanning-tree property applied to the separated sets.
  • Surrogate paths: With consistent tie-breaking, every node on the path from a hidden node to its surrogate has that same surrogate.A different surrogate would contradict either the distance ordering or the tie-breaking rule.
  • Distance bounds: The maximum hidden-node distance from a surrogate is bounded using graph degree, effective depth, and information-distance bounds.The proof introduces the worst-case graph and information distances and bounds both through the effective-depth parameter.
  • Edge contractions: Edge contractions transform the latent tree into the observed-variable MST, with the blind transformation reversing this mapping.This structural relationship underlies the connection between the Chow–Liu tree and the original latent tree.

A.4 Proof of Theorem 9: Correctness and Computational Complexity of CLBlind

Theorem 9 proves CLBlind’s correctness by relating the observed-variable Chow–Liu tree to the latent tree through surrogate-based edge contractions.

  • Correctness: CLBlind contracts each edge joining a hidden variable to its surrogate observed child, transforming the latent tree into a tree over observed variables.The blind transformation on the MST reverses this contraction mapping.

A.5 Proof of Theorem 10: Correctness and Computational Complexity of CLRG

The proof establishes CLGrouping’s correctness by induction over visited internal nodes, showing each recursive-grouping step reverses corresponding edge contractions. It also derives computational, structural-consistency, risk-consistency, and sample-complexity guarantees from recursive grouping and Chow–Liu consistency.

  • Correctness: CLGrouping maintains T^r = EC(Tp, V^r) at every iteration, where unvisited surrogate nodes remain contracted with their inverse surrogate sets.The induction starts from the Chow–Liu tree and concludes with the original latent tree when no internal nodes remain unvisited.
  • Correctness: Each iteration replaces the relevant contracted star graph with RG(Ar, d), and recursive grouping reverses the edge contractions to recover the corresponding latent subtree.The proof first establishes that the reconstructed subtree is identifiable and minimal.
  • Computational complexity: The Chow–Liu preprocessing costs O(m^2 log m), while recursive grouping costs max_r |Ar|^3, with |Ar| bounded by the maximum degree of the Chow–Liu tree.Thus, CLGrouping’s recursive work depends on the largest local neighborhood supplied to recursive grouping.
  • Consistency: Structural consistency follows because estimated information distances converge in probability to their true values as the sample size increases.The argument applies the consistency of the information-distance estimates to the structural recovery result.
  • Consistency: For Gaussian and symmetric discrete models, structural consistency implies parameter and risk consistency, with KL-divergence tending to zero in probability as n tends to infinity.Information distances correspond one-to-one with correlations or crossover probabilities, enabling consistent parameter recovery after structure recovery.
  • Sample complexity: Under constant effective depth and uniformly bounded information distances, relaxed recursive grouping achieves logarithmic sample complexity through exponentially decaying distance-estimation errors.The bound uses a threshold τ, error events for triples, and a union bound; CLGrouping inherits O(log m) sample complexity from recursive grouping and Chow–Liu consistency.
Loading 1009.2722v1…