SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism

Resumen Técnico: SHAP y Redes de Tensores

1. El Problema

Las Explicaciones Aditivas de Shapley (SHAP) son el estándar de facto para explicar las predicciones de modelos de aprendizaje automático (ML). Sin embargo, su principal limitación es la intractabilidad computacional:

• Para modelos simples como los árboles de decisión, SHAP se puede calcular en tiempo polinómico (ej. TreeSHAP).
• Para modelos más expresivos y complejos, como las redes neuronales (incluso las binarizadas), calcular SHAP exacto es NP-difícil (o #P-difícil).
• Esto crea una brecha crítica: los modelos donde más se necesitan explicaciones (redes neuronales profundas) son los más difíciles de explicar de manera exacta y eficiente.

El objetivo de este trabajo es analizar la complejidad computacional de calcular SHAP exacto para una clase de modelos más amplia y expresiva: las Redes de Tensores (Tensor Networks - TNs), y explorar bajo qué condiciones este cálculo se vuelve tratable y paralelizable.

2. Metodología

Los autores proponen un marco teórico basado en la teoría de la complejidad computacional y el álgebra tensorial. La metodología se estructura en tres pilares:

1. Formulación Tensorial de SHAP:

   • Replantean la fórmula clásica de SHAP como una operación de contracción de tensores.
   • Introducen el Tensor de SHAP Marginal ($T^{(M,P)}$), que resume toda la información de SHAP del modelo.
   • Demuestran que este tensor se puede construir mediante la contracción de dos componentes: un Tensor de Coalición Ponderada Modificado ($\tilde{W}$) y un Tensor de Valor Marginal ($V^{(M,P)}$).

2. Análisis de Estructuras Específicas (Tensor Trains - TTs):

   • Se centran en las Redes de Tensores en Tren (Tensor Trains - TTs), una subclase de TNs con topología unidimensional (cadena).
   • Demuestran que si tanto el modelo ($M$) como la distribución de datos ($P$) se representan como TTs, el Tensor de SHAP Marginal resultante también es un TT.
   • Utilizan algoritmos de contracción paralela (escaneo paralelo) para calcular los valores de SHAP.

3. Reducciones y Complejidad Parametrizada:

   • Utilizan reducciones para mapear otros modelos populares (árboles, RNNs lineales) a la estructura de TTs.
   • Para las Redes Neuronales Binarizadas (BNNs), aplican la complejidad parametrizada para analizar cómo la profundidad, el ancho y la dispersión (sparsity) afectan la dificultad del problema.

3. Contribuciones Clave

1. Marco General para TNs:

   • Presentan el primer algoritmo exacto para calcular SHAP en Redes de Tensores con estructuras arbitrarias.
   • Establecen que, en el caso general de TNs sin restricciones estructurales, el cálculo de SHAP es #P-Difícil.

2. Tractabilidad y Paralelismo en TTs (Clase NC):

   • Resultado Principal: Demuestran que para la familia de Tensor Trains (TTs), el cálculo de SHAP no solo es polinómico, sino que pertenece a la clase de complejidad NC (específicamente $NC^2$).
   • Esto significa que SHAP se puede calcular en tiempo polilogarítmico utilizando un número polinómico de procesadores paralelos.
   • Esta es la primera vez que se analiza teóricamente la paralelizabilidad de SHAP.

3. Mejora de Límites de Complejidad para Otros Modelos:

   • Mediante reducciones a TTs, demuestran que el cálculo de SHAP para árboles de decisión, ensembles de árboles, modelos lineales y RNNs lineales también pertenece a la clase NC.
   • Esto refina los resultados anteriores, permitiendo una computación mucho más eficiente mediante paralelismo masivo y soportando distribuciones de datos más complejas (dependencias entre características) que las implementaciones actuales.

4. Análisis de Redes Neuronales Binarizadas (BNNs):

   • Realizan un análisis fino de los parámetros estructurales:
     • Profundidad: Mantener la profundidad constante no hace que SHAP sea tratable (sigue siendo NP-difícil).
     • Ancho: Fijar el ancho de la red transforma el problema en la clase XP (polinómico en el tamaño de entrada, pero exponencial en el ancho).
     • Ancho + Dispersión: Fijar tanto el ancho como la dispersión (mediante el parámetro de cardinalidad reificada) hace que el problema sea FPT (Tractable de Parámetro Fijo).
   • Insight Crucial: Para las BNNs, el ancho (y no la profundidad) es el cuello de botella computacional principal para SHAP.

4. Resultados Principales

• Complejidad Paralela: El cálculo exacto de SHAP para TTs, árboles de decisión y RNNs lineales se puede realizar en tiempo $O(\log^k(n))$ con $O(n^c)$ procesadores. Esto es una mejora drástica sobre los algoritmos secuenciales actuales.
• Generalización de Distribuciones: El marco permite calcular SHAP bajo distribuciones de datos que capturan dependencias complejas entre características (distribuciones de Markov, HMM, Born Machines), algo que los métodos exactos anteriores no soportaban eficientemente.
• Límites de las BNNs: Se prueba que incluso redes muy poco profundas (una sola capa oculta) son intratables para SHAP si el ancho es grande. Sin embargo, redes "estrechas" y "dispersas" permiten explicaciones eficientes, independientemente de su profundidad.

5. Significado e Impacto

• Cierre de la Brecha de Expresividad: Este trabajo cierra la brecha entre la expresividad del modelo y la capacidad de explicarlo. Muestra que existen clases de modelos mucho más expresivas que los árboles de decisión (como los TTs y ciertas redes neuronales restringidas) para las cuales SHAP exacto es computacionalmente viable.
• Nueva Dirección para XAI: Al identificar el ancho como el factor limitante en lugar de la profundidad, el trabajo sugiere nuevas direcciones para el diseño de redes neuronales interpretables (arquitecturas "estrechas" y "dispersas").
• Paralelismo Masivo: La demostración de que SHAP está en la clase NC abre la puerta a la implementación de explicaciones exactas a gran escala utilizando hardware paralelo moderno (GPUs/TPUs), superando las limitaciones de tiempo de los métodos de muestreo aproximado.
• Fundamento Teórico: Proporciona una base rigurosa para entender cuándo y por qué ciertas arquitecturas de IA son explicables, moviendo el campo de la explicabilidad de la heurística a la teoría de la complejidad formal.

En resumen, el artículo demuestra que mediante el uso de Redes de Tensores y computación paralela, es posible obtener explicaciones SHAP exactas y eficientes para una gama mucho más amplia de modelos de IA de lo que se creía posible anteriormente, redefiniendo los límites de la interpretabilidad en el aprendizaje automático.