Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu
Arnab Bhattacharyya, Sutanu Gayen, Eric Price, Vincent Y. F. Tan, N. V. Vinodchandran · SIAM Journal on Computing · 2023
Abstract. We provide finite sample guarantees for the classical Chow–Liu algorithm [Chow and Liu, IEEE Trans. Inform. Theory, 14 (1968), pp. 462–467] to learn a tree-structured graphical model of a distribution. For a distribution [Formula: see text] on [Formula: see text] and a tree [Formula: see text] on [Formula: see text] nodes, we say [Formula: see text] is an [Formula: see text]-approximate tree for [Formula: see text] if there is a [Formula: see text]-structured distribution [Formula: see text] such that [Formula: see text] is at most [Formula: see text] more than the best possible tree-structured distribution for [Formula: see text]. We show that if [Formula: see text] itself is tree-structured, then the Chow–Liu algorithm with the plug-in estimator for mutual information with [Formula: see text] independent and identically distributed samples outputs an [Formula: see text]-approximate tree for [Formula: see text] with constant probability. In contrast, for a general [Formula: see text] (which may not be tree-structured), [Formula: see text] samples are necessary to find an [Formula: see text]-approximate tree. Our upper bound is based on a new conditional independence tester that addresses an open problem posed by Canonne et al. [ Proceedings of the 50 th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2018, pp. 735–748]: we prove that for three random variables [Formula: see text] each over [Formula: see text], testing if [Formula: see text] is 0 or [Formula: see text] is possible with [Formula: see text] samples. Finally, we show that for a specific tree [Formula: see text], with [Formula: see text] samples from a distribution [Formula: see text] over [Formula: see text], one can efficiently learn the closest [Formula: see text]-structured distribution in KL divergence by applying the add-1 estimator at each node.