从多个算法中选出最可能表现最好的，且保证高置信度。
Near Optimal Inference for the Best-Performing Algorithm
- 基于多项分布的子集选择框架，识别最可能出现的最优算法。
- 在有限样本下仍能高效选出包含最优算法的最小候选集。
- 理论证明性能最优，适合需要可靠算法筛选的研究者。
面对一组竞争的机器学习算法，我们希望根据其在基准数据集上的表现，识别出在未来未见数据集上最可能排名第一的算法。直接选择基准上表现最佳的算法虽直观，但当性能差异微小、存在多个候选时，该方法可能失效。本文将此问题形式化为多项分布的子集选择问题：给定来自可数符号集的样本，目标是找到一个最小符号子集，以高置信度包含总体中最频繁的符号。本文提出一种新颖的子集选择框架，给出渐近与有限样本下的方案，显著优于现有方法，并提供匹配的下界，证明所提方法的优越性。
原文摘要 · Abstract (English)
Consider a collection of competing machine learning algorithms. Given their performance on a benchmark of datasets, we would like to identify the best performing algorithm. Specifically, which algorithm is most likely to rank highest on a future, unseen dataset. A natural approach is to select the algorithm that demonstrates the best performance on the benchmark. However, in many cases the performance differences are marginal and additional candidates may also be considered. This problem is formulated as subset selection for multinomial distributions. Formally, given a sample from a countable alphabet, our goal is to identify a minimal subset of symbols that includes the most frequent symbol in the population with high confidence. In this work, we introduce a novel framework for the subset selection problem. We provide both asymptotic and finite-sample schemes that significantly improve upon currently known methods. In addition, we provide matching lower bounds, demonstrating the favorable performance of our proposed schemes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。