Active learning provides a solution for annotating huge pools of data efficiently to use it for mining and business analytics. Therefore, it reduces the number of instances that have to be annotated by an expert to the most informative ones. A common approach is to use uncertainty sampling in combination with a support vector machine (SVM). Some papers argue that uncertainty sampling performs badly due to missing exploration, others report good results using an SVM. This paper investigates whether uncertainty sampling is able to explore the data space due to the kernel trick used by the SVMs. Hence, we evaluate this on multiple synthetic and real datasets and the effects of parameter tuning and kernel selection for different evaluation criteria.
inside the decision area, whereupon US would readily consider them. Since the behavior of an SVM depends on the chosen kernel and the SVMs hyperparameters, we investigate the dependencies between the exploratory capabilities of US with SVMs and the chosen kernel, also w.r.t. its tuning.
current decision boundary labeled instances
unlabeled candidates
The following section briefly summarizes the background and related work, followed by a description of the experimental framework in section 3 and the conducted experiments in section 4. Finally, we provide a discussion and conclude our results. 2
Active learning (AL) is a special area of machine learning, more precisely semi-supervised learning. A pool-based
active learner successively selects and removes an instance x ∈ U from a large pool of unlabeled instances U .
An expert annotates this instance with a class label y. This information is added to the labeled set of instances
L ← L ∪ {(x, y)} which forms the training basis for a classifier [
Different strategies exist to determine which instances are chosen. A simple but naive approach is selecting instances at random, which has the benefit of potentially sampling a well distributed set of instances. A common approach is called uncertainty sampling (US), its underlying rationale being that the learner should select those instances the classifier is most uncertain about. For SVMs this might be the distance to the decision boundary (simple margin [23]), probabilistic classifiers might use the posterior estimates.
Uncertainty sampling is solely focused on exploitation of the data [4], i.e. it acquires the labels of instances
that are useful to refining the decision boundary already assessed by the classifier. If the decision boundary
proposed by the model is close to the actual decision boundary for the data, this process of refinement is likely
to perform well. However, if there are unexplored regions in the data space with wrongly predicted labels far
from the decision boundary, they will not be found. One approach to overcome this problem is to alternate
between US for exploitation and an exploration component like random sampling [
A Support Vector Machine (SVM) is a supervised learning model performing binary classification in a
kernelinduced feature space [
In this context, the goal of an SVM is to achieve an optimal separation in the kernel-induced space. As the
hyperplane is gradually ’refined’, exploration becomes less and less important. Indeed, Tong and Koller [23]
assume a quick reduction of the version space size using US since the current hypothesis of an SVM is roughly
in the center of the version space. Hence, choosing an instance near the center should approximately split the
version space in halves [
In our experiments, we use pool-based active learning as described in Sec. 2 and stop learning after 50 label acquisitions (budget B = 50). For uncertainty sampling (US), we use the most commonly used simple margin (sm) implementation for SVMs by [23]. To compare the exploratory behavior, we additionally use a random sampler with each classifier (SVM+kernel+tuning). Since an SVM requires at least one instance of each of the two classes for training the labeled set L set was initialized accordingly.
In Alg. 1, we show our framework to evaluate our active learning experiments. For a given data model M,
we perform US using SVMs with different kernels as defined in [
To tune the hyperparameters of each classifier (SVM+kernel), we perform a grid search on a separate tuning
set Dtune. This is generated by selecting B labeled instances from the data model M, to optimize the classifier
according to the final number of labels. The labels in the Dtune set are used solely for tuning and validating
the hyperparameters. To avoid a bias of the model due to overfitting, the labels in Dtune are not used in the
training or testing of the active learner. Based on the hyperparameter optimization, we select for each kernel (1)
the best parameter setting and (2) a parameter setting that achieved medium results. Surely, the classification
performance will probably decrease by selecting a non-optimal parameter setting. Here, we want to investigate
the influence of the parameter choice for doing exploitation. Hence, we get two different classifiers for each kernel
Ck,t. The search space of the hyperparameter optimization is given in Tab. 1: γ denotes the kernel coefficient,
C is the penalty parameter of the error term of the SVM, d is the degree of the polynomial kernel and coef0 is
the independent term of the kernel function [
γ C d coef0 |Dtest| x∈Dtest
xml∈inL ||x − xl||2
The experiments are conducted based on a set of 200 different seeds that were used for generating resp. splitting the datasets. For each seed, we generate a test set Dtest which we use for evaluation and a training set U consisting of solely unlabeled instances. As mentioned above, the labeled set L is initialized with one instance from each of the two classes. Then, the active learner chooses B instances successively to be labeled. The unlabeled instance is removed from U and added (with the corresponding label) to L.
As the model M is not explicitly given for the real world datasets, we split B instances from the real datasets for hyperparameter tuning. Then, half of the remaining instances is used for testing, the other half for training.
In the evaluation step, we focus on two aspects: (1) the classifier’s performance, and (2) the amount of exploration. To address the classifier’s performance, we determine the hold-out accuracy on the test set Dtest for each budget step resulting in a learning curve for each active learner and each classifier. The exploration is addressed by a score motivated by [6]. Here, we determine the average euclidean distance from each instance x ∈ Dtest to the nearest labeled instance xl ∈ L (see Eq. 1). This score (avg. min. distance) is determined after each acquisition, which again results in a learning curve. A low value indicates a good coverage of the data space, high values indicate that labeled instances are far away. Per definition, this score is decreasing over time, as more labeled instances are added subsequently to the labeled set.
Regarding the expected results of the experiments, it is difficult to make predictions as to the differences in performance and exploration between the different kernel functions. Generally, it is to be expected that the rbf and laplacian kernel will show a similar but not identical behavior based on their similarity. Among the artifical datasets the ones referred to as ’Three Cluster Datasets’ (Sec. 4.1) are designed with an expected result in mind: (1) Data: data model M, seeds S, budget B = 50, SVM C, active method US begin for k ∈ {RBF, Poly, Sigm, Laplace} do for t ∈ {best, middle} do
Dtune ← getLInst(M, B); pk,t ← gridSearch(C(k), Dtune, t); Ck,t ← initializeClassifier(C(k), pk,t); for s ∈ S do
Dtest ← getLInst(M, 350, s); L ← getOneLInstPerClass(M, s); U ← getUInst(M, 350, s); for i ∈ {1, . . . , B} do
C∗ ← trainClassifier(C, L); x∗ ← selectInst(US, U , C∗); y∗ ← getLabel(M, x∗); end
U ← U \ {x∗}; L ← L ∪ {(x∗, y∗)}; evaluate(C∗, L, Dtest) end end end end
since one of the three clusters is unknown to the active learner at the beginning because only two labels are given in the initial L set, we expect that learners using US with a linear classifier will find this cluster very late. However, as these clusters are generated with Gaussian distributions, it is likely that both the rbf and laplacian kernel will perfom better by using this implicit information. 4
In the experimental evaluation, we use 10 different data models resp. datasets to investigate the exploratory
capabilities of uncertainty sampling and SVMs (see Fig. 2a-2f). Therefore, we used a cluster system running the
NeuroDebian system [
The first model consists of three Gaussian clusters, two clusters of class one and the other cluster of the second class. To get more expressive results, we use three different standard deviations (equal for all clusters) to have well separated clusters as well as overlapping ones (high standard deviation (overlapping): gaussian 2dp0, medium: gaussian 2dp1, low (well-separated): gaussian 2dp2). Since 2 of the 3 clusters are sampled in the initialization step, the learner’s task is to discover the remaining cluster in order to perform well.
If a learner-classifier combination was able to find the remaining cluster is summarized in Tab. 2. In each cell, we show the percentage that the active learner found the unknown cluster within the first B label acquisitions across all 200 trials. Every classifier has a specific kernel and a set of hyperparameters coming from the grid search tuning. Here, we choose the best performing hyperparameters (best) as well as non-optimal ones (middle).
Choosing the best set of parameters, the SVMs with a laplacian and an rbf kernel are able to discover the remaining cluster reliably, whereas the discovery rate of those using a polynomial or sigmoid kernel is less than 25%. Applying not-optimal parameters, the detection rate of an SVM with an rbf decreases, but the rate of polynomial SVMs increases to approx. 50% and of sigmoid SVMs to higher than 80%. This exploratory behavior is also indicated by the average minimal distance score in Fig. 3b, 3d. Here, a high discovery rate correlates with a low value for the avg. min. distance. In this specific dataset, there is a clear correlation of the exploration score, resp. the discovery rate, and the learning curves in Fig. 3a. The previously mentioned expectation of the
quantiles_2c_2f 3 2 1 0 1 2 3 4 (b) Example of the ’quantiles’ dataset
Gaussian_2d_preset_0 5 10
(b) Avg. min. dist curve with best parameters 10
(d) Avg. min. dist curve with middle parameters 10 10 10
best middle rbf and laplacian kernel learners to perform better based on the Gaussian distributions of the data was shown to be correct. The accuracy curves of the random learners can also be used to find out, if the tuned SVM is able to fit the decision boundary. Using the best hyperparameters, all random active learners achieve a performance higher than 0.9 accuracy which means that these are generally able to perform well. Here, a lack of exploration also leads to bad performance.
Using non-optimal parameters, the discovery rate might increase, but the ability to find an appropriate boundary decreases (except for the laplacian kernel), which is not surprising. Hence, an increase of exploration by changing the kernel does not necessarily increase the accuracy of a classifier, as the classifier is not able anymore to fit the decision boundary accordingly. Interestingly, uncertainty sampling now performs better with non-optimal hyperparameters compared to random in general. This observation could be critical to active learning research: In active learning research, the main focus is to compare different active learning algorithms. Hence, they fix a classifier and a hyperparameter setting (however this is determined) and compare the active methods with each other. This experiment shows that random and US methods using the same SVM with the same kernel can change their order by just varying their hyperparameters.
Note that these experiments are based on normal distributions. We expect circular shapes which might favors the performance of rbf or laplace kernels. Hence, we perform more experiments using less structured data. 4.2
The results of the synthetic datasets are given in Fig. 4a-4b and Fig. 5a-5b. All three datasets are provided by
the scikit-learn library [
In the exemplary Fig. 4a-4b, a fast decreasing avg. min. distance (high exploration) in the early steps indicates a fast improvement in terms of accuracy. This tendency is also visible on the other datasets which we provide at our companion website1. This is also indicated by the observation that the random sampler is similar or better in the early steps (except for sigmoid on Quantiles) but beaten later by the uncertainty sampling (simple margin sm) method. This has also been shown by various other authors that an exploration phase in the beginning is beneficial.
Finding the best SVM+AL combination remains difficult: On Quantiles, the polynomial SVM in combination with simple margin is superior. On Classification and Moons, the winner is the laplacian SVM + simple margin. 4.3
The real-world datasets are chosen from the UCI machine learning repository [1] and include the ’Abalone’, ’Haberman’, ’Mammo’ and ’Vertebral’. Their characteristics are summarized in Tab. 3. We transformed nominal attributes into multiple binary attributes, numerical attributes were normalized to [0, 1].
On these datasets, we choose to show the learning curves of the well-tuned SVMs in Fig. 6a-6d as one would do this in practice. The winning kernel differs very much across the datasets. On Abalone, the laplacian kernel was superior; on Mammo it was the polynomial kernel and on Haberman and Vertebral, the rbf kernel was best.
On Mammo and Vertebral, we observe the same situation as in Sec. 4.2: random sampling outperforms simple margin in the early learning stage and the latter catches up or surpasses random sampling later on. The results on Abalone in Fig. 6a show that the laplacian kernel is beneficial. Even more interesting is that random outperforms
Abalone Haberman Mammo Vertebral the simple margin strategy for every other kernel. The same appears on Haberman in Fig. 6c. Only the laplacian kernel single margin strategy outperforms its random competitor, but the performance of both are far less then all others.
To summarize, there are quite a lot of cases where a solely exploratory strategy (random) outperforms the uncertainty sampling approach which was combined with a pre-tuned SVM to potentially add some exploration. 5
In this paper, we investigated the exploratory capabilities of uncertainty sampling (US) in combination with different support vector machines (SVMs). We described an evaluation framework and tested multiple synthetic and real datasets using this framework. Furthermore, we proposed to use the average minimum distance as an indicator for exploration.
Although SVM and US are seen as a promising combination for active learning, it does not mitigate the lack of exploration to which the inferior performance of US is accredited to. The exploiting behavior of US in the kernel-induced space ends up looking similar to exploratory behavior in the feature space, yet it does not perform actual exploration in a strict sense.
If non-optimal SVM hyperparameters are used, the exploitation that US performs in the kernel-induced space becomes less precise which can lead to the behavior showing more exploratory characteristics. However, in a strict sense this is more a misbehavior of the exploitation than real exploration of the data space. Hence, we conclude that merely choosing a SVM to perform US does not replace a dedicated exploratory component.
The experimental results affirm that exploration in the beginning of the active learning process is indeed beneficial to the classification performance. Furthermore, they indicate that the hyperparameter tuning is critical to classification performance. We propose to validate multiple hyperparameters in an evaluation of active methods to get rid of the bias induced.
We thank Michael Hanke and Alex Waite for support by providing the cluster for our computations and Pawel Matuszyk for the discussions on that topic. [1] Arthur Asuncion and David J. Newman. UCI machine learning repository, 2015. [2] Christian Beyer, Georg Krempl, and Vincent Lemaire. How to select information that matters: A comparative study on active learning strategies for classification. In Proc. of the 15th Int. Conf. on Knowledge Technologies and Data-Driven Business (i-KNOW 2015). ACM, 2015. [3] Wenbin Cai, Ya Zhang, Siyuan Zhou, Wenquan Wang, Chris Ding, and Xiao Gu. Active learning for support vector machines with maximum model change. In Machine Learning and Knowledge Discovery in Databases, pages 211–226. Springer, 2014. [4] Gavin C Cawley. Baseline methods for active learning. In Active Learning and Experimental Design@
AISTATS, pages 47–57, 2011. [5] Nicolas Cebron. Aktives Lernen zur Klassifikation großer Datenmengen mittels Exploration und Spezialisierung. PhD thesis, 2008. [6] Gang Chen, Tian-jiang Wang, Li-yu Gong, and Perfecto Herrera. Multi-class support vector machine active learning for music annotation. International Journal of Innovative Computing, Information and Control, 6(3):921–930, 2010.