Active Cost-Sensitive Learning

1 Introduction

A number of applications require learning algorithms that are capable (1) to learn from both labeled and unlabeled examples, (2) to minimize the cost non-uniform associated with the labeling efforts, and (3) to minimize the misclassification loss.

The active learning framework [Cohn et al., 1994] relies on algorithms that select unlabeled instances and provide them to the expert for labeling and learn a classifier based on the labeled data. In most of the cases the data is labeled incrementally and the classification model tries to minimize the misclassification error rate. To our knowledge, virtually all research efforts in active learning have assumed both a uniform loss function (for which the goal was to reduce the number of misclassifications) and a uniform labeling cost function (for which the goal was to reduce the number of instances that have to be labeled to achieve a certain accuracy).

Meanwhile, research in cost-sensitive learning [Elkan, 2001] has focused mostly on the problem of minimizing the expected loss of the learned models, and has assumed that all (training) instances and their labels were readily available prior to the training phase.

Our approach in addressing the active cost-sensitive learning problem is based on learning algorithms that construct models for conditional density (or class probability) estimation P (y|x), rather than class label predictors. The probability estimates provide an easy means for factoring in the misclassification losses in the classification decision making step. To address the labeling cost problem, we employ the same density estimation techniques over the available unlabeled data. The two methods are then combined into an algorithm that minimizes the combined cost.

Next section presents the general framework for our proposed techniques and discusses the challenges in implementing and applying these algorithms as well as some preliminary experimental results.

2 Active Learning for Minimizing the Combined Costs for Labeling and Decisions

Most learning algorithms can be transformed into class probability estimators that compute estimates P (y|x) for the probabilities that an instance x is in class y (y ∈ {1 . . .K}, where K is the number of classes). We employ these estimates in our algorithm both for minimizing the labeling costs and the misclassification decisions. We make the assumption that the loss function associated with the decisions is represented as a static K-by-K loss matrix L available at learning time. The contents of L(i, j) specify the cost incurred when an example is predicted to be in class i when in fact it belongs to class j.

The pseudo code for our approach, ACTIVE-CSL, is presented in Table 1.

The algorithm trains a base learner to compute the class probability estimates over the unlabeled data (line 2). Then, both the sampling step (line 3) and the decision making step (the hypothesis h) are based on those estimates. The unlabeled instance for which the next label is requested from the expert is selected in line 3. The selection rule chooses the instance that, if labeled provides the most expected gain in terms of the total cost (labeling + decision loss) on the labeled instances (or on a hold-out labeled validation set). It is important to note that iff C and L functions have a shape such that instances that are more expensive to label reduce the Input: a set Sl, of m labeled examples: Sl =< (xi, yi), i = 1, 2, . . . , m >, a set Su of v unlabeled examples: Su =< (ξi), i = 1, 2, . . . , v >, L (a loss matrix), C (a labeling cost function) a stopping criterion

Table 1: Pseudo code for the ACTIVE-CSL active costsensitive learning algorithm.

[1] repeat

1. for each j learn P (y|ξj) using Sl as training data; [3] l = argmin ξ∈Su (C(ξ)+

1. ψl = requested label for ξl;
2. remove ξl fromSu, add (ξl, ψl) to Sl;
3. while stopping criterion not met

// the optimal classification with respect to L and P

misclassification cost more than instances that are less expensive to label - the selection rule will trade the loss associated with misclassifications against examples to be labeled. The procedure selecting for the next instance to be labeled, as employed by ACTIVE-CSL, and based on computing the maximum expected gain upon labeling (the second sum in line 3), is somewhat similar in nature to the querying rule of uncertainty sampling [Lewis and Catlett, 1994].

One important detail that needs to be addressed when applying this algorithm in practice is the choice for the algorithm used for estimating the probabilities (line 3 in Table 1), given that ACTIVE-CSL and its predictions rely on these estimates. In general, the quality of learned density estimates is dependent on the amount and the distribution of the labeled data that is available and on the hypothesis constructed by the base learning algorithm. Several research studies have addressed the problem of learning good probability estimates and calibrating classification scores and ranks into accurate probabilities [Zadrozny and Elkan, 2001].

We have implemented and tested ACTIVE-CSL by using bagged probability estimation trees [Provost and Domingos, 2003] as class probability estimators (in line 2 of the code). We have compared two procedures for computing probability estimates out of the bagged trees: (a) by averaging the probabilities computed by the individual trees and (b) by estimating the confidence for the individual probabilities based on the distribution of the estimates of the individual trees (as suggested by [Margineantu, 2002]). For assessing the quality of the misclassification decisions we have employed active learning curves (showing the gain in terms of cost compared to a random selection of instances for labeling) and BDELTACOST [Margineantu and Dietterich, 2000] - a paired test for cost-sensitive classification decisions. The loss matrices for our experiments were generated based on some generic loss models, and the labeling cost function mapped instances that were closer to the decision boundary to higher labeling costs (the actual function we employed was a bell-shaped function with a maximum on the decision boundary).

We tested the two implementations of ACTIVE-CSL on five data sets from the UC Irvine Repository [Blake and Merz, 1998] (Breast cancer Wisconsin, Horse colic, King-rook vs. king-pawn, Liver disease, and Sonar) and on the binary version of the KDD Cup 1998 donations data.

The preliminary results show a minor advantage of the implementation employing confidence-based estimates over the implementation using averaged probability estimates. We have also run tests by employing random forests with logm attributes tested in a node [Breiman, 2001] as the class probability estimator and the results show no significant difference between the classification decisions based on random forests and the decisions based on bagged probability estimation trees.