Active learning aims to reduce annotation cost by predicting 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 selection strategies are hand-designed, and it has become clear that there is no best active learning strategy that consistently outperforms all others in all applications. This has motivated research into meta-learning algorithms for “learning how to actively learn”. In this paper, we compare 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.
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 process 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}i=l+1 is the set of n unlabelled examples. In this framework, active learning is an iterative process that continues until a labelling budget is exhausted or a pre-defined performance 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 corresponding class y?, and the pair (x?, y?) is added to L. The new learning set is 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
literature [
The active learning field comes from a parallel between active educational methods and machine learning theory. The learner is from now a statistical model and not a student. The interactions between the student and the teacher correspond 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 [
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
applications. 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 [
QBDc Densityd
OERe
[
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 [
Motivated by the success of methods that combine predictors, the first AL
algorithms within this paradigm were designed to combine traditional AL
strategies with bandit algorithms [
Within the meta-learning framework, some other algorithms have been
developed to learn from scratch an AL strategy on multiple source datasets and
transfer it to new target datasets [
From the state of the art, it appears that meta-learned AL strategies can outperform 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.
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 [
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 [
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 describes 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:
Qt+1(s, a) = (1 − αt(s, a))Qt(s, a) + αt(s, a) r + γ max Qt(s0, a0) ,
a0∈A
(1)
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
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? [
The goal of a reinforcement learning agent is to maximize the rewards received 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
In the Q-Learning algorithm, if the state-action table is implemented as a twoinput 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:
L(s, a, r, s0, θ) = r + γ max Q(s0, a0; θ) − Q(s, a; θ)
a0∈A However, this poses an obvious problem: updating the parameters leads to updating 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 [
(2) r + γ max Q(s0, a0; θ−) − Q(s, a; θ) a0∈A 2 where θ− is the vector of the target network parameters. The second novelty 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.
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
overestimation bias. It has indeed been empirically shown that Deep Q-Learning as
presented 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 [
a0∈A A maximum priority is assigned to each new experience, so that all the experiences 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 [
Pmρiβ β , k=1 ρk
with ρi = δi + e, 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.
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 g(xi, Lt) =
X dist(xi, xj ), g(xi, Ut) =
X dist(xi, xj ), (7) 1 |Lt| xj∈Lt
1 |Ut| 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.
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 Section 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 minibatch 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 examples
Simulation of 10 active learning episodes
Experience replay memory of size 10 000
In this section, we introduce our protocol of the comparative experimental study we conducted. 3.1
To learn the strategy, we used the same code6, the same hyperparameters and
the same datasets as those used in [
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 parameters θ are changed as follows: θ− ← (1−TARGET COPY FACTOR)·θ−+TARGET COPY FACTOR·θ. 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
Dataset
|D| |Y| #num #cat maj (%) min (%)
a given model. Several benchmarks conducted on numerous datasets have
highlighted the fact that margin sampling is the best heuristic strategy for logistic
regression (LR) and random forest (RF) [
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), x∈U (8) 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 [
The datasets were selected so as to have a high diversity according to the following 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 [
Dataset
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
literature. 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 [
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
[
The results of our experimental study are given in Table 5. The mean ALC obtained 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 corresponds 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 differences 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 banana bank-marketing-full climate-simulation eeg-eye-state hiva ibn-sina magic musk nomao orange-fraud ozone-onehr qsar-biodegradation seismic-bumps skin-segmentation statlog-german-credit thoracic-surgery thyroid-hypothyroid wilt zebra Mean win/tie/loss
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 [
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 [
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 [
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 [
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 [
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 [
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
[
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 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 [
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 [
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 [
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 [