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

DOI10.1137/22M1489678MaRDI QIDQ6110527zbMATH OpenFDO

Authors Arnab Bhattacharyya, Sutanu Gayen, Eric Price, Vincent Y. F. Tan, N. V. Vinodchandran

Publication date 6 July 2023

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.04144

zbMATH Keywords

Chow-Liu treedistribution testinghigh-dimensional statisticslearning theory

Mathematics Subject Classification ID

Computational learning theory (68Q32) Randomized algorithms (68W20) Information theory (general) (94A15)

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 $Sigm{a}^n$ and a tree $T$ on $n$ nodes, we say $T$ is an $varepsilon$-approximate tree for $P$ if there is a $T$-structured distribution $Q$ such that $D(P;||;Q)$ is at most $varepsilon$ 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 $widetildeO(|Sigma{|}^{3}nvarepsilo{n}^{-1})$ i.i.d.~samples outputs an $varepsilon$-approximate tree for $P$ with constant probability. In contrast, for a general $P$ (which may not be tree-structured), $Omega(n^{2}varepsilo{n}^{-2})$ samples are necessary to find an $varepsilon$-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;YmidZ)$ is $0$ or $geqvarepsilon$ is possible with $widetildeO(|Sigma{|}^3/varepsilon)$ samples. Finally, we show that for a specific tree $T$, with $widetildeO(|Sigma{|}^{2}nvarepsilo{n}^{-1})$ samples from a distribution $P$ over $Sigm{a}^n$, one can efficiently learn the closest $T$-structured distribution in KL divergence by applying the add-1 estimator at each node.

Cites work

• A Large-Deviation Analysis of the Maximum-Likelihood Learning of Markov Tree Structures
• A theory of the learnable
• An optimal approximation algorithm for Bayesian inference
• Approximating discrete probability distributions with dependence trees
• Asymptotic Coupling and Its Applications in Information Theory
• Convergence properties of functional estimates for discrete distributions
• Efficient distribution-free learning of probabilistic concepts
• Efficiently learning Ising models on arbitrary graphs (extended abstract)
• Estimating the ``wrong graphical model: benefits in the computation-limited setting
• Estimation of Entropy and Mutual Information
• Factor graphs and the sum-product algorithm
• Forest density estimation
• Graphical models, exponential families, and variational inference
• scientific article; zbMATH DE number 715424 (Why is no real title available?)
• scientific article; zbMATH DE number 1134987 (Why is no real title available?)
• scientific article; zbMATH DE number 1158743 (Why is no real title available?)
• scientific article; zbMATH DE number 1753154 (Why is no real title available?)
• Introduction to Property Testing
• Learning a tree-structured Ising model in order to make predictions
• Learning factor graphs in polynomial time and sample complexity
• Learning loosely connected Markov random fields
• Learning Markov networks: Maximum bounded tree-width graphs
• Learning with mixtures of trees.
• Maximum likelihood bounded tree-width Markov networks
• Minimax optimal conditional independence testing
• Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu
• On testing expansion in bounded-degree graphs
• Probabilistic graphical models.
• Reconstruction of Markov random fields from samples: some observations and algorithms
• Sample-optimal identity testing with high probability
• Testing Bayesian Networks
• Testing conditional independence of discrete distributions
• Testing Ising Models
• The minimax learning rates of normal and Ising undirected graphical models
• The sample complexity of learning fixed-structure Bayesian networks
• Toward efficient agnostic learning

Cited in

(3)

• Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu
• Learning polynomial transformations via generalized tensor decompositions
• Learning bounded-degree polytrees with known skeleton

This page was built for publication: Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6110527)