本研究提出了一些信息理论上的可行性和对话界限,并为基于计算效率的变体提供了略微较弱的可行性界限,为噪声自适应设置提供了可能的最优算法,解决了组测试问题的有关缺陷项和噪声模型的问题。
Mar, 2018
该论文从信息论的角度总结了群检测问题的最新进展,包括有效的算法、实用的存储和计算需求,解码方法的可达界限以及算法独立的反向界限。作者评估了理论保证的因素,并确定了现有算法是最优或接近最优的区域,同时也确定了可以改进的区域。此外,作者概述了标准群检测问题的若干变体的结果,包括部分恢复标准、带有有限阶段的自适应算法、受限测试设计和次线性时间算法。
Feb, 2019
本论文提出了一种新的信息论视角用于组测问题的建模,并且基于随机编码和最大似然检测器分析导出了总测试次数的单字母特征公式,并使用 Bernoulli 噪声模型和混水效应考虑了多种情况并得到了对应的较为紧凑的渐进界,同时可以验证现有无噪声情况下的渐进界以及带有绑定扭曲的近似重构。
Jul, 2009
引入了一种变种的 Group Testing 问题,通过多种类型的物品组合才能得出阳性测试结果,提出了各种不同的算法以可靠地识别所有的半缺陷集合,并且在减少测试次数方面表现优秀,是目前基于解决更一般问题的基础结果的重要改进。
Sep, 2023
该研究提出了一个基于 “指纹” 方法的新的隐私保护选择问题下限界估算,并通过分析实际排除了一些标准假设。
Apr, 2017
本研究主要研究了如何在高置信度条件下,通过有限样本同时检验分布 $q$ 和 $p$ 是否相同,其结果给出了最优样本复杂度并表明了经验分布在均匀性检测中的高效性。
Aug, 2017
在有界度模型的性质测试框架中研究了识别图的集群结构问题,提出了一个亚线性算法,可识别由参数 k, phi, epsilon 制定的 (d) 有界度图,并且是渐近最优的,关键是集群内外的 conductance。
Apr, 2015
探究在高维情况下对分类器的精度验证,证明一种基于排列组合的测试方法具有连续性及德克斯特拉极限分布的高斯近似测试也具有连续性,并以高斯分布为例进一步研究了线性判别分析和 Hotelling's 测试等方法的功率。
Feb, 2016
该研究探讨了如何决定两个随机数据库之间是否存在统计依赖关系,并通过零假设和备择假设构建了一个假设检验问题,其中在零假设下,这两个数据库是统计独立的,而在备择假设下,存在一个未知的行排列使得两个数据库具有已知的联合分布但与零假设的边际分布相同。我们通过研究数据集生成分布的特征、$n$、$d$ 等因素,确定了信息理论上不可能和可能进行最优检验的阈值。此外,我们还分析了当 $d$ 固定时的情况,并推导出了强(错误几乎为零)和弱检测的下界和上界。
Nov, 2023
本文研究实验设计问题,应用 D-optimality criterion 估计误差,设计了两种逼近算法并提出改进方案。
Feb, 2018