On the Complexity of Global Necessary Reasons to Explain Classification

Marco Calautti, Enrico Malizia, Cristian Molinaro · 2025

Read On the Complexity of Global Necessary Reasons to Explain Classification by Marco Calautti, Enrico Malizia, Cristian Molinaro (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-06766.txt.

Description

Calautti, Malizia, and Molinaro study in 2025 the cost of computing global reasons that explain how a classifier decides. Local reasons cover one case, while global reasons must hold for any case. Their focus is on the smallest sets of traits that force a given class label.

They run a full complexity study of that task. The study spans natural ways to define smallest, and key families of classifiers from the field. Results sort which forms of the task can be solved fast and which are hard in the worst case. Such maps matter for builders of explainable AI, since they show where exact global reasons are within reach.

Catalog record

CREATORMarco Calautti, Enrico Malizia, Cristian Molinaro
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE110 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-06766

Browse the full library · About the Tower of Babel