Abstract
Machine learning models face significant challenges post-deployment, including data drift, performance erosion, and the need for continuous monitoring. We propose "heavy sets," a flexible framework for identifying simple, interpretable regions (defined by sparse AND-rules) that maximize an aggregate weight of model mismatch or error. We develop an exact integer programming (IP) formulation for small datasets and a scalable greedy dynamic-programming (DP) heuristic for large-scale applications. Our approach incorporates statistical safeguards to handle multiple hypothesis testing and spatial dependence, ensuring that detected regions are statistically significant. We validate our framework on synthetic benchmarks and real-world datasets, demonstrating its utility in pinpointing specific sub-populations where models fail or data distributions shift.
Introduction
Once an ML model is deployed, engineers must monitor not just if it is failing, but where and why. Traditional diagnostic methods often focus on individual outliers, which may be noise, or global metrics, which obscure localized failures. We address this gap by finding interpretable regions—such as "High BMI AND High Blood Pressure"—that exhibit high aggregate weights of errors or mismatches. By focusing on regions with overall elevated weights, we can discover statistically significant effects even when individual errors do not stand out from the noise.
Methodology: Finding Heavy Sets
The core mathematical objective is to identify a region $R$ in the feature space that maximizes the sum (or average) of weights $w_t$ assigned to each datapoint. These weights are flexible and can represent prediction errors, differences between two models, or changes in data density.
- Sparse AND-rules: To ensure interpretability, regions are restricted to simple conjunctive rules (e.g., $x_1 > a \text{ AND } x_2 < b$).
- Integer Programming (IP): An exact IP formulation provides globally optimal solutions for smaller datasets.
- Greedy DP-Heuristic: For large-scale data, we propose a coordinate-descent approach that solves 1D subproblems exactly using a modified version of Kadane’s algorithm. This heuristic scales linearly with the number of observations and features.
The Localization Paradox
A significant challenge in finding heavy sets is the "localization paradox." In a standard maximum-sum search, the algorithm often returns regions that are far too large because it continues to add points as long as the aggregate sum increases, even marginally. We demonstrate that adding a small Lagrangean penalty ($\delta$) is essential for "shrinking" the detected region to its true, informative core.
Statistical Rigor
To prevent the discovery of "heavy" regions that are merely products of random chance, we employ permutation tests and adjust for spatial correlation. Standard statistical tests often overstate significance by assuming independent errors; by using clustered standard errors, we provide a more robust assessment of whether a model's failure in a specific region represents a real pattern or a fluke.
Empirical Evaluation
Synthetic Recovery
We evaluated the framework's ability to recover ground-truth anomalous regions planted in Gaussian noise. As the signal-to-noise ratio (represented by the planted mean) increases, the recovery performance of both the region overlap and the specific features improves significantly.
Real-World Case Studies
- Folktables: On a dataset of 1.7M observations, the method identified a 3-feature sub-population with an 84.2% high-income rate, compared to a 39% baseline.
- UCI Electricity: The framework successfully identified a region where a Random Forest significantly outperformed a Logistic Regression model (a 0.22 difference in predicted probability), even after correcting for spatial correlation.
Conclusion
The heavy sets framework provides a scalable and interpretable tool for ML diagnostics. By combining optimization techniques with statistical safeguards, it allows practitioners to move beyond global metrics and pinpoint the specific sub-populations where model performance or data distributions have drifted. Future work will explore extending these rules to more complex structures like Disjunctive Normal Form (DNF) rules or decision trees.
Summary updated