Learning active learning at the crossroads? evaluation and discussion L. Desreumaux1 , V. Lemaire2 1 SAP Labs, Paris, France 2 Orange Labs, Lannion, France Abstract. Active learning aims to reduce annotation cost by predict- ing which samples are useful for a human expert to label. Although this field is quite old, several important challenges to using active learning in real-world settings still remain unsolved. In particular, most selec- tion strategies are hand-designed, and it has become clear that there is no best active learning strategy that consistently outperforms all oth- ers in all applications. This has motivated research into meta-learning algorithms for “learning how to actively learn”. In this paper, we com- pare this kind of approach with the association of a Random Forest with the margin sampling strategy, reported in recent comparative studies as a very competitive heuristic. To this end, we present the results of a benchmark performed on 20 datasets that compares a strategy learned using a recent meta-learning algorithm with margin sampling. We also present some lessons learned and open future perspectives. 1 Introduction Modern supervised learning methods3 are known to require large amounts of training examples to reach their full potential. Since these examples are mainly obtained through human experts who manually label samples, the labelling pro- cess may have a high cost. Active learning (AL) is a field that includes all the selection strategies that allow to iteratively build the training set of a model in interaction with a human expert, also called oracle. The aim is to select the most informative examples to minimize the labelling cost. In this article, we consider the selective sampling framework, in which the strategies manipulate a set of examples D = L ∪ U of constant size, where L = {(xi , yi )}li=1 is the set of labelled examples and U = {xi }ni=l+1 is the set of unlabelled examples. In this framework, active learning is an iterative process that continues until a labelling budget is exhausted or a pre-defined perfor- mance threshold is reached. Each iteration begins with the selection of the most informative example x? ∈ U. This selection is generally based on information collected during previous iterations (predictions of a classifier, density measures, etc.). The example x? is then submitted to the oracle that returns the corre- sponding class y ? , and the pair (x? , y ? ) is added to L. The new learning set is 3 In this article, we limit ourselves to binary classification problems. © 2020 for this paper by its authors. Use permitted under CC BY 4.0. 2 L. Desreumaux Learning and V. Lemaire Active Learning at the Crossroads? Evaluation and Discussion 39 then used to improve the model and the new predictions are used in the next iteration. The utility measures defined by the active learning strategies in the litera- ture [36] differ in their positioning according to a dilemma between the exploita- tion of the current classifier and the exploration of the training data. Selecting an unlabelled example in an unknown region of the observation space Rd helps to explore the data, so as to limit the risk of learning a hypothesis too specific to the current set L. Conversely, selecting an example in a sampled region of Rd locally refines the predictive model. 1.1 Traditional heuristic-based AL The active learning field comes from a parallel between active educational meth- ods and machine learning theory. The learner is from now a statistical model and not a student. The interactions between the student and the teacher corre- spond to the interactions between the model and the oracle. The examples are situations used by the model to generate knowledge on the problem. The first AL algorithms were designed with the objective of transposing these “educational” methods to the machine learning domain. The easiest way was to keep the usual supervised learning methods and to add “strategies” relying on various heuristics to guide the selection of the most informative examples. From the first initiative and up to now, a lot of strategies motivated by human intuitions have been suggested in the literature. The purpose of this paper is not to give an overview of the existing strategies but the reader may find in [36, 1] of lot of them. A careful reading of the experimental results published in the literature shows that there is no best AL strategy that consistently outperforms all others in all applications, and some strategies cater to specific classifiers or to specific appli- cations. Based on this observation, several comprehensive benchmarks carried out on numerous datasets have highlighted the strategies which, on average, are the most suitable for several classification models [28, 41, 29]. They are given in Table 1. For example, the most appropriate strategy for logistic regression and random forest is an uncertainty-based sampling4 strategy, named margin sampling, which consists in selecting at each iteration the instance for which the difference between the probabilities of the two most likely classes is the smallest [34]. To produce this table, we purposefully omitted studies that have a restricted scope, such as focusing on too few datasets [4], specific tasks [37], an insufficient number of strategies [35, 31], or variants of a single strategy [21]. 4 The reader interested in the measures used to quantify the degree of uncertainty in the context of active learning may find in [25, 18] an interesting view which advocates a distinction between two different types of uncertainty, referred to as epistemic and aleatoric. 40 Learning Louis active learning Desreumaux at the crossroads? and Vincent Lemaire evaluation and discussion 3 Strategy RF1 SVM2 5NN3 GNB4 C4.55 LR6 VFDT7 Margina [29] Entropyb [41] QBDc [28] [28] Densityd [29, 28] [28] OERe [29] [29] [29] Table 1. Best model/strategy associations highlighted in the literature as a guide to use the appropriate strategy versus the classifier. Strategies: (a) Margin sampling, (b) Entropy sampling, (c) Query by Disagreement, (d) Density sampling, (e) Optimistic Error Reduction. Classifiers: (1) Random Forest, (2) Support Vector Machine, (3) 5- Nearest Neighbors, (4) Gaussian Naive Bayes, (5) C4.5 Decision Tree, (6) Logistic Regression, (7) Very Fast Decision Tree. 1.2 Meta-learning approaches to active learning While the traditional AL strategies can achieve remarkable performance, it is often challenging to predict in advance which strategy is the most suitable in a particular situation. In recent years, meta-learning algorithms have been gaining in popularity [23]. Some of them have been proposed to tackle the problem of learning AL strategies instead of relying on manually designed strategies. Motivated by the success of methods that combine predictors, the first AL algorithms within this paradigm were designed to combine traditional AL strate- gies with bandit algorithms [3, 12, 17, 8, 10, 26]. These algorithms learn how to select the best AL criterion for any given dataset and adapt it over time as the learner improves. However, all the learning must be achieved within a few exam- ples to be helpful, and these algorithms suffer from a cold start issue. Moreover, these approaches are restricted to combining existing AL heuristic strategies. Within the meta-learning framework, some other algorithms have been devel- oped to learn from scratch an AL strategy on multiple source datasets and trans- fer it to new target datasets [19, 20, 27]. Most of them are based on modern rein- forcement learning methods. The key challenge consists in learning an AL strat- egy that is general enough to automatically control the exploitation/exploration trade-off when used on new unlabelled datasets, which is not possible when using heuristic strategies. 1.3 Objective of this paper From the state of the art, it appears that meta-learned AL strategies can outper- form the most widely used traditional AL strategies, like uncertainty sampling. However, most of the papers that introduce new meta-learning algorithms do not include comprehensive benchmarks that could ascertain the transferability of the learned strategies and demonstrate that these strategies can safely be used in real-world settings. 4 L. Desreumaux Learning and V. Lemaire Active Learning at the Crossroads? Evaluation and Discussion 41 The objective of this article is thus to compare two possible options in the realization of an AL solution that could be used in an industrial context: using a traditional heuristic-based strategy (see Section 1.1) that, on average, is the best one for a given model and could be used as a strong baseline easy to implement and not so easy to beat, or using a more sophisticated strategy learned in a data-driven fashion that comes from the very recent literature on meta-learning (see Section 1.2). To this end, we present the results of a benchmark performed on 20 datasets that compares a strategy learned using the meta-learning algorithm proposed in [20] with margin sampling [34], the models used being in both cases logistic re- gression and random forest. We evaluated the work of [20] since the authors claim to be able to learn a “general-purpose” AL strategy that can generalise across diverse problems and outperform the best heuristic and bandit approaches. The rest of the paper is organized as follows. In Section 2, we explain all the aspects of the Learning Active Learning (LAL) method proposed in [20], namely the Deep Q-Learning algorithm and the modeling of active learning as a Markov decision process (MDP). In Section 3, we present the protocol used to do extensive comparative experiments on public datasets from various application areas. In Section 4, we give the results of our experimental study and make some observations. Finally, we present some lessons learned and we open future perspectives in Section 5. 2 Learning active learning strategies 2.1 Q-Learning A Markov decision process is a formalism for modeling the interaction between an agent and its environment. This formalism uses the concepts of state, which describes the situation in which the environment finds itself, action, which de- scribes the decision made by the agent, and reward, received by the agent when it performs an action. The procedure followed by the agent to select the action to be performed at time t is the policy. Given a policy π, the state-action table is the function Qπ (s, a) which gives the expectation of the weighted sum of the rewards received from the state s if the agent first executes the action a and then follows the policy π. Q-Learning is a reinforcement learning algorithm that estimates the optimal state-action table Q? = maxπ Qπ from interactions between the agent and the environment. The state-action table Q is updated at any time from the current state s, the action a = π(s) where π is the policy derived from Q, the reward received r and the next state of the environment s0 :   0 0 Qt+1 (s, a) = (1 − αt (s, a))Qt (s, a) + αt (s, a) r + γ max 0 Qt (s , a ) , (1) a ∈A where γ ∈ [0, 1[ is the weighting factor of the rewards and the αt (s, a) ∈ ]0, 1[ are the learning steps that determine the weight of the new experience in relation 42 Learning Louis active learning Desreumaux at the crossroads? and Vincent Lemaire evaluation and discussion 5 to the knowledge acquired at previous steps. Assuming that all the state-action pairs are visited an infinite number of times and under some conditions on the learning steps, the resulting sequence of state-action tables converges to Q? [40]. The goal of a reinforcement learning agent is to maximize the rewards re- ceived over the long term. To do this, in addition to actions that seem to lead to high rewards (exploitation), the agent must select potentially suboptimal actions that allow him to acquire new knowledge about the environment (exploration). For Q-Learning, the -greedy method is the most commonly used to manage this dilemma. It consists in randomly exploring with a probability of  and acting according to a greedy strategy that chooses the best action with a probability of (1 − ). It is also possible to decrease the probability  at each transition to model the fact that exploration becomes less and less useful with time. 2.2 Deep Q-Learning In the Q-Learning algorithm, if the state-action table is implemented as a two- input table, then it is impossible to deal with high-dimensional problems. It is necessary to use a parametric model that will be noted as Q(s, a; θ). If it is a deep neural network, it is called Deep Q-Learning. The training of a neural network requires the prior definition of an error criterion to quantify the loss between the value returned by the network and the actual value. In the context of Q-Learning, the latter value does not exist: one can only use the reward obtained after the completion of an action to calculate a new value, and then estimate the error achieved by calculating the difference between the old value and the new one. A possible cost function would thus be the following:  2 0 0 0 L(s, a, r, s , θ) = r + γ max 0 Q(s , a ; θ) − Q(s, a; θ) . (2) a ∈A However, this poses an obvious problem: updating the parameters leads to up- dating the target. In practice, this means that the training procedure does not converge. In 2013, a successful implementation of Deep Q-Learning introducing several new features was published [24]. The first novelty is the introduction of a target network, which is a copy of the first network that is regularly updated. This has the effect of stabilizing learning. The cost function becomes:  2 0 − 0 0 − L(s, a, r, s , θ, θ ) = r + γ max 0 Q(s , a ; θ ) − Q(s, a; θ) , (3) a ∈A where θ − is the vector of the target network parameters. The second nov- elty is experience replay. It consists in saving each experience of the agent (si , ai , ri , si+1 ) in a memory of size m and using random samples drawn from it to update the parameters by stochastic gradient descent. This random draw allows to not necessarily select consecutive, potentially correlated experiences. 6 L. Desreumaux Learning and V. Lemaire Active Learning at the Crossroads? Evaluation and Discussion 43 2.3 Improvements to Deep Q-Learning Many improvements to Deep Q-Learning have been published since the article that introduced it. We present here the improvements that interest us for the study of the LAL method. Double Deep Q-Learning. A first improvement is the correction of the overesti- mation bias. It has indeed been empirically shown that Deep Q-Learning as pre- sented in Section 2.2 can produce a positive bias that increases the convergence time and has a significant negative impact on the quality of the asymptotically obtained policy. The importance of this bias and its consequences have been verified in particular in the configurations the least favourable to its emergence, i.e. when the environment and rewards are deterministic. In addition, its value increases with the size of the set of actions. To correct this bias, the solution which has been proposed in [15] consists in not using the parameters θ − to both select and evaluate an action. The cost function then becomes:    2 0 − 0 0 0 − L(s, a, r, s , θ, θ ) = r + γQ s , arg max 0 Q(s , a ; θ); θ − Q(s, a; θ) . a ∈A (4) Prioritized Experience Replay. Another improvement is the introduction of the notion of priority in experience replay. In its initial version, Deep Q-Learning considers that all the experiences can identically advance learning. However, reusing some experiences at the expense of others can reduce the learning time. This requires the ability to measure the acceleration potential of learning asso- ciated with an experience. The priority measure proposed in [33] is the absolute value of the temporal difference error: δi = ri + γ max 0 Q(si+1 , a0 ; θ − ) − Q(si , ai ; θ) . (5) a ∈A A maximum priority is assigned to each new experience, so that all the experi- ences are used at least once to update the parameters. However, the experiences that produce a small temporal difference error at first use may never be reused. To address this issue, a method was introduced in [33] to manage the trade-off between uniform sampling and sampling focusing on experiences producing a large error. It consists in defining the probability of selecting an experience i as follows: ρβ p i = Pm i β , with ρi = δi + e, (6) k=1 ρk where β ∈ R+ is a parameter that determines the shape of the distribution and e is a small positive constant that guarantees pi > 0. The case where β = 0 is equivalent to uniform sampling. 44 Learning Louis active learning Desreumaux at the crossroads? and Vincent Lemaire evaluation and discussion 7 2.4 Formulating active learning as a Markov decision process The formulation of active learning as a MDP is quite natural. In each MDP state, the agent performs an action, which is the selection of an instance to be labelled, and the latter receives a reward that depends on the quality of the model learned with the new instance. The active learning strategy becomes the MDP policy that associates an action with a state. In this framework, the iteration t of the policy learning process from a dataset divided into a learning set D = Lt ∪Ut and a test set5 D0 consists in the following steps: 1. A model h(t) is learned from Lt . Associated with Lt and Ut , it allows to characterize a state st . 2. The agent performs the action at = π(st ) ∈ At which defines the instance x(t) ∈ Ut to label. 3. The label y (t) associated with x(t) is retrieved and the training set is updated, i.e. Lt+1 = Lt ∪ {(x(t) , y (t) )} and Ut+1 = Ut \ {x(t) }. 4. The agent receives the reward rt associated with the performance `t on the test set D0 . This reward is used to update the policy (see Section 2.5). The set of actions At depends on time because it is not possible to select the same instance several times. These steps are repeated until a terminal state sT is reached. Here, we consider that we are in a terminal state when all the instances have been labelled or when `t ≥ q, where q is a performance threshold that has been chosen as 98% of the performance obtained when the model is learned on all the training data. The precise definition of the set of states, the set of actions and the reward function is not evident. To define a state, it has been proposed to use a vector whose components are the scores ybt (x) = P(Y = 0 | x) associated with the unlabelled instances of a subset V set aside. This is the simplest representation that can be used to characterize the uncertainty of a classifier on a dataset at a given time t. The set of actions has been defined at iteration t as the set of vectors ai = yt (xi ), g(xi , Lt ), g(xi , Ut )], where xi ∈ Ut and : [b 1 X 1 X g(xi , Lt ) = dist(xi , xj ), g(xi , Ut ) = dist(xi , xj ), (7) |Lt | |Ut | xj ∈Lt xj ∈Ut where dist is the cosine distance. An action is therefore characterized by the uncertainty on the associated instance, as well as by two statistics related to the density of the neighbourhood of the instance. The reward function has been chosen constant and negative until arrival in a terminal state (rt = −1). Thus, to maximize its reward, the agent must perform as few interactions as possible. 5 Given that active learning is usually applied in cases, this test set assumed to be small or very small the performance evaluated on this test set could be a possibly bad approximation. This issue and techniques for avoiding it are not examined in this paper. 8 L. Desreumaux Learning and V. Lemaire Active Learning at the Crossroads? Evaluation and Discussion 45 2.5 Learning the optimal policy through Deep Q-Learning The Deep Q-Learning algorithm with the improvements presented in Section 2.3 is used to learn the optimal policy. To be able to process a state space that evolves with each iteration, the neural network architecture has been modified. The new architecture considers actions as inputs to the Q function in the same way as states. It then returns only one value, while the classical architecture takes only one state as input and returns the values associated with all the actions. The learning procedure involves a collection of Z labelled datasets {Zi }1≤i≤Z . It consists in repeating the following steps (see Figure 1): 1. A dataset Z ∈ {Zi } is randomly selected and divided into a training set D and a test set D0 . 2. The policy π derived from the Deep Q-Network is used to simulate several active learning episodes on Z according to the procedure described in Sec- tion 2.4. Experiences (st , at , rt , st+1 ) are collected in a finite size memory. 3. The Deep Q-Network parameters are updated several times from a mini- batch of experiences extracted from the memory (according to the method described in Section 2.3). To initialize the Deep Q-Network, some warm start episodes are simulated using a random sampling policy, followed by several parameter updates. Once the strategy is learned, its deployment is very simple. At each iteration of the sampling process, the classifier is re-trained, then the vector characterizing the process state and all the vectors associated with the actions are calculated. The vector a? corresponding to the example to label x? is then the one that satisfies a? = arg maxa∈A Q(s, a; θ), the parameters θ being set at the end of the policy learning procedure. Initial Simulation of 10 active Experience replay Selection of 32 experiences examples learning episodes memory of size 10 000 using the probabilities aa pi + stochastic gradient descent ×60 Q R T = |U0 | 1 ÿ 32 ◊ Ω ◊ ≠ 0.0001 · Ò◊ a L(sj , aj , rj , sj+1 , ◊, ◊ ≠ )b . 32 j=1 . ¸Øq . (si , ai , ri , si+1 , pi ) |V| = 30 Strategy : . fi(s) = arg max Q(s, a; ◊) (si+1 , ai+1 , ri+1 , si+2 , pi+1 ) s … a aœA . ¸Øq . Deep Q-Network Fig. 1. Illustration of the different steps involved in an iteration of the policy learning phase using Deep Q-Learning (the arrows give intuitions about main steps and data flows) . 46 Learning Louis active learning Desreumaux at the crossroads? and Vincent Lemaire evaluation and discussion 9 3 Experimental protocol In this section, we introduce our protocol of the comparative experimental study we conducted. 3.1 Policy learning To learn the strategy, we used the same code6 , the same hyperparameters and the same datasets as those used in [20]. The complete list of hyperparameters is given in Table 2 with the variable names from the code that represent them. The datasets from which the strategy is learned are given in Table 3. The specification of the neural network architecture is very simple (all the layers are fully connected): (i) the first layer (linear + sigmoid) receives the vector s (i.e. |V| = 30 input neurons) and has 10 output neurons; (ii) the second layer (linear + sigmoid) concatenates the 10 output neurons of the first layer with the vector a (i.e. 13 neurons in total) and has 5 output neurons; (iii) finally, the last layer (linear) has only one output to estimate Q(s, a). Hyperparameter Description N STATE ESTIMATION = 30 Size of V REPLAY BUFFER SIZE = 10000 Experience replay memory size PRIORITIZED REPLAY EXPONENT = 3 Exponent β involved in Equation (6) BATCH SIZE = 32 Minibatch size for stochastic gradient descent LEARNING RATE = 0.0001 Learning rate TARGET COPY FACTOR = 0.01 Value that sets the target network update1 EPSILON START = 1 Exploration probability at start EPSILON END = 0.1 Minimum exploration probability EPSILON STEPS = 1000 Number of updates of  during the training WARM START EPISODES = 100 Number of warm start episodes NN UPDATES PER WARM START = 100 Number of parameter updates after the warm start TRAINING ITERATIONS = 1000 Number of training iterations TRAINING EPISODES PER ITERATION = 10 Number of episodes per training iteration NN UPDATES PER ITERATION = 60 Number of updates per training iteration 1 In this implementation, the target network parameters θ − are updated each time the param- eters θ are changed as follows: θ − ← (1−TARGET COPY FACTOR)·θ − +TARGET COPY FACTOR·θ. Table 2. Hyperparameters involved in Deep Q-Learning. 3.2 Traditional heuristic-based AL used as baseline: margin sampling Our objective is to compare the performance of a strategy learned using LAL with the performance of a heuristic strategy that, on average, is the best one for 6 https://github.com/ksenia-konyushkova/LAL-RL 10 L. Desreumaux Learning and V. Lemaire Active Learning at the Crossroads? Evaluation and Discussion 47 Dataset |D| |Y| #num #cat maj (%) min (%) australian 690 2 6 8 55.51 44.49 breast-cancer 272 2 0 9 70.22 29.78 diabetes 768 2 8 0 65.10 34.90 german 1000 2 7 13 70.00 30.00 heart 293 2 13 0 63.82 36.18 ionosphere 350 2 33 0 64.29 35.71 mushroom 8124 2 0 21 51.80 48.20 wdbc 569 2 30 0 62.74 37.26 Table 3. Datasets used to learn the new strategy. Columns: number of examples, num- ber of classes, numbers of numerical and categorical variables, proportions of examples in the majority and minority classes. a given model. Several benchmarks conducted on numerous datasets have high- lighted the fact that margin sampling is the best heuristic strategy for logistic regression (LR) and random forest (RF) [41, 29]. Margin sampling consists in choosing the instance for which the difference (or margin) between the probabilities of the two most likely classes is the smallest: x? = arg min P(y1 | x) − P(y2 | x), (8) x∈U where y1 and y2 are respectively the first and second most probable classes for x. The main advantage of this strategy is that it is easy to implement: at each iteration, a single training of the model and |U| predictions are sufficient to select an example to label. A major disadvantage, however, is its total lack of exploration, as it only exploits locally the hypothesis learned by the model. We chose to evaluate the Margin/LR association because it is with logistic regression that the hyperparameters of Table 2 were optimized in [20]. In addi- tion, in order to determine whether it is necessary to modify them when another model is used, we also evaluated the Margin/RF association. This last associa- tion is particularly interesting because it is the best association highlighted in a recent and large benchmark carried out on 73 datasets, including 5 classification models and 8 active learning strategies [29]. In addition, we evaluated random sampling (Rnd) for both models. 3.3 Datasets The datasets were selected so as to have a high diversity according to the fol- lowing criteria: (i) number of examples; (ii) number of numerical variables; (iii) number of categorical variables; (iv) class imbalance. We have also taken care to exclude datasets that are too small and not representative of those used in an industrial context. The 20 selected datasets are described in Table 4. They all come from the UCI database [11], apart from the dataset “orange-fraud” which is dataset on fraud detection. Four of 48 Learning Louis active learning Desreumaux at the crossroads? and Vincent Lemaire evaluation and discussion 11 the datasets have been used in a challenge on active learning that took place in 2010 [14] and the dataset “nomao” comes from another challenge on active learning [6]. Dataset |D| |Y| #num #cat maj (%) min (%) adult 48790 2 6 8 76.06 23.94 banana 5292 2 2 0 55.16 44.84 bank-marketing-full 45211 2 7 9 88.30 11.70 climate-simulation-craches 540 2 20 0 91.48 8.52 eeg-eye-state 14980 2 14 0 55.12 44.88 hiva 40764 2 1617 0 96.50 3.50 ibn-sina 13951 2 92 0 76.18 23.82 magic 18905 2 10 0 65.23 34.77 musk 6581 2 166 1 84.55 15.45 nomao 32062 2 89 29 69.40 30.60 orange-fraud 1680 2 16 0 63.75 36.25 ozone-onehr 2528 2 72 0 97.11 2.89 qsar-biodegradation 1052 2 41 0 66.35 33.65 seismic-bumps 2578 2 14 4 93.41 6.59 skin-segmentation 51444 2 3 0 71.51 28.49 statlog-german-credit 1000 2 7 13 70.00 30.00 thoracic-surgery 470 2 3 13 85.11 14.89 thyroid-hypothyroid 3086 2 7 18 95.43 4.57 wilt 4819 2 5 0 94.67 5.33 zebra 61488 2 154 0 95.42 4.58 Table 4. Datasets used for the evaluation of the strategy learned by LAL. Columns: number of examples, number of classes, numbers of numerical and categorical variables, proportions of examples in the majority and minority classes. 3.4 Evaluation criteria In our evaluation protocol, the active sampling process begins with the random selection of one instance in each class and ends when 250 instances are labelled. This value ensures that our results are comparable to other studies in the liter- ature. For performance comparison, we used the area under the learning curve (ALC) based on the classification accuracy. We do not claim that the ALC is a “perfect metric”7 but it is the defacto standard evaluation criterion in active learning, and it has been chosen as part of a challenge [14]. Our evaluation was carried out by cross-validation with 5 partitions, in which class imbalance within the complete dataset was preserved. For each partition, the sampling process was repeated 5 times with different initializations to get a 7 There is literature on more expressive summary statistics of the active-learning curve [39, 30]. This could be a limitation of this current article, other metrics could be tester in future versions of experiments. 12 L. Desreumaux Learning and V. Lemaire Active Learning at the Crossroads? Evaluation and Discussion 49 mean and a variance on the result. However, we have made sure that the initial instances are identical for all the strategy/model associations on each partition so as to not introduce bias into the results. In addition, for Rnd, the random sequence of numbers was identical for all the models. 4 Results The results of our experimental study are given in Table 5. The mean ALC ob- tained for each dataset/classifier/strategy association are reported (the optimal score is 100). The left part of the table gives the results for logistic regression and the right part gives the results for random forest. The penultimate line cor- responds to the averages calculated on all the datasets and the last line gives the number of times the strategy has won, tied or lost. The non-significant dif- ferences were established on the basis of a paired t-test at 99% significance level (where H0: same mean between populations and where the mean is the estimate out of 5 repetitions x cross-validation with 5 partitions of each method). Dataset Rnd/LR Margin/LR LAL/LR Rnd/RF Margin/RF LAL/RF maj adult 77.93 78.91 78.97 80.17 81.27 81.21 76.06 banana 53.03 57.39 53.12 80.24 73.81 73.58 55.16 bank-marketing-full 86.85 87.62 87.72 88.19 88.34 88.49 88.30 climate-simulation 87.22 89.13 88.62 91.15 91.14 91.13 91.48 eeg-eye-state 56.08 55.32 56.11 65.53 67.58 64.42 55.12 hiva 64.43 70.84 71.80 96.32 96.47 96.44 96.50 ibn-sina 84.77 88.58 88.90 90.53 93.41 92.75 76.18 magic 76.49 77.93 77.64 78.05 80.79 79.68 65.23 musk 83.73 82.34 81.95 89.55 96.18 95.35 84.55 nomao 89.45 91.43 91.37 89.41 92.32 92.07 69.40 orange-fraud 76.70 81.74 74.26 89.15 90.66 90.48 63.75 ozone-onehr 92.90 94.26 95.06 96.61 96.83 96.89 97.11 qsar-biodegradation 80.98 82.62 83.53 80.34 82.76 82.40 66.35 seismic-bumps 90.87 92.59 92.14 92.48 92.92 93.02 93.41 skin-segmentation 77.05 82.69 83.21 91.51 95.70 95.77 71.51 statlog-german-credit 70.76 72.12 72.34 72.25 72.93 72.78 70.00 thoracic-surgery 83.76 83.93 82.72 83.51 84.41 84.18 85.11 thyroid-hypothyroid 97.21 97.99 97.97 97.75 98.77 98.71 95.43 wilt 93.53 95.18 92.87 94.86 97.23 97.02 94.67 zebra 86.40 90.31 91.36 94.71 95.54 95.25 95.42 Mean 80.51 82.65 82.08 87.12 88.45 88.08 79.53 win/tie/loss 0/5/15 3/15/2 2/15/3 1/4/15 3/16/1 0/16/4 Table 5. Results of the experimental study. Several observations can be made. First of all, it should be noted that the choice of model is decisive: the results of random forest are all better than those of logistic regression. The random forest model learns indeed very well from few data, as highlighted in [32]. We can notice that even with random sampling, RF is almost always better than LR, regardless of the strategy used. In addition, using 50 Learning Louis active learning Desreumaux at the crossroads? and Vincent Lemaire evaluation and discussion 13 margin sampling with this model allows a significant performance improvement. This model is very competitive in itself because by its nature, it includes terms of exploration and exploitation (see Section 5 Conclusion about this point). In addition, the results of the learned strategy clearly show that a good active learning strategy has been learned, since it performs better than random sampling over a large number of datasets. However, the learned strategy is no better than margin sampling. These results are nevertheless very interesting since only 8 datasets were used in the learning procedure. Finally, the results show a well-known fact about active learning: on very unbalanced datasets, it is difficult to achieve a better performance than random sampling, as shown in the last column of Table 5 in which the results obtained by always predicting the majority class are given. The “cold start” problem that occurs in active learning, i.e. the inability of making reliable predictions in early iterations (when training data is not sufficient), is indeed further aggravated when a dataset has highly imbalanced classes, since the selected samples are likely to belong to the majority class [38]. However, if the imbalance is known, it may be interesting to associate strategies with a model or criterion appropriate to this case, as illustrated in [13]. To investigate the “learning speed”, we show results for different sizes of L in Table 6. They lead to similar conclusions and our results for |L| = 32 confirm the results of [32]. The reader may find all our experimental results on Github8 . |L| = 32 |L| = 64 |L| = 128 |L| = 250 Dataset Rnd Margin LAL Rnd Margin LAL Rnd Margin LAL Rnd Margin LAL adult 77.95 77.88 78.16 79.72 80.51 81.05 81.13 82.79 82.48 82.12 83.55 83.40 banana 71.13 65.48 65.16 77.93 71.42 70.96 83.64 75.58 75.70 86.55 79.71 81.35 bank... 88.05 87.90 88.10 88.29 88.38 88.54 88.43 88.82 88.90 88.75 89.21 89.35 climate... 91.26 91.26 91.18 91.40 91.29 91.40 91.26 91.33 91.33 91.44 91.22 91.29 eeg... 58.28 58.94 57.34 62.07 63.17 60.79 66.77 69.38 65.35 72.55 75.08 72.46 hiva 96.36 96.52 96.49 96.36 96.55 96.54 96.46 96.57 96.56 96.49 96.65 96.65 ibn-sina 86.88 91.17 89.78 90.48 93.99 92.96 92.73 94.76 94.25 93.86 95.85 95.48 magic 71.99 75.63 72.95 76.85 80.20 77.26 80.15 82.71 82.01 82.42 84.53 84.43 musk 85.29 89.50 90.09 87.43 94.44 94.18 90.58 98.78 97.63 93.64 99.98 99.31 nomao 85.92 89.35 89.37 88.92 92.46 92.09 90.85 93.69 93.33 92.36 94.52 94.37 orange... 88.06 90.36 90.09 89.16 90.98 90.67 90.08 91.72 91.33 90.41 91.85 91.74 ozone... 96.36 96.97 97.01 96.74 97.04 97.10 96.93 97.08 97.11 97.02 97.03 97.05 qsar... 75.75 78.08 76.61 79.75 82.09 81.42 81.94 84.65 84.88 84.03 86.12 86.08 seismic... 92.39 93.21 93.19 92.42 93.28 93.19 92.52 93.26 93.20 93.14 93.08 93.28 skin... 86.42 89.19 89.46 90.80 96.19 96.06 93.70 98.86 98.65 95.85 99.56 99.49 statlog... 70.36 70.70 69.70 70.94 72.47 71.75 72.40 73.46 74.10 74.29 75.22 75.06 thoracic... 83.14 84.42 84.12 83.31 85.02 84.76 83.70 84.89 84.68 84.21 84.51 84.68 thyroid... 97.26 98.71 98.43 97.86 99.15 98.71 98.08 99.10 98.89 98.26 98.84 98.98 wilt 94.60 96.23 95.98 95.01 97.47 96.90 95.30 98.21 97.64 96.07 98.51 98.37 zebra 94.66 95.32 95.28 94.87 95.44 95.31 94.96 95.72 95.46 95.01 96.04 95.33 Mean 84.60 85.84 85.42 86.51 88.07 87.58 88.08 89.56 89.17 89.42 90.55 90.40 Table 6. Mean test accuracy (%) for different sizes of |L| with the random forest model. 8 https://github.com/ldesreumaux/lal_evaluation 14 L. Desreumaux Learning and V. Lemaire Active Learning at the Crossroads? Evaluation and Discussion 51 5 Discussion and open questions In this article, we evaluated a method representative of a recent orientation of active learning research towards meta-learning methods for “learning how to actively learn”, which is on top of the state of the art [20], versus a traditional heuristic-based Active Learning (the association of Random Forest and Margin) which is one of the best method reported in recent comparative studies [41, 29]. The comparison is limited to just one representative of each of the two classes (meta-learning and traditional heuristic-based) but since each is on top of the state of the art several lessons can be drawn from our study. Relevance of LAL. First of all, the experiments carried out confirm the relevance of the LAL method, since it has enabled us to learn a strategy that achieves the performance of a very good heuristic, namely margin sampling, but contrary to the results in [20], the strategy is not always better than random sampling. This method still raises many problems, including that of the transferability of the learned strategies. An active learning solution that can be used in an industrial context must perform well on real data of an unknown nature and must not involve parameters to be adjusted. With regard to the LAL method, a first major problem is therefore the constitution of a “dataset of datasets” large and varied enough to learn a strategy that is effective in very different contexts. Moreover, the learning procedure is sensitive to the performance criteria used, which in our view seems to be a problem. Ideally, the strategy learned should be usable on new datasets with arbitrary performance criteria (AUC, F-score, etc.). From our point of view, the work of optimizing the many hyperparameters of the method (see Table 2) can not be carried out by a user with no expertise in deep reinforcement learning. About the Margin/RF association. In addition to the evaluation of the LAL method, we confirmed a result of [29], namely that margin sampling, associated with a random forest, is a very competitive strategy. From an industrial point of view, regarding the computational complexity, the performances obtained and the absence of “domain knowledge required to be used” the Margin/RF association remains a very strong baseline difficult to beat. However, it shares a major drawback with many active learning strategies, that is its lack of reliability. Indeed, there is no strategy that is better or equivalent to random sampling on all datasets and with all models. The literature on active learning is incomplete with regard to this problem, which is nevertheless a major obstacle to using active learning in real-world settings. Another important problem in real-world applications, little studied in the literature, is the estimation of the generalization error without a test set. It would be interesting to check if the Out-Of-Bag samples of the random forests [5] can be used in an active learning context to estimate this error. Concerning the exploitation/exploration dilemma, margin sampling clearly performs only exploitation. The good results of the Margin/RF association may suggest that the RF algorithm intrinsically contains a part of exploration due to 52 Learning Louis active learning Desreumaux at the crossroads? and Vincent Lemaire evaluation and discussion 15 the bagging paradigm. It could be interesting to add experiments in the future to test this point. Still with regard to the random forests, an open question is to study if a better strategy than margin sampling could be designed. Since the random forests are ensemble classifiers, a possible way of research to design this strategy is to check if they could be used in the credal uncertainty framework [2] which seeks to differentiate between the reducible and irreducible part of the uncertainty in a prediction. About error generalization. In Real world application AL should be used most of the time in absence of a test dataset. A open question could be to a use another known result about RF: the possibility to have an estimate of the generalization error using the Out-Of-Bag (OOB) samples [16, 5]. We did not present experi- ments on this topic in this paper but an idea could be to analyze the convergence versus the number of labelled examples between the OOB performance and the test performance to check at which “moment” (|L|) one could trust9 the OOB performance (OOB performance ≈ test performance). The use of a “random uniform forest” [9] for which the OOB performance seems to be more reliable could also be investigated. About the benchmarking methodology. Recent benchmarks have highlighted the need for extensive experimentation to compare active learning strategies. The research community might benefit from a “reference” benchmark, as in the field of time series classification [7], so that new results can be rigorously compared to the state of the art on a same and large set of datasets. By this way, one will have comprehensive benchmarks that could ascertain the transferability of the learned strategies and demonstrate that these strategies can safely be used in real-world settings. If this reference benchmark is created, the second step would be to decide how to compare the AL strategies. This comparison could be made using not a single criterion but a “pool” of criteria. This pool may be chosen to reflect different “aspects” of the results [22]. References 1. Aggarwal, C.C., Kong, X., Gu, Q., Han, J., Yu, P.S.: Active Learning: A Survey. In: Aggarwal, C.C. (ed.) Data Classification: Algorithms and Applications, chap. 22, pp. 571–605. CRC Press (2014) 2. Antonucci, A., Corani, G., Bernaschina, S.: Active Learning by the Naive Credal Classifier. In: Proceedings of the Sixth European Workshop on Probabilistic Graph- ical Models (PGM). pp. 3–10 (2012) 3. Baram, Y., El-Yaniv, R., Luz, K.: Online Choice of Active Learning Algorithms. Journal of Machine Learning Research 5, 255–291 (2004) 9 Since when |L| is very low the RF do overtraining thus it’s train performance is not a good indicator for the error generalization 16 L. Desreumaux Learning and V. Lemaire Active Learning at the Crossroads? Evaluation and Discussion 53 4. Beyer, C., Krempl, G., Lemaire, V.: How to Select Information That Matters: A Comparative Study on Active Learning Strategies for Classification. In: Proceed- ings of the 15th International Conference on Knowledge Technologies and Data- driven Business. ACM (2015) 5. Breiman, L.: Out-of-bag estimation (1996), https://www.stat.berkeley.edu/ ~breiman/OOBestimation.pdf, last visited 08/03/2020 6. Candillier, L., Lemaire, V.: Design and analysis of the nomao challenge active learning in the real-world. In: Proceedings of the ALRA: Active Learning in Real- world Applications, Workshop ECML-PKDD. (2012) 7. Chen, Y., Keogh, E., Hu, B., Begum, N., Bagnall, A., Mueen, A., Batista, G.: The UCR Time Series Classification Archive (2015), www.cs.ucr.edu/~eamonn/time_ series_data/ 8. Chu, H.M., Lin, H.T.: Can Active Learning Experience Be Transferred? 2016 IEEE 16th International Conference on Data Mining pp. 841–846 (2016) 9. Ciss, S.: Generalization Error and Out-of-bag Bounds in Random (Uni- form) Forests, working paper or preprint, https://hal.archives-ouvertes.fr/ hal-01110524/document, last visited 06/03/2020 10. Collet, T.: Optimistic Methods in Active Learning for Classification. Ph.D. thesis, Université de Lorraine (2018) 11. Dua, D., Graff, C.: UCI Machine Learning Repository (2017), http://archive. ics.uci.edu/ml 12. Ebert, S., Fritz, M., Schiele, B.: Ralf: A reinforced active learning formulation for object class recognition. In: 2012 IEEE Conference on Computer Vision and Pattern Recognition. pp. 3626–3633 (2012) 13. Ertekin, S., Huang, J., Bottou, L., Giles, L.: Learning on the Border: Active Learn- ing in Imbalanced Data Classification. In: Conference on Information and Knowl- edge Management. pp. 127–136. CIKM (2007) 14. Guyon, I., Cawley, G., Dror, G., Lemaire, V.: Results of the Active Learning Chal- lenge. In: Proceedings of Machine Learning Research. vol. 16, pp. 19–45. PMLR (2011) 15. Hasselt, H.v., Guez, A., Silver, D.: Deep Reinforcement Learning with Double Q- Learning. In: AAAI Conference on Artificial Intelligence. pp. 2094–2100 (2016) 16. Hastie, T., Tibshirani, R., Friedman, J.: The elements of statistical learning: data mining, inference and prediction. Springer, 2 edn. (2009) 17. Hsu, W.N., Lin, H.T.: Active Learning by Learning. In: Proceedings of the Twenty- Ninth AAAI Conference on Artificial Intelligence. pp. 2659–2665. AAAI Press (2015) 18. Hüllermeier, E., Waegeman, W.: Aleatoric and Epistemic Uncertainty in Machine Learning: An Introduction to Concepts and Methods. arXiv:1910.09457 [cs.LG] (2019) 19. Konyushkova, K., Sznitman, R., Fua, P.: Learning Active Learning from Data. In: Advances in Neural Information Processing Systems 30, pp. 4225–4235 (2017) 20. Konyushkova, K., Sznitman, R., Fua, P.: Discovering General-Purpose Active Learning Strategies. arXiv:1810.04114 [cs.LG] (2019) 21. Körner, C., Wrobel, S.: Multi-class Ensemble-Based Active Learning. In: Proceed- ings of the 17th European Conference on Machine Learning. pp. 687–694. Springer- Verlag (2006) 22. Kottke, D., Calma, A., Huseljic, D., Krempl, G., Sick, B.: Challenges of Reli- able, Realistic and Comparable Active Learning Evaluation. In: Proceedings of the Workshop and Tutorial on Interactive Adaptive Learning. pp. 2–14 (2017) 54 Learning Louis active learning Desreumaux at the crossroads? and Vincent Lemaire evaluation and discussion 17 23. Lemke, C., Budka, M., Gabrys, B.: Metalearning: a survey of trends and technolo- gies. Artificial Intelligence Review 44, 117–130 (2015) 24. Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., Riedmiller, M.: Playing Atari with Deep Reinforcement Learning. arXiv:1312.5602 [cs.LG] (2013) 25. Nguyen, V.L., Destercke, S., Hüllermeier, E.: Epistemic Uncertainty Sampling. In: Discovery Science (2019) 26. Pang, K., Dong, M., Wu, Y., Hospedales, T.M.: Dynamic Ensemble Active Learn- ing: A Non-Stationary Bandit with Expert Advice. In: Proceedings of the 24th International Conference on Pattern Recognition. pp. 2269–2276 (2018) 27. Pang, K., Dong, M., Wu, Y., Hospedales, T.M.: Meta-Learning Transferable Ac- tive Learning Policies by Deep Reinforcement Learning. arXiv:1806.04798 [cs.LG] (2018) 28. Pereira-Santos, D., de Carvalho, A.C.: Comparison of Active Learning Strategies and Proposal of a Multiclass Hypothesis Space Search. In: Proceedings of the 9th International Conference on Hybrid Artificial Intelligence Systems – Volume 8480. pp. 618–629. Springer-Verlag (2014) 29. Pereira-Santos, D., Prudêncio, R.B.C., de Carvalho, A.C.: Empirical investigation of active learning strategies. Neurocomputing 326–327, 15–27 (2019) 30. Pupo, O.G.R., Altalhi, A.H., Ventura, S.: Statistical comparisons of active learning strategies over multiple datasets. Knowl. Based Syst. 145, 274–288 (2018) 31. Ramirez-Loaiza, M.E., Sharma, M., Kumar, G., Bilgic, M.: Active learning: an em- pirical study of common baselines. Data Mining and Knowledge Discovery 31(2), 287–313 (2017) 32. Salperwyck, C., Lemaire, V.: Learning with few examples: an empirical study on leading classifiers. In: Proceedings of the 2011 International Joint Conference on Neural Networks. pp. 1010–1019. IEEE (2011) 33. Schaul, T., Quan, J., Antonoglou, I., Silver, D.: Prioritized Experience Replay. arXiv:1511.05952 [cs.LG] (2016) 34. Scheffer, T., Decomain, C., Wrobel, S.: Active Hidden Markov Models for Informa- tion Extraction. In: Hoffmann, F., Hand, D.J., Adams, N., Fisher, D., Guimaraes, G. (eds.) Advances in Intelligent Data Analysis. pp. 309–318 (2001) 35. Schein, A.I., Ungar, L.H.: Active learning for logistic regression: an evaluation. Machine Learning 68, 235–265 (2007) 36. Settles, B.: Active Learning. Morgan & Claypool Publishers (2012) 37. Settles, B., Craven, M.: An Analysis of Active Learning Strategies for Sequence Labeling Tasks. In: Proceedings of the Conference on Empirical Methods in Natural Language Processing. pp. 1070–1079. Association for Computational Linguistics (2008) 38. Shao, J., Wang, Q., Liu, F.: Learning to Sample: An Active Learning Framework. IEEE International Conference on Data Mining (ICDM) pp. 538–547 (2019) 39. Trittenbach, H., Englhardt, A., Böhm, K.: An overview and a benchmark of active learning for one-class classification. CoRR abs/1808.04759 (2018) 40. Watkins, C.J.C.H., Dayan, P.: Q-learning. Machine Learning 8(3), 279–292 (1992) 41. Yang, Y., Loog, M.: A benchmark and comparison of active learning for logistic regression. Pattern Recognition 83, 401–415 (2018)