Proxy-Based Approximation of Shapley and Banzhaf Interactions

Resumen Técnico: Aproximación Basada en Proxies de las Interacciones de Shapley y Banzhaf

Planteamiento del Problema
Las aplicaciones modernas de aprendizaje automático dependen cada vez más de la teoría de juegos cooperativos para interpretar el comportamiento de los modelos, utilizando específicamente los valores de Shapley y Banzhaf para atribuir contribuciones a características individuales. Sin embargo, comprender dinámicas complejas y no lineales a menudo requiere analizar interacciones de orden superior (subconjuntos de características) en lugar de solo efectos individuales. Calcular índices de interacción cardinales-probabilísticos exactos es computacionalmente intratable para un gran número de características ($n$) debido al crecimiento exponencial del espacio de coaliciones ($2^n$).

Los estimadores existentes enfrentan una compensación crítica entre velocidad y precisión:

• Los métodos basados en muestreo (por ejemplo, SHAP-IQ, KernelSHAP-IQ) suelen ser precisos pero requieren presupuestos de muestra imprácticos para ajustar la gran cantidad de términos de orden superior, sufriendo una alta varianza que escala mal con el orden de la interacción.
• Los métodos basados en proxies (por ejemplo, ProxySPEX) ofrecen velocidad pero dependen de la extracción basada en Fourier a partir de surrogados de árboles. Este enfoque sufre de complejidad exponencial relativa a la profundidad del árbol y a menudo requiere una truncación agresiva que compromete la precisión. Además, los métodos de proxy existentes típicamente devuelven interacciones del proxy en lugar de la función de valor subyacente, introduciendo sesgo.

Metodología: ProxySHAP
Los autores proponen ProxySHAP, un marco que reconcilia la eficiencia de muestreo de los modelos proxy basados en árboles con un camino principiado hacia la consistencia mediante corrección de residuos. El método descompone el índice de interacción objetivo $\phi^p_S(\nu)$ en dos componentes:
$$\phi^p_S(\nu) = \underbrace{\phi^p_S(\hat{\nu}_T)}_{\text{Proxy Exacto}} + \underbrace{\phi^p_S(\nu - \hat{\nu}_T)}_{\text{Residuo}}$$

1. Ajuste del Proxy (Fase 1): Se entrena un modelo basado en árboles (por ejemplo, XGBoost, LightGBM) o un modelo lineal con características de interacción en coaliciones muestreadas para aproximar la función de valor subyacente $\nu$.
2. Extracción Exacta del Proxy (Fase 2): A diferencia de los métodos anteriores que extraen coeficientes de Fourier, ProxySHAP introduce una generalización de tiempo polinómico de TreeSHAP intervencionista. Esto permite el cálculo exacto de cualquier índice de interacción cardinal-probabilístico (incluyendo Shapley y Banzhaf) directamente desde la estructura del árbol.
   • El método aprovecha la representación de Möbius de los juegos de indicadores definidos por las hojas del árbol.
   • Evita la complejidad exponencial $O(4^d)$ de la extracción basada en Fourier (donde $d$ es la profundidad del árbol), logrando un tiempo de ejecución de $O(n_{nodes})$ por interacción.
3. Ajuste de Residuos: Para corregir el sesgo introducido por el proxy que no coincide perfectamente con $\nu$, el método estima las interacciones del juego residual $(\nu - \hat{\nu}_T)$ utilizando Reutilización Máxima de Muestras (MSR).
   • El artículo proporciona un análisis teórico que muestra que la varianza del estimador MSR para interacciones de orden $k$ escala como $O(n^{k-1}/|T|)$.
   • En consecuencia, los autores derivan condiciones bajo las cuales el ajuste MSR es beneficioso: principalmente para configuraciones de baja dimensión ($n < 30$) o cuando el presupuesto de muestreo $|T|$ es suficientemente grande en relación con $n^{k-1}$. Para interacciones de alto orden en juegos grandes, la varianza de la corrección puede superar la reducción de sesgo.

Contribuciones Clave

1. Marco ProxySHAP: Una estrategia de estimación novedosa que combina un proxy basado en árboles con corrección de residuos, permitiendo una aproximación eficiente y precisa de interacciones de orden superior.
2. Avance Teórico:
   • Derivación de un algoritmo de tiempo polinómico en forma cerrada para extraer índices de interacción cardinales-probabilísticos exactos de conjuntos de árboles, evitando la dependencia exponencial de la profundidad de los métodos anteriores basados en Fourier.
   • Caracterización formal del crecimiento de la varianza de MSR para interacciones de orden superior, estableciendo condiciones explícitas (en términos de $n$, presupuesto y orden de interacción $k$) bajo las cuales el ajuste de residuos mejora o degrada el rendimiento.
3. Rendimiento Empírico: Una extensa evaluación comparativa en 47 conjuntos de datos (tabulares, visión, lenguaje, grafos y visión-lenguaje) demuestra que ProxySHAP establece un nuevo estándar de vanguardia. Logra el error más bajo tanto en regímenes de presupuesto pequeño (donde supera a ProxySPEX) como en regímenes de presupuesto grande (donde supera a KernelSHAP-IQ).

Resultados

• Precisión: ProxySHAP supera consistentemente a las líneas base (KernelSHAP-IQ, ProxySPEX, SHAP-IQ) en términos de Error Cuadrático Medio Relativo (MSE). En aplicaciones a gran escala con miles de características (por ejemplo, Bioresponse con $n=1776$), ProxySHAP permanece efectivo donde otros métodos se vuelven computacionalmente inviables o inexactos.
• Eficiencia: El algoritmo de extracción de tiempo polinómico proporciona aceleraciones de órdenes de magnitud (de 10x a 1000x) en comparación con la extracción basada en Fourier, particularmente a medida que aumenta la profundidad del árbol.
• Tareas Derivadas: En una aplicación específica para explicar el modelo de visión-lenguaje SigLIP-2 (juego FIxLIP), ProxySHAP demostró una fidelidad superior (medida por el Área bajo la curva de Inserción-Borrado) en comparación con las líneas base de regresión lineal y ProxySPEX.
• Sensibilidad a Hiperparámetros: El estudio destaca que la calidad del proxy es crítica. La optimización de hiperparámetros (HPO) mejora significativamente el rendimiento, y se propone una configuración predeterminada "informada por HPO" (utilizando muchos árboles poco profundos) para equilibrar costo y precisión.

Significado y Afirmaciones
El artículo afirma que ProxySHAP resuelve la compensación de larga data entre velocidad y precisión en la estimación de interacciones. Al proporcionar un mecanismo de extracción exacto para proxies de árboles y una estrategia fundamentada teóricamente para la corrección de residuos, permite la cuantificación escalable de dependencias complejas en sistemas de IA modernos. Los autores enfatizan que su método es particularmente valioso para:

• Aplicaciones a gran escala: Manejo de conjuntos de datos con miles de características donde el cálculo exacto es imposible.
• Interacciones de orden superior: Proporcionar estimaciones confiables para interacciones más allá de los efectos pares, que son cruciales para comprender dependencias cruzadas entre modalidades (por ejemplo, en modelos de visión-lenguaje) y sinergias complejas de características.
• Despliegue práctico: Ofrecer un estimador de "vanguardia" que es robusto frente a diversas restricciones de presupuesto y tipos de modelos, respaldado por una implementación escalable en C++.

Los autores notan modestamente las limitaciones, específicamente que la calidad de la aproximación depende del proxy ajustado (requiriendo un ajuste cuidadoso de hiperparámetros) y que la varianza de la corrección de residuos limita su utilidad en configuraciones de muy alta dimensión para interacciones de alto orden. Se sugiere trabajo futuro para explorar clases de proxies alternativas y estimadores de residuos que escalen de manera más suave.