Introduction
As machine learning models become increasingly complex, the need for interpretable explanations has grown critical. Popular "post-hoc" explainers like LIME and SHAP attempt to demystify black-box behavior by training simple, interpretable models on local perturbations of an input. However, these methods often suffer from a lack of user control, weak theoretical guarantees on fidelity, and vulnerability to adversarial attacks that can hide underlying model bias.
The CLIME Framework
To address these challenges, we introduce CLIME (Constraint-driven LIME), a novel framework that incorporates domain knowledge into the explanation process via Boolean constraints. Unlike traditional methods that rely on random noise, CLIME treats the perturbation process as a constrained sampling problem.
The framework consists of several key components:
- Boolean Constraints: Users can define the "neighborhood" of an instance using Boolean formulas. This allows for the enforcement of integrity constraints (e.g., preventing impossible feature combinations) or specific distance-based requirements.
- Formal Sampling: CLIME utilizes state-of-the-art SAT-based samplers (such as WAPS and UniGen3) to ensure that perturbations are distributed almost uniformly within the valid constraint space.
- Certified Fidelity: By leveraging the AA-algorithm—an optimal Monte Carlo estimation technique—CLIME provides a "Probably Approximately Correct" (PAC) estimate of fidelity. This gives users a mathematically rigorous confidence interval for how well the explanation matches the black box.
- Model-Agnostic Design: CLIME remains model-agnostic, requiring no knowledge of the internal logic of the black box it explains.
Experimental Evaluation
CLIME was evaluated across standard tabular datasets (Bank Marketing, Adult Census, Recidivism, and Lending Club) and a suite of 150 logic benchmarks derived from binarized neural networks.
Performance and Accuracy
A significant advantage of CLIME is its efficiency. The certification framework is, on average, 7.5x faster than previous state-of-the-art methods based on ApproxMC for estimating fidelity.
Furthermore, the inclusion of domain knowledge directly improves explanation quality. In tests on the Bank dataset, adding integrity constraints increased explanation fidelity from 0.90 to 0.98, demonstrating that constraints help produce more "truthful" local models.
Robustness Against Adversarial Attacks
Adversarial models often hide bias by detecting when they are being sampled by an explainer (Out-of-Distribution detection). CLIME counters this by using Hamming distance constraints to keep samples "In-Distribution." In experiments against adversarial classifiers designed to hide racial bias, CLIME successfully identified the sensitive feature (race) as the primary explanation in 60% of cases where LIME was completely deceived.
Discussion and Future Work
CLIME demonstrates that constraints are not merely for data integrity; they act as a "zoom" lens, allowing users to drill down into specific subspaces until high-fidelity explanations are achieved. If fidelity is low, it serves as a clear signal that the black box's local behavior is too complex for a linear model to capture.
Current limitations include the reliance on Boolean discretization and the expertise required to write complex constraints. Future work aims to automate constraint mining from data and extend the framework to SMT (Satisfiability Modulo Theories) to handle arithmetic and real-valued data more natively.
Summary updated