Simple method improves picking best items from noisy choices
A Simple and General Approach to top-$k$ Selection
Machine Learning
Summary
Sometimes you need to pick the best few items from a group when you can only check their quality a limited number of times, and each check has some noise or error. The authors introduce an easy-to-understand method that decides how to split these checks among items to find the top choices with fewer mistakes. Their method works for any number of selected items and different types of quality measurements. They also prove their method is close to the best possible and show through tests that it often does better than existing approaches.
What this means in practice
- •For product recommendation teams: Select the best k products from many options by efficiently allocating user feedback tests under noisy conditions.
- •For clinical trial designers: Plan patient testing to identify top k treatment candidates when results are variable and testing resources are limited.
Authors
Motti Goldberger, Nils Rudi
Abstract
This paper considers the Bayesian top-$k$ identification problem, wherein a decision maker is tasked with selecting $k$ items from a pool of items of unknown quality. To assess the items, the decision maker adaptively allocates a fixed sampling budget, where each sample of an item yields a noisy observation of its quality, with the objective of minimizing the expected opportunity cost of the selected set. We propose an approach that allocates each batch of samples by minimizing a surrogate objective derived from an upper bound on the expected opportunity cost. The approach is general: samples can be allocated in batches, the selection size $k$ is arbitrary, and it applies to many sampling distributions. It is also simple and intuitive. We prove that the method's posterior expected opportunity cost decays at an exponential rate of at least half the best rate achievable by any sampling rule. In simulations across a wide range of settings, the method is competitive with, and often improves upon, the best existing algorithm in each setting.