The Sample Complexity of Best-k Items Selection from Pairwise Comparisons
The Sample Complexity of Best-k Items Selection from Pairwise Comparisons
复制标题
DOI：
--
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Wenbo Ren;Jia Liu;N. Shroff
中科院分区：
文献类型：
--
作者：
Wenbo Ren;Jia Liu;N. Shroff
本文研究了两两比较中主动最佳k项选择的样本复杂度（即比较次数）界。从一组给定的项目中，学习器可以对每对项目进行成对比较，每次比较都会返回关于首选项目的独立噪声结果。在任何时候，学习器可以根据过去的观察自适应地选择一对项目进行比较（即，主动学习）。学习者的目标是找到（近似）最好的-$k$项目与给定的信心，同时尝试使用尽可能少的比较。本文研究了两个问题：（i）在强随机传递性和随机三角不等式下，寻找可能近似正确（PAC）的最佳k元项和（ii）寻找精确的最佳k元项.对于PAC的最佳-$k$项目选择，我们首先显示了一个下界，然后提出了一个算法，其样本复杂度上限匹配的下界到一个常数因子。对于确切的最佳$k$项目选择，我们首先证明了一个最坏的情况下界。然后，我们提出了两个算法的基础上，我们的PAC最佳项目选择算法：一个工程为$k=1$，是样本复杂性最佳的对数因子，和其他工程为所有值的$k$，是样本复杂性最佳的对数因子。
This paper studies the sample complexity (aka number of comparisons) bounds for the active best-$k$ items selection from pairwise comparisons. From a given set of items, the learner can make pairwise comparisons on every pair of items, and each comparison returns an independent noisy result about the preferred item. At any time, the learner can adaptively choose a pair of items to compare according to past observations (i.e., active learning). The learner's goal is to find the (approximately) best-$k$ items with a given confidence, while trying to use as few comparisons as possible. In this paper, we study two problems: (i) finding the probably approximately correct (PAC) best-$k$ items and (ii) finding the exact best-$k$ items, both under strong stochastic transitivity and stochastic triangle inequality. For PAC best-$k$ items selection, we first show a lower bound and then propose an algorithm whose sample complexity upper bound matches the lower bound up to a constant factor. For the exact best-$k$ items selection, we first prove a worst-instance lower bound. We then propose two algorithms based on our PAC best items selection algorithms: one works for $k=1$ and is sample complexity optimal up to a loglog factor, and the other works for all values of $k$ and is sample complexity optimal up to a log factor.