{'fraction_non_alphanumeric': 0.029286608260325406, 'fraction_numerical': 0.003003754693366708, 'mean_word_length': 4.8452816386247255, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Active Search for High Recall: a Non-Stationary Extension of Thompson Sampling

We consider the problem of Active Search, where a maximum of relevant objects - ideally all relevant objects - should be retrieved with the minimum effort or minimum time. Typically, there are two main challenges to face when tackling this problem: first, the class of relevant objects has often low prevalence and, secondly, this class can be multi-faceted or multi-modal: objects could be relevant for completely different reasons. To solve this problem and its associated issues, we propose an approach based on a non-stationary (aka restless) extension of Thompson Sampling, a well-known strategy for Multi-Armed Bandits problems. The collection is first soft-clustered into a finite set of components and a posterior distribution of getting a relevant object inside each cluster is updated after receiving the user feedback about the proposed instances. The"next instance"selection strategy is a mixed, two-level decision process, where both the soft clusters and their instances are considered. This method can be considered as an insurance, where the cost of the insurance is an extra exploration effort in the short run, for achieving a nearly"total"recall with less efforts in the long run.


Introduction
Contrary to Active Learning, Active Search does not aim at building the best possible classifier with the minimum number of labelled instances, but simply aims at discovering virtually all the instances of the positive class (assuming a binary classification problem) with the minimum "reviewing" effort or cost. The collection -or pool -of objects to search in is assumed to be known in advance and the setting is, in some way, similar to the Transductive Learning setting, but with an on-line, incremental, "recall-oriented" perspective. Consequently, Active Search algorithms can be very different from traditional Active Learning algorithms. Active Search applications could be found in numerous domains: fraud detection, compliance monitoring, e-discovery, systematic medical reviews, prior art search when filing a patent, etc.
Recently, some pieces of work [5,9] have focused on developing Active Search strategies that significantly depart from Active Learning, by emphasizing the "Total Recall" aspect and the "Continuous Active Learning" setting. The main idea of this family of works is to greedily select the next instances as the ones with the largest estimated probabilities of belonging to the relevant class (these probabilities are given by a classifier incrementally trained from all labelled instances up to the current time).
In addition to belonging to a low prevalence class, relevant objects can take multiple forms or facets: the landscape of the positive class is often "multimodal". When considering these challenges -unbalanced class distribution and multi-modality of the relevant class -, there is a clear need to control the exploration-exploitation trade-off if we want to improve the "baseline" greedy approach and make it more robust: typically, the search starts with a small number of "seed" instances and these seeds rarely cover all modes and facets of the positive class. So, a greedy selection approach runs the risk of missing large areas of relevant instances, when the corresponding facets are not covered (or hardly reachable from) the instances reviewed ans labelled as positive up to the current time. At the early stage of the search, it can be useful to spend some effort in exploring diverse regions of the instance space, provided that these regions could offer potentially relevant elements in the long run.
The use of Multi-Armed Bandits (MAB) appears as a natural choice to solve this exploration-exploitation trade-off. Instead of considering the problem as an instance recommendation problem with a binary response as in [3] and solving it by using contextual bandit strategies, we follow an alternative strategy that turns out to be more efficient in our use cases. This alternative consists in discretizing the structure of the feature space into a finite set of clusters and in relying on the cluster structure to manage the exploitation-exploration trade-off. More precisely, the idea is to consider each cluster as an arm of a MAB and to focus on the most promising ones, while ensuring that the selection strategy covers all facets or clusters of the instance space. However, we face the problem of dealing with non-stationary (or restless) mortal bandits, as the reward distribution of a cluster gradually declines each time we "exploit" it.

Related work
Even if there is a large literature on Active Learning, the case of Active Search has not received the same attention. One of the first works on this problem was presented by [6] who proposed a Bayesian approach that requires computations exponential in the number of look-ahead steps (number of future steps considered), which makes this method impractical for large collections. Several pieces of work have approached Active Search as exploration on graphs [7] or also graph learning [8]. However, the mostly used state-of-the-art method remains the greedy (one single step ahead) approach: one of the most striking examples of this is the "Continuous Active Learning" concept of [5], implemented in the form of the AutoTAR system in the field of e-Discovery, and extended further in [9]. This vein of work relies on variants around a main baseline, which greedily selects the next instances as the ones with the largest probability scores with respect to the relevant class. The probability scores are estimated by a classifier trained incrementally.
The use of MAB in Active Learning is not new and relatively well studied. A relatively common way to solve Active Learning with MAB is to cluster the instances on the pool and consider that each cluster is an arm [2,4]. In this case, the payoff distribution for each arm is non-stationary since the probability of finding relevant instances in a cluster decreases as the cluster is exploited. This could be solved by assuming a known fixed trend as in [1].
Finally, our work is not the only one to use MAB for Active Search. Even if initially formulated as an item recommendation problem, the MAB-based approach of [3] could be used as such for Active Search; in this piece of work, the "next item selection" problem is expressed as a contextual bandit, where each instance is an arm; the expected reward (or relevance label) of an instance is expressed as a logistic regression model, whose parameters are sampled following a Thompson sampling strategy from the posterior distribution updated each time a new label is collected. We have implemented this method for our collections and the results were extremely weak due to the fact that the method is not adapted to sparse high-dimensional data and requires a lot of exploration, often exceeding the budget or simply the collection size.

Proposed Method
Traditional Active Search methods are typically greedy: they are looking for the most promising instances, i.e. the ones with the highest conditional probabilities as estimated by a classifier trained on the instances reviewed up to the current time. However, greedy strategies are likely to fail when the relevant class is "multi-modal" or "multi-faceted", in other words when they are multiple, well distinct and possible unbalanced ways of being relevant. As the greedy strategies introduce a high selection bias when incrementally building the training set, it could be that the selection algorithm will miss important sectors of the relevant category, because they are relative far from the positively-labelled training instances. In practice, this risk strongly depends on the quality of the seed set: the seed set should be diverse enough and have a good coverage of the different facets of relevance, but unfortunately this guarantee is hard to obtain.
We translate the Active Search problem into a MAB setting, by considering clusters of pool instances as arms. But this choice has the particularity that the algorithm can "exhaust" a cluster and that, consequently, the related arm will "die" once all instances in the cluster have been reviewed and labelled. Intuitively, we face a diminishing return issue: the retrieval rate of relevant objects decreases as we are exploiting the cluster. Note that, in our approach, we rely on soft clustering so that an instance can belong to multiple clusters with different degrees of membership. This renders the approach more robust with respect to a particular clustering method but, on the other side, we have to adapt the MAB algorithms for a non-standard reward scheme: the reward obtained for a particular instance should be re-assigned to multiple clusters (or arms) with an appropriate weighting. Moreover, as it is rather usual in Active Search to proceed with batches and not with single instance proposals, we have adapted the MAB algorithms so that they can provide us with a "batch" of arm trials and update the arms' sufficient statistics (i.e. the posterior distribution of the reward) accordingly.
Due to lack of space, we only give an intuitive description of the algorithm, redirecting the reader the full version of this paper [xxx] for a formal description of the algorithm.
The first step of the algorithm is the creation of an initial training set from the seed set: a few positive instances discovered by any means and a random sample from the pool set temporarily labelled as "negative" (which introduces very low label noise as the relevance class has low prevalence). It then iteratively creates a batch of instances from the pool using a non-stationary, batch extension of the "Thompson sampling" MAB algorithm, asks the reviewer to label them, removes them from the pool, updates the reward distribution estimates; and it finally retrains the classifier based on the labelled instances and a random sample re-drawn from the pool, temporarily labelled as negative. Actually, the MAB algorithm is a two-level process, where the algorithm first samples B times (the batch size) a "conversion rate" for each cluster/arm from a Beta posterior distribution (the conversion rate is the probability of a high-score member of the cluster to be annotated as a relevant instance) and, secondly, selects an instance that maximizes the probability of being relevant, given the sampled conversion rates of the clusters it belongs to.
Let's first focus on the update of the posterior distributions. The posterior distribution of the "conversion rate" of each cluster is a Beta distribution with parameters (S k , F k ), initialised with S k = F k = 0.5 for all arms k (Jeffreys' prior). When receiving the label (or, equivalently, the reward) of the instances selected at the previous round, the binary reward is re-distributed over the the clusters with a weight equal to the membership value of the instance with respect to the cluster. Updating the posterior is done using a forgetting factor γ, discounting the previous (weighted) success/failure counts by a factor γ. Assuming that, at round t, the conversion rate of cluster k follows a Beta distribution with parameters (S is the batch of instances selected at round t, µ i,k is the membership value of i in cluster k and r i is the binary reward (i.e. 0/1 label) of instance i.
Let's now focus on the double-stage selection process. For a batch of size B, we repeat B times the following steps: for each arm/cluster, draw a value θ k from the Beta distribution associated to the cluster: k ); this value should be interpreted as the parameter (the mean) of a Bernoulli distribution modelling the arm reward distribution; in this work, we use an "Optimistic Bayesian sampling" variant, where one does not allow θ k to be smaller than the empirical discounted mean of the arm reward (based on observations up to the current round): θ * k = max( , θ k ). The algorithm then chooses the instance i * such that: i * = argmax i∈U π (t) i towards a real relevant instance. The exploration effect relies on the sampling from Beta(S t k , F t k ), which can potentially favour less explored clusters as their posterior distribution is less peaked. Of course, when generating the batch of instances, once an instance has been selected, it is removed from the pool and will not be selected again.

Experiments and Results
Due to lack of space, we present the experimental results for a single use case, but the extended version of this paper also describes two other use cases (one in e-discovery and one in multi-media diversity-focused retrieval). The collection used here is the Reuters RCV1 Corpus, considering only classes (or topics) at the first level of the hierarchy with a prevalence less than 10% and having at least three children. These classes are C17, C18, E14, E31, E51 and G15. The reason of selecting these classes is that, by construction, they consist of multiple diverse sub-classes and, consequently, are "multi-faceted". The classifier used in all experiments is a L2-regularised Logistic Regression, based on the tokenised, TF-IDF-weighted, L2-normalised bag-of-word representation of the documents. As soft clustering method, we used LDA (Latent Dirichlet Analysis). We fixed the discounting factor γ to 0.99 and the number of arms/clusters K (the number of latent components in LDA) to 200. These hyper-parameters were tuned on an "unused" topic (M14).
The performance measure is simply the proportion of the collection to be reviewed to reach certain levels of recall, focusing on the high recall values. For each topic, we have performed 10 different runs with different seed sets; each seed set consisted of three random relevant instances of the topic. We have limited the reviewing budget to 40% of the collection. The values given in the table 1 are the average over these 10 runs. Note that we also tried to use a variant of the greedy strategy, based on the Maximal Marginal Relevance (MMR) method; but the latter performed worse than our method, because it is still favouring exploration and diversity at the late stage of the search.
There are several important observations that we can make from these experimental results. First, if the requested level of recall is relatively low, the baseline is still the best choice. But, for a sufficiently high recall, the exploration effort spent during the early phases of the search starts to be beneficial and our method outperforms the baseline. The "break-even" point between the two strategies depends on the collection and on the topic. In some way, our method can be considered as an"insurance" to be able to reach efficiently a high recall without forgetting significant segments of relevant instances; the cost of this insurance is the extra effort spent in exploring diverse clusters during the search. A second observation, which is more visible on other collections and topics not presented here, is that the beneficial effect seems to decrease, and even to disappear, for extreme values of recall. The most likely reason of this sudden decline is the label noise: some irrelevant instances, incorrectly labelled as relevant, are virtually unreachable from any classifier built from (correctly labelled) positive instances.

Conclusions and Future Works
This paper considers the Active Search problem as a resource allocation task in an uncertain environment and handles it in a way similar to what is done for petroleum drilling and ore mining projects. By soft-clustering the landscape of the instance feature space and using sampling strategies based on MAB, the method proposed here should be considered as an insurance to decrease the risk of missing a significant amount of relevant objects when the task is to achieve high recall of a low-prevalence, multi-faceted relevant class. Future works will focus on analysing the cost/benefit ratio depending on the task and the collection to be processed.