Metraipolis › archive › dc_c6feed45bb92

Do Feature Interactions Break Explainability? Provable Explanations for Any-Order Neural Additive Models — arXiv:2611.11224

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.11224
License (as archived): CC0-1.0
Archived: 2026-11-10T18:43:12.409Z
SHA-256 of the archived text: 5d18d2aa61fb5e06d05be468946c3a1576b6cf39f2d80aba5a1a5f52e4dacef7
Stable URL of this page: https://metraipolis.com/documento/dc_c6feed45bb92

How to cite

Do Feature Interactions Break Explainability? Provable Explanations for Any-Order Neural Additive Models — arXiv:2611.11224 — arXiv (en), https://arxiv.org/abs/2611.11224 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c6feed45bb92 (Metraipolis archive dc_c6feed45bb92, sha256 5d18d2aa61fb5e06d05be468946c3a1576b6cf39f2d80aba5a1a5f52e4dacef7)

BibTeX

@misc{dcc6feed45bb92,
  title = {Do Feature Interactions Break Explainability? Provable Explanations for Any-Order Neural Additive Models — arXiv:2611.11224},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.11224},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c6feed45bb92; sha256 5d18d2aa61fb5e06d05be468946c3a1576b6cf39f2d80aba5a1a5f52e4dacef7},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.11224. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Post-hoc explanation methods for neural networks are often heuristic and lack provable guarantees. A common alternative to such methods that was studied in recent years is to compute a cardinally-minimal subset of input features that is provably sufficient to determine the model's prediction. For general neural networks, however, finding such explanations is computationally intractable. In contrast, recent work showed that this problem becomes more tractable for a particular family of neural networks, namely neural additive models (NAMs), though standard NAMs are highly restrictive because they exclude feature interactions altogether. In this work, we study the computation of provably minimal and sufficient explanations for neural networks with restricted feature interactions, bridging the gap between fully general neural networks and purely additive models. We first prove that even with constant-order interactions, the problem is $\Sigma_2^P$-hard, implying that worst-case exponential complexity is unavoidable. We then identify two provably tractable settings: one based on sparsity in the interaction structure and another based on a stronger interaction-aware notion of sufficiency. Under either of these settings, we develop algorithms that compute provable explanations for neural networks with any-order interactions while retaining much of the computational efficiency of additive models. Empirically, we show that these explanations are significantly smaller and faster to obtain than those produced by standard algorithms, while being derived from models that achieve much higher accuracy than standard NAMs. Overall, our results help expand the class of neural networks that admit efficient provable explanations, while clarifying the fundamental role of feature interactions in shaping their complexity.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Artificial Intelligence (cs.AI); Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2611.11224 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-10T18:37:37.630Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).