Unfolding Latent Tree Structures using 4th Order Tensors
This addresses the challenge of latent structure discovery in fields like data analysis, offering a method that is agnostic to hidden state counts, though it appears incremental as it builds on quartet and tensor-based techniques.
The paper tackles the problem of discovering latent tree structures from observed variables without requiring the number of hidden states as input, by proposing a quartet-based approach with a nuclear norm test, resulting in a consistent algorithm with exponentially decaying error probability and favorable comparisons to alternatives.
Discovering the latent structure from many observed variables is an important yet challenging learning task. Existing approaches for discovering latent structures often require the unknown number of hidden states as an input. In this paper, we propose a quartet based approach which is \emph{agnostic} to this number. The key contribution is a novel rank characterization of the tensor associated with the marginal distribution of a quartet. This characterization allows us to design a \emph{nuclear norm} based test for resolving quartet relations. We then use the quartet test as a subroutine in a divide-and-conquer algorithm for recovering the latent tree structure. Under mild conditions, the algorithm is consistent and its error probability decays exponentially with increasing sample size. We demonstrate that the proposed approach compares favorably to alternatives. In a real world stock dataset, it also discovers meaningful groupings of variables, and produces a model that fits the data better.