SAL_τ: efficiently stopping TAR by improving priors estimates

AL algorithms prioritize the annotation of certain data items over others. Two of the most well-known AL techniques, still used to this day, were presented in 1994 by Lewis and Gale (1994): Active Learning via Relevance Sampling (ALvRS) and Active Learning via Uncertainty Sampling (ALvUS).

Algorithm 2.1 shows the typical structure of an AL process with a stopping rule. Given a data pool of unlabelled documents P, the reviewer annotates a “seed” set of documents \(S\subset P\) that defines the initial training set L. An iterative procedure is then started, in which L is used to train a classifier \(\phi \), which is then exploited by an AL policy pol to select the next set of documents to be presented to the reviewer. In ALvRS, \(\phi \) is used to rank the documents in \((P\setminus L)\) in decreasing order of their posterior probability of relevance \(\Pr (\oplus {\vert }{\textbf{x}})\). The reviewer is asked to annotate the b documents for which \(\Pr (\oplus {\vert }{\textbf{x}})\) is highest (with b the batch size), which, once annotated, are added to the training set L. The classifier is retrained on the new training set and the process repeats until a stopping condition is met, e.g., the annotation budget is exhausted or a target recall is reached. ALvRS is most-effective and has been mostly used when we are interested in finding all the items relevant to a given information need, as quickly as possible.

The ALvUS policy is a variation of ALvRS, where documents are ranked in ascending order of \({\vert }\Pr (\oplus {\vert }{\textbf{x}})-0.5{\vert }\), i.e., we top-rank the documents which the classifier is most uncertain about. ALvUS can be useful when we want to build a high-quality training set to later train a machine learning model on it, and has not been employed as often as ALvRS in TAR applications. While many other AL techniques have been proposed over the years (Dasgupta and Hsu 2008; Huang et al. 2014; Konyushkova et al. 2017), in this work we focus especially on ALvRS, and in particular on its variant called Continuous Active Learning (CAL), proposed by Cormack and Grossman (2015), which is specifically tailored to TAR applications.

Both ALvRS and ALvUS policies suffer from what is called sampling bias (Dasgupta and Hsu 2008; Krishnan et al. 2021), i.e. the fact that, due to the document selection policy, the sample of annotated items L is not representative of P, nor of the unlabelled set U (see Sect. 3 for a more thorough explanation and analysis). In order to investigate how and when a classifier is affected by this bias, Esuli et al. (2022) have introduced a policy called Rand(pol). The Rand(pol) policy is an oracle policy, i.e., it requires knowing the true labels of all documents in the pool. It is thus a synthetic policy designed to investigate the issue of sampling bias of a given AL policy pol.

Rand(pol) observes the prevalences of labels in the L set produced by pol and produces its own \(L^{Rand}\) set which exhibits the same prevalences, but using a random document selection policy. The idea is that substituting the selection policy of pol with random sampling keeps the content of elements in \(L^{Rand}\) unbiased with respect to P, while using the same prevalences produced by pol. The comparison of results produced by pol and Rand(pol) is thus a way to understand whether and how much sampling bias is affecting the decisions of a pol-based classifier: being a controlled random sampling, the Rand(pol) policy should produce a “sampling bias free” dataset.

TAR processes usually operate in a “needle in a haystack” scenario, i.e. the number of relevant items is just a tiny fraction of the whole collection of documents. Three of the main TAR real-world applications are: e-discovery, in the legal domain; the production of systematic reviews in empirical medicine, and online content moderation. In this work, we focus on the first two tasks.

Finding a way to stop the AL process as soon as a target recall R is reached is a key aspect in lowering the cost of human review, the other being using an AL policy that efficiently selects relevant documents over non-relevant ones. The target recall is usually very high, in many cases equal or close to 100%, transforming the task in a “total recall” task; other high target recalls are often seen in TAR applications, such as 80% or 90% (Li and Kanoulas 2020; Yang et al. 2021a, b).

The scope and aim of this paper is on stopping algorithms which work inside an AL process without changing the sampling policy. We thus do not consider “interventional stopping rules”, e.g. Li and Kanoulas (2020). As observed in (Yang et al. 2021a, §2), we argue that interventional methods are (i) less efficient than AL (i.e., they usually trade off annotation costs for a safer recall estimation) and (ii) less applicable in real case scenarios, where reviewers are often limited to using some AL methods (i.e., relevance sampling) provided by a specific software. We will now give an overview of the most relevant methods, which are then compared to our proposal in the experiments.

The Saerens–Latinne–Decaestecker (SLD) algorithm (Saerens et al. 2002) was proposed as a technique to adjust a priori and a posteriori probabilities (priors and posteriors here after) in prior probability shift (PPS) scenarios, i.e. when the prior probability \(\Pr (y)\) diverges between the labelled L and the unlabelled U sets (Moreno-Torres et al. 2012). The algorithm works by iteratively and jointly updating the prior and posterior probabilities (see Algorithm 3).

AL policies, such as relevance and uncertainty sampling, naturally tend to generate a high PPS: in particular, when \(\Pr _P(\oplus )\) is fairly low to start with (as it usually is in TAR applications), the AL process generates a PPS such that \(\Pr _L(\oplus ) \gg \Pr _U(\oplus )\). Hence, using SLD to improve both our prevalence estimates and our posteriors might seem like a promising idea. However, recent works (Esuli et al. 2022; Molinari et al. 2023) have shown that in this context SLD has a disastrous effect on the posteriors. In the next sections, we analize this behaviour (Sect. 3) and propose a solution (Sect. 4) that enables using SLD in AL (and hence, in TAR).

The reason why sampling bias is a key element in our analysis lies beneath the main assumptions made by SLD on the posterior probability distribution of the classifier: SLD reasonably assumes to be in the scenario represented by the Rand(RS) policy rather than the AL one. More precisely, it assumes that there is no dataset shift on the conditional probability \(\Pr (x\vert y)\) between the labelled set L and U, i.e., that \(\Pr _L(x \vert y) = \Pr _U(x \vert y)\). If this assumption holds, the trained classifier will have a bias on L which will “uniformly” translate (i.e., in our previous example, the bias is consistent for all regions of the graph) to the posterior probabilities \(\Pr _{U}(\oplus \vert x)\) on the unlabelled set. In a PPS scenario, this means that the classifier estimate of the prevalence (i.e., the average of the classifier posteriors) will be closer to L, and that they can be “adjusted” consistently across the whole distribution. Nonetheless, when using an active learning policy such as ALvRS or ALvUS, we not only generate prior probability shift, but we also affect the distribution of the conditional probability \(\Pr (x \vert y)\), such that \(\Pr _L(x \vert y) \ne \Pr _U(x \vert y)\).

Let us now focus on one of the key updates in SLD: the priors ratio (Line 13 of Algorithm 3), which is later multiplied by the posteriors. This is defined as:This linear relation is represented by the red line of Fig. 3. When \({\hat{\Pr }}_{U}(\oplus ) = \Pr _{L}(\oplus )\), the ratio is 1, and posteriors do not change. However, as \({\hat{\Pr }}_{U}(\oplus )\) drifts further away from \(\Pr _{L}(\oplus )\) (recall that this latter quantity is constant for all iterations in SLD), the ratio becomes progressively smaller, resulting in a multiplication of \(\Pr _U(\oplus {\vert }x)\) by a number very close to 0.² We argue this is one of the main culprits of degenerated outputs from SLD.

In other words, let us assume that \(\Pr _L(x\vert y) = \Pr _U(x\vert y)\), and that L is then a representative sample of U. A classifier trained and biased on L will tend to shift any prevalence estimate toward \(\Pr _{L}(\oplus )\). When the classifier estimated \({\hat{\Pr }}_{U}(\oplus )\) is lower (or higher) than \(\Pr _{L}(\oplus )\), SLD deems the true \(\Pr _{U}(\oplus )\) to be even lower (or higher). Indeed, this works very well when the previous assumption holds, e.g., for Rand(pol). As a matter of fact, SLD has been a state-of-the-art technique for prior and posterior probabilities adjustments in PPS for 20 years. However, ALvRS and similar techniques generate a \(\Pr _L(x\vert y) \ne \Pr _U(x\vert y)\) type of shift (as well as PPS), and, as a result, we cannot apply SLD update with confidence: we should rather find a way to apply a milder correction, when possible, or no correction at all when we have no way of estimating how “far” we are from the SLD assumption.

We have seen that SLD works on the output of a Rand(RS)-based classifier (Esuli et al. 2022). We can build our estimate of \(\tau \) for SAL\(_\tau \) by measuring how much the ALvRS classifier posteriors are more or less distributed like those of a Rand(RS) classifier. The more ALvRS posteriors diverge from Rand(RS) ones, the milder SLD correction should be, up to the point where we do not use SLD at all.

Let us consider the posteriors for the relevant class, i.e., \(\Pr (\oplus {\vert }x)\): we collect a vector \({\mathcal {A}}\) of posteriors \(\Pr (\oplus {\vert }x)\) for all documents in U for the classifier trained on the ALvRS training set, and an analogous one \({\mathcal {R}}\) for the classifier trained on the Rand(RS) training set. We define \(\tau \) as the cosine similarity between these two vectors:Since \(\Pr (\oplus {\vert }x) \ge 0\) by definition of probability, the cosine similarity is naturally bounded between 0 and 1, a required property of our \(\tau \) parameter. In other words, we apply the SLD update when AL posteriors are similar to posteriors for which we know the assumption made in SLD holds (i.e., \(\Pr _L(x\vert y) = \Pr _U(x\vert y)\), see Sect. 3); we apply an accordingly milder correction the further the AL posteriors are from this assumption.

Equation (8) would be a good solution, as well as an impossible one, since the Rand(pol) policy requires knowledge of the labels (e.g., relevancy) for the entire data pool.

We thus resort to an heuristic formulation based on the evolution of the classifier during the iterations of the AL process.³ Given the batch of documents \(B_i\) reviewed at the i-th iteration, we define \({\mathcal {A}}_{\phi _i}\) and \({\mathcal {A}}_{\phi _{i-1}}\) as:i.e., the posteriors on \(B_i\) returned by the classifiers \(\phi _i\) and \(\phi _{i-1}\). The \(\tau \) parameter is then defined as the cosine similarity between \({\mathcal {A}}_{\phi _i}\) and \({\mathcal {A}}_{\phi {i-1}}\). The assumption we make is that:Let us consider the ALvRS policy, in a scenario similar to the one depicted in Fig. 2a, that is, overall prevalence is low and we start with a small seed set: in the first iterations we are likely going to find many positive items; that is, when we compare \({\phi _i}\) and \({\phi _{i-1}}\) predictions on \(B_i\) they are likely to be similar, since the “clusters” of data available to \({\phi _i}\) are probably the same that were available to \({\phi _{i-1}}\). However, as we review all the positive items in a cluster, the process is forced to explore items in the neighbour clusters. This is when the cosine similarity should be effective: by comparing the posterior distribution of \(\phi _i\) to that of \(\phi _{i-1}\) for the same \(B_i\) documents, we should be able to assess the impact of the new documents on the classifier. Indeed, if \(\phi _i\) accessed previously unseen clusters, the posteriors on \(B_i\) might radically change and, in turn, roughly give us an estimate of how much sampling bias was affecting \(\phi _{i-1}\) predictions.

Finally, let us consider one last issue: we said that in the first AL iterations \({\mathcal {A}}_{\phi _i}\) will likely be similar to \({\mathcal {A}}_{\phi _{i-1}}\), and their distance cannot be used as an indication of sampling bias. How can we establish when to use our method and when to fallback to the classifier posteriors? In lack of better solutions (which we defer to future works), we introduce a hyperparameter \(\alpha \):The simple intuition behind this heuristic is that when the NAE between the true prevalence and the prevalence estimation of SAL\(_\tau \) is too high, then the estimates of SAL\(_\tau \) are likely going to be poor on the rest of the pool as well.

To recap, we give below an overview of how SAL\(_\tau \) integrates into the active learning process (see Algorithm 5):

As it will be clear in the results section (Sect. 6), SAL\(_\tau \) achieves significant improvements with respect to the compared methods. However, SAL\(_\tau \) also tends, in some cases and especially for higher recall targets, to overestimate the recall, stopping the TAR process too early. Leaving the study of more complex approaches to future work, we propose a simple way to mitigate the issue of recall overestimation by raising by a margin value the target recall given in input to the method. We call this variant SAL\(_\tau ^m\) (SAL\(_\tau \) with margin m), which trades off an increment in annotation costs for a safer TAR process that reduces the early stops. SAL\(_\tau ^m\) is actually SAL\(_\tau \) with the only difference being the use of a target recall \(R^m\) determined as a function of the target recall R and the margin m:The margin m ranges from 0 to 1. When \(m=0\), \(\textrm{SAL}_\tau ^m= \textrm{SAL}_\tau \); when \(m=1\), \(R^m=1\). A low value means fully trusting SAL\(_\tau \), a high value means accepting to label more documents to avoid early stops. In order to avoid adding a free parameter to the method we decided to set \(m=R\), following the intuition that it is crucial to guarantee a given target recall R, the closer R is to 1. Equation (12) thus becomes:We call this configuration SAL\(_\tau ^R\) and comment upon its results in Sect. 6. We defer to future works the exploration of more informed methods to set m, which could possibly enable a more convenient trade-off between annotation costs and proper recall targeting.

The SAL\(_\tau \) algorithm can be tested in any AL scenario where we need to improve priors and posteriors. In this paper, we focus on testing SAL\(_\tau \) capabilities for TAR: our goal is to stop the review process as soon as a target recall R is reached, lowering the review cost.

We test the SAL\(_\tau \) algorithm with three configurations: We compare against the following well-known methods (see Sect. 2): For all methods that require a confidence interval, we set it to \(95\%\). The positive sample size r of the QBCB method (see Sect. 2.3.4) is instead set at 50, which in the results reported in the original paper appears to be a good trade-off between a low overall cost and a low variance in such cost across different samples.

We run the same active learning workflow for all tested methods. In most TAR applications (Yang et al. 2021a; Cormack and Grossman 2015), we usually have only a single positive document to start the active learning with, called the initial seed: for our experiments, we decide to seed the active learning process with an additional negative document randomly sampled from the document pool P; that is, our initial seed set S consists of a positive and a negative document, randomly sampled from P.

As mentioned earlier (Sect. 2), the active learning policy we pick is CAL (Cormack and Grossman 2015) (a variation of ALvRS) since this is the most common policy used in TAR tasks. As the batch size b, we follow (Yang et al. 2021a) and set it to 100. The classifier we use in all our experiments is a standard Logistic Regression, as this is also the classifier of choice in most (if not all) TAR applications. We test the target recalls values \(\{0.8, 0.9, 0.95\}\).

We run our experiments⁴ on two well-known datasets: the RCV1-v2 and the CLEF Technology-Assisted Reviews in Empirical Medicine (EMED) datasets (specifically, the dataset made available for the CLEF 2019 edition). Both datasets have been already used to test TAR frameworks and algorithms, e.g., the MINECORE framework (Oard et al. 2018), the QuantCI stopping technique (Yang et al. 2021a) and Li and Kanoulas sampling methodology (Li and Kanoulas 2020). We also use a sample of the Jeb Bush Email collection to set SAL\(_\tau \) \(\alpha \) hyperparameter.

All text is converted into vector representation first converting it to lowercase, removing English stopwords and any term occurring in more than 90% of the documents in P; vectors are weighted using tf-idf.

We evaluate the tested methods using three measures: The first two measures are well-known and used in many different tasks in IR and machine learning literature, and they have been used to evaluate TAR tasks (Li and Kanoulas 2020; Yang et al. 2021a).

The IC metric is defined as follows: it uses a cost structure (similar to what was previously done in Oard et al. (2018)), a four-tuple \(s = (\alpha _p, \alpha _n, \beta _p, \beta _n)\). Subscript p and n indicate the cost of reviewing positive (relevant) and negative (non-relevant) documents; \(\alpha \) and \(\beta \) represents the costs of reviewing a document in a first or second phase: in a one-phase TAR process, this “second” phase is referred to as the failure penalty. That is, it would be the cost of continuing the review with an optimal second phase, by ranking documents with the model trained in the first one.

Let Q be the minimum number of documents to review to reach the recall target R. Say we review batches of size b and we stop at iteration t: let \(Q_t\) be the number of documents we reviewed before the method stopped the review. If \(Q_t < Q\), we have a deficit of \(Q - Q_t\) positive documents; let \(\rho _t\) be the number of documents that need be reviewed,⁸ following the ranking, to find the additional \(Q - Q_t\) positive documents. The total cost of our review is then:Where \(I[Q_t < Q]\) is 0 if Q documents were found in the first t iterations and 1 otherwise.

Following both Yang et al. (2021b) and Oard et al. (2018), we evaluate our results with three cost structures: