Heavy Sets with Applications to Interpretable Machine Learning Diagnostics

Dmitry M. Malioutov, Sanjeeb Dash, Dennis WeiAISTATS 2023 · OpenReview

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.

Localization of planted regions with and without penalty. The top plot shows how a standard search over-expands the region, while the bottom plot shows how a Lagrangean penalty correctly identifies the core anomalous region.

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.

Recovery performance vs. planted mean. The chart shows the fraction of correctly recovered regions (yellow) and features (blue) as the signal strength increases.

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

Abstract

ML models take on a new life after deployment and raise a host of new challenges: data drift, model recalibration and monitoring. If performance erodes over time, engineers in charge may ask what changed – did the data distribution change, did the model get worse after retraining? We propose a flexible paradigm for answering a variety of model diagnosis questions by finding heaviest-weight interpretable regions, which we call heavy sets. We associate a local weight describing model mismatch at each datapoint, and find a simple region maximizing the sum (or average) of these weights. Specific choices of weights can find regions where two models differ the most, where a single model makes unusually many errors, or where two datasets have large differences in densities. The premise is that a region with overall elevated errors (weights) may discover statistically significant effects despite individual errors not standing out in the noise. We focus on interpretable regions defined by sparse AND-rules (conjunctive rule using a small subset of available features). We first describe an exact integer programming (IP) formulation applicable to smaller data-sets. As the exact IP is NP-hard, we develop a greedy coordinate-wise dynamic-programming based formulation. For smaller datasets the heuristic often comes close in accuracy to the IP in objective, but it can scale to datasets with millions of examples and thousands of features. We also address statistical significance of the detected regions, taking care of multiple hypothesis testing and spatial dependence challenges that arise in model diagnostics. We evaluate our proposed approach both on synthetic data (with known ground-truth), and on well-known public ML datasets.
BibTeX
@inproceedings{malioutov2023heavy,
  author = {Dmitry M. Malioutov and Sanjeeb Dash and Dennis Wei},
  title = {{Heavy Sets with Applications to Interpretable Machine Learning Diagnostics}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=S71Jd3LenL},
}
Figure