Browsing by Author "Bustamante Henríquez, Diego Emilio"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    A Uniform Language to Explain Decision Trees
    (International Joint Conferences on Artificial Intelligence (IJCAI), 2024) Arenas Saavedra, Marcelo Alejandro; Barceló Baeza, Pablo; Bustamante Henríquez, Diego Emilio; Caraball Mieri, José Thomas; Subercaseaux, Bernardo
    The 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.
  • Thumbnail Image
    Item
    Towards a generalized uniform language for explainability
    (2024) Bustamante Henríquez, Diego Emilio; Arenas Saavedra, Marcelo Alejandro; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    Explainability, razonamiento sobre decisiones en Aprendizaje de Máquinas, es una área que ha crecido con gran interés. Construímos sobre efuerzos como los de Barceló et al. (2020), quienes definieron una estructura que permite comparar la interpretabilidad entre modelos de Aprendizaje de Máquinas. Ellos modelaron las explicaciones como problemas de decisión y estudiaron la complejidad de decidirlas en distintas clases. Y Arenas et al. (2024), quienes propusieron un lenguaje declarativo basado en lógica de primer orden lo suficientemente expresivo para capturar varias nociones de explicabilidad. Capturamos la complejidad de decidir importantes conceptos de explicabilidad sobre decision trees y free binary decision diagrams. Nuestra contribución fueron las nuevas cotas para las consultas DFS y MINIMALDFS que permitieron diseñar EXPLAINER, una lógica generalizada de interpretabilidad con predicados cuya interpretación es independiente de la clase de modelos y una nueva cuantificación sobre las features del modelo. EXPLAINER puede expresar consultas de explicabilidad mientras que su evaluación se puede decidir en la Jerarquía Booleana en las clases citadas. Esto proviene del uso de predicados basados en pruebas polinomiales de satisfacibilidad y tautología. En consecuencia, extendimos nuestros resultados a una larga lista de clases con dichas pruebas. Respecto a la computación de explicaciones, mostramos que la existencia de un algoritmo eficiente equipado con un oráculo NP implica el colapso de la Jerarquía Polinomial. Creamos una extensión sobre la implementación original para soportar la evaluación de EXPLAINER; la principal adaptación fue el nuevo tipo de cuantificación. Nuestros resultados experimentales muestran que los beneficios teóricos se transfieren a nuestra extensión en términos de clases soportadas, expresividad y rendimiento. Creemos estar en un buen camino para encontrar un lenguage general y uniforme para explicabilidad.