Modelling Stopping Criteria for Search Results using Poisson Processes

Alison Sneyd, Mark StevensonEMNLP 2019 · DOI

TL;DR

This paper introduces a novel method for determining when to stop reviewing search results in information retrieval, using a Poisson process to model the rate of relevant documents. This approach aims to significantly reduce manual effort in tasks like systematic reviews by predicting the optimal stopping point while guaranteeing a desired level of recall with high probability.

What Problem Does This Paper Address?

Information retrieval systems often return vast numbers of documents in response to a query. Manually reviewing these documents to identify relevant ones is a time-consuming and expensive process, especially in fields like medical literature reviews where missing a crucial document can have serious consequences. Existing methods for deciding when to stop reviewing search results, such as "target" and "knee" methods, help reduce this burden but often lack probabilistic guarantees about the achieved recall or can be sensitive to the quality of the initial search ranking. This paper addresses the need for a stopping criterion that is both efficient and robust across different ranking qualities, providing a clear probabilistic guarantee on the achieved recall.

Methods

The core of this paper's contribution is the application of an inhomogeneous Poisson process to model the occurrence of relevant documents within a ranked list. The rate at which relevant documents appear is modeled using an exponential function, $\lambda(x) = de^{kx}$, where $d$ and $k$ are parameters learned from an initial sample of the retrieved documents.

The method then uses the properties of the Poisson distribution to predict the total number of relevant documents ($R$) in the entire collection, given a desired recall level ($r$) and a desired probability of achieving it. The stopping point is then determined as the rank at which a specific number of relevant documents, corresponding to the target recall, have been found.

Key aspects of the method include:

  • Parameter Estimation: The parameters $d$ and $k$ of the exponential rate function are estimated by fitting a curve to data points derived from an initial sample of documents.
  • Stopping Condition: The process stops when a predicted number of relevant documents, sufficient to meet the desired recall with a specified probability, have been identified.
  • Robustness Checks: The method includes checks to ensure the fitted curve is a good predictor and that relevant documents are not too rare or consistently ranked very low. If these checks fail, the system defaults to examining all documents to preserve recall.

Datasets

The experiments were conducted using data from the CLEF 2017 e-Health Lab Task 2 "Technology Assisted Reviews in Empirical Medicine". This dataset involved 30 Diagnostic Test Accuracy systematic reviews, for which participants were provided with documents retrieved by complex Boolean queries. The task required participants to rank these documents based on relevance. The dataset included relevance judgments and 33 different ranking runs submitted by 11 groups, offering a diverse set of ranking qualities for evaluation.

Key Insights and Ideas

  • Poisson Process as a Natural Fit: The paper demonstrates that a Poisson process can effectively model the decreasing rate of relevant documents in a ranked list, a common phenomenon in information retrieval.
  • Probabilistic Guarantees: Unlike some previous methods, the Poisson process approach provides a direct way to specify and guarantee a desired level of recall with a high probability, which is crucial for applications like systematic reviews where missing evidence is a significant concern.
  • Robustness to Ranking Quality: A key finding is that the proposed Poisson process method is less sensitive to the quality of the initial search ranking compared to other methods, making it more generally applicable. This is a significant advantage as the quality of rankings can vary widely.
  • Efficiency Gains: The method achieves substantial reductions in manual effort, saving a significant percentage of documents from being reviewed.

Key Results

The proposed Poisson process (PP) method was found to be reliable, achieving the desired recall of 0.7 for at least 95% of topics. Across all 33 CLEF 2017 runs, the PP method required the least effort, saving an average of 42.1% of documents from manual review. This was 4.9% more than the next best method (KM-tuned).

The PP method also showed strong performance across different ranking qualities:

  • It was the most efficient for middle and bottom-ranked runs (saving 48.7% and 14.4% of documents, respectively).
  • It was the second most efficient for the top-ranked runs (saving 53.4% of documents).

The paper also includes visualizations showing how the estimated rate function $\lambda(x)$ from the Poisson process closely matches the actual gain curves of relevant documents in well-ranked lists, indicating the model's accuracy.

Limitations and Future Work

  • Assumptions: The Poisson process model assumes that relevant documents occur with a rate that decreases exponentially. While this often holds, it's not guaranteed, and the paper includes checks for deviations. If these deviations are significant, the method defaults to examining all documents, which is less efficient.
  • Parameter Tuning: While the PP method is less sensitive to ranking quality, the initial sample size ($a$) and batch increase size ($\beta$) for rate estimation might still require some tuning for optimal performance in specific scenarios.
  • Future Work: The authors suggest that the method could be applied to a wider variety of document retrieval problems beyond systematic reviews. Further exploration into adapting the model for different types of document collections or query structures could also be valuable.

Summary updated

BibTeX
@inproceedings{sneyd2019modelling,
  author = {Alison Sneyd and Mark Stevenson},
  title = {{Modelling Stopping Criteria for Search Results using Poisson Processes}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2019},
  doi = {10.18653/v1/d19-1351},
}
Figure