Uncertainty quantification is a cornerstone of reliable machine learning, especially in high-stakes fields like medicine or autonomous driving. Conformal Prediction (CP) has emerged as a favorite tool because it provides "distribution-free" guarantees: if you ask for 90% coverage, CP gives you a prediction interval that contains the true value at least 90% of the time.
However, there’s a catch. Standard CP usually only guarantees marginal coverage—the average performance across the whole dataset. In the real world, data is often missing. If your model is 90% accurate on average but fails completely whenever a specific sensor is offline, that’s a major safety risk. This paper, recently published by researchers at Université Paris-Saclay and Capgemini Invent, tackles this "mask-conditional" coverage gap without relying on the traditional (and often problematic) crutch of data imputation.
What Problem Does This Paper Address?
When data is missing, it creates distributional heterogeneity. The relationship between observed features and the target variable can shift dramatically depending on which features are absent.
The standard industry response is to "impute" (fill in) the missing values. But the authors argue that imputation is a double-edged sword:
- It’s expensive: Imputation adds significant computational overhead.
- It destroys information: The fact that a value is missing (the "mask") is often a signal in itself. Imputation hides this pattern, making it harder for CP to adapt its uncertainty intervals to specific missingness scenarios.
Existing CP methods that try to handle missingness often assume the data is Missing Completely at Random (MCAR), which is rarely true in practice. This paper seeks a robust pipeline that provides valid, informative prediction sets under general missingness mechanisms (MAR and MNAR) without ever filling in a single NA.
Methods
The authors propose a framework that is adaptive to missingness patterns. Instead of fixing the data, they fix the feature representation.
- Tree Embeddings: They use tree ensembles (like LightGBM) to handle missing values natively. Trees naturally split data based on whether a value is present or absent. The ensemble induces a deterministic "tree embedding"—essentially a high-dimensional map of where a data point lands in the forest.
- Mask Augmentation: They augment this tree embedding with the raw binary missingness mask ($M$). This ensures the model explicitly "knows" what is missing.
- Regularized Quantile Learning: They learn a score threshold function by solving a regularized optimization problem using a pinball loss. By carefully choosing the penalty matrix ($J$), they can target different levels of validity:
- Coordinate-wise validity: Ensuring coverage when a specific feature $j$ is missing.
- Observed-mask validity: Ensuring coverage for every specific pattern seen in the calibration set.
- Approximate conditional validity: Providing theoretical bounds for general, unseen missingness patterns.
To make this computationally feasible, they derive a dual formulation that allows them to find the prediction intervals efficiently using standard solvers.
Datasets
The researchers evaluated their method across a range of environments:
- Synthetic Gaussian Data: Controlled environments to test MCAR, MAR, and a "Pattern Mixture" (PMIX) setting where the covariate distribution shifts linearly with the mask.
- Concrete Compressive Strength: A semi-synthetic benchmark where they manually introduced missingness into a real-world dataset of 8 continuous features.
- MIMIC-IV Length-of-Stay (LOS): A high-dimensional (300 features) real-world medical dataset. This represents a "wild" missingness scenario where measurements are irregular and sparse.
Key Insights and Ideas
- Trees are "Missingness-Aware": Tree-based models are uniquely suited for this task because their splitting logic inherently accounts for the presence or absence of data. As shown in Figure 3, using tree embeddings is critical; without them (using only the mask), coverage drops significantly below the target.
- Imputation is Not Required: By preserving the mask and using embeddings, the model can learn "mask-specific" uncertainty. This avoids the task-dependent overhead and potential biases introduced by imputation.
- Adaptivity vs. Conservatism: A major challenge in conditional CP is that being too specific can lead to intervals that are so wide they are useless. This framework allows for a "smooth" trade-off, providing tight intervals for common masks and becoming more conservative only for rare, "difficult" patterns.
Key Results
The proposed method, "Ours," consistently outperformed baselines in maintaining the target 90% coverage while keeping intervals informative.
- Subgroup Reliability: In coordinate-wise tests (Table 1), the method maintained coverage near the 90% nominal level across all missingness mechanisms.
- Handling Heterogeneity: In the PMIX setting (where missingness strongly correlates with the data distribution), the method significantly reduced shortfall risk (the amount of undercoverage) compared to standard CP and other advanced baselines like MDA-Exact or Weighted-CP.
- Rare Mask Performance: As seen in Figure 2, even for masks that appeared fewer than 10 times in the calibration set, the empirical coverage remained centered around the 0.9 target.
Limitations and Future Work
While powerful, the method has some trade-offs:
- Computational Cost: The exact dual optimization path is slower than simple CP baselines, particularly as the number of trees in the embedding grows. However, it remains much more feasible than "Nested" CP methods in high dimensions.
- Regime-Specific Theory: The theoretical guarantees for general, unseen masks are approximate and depend on the quality of the tree representation and certain regularity conditions.
- Future Directions: The authors suggest extending this work to achieve even richer $X$-conditional validity (beyond just the mask) and exploring more complex embedding models.
In summary, this paper provides a robust path forward for uncertainty quantification in the messy, "holey" datasets common in real-world applications, proving that sometimes, the best way to handle missing data is to embrace the gaps rather than trying to fill them.
Summary updated