快速近似秩确定与分组检测选择-计算机科学-机器学习-秩确定-随机化算法.pdfVIP

快速近似秩确定与分组检测选择

AdieshaLiyanage∗BraedenSopp†BrendanMumey‡

摘要

假设可以使用分组测试操作来检查集合中的顺序关系，这能否加速诸如寻找最小/最大元素、秩判定

和选择等问题？我们考虑一种单边的分组测试，其中查询形式为或，当且仅当存在某

个使得或时，答案是“是”。我们将注意力限制在全序上，并专注于查询复杂性；对

于寻找最小值或最大值的问题，我们提供了一个预期查询次数为log的拉斯维加斯算法。我们也

本给出了用于秩判定和选择的随机近似算法；我们在估计秩或选定元素时允许相对误差为的。

译在这种情况下，我们给出一个具有预期查询复杂度log的蒙特卡罗算法来进行近似秩判定，

其中是算法成功的概率。我们还提供了一个用于近似选择的蒙特卡罗算法，其预期查询复杂度为

中

log；它以至少的概率输出一个元素，并且如果这样做了，具有期望的近似排名的概

1率为。

v

4

3关键词：选择，秩确定，群组测试，随机化算法，近似算法

6

2

1

.1介绍

7

0

5在这项工作中，我们考虑了分组检测如何加速求序问题，例如找到全序集中的最小/最大元素、

2

:确定一个元素的秩以及选择给定秩的元素。给定集合上的顺序关系，该集合大小为，我们假

v

i设存在一个可以回答形式为或的一对多查询的预言机，其中答案是肯定的当且仅

x

r当存在某个满足不等式。

a

可以设想一种情境，我们只能观察到特定参与者（比如）的比赛结果，即，是否最后一名，

还是他们至少能够击败其他竞争对手中的一个（比如）？这种概念由群组测试捕捉到，假

设意味着比快。同样，我们可以通过测试来检查是否是最快的竞争对手；如

果答案是否定的，我们知道是最快的。在这样的情况下，如果目标是找到某些元素（例如最小值

或最大值），自然会问群体检测策略能否有效应用。这个问题的一个具体实例出现在计算生物学中，

在那里人们试图识别所有简约解决方案中的恒定关系以从噪声数据中重建肿瘤细胞进化[8]。通过解

决一个定制的整数线性规划（ILP），可以验证细胞之间的成对关系，并且可以通过加入额外约束将

这种方法扩展到群体检测，而不显著增加实际求解时间。

∗GianforteSchoolofComputing,MontanaStateUniversity,Bozeman,MT59717,USA.Email:a.liyanaralalage@montana.edu

†GianforteSchoolofComputing,MontanaStateUniversity,Bozeman,MT59717,USA.Email:

braeden.sopp@student.montana.edu

‡GianforteSchoolofComputing,MontanaStateUniv