Research map / Learning theory and algorithms / Prediction and decision losses
On the Tractability of SHAP Explanations under Markovian Distributions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that exact SHAP score computation is polynomial-time (in FP) for weighted automata, disjoint DNFs and decision trees when features follow Markovian distributions rather than independent ones.
Problem
Exact SHAP computation is NP-hard in general and prior tractability results for trees and circuits rely on feature independence, which is unrealistic; the paper asks whether SHAP is tractable under correlated (Markovian) feature distributions.
Approach
Reformulates SHAP over sequences using pattern languages for coalitions and shows that, under polynomial-time-computable Markovian distributions, the SHAP score reduces to language operations (product, partition constant, projection) that weighted automata and transducers support in polynomial time; d-DNFs and decision trees are reduced to the WA case via sequentialization.
Key results
- SHAP(WA, MARKOV) is shown to be in FP, computable in time polynomial in automaton size, sequence length and alphabet size.
- SHAP for disjoint DNFs under Markovian distributions is in FP, and by reduction so is SHAP for decision trees under Markovian distributions.
- The paper is purely theoretical and presents no empirical experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Compute exact SHAP under polynomial-time computable Markovian distributions | Weighted automata · Weighted automata under Markovian distributions | computational complexity | Helped |
| Compute exact SHAP under Markovian distributions | Disjoint DNFs · Disjoint DNFs under Markovian distributions | computational complexity | Helped |
| Reduce decision-tree SHAP computation to disjoint-DNF SHAP | Decision trees · Decision trees under Markovian distributions | computational complexity | Helped |
Limitations
- Results hold only under the Markovian assumption and polynomial-time-computable distributions with strictly positive parameters.
- No experiments or implementation are provided to validate the practical runtime.
- Extension to higher-order Markov models is only sketched and is expected to be feasible only for small orders.
Experimental setup
Metrics: polynomial-time complexity
Baselines: TreeSHAP
Builds on: SHAP TreeSHAP weighted automata
Closest papers by meaning
- SHAP values via sparse Fourier representation (NeurIPS 2025 · similarity 0.88)
- SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism (NeurIPS 2025 · similarity 0.87)
- Shaping Up SHAP: Enhancing Stability through Layer-Wise Neighbor Selection (AAAI 2024 · similarity 0.86)
- Towards Trustable SHAP Scores (AAAI 2025 · similarity 0.86)
- Provably Accurate Shapley Value Estimation via Leverage Score Sampling (ICLR 2025 · similarity 0.85)
- InstaSHAP: Interpretable Additive Models Explain Shapley Values Instantly (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.