Additive Models Explained: A Computational Complexity Approach

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: (i) 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; (ii) 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; (iii) significant complexity distinctions appear for obtaining explanations in regression tasks versus classification tasks in GAMs; and (iv) 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.

Beyond the direct contributions that our results offer of both efficient algorithms and intractability outcomes, they also uncover several surprising insights into the computational nature of generating explanations for GAMs, as highlighted below:

• The complexity of computing explanations for GAMs depends heavily on the input domain, unlike other ML models where a variation based on the input domain is not observed. We show that for most explanation types we studied -like sufficient explanations, contrastive explanations, and Shapley values -computing explanations becomes exponentially harder in continuous and discrete settings compared to enumerable discrete ones. An interesting exception is the feature redundancy explanation, which is actually exponentially easier in the continuous case. This significant sensitivity to the input domain is surprising since it appears to be unique to additive models, as other ML models (e.g., decision trees, tree ensembles, neural networks) do not exhibit such diversity in complexity across input domains.

• The complexity of obtaining explanations for GAMs largely depends on their component models, but this effect interestingly appears only in certain input domains. We