提出高效算法，用最少样本学习高斯树模型结构。
Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information
- 设计基于线性回归的高斯条件互信息测试器，仅需O(ε⁻¹)样本。
- 实现n变量高斯树模型ε-近似学习，样本复杂度为Õ(nε⁻¹)。
- 理论与实验结合，适合关注连续分布结构学习的研究者。
高维分布学习是机器学习与统计学中的重要挑战。现有研究多聚焦离散分布的渐近分析，而本文针对高斯分布的树结构学习问题，提出高效算法并给出坚实的理论保证。核心是设计一个条件互信息测试器，用于判断两个高斯变量是否独立或其条件互信息至少为ε，仅需O(ε⁻¹)样本（近最优）。相比加法估计所需的Ω(ε⁻²)样本，效率显著提升。该方法利用对随机变量的适当前处理后进行线性回归。我们证明估计的条件互信息仍满足链式法则。作为应用，给出了n元高斯树模型的ε-近似结构学习算法，样本复杂度为Õ(nε⁻¹)，同样近最优。若未知模型为树形，则需Õ(n²ε⁻²)样本才能获得ε-近似结构。实验结果验证了理论收敛性。
原文摘要 · Abstract (English)
Learning high-dimensional distributions is a significant challenge in machine learning and statistics. Classical research has mostly concentrated on asymptotic analysis of such data under suitable assumptions. While existing works [Bhattacharyya et al.: SICOMP 2023, Daskalakis et al.: STOC 2021, Choo et al.: ALT 2024] focus on discrete distributions, the current work addresses the tree structure learning problem for Gaussian distributions, providing efficient algorithms with solid theoretical guarantees. This is crucial as real-world distributions are often continuous and differ from the discrete scenarios studied in prior works. In this work, we design a conditional mutual information tester for Gaussian random variables that can test whether two Gaussian random variables are independent, or their conditional mutual information is at least $\varepsilon$, for some parameter $\varepsilon \in (0,1)$ using $\mathcal{O}(\varepsilon^{-1})$ samples which we show to be near-optimal. In contrast, an additive estimation would require $Ω(\varepsilon^{-2})$ samples. Our upper bound technique uses linear regression on a pair of suitably transformed random variables. Importantly, we show that the chain rule of conditional mutual information continues to hold for the estimated (conditional) mutual information. As an application of such a mutual information tester, we give an efficient $\varepsilon$-approximate structure-learning algorithm for an $n$-variate Gaussian tree model that takes $\widetildeΘ(n\varepsilon^{-1})$ samples which we again show to be near-optimal. In contrast, when the underlying Gaussian model is not known to be tree-structured, we show that $\widetilde{Θ}(n^2\varepsilon^{-2})$ samples are necessary and sufficient to output an $\varepsilon$-approximate tree structure. We perform extensive experiments that corroborate our theoretical convergence bounds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。