Selective Supervision: Guiding Supervised Learning with Decision-Theoretic Active Learning

1 Introduction

Increased sensing and decreased storage costs are leading to the growing availability of large data sets. However, data resources are often unavailable for machine learning and reasoning because of the high cost of labeling cases. As an example, we may have access to several thousand voice messages stored on a server and wish to build a classification system that could automatically classify voicemail messages into different categories. Unfortunately, performing supervised learning with the data set would require the manual effort of listening to voice messages and applying labels.

Unsupervised learning shows promise for reducing the effort required for tagging, such as its use in preparing data sets for supervised learning. However, pure unsupervised learning, based on notions of clusters and similarity, is often fraught with labeling errors.

We believe that there is a rich space of opportunities within the realm of complementary computing [Horvitz and Paek, 2007] for machine learning. We focus on the ideal coupling of human supervision with unsupervised methods and we discuss selective supervision, the use of value-of-information to triage human tagging efforts. The active-learning method considers both the cost required to tag data as well as the costs associated with the use of a classifier in a real-world setting. We show how we can minimize the total cost associated with the construction and use of classification systems, where costs are measured in currencies such as monetary quantities or other valuable resources.

Given the cost of labeling previously unlabeled cases and the cost of misclassification-which may be different for different classes-we seek to quantify the expected gain in expected value associated with seeking information on an unlabeled data point. This expected gain, which corresponds to the value of information provided by labeling, is the guiding principle for the active learning framework. We shall show how we can employ this value of information in learning within the Gaussian Process classification framework, and describe the applicability of the approach to both supervised and semi-supervised scenarios.

After a review of some key work in active learning, we describe the active learning framework that uses expected valueof-information (VOI) criterion to triage labeling. Then, we present concepts and computational issues with the use of Gaussian Process classification, and we show how the methods can be extended to handle semi-supervised learning. We highlight the effectiveness of the framework on the task of classifying voice messages and we conclude with experimental results and discussion.

2 Background

Interest has been growing in recent years in active learning. Numerous heuristics and schemes have been proposed for choosing unlabeled points for tagging. For example, Freund et al. 1997 propose disagreement among the committee of classifiers as a criterion for active learning. Tong and Koller, 2000 explore the selection of unlabeled cases to query based on minimizing the version space within the support vector machines (SVM) formulation. Within the Gaussian Process framework, the method of choice has been to look at the expected informativeness of an unlabeled data point [MacKay, 1992; Lawrence et al., 2002]. Specifically, the idea is to choose to query cases that are expected to maximally influence the posterior distribution over the set of possible classifiers. Additional studies have sought to combine active learning with semi-supervised learning [McCallum and Nigam, 1998; Muslea et al., 2002; Zhu et al., 2003].

All of these methods inherently focus on minimizing the misclassification rate. We focus on the value of moving to a decision-theoretic framework in active learning, where we consider the costs and risks in real-world currencies and employ computations of expected value of information to balance the cost of misdiagnosis with the costs of providing labels.

3 Decision-Theoretic Active Learning

A linear classifier parameterized by w classifies a test point x according to: sign(f(x)), where f(x) = wT x. Given a set of training data points XL = {x1, .., xn}, with class labels TL = {t1, .., tn}, where ti ∈ {1, -1}, the goal of a learning algorithm is to learn the parameters w. Most classification techniques focus on minimizing classification error. However, preferences about the relative numbers of false positives and negatives produced by a classification system can vary by person and task. These preferences can be expressed in terms of real-world measures of cost such as a monetary value and we can seek to minimize the expected cost for the use of a classifier over time. Additionally, we have the cost of tagging cases for training, which can vary for cases in different classes or with other problem-specific variables.

We aim to quantify the values of acquiring labels of different data points and to use computations of these values as a guiding principle in active learning. Intuitively, knowing the label of one or more currently unlabeled points may reduce the total risk in the classification task. On the other hand, labels are acquired at a price. The difference in the reduction in the total expected cost of the use of the classifier, which we shall refer to as the risk, and the cost of acquiring a new label is the expected value of information for learning that label. The real-world cost associated with the usage of a classifier is a function of the number of times that a classifier will be used in the real world, so a probability distribution over usage is considered in the computation of expected cost.

For simplicity, we shall focus in the discussion on twoclass discrimination problems. The methods discussed in the paper can be generalized in a straightforward manner to handle multiple classes. We note that the work presented here makes a myopic assumption, where we only seek to label one data point at a time. This can be generalized by applying lookahead procedures that consider the acquisition of labels for different sets of points.

Let us define the risk matrix R = [Rij] ∈ IR2×2 , where Rij denote the cost or risk associated with classifying a data point belonging to class i as j. We use the index 2 to denote the class -1. We assume that the diagonal elements of R are zero, specifying that correct classification incurs no cost. Thus, given the labeled set XL with labels TL we can train a classifier f(x) and compute the total risk on the labeled data points as:

Here, pi denotes the probability that the point xi is classified as class +1, i.e. pi = p(sign(f(xi)) = 1|xi). Further, L+ and L- are the indices of positively and negatively labeled points respectively. Note, that pi is the predictive distribution and depending upon the classification technique may or may not be available. Predictive distributions are available for Gaussian Process classification (Section 4) and other probabilistic classifiers, including probabilistic mappings of outputs of SVMs [Platt, 2000].

Beyond labeled cases, we also have a set of unlabeled data points XU = {xn+1, .., xn+m}, that we wish to classify. We seek to include the total risk associated with the unlabeled data points:

Here, p∗i = p(ti = 1|xi) is the true conditional density of the class label given the data point. As we do not have the true conditional, we cannot compute this expression exactly. However, we can approximate p∗i with pi; thus, we approximate the total risk on the unlabeled data points as:

Now, let Ci denote the cost of knowing the class label of xi. We assume that the costs Ci and the risks R12 and R21 are measured with the same currency. This assumption does not impose significant constraints as different currencies can be transformed into a single utility by using appropriate realworld conversions.

Given the risks (JL and JU ), we approximate 1 the expected misclassification cost per point as ¯ J = JL+JU n+m . Assuming a closed world, where the system only encounters the n +m points in XL ∪ XU, the expected cost is the sum of the total risk (Jall = (n +m) ¯ J) and the cost of obtaining the labels:

Upon querying the new point, we may see a reduction in the total risk. However, a cost is incurred when we query a label and computing the difference in these quantities triages the selection of cases to label. Formally, we define the VOI of an unlabeled point xj as the difference in the reduction in the total risk and the cost of obtaining the label:

Here, U j and J jall denote the total expected cost and the total misclassification risk respectively if we consider xj as labeled. The VOI quantifies the gain in utilities in terms of the real-world currency that can be obtained by querying a point; hence, our strategy would be to choose next for labeling the point that has the highest value of information. This results in minimization of the total cost U that consists of the total risk in misclassification as well as the labeling cost. We note that this approach differs from the earlier methods in active learning where the focus has been to minimize the classification error.

Now, let us consider xj for querying. Note that we need to compute the expression for VOI before we know the label for xj and the total risk J jall cannot be computed before we know the actual label tj. Similarly, Cj cannot be computed if the costs of labels are different for different classes. We approximate the terms J jall for the j th data point with an expectation of the empirical risk as: J jall ≈ pjJ j,+ + J j,-(1 -pj). Here J j,+ and J j,- denote the total risks when xj is labeled as class 1 and class -1 respectively. These risks can be written as sum of risks on labeled and unlabeled data as following:

1 This approximation can be used for any case, whether previously seen or unseen, provided the density p(x) does not change.

To calculate these risks we first compute pj,+, the resulting posterior probability upon adding xj as a positively labeled example in the active set. Now, using similar expressions to equations 1 and 3 we can compute J j,+ L and J j,+ U , the risks on the labeled and the unlabeled data points when xj is assumed to be positively labeled. The corresponding computations follow for J j,- L and J j,- U as well. Similarly, we can use expectation of Cj if costs of labeling vary by class.

Thus, our strategy is to select cases for labeling that have the highest VOI:

We note that whenever V OI (xjsel ) is less than zero, we have a condition where knowing a single label does not reduce the total cost; thus, this situation can be employed as a stopping criterion. Stopping criteria for open-world situations would include the computation of gains in accuracy of the classifier over multiple uses, based on a probability distribution over expected cases and the lifespan of the system. We note that a greedy policy might indicate stopping when there is still potential for further reduction of the overall cost via querying a set of points.

We now demonstrate the approach, starting with illustrations with a toy data set. We shall employ Gaussian Process classification (see section 4) within the active learning framework. Figure 1 shows the selection of unlabeled points to query based on the VOI criterion. The sample data consists of two half moons in a multidimensional space, where the top half belongs to class +1 and the bottom to the class -1. In the simulation, we start with a few cases that are already labeled and are represented as squares for class 1 and triangles for the class -1. The different graphs in the figure correspond to different settings of risks (R12 and R21) and labeling costs. We assume that C1 and C2 are the costs for querying points that belong to class +1 and -1 respectively. The unlabeled points are displayed as circles and the radii correspond to the VOI of labeling these cases. The next case selected to be queried is marked with a cross. Figure 1(a) shows the VOI for all the unlabeled data points and the case selected for the next query when the risks and the cost of labelings are equal for both classes. For this situation, cases that are nearest to the decision boundary are associated with the highest VOI. Choosing cases that minimize the objective for overall cost corresponds to the selection of queries that would minimize the classification error; hence, the points at the decision boundary are the ones that are the most informative. Figure 1(b) illustrates the situation where it is far more expensive to misclassify a point belonging to class -1. Due to this asymmetry in risks, the points that are likely to belong to class -1, but that also lay close to the decision boundary, have the highest VOI. Figure 1(c) depicts the situation where obtaining a label for a point in class -1 is 1.25 times as expensive to obtain the label for a point belonging to class 1. The VOI is highest for those points that are more likely to belong to class 1 and that are close to the decision boundary. The sample data set illustrates how VOI can be used effectively to guide tagging supervision such that it minimizes both the operational and training costs of a classifier.

We point out that we have assumed a closed system where both the set of the labeled and the unlabeled data are available beforehand. Prior work on active learning includes studies that assume an open system, where the data points arrive one at a time. The methods discussed in this paper can be extended to handle the open system case by using the average empirical risk ( JL n ) as a guiding principle as earlier used by Zhu et al., 2003. Note that this is not a transductive learning framework; the final classification boundary depends only on the labeled data. Both the labeled and the unlabeled data points are used only to determine which cases to query. Once trained, the classifier can be applied to novel test points, beyond the original set of labeled and the unlabeled points. We shall describe in Section 4.2 extensions to handle the transductive case by using a semi-supervised learning algorithm to train the classifier. Before that, we will pause to review Gaussian Process classification.

4 Gaussian Process Classification

In this work, we explore active learning with the use of Gaussian Process (GP) classifiers. One of the advantages of using GP classification is that we directly model the predictive conditional distribution p(t|x), consequently making it easy to compute the actual conditional probabilities without any calibrations or post-processing. GP methods provide a Bayesian interpretation of classification. With the approach, the goal is to infer the posterior distribution over the set of all possible classifiers given a training set:

Here, p(w) corresponds to the prior distribution over the classifiers and is selected typically so as to prefer parameters w that have a small norm. Specifically, we assume a spherical Gaussian prior on the weights: w ∼ N(0, I). The prior imposes a smoothness constraint and acts as a regularizer such that it gives higher probability to the labelings that respect the similarity between the data points. The likelihood terms p(ti|w, xi) incorporate the information from the labeled data and different forms of distributions can be selected. A popular choice is the probit likelihood: p(t|w, x) = Ψ(t · wT x). Here, Ψ(·) denotes the cumulative density function of the standard normal distribution. The posterior prefers those parameters that have small norm and that are consistent with the training data.

Computing the posterior, p(w|X, T ), is non-trivial and approximate inference techniques such as Assumed Density Filtering (ADF) or Expectation Propagation (EP) are typically required. The idea behind ADF is to approximate the posterior p(w|XL, TL) as a Gaussian distribution, i.e. p(w|XL, TL) ≈ N( ¯w, Σw). Similarly, EP is another approximate inference technique. EP is a generalization of ADF, where the approximation obtained from ADF is refined using an iterative message passing scheme. We refer readers to Minka, 2001 for the details.

Given the approximate posterior p(w|X, T ) ∼ N( ¯w,Σw), a frequent practice is to choose the mean ¯w of the distribution as the point classifier. The mean, which is also called the Bayes point, classifies a test point according to: sign( ¯wT x). It is relatively straightforward to generalize to the non-linear case by using the kernel trick, where the idea is to first project the data into a higher dimensional space to make it separable [Evgeniou et al., 2000].

One of the byproducts of using the GP classification framework is that we obtain a predictive distribution p(sign(f (x))|x):

Unlike other classifiers, the GP classification models the predictive conditional distribution p(t|x), making it easy to compute the actual conditional probabilities without any calibrations or post-processing. Probabilistic interpretations have been made of other kernel classifiers such as SVM [Sollich, 1999] and other attempts that map the output of the classifiers directly to the probability [Platt, 2000]. Our approach is to use this predictive distribution in the selective-supervision framework to compute expected risks and to quantify the value of information.

4.1 Computational Issues

As mentioned earlier, ADF or EP can be used for approximate inference in GP classification. However, the proposed scheme for selecting unlabeled points is computationally expensive. Note, that computational complexity for EP is O(n3 ), where n is the size of labeled training set. In the proposed method, we have to compute VOI for every unlabeled data point, requiring us to perform EP twice for every point under consideration.

A faster alternative is to use ADF for approximating the new posterior over the classifier rather than computing EP. Specifically, to compute the new posterior pj,+(w|XL∪j , {TL∪+1}) we can compute the Gaussian projection of the old posterior multiplied by the likelihood term for the j th data point. That is: pj,+(w|XL∪j, {TL ∪+1}) ≈ N ( ¯wj,+, Σj,+ w ), where ¯wj,+ and Σj,+ w are respectively the mean and the covariance of p(w|XL, TL) · Ψ(1 · wT xj). This is equivalent to performing ADF starting with the old posterior p(w|XL, TL) and incorporating the likelihood term Ψ(1 · wT xj) and does not require O(n3 ) operations to compute VOI for every unlabeled data point. We can use similar computations to approximate pj,-(w|XL∪j , {TL ∪ -1}).

4.2 From Supervised to Semi-Supervised Learning

The underlying classifier in the proposed framework is based on Gaussian Processes and it can be easily extended for the semi-supervised case [Kapoor, 2006; Sindhwani et al., 2005]. Specifically, at the core in the GP classification is the kernel matrix K, where entry Kij encodes the similarity between the ijth and the j th data points. Rather than using K as the similarity matrix for GP classification, we can use the inverse of the transformed Laplacian:

Here, D is the diagonal matrix where the diagonal elements are: Dii = ∑j Kij and σ > 0 is added to remove the zero eigenvalue from the spectrum of r(Δ). Intuitively, rather than computing similarity directly via the kernel Kij, the inverse of the transformed Laplacian computes the similarity over a manifold. Thus, the unlabeled data points help in classification by populating the manifold and using the similarity over the manifold to guide the decision boundary. The extension of GP classification to handle semisupervised learning has been recently studied [Kapoor, 2006; Sindhwani et al., 2005] and is related to the graph-based methods for semi-supervised learning. The rest of the active learning framework can be used as it is on top of this semisupervised GP classification framework.

5 Sample Challenge: Classifying Voicemail

We shall now move to a challenging classification task that highlights the value of employing the selective supervision methods. Specifically, our goal is to build a system that can classify voice messages in several ways, including whether the messages are urgent vs. non-urgent, the caller is personally close vs. not close to the person being called, and to detect if the caller is calling from a mobile phone. The classification task is related to prior work on the prioritization and routing of email messages with statistical classifiers [Horvitz et al., 1999].

Given a set of voice messages, we first extract features that promise to be of value in discriminating among the target classes. Specifically, we look at the prosody and metadata that accompanies the messages.

Prosodic features: We consider multiple prosodic features including syllable rate, pause structure, and pitch dynamics. We employ a pitch tracker and then extract the prosodic features summarized in table 1.

Message metadata: We also extract metadata from the voice messages. Specifically, we extract features that indicate the day and the time of the call. Additionally, we consider the size of the voicemail in bytes as well as the length of the message in seconds. We also extract features that indicate whether the caller is calling from outside the recipient's organization. Several metadata features are shown in table 1.

We now explore the selective supervision concepts applied to the voicemail classification challenge. The data set consists of 207 labeled voice messages received by a single user over a period of 8 months. We explore the use of the methods to guide the labeling efforts for supervised classification. Annotating a voicemail is tedious and shorter voicemails can be labeled more quickly than the longer ones. Thus, we use the asymmetric cost criterion where the cost of a label scales with the length of the voicemail. Specifically, we assume that the cost of labeling voicemail is 0.01 US dollars per second of message length. Further, for all of the experiments we assume that misclassification costs R12 = R21 = 10 US dollars. For Gaussian Process classification, the polynomial kernel of degree 2 is used.

We compare the selective-supervision strategy in supervised learning with three other schemes: 1) selecting points randomly, 2) choosing the point where the classification is most uncertain (i.e., jsel = argminj∈U |pj - 0.5|) and 3) choosing the point that is likely to change the posterior over w the most [MacKay, 1992; Lawrence et al., 2002], i.e., jsel = argmaxj∈U pjΔj,+ + (1 -pj)Δj,-. Here, Δj,+ and Δj,- are the differential entropy scores [Lawrence et al., 2002] when j th point is added as a positively and a negatively labeled point in the training set respectively. The term being maximized quantifies the expected change in the posterior over w when point xj is added to the training set.

Graphs (a) and (c) in Figure 2 compare the different active learning schemes on the task of detecting if the caller is personally close to the person being called. Similarly, graphs (b) and (d) in Figure 2 show the plots for the task of classifying whether the voice messages originated from a mobile phone. For the studies, results are averaged over 20 runs, where, for each run, we select one case per class as labeled and the rest of the points are selected according to the different active learning policies. Note, that, in the beginning, when there are a very few labeled data points, it is difficult to estimate the misclassification risk (RL + RU). However, with increasing numbers of labeled cases, the Gaussian Process classification will typically provide a better estimate of the posterior p(sign(f (x) = 1|w, x).

We found that the VOI policy results in significant gains over the other methods, both in terms of the accuracy as well as the cost. Table 2 shows the average classification accuracy and the standard error on the unlabeled data points together with the total cost (the sum of the misclassification and training costs) incurred after querying 20 points guided by the VOI criterion and random selection policy. As indicated by the results, the VOI criterion provides significant gains over random sampling in terms of cost and accuracy for classifying messages as personally close versus not close and mobile versus non-mobile. The VOI criterion for selective supervision provides valuable guidance on labeling efforts under budget constraints. We found that the gain with the use of VOI was not significant for detecting urgency. We hypothesize that this is due to the poor separability of the data.

6 Conclusion

We have investigated a decision-theoretic approach to classification, focusing on the use of value of information as the basis for guiding supervision. We showed how the risks of misclassification and cost of obtaining labels can be used to quantify the value of querying for labels of unknown cases. We applied and tested the ideas within the Gaussian Process classification framework. Finally, we reviewed results obtained from applying the methods to the task of building predictive models for classifying voice messages, where the cost of labeling a voicemail scales with the length of messages. We are continuing to explore challenges with the efficient computation of VOI and with studying the value of using the methods in triaging labeling effort in selective supervision.