Bias-Aware Heapified Policy for Active Learning

The data efficiency of learning-based algorithms is more and more important since high-quality and clean data is expensive as well as hard to collect. In order to achieve high model performance with the least number of samples, active learning is a technique that queries the most important subset of data from the original dataset. In active learning domain, one of the mainstream research is the heuristic uncertainty-based method which is useful for the learning-based system. Recently, a few works propose to apply policy reinforcement learning (PRL) for querying important data. It seems more general than heuristic uncertainty-based method owing that PRL method depends on data feature which is reliable than human prior. However, there have two problems - sample inefficiency of policy learning and overconfidence, when applying PRL on active learning. To be more precise, sample inefficiency of policy learning occurs when sampling within a large action space, in the meanwhile, class imbalance can lead to the overconfidence. In this paper, we propose a bias-aware policy network called Heapified Active Learning (HAL), which prevents overconfidence, and improves sample efficiency of policy learning by heapified structure without ignoring global inforamtion(overview of the whole unlabeled set). In our experiment, HAL outperforms other baseline methods on MNIST dataset and duplicated MNIST. Last but not least, we investigate the generalization of the HAL policy learned on MNIST dataset by directly applying it on MNIST-M. We show that the agent can generalize and outperform directly-learned policy under constrained labeled sets.


Introduction
Nowadays, deep learning has been widely used in several fields, like medical field or automatic driving. However, to reach the whole potential of deep learning, we still struggle to prepare tons of annotated data for training. The progress of collecting such amount of data is obviously a tedious and laborious work. Thus, it is a critical bottleneck to obtain adequate data for training an accurate model. To solve the problem, simply collecting more data may be the most intuitive idea, yet it is highly time-consuming and expensive in certain domains such as cancer detection, Natural Language Copyright c 2019, National Tsing Hua University. All rights reserved.

… … …
Uncertainty Strategy Other Strategy Policy Figure 1: For selecting the most acceptable image from the unlabeled set, we construct a heap for comparing the whole data two by two which is determined by policy individually. The policy will observe bias-aware feature (Fig. 3) to avoid using uncertainty-based sampling strategy. After the whole comparison, the final image will be annotated and sent to the training set. This process will be repeated until the budget is exhausted.
Processing tasks, etc. Thus, active learning comes in handy to minimize the cost by querying important data in order to improve accuracy by labeling as few data as possible.
As to the methodology of active learning, there have been quite a few heuristic methods querying data according to uncertainty (Shannon 2001;Zhou and Sun 2014;Tang et al. 2017), diversity (Sener and Savarese 2018;Wang et al. 2017), etc. Additionally, some work carries out active learning by virtue of multi-heuristic methods such as RALF (Ebert, Fritz, and Schiele 2012) which tries to manage different methods with hybrid strategies according to the time, considering that exploration/exploitation criteria should be balanced in different moment.
Nevertheless, imbalanced data is the one that possesses stronger relation to the strategy rather than time, which brings about overconfidence, quite problematic as querying data. To cope with it, many works (Sener and Savarese 2018;Wang et al. 2019;Geirhos et al. 2019;Bachem, Lucic, and Krause 2017;Lakshminarayanan, Pritzel, and Blundell 2017;Pop and Fulop 2018) intend to eliminate the overconfidence effect. One of the approaches is to query by commit-tee (QBC) (Lakshminarayanan, Pritzel, and Blundell 2017;Pop and Fulop 2018), using the ensemble idea to avoid overconfidence on one single model through multi-models, sacrificing computational cost for training stability. Another approach is to query by disagreement (QBD), directly learning from errors which are probably disagreement samples, including unseen samples and in-class potential uncertainty samples, which are predicted incorrectly but possess high confidence from the classification model. However, it is a chicken-egg problem that it is hard to identify if the sample is an error before the annotation. Thus, some works (Gissin and Shalev-Shwartz 2019; Su et al. 2019) propose using meta-heuristic method to approximate the idea. More specifically (Gissin and Shalev-Shwartz 2019) queries data that is likely to be unseen. (unlike the labeled set distribution.) However, it is not general enough to model the behavior of in-class potential uncertain samples.
Considering the generalization of methods, they are not general enough that in every different case, algorithms should be customized. What if we can guide the model with a general agent that shares the experience of querying data? Recently, there are a few works (Bachman, Sordoni, and Trischler 2017;Pang et al. 2018;Konyushkova, Sznitman, and Fua 2017;Fang, Li, and Cohn 2017;Chen et al. 2018) focusing on ways of "learning to active learn". Through similar features of data between different datasets, the agent is capable of sharing the experience that is transferred from other datasets. For example, a stream-based reinforcement learning (Fang, Li, and Cohn 2017) on prediction of part of the speech, the agent's selection depends on the grammatical architecture of a sentence, which can be applied on both Spanish and Dutch. Additionally, Chen et al. (Chen et al. 2018) propose to take video motion as feature to share experience. However, in spite of the avoidance of time-consuming by using stream-based active learning, the stability is influenced by order of the stream.
To sum up, the low generalization of current methods for active learning is a critical problem that can result in high cost for designing customized algorithm, and also about how we avoid overconfidence that obstacles uncertainty querying is what we should solve urgently. In this paper, we propose a bias-aware heapified active learning method for pooling based active learning called heapified active learning (HAL). It can observe the whole data and spend low computing time with a heapified structure, which is not influenced by the problem of ordering in stream-based reinforcement learning. Additionally, during querying, we design a bias-aware feature which contributes to the switching of strategy. Learning with prior of images, the experiences can be transferred to other target domains and remain high performance. In short, our HAL enables the agent to make use of features of the training dataset as to query data with the best strategy, avoiding bias which skews the labeled domain. In the experiments, our model outperforms other baseline methods on MNIST dataset and synthetic duplicated MNIST dataset which mimics properties in static surveillance videos. Moreover, our policy trained on MNIST achieves the best results on MNIST-M. This demonstrates the great generalization of our method across datasets.

Contribution:
• The policy of our methods for querying data is formulated generally which possesses high generalization between datasets. • Our pool based policy agent queries data more efficiently with low time consumption through heapified structure. • Through using bias aware feature, the policy will be able to avoid overconfidence which makes uncertainty based query method inefficiently. In the following sections, we first describe related work in Sec. 2. Then, we introduce our main technical contribution in Sec. 3, including feature designing, policy setting and so on. Finally, we report our experimental results in Sec. 4.

Related Work
To improve the efficiency of data sampling, many works tend to use uncertainty-based method and select more sparsing data at the same time in batch mode selection. However, this kind of methods cannot solve the overconfidence problem. In order to deal with it, in recently, there are three main research directions on active learning related to ours. One is learning with other experts(query by committee, QBC (Pop and Fulop 2018;Gal, Islam, and Ghahramani 2017;Rosales, Krishnamurthy, and Bharat Rao 2008)). Another is learning from disagreement(query by disagreement, QBD (Gissin and Shalev-Shwartz 2019; Kane et al. 2017;Zhang and Chaudhuri 2014;Ducoffe and Precioso 2018)). The other is to manage different criteria and combine the strategies (Pang et al. 2018;Konyushkova, Sznitman, and Fua 2017;Fang, Li, and Cohn 2017;Chen et al. 2018). Query By Committee. The QBC method is to make use of mutual information from multiple models and enable certain sample to be more confident. For instance, DBAL (Gal, Islam, and Ghahramani 2017) generates different outputs through Bayesian network with noises called MC-dropout. However, the outputs generated from different noisy models are not ideal. DEBAL (Pop and Fulop 2018) , following the previous method, proposes the concept of ensembling to solve the problem above. The difference between our method and the ensemble idea is that we use features of labeled data to let the policy model conscious of the situation of overconfidence. Query By Disagreement. To query by disagreement, we should know which sort of data belong to disagreement cases, thus meta-heuristic exploring strategies are required, like DAL (Gissin and Shalev-Shwartz 2019) which selects data predicted unlabeled by a discriminator trained with labeled and unlabeled data and DFAL (Ducoffe and Precioso 2018) using adversarial image to build up an image decision boundary, finding its nearby unlabeled sample as uncertain data. However, those meta-heuristic strategies can not be general enough. Our method uses data-driven policy to learn switching strategy for disagreement samples instead, which can be more general in other cases. Learning to Active learning. Instead of designing the algorithm for selecting unlabeled data heuristically, some adopt stream-based learning (Fang, Li, and Cohn 2017)  comparison.(E l , Eu is labeled/unlabeled set embedding feature ∈ R fn ) In every single comparison with heapified policy, π θ , the agent will choose a preferable data. After a series of comparison, the data which is estimated as the most valuable will be annotated and added to the training set D l . By training the prediction model f φ with the new labeled set D l and evaluating by validation set, D val , we can obtain the performance growth of f φ which can be used as the reward for the agent π θ .
(RL). Through training on Deep Q Network (DQN), it can learn the selecting policy and choose informative data that enable the model to be more robust to certain types of errors. As the number of selected data reaches the budget, the Markov Decision Process (MDP) terminates. The state for the agent is composed of the content, marginals and the confidence of prediction. By doing so, the agent can give consideration to both the uncertainty of every word class prediction and the architecture of every sentence which can avoid the bias in the prediction model. At last, taking the performance growth as reward can enable the model to predict the reward of every selection precisely as to make great progress on the performance of the prediction model. However, they trade off time consuming and performance by just reviewing a subset of data and missing more important data in early steps. As for our method, we use pool-based active learning, selecting the most valuable one in the dataset and using heap structure to reduce the time complexity.

Method
In the following, first, we overview our active learning pipeline in Sec. 3.1. Second, we describe the design of the observation features for policy learning and introduce each of them individually in Sec. 3.2. Third, in Sec. 3.3, we propose a new structure of policy which is "heapified" as querying data, and each policy is learned with offline policy gradient. Before that, we define some common notations below. Notation : We have three sets, labeled set, validation set, and unlabeled set, which are denoted as is image, we assume there are L classes and denote y i ∈ {1, 2, ..., L} as labels. Besides, we have two models; one is a classification model f φ with parameter φ, and the other is an agent π θ with parameter θ. In the classification model, we extract embedding feature which is denoted as f E φ (.) ∈ R fn .

Overview
As illustrated in Fig. 2, in our active learning procedure we have a prediction model f φ supervised by D l . Next, our agent π θ will repeatedly pick two random samples from D u and compare which unlabeled data has more impact on classification model f φ until the whole D u has already been compared. After iterating the comparisons, a final image will be determined and annotated by annotators, and then we add it to D l for the training of the prediction model f φ . Finally, the reward can be calculated by evaluating the marginal performance of the task with the evaluation set D val , offering the agent π θ to learn. Through the steps mentioned above, the agent π θ is able to learn a querying policy from the data.

Observation Feature Designing
As the objective of active learning, we aim to find out the hard samples and the disagreement samples. The disagree-  Figure 3: Bias-aware concept. It's riskier to fall in overconfidence condition that the eigenspace contribution highly depends on principal eigenvectors, leading to non-continuous distribution of data described by only specific dimensions such as the (V1, V2) eigenspace, which have large eigenvalue. Thus, we need to reduce the dependence on principal eigenvectors and get to obtain continuous distribution like the space such as the (V3, V4) eigenspace, which have small eigenvalue. ment samples include unseen samples and the in-class potential uncertain samples. The unseen samples are the data far from labeled set distribution. The in-class potential uncertain samples are predicted incorrectly but possess high confidence from the classification model. Therefore, feature design can be divided into three parts, bias-aware feature, uncertainty to deal with hard samples, and the disagreement sample learning, respectively.
Bias-aware: maximum component suppression During query procedure, imbalanced data usually results in overconfidence of certain labels, which introduces bias on them. Thus, we design bias-aware feature, enabling the agent to observe the distribution of each class for the query policy. As shown in Fig. 3, overconfidence usually occurs as the real data distribution is non-continuous. Additionally, the blue region in Fig. 3 is where some samples are predicted incorrectly but possess high confidence from the classification model, we called that in-class potential uncertainty sample. Therefore, in this case, selecting samples with high uncertainty is not an optimal policy. In contrast, if the data distribution is continuous, selecting samples located at the boundary area benefits the training of the classification model.
Every data in the dataset can be represented by their own embedding features f E φ (.) which is extracted from the classification model, indicating that they can be mapped to a multidimensional space. In each class, through the calculation of the eigenvalues, we can observe the degree of the dominance of each vector. By taking the largest eigenvalue, the bias-aware feature offers information about the degree of how simply a certain class of data are described. In our design, we select the value oppositely as the feature BA(.) shown in Eq. 1, we called it as maximum component suppression. Lower value implies the oversimplification of feature description, causing overconfidence on the unlabeled set D u . As a result, the bias-aware feature can be served as a signal enabling the agent to observe the distribution of labeled data D l for switching different strategies. Here, we define bias-aware feature as follow: where BA(.) ∈ R L is the feature of bias aware, is the set of class-wise eigenvalues of labeled set's embedding features and this criterion describes how confident can the embedding feature represent the data without main eigenvector.
Uncertainty In order to boost the performance of the classification model f φ trained on rough data at the beginning of selecting data, we need to find out hard samples located in ambiguous regions near the decision boundary. Here, we model it by MC-dropout (Gal, Islam, and Ghahramani 2017) which outperforms Shannon entropy. We perturb the model by dropout and compare it with the unperturbed model so as to find out how uncertain is the data. That is, the higher the uncertainty of the data, the more it is worth to be selected. The MC-dropout method is formulated as follow: where the H(x; φ) = − L i=1 P (ŷ i |x; φ)log(P (ŷ i |x; φ)) , y i is the probability distribution, φ is the parameters of active model and φ is the parameters with noise by dropout which is done n times.
However, depending merely on information of uncertainty limits the growth of performance resulting by overconfidence, so we need to solve it by disagreement samples.
Disagreement sample learning In order to solve the overconfidence samples, we try to use the concept of QBD to learn from disagreement samples , which are unseen samples and in-class potential uncertain samples clearly defined in Sec. 3.2. To find out unseen sample, inspiring by DAL (Gissin and Shalev-Shwartz 2019), we query samples that are far from class-wise labeled set distribution. We formulate the calculation of the distance shown as follow: where the diversity feature is defined as the distance between unlabeled data and the labeled set representation of each class distribution. The Dist(.) is defined as follow: where the x is input image sample, φ is model parameters, f E φ (X D l y=yi ) ∈ R fn is the mean of embedding features in each class of labeled set and f n is the length of the embedding feature. We have ablation study about labeled set representation in table 1. In the Eq. 4, we calculate the distance between the unlabeled data D u and the labeled data D l to represent whether data is seen or not for the classification Here we use memory replay to achieve reward collection efficiently. In every single episode, the agent is required to choose only K images as budget for labeling to the training set D l . In each data query, the agent will go through unlabeled set Duwhich have M images, and the certain path of the final winner of the whole comparison (dark blue path shown above in the figure) is the most related reward's experience. Policy learns from the path and we show up detail of the decision process with agent network in double box. model f φ . In addition, we normalize the distance for each class owing that every class distribution is quite different.
On the other hand, searching in-class potential uncertain samples for sampling is quite tricky unless we provide handcraft features (e.g. SIFT (Lowe 2004), SURF (Bay et al. 2008), HOG (Dalal and Triggs 2005), BoVW (Chandra, Kumar, and Jawahar 2012)) as prior and information of labeled set D l as constraint.
As designing the feature we observe the model prediction, embedding feature of the unlabeled set D u and some analysis of the labeled set D l .The feature of a single data can be represented as follow: O = {I(x; φ), D(x; φ, D l ), P rior(x), BA(φ, D l )}, (5) using the uncertainty approach of mutual information Eq. 2 as the value of uncertainty for exploiting the mainstream data. To explore unseen case in labeled set D l , we use Eq. 3 to model it. In addition, as to in-class potential uncertain sample which provides a conditional prior, we add a handcraft feature to describe the image statistic information for the active modelf φ to explore more efficiently. Finally, we express the bias-aware feature with D l by Eq. 1 in order to prevent overconfidence which means that in a few classes, misclassification occurs which is caused by low complexity of class features description.

Heapified Policy
Our policy π θ is a maximum-heap like pooling based query method, so the action space(A) is quite large. Thus, to learn experience more efficiently, we adopt off-policy policy gradient method. As shown in Fig. 4 , our single episode is limited by budget K and our heapified policy will select the most valuable image from M unlabeled set images. Then, we break the task into as many sub-policies, which only compare two features of images, and the better one advances to the next round. We analyze the time complexity of Monte Carlo experience collection and maximum heapified like sub-policies. The time complexity of maximum heapified collection is O(logM ) less than Monte Carlo collection which is O(M ) . In Monte Carlo sampling method, in order to select the best item, we need to compare pair item M − 1 times. On the other hands, maximum heapified collection uses logM times to achieve the goal of the most influential of classification model performance unlabeled data selection. In this setting, even if the action space is reduced, the global information(overview of the whole unlabeled set) still remains. Sub-Policy model. Our sub policy agent a = π θ (s) tries to compare which one is better based on two image's features, O define in Eq. 5, where a ∈ {0, 1}, s = (O 1 ,O 2 ). After two comparisons are done, the two winner data will form the next state, noted as the sub transition T (s t+1 |a top tion task with prediction model φ as r = Acc(D val , φ ) − Acc(D val , φ), where φ is trained model parameters and the φ is original parameters before training. Offline policy gradient. The reward collection is not efficient and single collection cost much time by reward designed as the increase of performance. Therefore, we learn from previous sampling reward and decision. Then we compute offline-policy gradient to update model as follow: logπ θ (a i,j,t |s i,j,t ) * r * corr . (6) where N is episode of game and the K is limited of budget.
M is the number of totally unlabeled set images. π θ (.) is now noted as probability estimate.The corr term is to correct the reward which remained from previous policy action probability. The correction term of reward is noted as π θ (ai,j |si,j ) π θ (ai,j |si,j ) , it will maintain the present behavior if identical to previous experience, where π θ (.) is previous probability estimate, and the π θ (.) is nowstaged probability estimate. The agent will update their gradient direction more stably with previous experience.

Experiments
We conduct experiments to validate the proposed biasaware learning to learn policy in cross modalities setting and image duplicated setting. Firstly, in Sec. 4.1 , the result of ablation study shows that our method using bias aware feature and mean representation of labeled set as diversity hint obtain the best result with a few labeled data in the beginning and the experiment is in train model from scratch setting. Secondly, in Sec. 4.2, we get better result comparing with other baselines in finetune setting. Finally, we validate the transferability of our query policy across datasets in Sec. 4.3. We report average (15 times) performance of all experiments.
Implementation detail. We train classification model LeNet5 (Lecun et al. 1998) with two datasets. One is MNIST (LeCun and Cortes 2010) , and the other one is MNIST-M (Ganin and Lempitsky 2015) which blend background with color photos from BSDS500. Firstly, we split MNIST, MNIST-M in three subset -labeled, unlabeled and validation set (D l , D u , D val ), which amounts to (50, 60000, 10000) training pairs with balanced number of class. Secondly, we use Adam optimizer (Kingma and Ba 2015) with learning rate 0.001 to train our policy agent in 800 episodes. Each episode has 10 steps and each step samples 10 images. The discount factor of policy gradient is set as 0.9998. Finally, we use the accuracy to plot a learning curve with the size of images and ALC norm = ALC−A rand Amax−A rand which is mentioned in the active learning challenge (Guyon et al. 2011). Moreover, ALC is the performance of the classification model by proposed query method. A rand is performance of the classification model by random query. A max is performance of the classification model by fully D u with label which will be used in table 1.

Ablation Study
Diversity feature. In the design of the diversity feature, we calculate the distance between the representation of unlabeled set and the labeled set. There are different kinds of statistic method to represent the diversity feature. We compare these methods, including mean, median, mode, maximum and minimum in table 1 by average ALC norm on MNIST. As table 1 shown, we use average ALC norm as an indicator and we can find out mean representation of the class-wise labeled set feature is the best choice. Thus, we apply mean representation method to represent labeled data and calculate the diversity feature of unlabeled data by Eq. 3. Bias aware feature. We design the bias aware feature to avoid overconfidence condition in query data procedure. In order to simulate the dilemma, we train classification model from scratch with little labeled data. Because of imbalanced data (mode collapse (Pop and Fulop 2018) have mentioned), the effect is more extreme on a small dataset, resulting in overconfidence. As Fig. 5 shown, we can see that heapified active learning w/ bias feature can get better performance than w/o bias feature in the interval from 50 to 100 images. The uncertainty approach-DBAL, due to incomplete data understanding, faces overconfidence in the beginning. Thus, we know the importance of bias aware feature to avoid overconfidence at the beginning of the query procedure.

Compare Previous Works
Here, we compare different types of query methods on MNIST and duplicated MNIST which has many redundant and noise information. From the results, we show that our HAL is outstanding both dataset. Before that, we introduce the baseline methods as following: w/ bias aware wo/ bias aware DBAL Figure 5: The ablation study of bias aware feature: w/, w/o bias aware comparison. Bias is easily be generated while training from scratch, resulting in uncertainty approach-DBAL will not be useful. Thus, with bias aware feature, overconfidence can be prevented.  figure, we can find out that our HAL only needs less than 100 images to achieve over 85% of accuracy compared to other methods on average. On the right figure, even in a repeated and noised dataset, HAL can achieve over 85% of accuracy with less than 75 images; on the contrast, other methods need over 100 images to reach this criterion.
• Random: Sample data uniformly from D u .
• Entropy (Shannon 2001): Sample maximum value of chaotic prediction from D u . • DBAL (Gal, Islam, and Ghahramani 2017): Apply MC-dropout in the model to produce noises, and then query data with Eq. 2 from D u with maximum value. • K-center (Sener and Savarese 2018): It will compute the minimum Euclidean distance d of an unlabeled data by kcenter(x i ) = min(x i , x j ), where x j ∈D l . Then, it will query data with the maximum distance. • Stream-based policy network (Fang, Li, and Cohn 2017): Through Deep Q Learning (DQN), the agent learns the strategy of choosing images.With the arrival of every batch of images, the agent will decide if the batch of data is necessary to be added to the training set by observing the feature of the batch with the length of action space len(A) = 2. As the budget is exhausted, the selection process will be terminated. As shown in Fig. 6, our method queries data more efficiently than the other method in the whole training procedure. Instead of the uncertainty based method, they are unstable in the beginning and fall in the overconfidence condition. Specifically, we outperform the stream-based agent on average that it misses many important data in early steps. On the other hand, we create a special dataset to test the ability to perform generally among repeated and noised dataset.
Synthetic dataset: In real world application, there may be a lot of redundant data and make the model bias easily. For example, image data from surveillance camera, it may completely capture the same street view for hours. In this scenario, the capability to avoid duplicate information is essential. Therefore, we create a synthetic dataset -Duplicate M N IST with 60000 images. In the set, we have 48000 class-uniformly repeated image (80 percent of the total dataset) with random Gaussian noise. In the right figure of Fig. 6, our method is general enough that it is able to achieve high performance in few amounts of data when encountering repeated and noised images.

Generalization
Our method learns how to query from meta-experience with image spatial texture structure as prior by HoG, so we can adopt the experience in cross-domain setting which is Gray(MNIST) v.s. RGB(MNIST-M) scale and outperform with 5% through querying procedure on average. In this setting, we train the agent in MNIST and directly apply as a query method in MNIST-M. We obtain a better result than training from scratch randomly shown in Fig. 7. In this setting, we realize that our HAL is a general method can adopt query experience to other works that have similar prior.

Conclusion
We proposed a bias-aware policy network called heapified active learning (HAL), which prevents data sample bias due to overly confident model prediction. Moreover, our policy model trades off the query time complexity and global information by heapified structure in pooling based active learning setting. In addition, in our experiment, HAL outperforms other baseline methods on MNIST dataset and duplicated MNIST. From the results, we can show that our method is able to reach high generalization on different dataset which share similar features.

HAL (Our) Train from scratch
Figure 7: The generalization of query method, HAL . Using our HAL query data directly is more efficiently than training from scratch randomly by about 5% performance is Gray(MNIST)→ RGB(MNIST-M) dataset