Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons
This work addresses rank aggregation for applications like recommendation systems by improving efficiency in noisy, heterogeneous user data, though it is incremental as it builds on existing active sampling methods.
The paper tackles the problem of rank aggregation from noisy pairwise comparisons by proposing an elimination-based active sampling strategy that adaptively selects users to improve accuracy, proving it can return the true ranking with high probability and showing better sample complexity than non-active methods.
In heterogeneous rank aggregation problems, users often exhibit various accuracy levels when comparing pairs of items. Thus a uniform querying strategy over users may not be optimal. To address this issue, we propose an elimination-based active sampling strategy, which estimates the ranking of items via noisy pairwise comparisons from users and improves the users' average accuracy by maintaining an active set of users. We prove that our algorithm can return the true ranking of items with high probability. We also provide a sample complexity bound for the proposed algorithm which is better than that of non-active strategies in the literature. Experiments are provided to show the empirical advantage of the proposed methods over the state-of-the-art baselines.