-

2

Related Work

AL methods in deep networks use di erent strategies or a combination of the strategies to query for labels [ 7 ]. The strategies range from density estimation to multi-factor methods. The strategies can be categorized into two groups: population-based strategies and pool-based strategies [ 18 ]. In population-based AL, training and test sets are drawn from the same distribution with an assumption that training and test data both follow the same conditional distribution p(yjx). In this type, the objective is to nd the optimal training input density to generate the training input instances. In pool-based AL, the objective is to optimally select some unlabeled instances from a pool so that a model trained from them can best label the remaining samples. Regardless of whether it is population-based or pool-based, AL is an iterative process [ 14 ]. It rst builds a base model from a small number of labeled training instances, and then using di erent or a combination of utility metrics it selects unlabeled instances and queries for their labels. The newly labeled instances are added to the training labeled set and the model is updated. This process iterates until a termination criterion is met, for example, when the labeling budget is exhausted or the maximum number of iterations is met. Based on the number of unlabeled instances to query at each iteration, AL methods can be grouped as either sequence-mode AL, where one instance is queried each time or batch-mode AL, where multiple instances are queried at each iteration [ 14 ].

This paper focuses on pool-based batch-mode AL for DN. Although numerous AL approaches have been proposed in the literature [ 16 ], a number of them are for standard pool-based AL problems e.g. Donmez et al. presents a dynamic approach that updated selection parameters based on estimated future residual error reduction after each actively sampled instance [ 3 ], Settles and Craven formulates the implementation of AL using information density [ 17 ] and Krempl et al. implements cost-sensitive probabilistic approach for binary classi cation [ 11 ]. Among those approaches limited to AL for DN include the work presented by Duco e and Precioso that uses margin theory to compute instances along the decision boundary, [ 4 ], [ 1 ], [ 8 ] and [ 9 ].

The emphasis in AL is to evaluate the informativeness of an instance, with an assumption that an instance with higher classi cation uncertainty is more crucial to label. This classical approach usually uses statistical theory such as entropy and margin to measure instance utility, however it fails to capture the data distribution information contained in the unlabeled data. This can eventually cause the classi er to select outlier instances to label. Therefore, its important to consider the classi cation uncertainty as well as instances diversity in a population while developing an AL solution. In our approach we consider both the uncertainty and correlation measure to calculate the most informative and representative instance, which we refer as a high con dence instance.

In AL where there is a pre-determined budget on labeling, it is important to estimate the objective function for data selection. This guarantees near-optimal results with signi cantly less computational e ort. The aim is to maximize the objective function while minimizing data acquisition costs (or to remaining within a budget). To deal with this problem we formulate the most informative budget selection task as a continuous optimization problem. The aim is to determine possible queries that maximize the improvement to the classi ers strategy, without overspending the budget. The proposed model addresses the cost-sensitive learning problem based on learning algorithms that construct models for class probability estimation p(yjx). The probability estimates provide an easy means for factoring in the misclassi cation losses in the classi cation decision making step. To address the labeling cost problem, we employ the same probability estimation techniques over the selected high con dence instances. The two methods are then combined into an algorithm that minimizes the combined cost. At each iteration (while the total sum of annotation cost is under a given budget) a high con dence instance 1 to label is selected. 3

Selecting Most Informative Instance

We consider the problem of actively selecting a batch of instances to label, where the contents of the batch must be constrained by some budget. We will use the following notation in this paper. Let xi represents an instance and yi where yi 2 f1; +1g represents the class label for xi, D = DL [ DU , DL denotes labeled instances where 1High con dence instances are the most informative and representative instances selected from the unlabeled set Given a label space Y the uncertainty measure fu of an instance considering both the features and the label can be de ned as: fu(x) : (LS ! R; (i) features view

(DU LS ) ! R; (ii) features-label view to a real number space R. From Equation 1 above: (i) the uncertainty measure is computed from instancefeatures only while (ii) the uncertainty measure is computed from both the instance-features and instance-label. In our method we consider the uncertainty measure computed from instance features and label view which is considered the most e ective [ 10 ]. Out of the three common uncertainty measure criteria namely least con dence, sample margin and entropy, sample margin is prefered since it integrates the second most probable class label in the uncertainty metric hence able to reduce the error rate by de ning the decision boundary. We therefore de ne uncertainty measure as: DL = f(x1; y1); (x2; y2); ::::; (xn; yn)g, DU denotes unlabeled instances where DU = f(x1; ?); (x2; ?); ::::; (xn; ?)g, DH denotes high con dence instances and denotes the model de ned by model parameters. For label space Y with K classes in D we use the class probability estimator P (yjx) to compute the estimate of a label. In order to avoid the problem of generalization of unseen instances and to learn an accurate model, we present a robust approach that uses di erent utility metrics and a cost function. The utility metrics considered in this work are uncertainty, correlation and informativeness measure, thus we present three main components of our approach: a) uncertainty measure, b) correlation measure and the cost-based labeling. 3.1

Uncertainty Measure

(1) (2) (3) (4) fu(x) = P (yi = l1jxi; Y )

P (yi = l2jxi; Y ) With l1 and l2 being the most likely and second most likely labels. High uncertainty value fu implies current model have little knowledge of the instance, and including it into the training set can help improve to the prediction performance of the model. 3.2

Correlation Measure

When developing e cient AL methods, it is critical to consider samples distribution information [ 19 ]. The instance diversity information aids in selecting most representative instances. In order to have more information about the unlabeled instances it is appropriate to select a candidate instance in a more dense region. In addition, selecting an instance to label only based on uncertainty measure may lead to selecting an outlier instance, therefore exploiting sample instance diversity will provide the most informative instance to label. Our method is based on the fact that the trade o between instance uncertainty and correlation is an essential AL problem to address. Given a label space Y , we can de ne di erent groups of correlation of an instance x in a set of unlabeled set as; fc(x) : 8DU > <

DU ! R; feature view

Y Y ! R; label view >:(DU ; y) (DU ; y) ! R; combined view to a real number space R. In Equation 3, the combination of feature and label correlation is called combined view. Di erent algorithms exist for exploiting this type of combination [ 10 ]. Majorly these algorithms are used in a multi-label learning tasks when an instance has more than one label. This setting is ideal for mining tasks on instances with complex structure. In this work we focus on exploiting the pairwise similarities of instances, therefore the informativeness of an instances is weighed by average similarity to its neighbours. Let xi and xj be a pair of instances. To cope with the drawback of uncertainty based selection, we then consider the diversity by evaluating the correlation of the instances. Given a label space Y the correlation measure fc(xi; xj ) between a pair of instances xi and xj can be de ned as: fc(x) = The value of fc(xi) represents the instance density of xi in the unlabeled set. The larger the value, the more densely an instance is correlated with others. A low value of the correlation measure indicates an outlier instance which should not be considered for labeling. Our motivation is that the most representative instances of a distribution can be very informative for improving the generalization performance. Therefore, given correlation measure fc(xi) and uncertainty measure fu(xi) the informativeness of an instance can be de ned as: (5) (6) (7) (8) It can be rewritten as: 3.3

Cost-Based labeling

fi(x) = fu(xi) fc(xi) xi = argmax(ui ci)

i In our approach the high con dence instance evaluation is based on the instance informativeness which is computed from both uncertainty and correlation metrics. The model is trained on labeled instances: feature and label views. After querying for an high con dence unlabeled instance, a model prediction result is generated based on output probability distribution. Each instance xi = ff1i; f2i; :::fqi; yig in labeled set DL = fx1; x2; ::::xsg is represented in a feature space F consisting of a feature space and its class label yi. The size of DL is denoted by s and xi denoted the ith instance in DL. The prediction can be denoted as a mapping function from the feature space F to the class label space Y which can be expressed as;

P (x) : F 7! Y The query strategy used in this work is based on the value of fi discussed in equation 6. Instances are ranked based on the value fi with top ranked instances being the most appropriate to label. Under the current distribution P (yijxi; Y ) each possible instance (xi; ?) from the selected instances DH will be labeled with label yi. When yi = 1, xi is regarded as a high con dence sample. The model update strategy is to train a model based on the information provided by model weights computed from model validation of the performance. We employ the probability estimators in our approach to both minimize the labeling costs and the misclassi cation decisions. We make the assumption that the loss function associated with the decisions is represented as a static K and a 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. Therefore, high con dence instance selection criteria in this study will be based on probability of xi belonging to Kth class which can be expressed as:

K K yi = arg min(C( )+XP (kj )XXP ;k(jjxi)L(yi; j))

2DH k=1 i j=1

The Algorithm 1 describes the Cost-Based Budget Active Learning (CBAL) with budget labeling.

Algorithm 1: Cost-Based Budget Active Learning (CBAL). 1 Input: labeled instance set DL, unlabeled instance set DU , loss matrix L, labeling cost C, empty set DH , a budget m; 2 Output: model ; 3 getModel (DL); 4 while jDLj < m do 5 for each xi in DU do 6 ui fu(xi); 7 ci fc(xi); 8 x argmax(u c);

i 9 DH DH [ fxg; for each j learn P (yjDH ); yi getLabel using Eq.8; DH DH n fyig; DL DL [ fyig;

updateModel (DL); 15 return ;

In Algorithm 1, the labeling is de ned by the budget m with model updates after each iteration (lines 414). At rst the base model is trained using the initial set of labeled data DL. Instance evaluation is done to identify the most informative and representative instance to label (lines 5-9). This evaluation returns the high con dence instances DH selected from the unlabeled population (line 9). For each of the selected instance, its label is queried and consequently the labeled set is updated. The model selection strategy is updated with the learned parameters after every iteration. CBAL is designed to train a classi cation model using a small labeled population sample proportion. 4

Experiments

We conduct experiments with 12 real-world data sets (wine2, seeds3, v2-plant seedling4, liver5, sonar6, vehicle7, breast8, diabetic9, heart10, isolet11, plant12, svhn13) previously considered by other authors in similar domain. For each data set, we split 80% of the instances as the training set, and the balance 20% as the test set to evaluate the prediction accuracy of the models. We select a subset of instances from the training data to query (100 instances per query) for labels and then construct a base classi cation model according to these labeled data. The goal is to pick out high con dence instances such that the constructed model maintains e ective classi caion ability. The training is implemented in a batch-mode AL. We compare our method with other state-of-the-art methods: a). Random Sampling (RS) which selects a certain number of samples from a given set and quire labels; b). Core-Set AL (CSAL) [ 15 ] which de nes the AL problem as a competitive sample core-set selection which is then applied to a CNN in a batch setting; c). Deep Bayesian Active Learning (DBAL): a Bayesian framework proposed in [ 6 ] for high dimensional data which considers Deep Learning problem of dependence on big amount of data; d). Adversarial AL for deep networks (AAL) a margin based approach proposed in [ 4 ] for deep networks with intention of reducing the number of queries to the oracle during training. The both the budget m and the initial labeled set is speci ed before start of iterations. A batch size of 64 was considered for all iterations for both training and testing selection. 100 queries were considered for each iteration. 4.1

Results and Discussion

Figure 1 shows the classi cation accuracy of di erent active learning approaches with varied number of queries. From the observation RS tends to yield better performance when the number of queries is small but as the number of queries increases it starts to slow its e ectivenes in prediction. This observation might be as a result of sampling bias induced by an intelligent selection strategy. CSAL that de ne AL as a core-set problem, is not performing well at the start of training. As the number of queries increases, there is improvement and yields better performance. This is because with few training instances, the learned decision boundary tends to be inaccurate, and as a result, the unlabeled instances near the decision boundary may not be the most high con dence instances to label. The performance of DBAL is better on some datasets but performs poorly on others. This inconsistency might be as a result of identi ed cluster structure of unlabeled data that is not always consistent with the target classi cation model. The behavior of AAL is similar to that of DBAL. Finally, we observe that for most cases, CBAL is able to outperform the baseline methods signi cantly and we attribute this success to the principle selecting high con dent samples at each iteration, and the specially aspect of minimizing the labeling and decision cost after each subsequent iteration. 5

Conclusion and Future Work

We propose a new near optimal AL approach called CBAL, that measure both the informative and representative of an instance using instance utility to get a high con dence instance to lable while minimizing the labeling and 2http://archive.ics.uci.edu/ml/datasets/Wine 3https://archive.ics.uci.edu/ml/datasets/seeds 4https://www.kaggle.com/vbookshelf/v2-plant-seedlings-dataset 5https://archive.ics.uci.edu/ml/datasets/Liver+Disorders 6https://archive.ics.uci.edu/ml/datasets/Connectionist+Bench+(Sonar,+Mines+vs.+Rocks 7https://archive.ics.uci.edu/ml/datasets/Statlog+Vehicle+Silhouettes 8https://www.kaggle.com/paultimothymooney/breast-histopathology-images 9https://www.kaggle.com/sovitrath/diabetic-retinopathy-224x224-gaussian- ltered 10https://archive.ics.uci.edu/ml/datasets/Heart+Disease 11https://archive.ics.uci.edu/ml/datasets/isolet 12https://www.kaggle.com/vipoooool/new-plant-diseases-dataset 13https://www.kaggle.com/stanfordu/street-view-house-numbers 70 60 y rcau 50 c c onA 40 i t iecd 30 r P

20 80 70 60 50 40 90 80 70 60 50 40 90 80 rcay 70 ccuA 60 iton 50 c i red 40 P 30

CBAL RS CSAL AAL DBAL

CBAL RS CSAL AAL

DBAL CBAL RS CSAL AAL DBAL CBAL RS CSAL AAL DBAL 70 60 50 40 decision cost. The proposed approach of minimizing cost is based on the minmax principled view. Our current work is based on budget constrained learning with pairwise similarities of instances. In the future, we plan to extend this work to multi-label learning tasks by considering instances with more than one label. In addition we plan to consider the expert knowledge in the training by allowing the user to control tradeo between selection and labeling, this will lead to incoporating domain knowledge into AL

References

[1] Hamed H Aghdam , Abel Gonzalez-Garcia, Joost van de Weijer, and Antonio M Lopez, ` Active learning for deep detection neural networks' , in Proceedings of the IEEE International Conference on Computer Vision , pp. 3672 { 3680 , ( 2019 ).

[2] Dana Angluin , ` Queries and concept learning' , Machine learning , 2 ( 4 ), 319 { 342 , ( 1988 ).

[3] Pinar Donmez , Jaime G Carbonell, and Paul N Bennett, ` Dual strategy active learning' , in European Conference on Machine Learning , pp. 116 { 127 . Springer, ( 2007 ).

[4] Melanie Duco e and Frederic Precioso, ` Adversarial active learning for deep networks: a margin based approach' , arXiv preprint arXiv: 1802 . 09841 , ( 2018 ).

[5] Andre Esteva and Brett Kuprel et al, ` Dermatologist-level classi cation of skin cancer with deep neural networks' , Nature , 542 ( 7639 ), 115 , ( 2017 ).

[6] Yarin Gal and Riashat Islam et al, ` Deep bayesian active learning with image data' , in ICML , pp. 1183 { 1192 , ( 2017 ).

[7] M Hasenj ager and H Ritter, `Active learning in neural networks', in New learning paradigms in soft computing , 137 { 169 , Springer, ( 2002 ).

[8] Manuel Haussmann , Fred A Hamprecht, and Melih Kandemir, ` Deep active learning with adaptive acquisition' , arXiv preprint arXiv: 1906 . 11471 , ( 2019 ).

[9] Steven CH Hoi , Rong Jin, Jianke Zhu, and Michael R Lyu, ` Batch mode active learning and its application to medical image classi cation' , in ICML , pp. 417 { 424 , ( 2006 ).

[10] Sheng-Jun Huang , Nengneng Gao , and Songcan Chen, `Multi-instance multi-label active learning .', in IJCAI , pp. 1886 { 1892 , ( 2017 ).

[11] Georg Krempl , Daniel Kottke, and Vincent Lemaire, ` Optimised probabilistic active learning (opal)' , Machine Learning , 100 ( 2-3 ), 449 { 476 , ( 2015 ).

[12] Mingsheng Long and Han Zhu et al, ` Deep transfer learning with joint adaptation networks' , in ICML , pp. 2208 { 2217 , ( 2017 ).

[13] Kamal Nigam and Andrew McCallum , ` Pool-based active learning for text classi cation' , in Conference on Automated Learning and Discovery (CONALD) , ( 1998 ).

[14] Hiranmayi Ranganathan , Hemanth Venkateswara, Shayok Chakraborty, and Sethuraman Panchanathan, ` Deep active learning for image classi cation' , in 2017 IEEE International Conference on Image Processing (ICIP) , pp. 3934 { 3938 , ( 2017 ).

[15] Ozan Sener and Silvio Savarese, ` Active learning for convolutional neural networks: A core-set approach' , arXiv: 1708 . 00489 , ( 2017 ).

[16] Burr Settles , ` Active learning literature survey' , Technical report , University of Wisconsin-Madison, Dept of Computer Sciences, ( 2009 ).

[17] Burr Settles and Mark Craven , ` An analysis of active learning strategies for sequence labeling tasks' , in Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing , pp. 1070 { 1079 , ( 2008 ).

[18] Masashi Sugiyama and Shinichi Nakajima, ` Pool-based active learning in approximate linear regression' , Machine Learning , 75 ( 3 ), 249 { 274 , ( 2009 ).

[19] Martin Szummer and Tommi S. Jaakkola , ` Information regularization with partially labeled data' , in Advances in Neural Information processing systems , pp. 1049 { 1056 , ( 2003 ).

[20] Xingquan Zhu and Peng Zhang et al, ` Active learning from data streams' , in IEEE ICDM, pp. 757 { 762 , ( 2007 ).