Resumen Técnico: WOODELF++

Enunciado del Problema

Los conjuntos de árboles de decisión son omnipresentes en aplicaciones del mundo real, pero interpretar sus predicciones sigue siendo un desafío crítico para la confianza y la toma de decisiones. Tres herramientas principales para interpretar estos modelos son los Gráficos de Dependencia Parcial (PDP), los Gráficos de Dependencia Parcial Conjunta (Joint-PDP) y los Valores de Interacción de Dependencia Parcial (PDIV).

• PDP visualizan cómo una sola característica afecta la predicción promedio del modelo.
• Joint-PDP extienden esto a pares de características para revelar efectos combinados.
• PDIV (específicamente la tarea "Any-Order") cuantifican los efectos de interacción a través de todos los subconjuntos posibles de características para cada fila en un conjunto de datos.

Los métodos actuales del estado del arte, como los de scikit-learn y el algoritmo FastPD (implementado en el paquete GLEX), sufren de una complejidad computacional prohibitiva. Los enfoques ingenuos escalan linealmente con el número de muestras y características, pero exponencialmente con la profundidad del árbol y el número de características involucradas en las interacciones. Para conjuntos de datos grandes (por ejemplo, 400,000 filas) y tareas de interacción complejas (Any-Order-PDIV), los métodos existentes son o bien imprácticamente lentos (tardan días o años) o dependen de aproximaciones que pueden pasar por alto comportamientos críticos del modelo, como discontinuidades abruptas.

Metodología

Los autores presentan WOODELF++, un marco unificado y eficiente para calcular PDP, Joint-PDP y Any-Order-PDIV en conjuntos de árboles de decisión. El enfoque se basa en el trabajo anterior de los autores, WOODELF, que calcula eficientemente los valores SHAP modelando conjuntos de árboles de decisión como funciones Pseudo-Booleanas (PB) representadas en Forma Normal Disyuntiva Ponderada (WDNF).

Las innovaciones técnicas centrales incluyen:

1. Unificación mediante WDNF y Linealidad:
   Los autores formulan las tareas PDP, Joint-PDP y PDIV como métricas de juegos cooperativos sobre fórmulas WDNF. Al aprovechar la propiedad de linealidad de estas métricas, pueden calcular explicaciones globales complejas agregando resultados de "cubos" individuales (conjunciones de literales) dentro de la representación WDNF. Esto evita la necesidad de reevaluar el modelo para cada combinación de muestra-característica individualmente.

2. Construcción Eficiente de Conjuntos de Datos de Consumo:
   Para calcular PDP y Joint-PDP de manera eficiente, los autores construyen conjuntos de datos "de consumo" ($C$) compactos que permiten a los algoritmos de atribución local calcular gráficos de dependencia globales.

   • Para PDP, construyen un conjunto de datos con $k$ filas que representan valores de características muestreados.
   • Para Joint-PDP, introducen una construcción novedosa que reduce el tamaño del conjunto de datos de $O(k^2 f)$ a $O(k^2 \log f)$ codificando los índices de características en binario y utilizando las operaciones np.tile y np.repeat para asegurar que todas las combinaciones de valores por pares estén representadas sin filas redundantes.

3. PDP Completas:
   Reconociendo que los PDP estándar con valores muestreados ($k$) pueden pasar por alto picos estrechos o efectos de un solo valor (por ejemplo, un modelo de fraude que marca un salario específico por defecto), los autores proponen PDP Completas. En lugar de un muestreo arbitrario, las PDP Completas utilizan todos los umbrales de división de los nodos del árbol como valores del eje X. Dado que las predicciones de los árboles de decisión son constantes por partes entre umbrales, este método captura el comportamiento exacto del conjunto con puntos de evaluación mínimos.

4. Reducción de Complejidad para Any-Order-PDIV:
   La contribución teórica más significativa es la reducción de la complejidad para Any-Order-PDIV.

   • Ingenio/FastPD: FastPD procesa los árboles independientemente, lo que resulta en una dependencia de complejidad de $2^{2D}$ (donde $D$ es la profundidad del árbol) en el peor de los casos.
   • WOODELF++: Al procesar cada camino de raíz a hoja por separado y utilizar la estructura específica de la métrica PDIV en WDNF, la dependencia de complejidad se reduce a $4^D$. Esto representa una mejora exponencial sobre el estado del arte.

5. Aproximación y Soporte GPU:
   El marco soporta naturalmente aproximaciones Dependientes del Camino (equivalentes a establecer el conjunto de datos de fondo como vacío) y está implementado en Python puro con soporte para aceleración GPU.

Contribuciones Clave

1. Aceleración en PDP y Joint-PDP: WOODELF++ logra una aceleración de aproximadamente 6× sobre FastPD y hasta cinco órdenes de magnitud sobre scikit-learn para tareas de PDP y Joint-PDP en conjuntos de datos grandes.
2. Mejora Exponencial de Complejidad para Any-Order-PDIV: Los autores demuestran que para árboles equilibrados, la complejidad cambia de exponencial en el tamaño de entrada ($2^{2D}$ de FastPD) a polinomial en el tamaño de entrada ($4^D$ de WOODELF++). Empíricamente, esto reduce el tiempo de ejecución para Any-Order-PDIV en 400,000 muestras de un estimado de 1,000,000 de años (FastPD) a 5 minutos (WOODELF++).
3. Introducción de PDP Completas: Un método novedoso para capturar la estructura completa constante por partes de los conjuntos de árboles, permitiendo la detección de sobreajuste y violaciones de monotonicidad que los PDP muestreados pasan por alto.
4. Marco Unificado: El artículo establece una conexión simple entre PDP aproximados, PDP exactos y SHAP Dependiente del Camino, unificándolos bajo un único marco algorítmico.

Resultados Experimentales

Los autores evaluaron WOODELF++ en dos conjuntos de datos grandes y ampliamente utilizados: IEEE-CIS (472k filas, 397 características) y KDD Cup 1999 (4.9M filas, 127 características). Los modelos se entrenaron utilizando HistGradientBoostingRegressor con 100 árboles y una profundidad máxima de 6.

• Rendimiento de PDP: En IEEE-CIS, WOODELF++ calculó PDP Exactos (k=5) en 13.1 segundos (GPU) en comparación con 99 segundos para FastPD y 58.5 minutos para scikit-learn.
• Rendimiento de Joint-PDP: Para Joint-PDP (k=5), WOODELF++ tardó 25 segundos (GPU) frente a 130 segundos para FastPD y un estimado de 35 días para scikit-learn.
• Any-Order-PDIV: En IEEE-CIS con 10,000 muestras, WOODELF++ completó la tarea en 22.6 segundos (GPU). Se estimó que FastPD requeriría 60,000 años.
• Corrección: Los autores verificaron que las salidas de WOODELF++ coinciden con scikit-learn y los cálculos directos de PDIV con una diferencia máxima de 0.00001.

Significado

El artículo afirma que WOODELF++ cambia fundamentalmente la viabilidad de interpretar conjuntos de árboles de decisión. Al reducir la complejidad de Any-Order-PDIV de intratable a práctica, permite el análisis de interacciones de características de alto orden que anteriormente eran computacionalmente imposibles. Además, la introducción de PDP Completas permite a los profesionales visualizar los límites de decisión exactos de los modelos de árboles, superando las limitaciones de las aproximaciones muestreadas. Los autores posicionan a WOODELF++ como una herramienta necesaria para la IA escalable y confiable en dominios que requieren una comprensión profunda del modelo, como la atención médica, las finanzas y la ecología.