Source-linked AI summary
Spectral Methods for Learning Multivariate Latent Tree Structure
Animashree Anandkumar, Kamalika Chaudhuri, Daniel Hsu, Sham M. Kakade, Le Song, Tong Zhang
TL;DR
The paper asks how to recover multivariate latent-tree structure when only observed variables are sampled. It introduces Spectral Recursive Grouping, which combines spectral quartet tests with recursive grouping, and proves high-probability recovery with sample complexity independent of observed-variable dimensionality. The method applies under structural and correlation conditions, while degenerate completely correlated hidden nodes remain outside its identifiable scope.
Problem
Structure learning is difficult for graphical models with unobserved variables, motivating recovery of multivariate latent-tree structure from observed leaves.
Method
Spectral Recursive Grouping combines a multivariate spectral quartet test using canonical correlation analysis with bottom-up recursive grouping.
Results
The algorithm recovers the correct undirected latent-tree structure with high probability, with sample complexity depending on intrinsic spectral properties rather than observed-variable dimensions.
Takeaways & Limitations
The framework extends quartet-based structure learning to broad multivariate, continuous, discrete, and mixed latent-tree models, including high-dimensional observations.
Takeaways & Limitations
The test does not return a topology for deterministically identical hidden variables, a degenerate case where the non-redundancy condition fails.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses structure learning for multivariate latent tree models from samples of observed leaves. It extends quartet-based methods with spectral techniques and proposes an efficient, high-probability recovery procedure for broader high-dimensional settings.
- Motivation: Structure learning estimates the underlying graphical-model structure, but is generally NP-hard and more difficult when variables are unobserved.Existing approaches are mainly greedy, local-search, or convex-relaxation methods.
- Problem setting: The target models are directed trees with multivariate observed and hidden variables, learned using samples only from observed leaves.Applications include computer vision and phylogenetics.
- Scope: The work extends prior latent-tree studies from discrete or scalar Gaussian variables to multivariate random vectors and mixed distributions.The framework includes settings where different nodes may have discrete or continuous state spaces.
- Approach: Spectral Recursive Grouping combines a multivariate spectral quartet test based on canonical correlation analysis with recursive grouping for tree reconstruction.The quartet test extends classical scalar-variable tests to multivariate statistics.
- Results: The method recovers the correct latent tree structure with high probability in a provably efficient manner.Its analysis uses natural correlation conditions that generalize more restrictive effective-depth conditions.
2 Preliminaries
The paper models directed latent trees with multivariate random variables under linearity, rank, structural, and correlation assumptions. Its spectral quartet test uses empirical second-moment matrices to return a quartet pairing or abstain.
- 2.1 Latent variable tree models: A latent tree has observed leaves and hidden internal nodes, with every node having at most one parent.Nodes generally represent multivariate random vectors.
- 2.1 Latent variable tree models: The joint distribution obeys tree-structured conditional independence: separated variable sets are conditionally independent given the separating set.Observed variables lie in R^d and hidden variables in R^k.
- 2.2 Structural and distributional assumptions: Linear tree models impose matrix-linear conditional means for hidden and observed children of each hidden variable.These models include linear-Gaussian models, Kalman filters, discrete hidden Markov models, evolutionary trees, and Gaussian mixtures.
- 2.2 Structural and distributional assumptions: The rank condition requires full-rank hidden second moments and full-rank transition or observation matrices.These conditions support identifiability and exclude hard or non-identifiable instances.
- 2.2 Structural and distributional assumptions: Non-redundancy requires every hidden node to have at least three neighbors and prevents completely correlated hidden nodes from being merged.The condition is necessary for identifying the correct tree structure.
- 2.2 Structural and distributional assumptions: The correlation condition controls subtree separation through γmin and relates to effective depth, the distance from hidden variables to their closest observed variables.Effective depth can be logarithmic in tree size or constant in models such as hidden Markov models.
- Spectral quartet test: SpectralQuartetTest takes empirical pairwise second-moment matrices and confidence parameters, then returns a variable pairing or ⊥.Its output is used to identify one of the quartet topologies or abstain.
3 Spectral quartet tests
The spectral quartet test infers the topology induced by four observed variables from empirical second-moment matrices and either returns a pairing or abstains. Under stated structural conditions and valid confidence bounds, any returned pairing is correct with high probability.
- Test definition: The test examines four observed variables and returns either their induced subtree topology or ⊥ to indicate abstinence.There are four possible induced configurations; a non-null output is restricted to the valid pairings.
- Finite-sample test: The test uses empirical second-moment matrices and confidence bounds for each observed-variable pair, with thresholds depending on sample and distributional properties.A common threshold can be used in practice, and the analysis covers that case.
- Test definition: A pairing such as {{z1, z2}, {z3, z4}} identifies the corresponding quartet topology.
- Exact-moment guarantee: With exact second moments, the correct topology is identified by strict inequalities among products of the top k singular values under the model conditions.The perfect-quartet lemma establishes the equality pattern for the two incorrect pairings and the resulting strict comparison.
- Finite-sample guarantee: Valid confidence intervals make the test reliable: if it returns a pairing, that pairing is the correct topology with high probability.The test may abstain when sampling uncertainty prevents a reliable decision.
- Conditions: The non-redundancy quantity ρ controls the separation between the correct and incorrect pairing scores and therefore the required confidence accuracy.Smaller ρ yields a larger gap, while ρ = 1 corresponds to completely correlated hidden nodes that can be merged.
4 The Spectral Recursive Grouping algorithm
Spectral Recursive Grouping combines quartet-based tests with a bottom-up recursive grouping procedure to reconstruct multivariate latent trees from observed-leaf samples. Under Conditions 1–4 and suitable thresholds, it recovers the tree’s undirected graph with probability at least 1 −η, with no explicit dependence on observed-vector dimension.
- Algorithm overview: Spectral Recursive Grouping modifies recursive grouping to estimate a latent-tree structure from iid samples of observed leaf variables.It maintains roots of disjoint discovered subtrees and processes them bottom-up.
- Algorithm overview: At each iteration, the algorithm combines working-set variables as siblings or parent and child, updating the discovered subtrees until one tree remains.Sibling merges introduce a hidden parent; parent-child merges remove the child from the working set.
- Quartet-guided grouping: Relationship distinguishes siblings from parent-child neighbors by applying Mergeable tests to candidate roots and their children.The procedure checks whether one candidate is a sibling of each child of the other.
- Sample efficiency: The algorithm restricts candidate merges to highly correlated variables, using observed leaves in their subtrees as correlation proxies to avoid unreliable long-range estimates.
- Quartet-guided grouping: Mergeable returns false when a quartet test shows that two candidate subtrees should first join different variables, and true when no such evidence appears.
- Guarantee: With probability at least 1 −η, the algorithm returns a tree with the same undirected graph structure as the true tree under Conditions 1–4 and the theorem’s parameter choices.The guarantee assumes iid observed-variable samples and globally defined empirical second-moment estimates and thresholds.
- Guarantee: The sample complexity depends on intrinsic spectral properties and has no explicit dependence on observable-variable dimensions.This supports applicability to high-dimensional observed random vectors.
A Sample-based confidence intervals for singular values
The paper derives high-probability confidence intervals for empirical second-moment singular values, using exponential spectral-norm tail bounds for general and discrete random vectors. These intervals depend on sample size, confidence, and distributional properties, with practical plug-in or upper-bound choices.
- Confidence intervals: Confidence intervals place every singular value σs(Σi,j) within ∆i,j of σs(ˆΣi,j) simultaneously over all pairs and s ∈[k].The intervals are chosen as functions of N, δ, and distributional properties so the event holds with high probability.
- Tail inequalities: Exponential tail inequalities bound the spectral norm of empirical second-moment estimation errors for general and discrete random vectors.The general bound uses Bernstein-type conditions, while the discrete case has a tighter exponential inequality.
- Proof strategy: The analysis can use a matrix Bernstein inequality and derives the singular-value result by combining the concentration lemma with Weyl’s Theorem.The paper works with Lemma 5 for simplicity, while noting that alternative tail inequalities can be substituted.
- Confidence intervals: The interval widths ∆i,j depend on N, δ, and quantities such as Mi, Mj, and ¯di,j describing the random-vector distributions.These dependencies are unavoidable for additive confidence intervals; practical implementations may use plug-in estimates or loose upper bounds.
B Analysis of the spectral quartet test
The spectral quartet analysis establishes that the log det_k metric is additive along paths in the latent tree, including cases involving observed variables. This additivity supports quartet topology testing from second-order statistics.
- Proof mechanism: The proof derives additivity by factoring cross-moment matrices through an intermediate node and comparing their rank-k singular structures.The argument invokes Condition 2 to preserve rank k in the relevant normalized matrices.
- Metric additivity: The log det_k metric is additive whenever an intermediate node lies on the undirected path between two variables.Under Conditions 1 and 2, µ(u, v) = µ(u, w) + µ(w, v) for any such u, v, and w.
- Metric additivity: The same path-additivity relation extends to quartets containing one or both observed variables.The mixed hidden-observed case uses the corresponding cross-moment factorization and yields µ(u, v) = µ(u, w) + µ(w, v).
B.2 Proof of Lemma 1
The proof of Lemma 1 compares determinant expressions for alternative quartet pairings using metric additivity and bounds the middle-node contribution. Under an additional condition, the intended pairing is strictly separated.
- Determinant expansion: Alternative quartet determinant products can be rewritten as exponentials of sums of path metrics through the hidden nodes h and g.The displayed expressions expand pairwise determinant terms into combinations involving µ(z_i,h), µ(h,g), and µ(g,z_j).
- Determinant expansion: The cross-pairing expression contains the factor exp(2µ(h, g)), isolating the contribution of the internal hidden path.This follows from the path decomposition through h and g.
- Bounding the comparison: Cauchy–Schwarz bounds the normalized bilinear form involving h and g by the product of the vector norms.This bound controls the middle-node term used in comparing quartet pairings.
- Bounding the comparison: When Condition 3 also holds, Lemma 1 yields strict inequalities between the determinant products associated with the quartet pairings.The strict separation is the condition needed to distinguish the correct topology.
B.3 Proof of Lemma 2
Lemma 2 shows that if the spectral quartet test returns a pairing under the stated singular-value inequalities, that pairing must match the quartet’s true topology.
- Topology identification: If all empirical singular-value comparisons satisfy condition (2), any returned spectral quartet pairing must be the true pairing.The proof uses Lemma 1 to rule out the alternative configurations.
B.4 Proof of Lemma 4
Under the lemma’s assumptions, the relevant cross-covariance matrices inherit rank k, enabling the spectral quartet test to identify the correct pairing.
- The proof concludes the lemma by establishing this correct-pairing guarantee.
- The lemma’s assumptions imply that E[hg⊤] and the matrices Σi,j have rank k.
- The spectral quartet test therefore returns the pairing {{z1, z2}, {z3, z4}}.
B.5 Conditions for returning a correct pairing when rank(E[hg⊤]) < k
When E[hg⊤] has rank r < k, the spectral quartet test remains reliable under confidence bounds whose allowable widths increase as rank decreases.
- The spectral quartet test remains useful when E[hg⊤] has rank r < k.
- The lower-rank case permits wider confidence intervals than the rank-k case.The analysis depends on σmin and ρ1 rather than mini,j{σk(Σi,j)} and ρ.
- Under the lemma’s topology, model, rank, and confidence-bound assumptions, Algorithm 1 returns the correct pairing.
- The allowed confidence-bound width increases, up to a point, as rank r decreases.
- The proof again concludes that the spectral quartet test returns the correct pairing.
C.1 Overview
Theorem 1 is proved by conditioning on accurate empirical moments, characterizing merge decisions, and maintaining invariants until the entire tree is discovered.
- The proof first conditions on a 1−η event where empirical second-moment matrices are close to their population values in spectral norm.This permits deterministic reasoning about the algorithm’s behavior.
- It then characterizes which working-set pairs make Mergeable return true or false.
- The while-loop maintains invariants that ensure complete tree discovery when it terminates.
- Each iteration selects a Mergeable pair whose proper combination preserves the required invariants.
- Relationship determines whether the selected pair should be combined as siblings or as a parent and child.
C.2 Proof of Theorem 1
The proof establishes that empirical spectral tests support correct merge decisions throughout recursive grouping, so the algorithm reconstructs the latent tree’s undirected structure.
- Under the confidence event, empirical singular values and population singular values differ according to the bounds in Lemma 8.
- The algorithm’s subtree and super-tree definitions organize disjoint rooted subtrees whose leaf sets partition the observed variables.
- The spectral quartet test uses four observed variables, returns a correct topology when decisive, and may abstain with output ⊥.
- Mergeable pairs are supported when subtrees are sibling-like or neighboring leaf components, while un-mergeable pairs produce a separating quartet.
- For un-mergeable pairs satisfying the stated threshold and topology conditions, the quartet test returns {{x, x1}, {y, y1}} and Mergeable returns false.
- After n−1 iterations, the final subtree has one root and all observed leaves, giving the same undirected structure as T.