Active Learning Using Uncertainty Information
Yazhou Yang Marco Loog
















































Active Learning Using Uncertainty Information
    Yazhou Yang1 2,
Marco Loog1 3
1Pattern Recognition Laboratory, Delft University of Technology, Delft, The Netherlands
2College of Information System and Management, National University of Defense Technology, Changsha, China
3The Image Section, University of Copenhagen, Copenhagen, Denmark
Email: {y.yang-4, m.loog}@tudelft.nl
    December 30, 2023
==========================================================================================================================================================================================================================================================================================================================================






Many active learning methods belong to the retraining-based approaches, which select one unlabeled instance, add it to the training set with its possible labels, retrain the classification model, and evaluate the criteria that we base our selection on. However, since the true label of the selected instance is unknown, these methods resort to calculating the average-case or worse-case performance with respect to the unknown label. In this paper, we propose a different method to solve this problem. In particular, our method aims to make use of the uncertainty information to enhance the performance of retraining-based models. We apply our method to two state-of-the-art algorithms and carry out extensive experiments on a wide variety of real-world datasets. The results clearly demonstrate the effectiveness of the proposed method and indicate it can reduce human labeling efforts in many real-life applications.





















§ INTRODUCTION

Over the past decade, a primary foundation of much progress in machine learning is the rapid growth of the number and size of data sets available, such as ImageNet <cit.> containing over 14 million labeled images for object recognition. In a practical scenario, we frequently encounter the situation where few labeled instances along with abundant unlabeled samples are available. Labeling a large amount of data is, however, very difficult due to the huge amount of time required or expensive because of the need of human experts <cit.>. Thus, it is very attractive to propose a proper labeling scheme to reduce the number of labels required in order to train a classifier.

Active learning has been put forward to overcome the above labeling problem. The main assumption behind active learning is that if an active learner can freely select any samples it wants, it can outperform random sampling with less labeling  <cit.>. Thus, the main task of active learning is querying as little data as possible to minimize the annotation cost while maximizing the learning performance. Active learning tries to achieve this by selecting the most valuable samples. However, it is difficult to define or measure the value of one instance to the learning problem. We can view it as the amount of information carried which potentially promotes the  learning performance, once its true label is known <cit.>. As a result of the fact that we do not have an exact measure of the value, there are a great number of selection criteria proposed from different perspectives on how to estimate the usefulness of each sample.  

Most commonly used criteria in active learning include query-by-committee <cit.>, uncertainty sampling  <cit.>, expected error reduction <cit.>, expected model change <cit.>, variance reduction <cit.> and “Min-max” view active learning <cit.>. Query-by-committee put forward multiple models as the committees and selected the samples which receive highest level of disagreement from the committees   <cit.>. Uncertainty sampling approach preferred the instances with maximum uncertainty. Based on the measurement of uncertainty, uncertainty sampling can be roughly divided two categories: maximum entropy of the estimated label  <cit.> and minimum distance from the decision boundary <cit.>. For example, Tong and Koller <cit.> proposed to query the instance which is closed to the current learning boundary using the classifier of support vector machines. Campbell et al.  <cit.> shared the same idea with Tong and Koller <cit.>.  

Roy and McCallum <cit.> proposed the expected error reduction (EER), which is a popular active learning method. EER aimed to reduce the  generalization error when labeling a new instance. Since we do not have access to the test data, Roy and McCallum suggested to  compute the “future error” on the unlabeled pool  under the assumption that the unlabeled data set is representative of the test distribution. In other words, the unlabeled pool can be viewed as a validation set. Also, we  have no knowledge about the true labels of unlabeled samples. EER estimated the average-case criterion of potential loss instead. Expected model change followed the idea of EER, but turned to select the instance which leads to maximum change of the current model. The variance reduction methods tried to minimize the output variances <cit.>. Schein and Ungar <cit.> extended this approach to expected variance reduction method on logistic regression by following the idea of EER. “Min-max” view active learning was originally proposed by Hoi et al. <cit.>, where “Min-max” indicates the worst-case criterion is adopted. The key idea behind is to select the sample which minimizes the gain of objective function no matter what its assigned label is.  Huang et al. <cit.> extended this framework by taking into account all the unlabeled data when calculating the objective function.

Current active learning methods can be split in two classes: retraining-based and retraining-free active learning. Retraining-based active learning represents methods which measure the information of unlabeled sample by labeling it (any possible label) and adding it to the training set to retrain the classification model. Then, some appropriate criteria can be evaluated and used for the sample selection. The second class, retraining-free active learning, contains the remaining methods which not need repeatedly train the model for each unlabeled instance during one single selection. For example, uncertainty sampling and query-by-committee belong to this category. 

However, since the true label of the selected unlabeled instance is unknown, these methods resort to calculating the average-case or worse-case criteria with respect to the unknown label. In this paper, we propose a different criterion for retraining-based methods. We incorporate the uncertainty information (measured by the posterior probabilities within the min-max framework) for the selection. The proposed criterion can be seen as a trade-off of the exploration and the exploitation. The uncertainty information plays the role of the exploitation while the retraining-based models act as the exploration part. We concentrate on the pool-based active learning setting which assumes a large pool of unlabeled data along with a small set of labeled data already available <cit.>. We consider the myopic active learning which sequentially and iteratively selects unlabeled instance. 



 §.§ Outline

The rest of this paper is organized as follows.  Section <ref> firstly reviews the framework of retraining-based active learning. Then two state-of-the-art methods under the retraining framework are briefly described. Section <ref> demonstrates the primary motivation of the proposed method and derives a general algorithm for retraining-based active learning in detail. It also illustrate how to extend the proposed criterion to current methods. Experimental design and results are reported in <ref> ; Section <ref> concludes this work followed by some future issues.


§ RETRAINING-BASED ACTIVE LEARNING


In this section, we summarize a general framework of retraining-based active learning. Then we demonstrate two examples under this framework: Expected error reduction and Minimum Loss Increase.


 §.§ Retraining-based Active Learning 



Firstly, let us introduce some preliminaries and notation. Let ℒ ={ (x_i,y_i) }_i=1^m represent the training data set that consists of m labeled instances and 𝒰 be the pool of unlabeled instances { x_i } _ i=m+1^ n . Each x_i ∈ℝ^d is a d dimensional feature vector, and y_i ∈ C ={ +1,-1 } is the class label of x_i. In this paper, let us focus on binary classification problem firstly, and it is easy to extend this work to multi-class problem by extending C to multi-labels set. We denote P_ℒ (y|x) be the conditional probability of y given x according to a classifier trained on ℒ.



For the retraining-based active learning, its framework can be summarized in Algorithm <ref>,  where V(x_i,y_i) represents any selection criterion associated with (x_i,y_i). The main procedure contains the loops which checks all the points in unlabeled pool 𝒰  over all the possible labels. For example, we firstly select one instance from the unlabeled pool and assign it any possible label. Then we update the labeled set (since we acquire a new labeled sample) and retrain the classifier we use. Based on the new trained classifier, we can measure some kind of selection criteria (e.g., generalization error in EER <cit.>). However, since the true label information of last selected sample is unknown, we need calculate some kind of performance, e.g., the average-case in <cit.>, worst-case in <cit.>, or even the best-case criteria in <cit.>. Finally, we will query the instance which leads to maximum or minimum value in terms of the criterion we are interested in.

EER is one example of retraining-based active learning, which uses the generalization error as V(x_i,y_i). We get expected model change <cit.> by adopting model change as the criterion. By adopting variance and logistic regression as the classifier, we get expected variance reduction <cit.>. Similarly, if we want to minimize the value of objective function after labeling a new instance and use the worst-case performance (corresponding to min-max framework), then we can get  <cit.>. Clearly, the retraining-based approaches may suffer from high computational cost due to the fact that they need go over all the unlabeled data and all the possible labels. 



 §.§ Expected Error Reduction 


Expected error reduction has demonstrated its effectiveness on text classification domain <cit.>. There are also some follow-up work of EER contributed by other researchers <cit.> <cit.> <cit.>. EER aims to select the sample which will reduce the future generalization error.  Since we can not see the test data, the unlabeled pool can be used as the validation set to predict the future test error. We encounter a new problem since we do not know the true labels of the pool. Roy and McCallum <cit.> suggested, in practice,  we can approximately estimate the error using the expected log-loss or 0/1 loss over the pool. For example, if we adopt the log loss, EER can be written as follows:

	
    min_x ∈𝒰∑_y ∈ C P_ℒ(y|x) ( -∑_x_i ∈𝒰∑_y_i ∈ CP_ℒ^+(y_i|x_i) log P_ℒ^+(y_i|x_i)  )


where ℒ^+ = ℒ∪(x,y) means that the selected instance x is labeled y and added to ℒ. Note that the first term P_ℒ(y|x) contains the pre-trained label information. The second term is the sum of potential entropy over the unlabeled data set 𝒰. 




 §.§ Minimum Loss Increase


We can find that EER attempts to reduce the future generalization error, however, it is not easy due to the missing of test data and true label information of unlabeled data. There are some researchers which try to solve this problem from a different perspective. Hoi et at. <cit.> presented a so called “min-max” view active learning. It prefers the instance which results in a small value of an objective function in spite of its assigned label. This is because the smaller the value of an objective function, the better the learning model, at least in high probability. Assume G_ℒ is the value of an objective function on current labeled data  ℒ. When we label a new instance and update the training data ℒ^+=ℒ∪{x_i, y_i}, we get a new value of objective function G_ℒ^+. What we want is the minimum increase of objective function, i.e., G_ℒ^+- G_ℒ,  when adding one more labeled sample. However, because the second term G_ℒ is independent of the next queried instance, so we can ignore it and focus on minimizing G_ℒ^+. Since we expect a minimum value of G_ℒ^+ regardless of the assigned label of x_i, we adopt the worst-case performance as follows, instead of the average-case version.


    min_x_i ∈𝒰max_y_i∈ C G_ℒ^+


Note that we can view G_ℒ^+ as one choice of V(x_i,y_i) mentioned in Algorithm <ref>. 

Let us consider an unconstrained optimization problem using L_2-loss regularized classifier with arbitrary loss l(w;x_i,y_i):
g(w)= 1/2λ || w ||^2 + ∑_x_i ∈ℒ l(w;x_i,y_i), where w is the parameter of learning classifier. If we adopt the Hinge loss l(w;x_i,y_i)=max(0,1-y_iw^Tx_i), we can derive the same model with “min-max” view active learning described in <cit.>, but without extend it to batch model setting. If we use square loss l(w;x_i,y_i)=(y_i-w^Tx_i)^2, we can get the same model with <cit.>. Note that, as is stated in <cit.>, though <cit.> includes all the unlabeled data when calculating the objective function, the unlabeled examples play no role since <cit.> relaxes the constraint of the labels of unlabeled pool in the end. This operation can guarantee zero contribution of unlabeled data to the objection function. Thus, <cit.> is also one special case using the square loss. Moreover, we can conclude that the main idea of min-max view active learning is to minimize the increase of the value of an objective function. 

In our paper, we consider the logistic loss l(w;x_i,y_i)=log(1+exp^-y_iw^Tx_i), which results in:
 
	
    min_x ∈𝒰max_y ∈ C1/2λ || ŵ ||^2 + ∑_x_i ∈ℒ^+  -log P_ℒ^+(y_i|x_i)


where ŵ is estimated parameter of L_2-regularized logistic regression model. Logistic regression is chosen as the base classifier since it is generally widely used in many fields and can output the conditional probability straightly, which can be used in active learning <cit.>. We call this method Minimum Loss Increase (MLI) in this paper.  EER tries to minimize the error on unlabeled data while MLI aims to minimize the loss on data already labeled. 



§ A NEW RETRAINING-BASED ACTIVE LEARNER



In this section, we motivate our proposed
method and, subsequently, describe a general adaptation for retaining-based active learning models.



 §.§ Motivation


Obviously, not knowing the true labels of the unlabeled data complicates calculating the final score of each instance in step 10 in Algorithm <ref>. 
One simple possibility is computing the average-case <cit.> or worst-case performance <cit.>, or even the best-case criterion <cit.>. These choices, however, may fail to take into account some potentially valuable information: Firstly, although the average-case criterion makes use of the label distribution information P_ℒ (y_i|x_i) already known, the expectation calculation can hide or underestimate some outstanding samples due to the re-weighting by P_ℒ (y_i|x_i). For example, the true label of instance x_i is +1 but the estimated P_ℒ (+1 |x_i) = 0.1, and the V(x_i,+1) has a maximum value compared with other instances. Then the average-case criterion of x_i, namely ∑_y_i P_ℒ (y_i|x_i)V(x_i,y_i), is highly likely to be surpassed by other instances. Secondly, as to the worst-case criterion, it suffers from not taking advantage of label distribution information at all. Worst-case analysis is a safe analysis since it is never underestimated. However, making no use of the available label information P_ℒ (y_i|x_i) can lose sight of some valuable information. 

Thus, to overcome the shortcomings mentioned, a new criterion for retraining-based active learning is proposed. The main motivation is that we want to incorporate the uncertainty information (e.g., known label distribution information) within min-max framework for retraining-based models. The proposed criterion is therefore as follows:

    min_x_i ∈𝒰max_y_i ∈ C P_ℒ(y_i|x_i) V(x_i,y_i)

where P_ℒ(y_i|x_i) contains the pre-trained label information and V(x_i,y_i) represents any criteria we are interested. Note that for some classifiers like logistic regression, we can use the estimated posterior probability as  P_ℒ(y_i|x_i). For classifiers which do not produce a probabilistic output, e.g., SVMs, we can transform their output to some probability using Platt's <cit.> or Duin & Tax's method <cit.>. And for V(x_i,y_i), various choices are possible, such as the test error on the unlabeled pool in EER, the output variance as in <cit.>, or the value of an objective function <cit.>.



The proposed method can be interpreted as follows: it utilizes the pre-trained label information, although this kind of information might be inaccurate due to limited labeled data we have, it still shows some underlying or potential useful clues which may promote active learning. Firstly, it improves upon the average-case criterion since it does not compute the expected value. The calculation of expectation tends to ruin the discriminative information contained in the data due to its averaging manner.  Secondly, it outperforms the worst-case criterion because it takes advantage of the knowledge of the potential label distribution while worst-case analysis does not use this at all. Thus, it avoids the disadvantages of average-case and worst-case criteria. It can be seen as a trade-off between the average-case and the worst-case criteria. Lastly, it can be considered as incorporating uncertainty sampling (encoded by the posterior probabilities) for retraining-based model. If all V(x_i,y_i)  become one constant term like 1 or P_ℒ(y_i|x_i) itself, then the proposed method will turn into exactly the uncertainty sampling. More specifically,  min_x_i ∈𝒰max_y_i ∈ C P_ℒ(y_i|x_i) or min_x_i ∈𝒰max_y_i ∈ C [P_ℒ(y_i|x_i)]^2 will act as totally same as uncertainty sampling since they will select the instance whose posterior probability comes closest to 0.5 on the binary problem. This shows that our proposed method actually fuses uncertainty sampling with retraining-based models. 


 §.§ Two Examples of the Proposed Method



















To provide valuable insights on the underlying characteristic of the proposed method, we apply it to two state-of-the-art retraining-based models EER and MLI. We also demonstrate its advantage on a synthetic data set in Figure <ref>.

Since our method tries to make use of the uncertainty information, the following adapted methods are termed uncertainty retraining-based active learners. It is easy to extend EER to uncertainty-based error reduction by adopting our method in Equation <ref> as follows:

	
    min_x ∈𝒰max_y ∈ C P_ℒ(y|x) ( -∑_x_i ∈𝒰∑_y_i ∈ CP_ℒ^+(y_i|x_i) log P_ℒ^+(y_i|x_i)  )


This method is called UEER for short. We can also apply our proposed criterion on MLI. The new approach is called UMLI in this paper. Note that the regularization parameter  1/2λ in Equation <ref> is usually quite small, so we ignore it in our adapted criterion:

    min_x ∈𝒰max_y ∈ C P_ℒ(y|x) ∑_x_i ∈ℒ^+ -log P_ℒ^+(y_i|x_i)

As is shown in Figure <ref> , we construct a synthetic binary data set and two colours represent
different classes. We demonstrate the performance of four retraining-based active learners EER, UEER, MLI and UMLI on four corners, respectively. One black triangle and circle in each corner represent two initial labeled points. When we compare UEER with EER, it is obvious that UEER selects a number of instances near the decision boundary while EER explores points in a wider range. This is because our method helps UEER make use of the uncertainty information and uncertainty information makes UEER focus on the region which is least certain about. Similar results can also be found between UMLI and MLI. MLI explores over the data space and queries the points around the	border while UMLI balances the exploration and the exploitation. UMLI concentrates on the central part (exploitation) and also searches around the edge. Therefore, we can see that our method enhances retraining-based model by balancing the exploration and the exploitation.



§ EXPERIMENTS

In this section, we investigate the performance of our proposed methods to examine the effectiveness and robustness of our new criterion. The following experiments are limited to binary classification problems. Firstly, we show the experimental setting, then present the extensive experiment results, followed by further discussion and analysis.


 §.§ Experimental setting

We compare the our proposed methods UEER and UMLI against their original version EER and MLI, respectively. Random sampling is also included in this comparison. In all the experiments, we use L_2-regularized logistic regression included in LIBLINEAR package <cit.> as default classifier with the same regularization parameter, λ = 100, for all methods.

The classification accuracy is used as the comparison criterion in our experiment. However, since active learning is a iteratively labeling procedure, we care about the performance during the whole learning process. Thus, it is not reasonable to merely compare the accuracy at some single points. Instead, we generate the learning curve of classification accuracy versus the number of labeled instances. Then, we calculate the area under the learning curve (ALC) as a measure of evaluation.

We test on totally 49 real-world data sets from various real-life applications, including many UCI data sets <cit.>, MNIST handwritten digit dataset <cit.> and 20 Newsgroups dataset <cit.>. There are 39 datasets from UCI benchmark datasets, such as breast, vehicle, heart and so on. These datasets are pre-processed according to <cit.>. For wine data set, we conduct class 2 against class 1 and 3 as binary problem. For glass data set, we also split it into two groups (class 1-3 vs. class 5-7) to build binary case. 
We randomly sub-sample 1000 instances from mushroom for computing efficiency. We select six pairs of letters from Letter Recognition Data Set <cit.>, i.e., D vs. P, E vs. F, I vs.J , M vs.N, V vs. Y and U vs. V since these pairs look similar to each other and distinguishing them is a little challenging. 3 vs. 5, 5 vs. 8 and 7 vs. 9 are three difficult pairs taken from MNIST data set [http://yann.lecun.com/exdb/mnist/http://yann.lecun.com/exdb/mnist/] and used as the binary classification data set. We randomly sub-sample 1500 instances from the three data sets for computing efficiency. We also test the performance on 20 Newsgroups dataset which is a common benchmark used for text classification [http://qwone.com/ jason/20Newsgroups/http://qwone.com/ jason/20Newsgroups/]. Following the work of <cit.>, we also evaluate three binary tasks from 20 Newsgroups dataset: baseball vs. hockey, pc vs. mac, and religion.misc vs. alt.atheism. And the three pairs represent easy, moderate and difficult classification problems, respectively. We apply PCA to reduce the dimensionality of the above three datasets to 500 for computation efficiency. We also use the pre-processed data autos, motorcycles, baseball, hockey used in <cit.>.

To objectively evaluate the performance, each data set is randomly divided into training and test data set of equal size. At the very beginning of active learning, we assume that only two instances randomly picked up from the training data are labeled, and one of them is from the positive class and the other is from the negative class. We run each active learning algorithm 20 times on each real-world dataset. The average performance of each active learning method is reported in the following section. 






 §.§ Results
















































































Table <ref>  shows the experimental results on 49 data sets. The datasets in Table <ref> are sorted with respect to the performance of random sampling. We can find that the comparisons contain the datasets which vary from very difficult problems (e.g., hill) to easy tasks (e.g., acute). To clearly demonstrate the advantage of the proposed method, we do pairwise comparison between the original algorithm and its counterpart, e.g., EER vs. UEER and MLI vs. UMLI, respectively. On each data set, a paired t-tests at 95% significance level is used to determine which method has the best performance or provides comparable outcome. These methods are highlighted in bold face. Over all the experiments, average performances are reported in Table <ref>. “Average Rank” shows the average rank of all the methods with regard to their performances on all the experiments. The lower the value of average rank, the better the method. The “win/tie/loss counts” represents times of our proposed methods versus its counterparts over all the 49 datasets.

As is shown in Table <ref>, our proposed methods UEER and UMLI evidently outperform their counterparts EER and MLI, respectively. UEER surpasses EER in terms of average accuracy, and improves its performance from 0.812 to 0.822. UEER also outperforms EER in terms of “average rank”, which demonstrates the effectiveness of our method. Similar results can be found between UMLI and MLI. UMLI is superior to MLI on the overall performance. Moreover, it is interesting to observe that UEER attains the best overall performance among all the active learning methods.  Over all the experimental data sets, the “win/tie/loss” counts of UEER versus EER is 29/7/13, meaning that UEER is the preferred active learner in over half the cases. With regard to UMLI and MLI, the “win/tie/loss” count is 27/11/11, which also shows the clear benefit of our scheme nonetheless. We also notice that even random sampling can surpass all the other methods, e.g., on the blood data set, indicating that, generally, one might not want to use active learners in a blind way.

To investigate the robustness of our method, we also apply the worst-case criterion on EER and the average-case criterion on MLI, respectively. Due to the lack of space, we omit the results on each data set and only report the average performances. The average performance (ALC) of the worst-case on EER is 0.771 while that of the average-case on MLI is 0.710. To our surprise, they definitely show poorer performances in comparison with our method and even perform worse than random sampling. The possible reason may be that: EER computes the error on the unlabeled data and none of the true label are known, the average-case criterion is a safe choice for EER. Since MLI estimates the loss on the enlarged labeled set ℒ∪{x_i, y_i} and only the true label of x_i is unknown, the worst-case criterion is more appropriate for MLI than the average-case criterion. However, since the proposed method is a trade-off of the two criteria, it can adapt to both settings and show a robust performance for different retraining-based models.























§ CONCLUSIONS


In this paper, we propose a new general method for retraining-based active learning. The proposed method can balance a trade-off of the average-case and worst-case criteria by incorporating uncertainty information (carried by the pre-trained posterior probabilities) within min-max framework. It drives current retraining-based models to pay more attention to the exploitation. We employ the new idea on two state-of-the-art methods to investigate its effectiveness. The synthetic data demonstrates that our method prefers to select the instances which are near the decision boundary in comparison with the original retraining-based approaches. Moreover, extensive experiments on 49 real-world datasets also prove that the proposed method is a promising approach for promoting retraining-based active learners. 









































































































































IEEEtran






