The Saerens-Latinne-Decaestecker (SLD) algorithm is a method whose goal is improving the quality of the posterior probabilities (or simply “posteriors”) returned by a probabilistic classifier in scenarios characterized by prior probability shift (PPS) between the training set and the unlabelled (“test”) set. This is an important task, (a) because posteriors are of the utmost importance in downstream tasks such as, e.g., multiclass classification and cost-sensitive classification, and (b) because PPS is ubiquitous in many applications. In this paper we explore whether using SLD can indeed improve the quality of posteriors returned by a classifier trained via active learning (AL), a class of machine learning (ML) techniques that indeed tend to generate substantial PPS. Specifically, we target AL via relevance sampling (ALvRS) and AL via uncertainty sampling (ALvUS), two AL techniques that are very well-known especially because, due to their low computational cost, are suitable to being applied in scenarios characterized by large datasets. We present experimental results obtained on the RCV1-v2 dataset, showing that SLD fails to deliver better-quality posteriors with both ALvRS and ALvUS, thus contradicting previous findings in the literature, and that this is due not to the amount of PPS that these techniques generate, but to how the examples they prioritize for annotation are distributed.
In the field of probabilistic classification, a posterior probability (or simply: a posterior ) Pr(|x) represents the confidence that a classifier ℎ : → has in the fact that an unlabelled (“test”) document x belongs to class . As all confidence scores, posteriors are useful for ranking unlabelled documents (say, in terms of perceived relevance to class ). However, for some downstream tasks other than ranking, such as multiclass classification and cost-sensitive classification, standard (non-probabilistic) confidence scores are not enough, and true posteriors are needed.
For these downstream tasks to be carried out accurately, it is essential that the posteriors are
high-quality, i.e., well-calibrated.1 Some classifiers (e.g., those trained by logistic regression)
tend to return calibrated posteriors (we thus say that they are calibrated classifiers ); some other
classifiers (e.g., those trained by naive Bayesian methods) tend to return posteriors that are not
calibrated; yet some other classifiers return confidence scores that are not probabilities. For the
last two cases, methods exist (see e.g., [
Unfortunately, independently of the learning method used for training the classifiers,
posteriors tend to be uncalibrated when the application scenario sufers from prior probability shift
(PPS – [
The Saerens-Latinne-Decaestecker (SLD) algorithm [
However, its real efectiveness in improving the quality of the posteriors is not yet entirely
clear. On one side, a recent, large experimental study [
The goal of this paper is to shed some light on this relationship. The reason why we are
interested in this is that, if SLD indeed improved the quality of the posteriors under PPS, it
would be extremely useful for TAR. In fact, in TAR we typically use a classifier trained on
labelled data in order to return posterior probabilities of relevance for a large set of unlabelled
documents. These posteriors are needed for ranking the unlabelled documents in terms of their
probability of relevance, and high-quality posteriors are of key importance for approaches to
1The posteriors Pr(|x), where x belongs to a set = {x1, ..., x| |}, are said to be well-calibrated when, for all
∈ [
TAR based on risk minimization [
RQ: Does SLD improve the quality of posterior probabilities in situations in which the training set used for training the probabilistic classifier has been generated via active learning? In the rest of the paper we briefly introduce the SLD algorithm (Section 2) and the two active learning techniques (ALvRS and ALvUS) we use in order to investigate our research question (Section 3), after which we present the results of our experiments (Section 4) followed (Section 5) by a few concluding remarks.
We assume a training set of labelled examples and a set = {(x1, (x1)), . . . , (x||, (x||))} of unlabelled examples, i.e., examples whose true labels (x) ∈ = {1, . . . , ||} are unknown to the system.
SLD, proposed by Saerens et al. [
Essentially, SLD iteratively updates (Line 13) the estimates of the class priors by using the posteriors computed in the previous iteration, and updates (Line 15) the posteriors by using the estimates of the class priors computed in the present iteration, in a mutually recursive fashion. The main goal is to adjust the posteriors and re-estimate the priors in such a way that they are mutually consistent, i.e., that they should be such that
Pr () = 1 ∑︁ Pr(|x) | | x∈ Equation 2 is a necessary (albeit not suficient) condition for the posteriors Pr(|x) of the documents x ∈ to be calibrated. SLD may thus be viewed as making a step towards calibrating these posteriors.
The algorithm iterates until convergence, i.e., until the class priors become stable and Equation 2 is satisfied. The convergence of SLD may be tested by computing how the distribution of the priors at iteration ( − 1) and that at iteration () still diverge; this can be evaluated, for instance, in terms of absolute error, i.e.,2
AE(^(− 1), ^()) =
|| ∈
1 ∑︁ | P^r ()() − P^r (− 1)()|
2Consistently with most mathematical literature, we use the caret symbol (ˆ) to indicate estimation.
(2)
(3)
Algorithm 1: The SLD algorithm [
Input : Class priors Pr() on , for all ∈ ;
Posterior probabilities Pr(|x), for all ∈ and for all x ∈ ; Output : Estimates P^r () of class prevalence values on , for all ∈ ;
Updated posterior probabilities Pr(|x), for all ∈ and for all x ∈ ; 6 7 8 end
end 1 // Initialization 2 ← 0; 3 for ∈ do 4 P^r ()() ← Pr(); 5 for x ∈ do
Pr()(|x) ← Pr(|x); 9 // Main Iteration Cycle 10 while stopping condition = false do 11 ← + 1; 12 for ∈ do 13 P^r ()() ← 1 ∑︁ Pr(− 1)(|x); // Initialize the prior estimates
// Initialize the posteriors // Update the prior estimates
// Update the posteriors | | x∈ for x ∈ do
Pr()(|x) ← end ^ () Pr () · Pr(0)(|x) ^ (0) Pr ()
^ () ∑︁ Pr () · Pr(0)(|x)
^ (0) ∈ Pr () 14 15 16 17 18 end
end In the experiments of Section 4, we decree that convergence has been reached when AE(^(− 1), ^()) < 10− 6; we stop SLD when we have reached either convergence or the maximum number of iterations (that we set to 1000).
While SLD is a natively multiclass algorithm, in this paper we restrict our analysis to the binary case, with codeframe = {⊕ , ⊖} .
In the experiments for this work, we test the SLD algorithm on training/test sets generated via
two of the best-known active learning policies, namely Active Learning via Relevance Sampling
(ALvRS) and Active Learning via Uncertainty Sampling (ALvUS), first presented in [
Active Learning via Relevance Sampling (ALvRS). ALvRS is an interactive process which, given a data pool of unlabelled documents , asks the reviewer to annotate an initial “seed” set of documents ⊂ , uses as the training set to train a binary classifier ℎ, and uses ℎ to rank the documents in ( ∖ ) in decreasing order of their posterior probability of relevance Pr(⊕| x). Then, the reviewer is asked to annotate the documents for which Pr(⊕| x) is highest (with the batch size), which, once annotated, are added to the training set . Finally, we retrain our classifier on the new training set and repeat the process, until a predefined number of documents (the annotation budget) have been reviewed.
Active Learning via Uncertainty Sampling (ALvUS). The ALvUS policy is a variation of ALvRS, where we review the documents not in decreasing order of Pr(⊕| x) but in decreasing order of | Pr(⊕| x) − 0.5|, i.e., we top-rank the documents which the classifier is most uncertain about.
The Rand policies. For each of the two policies defined above, we define an “oracle-like” policy which we will use for a control experiment. The aim of these policies, which we call (RS) and (US) (corresponding to ALvRS and ALvUS, respectively), is helping to better understand whether the results we are seeing are due to the PPS generated by the two active learning policies, or to their document selection strategy. Given a set of labelled documents and a set of unlabelled documents generated via an active learning policy by sampling , the policy samples randomly to generate alternative labelled and unlabelled sets ′ and ′ subject to the constraints that || = |′|, | | = | ′|, Pr(⊕ ) = Pr′ (⊕ ), and Pr (⊕ ) = Pr′ (⊕ ). In other words, the policies generates the same PPS as the active learning policy, but with a diferent choice of documents.
We run a set of comparative experiments to explore the interaction between AL-based classifiers and SLD. In order to do this we test the two AL policies described above, ALvRS and ALvUS, and compare them with the (RS) and (US) policies.
We run our experiments on the RCV1-v2 dataset [
For each class ∈ , and for each AL policy, we run the AL process to generate a sequence
of binary classification training sets with incremental sizes; this determines a corresponding
sequence of test sets, since the pool is always the union of the training set and the test set ..
As for training the classifier, in all of our experiments we use a SVM algorithm, post-calibrated
via Platt calibration [
The active learning process is seeded with a set of 1000 initial training documents ⊂ , i.e., we randomly sample 1000 documents from our pool and train our classifier on it. Since in order to calibrate the SVM classifier we need at least 2 positive instances (i.e., instances of ⊕ ) for cross-validation, we always ensure this condition is respected in . We then run the active learning process on the remaining 99,000 documents. This procedure is illustrated in Algorithm 2. As previously mentioned, we also generate an analogous sequence of training/test
Algorithm 2: Pseudo-code to generate active learning datasets.
Input : Documents ; Set of training set sizes Σ; AL policy ; Batch size 1 ← random_sample(, 1000); 2 ← − ; 3 ← max(Σ); 4 ← | |; 5 ← train_svm(); 6 while || < do 7 ← ∪ select_via_policy(, , , ); 8 9 10 11 12 13 14 end ← train_svm(); ← − ; ← | |; if ∈ Σ then
save(, ) end sets with a policy, i.e., random sampling constrained to keep the same class prevalence values obtained by the corresponding active learning policies.
Once the diferent training sets are generated, we train a calibrated SVM from scratch on each of them and obtain a set of posterior probabilities PrPreSLD(⊕| x) for each respective test set. Finally, we apply the SLD algorithm, obtaining a new set of posteriors PrPostSLD(⊕| x).
In TAR scenarios, we are usually interested on the classification performance on the entire pool : for this reason, we merge the labels on the training set with the posterior probabilities on the test set, obtaining a new set of probabilities Pr(⊕| x) where, for all x ∈ , we take Pr(⊕| x) = 1 if ⊕ is the true label of x and Pr(⊕| x) = 0 if ⊖ is the true label of x, with the training set. All of our evaluation measures are computed on this set of probabilities.
To evaluate the performance of our classifier and the quality of the posteriors we use several metrics, namely, Accuracy, Precision, Recall, 1, and Brier Score. We will explain more in detail the last metric, as the reader is likely familiar with the first four.
Given a set = {(x1, (x1)), . . . , (x||, (x||))} of unlabelled documents to be labelled
according to codeframe = {⊕ , ⊖} , and given posteriors Pr(⊕| x) for these documents, the
Brier score [
BS = 1 ∑|︁| (((x) = ⊕ ) − Pr(⊕| x))2 | | =1 (4) where (· ) is a function that returns 1 if its argument is true and 0 otherwise. BS ranges between 0 (best) and 1 (worst), i.e., it is a measure of error, and not of accuracy, and rewards probabilistic classifiers that return a high value of Pr(⊕| x) for instances of ⊕ and a low such value for instances of ⊖ . In our result tables we will report, instead of the Brier score, its complement to 1, i.e., (1 - BS), so that all our metrics can be interpreted as “the higher, the better”.
We present the results of our experiments in Table 1 for ALvRS and in Table 2 for ALvUS.
These results are averages across all of the 103 RCV1-v2 classes used in our experiments. We show both the average results for each training set size (2000, 4000, 8000, 16000) and the results averaged on all sizes. We note that in all cases (i.e., for both ALvRS and ALvUS, and for all sizes), the use of SLD has a detrimental efect on the posterior probabilities. However, while this is true for the setups generated via active learning, the use of SLD has a beneficial efect on the posteriors when the policies have been used.
What we see on the AL datasets seems to contradict what was argued in [
While we defer a proper analysis of the causes of this problem to future work, a first hypothesis
might be that the following is happening. When building active learning datasets, we can assume
that the documents that remain in the test set, as this decreases in size, are documents for which
the classifier is either fairly sure of their negative label (ALvRS) or of their label in general
(ALvUS). Furthermore, AL policies such as relevance sampling or uncertainty sampling sufer
from sampling bias [
All this would require a deeper analysis, which however we defer to future work. 4We did not plot the entire [0.0, 1.0] interval as there was hardly any probability after the 0.3 threshold. This makes the plots more readable.
(a) ALvUS posteriors pre- and post-SLD.
We have studied the interactions between active learning methods and the SLD algorithm. It is known that AL-generated scenarios tend to exhibit a high prior probability shift, and that in past research SLD has proven efective in improving the quality of the posteriors on sets of unlabelled data, especially in cases of high PPS. We thus tested the use of SLD on the posteriors generated by classifiers trained on AL-generated training sets, testing the hypothesis that SLD would improve the quality of these posteriors. Our results do not support this hypothesis, showing instead that the posteriors returned by AL-based classifiers deteriorate after the application of SLD. We have run control experiments that used the same amount of PPS of the AL-generated scenarios, albeit obtained by sampling the elements of the pool randomly. In this case SLD did improve the quality of the posteriors, which indicates that SLD has a specific problem not with the amount of PPS but with the documents selected by AL techniques.
From these preliminary experiments we conclude that, counterintuitively, it is not recommended to combine AL and SLD. In future work we will investigate more deeply the causes of this problem, i.e., what aspect of the AL process results in the bad interaction with SLD, and if and how it is possible to solve this problem, so as to combine the benefits of both methods.
This work has been supported by the AI4Media project, funded by the European Commission (Grant 951911) under the H2020 Programme ICT-48-2020, and by the SoBigData++ project, funded by the European Commission (Grant 871042) under the H2020 Programme INFRAIA2019-1. The authors’ opinions do not necessarily reflect those of the European Commission.
Accuracy Precision
Recall
F1 (1-BS)