On-line learning for active pattern recognition

An adaptive on-line learning method is presented to facilitate pattern classification using active sampling to identify the optimal decision boundary for a stochastic oracle with a minimum number of training samples. The strategy of sampling at the current estimate of the decision boundary is shown to be optimal compared to random sampling in the sense that the probability of convergence toward the true decision boundary at each step is maximized, offering theoretical justification on the popular strategy of category boundary sampling used by many query learning algorithms.