Near-optimal learning of tree-structured distributions by Chow-Liu
Near-optimal learning of tree-structured distributions by Chow-Liu
复制标题
Chow-Liu 的树结构分布的近乎最优学习
DOI：
10.1145/3406325.3451066
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Vinodchandran, N. V.
中科院分区：
文献类型：
--
作者：
Bhattacharyya, Arnab;Gayen, Sutanu;Price, Eric;Vinodchandran, N. V.
我们为经典 Chow-Liu 算法（IEEE Trans.Inform.Theory，1968）提供有限样本保证，以学习分布的树形结构图形模型。对于 Σn 上的分布和树 Tonn 节点，如果存在 T 结构分布 Q，使得 D(P||Q) 至多比 P 的最佳可能树结构分布多 ε，则称 T 是 P 的 ε 近似树。我们证明，如果 Pitself 是树形结构，则带有插件估计器的 Chow-Liu 算法用于互信息与 O(|Σ|3nε−1) i.i.d。 样本以恒定概率输出 P 的 ε 近似树。相反，对于一般 P（可能不是树结构），需要 Ω(n2ε−2) 个样本才能找到 ε 近似树。我们的上限基于一个新的条件独立性测试器，该测试器解决了 Canonne、Diakonikolas、Kane 和 Stewart 提出的开放问题（STOC，2018）：我们证明，对于 Σ 上的三个随机变量 X、Y、Zeach，可以使用 O(|Σ|3/ε) 个样本测试 I(X;Y∣Z) 是否为 0 或 ≥ ε。最后，我们表明，对于特定的树 T，通过来自分布 Pover Σn 的 O(|Σ|2nε−1) 个样本，可以通过在每个节点应用 add-1 估计器来有效地学习 KL 散度中最接近的 T 结构分布。
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 distributionPon Σnand a treeTonnnodes, we sayTis an ε-approximate tree forPif there is aT-structured distributionQsuch thatD(P||Q) is at most ε more than the best possible tree-structured distribution forP. We show that ifPitself is tree-structured, then the Chow-Liu algorithm with the plug-in estimator for mutual information withO(|Σ|3nε−1) i.i.d. samples outputs an ε-approximate tree forPwith constant probability. In contrast, for a generalP(which may not be tree-structured), Ω(n2ε−2) samples are necessary to find an ε-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 variablesX,Y,Zeach over Σ, testing ifI(X;Y∣Z) is 0 or ≥ ε is possible withO(|Σ|3/ε) samples. Finally, we show that for a specific treeT, withO(|Σ|2nε−1) samples from a distributionPover Σn, one can efficiently learn the closestT-structured distribution in KL divergence by applying the add-1 estimator at each node.
登录
查看更多内容
DOI：
--
发表时间：
2018
期刊：
and Automata
影响因子：
--
作者：
Diakonikolas, Ilias;Gouleakis, Themis;Peebles, John;Price, Eric
通讯作者：
Price, Eric
贝叶斯网络的 Square Hellinger 子可加性及其在身份测试中的应用
DOI：
--
发表时间：
2016
期刊：
Annual Conference Computational Learning Theory
影响因子：
--
作者：
C. Daskalakis;Qinxuan Pan
通讯作者：
Qinxuan Pan
没有项目独立性的多项目机制：通过鲁棒性实现可学习性
DOI：
10.1145/3391403.3399541
发表时间：
2020
期刊：
21st ACM Conference on Economics and Computation
影响因子：
--
作者：
Brustle, Johannes;Cai, Yang;Daskalakis, Constantinos
通讯作者：
Daskalakis, Constantinos
PAC学习有界树宽图形模型
DOI：
--
发表时间：
2004
期刊：
Conference on Uncertainty in Artificial Intelligence
影响因子：
--
作者：
Mukund Narasimhan;J. Bilmes
通讯作者：
J. Bilmes
测试贝叶斯网络
影响因子：
2.5
作者：
C. Canonne;Ilias Diakonikolas;D. Kane;Alistair Stewart
通讯作者：
Alistair Stewart