Noise-Tolerant Interactive Learning Using Pairwise Comparisons

December 2017

Noise-Tolerant Interactive Learning Using Pairwise Comparisons

Authors:

Yichong Xu, Hongyang Zhang, Kyle Miller, Aarti Singh, and Artur Dubrawski
Conference Paper
Proceedings of (NeurIPS) Neural Information Processing Systems

Abstract:

We study the problem of interactively learning a binary classifier using noisy labeling and pairwise comparison oracles, where the comparison oracle answers which one in the given two instances is more likely to be positive. Learning from such oracles has multiple applications where obtaining direct labels is harder but pairwise comparisons are easier, and the algorithm can leverage both types of oracles. In this paper, we attempt to characterize how the access to an easier comparison oracle helps in improving the label and total query complexity. We show that the comparison oracle reduces the learning problem to that of learning a threshold function. We then present an algorithm that interactively queries the label and comparison oracles and we characterize its query complexity under Tsybakov and adversarial noise conditions for the comparison and labeling oracles. Our lower bounds show that our label and total query complexity is almost optimal.
@conference{Xu-2017-121811,
author = {Yichong Xu And Hongyang Zhang And Kyle Miller And Aarti Singh And Artur Dubrawski},
title = {Noise-Tolerant Interactive Learning Using Pairwise Comparisons},
booktitle = {Proceedings of (NeurIPS) Neural Information Processing Systems},
year = {2017},
month = {December},
pages = {2428 - 2437},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.