Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu

Abstract

We provide finite sample guarantees for the classical Chow-Liu algorithm (IEEE Trans.~Inform.~Theory, 1968) to learn a tree-structured graphical model of a distribution. For a distribution $P$ on ${\Sigma }^n$ and a tree $T$ on $n$ nodes, we say $T$ is an $\epsilon$-approximate tree for $P$ if there is a $T$-structured distribution $Q$ such that $D(P||Q)$ is at most $\epsilon$ more than the best possible tree-structured distribution for $P$. We show that if $P$ itself is tree-structured, then the Chow-Liu algorithm with the plug-in estimator for mutual information with $\tilde{O}(|\Sigma {|}^{3}n{\epsilon }^{-1})$ i.i.d.~samples outputs an $\epsilon$-approximate tree for $P$ with constant probability. In contrast, for a general $P$ (which may not be tree-structured), $\Omega (n^2{\epsilon }^{-2})$ samples are necessary to find an $\epsilon$-approximate tree. Our upper bound is based on a new conditional independence tester that addresses an open problem posed by Canonne, Diakonikolas, Kane, and Stewart~(STOC, 2018): we prove that for three random variables $X,Y,Z$ each over $\Sigma$, testing if $I(X;Y\mid Z)$ is $0$ or $\ge \epsilon$ is possible with $\tilde{O}(|\Sigma {|}^3/\epsilon )$ samples. Finally, we show that for a specific tree $T$, with $\tilde{O}(|\Sigma {|}^{2}n{\epsilon }^{-1})$ samples from a distribution $P$ over ${\Sigma }^n$, one can efficiently learn the closest $T$-structured distribution in KL divergence by applying the add-1 estimator at each node.

arXiv comment33 pages, 3 figures

References in corpus (8)

• Optimal Testing for Properties of Distributions
• Forest Density Estimation
• A Large-Deviation Analysis of the Maximum-Likelihood Learning of Markov Tree Structures
• Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models
• Finding a Path is Harder than Finding a Tree
• Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing
• Learning Loosely Connected Markov Random Fields
• Exact Asymptotics for Learning Tree-Structured Graphical Models with Side Information: Noiseless and Noisy Samples

Cited by in corpus (4)

• Outlier-Robust Learning of Ising Models Under Dobrushin's Condition
• Sample-Optimal and Efficient Learning of Tree Ising models
• Optimal Rates for Learning Hidden Tree Structures
• Efficient inference of interventional distributions