论文标题
来自成对比较的最佳$ K $项目的样本复杂性
The Sample Complexity of Best-$k$ Items Selection from Pairwise Comparisons
论文作者
论文摘要
本文研究了来自成对比较的主动最佳$ K $项目选择的样本复杂性（又称比较数）。从给定的一组项目中，学习者可以对每对项目进行成对比较，每个比较都会返回有关首选项目的独立嘈杂结果。在任何时候，学习者都可以自适应地选择一对项目以根据过去的观察（即主动学习）进行比较。学习者的目标是以给定的信心找到（大约）最佳$ K $项目，同时尝试使用尽可能少的比较。在本文中，我们研究了两个问题：（i）在强大的随机传递性和随机三角形不平等的情况下，找到可能近似正确的（PAC）最佳$ K $项目，以及（ii）找到确切的最佳$ K $项目。对于PAC最佳$ K $项目的选择，我们首先显示一个下限，然后提出一种算法，其样品复杂性上限将下限匹配到一个恒定因子。对于确切的最佳$ K $项目选择，我们首先证明了最差的下限。然后，我们根据我们的PAC最佳项目选择算法提出了两种算法：一种适合$ k = 1 $的作品，并且是示例复杂性最佳的loglog因子，而其他所有值则适用于$ 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.
