Resumen Técnico: Valores de Shapley y de Interacción Tratables mediante Redes de Tensores

Planteamiento del Problema

Explicar las predicciones de modelos de aprendizaje automático mediante valores de Shapley y sus generalizaciones de orden superior (Índices de Interacción de Shapley, SII) es fundamental para el soporte de decisiones y la interpretabilidad. Sin embargo, computar estos índices es computacionalmente prohibitivo para modelos con $n$ características, ya que tradicionalmente requiere la enumeración de $O(2^n)$ coaliciones. Las soluciones existentes enfrentan compromisos significativos:

• Supuestos Estructurales: Métodos como TreeSHAP o aquellos para Modelos Aditivos Generalizados (GAMs) son exactos solo para arquitecturas específicas (p. ej., árboles, modelos lineales).
• Aproximaciones Basadas en Muestreo: Enfoques como KernelSHAP o SHAP-IQ dependen de un muestreo pesado, lo que requiere un ajuste delicado de la varianza y a menudo falla al escalar a interacciones de orden superior sin costos computacionales masivos.
• Estimación Amortizada: Los métodos que entrenan modelos auxiliares suelen incurrir en una sobrecarga de entrenamiento significativa y pueden carecer de garantías teóricas sobre la fidelidad de la explicación.

El desafío central es computar valores de Shapley e interacciones de forma exacta (o con error controlado) para predictores generales sin la enumeración exponencial o el muestreo excesivo.

Metodología: TN-SHAP

Los autores proponen TN-SHAP, un método que reemplaza la enumeración exhaustiva de coaliciones por un esquema de pocas evaluaciones sobre un sustituto de Red de Tensores (TN). El enfoque aprovecha tres ideas clave para reducir la complejidad de $O(2^n)$ a $O(n \cdot \text{poly}(\chi))$, donde $\chi$ es la dimensión de enlace máxima de la red de tensores.

1. Representación Multilineal y Extracción de Coeficientes

El método asume que el predictor $f$ puede ser bien aproximado por una función multilineal $g$ en un espacio de características elevado. En una expansión multilineal, $f(x) = \sum_{T \subseteq N} c_T \prod_{j \in T} x_j$, los valores de las coaliciones corresponden a combinaciones lineales de coeficientes tensoriales. Crucialmente, los valores de Shapley dependen solo de las contribuciones marginales agregadas por tamaño (sumas de contribuciones para coaliciones de tamaño $s$), en lugar de la membresía de coalición específica.

2. Selectores Diagonales e Interpolación Polinómica

En lugar de consultar $2^n$ coaliciones, TN-SHAP utiliza matrices de selección diagonal $S_r(t) = \text{Diag}(t, 1)$ aplicadas a características elevadas $\tilde{x}_r = [\phi(x_r), 1]^\top$.

• Al evaluar el sustituto $g$ en puntos donde las características son escaladas por un parámetro $t$, el método agrega todas las coaliciones de tamaño $s$ en el coeficiente de $t^s$ de un polinomio resultante $P(t)$.
• Específicamente, para una característica objetivo $i$, se construye una función de sonda $G_i(t)$ para aislar la contribución marginal de $i$ a través de todos los subconjuntos de otras características.
• Esto transforma el problema combinatorio en una interpolación polinómica. Al evaluar $G_i(t)$ en $n$ puntos distintos (p. ej., nodos de Chebyshev-Gauss), el sistema resuelve un sistema lineal de Vandermonde para recuperar las contribuciones marginales agregadas por tamaño $\{m_s^{(i)}\}$.
• El valor de Shapley se calcula entonces como una suma ponderada de estos coeficientes recuperados.

3. Sustitutos de Red de Tensores

Para hacer tratable la evaluación del mapa multilineal a escala, el tensor de coeficientes se factoriza en una Red de Tensores (TN) (p. ej., Tensor Train o Árbol Jerárquico) con dimensión de enlace $\chi$.

• Mapas de Características: Para manejar datos no lineales del mundo real, las características escalares se elevan mediante mapas aprendidos o diseñados a mano $\phi_i: \mathbb{R} \to \mathbb{R}^{d_i-1}$ antes de entrar en la TN. Esto preserva la multilinealidad en el espacio elevado mientras permite que el sustituto modele las no linealidades en el espacio de entrada original.
• Eficiencia: Cada paso de propagación hacia adelante (forward pass) a través de la TN cuesta $O(\text{poly}(\chi))$. Dado que solo se requieren $O(n)$ evaluaciones para la interpolación, la complejidad total para computar interacciones de orden-$k$ se vuelve polinomial en $n$.

Principales Contribuciones

1. Esquema Unificado de Sonda-Interpolación: Un algoritmo exacto para computar valores de Shapley e interacciones de $k$ vías en un sustituto multilineal de TN utilizando solo $O(n)$ pasadas hacia adelante estructuradas, evitando $O(2^n)$ consultas.
2. Sustitutos Mejorados con Mapas de Características: Un marco que demuestra cómo las elevaciones de características aprendidas preservan la multilinealidad requerida para el cálculo exacto al tiempo que mejoran la fidelidad del sustituto para modelos no lineales.
3. Garantías Teóricas:
   • Exactitud: El método computa los valores de Shapley exactamente sobre el sustituto multilineal ajustado.
   • Error de Aproximación: El error relativo al modelo original está acotado por el error de aproximación de coalición del peor caso del sustituto ($\epsilon$). Para los valores de Shapley, $|\phi^g_i - \phi^f_i| \leq 2\epsilon$.
   • Tractabilidad: Reducción probada de la complejidad de exponencial a polinomial $O(n \cdot \text{poly}(\chi) + n^2)$.

Resultados Experimentales

Los autores evaluaron TN-SHAP en funciones multilineales sintéticas y conjuntos de datos de regresión de UCI (Concrete, Diabetes, Energy) utilizando profesores MLP.

• Validación Sintética: En funciones exactamente multilineales, TN-SHAP logró la exactitud teórica con tiempos de ejecución en la escala de milisegundos, superando a KernelSHAP-IQ por órdenes de magnitud (p. ej., 3.5ms vs 18.7ms para $n=10$; 19.7ms vs 447.3ms para $n=50$).
• Precisión en el Mundo Real: En conjuntos de datos UCI con profesores MLP:
  • TN-SHAP logró aceleraciones de tiempo de ejecución de 25–1000× sobre KernelSHAP-IQ con una precisión comparable.
  • Para atribuciones de primer orden ($k=1$), TN-SHAP logró una similitud de coseno casi perfecta (0.994) con la verdad de campo (ground truth).
  • Para interacciones de orden superior ($k=2, 3$), TN-SHAP mantuvo una precisión competitiva mientras que las líneas base basadas en muestreo luchaban con la varianza o requerían significativamente más tiempo de cómputo para alcanzar una fidelidad similar.
• Ablación de Rango: Los experimentos mostraron que un rango de estudiante TN de $r=5-6$ fue suficiente para recuperar todas las órdenes de interacción con $R^2 > 0.99$ cuando el profesor tenía un rango de 16. Los rangos más bajos subajustan las interacciones de orden superior.
• Estabilidad en Alta Dimensión: En entornos sintéticos de alta dimensión ($D=50, 100$), TN-SHAP mantuvo una alta fidelidad del sustituto ($R^2 > 0.95$) y una fuerte recuperación de características Top-$k$ bajo presupuestos de consulta de costo lineal.

Significado y Reivindicaciones

El artículo afirma que TN-SHAP cierra la brecha entre el rigor teórico del cálculo exacto de Shapley y la necesidad práctica de eficiencia. Al aprovechar la estructura algebraica de las funciones multilineales y la eficiencia de las redes de tensores, el método:

• Convierte un problema de enumeración exponencial en un pequeño número de evaluaciones estructuradas.
• Proporciona garantías estructurales (vía límites de rango) que abordan los problemas de fidelidad comunes en los métodos de sustitutos locales sin restricciones como LIME.
• Unifica las explicaciones locales de Shapley con estructuras aditivas globales (GAMs), ya que el ajuste de un sustituto de orden-$k$ produce coeficientes $k$-SII exactos que coinciden con los términos correspondientes de los GAMs.
• Ofrece una alternativa escalable a los métodos basados en muestreo, particularmente para interacciones de orden superior donde la varianza del muestreo es típicamente alta.

Los autores señalan que el rendimiento del método depende de la calidad del ajuste del sustituto TN y de la elección de los mapas de características, pero los resultados empíricos sugieren que incluso elevaciones de características modestas y rangos tensoriales moderados son suficientes para capturar estructuras coalicionales complejas en la práctica.