Research map / Learning theory and algorithms / Prediction and decision losses
Additive Models Explained: A Computational Complexity Approach
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.
Theoretical complexity analysis of computing sufficient reasons, contrastive reasons, Shapley values, count completions and feature redundancy for generalized additive models (smooth GAMs, NAMs, EBMs) across enumerable discrete, general discrete, and continuous input domains.
Problem
Whether explanations for GAMs, often regarded as interpretable, can be computed efficiently, given the computational complexity of various explanation types under different component models and input domains.
Approach
Systematically maps the complexity of explanation queries (CSR, MSR, MCR, FR, CC, SHAP) across the cross-product of GAM component type, explanation type, and input domain, showing that input domain and component type strongly affect complexity for GAMs unlike other model classes.
Key results
- Explanations (CSR, MSR, MCR, SHAP-regression) for any GAM over enumerable discrete inputs, and smooth GAMs over discrete/continuous inputs, are polynomial-time solvable.
- For NAMs and EBMs over discrete or continuous inputs, CSR is coNP-complete and MCR is NP-complete; CC and SHAP for classification are #P-complete.
- SHAP is polynomial-time for regression GAMs but #P-hard for classification GAMs, a complexity separation unique to SHAP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use enumerable discrete inputs instead of general discrete or continuous inputs | GAMs · CSR, MCR, MSR, CC, and SHAP | computational complexity: PTIME vs. coNP-H, NP-C, or #P-C (depending on explanation and component type) | Helped |
| Use continuous inputs instead of enumerable or general discrete inputs | GAM feature redundancy (FR) · Continuous vs. discrete input domains | computational complexity: PTIME vs. coNP-C for Smooth GAMs | Helped |
| Use spline components rather than neural-network or boosted-tree components | GAMs · General discrete and continuous domains; CSR, MSR, MCR, SHAP | computational complexity: PTIME vs. coNP-H, NP-C, or #P-C (depending on query) | Helped |
| Use spline components rather than neural-network or boosted-tree components | GAMs · Enumerable discrete domain | computational complexity: PTIME for CSR, MSR, and MCR across component types | No clear effect |
| Use regression instead of classification | Smooth GAM SHAP · SHAP | computational complexity: PTIME vs. #P-C | Helped |
| Use regression instead of classification | GAM SHAP with enumerable inputs · SHAP | computational complexity: PTIME vs. #P-C | Helped |
| Use unary encoding and polynomially bounded output | GAMs over enumerable discrete inputs · CC and SHAP-C | computational complexity: #P-C (Pseudo-P) | Helped |
| Express neural networks or tree ensembles additively as NAMs or EBMs | Neural networks and tree ensembles · Enumerable discrete domain; CSR, MSR, MCR, and SHAP-R | computational complexity: PTIME vs. coNP-C, Σ^P_2-C, NP-C, or #P-C (depending on query) | Helped |
| Express neural networks or tree ensembles additively as NAMs or EBMs | Neural networks and tree ensembles · General discrete or continuous domain; MSR | computational complexity: coNP-H, in Δ^P_2 vs. Σ^P_2-C | Helped |
| Express neural networks or tree ensembles additively as NAMs or EBMs | Neural networks and tree ensembles · General discrete or continuous domain; CSR, MCR, FR, CC, and SHAP | computational complexity | No clear effect |
| Use continuous rather than enumerable discrete or general discrete inputs | GAM feature redundancy (FR) · FR | computational complexity: PTIME vs. coNP-C | Helped |
Surprising findings
- Feature redundancy is exponentially easier in the continuous case than in discrete settings for GAMs.
- Complexity of GAM explanations depends on input domain, unlike decision trees, tree ensembles, and neural networks.
Limitations
- Analysis limited to specific explanation definitions and component model types.
- Does not consider high-order interactions or concurvity.
- Pseudo-polynomial results require unary-encoded weights and polynomially bounded output.
Experimental setup
Builds on: linear model explanation complexity formal explainable AI Shapley values
Closest papers by meaning
- Local vs. Global Interpretability: A Computational Complexity Perspective (ICML 2024 · similarity 0.91)
- Provably Explaining Neural Additive Models (ICLR 2026 · similarity 0.90)
- Model Interpretability through the lens of Computational Complexity (NeurIPS 2020 · similarity 0.90)
- InstaSHAP: Interpretable Additive Models Explain Shapley Values Instantly (ICLR 2025 · similarity 0.88)
- Explainable Neural Networks with Guarantee: A Sparse Estimation Approach (AAAI 2025 · similarity 0.87)
- Training Language Models to Explain Their Own Computations (NeurIPS 2026 · similarity 0.86)
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.