A logic-based language for querying decision tree explanations
Loading...
Date
2025
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
La IA Explicable, el campo de investigación que estudia métodos para comprender las respuestas de modelos de aprendizaje de máquina, ha crecido sustancialmente junto con la necesidad de entender mejor las decisiones de estos modelos. Este trabajo responde al llamado de Arenas et al., 2021, quienes propusieron la lógica de interpretabilidad de primer orden (FOIL): un lenguaje declarativo agnóstico al modelo, basado en lógica de primer orden, que captura diversas nociones de explicabilidad. Primeramente, se analiza formalmente FOIL, demostrando sus limitaciones inherentes tanto en expresividad como en complejidad. Para superar estas deficiencias, se introduce la lógica DT-FOIL, una lógica diseñada para árboles de decisión que garantiza evaluación en tiempo polinomial al incorporar predicados específicos de arboles y restringir la cuantificación. Aunque DT-FOIL proporciona una base tratable, su expresividad es limitada. Consecuentemente, se proponen dos extensiones: Q-DT-FOIL y OPT-DT-FOIL. Q-DT-FOIL agrega cuantificación general, ampliando significativamente el alcance de las explicaciones expresables. Se establece que su problema de evaluación extiende la Jerarquía Booleana, mientras que su problema de cómputo es intratable bajo supuestos de complejidad estándar. En contraste, O PT-DT-FOIL está diseñada para computar instancias óptimas que satisfacen una propiedad dada con respecto a un orden parcial estricto. Este diseño enfocado permite a O PT-DT-FOIL capturar explicaciones óptimas cruciales, asegurando que su problema de cómputo sea tratable accediendo a un oráculo NP. Finalmente, para materializar el valor practico de los marcos teóricos, se presenta GoExpDT, una librería de Golang que implementa tanto Q-DT-FOIL como OPT-DT-FOIL. Aprovechando solucionadores SAT modernos como oráculos NP, GoExpDT proporciona un motor de consultas eficiente. Los resultados experimentales confirman su capacidad para manejar consultas de explicabilidad complejas sobre árboles de decisión de tamaño industrial en un tiempo manejable, afirmando la viabilidad del enfoque propuesto. Este trabajo representa un paso significativo hacia una base uniforme y práctica para la explicabilidad de árboles de decisión.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2025.
Keywords
Explicabilidad, Interpretabilidad, Aprendizaje de máquina, Lógica