Selective Sampling for Nearest Neighbor Classifiers

Abstract

. Most existing inductive learning algorithms assume the availability of a training set of labeled examples. In many domains, however, labeling the examples is a costly process that requires either intensive computation or manual labor. In such cases, it may be beneficial for the learner to be active by intelligent selection of examples for labeling with the goal of reducing the labeling cost. In this paper we propose a lookahead algorithm for selective sampling of examples for nearestneighbors classifiers. The algorithm attempts to find the example with the highest utility considering its effect on the resulting classifier. Computing the expected utility of an example requires estimating the probability of the possible labels. We propose to use the random field model for this estimation. The proposed selective sampling algorithm was evaluated empirically on real and artificial data sets. The experiments show that the proposed algorithm outperforms other methods. Keywords: active lear...