Resumen Técnico: Quadrature-TreeSHAP

Enunciado del Problema

La explicabilidad para modelos de conjuntos de árboles (por ejemplo, XGBoost, Random Forests) depende en gran medida de los valores de Shapley. Aunque SHAP dependiente de la ruta es el enfoque estándar debido a su eficiencia, los métodos existentes enfrentan compensaciones significativas en cuanto a tiempo de ejecución dependiente de la profundidad, estabilidad numérica y soporte para interacciones de orden superior.

Los métodos actuales más avanzados presentan limitaciones específicas:

• TreeSHAP y GPUTreeSHAP operan con una complejidad temporal de $O(MTLD^2)$ (donde $M$ son muestras, $T$ árboles, $L$ hojas, $D$ profundidad).
• FastTreeSHAP v2 y Woodelf reducen la complejidad a $O(MTLD)$ pero introducen pasos de preprocesamiento exponenciales en la profundidad, volviéndolos poco prácticos para árboles profundos.
• Linear TreeSHAP logra $O(MTND)$ pero sufre de inestabilidad numérica debido a operaciones en la base monomial.
• TreeGrad-Shap mejora la estabilidad mediante formulaciones de gradiente pero se limita a atribuciones de primer orden.
• TreeSHAP-IQ se extiende a interacciones de orden superior pero tiene una complejidad de $O(MTLD \binom{F-1}{s-1})$, lo que escala mal a medida que aumentan el número de características ($F$) y el orden de interacción ($s$).

Metodología

Los autores proponen Quadrature-TreeSHAP, una reformulación de TreeSHAP dependiente de la ruta basada en cuadratura de Gauss–Legendre y un polinomio de interacción de Banzhaf ponderado.

1. Fundamento Teórico

El método aprovecha la relación entre los valores de Shapley y los valores de Banzhaf ponderados.

• Polinomio de Banzhaf Ponderado: Para una hoja $v$ de un árbol de decisión, el valor de interacción de Banzhaf ponderado dependiente de la ruta para un subconjunto de características $S$ en la probabilidad de inclusión $p$ se expresa como un polinomio $B^{(S)}_{p,v}$. Este polinomio se deriva de la estructura del camino de la hoja y los pesos de las aristas.
• Recuperación por Integral: Los valores de interacción de Shapley se recuperan integrando estos polinomios de Banzhaf sobre la probabilidad de participación $p \in [0, 1]$:
  $$SII^{(S)}(f_v) = \int_0^1 B^{(S)}_p(f_v) \, dp$$
• Aproximación por Cuadratura: En lugar de la integración simbólica, los autores evalúan esta integral utilizando cuadratura de Gauss–Legendre. La integral se aproxima como una suma ponderada del polinomio evaluado en nodos fijos $t_m$:
  $$SII^{(S)}_v \approx \sum_{m=1}^n w_m B^{(S)}_{t_m, v}$$

2. Implementación Algorítmica

• Formulación de Punto Fijo: El algoritmo realiza un único recorrido en profundidad (DFS) del árbol. Durante el recorrido, propaga los valores del polinomio de camino en un conjunto fijo de nodos de Gauss–Legendre (típicamente 8) en lugar de expandir polinomios simbólicamente.
• Reducción de Complejidad:
  • Teóricamente, el grado del integrando para interacciones de orden-$s$ es como máximo $d-s$ (donde $d$ es el número máximo de características únicas en un camino).
  • Prácticamente, los autores demuestran que 8 puntos de cuadratura fijos son suficientes para alcanzar la precisión de máquina (float32) incluso para árboles muy profundos.
  • Esto elimina la dependencia de la profundidad del árbol $d$ del cálculo interno, reduciendo la complejidad efectiva de $O(MTN \lceil d/2 \rceil)$ a $O(MTN)$ para primer orden, y de $O(MTN d^s)$ a $O(MTN d^{s-1})$ para interacciones de orden-$s$.
• Aceleración por Hardware: Dado que el cálculo implica evaluar el mismo conjunto fijo de puntos para cada camino, la aritmética es regular. Esto permite una ejecución eficiente SIMD (Instrucción Única, Múltiples Datos) en CPUs y SIMT (Instrucción Única, Múltiples Hilos) en GPUs, eliminando la sobrecarga de empaquetado en contenedores y programación requerida por GPUTreeSHAP.

Contribuciones Clave

1. Algoritmo de Interacción de Cualquier Orden: El artículo presenta un algoritmo para calcular valores de interacción de Shapley de cualquier orden que mejora la complejidad del estado del arte de TreeSHAP-IQ de $O(MTLD \binom{F-1}{s-1})$ a $O(MTN d^s)$. Esto produce ganancias sustanciales cuando el número de características excede la profundidad del árbol ($F > D \ge d$).
2. Reformulación Basada en Cuadratura: Los autores proporcionan un análisis teórico y empírico que muestra que 8 puntos de Gauss–Legendre son suficientes para alcanzar la precisión de máquina para valores de Shapley e interacciones, desacoplando efectivamente el tiempo de ejecución de la profundidad del árbol en la práctica.
3. Estabilidad Numérica: Al evaluar el polinomio resumen en nodos acotados y positivos en lugar de expandir coeficientes en una base monomial, el método evita la cancelación catastrófica. Los autores afirman que Quadrature-TreeSHAP es más numéricamente estable que TreeSHAP, particularmente para conjuntos profundos.
4. Implementación Eficiente para Hardware: El método está implementado en C++ para CPU e integrado en XGBoost para GPU. Aprovecha la vectorización (4 puntos en CPU, 32 en GPU) para lograr aceleraciones significativas sobre implementaciones existentes.
5. Integración de Código Abierto: La implementación es de código abierto e integrada en la biblioteca XGBoost (reemplazando el backend de TreeSHAP), accesible mediante llamadas API estándar (pred_contribs=True y pred_interactions=True).

Resultados Experimentales

Los autores evaluaron Quadrature-TreeSHAP en 12 conjuntos de ensambles de referencia de XGBoost (Adult, CalHousing, CovType, Fashion-MNIST) a través de regímenes pequeños, grandes y dispersos.

• Primer Orden (Valores de Shapley):
  • CPU: 1.06× a 10.59× más rápido que TreeSHAP (mediana 3.84×).
  • GPU: 1.84× a 6.95× más rápido que GPUTreeSHAP.
• Segundo Orden (Interacciones Pareadas):
  • CPU: 3.80× a 58.11× más rápido que TreeSHAP (mediana 12.86×).
  • GPU: Hasta 6.65× más rápido que GPUTreeSHAP (aunque GPUTreeSHAP permaneció competitivo en cargas de trabajo específicas de poca profundidad).
• Interacciones de Orden Superior (Pruebas de Python):
  • Comparado contra TreeSHAP-IQ en interacciones de tercer orden, Quadrature-TreeSHAP fue 18.73× a 26.49× más rápido.
  • En el conjunto de datos CovType disperso, la aceleración sobre TreeSHAP-IQ aumentó con el orden de interacción, alcanzando 1209.37× en el orden 6.
• Estabilidad Numérica:
  • En la prueba de referencia Fashion-MNIST dispersa con profundidad de árbol creciente, TreeSHAP se volvió inestable más allá de la profundidad 32. Quadrature-TreeSHAP permaneció estable, con 6–8 puntos alcanzando alta precisión.

Significancia

El artículo afirma que Quadrature-TreeSHAP ofrece una reformulación numéricamente estable, eficiente para hardware y consciente de las interacciones de SHAP dependiente de la ruta. Al cambiar de la aritmética polinómica simbólica a la cuadratura de punto fijo, el método resuelve la compensación entre la dependencia de la profundidad y la estabilidad numérica. Permite el cálculo eficiente de interacciones de alto orden en árboles profundos, una tarea previamente obstaculizada por la complejidad exponencial o la inestabilidad de los métodos anteriores. La integración en XGBoost asegura utilidad práctica inmediata para los usuarios de la biblioteca y el paquete shap más amplio.