Probabilistic Relaxation for Succinct Model Explanations

25 concepts13 papers1 proposal

Imagine a machine learning model that evaluates loan applications. The model denies a specific applicant based on dozens of interacting features. To understand this decision, we might look for a formal explanation—specifically, a "sufficient reason" or "abductive explanation." In formal explainable AI (XAI), a subset of features is considered a sufficient reason if fixing those features guarantees the model's prediction, regardless of what values the remaining features take.

Suppose the model denies the loan because Income = Low and Credit Score = Poor. Does this pair of features strictly guarantee denial? What if the applicant's Savings = 10 Million Dollars? Or what if their Collateral = Prime Real Estate? To provide a 100% deterministic guarantee, a formal explanation must include enough features to rule out every imaginable counter-scenario, no matter how absurd or highly improbable.

Consequently, exact logical explanations become bloated, often containing dozens of features just to cover rare edge cases. They violate human cognitive limits and fail to provide actionable clarity.

The Computational Wall of Exact Explanations

This rigidity doesn't just hurt human readability; it breaks our algorithms. As proven by Stephan Waeldchen et al., finding the exact smallest subset of features that guarantees a classifier's decision is $\text{NP}^{\text{PP}}$-complete, and even approximating its size is NP-hard.

Even for models often praised for their inherent interpretability, like decision trees, Alexander Kozachinskiy et al. and Marcelo Arenas et al. demonstrated that finding minimal sufficient reasons remains computationally intractable. The core issue is that deterministic explanations require checking all possible completions of a partial input. In high-dimensional spaces, this exhaustive verification forces us into a computational corner.

As Shahaf Bassan et al. observe, there is a critical need to transition away from these rigid deterministic constraints and toward frameworks that reflect the stochastic nature of data and machine learning models.

The Core Mechanism: Probabilistic Relaxation

To break through this wall, a shared research direction has emerged: probabilistic relaxation. Instead of demanding that a feature subset guarantees a prediction 100% of the time, we ask that it maintains the prediction with a high probability (e.g., $\ge 95\%$ or $1-\epsilon$) under a natural distribution of the remaining features.

This concept manifests across several frameworks:

  • Probabilistic Sufficient Explanations (PSEs): Introduced by Eric Wang et al. to balance simplicity with formal guarantees.
  • Probabilistic Abductive Explanations: Explored by Yacine Izza et al. to compress explanations down to human cognitive limits.
  • $(\delta, \epsilon)$-Sufficient Reasons: Formulated by Bernardo Subercaseaux et al. to introduce explicit error tolerances into formal explanations.
  • Anchors: An earlier, model-agnostic instantiation by Marco Túlio Ribeiro et al. that uses local precision thresholds to ensure an "if-then" rule holds with high probability.

By shifting from absolute logical certainty to a high-probability threshold, we accommodate noise and rare edge cases rather than letting them invalidate an otherwise excellent explanation.

Why It Works: The Non-Linear Payoff of Uncertainty

Why does relaxing the certainty requirement by just a few percentage points yield such massive benefits?

The answer lies in the distribution of real-world data. In high-dimensional spaces, the vast majority of feature combinations that could theoretically exist never actually occur. A deterministic explanation is forced to defend against adversarial, impossible-in-practice feature combinations (such as an applicant who has 40 years of employment history but is only 18 years old).

By introducing a probability threshold, we allow the explanation mechanism to ignore this long tail of rare or impossible edge cases.

Deterministic Explanation (100% Certainty)
└── Must cover: [Common Cases] + [Rare Edge Cases] + [Adversarial Combinations]
└── Result: Large, unreadable feature set.

Probabilistic Explanation (e.g., 95% Certainty)
└── Must cover: [Common Cases]
└── Result: Small, succinct feature set (ignores the long tail).

As Bernardo Subercaseaux et al. and Kuldeep S. Meel et al. demonstrate, a minor reduction in the required confidence level triggers a dramatic, non-linear drop in the number of features needed for the explanation.

Louenas Bounia et al. show that this relaxation can compress complex model decisions down to a human-intelligible size of approximately seven features while maintaining high predictive confidence. Similarly, Stylianos Loukas Vasileiou et al. note that in uncertain environments, an explanation is far more effective if it prioritizes high-likelihood conditions over logically airtight but highly improbable events.

Restoring Computational Tractability

Beyond making explanations readable, probabilistic relaxation fundamentally alters the computational complexity landscape. By bypassing the strict counting requirements of exact logical verification, we can leverage optimization and structural properties to find explanations efficiently.

Polynomial-Time Linear Explanations

While computing exact explanations for linear models can be surprisingly difficult due to combinatorial counting, Bernardo Subercaseaux et al. proved that allowing a small error margin ($\epsilon$) transforms the search for concise justifications into a polynomial-time problem.

Supermodular Minimization

Louenas Bounia et al. proved that the mathematical structure of probabilistic explanations allows the search to be framed as a supermodular minimization problem. This enables greedy algorithms that are mathematically guaranteed to be near-optimal and run orders of magnitude faster than exact solvers.

Structural and Parameterized Tractability

For discrete models like decision trees, lists, and sets, Mateusz Rychlicki developed a unified algorithmic framework showing that these difficult counting problems become fixed-parameter tractable when certain structural properties of the model are bounded. For complex tree ensembles like Random Forests, Nico Potyka et al. demonstrated that mapping the ensemble to Bipolar Argumentation Graphs and Markov Networks allows researchers to use probabilistic inference to efficiently extract nearly-sufficient reasons.

Relaxing Other Constraints

This philosophy of strategic relaxation extends to other interpretability trade-offs as well. For instance, when evaluating removal-based explanations (like SHAP), Yifan Zhang et al. showed that relaxing the strict efficiency constraint—the requirement that feature weights sum exactly to the model's output—allows algorithms to much more accurately capture a model's primary logic and feature interactions.

By abandoning the demand for absolute certainty, probabilistic relaxation resolves the fundamental tension between mathematical rigor and human cognitive limits, turning an intractable logical problem into a practical, scalable tool for understanding complex AI decisions.

Key Foundational Work

Probabilistic Sufficient Explanations (2021) — contributed 2 concept elements to this direction.
The Computational Complexity of Understanding Binary Classifier Decisions (2021) — contributed 2 concept elements to this direction.
Anchors: High-Precision Model-Agnostic Explanations (2018) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 14 papers
  2. Version 1 · 2026-10-04 · 23 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_probabilistic_explanation_relaxation_b4fc278c,
  title = {probabilistic explanation relaxation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/probabilistic-explanation-relaxation/rdr_b4fc278c5d2940da940a4c14f981ade1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_probabilistic_explanation_relaxation_b4fc278c_v2,
  title = {probabilistic explanation relaxation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/probabilistic-explanation-relaxation/rdr_b4fc278c5d2940da940a4c14f981ade1/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake