Nov, 2023

非同分布样本的测试

PDF
TL;DR在非独立同分布的样本情况下，研究子线性样本属性测试和估计在哪些情形适用；给定一组分布，考虑学习或测试平均分布的属性，在某些情况下需要 $\Theta (k/\varepsilon^2)$ 样本；对于均匀性或相似性的测试，给定 $c=1$ 个样本，需要线性数量级的 $k$ 样本；$c \geq 2$ 时，恢复了独立同分布的亚线性样本测试，需要 $O (\sqrt {k}/\varepsilon^2 + 1/\varepsilon^4)$ 样本，且在 $c=2$ 的情况下，即使是线性数量级的 $\rho k$ 样本，也不能进行均匀性测试。
sublinear-sample property testingdistributional property testingheterogeneous entitiessample complexityuniformity testing
发现论文，激发创造
  • 对离散分布属性进行测试的新方法

    研究了分布检测的样本测试的复杂度问题，提出了两种技术方法，一种是提供样本最优测试器，另一种是提供匹配样本下界。作者解决了大量重要的测试问题并证明了样本最优性，并且得到了第一个样本最优的对应测试器。

    Jan, 2016

  • 高概率离散分布的最佳测试

    研究总变差距离下的离散分布测试问题，提出可用于样本较高概率区域的属性测试的算法，包括相应参数的样本复杂度与正确性保障。

    Sep, 2020

  • 测试离散分布的条件独立性

    研究了离散分布的条件独立性检验问题，并给出了样本复杂度的上下界，提出了第一种具有次线性样本复杂度的条件独立性测试器，用于对分布属性进行测试。

    Nov, 2017

  • 高概率优化身份测试

    本研究主要研究了如何在高置信度条件下，通过有限样本同时检验分布 $q$ 和 $p$ 是否相同，其结果给出了最优样本复杂度并表明了经验分布在均匀性检测中的高效性。

    Aug, 2017

  • 分布属性的最佳测试

    研究如何通过样本来鉴别未知分布是否属于某个分布类，提出了一种可获得最优样本和计算效率的通用方法，并为分布的基本属性提供了测试方法。

    Jul, 2015

  • 离散分布身份和接近性的差分隐私测试

    该研究提供了关于差分隐私下 k 个元素分布的标识检测和接近度检验的上下界。他们提出了一般框架以建立隐私统计任务的样本复杂度的下界，同时通过构建精心选择的先验概率来证明隐私算法的下界。

    Jul, 2017

  • 使用不均等大小的样本进行接近度测试

    考虑从一个未知分布 $p$ 取 $m_1$ 个样本，从另一个未知分布 $q$ 取 $m_2$ 个样本的情形，介绍了一种测试是否有 $p=q$ 的快速算法，并分析了测试的样本复杂度，同时提出了估计马尔科夫链混合时间的算法及其初始样本个数的选择方法。测试算法主要依靠一种表现较为优异的统计量。

    Apr, 2015

  • 离散分布形状约束的检验

    本文主要研究了离散分布的结构性质（类），提出了一个通用的算法，可以测试各种形状约束的属性，包括单调、对数凹、t - 模态、分段多项式和泊松二项式分布。此外，对于所有考虑的情况，算法在领域大小方面具有近乎最优的样本复杂度，并且计算效率高。

    Jul, 2015

  • 离散分布相似度检测的最优算法

    本文研究了对于两个离散分布的近似度检测问题，给出了一些用于信息理论最优的简单测试方法，并且在 $n$ 和 $\eps$ 的依赖关系上都达到了常数因子。

    Aug, 2013

  • 作为双样本检验代理的分类准确性

    探究在高维情况下对分类器的精度验证，证明一种基于排列组合的测试方法具有连续性及德克斯特拉极限分布的高斯近似测试也具有连续性，并以高斯分布为例进一步研究了线性判别分析和 Hotelling's 测试等方法的功率。

    Feb, 2016