Active Sampling for Class Probability Estimation and Ranking

Abstract. In many cost-sensitive environments class probabilityestimates are used by decision makers to evaluate the expected utilityfrom a set of alternatives. Supervised learning can be used to buildclass probability estimates; however, it often is very costly to obtaintraining data with class labels. Active learning acquires dataincrementally, at each phase identifying especially useful additionaldata for labeling, and can be used to economize on examples needed forlearning. We outline the critical features of an active learner andpresent a sampling-based active learning method for estimating classprobabilities and class-based rankings. BOOTSTRAP-LV identifiesparticularly informative new data for learning based on the variance inprobability estimates, and uses weighted sampling to account for apotential example’s informative value for the rest of the inputspace.We show empirically that the method reduces the number of dataitems that must be obtained and labeled, across a wide variety ofdomains.We investigate the contribution of the components of thealgorithm and showthat each provides valuable information to helpidentify informative examples.We also compare BOOTSTRAP-LV withUNCERTAINTY SAMPLING, an existing active learning method designed tomaximize classification accuracy. The results show that BOOTSTRAP-LVuses fewer examples to exhibit a certain estimation accuracy and provideinsights to the behavior of the algorithms. Finally, we experiment withanother new active sampling algorithm drawing from both UNCERTAINTYSAMPLING and BOOTSTRAP-LV and show that it is significantly morecompetitive with BOOTSTRAPLV compared to UNCERTAINTY SAMPLING. Theanalysis suggests more general implications for improving existingactive sampling algorithms for classification.