Noise-Tolerant Interactive Learning Using Pairwise Comparisons
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Noise-Tolerant Interactive Learning from Pairwise Comparisons
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 posit…
Robust Conditional GAN from Uncertainty-Aware Pairwise Comparisons
Conditional generative adversarial networks have shown exceptional generation performance over the past few years. However, they require large numbers of annotations. To address this problem, we propose a novel generativ…
AttributeGenerative Adversarial NetworkActive Ranking using Pairwise Comparisons
This paper examines the problem of ranking a collection of objects using pairwise comparisons (rankings of two objects). In general, the ranking of $n$ objects can be identified by standard sorting methods using $n log_2…
RoLNiP: Robust Learning Using Noisy Pairwise Comparisons
This paper presents a robust approach for learning from noisy pairwise comparisons. We propose sufficient conditions on the loss function under which the risk minimization framework becomes robust to noise in the pairwis…
Diameter-based Interactive Structure Discovery
We introduce interactive structure discovery, a generic framework that encompasses many interactive learning settings, including active learning, top-k item identification, interactive drug discovery, and others. We adap…
Active LearningDrug Discovery