TL;DR
This paper introduces a novel two-stage conformal risk control framework designed for sequential machine learning systems like ranked retrieval. By adapting existing conformal prediction methods, it allows for simultaneous control of prediction uncertainty across multiple stages, offering theoretical guarantees and demonstrating practical effectiveness on large-scale datasets.
What Problem Does This Paper Address?
Many real-world machine learning systems, such as search engines and recommendation platforms, operate in sequential stages. A prime example is ranked retrieval, where an initial retrieval stage identifies a subset of relevant documents from a vast corpus, followed by a ranking stage that orders these documents. This multi-stage architecture is necessary because processing all documents at once is computationally infeasible. However, this sequential nature introduces a significant challenge: errors or uncertainties from the first stage can propagate and amplify in the subsequent stages, making it difficult to reliably quantify and control the overall prediction uncertainty. Existing methods often focus on single-stage processes or address multiple risks independently, failing to leverage the inherent structure of these sequential systems. This paper aims to bridge this gap by developing methods that can effectively control risk across these cascaded stages.
Methods
The core contribution of this paper is a two-stage conformal risk control (tCRC) framework. It builds upon two key ideas:
- Learn-Then-Test (LTT) Framework: This is a general approach for controlling risk in machine learning, adapted here for the two-stage problem.
- Conformal Risk Control (CRC): This framework, previously developed for single-stage systems, is extended to handle the sequential nature of the problem.
The authors propose two main approaches:
- LTT Framework Adaptation: This involves applying hypothesis testing to control risks at each stage sequentially. They leverage the Bonferroni procedure and a fixed-sequence procedure to manage the global family-wise error rate (FWER) across all hypotheses tested in both stages. This method provides strong guarantees but can be computationally intensive.
- Extended CRC Framework: This approach directly extends the single-stage CRC framework to a two-stage setting. It aims to control expected risk at each stage. The authors introduce novel loss functions tailored for ranked retrieval, specifically addressing miscoverage in retrieval and ranking quality. They also propose a data-splitting technique to achieve finite-sample guarantees for the second stage.
A key novelty is the design of stage-specific loss functions:
- Retrieval Loss: Measures the fraction of relevant documents missed by the retrieval stage.
- Ranking Loss: Based on a modified Normalized Discounted Cumulative Gain (nDCG), it evaluates the ranking quality of documents within the retrieved set, prioritizing higher-ranked, more relevant items.
The paper also introduces a method for parameter pair selection by minimizing the empirical set size in the second stage, balancing risk control with efficiency.
Datasets
The proposed methods were evaluated on two large-scale, widely-used datasets for ranked retrieval:
- MSLR-Web
- Yahoo LTRC
These datasets are standard benchmarks in the learning-to-rank community. The authors split these datasets into calibration and test sets for training and evaluation, respectively.
Key Insights and Ideas
- Sequential Risk Control is Crucial: The paper highlights that simply controlling risk in the final stage is insufficient. The first stage's performance significantly impacts the second stage's ability to control risk and overall system effectiveness.
- Leveraging Monotonicity: The proposed loss functions are designed to be non-increasing and right-continuous with respect to their tuning parameters. This monotonicity is key to efficiently applying conformal risk control techniques.
- Tailored Loss Functions Matter: Developing loss functions that specifically capture the objectives of retrieval (covering relevant documents) and ranking (ordering them by relevance) is essential for effective two-stage risk control.
- Trade-offs Exist: Different methods (LTT, tCRC, tCRC-s) exhibit varying trade-offs between risk control, prediction set size, and recall/precision, offering flexibility based on specific application needs.
Key Results
The experiments on MSLR-Web and Yahoo LTRC datasets demonstrate that the proposed tCRC and tCRC-s methods effectively control risks at the specified levels (α₁, α₂).
- Risk Control: Both methods consistently achieve empirical risks close to or below the target levels, validating their theoretical guarantees.
- Set Size vs. Recall: The tCRC method, when optimizing for set size, achieves smaller prediction sets in the second stage compared to LTT, while maintaining competitive recall rates.
- LTT Conservatism: The LTT approach, while providing strong guarantees, tends to be more conservative, often resulting in larger prediction sets.
- tCRC-s Sensitivity: The data-splitting approach (tCRC-s) shows sensitivity to changes in risk levels, particularly α₁, and its performance can be impacted by the unknown parameter λ₀.
Limitations and Future Work
- Unknown Parameter λ₀: The tCRC-s method's reliance on an unknown parameter λ₀, which needs to be estimated, is a practical limitation.
- Non-Monotone Risk Functions: The paper acknowledges that for non-monotone risk functions, additional monotonization procedures are required, which can add complexity.
- Generalization to K Stages: The authors suggest extending the framework to handle more than two sequential stages (K > 2), which is a natural next step for more complex systems.
- Alternative Objective Functions: While set size minimization is explored, other objectives for parameter selection (e.g., maximizing precision or recall) could be investigated.
- Computational Efficiency: Further research into optimizing the computational efficiency of these methods, especially for very large-scale applications, is warranted.
Summary updated