A Uniform Language to Explain Decision Trees

Simple item page
dc.catalogadorvdr
dc.contributor.authorArenas Saavedra, Marcelo Alejandro
dc.contributor.authorBarceló Baeza, Pablo
dc.contributor.authorBustamante Henríquez, Diego Emilio
dc.contributor.authorCaraball Mieri, José Thomas
dc.contributor.authorSubercaseaux, Bernardo
dc.date.accessioned2025-06-12T19:45:59Z
dc.date.available2025-06-12T19:45:59Z
dc.date.issued2024
dc.description.abstractThe formal XAI community has studied a plethora of interpretability queries aiming to understand the classifications made by decision trees. However, a more uniform understanding of what questions we can hope to answer about these models, traditionally deemed to be easily interpretable, has remained elusive. In an initial attempt to understand uniform languages for interpretability, Arenas et al. (2021) proposed FOIL, a logic for explaining black-box ML models, and showed that it can express a variety of interpretability queries. However, we show that FOIL is limited in two important senses: (i) it is not expressive enough to capture some crucial queries, and (ii) its model agnostic nature results in a high computational complexity for decision trees. In this paper, we carefully craft two fragments of first-order logic that allow for efficiently interpreting decision trees: Q-DT-FOIL and its optimization variant OPT-DT-FOIL. We show that our proposed logics can express not only a variety of interpretability queries considered by previous literature, but also elegantly allows users to specify different objectives the sought explanations should optimize for. Using finite model-theoretic techniques, we show that the different ingredients of Q-DT-FOIL are necessary for its expressiveness, and yet that queries in Q-DT-FOIL can be evaluated with a polynomial number of queries to a SAT solver, as well as their optimization versions in OPT-DT-FOIL. Besides our theoretical results, we provide a SAT-based implementation of the evaluation for OPT-DT-FOIL that is performant on industry-size decision trees.
dc.fechaingreso.objetodigital2025-06-12
dc.format.extent11 páginas
dc.fuente.origenWOS
dc.identifier.doi10.24963/kr.2024/6
dc.identifier.issn2334-1033
dc.identifier.urihttps://doi.org/10.24963/kr.2024/6
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/104661
dc.identifier.wosidPPRN:85698984
dc.information.autorucEscuela de Ingeniería; Arenas Saavedra, Marcelo Alejandro; 0000-0003-3678-1868; 81488
dc.information.autorucEscuela de Ingeniería; Barceló Baeza, Pablo; 0000-0003-2293-2653; 13516
dc.information.autorucEscuela de Ingeniería; Bustamante Henríquez, Diego Emilio; 0009-0001-3987-8625; 1064703
dc.information.autorucEscuela de Ingeniería; Caraball Mieri, José Thomas; S/I; 223344
dc.language.isoen
dc.pagina.final70
dc.pagina.inicio60
dc.publisherInternational Joint Conferences on Artificial Intelligence (IJCAI)
dc.revistaArxiv
dc.rightsacceso abierto
dc.subject.ddc620
dc.subject.ods09 Industry, innovation and infrastructure
dc.subject.odspa09 Industria, innovación e infraestructura
dc.titleA Uniform Language to Explain Decision Trees
dc.typepreprint
sipa.codpersvinculados81488
sipa.codpersvinculados13516
sipa.codpersvinculados1064703
sipa.codpersvinculados223344
sipa.trazabilidadWOS;2024-08-31
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
kr2024-0006-arenas-et-al.pdf
Size:
330.36 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de revistas