Resumen Técnico: PolySHAP – Extensión de KernelSHAP con Regresión Polinómica Informada por Interacciones

Enunciado del Problema

Los valores de Shapley son una herramienta central de la teoría de juegos en la IA Explicable (XAI) para atribuir la predicción de un modelo a sus características de entrada. Sin embargo, calcular los valores de Shapley exactamente requiere evaluar el modelo en todas las $2^d$ posibles subconjuntos de características, lo cual es computacionalmente inviable para modelos con un gran número de características $d$.

KernelSHAP (Lundberg & Lee, 2017) ha surgido como un método líder para aproximar los valores de Shapley de manera eficiente. Plantea el problema como una regresión de mínimos cuadrados ponderada, aproximando el juego cooperativo $\nu$ con una función lineal ajustada a una muestra de subconjuntos aleatorios de características. Aunque es efectivo, esta aproximación lineal asume inherentemente la aditividad de las características, fallando en capturar las interacciones no lineales entre ellas. En consecuencia, KernelSHAP puede producir estimaciones subóptimas cuando el juego subyacente exhibe interacciones de orden superior significativas.

Metodología: PolySHAP

Los autores proponen PolySHAP, una generalización de KernelSHAP que aproxima el juego $\nu$ utilizando polinomios de grado superior en lugar de una función lineal. Este enfoque modela explícitamente las interacciones no lineales de las características.

Mecanismo Central

1. Representación Informada por Interacciones: En lugar de ajustar un modelo lineal $\sum \phi_i \mathbb{1}[i \in S]$, PolySHAP ajusta un polinomio de grado $k$ sobre los indicadores binarios de características $\mathbb{1}[i \in S]$. La aproximación incluye un "límite de interacción" $\mathcal{I}$, un subconjunto de términos de interacción (subconjuntos de características de tamaño $\ge 2$).
   $$\hat{\nu}(S) \approx \sum_{T \in \mathcal{D} \cup \mathcal{I}} \phi_T \prod_{j \in T} \mathbb{1}[j \in S]$$
   donde $\mathcal{D}$ representa las características individuales y $\mathcal{I}$ representa los términos de interacción.

2. Formulación de Regresión: PolySHAP resuelve un problema de mínimos cuadrados ponderados similar a KernelSHAP, pero con una matriz de diseño expandida que contiene columnas tanto para los efectos principales como para los términos de interacción seleccionados. El objetivo minimiza la pérdida $\ell_2$ ponderada entre los valores del juego muestreados $\nu(S_\ell)$ y la aproximación polinómica.

3. Extracción de Valores de Shapley: Un resultado teórico clave (Teorema 4.3) demuestra que los valores de Shapley del juego original pueden recuperarse directamente a partir de los coeficientes de la aproximación polinómica. Específicamente, el valor de Shapley para la característica $i$ es la suma del coeficiente del efecto principal $\phi_i$ y los coeficientes de todos los términos de interacción que contienen a $i$, divididos por el tamaño de esos conjuntos de interacción:
   $$\phi_i^{SV} = \phi_i + \sum_{S \in \mathcal{I}: i \in S} \frac{\phi_S}{|S|}$$

4. Estrategias de Muestreo: El método admite el muestreo estándar y el muestreo emparejado (muestreando subconjuntos $S$ y sus complementos $D \setminus S$). Los autores utilizan el muestreo por puntuación de palanca (leverage score) para mejorar la calidad de la estimación, señalando que para interacciones de orden superior, las puntuaciones de palanca de orden 1 (uniformes sobre los tamaños de los subconjuntos) funcionan bien en la práctica.

Contribuciones Clave

1. Consistencia y Extensión Teórica

El artículo demuestra que PolySHAP proporciona estimaciones consistentes de los valores de Shapley. A medida que el número de muestras $m$ se acerca al número total de subconjuntos $2^d$, las estimaciones de PolySHAP convergen exactamente a los valores de Shapley verdaderos (Teorema 4.3). Esto contrasta con algunos métodos de aproximación basados en árboles (por ejemplo, RegressionMSR) que requieren pasos adicionales de ajuste de regresión para lograr consistencia.

2. Equivalencia Teórica entre Muestreo Emparejado y 2-PolySHAP

Una contribución teórica mayor es la demostración de que KernelSHAP con muestreo emparejado es matemáticamente equivalente a 2-PolySHAP (Teorema 5.1).

• Cuando los subconjuntos se muestrean en pares ($S$ y $D \setminus S$), la solución de regresión lineal de KernelSHAP produce exactamente las mismas aproximaciones de valores de Shapley que una regresión polinómica de segundo orden (2-PolySHAP).
• Este hallazgo proporciona la primera justificación teórica sólida para el éxito empírico del muestreo emparejado, explicando que captura implícitamente todas las interacciones de segundo orden sin ajustar explícitamente un polinomio de grado 2.

3. Rendimiento Empírico

Extensos experimentos en 15 juegos de explicación local (que abarcan dominios tabulares, de imágenes y de lenguaje) demuestran que:

• Precisión de orden superior: Aumentar el grado del polinomio (por ejemplo, 3-PolySHAP) mejora consistentemente la calidad de la aproximación (medida por MSE, Precision@5 y correlación de Spearman) en comparación con KernelSHAP (1-PolySHAP) y el Muestreo por Permutación, siempre que el presupuesto de muestreo sea suficiente.
• Eficiencia del Muestreo Emparejado: Bajo muestreo emparejado, KernelSHAP logra un rendimiento comparable al de 2-PolySHAP, validando la equivalencia teórica.
• Resultados de vanguardia: En configuraciones de dimensión baja a moderada, PolySHAP (específicamente 3-PolySHAP) a menudo supera a otras líneas base, incluyendo RegressionMSR (que depende de aproximaciones XGBoost) y SVARM.

Significado y Afirmaciones

El artículo afirma ofrecer una extensión principista del ampliamente utilizado marco KernelSHAP. Al pasar de aproximaciones lineales a polinómicas, PolySHAP aborda la limitación de ignorar las interacciones entre características, lo que conduce a explicaciones más precisas para modelos complejos.

Crucialmente, el trabajo cierra una brecha entre las prácticas heurísticas y la teoría. Al demostrar que la popular heurística de "muestreo emparejado" es equivalente al modelado de interacciones de segundo orden, los autores proporcionan una base rigurosa para entender por qué esta estrategia de muestreo funciona tan bien en la práctica. Los autores notan modestamente que, aunque las interacciones de orden superior mejoran la precisión, requieren presupuestos de muestreo más grandes, y en configuraciones de muy alta dimensionalidad ($d \ge 60$), las ganancias son más modestas debido a la explosión combinatoria de los términos de interacción.

El artículo concluye que PolySHAP es un método robusto, consistente y empíricamente superior para la estimación de valores de Shapley, particularmente cuando el juego subyacente involucra interacciones no lineales de características.