Dual Active Learning for Both Model and Data Selection

1 Introduction

Labeling a large number of examples for model training is expensive in many real applications. Active learning (AL) [Settles, 2009] is a common approach to reduce the labeling cost. It usually requires a target model to evaluate the unlabeled data, and tries to select the most informative instances for querying their labels from the oracle.

A common assumption in the AL literature is that the target model is given as a prior. However, due to the lack of knowledge of the task, one can hardly determine the best model before querying in practice. A naive solution for active learning is simply applying a commonly used model for data selection.

∗This research was supported by the National Key R&D Program of China (2020AAA0107000), NSFC (62076128) and the China University S&T Innovation Plan Guided by the Ministry of Education. Sheng-Jun Huang is the corresponding author.

Unfortunately, this simple method will significantly jeopardize the performance of AL. It has been reported that, if applying different models for data evaluation and task learning, AL tends to be noneffective (i.e., comparable to the random strategy) [Lowell et al., 2019].

One possible remedy is introducing the model search (i.e., model selection) [Elshawi et al., 2019] to active learning to discover the applicable target model [Sugiyama and Rubens, 2008; Ali et al., 2014; Geifman and El-Yaniv, 2019]. However, most of existing works simply conduct data querying and model selection separately, they neglect the vulnerability of either of these two parts in such a challenging setting. Specifically, i) The distribution of the labeled data is skewed with the active querying, the model evaluation on the training set can be highly biased. ii) The target model varies during the AL process due to the model search. Greedily sampling with the winner model in the current iteration could be myopic. iii) Model search is usually time-consuming. It is impractical to perform model selection after each query, which will seriously affect the labeling efficiency. Although Ali et al. [2014] try to refrain from the first problem by maintaining an unbiased validation set by random sampling, this simple strategy may lead to extra labeling cost. As a result, it is still a challenging problem to reach the optimal performance with least cost when the target model prior is unavailable.

In this paper, we propose a novel DUal Active Learning (DUAL) framework to cope with the practical challenges by simultaneously performing model search and data selection. It well addresses all the concerns raised above, and deeply exploits the characteristics of both active querying and Combined Algorithm Selection and Hyperparameter optimization (CASH) [Thornton et al., 2013] to improve the final performance. Specifically, we propose an effective CASH method to search model configurations (i.e., algorithm and hyperparameters) along with the data querying process. It is equipped with the truncated importance sampling and a successive function to better accommodate to the framework. The former ameliorates the evaluation bias on the skewed labeled set, and the latter dramatically lowers the computational complexity of the algorithm. Based on the results of CASH, an effective active data querying strategy is proposed. It on one hand tries to help CASH identify the models with high potential to achieve the best performance by selecting the most discriminative examples, and on the other hand queries informative instances to accelerate the convergence of winner models of CASH. Consequently, the performance on the given task will be significantly improved with a few queries. The experimental results on 12 openML datasets demonstrate the superiority of the proposed framework.

2 RelatedWork

Active learning has been extensively studied in many tasks with expensive labeling cost, such as multi-label learning [Huang et al., 2017], multi-modality learning [Gao et al., 2018], deep learning [Shui et al., 2020], and so on. Many criteria are proposed to evaluate the informativeness of unlabeled data. There are mainly two groups of methods, namely uncertainty-based [Yan and Huang, 2018; Kirsch et al., 2019] and representativeness-based [Sener and Savarese, 2018; Li et al., 2020a]. The former prefers the uncertain data to the target model, while the latter favors the examples which can represent most patterns in the dataset. It has also been reported that a mixture of multiple criteria can usually achieve a better performance [Du et al., 2015; Huang and Chen, 2016; Tang and Huang, 2019]. Recently, several works are proposed to learn a query strategy rather than designing one heuristically [Konyushkova et al., 2017; Casanova et al., 2020]. Most of these works require the target model prior, which can hardly be satisfied in practice.

CASH [Thornton et al., 2013] and Neural Architecture Search (NAS) [Elsken et al., 2019] are popular topics in automatic machine learning [Elshawi et al., 2019]. The former mainly focuses on the traditional models, while the latter considers deep models, which typically lead to much higher cost for model evaluation. In this paper, we mainly consider the CASH setting. CASH methods can be roughly divided into black-box optimization methods and multi-fidelity optimization methods. The former is mainly implemented by Bayesian optimization [Hutter et al., 2011; Bergstra et al., 2011; Falkner et al., 2018], and the latter tries to dynamically allocate time resource to different configurations, which is usually implemented by bandit algorithms [Jamieson and Talwalkar, 2016; Li et al., 2017; Hu et al., 2019; Huang et al., 2020]. All these methods require an unbiased evaluation, such information may not be directly obtained in active learning framework.

Recently, several works try to combine the active learning and model selection for better performance. However, they are significantly different from our work. Specifically, ALMS [Ali et al., 2014] queries points for either model training or model selection. If the maximum score of all unlabeled data for model training is higher than model selection, a point will be selected by the expectation of improvements of the candidate models, and added to the training set. Otherwise, a randomly selected point will be added to the validation set for model selection. However, the algorithm performs leave-2out cross-validation to calculate the expected model improvement. It could be extremely expensive when the number of candidate models and unlabeled data are large, which limits its practicability. Moreover, the method maintains an unbiased validation set for model selection by random sampling. It may lower the utilization of the labeling cost.

Geifman and El-Yaniv [2019] propose Active-iNAS to search for the proper network architecture along with the AL process. It is different from DUAL with the following aspects. Firstly, the authors apply off-the-shelf data selection methods to query data based on the winner architecture searched by NAS. The query strategy does not consider the model selection. While in our approach, the data querying and CASH are well supported by each other. Secondly, the authors believe that the model capacity should monotonically increase with the size of labeled data. They neglect the characteristics of the dataset. While in our approach, the search space will be adjusted accordingly for different tasks. Lastly, they focus on NAS while we consider the CASH problem.

3 The Proposed Framework

We denote the dataset with n instances by D, which includes a small labeled set L = {(xi, yi)}nl i=1 with nl instances, and a large unlabeled set U = {xi}nl+nu i=nl+1 with nu instances, where nl ≪ nu and n = nl + nu. Let A = {A1 , . . . , AK } be the set of candidate algorithms (e.g., SVM, decision tree, etc.). The corresponding hyperparameter space of Aj is Λj . A configuration Ajλ is a specific algorithm with hyperparameters λ where Aj ∈ A, λ ∈ Λj . The objective of CASH is searching for the best configuration based on a quality metric V (·) (e.g., the cross-validation accuracy), which can be formulated as

3.1 Model Selection

CASH module responses for discovering the best model configurations for the current task. One challenge here is the distribution of labeled data is not identical to the test distribution due to the active querying, while the model evaluation usually requires an unbiased estimation of the performance for an accurate selection. For this reason, directly conducting cross validation on the labeled set may be suboptimal.

To cope with this problem, we employ the importance sampling [Tokdar and Kass, 2010] to alleviate the bias of evaluation. As discussed in [Sugiyama et al., 2007], the importance weighted validation error is an unbiased estimation of generalization error.

where pq and pd are the distributions of queried data and the whole dataset, ℓ(Ajλ , xi) is the loss of the trained model Ajλ on example xi.

In order to get the importance weights of the validation data (sampled randomly from the labeled set), inspired by the recent works [Zhang et al., 2018], we train a domain discriminator to distinguish the data sampled from labeled set and data pool. The objective of the discriminator is

By setting the partial derivative to zero as in [Goodfellow et al., 2014], the optimal D∗ can be represented by pq and pd. In this way, the importance weights w for the validation data can be approximated by D∗

However, sometimes the discriminator D may output a very small value. It will lead to an extremely large importance weight to overemphasize a specific example and may mislead the model selection. Here we further apply the truncated importance sampling [Ionides, 2008] to mitigate this practical problem. Let w′ = w ∧ τ be the truncated importance weight, where ∧ is the minimum of w and τ, and τ is a hyperparameter. Next, by applying the results from [Ionides, 2008], we show that the validation error with truncated importance weights is consistent with the generalization error.

Theorem 1. Supposing that ℓ(Ajλ , xi) < ∞ and pd(xi)ℓ(Ajλ , xi) = 0 whenever pq(xi) = 0. Denote w′i = w′ (xi), the bias and variance of 1 nl ∑nl i=1 w′i ℓ(Ajλ , xi) will converge to zero, as long as τ →∞ and τ/nl → 0.

Proof. The bias is calculated as

Since ∣∣∣ℓ(Ajλ , x) (τpq(x) -pd(x))∣∣∣ ≤ ∣∣∣ℓ(Ajλ , x)pd(x)∣∣∣, the bias → 0 when τ → ∞. To bound the variance,

Since

when τ/nl → 0, the variance → 0.

Letting V (Ajλ ,L) be the truncated importance weighted performance on validation set, it is a consistent estimation of the generalization performance. In this case, the off-theshelf CASH method for model search can be applied. However, simply performing CASH after each query is unacceptable due to the computational complexity. To this end, inspired by [Li et al., 2020b], we further propose a successiveSMAC method to better accommodate the problem setting. It is based the SMAC [Hutter et al., 2011] method, with adopting an elimination function to filter less effective candidates algorithms along with the query process for efficiency.

Specifically, we maintain a set of well-performed candidate algorithms AG = {A1 , . . . ,Ag },AG ⊆ A, and perform SMAC for each of them separately with the identical time budget after each query. At iteration t, the configuration Ajλ∗t with the highest importance weighted validation performance rj t (e.g., accuracy) for each algorithm j in the candidate set will be returned. In this way, each algorithm j has a history performance vector Rj = {rj1 , . . . , rj t }. In order to remove those less effective algorithms according to the past performances, we calculate the mean and standard deviation of the performances in the last C iterations {rj t , rj t-1 , . . . , rj t-C }, which are denoted by mjt , vj t . Then we remove the less effective algorithms, which are defined as {Aj |mjt + vj t <mkt - vk t , j, k ∈ [1, . . . , g], k ̸= j}.

3.2 Data Selection

To maximize the performance on the target task, we believe that the active querying strategy should on one hand help CASH promptly discover the high potential algorithms for the current task, and on the other hand try to improve the winner model to accelerate its convergence. We term these two characteristics as "exploration" and "exploitation", respectively. By well balancing these two aspects, we expect that the size of candidate algorithms should decrease rapidly at early stage. After the best algorithm is identified, the data selection tends to focus more on improving the winner model.

For the exploration, we try to query examples to help CASH in model search. Before we elaborate the selection criterion, we first introduce a lemma to explain our motivation. Remember that we search for the best configuration of each candidate algorithm after each query, and we would like to discover the best algorithmwith least iterations. If we regard the performance {rj t }Tt=1 as reward, it is accord with the nonstochastic multi-armed bandit problem [Jamieson and Talwalkar, 2016], where each algorithm is an arm, each arm will be pulled once time at each iteration, the received rewards are non-stochastic (i.e., not sampled i.i.d from a probability distribution supported on [0, 1]). The goal is to identify the best armwith least trials.

Formally, define ejt = max{rj b |b = 1, . . . , t}, we can have that {ejt } is bounded and non-decreasing. Assume limk→∞ejk = ν j , and | limk→∞ejk - ejt | ≤ γj(t), limt→∞γj(t) = 0. We introduce the following lemma to deduce our data querying strategy.

Lemma 1. [Jamieson and Talwalkar, 2016] Assume ν 1 > ν 2 ≥ · · · ≥ ν g . Define γj -1 (α) = min{t ∈ N : γj(t) ≤ α}. If tj > γj -1 ( ν 1-ν j 2 ) and t1 > γ1-1 ( ν 1-ν j 2 ), then

The lemma indicates that when the assumptions are met, it is guaranteed that e1t1 > ejtj with ν 1 ≥ ν j . On the contrary, if we do not know which ν is bigger, comparing e1t1 and ejtj suffices to identify, which can be proofed by contradiction. Moreover, the larger the gap between algorithms ν 1 -ν j , the earlier we can distinguish the better one. Since the distribution of training examples is controlled by the data querying strategy, it is reasonable to select the instances which lead to significant divergence of candidate algorithms. For this reason, we query the data based on the disagreement between the promising configurations of the candidates AG, in order to make the superior and inferior algorithms distinguishable as soon as possible. The implementation is deferred to Eq. (9).

For the exploitation, we directly utilize the winner model returned by CASH, and query by uncertainty to accelerate its convergence. Formally, Supposing that there are g candidate algorithms at iteration t, and r1 t > · · · > rg t , we have the following selection criterion S(x) for data x

where i ranges over all possible labels, PA1λ∗t (yi|x) is the probability prediction of model trained with configuration A1λ∗t for example x on class i, β is the tradeoff, and

where I(·) is the indicator function, Ajλ∗t (x) is the prediction of the configuration of data x. The first term of S(·) is the prediction entropy of data according to the winner model, the second term is the vote entropy for estimating the disagreement between the best configurations of each candidate algorithm in AG. We summarize the proposed DUAL framework in Algorithm 1.

4 Experiment

4.1 Empirical Settings

We compare the proposed DUAL method with the following approaches in the experiments.

• Coreset: [Sener and Savarese, 2018] A representativeness-based method which selects the data point to best cover the unlabeled pool.
• QUIRE: [Huang et al., 2014] A query strategy that considers both uncertainty and representativeness in AL.
• Entropy: An uncertainty-based method to select the data point with the highest entropy value according to the prediction of the target model.
• Random: Randomly selecting examples to query.
• CASH: Performing successive CASH for model search, along with random querying.
• ALMS: [Ali et al., 2014] Selecting model by crossvalidating each candidate model, and querying data by expected model improvement.
• Active-iNAS: [Geifman and El-Yaniv, 2019] Querying examples by entropy, and searching models from simple to complex gradually.

Algorithm 1 The DUAL Algorithm

Input: Candidate algorithms AG, performance history Rj , iteration t, truncated threshold τ, tradeoff parameter β, unlabeled pool U, labeled set L.

Output: Selected data xq, best configuration Abλ∗t .

• 1: Ltr,Lval ← split(L) ▷ Split labeled data into training set Ltr and validation set Lval.
• 2: D ← trainD(Ltr, L ∪ U) ▷ Train domain discriminator D from labeled data and the whole dataset.
• 3: yv ← predict(D, Lval)
• 4: w′v ← ( 1 yv - 1) ∧ τ ▷ Get truncated importance weights.
• 5: for j ← 1 to g do ▷ Perform CASH for candidates.
• 6: rj t , Ajλ∗t ← SMAC(Aj , Λj , Ltr , Lval , w′v , V )
• 7: Rj ←Rj ∪ rj t
• 8: mjt ←mean(Rj ,C); vj t ← var(Rj ,C) ▷ Calculate mjt and vj t with the last C elements of Rj .

9: end for

• 10: b ← argmaxj(rj t )
• 11: B ← {Aj |mjt +vj t <mkt -vk t , j, k ∈ [1, . . . , g], k ̸= j}
• 12: AG ←AG \ B ▷ Remove less effective algorithms.
• 13: Z ← {S(xi)|xi ∈ U} ▷ Scoring unlabeled data with Eq. (9).
• 14: q ← argmaxi(Z)

• 16: Update and test model with configuration Abλ∗t

Note that the last 3 methods will conduct model search after each query, and DUAL, CASH, Active-iNAS will use the model search method proposed in this paper for better comparison. ALMS requires a given discrete candidate set for model selection, which will be specified latter. The others employ a fixed target model for data selection, which is searched on the initially labeled set.

We conduct our experiments on 12 openML [Vanschoren et al., 2013] multiclass classification datasets. The basic information is summarized at Table 1. For each case, we randomly sample 40% data as test set, 5% data as initially labeled set, and the rest is treated as the unlabeled pool. The data split is repeated for 10 times with different random seeds.

For the initial candidate algorithms in CASH module, we employ 12 commonly used models: Adaboost, Random Forest, Libsvm SVC, SGD, Extra Trees, Decision Tree, K Nearest Neighbors, Passive Aggressive, Gradient Boosting, LDA, QDA, Multi Layer Perceptron. We use the default implementation of auto-sklearn [Feurer et al., 2015] for model search.

ALMS can only work with a set of discrete candidate models. We set the candidate models as the default model of each algorithm in A (i.e., the model with default parameters in scikit-learn). Note that even with this small set, it is still very time-consuming, and can hardly be performed in the datasets with more than 2,000 examples. Thus we only report its results in the relative small datasets.

For Active-iNAS, it requires the complexity rank of candidate algorithms as prior. However, it is hard to compare the complexity of traditional models. To compare with this method, we empirically set the order of candidate algorithms, which is deferred to the supplementary material. Note that once the method selects a complex model, it can never return to a simple one.

For the hyperparameters in our method, we follow the suggestion in [Ionides, 2008] to set the truncated threshold as τ = √m, where m is the number of validation data. For the tradeoff β, we believe that the primary task of DUAL at early stage is to explore the applicable algorithms, the improvement of winner models should be preferred later. To achieve this goal, we set the parameter empirically as β = 1/g, since the number of candidate algorithms g will decrease along with the query process. Note that the results of parameter sensitivity in the supplementary material indicate that our method is insensitive to β.

4.2 Performance Comparison

We plot the averaged learning curves in Fig. 1. Some legends of the figures are omitted to avoid the occlusion, the figures in the same line have the same legends. It can be observed that, our proposed DUAL method can outperform the others significantly in most cases, which demonstrates its effectiveness. The CASH method with random querying can usually achieve the second best. This phenomenon indicates that an effective target model may bring more benefits than the query strategy, which implicitly reveals the practicability of the proposed framework, since the target model is hard to be decided as a prior in real tasks. ALMS does not perform well. Note that its computational complexity immensely limits the size of candidate models. Due to this defect, the best target model can hardly fall into the candidate set, which impairs the performance. Active-iNAS searches model from the simplest one initially, thus it has a different initial point with the other methods. It works well on some datasets but fails on the others. Note that this method heavily relies on the intuition of the increasing model complexity, which may not be suitable for every dataset. The rest query strategies with the fixed model perform diversely across datasets. It may be caused by the varying target models, which are searched based on the limited initially labeled data. This result also implies the importance of simultaneously considering the model and data selection in active learning, because a query strategy can perform inconsistently with different target models.

4.3 Ablation Study

To further validate the effectiveness of each component in DUAL, we conduct the ablation studies. Due to the space limitation, we report the mean values of the accuracy and number of candidate algorithms along with the querying process on 12 openML datasets instead of plotting them. 'w/o active' means eliminating the active querying part, and 'succe.' represents the successive function in model search. The results are reported in Table 2.

we can observe that DUAL significantly outperforms the methods without active sampling in both effectiveness and efficiency, which demonstrates the superiority of the data selection strategy on both exploration and exploitation aspects. Also, we find that the two ablation methods have comparable performances, but the one with successive function is much faster than another. It reveals that the function could accelerate the model search significantly without impairing the performance. These results on one hand show that the data querying strategy is helpful for both model search and accuracy improvement, on the other hand validate the efficiency of the successive function.

5 Conclusion

In this paper, we propose a novel dual active learning framework DUAL to tackle with the lack of target model prior problem by simultaneously performing model and data selection. On one hand, we propose an efficient CASH method with the truncated importance sampling to search for the best model configuration based on the skewed labeled set. On the other hand, we propose a data querying strategy to adaptively help CASH in model search or improve the winner models by active sampling. Both parts are well supported by each other to improve the final accuracy. Experimental results on 12 openML datasets demonstrate the effectiveness and practicability of the proposed framework. In the future, we would like to introduce the meta learning to deal with the scarcity of prior knowledge problem.