Optimal Local Explainer Aggregation for Interpretable Prediction

Qiaomei Li, Rachel Cummings, Yonatan MintzAAAI 2022 · DOI

Abstract

In high-stakes domains like precision medicine, the trade-off between the predictive power of "black box" models and the need for human-interpretable explanations is a critical challenge. We present a novel framework that optimally aggregates local explainer models into a near-global explanation using Integer Programming (IP). This approach allows for a precise, mathematically grounded trade-off between explanation coverage and fidelity. Evaluated on complex multi-class healthcare datasets, our IP framework significantly outperforms existing heuristic-based methods, providing a clear Pareto frontier for clinical decision-making.

Introduction

Machine learning models such as deep neural networks and random forests have become indispensable in healthcare for their high accuracy. However, their lack of transparency—the "black box" problem—hinders clinical adoption. To address this, researchers use "explainers": simpler models that approximate the black box's behavior. While global explainers offer full coverage but often low fidelity, local explainers (e.g., LIME, SHAP) provide high fidelity in small neighborhoods but lack broad applicability.

The Aggregation Challenge

A promising middle ground involves selecting a small "budget" of local explainers to cover as much of the data as possible. Selecting the optimal subset is a combinatorial problem. Previous methods, like Submodular Pick, rely on greedy heuristics that lack optimality guarantees. This paper, presented at AAAI-22, introduces a framework to solve this aggregation problem optimally.

Proposed Methodology

We introduce two primary contributions:

  1. Integer Programming (IP) Framework: We reformulate the aggregation problem as a formal optimization task. By defining coverage (the fraction of data explained) and fidelity (the minimum accuracy of local models relative to the black box), we use IP solvers to find the mathematically optimal set of explainers for a given budget and fidelity threshold.
  2. Information-Filter Local Explainers: To enhance interpretability, we developed a local explainer algorithm using Fast Forward Feature Selection (FFFS). This method uses mutual information to select only the most relevant features, resulting in sparse, readable "local rules" that typically use five or fewer features.

Experimental Results

The framework was tested on healthcare datasets where interpretability is paramount: the Parkinson’s Progression Marker Initiative (PPMI) and a Geriatric Mobility dataset.

Performance in Multi-class Scenarios

Our IP approach demonstrates significant superiority in multi-class settings. While traditional global methods often struggle with fidelity as complexity increases, our framework maintains high performance.

Figure 1: Coverage and Fidelity vs. Budget for the PPMI 5-class dataset. The IP framework allows for high fidelity (e.g., 0.9) while maximizing coverage for a given budget.

As shown in the figure above, for the PPMI 5-class task, the IP(0.9) variant maintains a fidelity of approximately 90% while achieving substantial coverage as the budget increases, far surpassing heuristic baselines like Submodular Pick.

The Coverage-Fidelity Trade-off

A key advantage of the optimization-based approach is the ability to generate a "Pareto frontier"—a curve representing the best possible coverage for any given level of fidelity.

Figure 2: The Pareto frontier for the PPMI-Binary dataset, showing the optimal trade-off between coverage and fidelity for different budgets (5, 10, and 15).

This frontier, illustrated for the PPMI-Binary dataset, provides a clear menu of choices for decision-makers. Clinicians can use these curves to select an explanation strategy that meets their specific requirements for transparency and accuracy.

Conclusion

The proposed IP framework provides a robust, optimal solution for aggregating local explanations. By outperforming greedy heuristics and offering a clear menu of trade-offs via the Pareto frontier, this method bridges the gap between high-performance black box models and the interpretability required in clinical practice. Future work will focus on reducing computational complexity for massive datasets and automating the discovery of optimal local radii.

Summary updated

BibTeX
@inproceedings{li2022optimal,
  author = {Qiaomei Li and Rachel Cummings and Yonatan Mintz},
  title = {{Optimal Local Explainer Aggregation for Interpretable Prediction}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i11.21458},
}
Figure