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:
- 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.
- 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.
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.
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