Technical Summary: Beyond Explaining Predictions: Logic-Based Explanations for Confidence in Machine Learning Models

Problem Statement

Machine learning models, particularly in critical domains like healthcare and finance, are increasingly expected to provide not only accurate predictions but also reliable indicators of uncertainty. While logic-based abductive explanations (AXps) have emerged as a rigorous method for interpretability, offering formal guarantees of correctness and minimality, they possess a critical limitation: they focus solely on preserving the predicted class.

Traditional AXps identify minimal subsets of features sufficient to guarantee that any instance satisfying those conditions receives the same classification as the original instance. However, they do not account for the model's predictive confidence. Consequently, a single abductive explanation may cover a set of instances that includes both highly confident predictions and those lying very close to the decision boundary (high uncertainty). In high-stakes applications, this can lead to overconfidence, as users may assume all justified predictions are equally reliable, obscuring the model's actual limitations.

Existing uncertainty-aware explanation methods often rely on attribution or perturbation techniques that estimate uncertainty but lack formal guarantees regarding the set of instances covered. They typically estimate the uncertainty of an explanation rather than constraining the explanation to guarantee a minimum confidence level across all covered instances.

Methodology

1. Minimum Confidence Threshold (MCT)

The authors introduce the concept of the Minimum Confidence Threshold (MCT) to quantify the weakest confidence guarantee provided by an abductive explanation.

• Definition: For a given explanation $\mathcal{E}$, the MCT is the prediction score closest to the decision boundary among all instances satisfying $\mathcal{E}$.
  • For class $+1$, $MCT(\mathcal{E}) = \min_{\mathcal{E} \subseteq \mathbf{x}'} S(\mathbf{x}')$.
  • For class $-1$, $MCT(\mathcal{E}) = \max_{\mathcal{E} \subseteq \mathbf{x}'} S(\mathbf{x}')$.
• Significance: The MCT represents the worst-case predictive confidence for the set of instances covered by the explanation. It is computed by formulating an optimization problem over the symbolic prediction score expression of the model, subject to the constraints of the model encoding and the feature assignments in the explanation.

2. Confidence-Aware Abductive Explanations

Building on MCT, the paper proposes confidence-aware abductive explanations. These are minimal subsets of features that guarantee not only the preservation of the predicted class but also that the prediction score for any satisfying instance meets a user-specified threshold $\tau$.

• Formulation: An explanation $\mathcal{E}$ is confidence-aware with respect to $\tau$ if it is an abductive explanation and:
  • $MCT(\mathcal{E}) \geq \tau$ (for class $+1$)
  • $MCT(\mathcal{E}) \leq \tau$ (for class $-1$)
• Threshold Constraints: The threshold $\tau$ is constrained by the prediction score of the original instance being explained, as the original instance must satisfy the explanation. Thus, $\tau$ cannot demand a confidence level higher than the instance's own score.

3. Algorithmic Approach

The authors adapt the standard feature-removal procedure used for computing traditional AXps (Algorithm 1) to incorporate confidence constraints (Algorithm 2).

• Process: Starting with the full instance, features are iteratively removed. A feature is removed only if the resulting subset of features still satisfies the user-defined confidence threshold $\tau$.
• Optimization: At each step, the algorithm computes the MCT of the candidate explanation using optimization solvers (specifically Z3 for SMT solving).
• Monotonicity: The approach relies on the monotonicity of the confidence-aware condition: if a subset of features fails to meet the confidence threshold, any further reduction (subsets of that subset) will also fail. This ensures the algorithm terminates with a minimal explanation.
• Refinement: The paper also discusses a strategy to recompute explanations from scratch under stricter confidence constraints rather than incrementally extending existing explanations. This allows the search to find alternative minimal subsets that may offer better confidence guarantees without necessarily increasing the explanation size.

Key Contributions

1. Identification of a Gap: The paper demonstrates that traditional abductive explanations often provide substantially weaker confidence guarantees than the confidence associated with the specific instance being explained, potentially misleading users in high-stakes scenarios.
2. MCT Concept: Introduction of the Minimum Confidence Threshold as a formal metric to quantify the weakest confidence guarantee of an explanation.
3. Confidence-Aware Framework: Proposal of a new class of explanations that enforce user-defined confidence thresholds while maintaining the formal guarantees of correctness and minimality.
4. Algorithmic Implementation: Development of an algorithm (Algorithm 2) that integrates MCT computation into the explanation generation process, formulated as an optimization problem over logic-based representations of Gradient-Boosted Trees (GBTs).
5. Empirical Validation: Experimental evaluation showing that confidence-aware explanations consistently improve minimum confidence guarantees with only a modest increase in explanation length, and in many cases, can achieve stronger guarantees without increasing the explanation cardinality at all.

Experimental Results

The framework was evaluated on binary classification tasks using Gradient-Boosted Trees (XGBoost) across four benchmark datasets: MAGIC, Adult, Mushroom, and Spambase.

• Baseline Weakness: Traditional abductive explanations frequently provided confidence guarantees (MCT) significantly lower than the confidence of the original instance. In many cases, the transformed MCT values were close to 0.5 (the decision boundary), even for highly confident predictions.
• Improvement with Constraints: Applying confidence-aware constraints (e.g., requiring 50% or 75% of the original prediction score) consistently shifted the MCT values away from the decision boundary, indicating stronger confidence guarantees.
• Trade-off Analysis:
  • Explanation Size: Stricter confidence requirements generally led to longer explanations (more features). However, the increase was often modest relative to the total number of features. For example, in the Spambase dataset (57 features), a 75% threshold increased the average explanation length from 13.25 to 19.12 features, a relative growth of roughly 10%, while significantly improving confidence.
  • Cardinality Preservation: A significant finding (RQ3) is that stronger confidence guarantees do not always require larger explanations. The study found that for a substantial percentage of instances (ranging from 1% to 34% depending on the dataset and class), alternative explanations with the same cardinality as the original AXp could be found that offered strictly better confidence guarantees. This validates the strategy of recomputing explanations from scratch rather than simply extending existing ones.

Significance and Claims

The paper claims that its proposed approach is particularly suitable for applications where both predictive correctness and confidence are essential for trustworthy decision-making. By integrating confidence guarantees directly into the logic-based explanation process, the framework allows users to explicitly trade explanation succinctness for stronger confidence guarantees.

The authors emphasize that their work addresses a specific limitation in current XAI: the lack of formal guarantees regarding the reliability of the set of instances covered by an explanation. Unlike methods that merely estimate uncertainty, this approach constrains the explanation generation to ensure that every instance satisfying the explanation meets a minimum confidence standard.

The paper remains modest in its scope, noting that while the method is demonstrated on Gradient-Boosted Trees, the approach is applicable to any model providing confidence scores. It suggests future work could extend these concepts to multiclass classification and other logic-based explanation formalisms, but does not claim immediate applicability to those domains without further research.