Additive Models Explained: A Computational Complexity Approach

• URL: http://arxiv.org/abs/2510.21292v1
• Date: Fri, 24 Oct 2025 09:40:30 GMT
• Title: Additive Models Explained: A Computational Complexity Approach
• Abstract summary: Generalized Additive Models (GAMs) are commonly considered *interpretable* within the ML community.<n>We analyze the *computational complexity* of generating different explanations for various forms of GAMs across multiple contexts.
• Score: 9.380879437204277
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Generalized Additive Models (GAMs) are commonly considered *interpretable* within the ML community, as their structure makes the relationship between inputs and outputs relatively understandable. Therefore, it may seem natural to hypothesize that obtaining meaningful explanations for GAMs could be performed efficiently and would not be computationally infeasible. In this work, we challenge this hypothesis by analyzing the *computational complexity* of generating different explanations for various forms of GAMs across multiple contexts. Our analysis reveals a surprisingly diverse landscape of both positive and negative complexity outcomes. Particularly, under standard complexity assumptions such as P!=NP, we establish several key findings: (1) in stark contrast to many other common ML models, the complexity of generating explanations for GAMs is heavily influenced by the structure of the input space; (2) the complexity of explaining GAMs varies significantly with the types of component models used - but interestingly, these differences only emerge under specific input domain settings; (3) significant complexity distinctions appear for obtaining explanations in regression tasks versus classification tasks in GAMs; and (4) expressing complex models like neural networks additively (e.g., as neural additive models) can make them easier to explain, though interestingly, this benefit appears only for certain explanation methods and input domains. Collectively, these results shed light on the feasibility of computing diverse explanations for GAMs, offering a rigorous theoretical picture of the conditions under which such computations are possible or provably hard.

Related papers

• Unifying Formal Explanations: A Complexity-Theoretic Perspective [9.350838775251075]
  We show that complexity of computations is influenced by three key properties of the value function.<n>We show that even highly simplified versions of these explanations become NP-hard to compute in the corresponding local explainability setting.
  arXiv  Detail & Related papers  (2026-02-20T11:52:26Z)
• On the Hardness of Computing Counterfactual and Semifactual Explanations in XAI [5.172213041663734]
  We show that in many cases, generating explanations is computationally hard.<n>We discuss the implications for the XAI community and for policymakers seeking to regulate explanations in AI.
  arXiv  Detail & Related papers  (2026-01-14T13:02:24Z)
• What makes an Ensemble (Un) Interpretable? [6.760285368641258]
  Ensemble models are widely recognized in the ML community for their limited interpretability.<n>Despite this folklore recognition, there remains a lack of rigorous mathematical understanding of what makes an ensemble (un)-interpretable.
  arXiv  Detail & Related papers  (2025-06-09T20:38:04Z)
• Efficient Contrastive Explanations on Demand [7.109897082275965]
  This paper proposes novel algorithms to compute the so-called contrastive explanations for machine learning models.<n>The paper also proposes novel algorithms for listing explanations and finding smallest contrastive explanations.
  arXiv  Detail & Related papers  (2024-12-24T08:24:10Z)
• MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs [80.96119560172224]
  MathGAP generates problem statements and chain-of-thought reasoning traces according to specifications about their arithmetic proof structure.<n>Using MathGAP, we find that LLMs show a significant decrease in performance as proofs get deeper and wider.
  arXiv  Detail & Related papers  (2024-10-17T12:48:14Z)
• Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation [0.9558392439655016]
  The ability to interpret Machine Learning (ML) models is becoming increasingly essential. Recent work has demonstrated that it is possible to formally assess interpretability by studying the computational complexity of explaining the decisions of various models.
  arXiv  Detail & Related papers  (2024-08-07T17:20:52Z)
• Local vs. Global Interpretability: A Computational Complexity Perspective [0.9558392439655016]
  We use computational complexity theory to assess local and global perspectives of interpreting ML models. Our findings offer insights into both the local and global interpretability of these models. We believe that our findings demonstrate how examining explainability through a computational complexity lens can help us develop a more rigorous grasp of the inherent interpretability of ML models.
  arXiv  Detail & Related papers  (2024-06-05T06:23:49Z)
• Explaining Text Similarity in Transformer Models [52.571158418102584]
  Recent advances in explainable AI have made it possible to mitigate limitations by leveraging improved explanations for Transformers. We use BiLRP, an extension developed for computing second-order explanations in bilinear similarity models, to investigate which feature interactions drive similarity in NLP models. Our findings contribute to a deeper understanding of different semantic similarity tasks and models, highlighting how novel explainable AI methods enable in-depth analyses and corpus-level insights.
  arXiv  Detail & Related papers  (2024-05-10T17:11:31Z)
• Shape Arithmetic Expressions: Advancing Scientific Discovery Beyond Closed-Form Equations [56.78271181959529]
  Generalized Additive Models (GAMs) can capture non-linear relationships between variables and targets, but they cannot capture intricate feature interactions. We propose Shape Expressions Arithmetic ( SHAREs) that fuses GAM's flexible shape functions with the complex feature interactions found in mathematical expressions. We also design a set of rules for constructing SHAREs that guarantee transparency of the found expressions beyond the standard constraints.
  arXiv  Detail & Related papers  (2024-04-15T13:44:01Z)
• Amortized Inference for Causal Structure Learning [72.84105256353801]
  Learning causal structure poses a search problem that typically involves evaluating structures using a score or independence test. We train a variational inference model to predict the causal structure from observational/interventional data. Our models exhibit robust generalization capabilities under substantial distribution shift.
  arXiv  Detail & Related papers  (2022-05-25T17:37:08Z)
• Model-agnostic multi-objective approach for the evolutionary discovery of mathematical models [55.41644538483948]
  In modern data science, it is more interesting to understand the properties of the model, which parts could be replaced to obtain better results. We use multi-objective evolutionary optimization for composite data-driven model learning to obtain the algorithm's desired properties.
  arXiv  Detail & Related papers  (2021-07-07T11:17:09Z)
• Deducing neighborhoods of classes from a fitted model [68.8204255655161]
  In this article a new kind of interpretable machine learning method is presented. It can help to understand the partitioning of the feature space into predicted classes in a classification model using quantile shifts. Basically, real data points (or specific points of interest) are used and the changes of the prediction after slightly raising or decreasing specific features are observed.
  arXiv  Detail & Related papers  (2020-09-11T16:35:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.