Active Learning with near Misses

Abstract

Assume that we are trying to build a visual recognizer for a particular class of objects—chairs, for example—using exist-ing induction methods. Assume the assistance of a human teacher who can label an image of an object as a positive or a negative example. As positive examples, we can obvi-ously use images of real chairs. It is not clear, however, what types of objects we should use as negative examples. This is an example of a common problem where the concept we are trying to learn represents a small fraction of a large uni-verse of instances. In this work we suggest learning with the help of near misses—negative examples that differ from the learned concept in only a small number of significant points, and we propose a framework for automatic generation of such examples. We show that generating near misses in the fea-ture space is problematic in some domains, and propose a methodology for generating examples directly in the instance space using modification operators—functions over the in-stance space that produce new instances by slightly modify-ing existing ones. The generated instances are evaluated by mapping them into the feature space and measuring their util-ity using known active learning techniques. We apply the proposed framework to the task of learning visual concepts from range images.