Active learning is a subfield of machine learning which allows to reduce the amount of data necessary to train a classifier. The training set is built in an iterative way such that only the most significant and informative data are used and labeled by an external person called oracle. It is furthermore possible to use active learning with the theory of belief functions in order to take erroneous labels due to the oracle's uncertainty and imprecision into account in order to limit their influence on the classifier's performance. In this article, we compare the classifier of the k nearest neighbours (kNN) to a variant based on belief functions from the theory of belief functions (EkNN), in a situation where some labels have been noised in order to model uncertain labels. We show that although the superiority of EkNN over kNN is not systematic, there are some interesting and modest results supporting the relevance of belief functions in active learning.
In supervised machine learning, the size of the training set, i.e. the number of
labeled examples, is often correlated to the performance of the learned model.
Although having access to large database is no longer dificult nowadays, labeling
the data remains an expensive task, especially when the application domain
requires some expertise. Active learning ofers a solution to this issue by reducing
the number of labeled examples and ensuring that data to be labeled is selected
by the model or a strategy [
In this paper, our contribution consists in the use of an evidential variant of the k nearest neighbours classifier which involves belief functions in active learning. More precisely, we compare this evidential classifier to the common k nearest neighbours in a context where the labels provided by the oracle are uncertain.
© 2021 for this paper by its authors. Use permitted under CC BY 4.0.
This article is organised as follow. First of all, we introduce active learning and belief functions in section 2. Our contribution is then described in section 3 and our experiments and results are presented in section 4. Finaly the last section 5 concludes this paper. 2
In this section, we first introduce some notions about active learning (section 2.1) before dealing with the theory of belief functions (section 2.2). 2.1
Active learning (AL) is a subfield of machine learning which allows to limit the
amount of training data to train a classiefir. Its specificity lies in the construction
step by step of a reduced training set, with a limited amount of information [
For a given classification problem, let us consider X ⊂ Rd, the set of samples described by d ∈ N∗ features and Y, the set of the diferent classes. The labeled and unlabeled samples are respectively gathered in L and U such that X = L ∪ U and L ∩ U = ∅. The aim is to label the minimum amount of data required by the model to reach a given performance or the best performance given a budget. The classifier first selects the sample x ∈ U whose contribution to the model is supposed to be the most significant before asking for its label to the oracle; this step is called a query. Once the label y ∈ Y of x is provided, the classifier learns it and updates its knowledge, moving x from U to L. Queries are formulated repeatedly in the same way until a certain stop criterion is satisfied. At the end of the complete learning process, it is highly probable that U still contains a lot of samples but it is a matter of little importance as the classifier does not need to learn the whole dataset to perform eficiently.
This strategy is known as the pool-based sampling [
There are several ways to select and to evaluate the relevance or the
“informativeness” of a sample. The utility measures defined by the active learning
strategies in the literature [
x∈U With yx(1) and yx(2) being respectively the most and the second most probable classes for x ∈ U according to the classifier. The idea is quite natural: if the diference between the probabilities – the margin – is small, then the classification of x would be considered as ambiguous; – the entropy sampling : the sample x∗H which maximises the entropy of Shannon is considered as the most uncertain and will be sent to the oracle: (2) (3) x∗H = arg max − x∈U
X P (y|x) log(P (y|x)) y∈C Unlike the previous methods, this approach considers every class and not only the most probable ones.
One can also notice that the uncertainty could be “divided” or viewed in two
distincts parts [
It is however important to notice that the uncertainty described in this section is related to the classifier and not to the oracle. The latter’s lack of knowledge and epistemic uncertainty might be modeled with the theory of belief functions introduced in the next section. 2.2
The theory of belief functions also known as theory of Dempster-Shafer is an ideal
tool for modeling uncertainty and imprecision [
Let us consider a set Θ called the frame of discernment, containing the elementary and exclusive hypotheses of a given problem. In the context of classification, it would be the set of classes, therefore: Θ = Y.
The theory is based on belief functions which are defined from 2 Θ to [
X m(X) = 1 X∈2Θ (4) A BBA allows to assign elementary belief on diferent combinations of hypothesis. For exemple, if we consider X = {θ1, θ2, θ3} ∈ 2Θ, then m(X) is the confidence assigned to θ1, θ2 and θ3 altogether and cannot be subdivided among the diferent sub-hypothesis {θ1}, {θ2} or {θ3}; thus, m(X) supports the veracity of X as a whole.
In particular, if m(∅) = 0, then the assumption of closed world is true, meaning that the frame of discernment is exhaustive. On the contrary, the assumption of open world prevails if m(∅) ̸= 0, which implies that unknown hypothesis exist and may not belong to Θ. In this article, the world will be supposed as closed.
The uncertainty about an hypothesis θ ∈ Θ is modeled by the value of the
BBA: the higher the BBA is (close to 1) and the more confidence there is in θ.
However, if the value of BBA is low (close to 0), it means that few evidences
support θ. The imprecision happens when the oracle hesitates between several
hypotheses. This phenomenon is modeled by non empty and non singleton values
of 2Θ and can be extended to the situation of total ignorance, in which case, the
entire belief is assigned to Θ in the following way: m(Θ) = 1 and m(X) = 0 for all
X ∈ 2Θ −{Θ}. In a such context, every hypothesis is possible. For example, let us
consider a classification problem of 10 classes so that Θ = Y = {θi | i ∈ J1, 10K}
and let us note A = {θ1, θ5, θ8} ∈ 2Θ. If, for a given sample x ∈ X , the oracle
believes that the class of x might be either θ1, θ5 or θ8 without being able to
determine which one is the most likely and without having evidences supporting
other classes, then a BBA mx : 2Θ → [
The core feature of the Dempster-Shafer’s theory is the conjunctive rule of combination of Dempster. It allows the combination of several BBA defined from the same frame of discernment. As a result, the hypotheses on which the BBA agree are enhanced. Let us consider l ∈ N∗, the BBAs (mi)i∈J1,lK defined on the same frame of discernment Θ will be combined into a single BBA m⊕: Even though each BBA mi respects the assumption of closed world, m⊕ might not. It is possible to normalise m⊕ in order to restore the closed world assump3
Active learning is a paradigm of machine learning which reduces the amount of
training data necessary to train the classifier. As uncertain oracle leads to errors
in the labeling task, by coupling AL and the theory of belief functions [
In this section, we present the evidential k nearest neighbours introduced for
the first time in [
The evidential k nearest neighbours classifier (EkNN) is a variant of the classical
k nearest neighbours (kNN) based on belief functions [
Let us consider x ∈ U and x˜ ∈ L, one of the k nearest neighbours of x according to the euclidian distance. It is possible to define a BBA mx,x˜ which supports the sole hypothesis that x and x˜ belong to the same class θ ∈ Θ. A such BBA must also deal with the distance between x and x˜: the closer they are and the stronger the belief is. Therefore, the BBA might be defined as follow: (6) (7) (8) tion:
This rule of combination might be useful in decisions’ rules. It is therefore possible to define classifiers based on belief functions as described in the next section. with α and γθ parameters and d(x, x˜) the Euclidean distance between x and x˜.
In the original paper [
The combination rule of Dempster is then applied among the BBA which support the same classes. For each class, we get the BBA (mx,(θ))θ∈Θ. Finally, the rule of combination is applied one more time among every BBA (mx,(θ))θ∈Θ and we get mx which aggregates every original BBA supporting diferent classes.
The decision rule is then the following: ∀x ∈ U y = arg max mx({θ})
θ∈Θ
In the context of active learning, it is necessary to take into account the time complexity of the training phase, as the classifier is updated after each query. In the implementation of EkNN used in this article, the training phase consists to store the training data, then, to compute the γθ parameters which take the value of the inverse of the mean distance between every pair of samples from the same class θ ∈ Θ. If the euclidian distance is used, then the number of features d will necessarily influence the time complexity. Let us consider nθ ∈ N∗, the number of samples whose class is θ. There are Nθ = nθ(nθ−1) unique couples 2 of samples, which is also the number of distances to be computed. So the time complexity to compute the mean distance of the class θ is in O((d + 1)Nθ). The global time complexity of the training phase (including every class of Θ) is then in O (d + 1) Pθ∈Θ Nθ = O d +21 Pθ∈Θ(nθ2 − nθ) = O(d Pθ∈Θ nθ2). As the training set grows by adding samples, it is not necessary to recalculate the distances that have already been computed; in order to update the mean distance, adding the distances of the new training data and weighting them accordingly is suficient.
In this context, the fact that the class of an unkown sample x might be one of its neighbour’s would be a form of imprecision if there are several diferent classes. Moreover, the uncertainty could be deduced from the distance: the closer the neighbour is the more believable it is that x belongs to the same class as its neighbour. However, uncertainty and imprecision do not directly depend on the oracle in this situation but only on the training set used by EkNN. 3.2
The interest in using the theory of belief functions is to model uncertainty and
imprecision in the data used in active learning. In particular, it becomes
possible to model the ignorance, which would be dificult in the classical theory of
probability [
The approach described in this article consists to use EkNN in the context of active learning where some labels provided by the oracle are false. Parameters such as level of confidence or expertise estimation can not be taken into account in a such configuration as far as we know. Therefore, the oracle’s uncertainty is not modeled in this article. The approach tends rather to limit the influence of erroneous labels given by the oracle. Once the learning phase is over, with some samples being mislabeled, the EkNN classifier uses the density of the distribution and its distances to modulate the influence of each neighbor of a sample to be labeled. It is finally the use of the combination rule (eq. (5)) that will contribute to enhance the hypotheses where the BBAs are in agreement, and therefore, to limit the indirect efect of the oracle’s uncertainty.
Let us consider a dataset of two classes Θ = {θ1, θ2} and the classifier EkNN with k = 5. Let x be a sample to be labeled and its 5 nearest neighbours (xi)i∈J1,5K represented in figure 1. Whether the oracle mislabeled the samples (case A) or not (case B), the goal after the learning phase for the classifier is to find the actual class of x. In case B, two neighbours have been mislabeled, therefore, class 1 is majoritary, but the two remaining class 2 (correctly labeled) are closer to x. The classifier will take the distance into account and attribute a greater belief on θ2 even though the actual class is minoritary in the neighbourhood (see table 2). The coordinates of the samples and their distances to x are described in table 1. In this section, we prove that EkNN is a viable classifier in active learning and that its robustness to uncertain labels is interesting. We first present the methodology and protocol used in our experiment (section 4.1) and then discuss and interpret the results (section 4.2).
The EkNN classifier will be compared to kNN in order to highlight the performance of the former in active learning. The value of the nearest neighbours k is dificult to choose. A very small value will make the data very sensitive to noise while a larger value will lead to heavy computations. In this article, the value k will be arbitrarily set to 5 for each experiment and each dataset. These classifiers will also be used in association with uncertainty sampling (least confident prediction) and random sampling to select data for labeling. The secondary sampling method involves selecting the data to be labeled randomly so that its potential contribution or relevance to the model is ignored. Random sampling is often used to highlight a better eficiency of active learning’s sampling methods.
Several datasets are used to evaluate the classifiers’ behaviour. Synthetic
random data have been generated from scikit-learn’s library [
To evaluate the performance of a classifier coupled to a given sampling
method, the accuracy criterion is often used, but this metrics is not always
relevant, especially when the class distribution is unbalanced [
1 T P T N ab = + (9)
2 P N With T P , T N , P and N being respectively the amount of true positive, true negative, of samples from the positive class and samples from the negative class. The results for a combination of a classifier and a sampling method will be plot under the form of a learning curve of balanced accuracy according to the number of queries.
First, a simple comparison between EkNN and kNN is made according to the following protocol. The initial dataset X is split into a test set T consisting of 25 % of the samples while a “training” set contains the remaining samples. From the latter, 5 samples of each class is drawn, forming the bootstrap B, and will be used to pre-train the classifier. The remaining of the “training” set becomes the pool P so X = T ∪ B ∪ P. Then, the active learning phase begins: the classifier will forge queries from P by selecting the sample according to a given sampling method (uncertainty or random sampling) until the number of 150 queries is reached. After each query, the oracle gives the label of the requested sample and the classifier updates its knowledge. Finally, the classifier computes the balanced accuracy on T and adds it to the learning curve before making another query. The whole process is repeated 20 times such that an averaged learning curve is computed over the 20 learning curves for a given combination of classifier-sampling method.
Second, in order to add some uncertainty to the answers provided by the oracle, noise will be added to the labels, meaning that some of them are replaced by false values. Noise might not always be caused by uncertainty (the oracle can still provide false label while being confident and certain) but it will be suficient in the current configuration as the uncertainty is studied through its consequences. The protocol used is the same as in the previous experiment except that a copy of the labels is generated with t % of them being noised. To answer queries, the oracle uses this noised copy instead of the original labels. Finally, the noised curves will be compared to the curves corresponding to the data that have not been noised. 4.2
The comparison between EkNN and kNN in figure 2, whether with uncertainty or random sampling, suggests that the contribution of belief functions is most often interesting in AL. It is important to highlight that the EkNN is always superior or equivalent to kNN. This is the case for each dataset except for Speaker Accent Recognition where EkNN’s random sampling has significant low performance compared to the other curves. However, the diference is not always significant as the confidence intervals are often overlapping. Due to the definition of the balanced accuracy, the dataset with balanced class distribution presents higher score while the highly unbalanced one generate more learning dificulties. As a sidenote, the fact that uncertainty sampling is superior to random sampling is an expected behaviour, otherwise AL would not be an interesting learning paradigm.
When noise is added to label, it is worth mentioning that on dataset that are easy to classify, the confidence intervals of noised data is wider than non-noised data (Hard). This might be explained by the fact that noised data leads to bigger variance among results, and thus to a less precise balanced accuracy as it can be seen in figure 4. Although, this is not always the case as shown in figures 3 and 5. Predictably in such cases, when the noise rate is high, the Hard and Noised curves of a same classifier move away from each other. It is more interesting to compare EkNN and kNN’s Noised curves. Again, the former’s curve is often above or at the same level as the latter’s curve. The gap between the confidence intervals, however, does not appear to be large as they often overlap each other; the gap is wider in gfiure 5.
Therefore, it appears that EkNN is slightly more robust to noise than kNN.
Active Learning is a subfield of Machine Learning that aims to reduce the size of the training set and the amount of labels required. This paradigm might be coupled to the theory of belief functions in order to have a way to model uncertainty and imprecision amongst the data.
In this article, we attempt to show the eficiency of a classiefir based on belief functions, EkNN, compared to a more common classifier, kNN. Our results suggest that in the majority of the experiments there is a real contribution of the EkNN classifier.
The imperfect label discussed in this article mostly covered the uncertainty aspect with the use of noised label. Further experiments on imprecision could be done in future work to complete this paper. This could be achieved by allowing the oracle to propose several classes instead of one after each query. However, a more flexible classifier would be required to treat imprecision as EkNN is not particularly adapted to deal with several classes per sample. Besides, the EkNN classifier requires heavy computation in AL as the distances between samples are re-computed after each query. Thus, it might be interesting to design a more eficient and adapted belief functions-based classifier for AL in order to treat both uncertainty and imprecision.