检验两分布熵是否相等，效率远超传统近似测试。
Entropy Equivalence Testing
- 通过熵差判断分布是否相同，放宽了传统测试要求。
- 样本复杂度显著低于近似测试，实现高效检测。
- 适用于低阶贝叶斯网络的近似测试，提升效率。
我们提出了概率分布的熵等价性检验问题，这是经典近似测试问题的一种放松形式。给定两个未知分布 $p,q$ 的样本及参数 $\varepsilon \= (0,1/2]$，算法只需区分 $p=q$ 与 $|H(p)-H(q)| \geq \varepsilon$（其中 $H$ 表示香农熵）。我们设计了一种时间与样本均高效的算法，证明该任务的最优样本复杂度可远低于近似测试。作为应用，我们据此构建了首个非平凡的低阶贝叶斯网络近似测试算法，显著优于基于全量学习的基线方法在样本或时间复杂度上的表现。
原文摘要 · Abstract (English)
We introduce the problem of \emph{entropy equivalence testing} for probability distributions, a relaxation of the well-studied closeness testing problem, where the distribution testing algorithm is now only required to distinguish, given samples from two unknown distributions $p,q$ and a parameter $\varepsilon \in(0,1/2]$, between $p=q$ and $|H(p)-H(q)| \geq \varepsilon$ (where $H$ denotes the Shannon entropy). We provide a time- and sample-efficient algorithm for this task, showing that the optimal sample complexity for this task can be significantly lower than that of closeness testing. As an application, we leverage this result to provide the first non-trivial testing algorithm for (standard) closeness of low-degree \emph{Bayesian networks}, which significantly improves on either the sample or time complexity of a baseline based on full learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。