Resumen Técnico: ShaplEIG

Planteamiento del Problema

Los valores de Shapley (SV, por sus siglas en inglés) sirven como una medida de atribución fundamentada en el aprendizaje automático interpretable, pero su computación exacta suele ser intratable. La carga computacional surge de dos factores: el crecimiento exponencial de las coaliciones ($2^p$) con el número de jugadores $p$, y el alto costo de evaluar la función de valor $\nu$ para cada coalición. En aplicaciones como la importancia de características basada en el reentrenamiento, la valoración de datos y la importancia de hiperparámetros, las evaluaciones de la función de valor pueden implicar el reentrenamiento completo de un modelo o una inferencia costosa, lo que limita severamente el presupuesto de evaluación.

Los métodos de aproximación existentes, incluyendo el muestreo de Monte Carlo y los enfoques basados en sustitutos (por ejemplo, Kernel SHAP, Regresión MSR), dependen típicamente de distribuciones de muestreo fijas y no adaptativas. Esto plantea la pregunta de si la precisión de la aproximación puede mejorarse seleccionando coaliciones para la evaluación de forma adaptativa basándose en observaciones previas, particularmente en regímenes de bajo presupuesto. Aunque el Diseño Experimental Bayesiano (BED) ofrece un marco para el diseño secuencial utilizando la Ganancia de Información Esperada (EIG), su adopción en la estimación de SV ha sido limitada debido a la falta de expresiones de EIG de forma cerrada y a la intratabilidad computacional de estimar la EIG para espacios discretos de alta dimensión.

Metodología

Los autores proponen ShaplEIG, un enfoque de diseño experimental bayesiano que selecciona coaliciones de forma adaptativa para maximizar la ganancia de información respecto a los valores de Shapley.

1. Sustituto de Proceso Gaussiano con Núcleo de Hamming

ShaplEIG modela la función de valor $\nu$ utilizando un sustituto de Proceso Gaussiano (GP). Para manejar el espacio de entrada binario de las coaliciones (representadas como vectores indicadores $z \in \{0, 1\}^p$), el método emplea un núcleo de distancia de Hamming. Este núcleo cuantifica la similitud entre coaliciones basándose en distancias de Hamming ponderadas, con hiperparámetros de escala de longitud $\xi$ aprendibles. El GP proporciona una distribución posterior sobre la función de valor en todas las $2^p$ coaliciones dado un conjunto de datos $D_t$ de evaluaciones observadas.

2. Estimación de SV Consistente mediante Linealidad

Un hallazgo teórico clave es la linealidad de los valores de Shapley con respecto a la función de valor. Los SV $\phi$ pueden expresarse como una transformación lineal del vector de la función de valor $\nu$: $\phi = A\nu$, donde $A$ es una matriz conocida derivada de la fórmula de Shapley. En consecuencia, bajo el sustituto GP, la distribución posterior sobre los SV también es gaussiana y está disponible en forma cerrada:
$$\phi | D_t \sim \mathcal{N}_p(A\mu_{\nu|D_t}, A\Sigma_{\nu|D_t}A^\top)$$
Los autores extraen las estimaciones de los SV de la media posterior, $\hat{\phi} = A\mu_{\nu|D_t}$. Crucialmente, para GPs sin ruido (o cuasi-sin ruido), este estimador es consistente: si se evalúan todas las $2^p$ coaliciones, las estimaciones convergen exactamente a los verdaderos valores de Shapley.

3. EIG de Forma Cerrada

La contribución central es la derivación de una expresión de forma cerrada para la EIG de una coalición candidata $z^{(i)}$ respecto a los SV. Al enmarcar la selección secuencial como un problema inverso lineal bayesiano donde los SV son un objetivo lineal, se demuestra que la EIG depende únicamente de la covarianza posterior de los SV:
$$\text{EIG}^{(t)}_{\phi}(z^{(i)}) \propto -\log \det \left( A \Sigma_{\nu|\nu'(z^{(i)}), D_t} A^\top \right) + C$$
Esto evita las expectativas anidadas que típicamente requieren los BED, ya que la EIG depende únicamente del diseño experimental (la coalición seleccionada) y no del resultado específico $y(x)$.

4. Computación Eficiente mediante Polinomios Simétricos Elementales

La computación directa de la EIG implica operaciones en matrices de tamaño $2^p \times 2^p$, lo que conduce a una complejidad exponencial. Los autores proponen un esquema de computación eficiente que reduce la complejidad a tiempo polinomial ($O(p^4 + t^3)$) explotando la estructura multiplicativa del núcleo de Hamming.

• Los términos requeridos para la EIG (específicamente $A\Sigma_{\nu|D_t}e_i$ y $A\Sigma_{\nu|D_t}A^\top$) se reescriben como sumas ponderadas de evaluaciones del núcleo.
• Estas sumas se identifican con polinomios simétricos elementales (ESP) escalados.
• Al computar estos polinomios de manera eficiente (usando programación dinámica y tablas de prefijos/sufijos), el método evita la enumeración explícita de todas las coaliciones.

5. Algoritmo

El algoritmo procede de forma codiciosa (greedy):

1. Inicializar con un diseño pequeño (por ejemplo, muestreo de puntuación de apalancamiento/leverage score).
2. Ajustar el sustituto GP y optimizar los hiperparámetros.
3. Computar la EIG para todas las coaliciones candidatas usando el esquema polinomial eficiente.
4. Seleccionar la coalición con la máxima EIG, evaluar la función de valor y actualizar el conjunto de datos.
5. Repetir hasta que se agote el presupuesto.

Contribuciones Clave

1. Marco de Trabajo ShaplEIG: Introducción de un novedoso método basado en BED para la estimación de SV que utiliza un sustituto GP con un núcleo de Hamming y selecciona coaliciones de forma adaptativa basándose en la EIG.
2. EIG de Forma Cerrada: Demostración de que la EIG para los valores de Shapley admite una expresión de forma cerrada bajo un sustituto GP, aprovechando la linealidad de los SV en la función de valor.
3. Complejidad Polinomial: Propuesta de un esquema de computación eficiente para la EIG que reduce la complejidad de exponencial a polinomial en el número de jugadores ($p$) mediante polinomios simétricos elementales.
4. Estimación Consistente: Provisión de un estimador de SV consistente que converge a los valores exactos cuando se evalúan todas las coaliciones, contrastando con algunos métodos de sustitutos basados en árboles que requieren pasos de ajuste adicionales.

Resultados Experimentales

Los autores evalúan ShaplEIG a través de diversas aplicaciones costosas que involucran juegos de tamaño pequeño a moderado ($8 \le p \le 101$):

• Tareas: Importancia global de características (TabPFN), valoración de datos (Random Forest, Gradient Boosting), importancia de hiperparámetros (XGBoost, LCBench) y explicaciones locales (ResNet, ViT, Random Forest).
• Líneas Base: Comparación contra Kernel SHAP, Leverage SHAP, Muestreo de Permutación y el estado del arte de Regresión MSR (acoplado con XGBoost).
• Ablaciones: Comparación contra variantes que utilizan el mismo sustituto GP pero diferentes estrategias de selección (Aleatorio, Muestreo de Incertidumbre, Muestreo de Puntuación de Apalancamiento).

Hallazgos:

• Eficiencia de Muestreo: ShaplEIG logra consistentemente la mejor precisión general (menor Error Cuadrático Medio) en el régimen de bajo presupuesto en la mayoría de las tareas. A menudo domina estrictamente a los competidores, particularmente en juegos asimétricos donde las interacciones de los jugadores no son uniformes.
• Perspectivas de Ablación: El fuerte rendimiento se atribuye principalmente a la estrategia de selección basada en EIG más que al uso de un sustituto GP. El Muestreo de Incertidumbre (US) a menudo funcionó peor que el muestreo aleatorio, resaltando que maximizar la varianza marginal no equivale a maximizar la información sobre los SV linealmente transformados.
• Escalabilidad: Para juegos más grandes ($p > 16$), el método sigue siendo efectivo incluso si el reajuste de hiperparámetros se realiza de forma programada en lugar de en cada iteración.
• Costo Computacional: Aunque la computación de la EIG es eficiente (segundos), el ajuste de hiperparámetros puede convertirse en un cuello de botella para $p$ grande (hasta 25 minutos por iteración para $p \approx 100$). Los autores señalan que ShaplEIG es más apropiado cuando las evaluaciones de la función de valor son genuinamente costosas, justificando la sobrecarga.

Significado y Reivindicaciones

El artículo afirma que ShaplEIG proporciona un marco fundamentado para mejorar la eficiencia de muestreo en la estimación de SV para juegos costosos. Al derivar una EIG de forma cerrada y un esquema de computación eficiente de tiempo polinomial, los autores superan las principales barreras para aplicar el Diseño Experimental Bayesiano en este dominio.

Los autores declaran modestamente que, si bien el método incurre en una sobrecarga computacional debido a la optimización repetida del GP, ofrece ganancias sustanciales en la precisión de la estimación cuando los presupuestos de evaluación son limitados. Reconocen que para juegos muy grandes o funciones de valor menos costosas, la sobrecarga puede ser prohibitiva, sugiriendo que el trabajo futuro debería centrarse en mejoras computacionales adicionales para ampliar su aplicabilidad. El trabajo no pretende resolver la estimación de SV para todos los escenarios, sino que apunta específicamente al régimen de funciones de valor costosas donde la selección adaptativa es crítica.