## An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification

author: Gautam Dasarathy, Computer Science Department, Carnegie Mellon University
published: Aug. 20, 2015,   recorded: July 2015,   views: 35
Categories

# Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

# Description

This paper investigates the problem of active learning for binary label prediction on a graph. We introduce a simple and label-efficient algorithm called $S^2$ for this task. At each step, $S^2$ selects the vertex to be labeled based on the structure of the graph and all previously gathered labels. Specifically, $S^2$ queries for the label of the vertex that bisects the {\em shortest shortest} path between any pair of oppositely labeled vertices. We present a theoretical estimate of the number of queries $S^2$ needs in terms of a novel parametrization of the complexity of binary functions on graphs. We also present experimental results demonstrating the performance of $S^2$ on both real and synthetic data. While other graph-based active learning algorithms have shown promise in practice, our algorithm is the first with both good performance and theoretical guarantees. Finally, we demonstrate the implications of the $S^2$ algorithm to the theory of nonparametric active learning. In particular, we show that $S^2$ achieves near minimax optimal excess risk for an important class of nonparametric classification problems.