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 $\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 $\widetilde{O}(|\Sigma|^3 n\varepsilon^{-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\varepsilon^{-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; Y \mid Z)$ is $0$ or $\geq \varepsilon$ is possible with $\widetilde{O}(|\Sigma|^3/\varepsilon)$ samples. Finally, we show that for a specific tree $T$, with $\widetilde{O} (|\Sigma|^2n\varepsilon^{-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.

翻译：我们为古典Chow-Liu运算( IEEE Trans.~Inform.~Theory,1968) 提供有限的样本保证,用于学习树结构化的分布模型。对于以美元计的发行量P$和以美元节点计的树$T$,我们说$T$是用美元结构化的发行量P$P$;如果有美元结构化的发行量QQQ$,则美元(P\;@@@@@Q); Q) 最多为美元(d) 美元(varepsil) 而不是最好的树结构化的发行量美元。如果以美元结构化的本身是树结构化的,那么Chow-Liu算法的共享量为美元;如果以美元(crecial) 或以美元(美元) 以美元结构化的发行量(美元),那么以美元(cicilsion) 以美元(crecial-toal_Zeal) 根基的发行量數。