AI Seminar sponsored by Apple

Yichong Xu -- Interactive learning using Comparison Queries

Abstract: In supervised learning, we leverage a labeled dataset to design methods for function estimation. In many practical situations, we are able to obtain alternative feedback, possibly at a low cost. A broad goal is to understand the usefulness of, and to design algorithms to exploit, this alternative feedback. We consider a interactive learning setting where we obtain additional ordinal (or comparison) information for potentially unlabeled samples. In this talk we show the usefulness of such ordinal feedback for two tasks: Binary classification and nonparametric regression. For binary classification, we show that comparison queries can help in improving the label and total query complexity by reducing the learning problem to that of learning a threshold function. We present an algorithm that achieves near-optimal label and total query complexity. For nonparametric regression, we show that it is possible to accurately estimate an underlying function with a very small labeled set, effectively escaping the curse of dimensionality. We develop an algorithm called Ranking-Regression(R^2) and analyze its accuracy as a function of size of the labeled and unlabeled datasets and various noise parameters. We also derive lower bounds to show that R^2 is optimal in a variety of settings. Experiments show that our algorithms outperforms label-only algorithms when comparison information is available.

Based on joint works with Sivaraman Balakrishnan, Artur Dubrawski, Kyle Miller, Hariank Muthakana, Aarti Singh and Hongyang Zhang.