An Odd Estimator for Shapley Values

Resumen Técnico: Un Estimador Impar para los Valores de Shapley

Planteamiento del Problema

El valor de Shapley es el marco estándar para la atribución en el aprendizaje automático, utilizado para la importancia de las características, la valoración de datos e la inferencia causal. Sin embargo, su computación exacta es generalmente intratable debido al número exponencial de coaliciones ($2^d$) requeridas para su evaluación. Aunque existen métodos de aproximación, los estimadores más efectivos suelen depender del "muestreo por pares" (muestrear una coalición $S$ y su complemento $S^c$), un heurístico que mejora empíricamente la precisión pero que carece de una justificación teórica rigurosa sobre por qué funciona, particularmente respecto a las interacciones de orden superior. Además, los métodos existentes de regresión polinómica de orden superior (por ejemplo, PolySHAP) enfrentan un cuello de botella de escalabilidad donde el costo computacional crece cuadráticamente con el tamaño de la base polinómica, limitando su aplicación en entornos de alta dimensionalidad.

Metodología

Los autores proponen OddSHAP, un nuevo estimador que aprovecha una propiedad estructural fundamental del valor de Shapley: este depende exclusivamente del componente impar de la función de valor $f$.

Fundamento Teórico

1. Descomposición Impar-Par: Cualquier función de conjunto $f$ puede descomponerse de forma única en un componente impar ($f_{odd}$) y un componente par ($f_{even}$), donde $f_{odd}(S) = -f_{odd}(S^c)$ y $f_{even}(S) = f_{even}(S^c)$.
2. Propiedad del Valor de Shapley: Los autores demuestran que $\phi_i(f) = \phi_i(f_{odd})$ para todos los jugadores $i$. El componente par contribuye con cero al valor de Shapley. El componente par es irrelevante.
3. Mecanismo de Muestreo por Pares: El artículo proporciona la primera justificación teórica general para el muestreo por pares. Al muestrear pares $(S, S^c)$ con pesos simétricos, el problema de regresión de mínimos cuadrados ponderados se ortogonaliza (desacopla) en problemas de optimización independientes para los componentes impar y par. Dado que el componente par es irrelevante, el muestreo por pares efectivamente aísla la señal requerida para los valores de Shapley. Esto resuelve una conjetura de que el muestreo por pares con un ajuste de orden-$k$ (para $k$ impar) es equivalente a un ajuste de orden-$(k+1)$.

Diseño del Algoritmo: OddSHAP

Para explotar esta idea evitando la explosión combinatoria de ajustar todos los términos de orden superior, OddSHAP opera en la base de Fourier en lugar de la base de unanimidad.

• Ventaja de la Base de Fourier: En la base de Fourier, una función de base $\chi_T$ es impar si y solo si la cardinalidad $|T|$ es impar. Esto permite una separación limpia de los términos pares e impares, a diferencia de la base de unanimidad.
• Proceso de Dos Etapas:
  1. Cribado de Interacciones: Se ajusta un modelo proxy de Árboles de Potenciación de Gradiente (GBT) a las coaliciones muestreadas. Utilizando un método como ProxySPEX, el algoritmo extrae un conjunto disperso de coeficientes de Fourier de orden impar de alto impacto. Esto evita la necesidad de ajustar todas las interacciones posibles.
  2. Regresión Impar: Se realiza una regresión de mínimos cuadrados ponderados estrictamente sobre los términos de la base de Fourier de orden impar seleccionados (más los términos lineales), restringida a coincidir con la función de valor en los conjuntos vacío y completo.
• Eficiencia: Al restringir la regresión al subespacio impar y utilizar un proxy para seleccionar los términos, el método logra una complejidad de tiempo polinomial relativa al presupuesto de muestreo, evitando la escala $O(d^k)$ de los métodos de orden fijo.

Contribuciones Clave

1. Unificación Teórica del Muestreo por Pares: El artículo demuestra que el muestreo por pares desacopla implícitamente el objetivo de regresión en componentes pares e impares, proporcionando una explicación rigurosa para su éxito empírico y generalizando hallazgos previos limitados a interacciones de bajo orden.
2. El Estimador OddSHAP: Un estimador consistente que realiza regresión polinómica únicamente sobre una selección dispersa de funciones de la base de Fourier de orden impar. Este filtra los componentes pares irrelevantes e identifica interacciones de alto impacto mediante un modelo proxy.
3. Rendimiento de Vanguardia: Benchmarks extensos demuestran que OddSHAP logra una precisión de estimación superior a los métodos existentes (incluyendo RegressionMSR, LeverageSHAP y PolySHAP) bajo presupuestos de muestreo mayores, particularmente en entornos de alta dimensionalidad.

Resultados Experimentales

Los autores evaluaron OddSHAP en ocho funciones de valor que van desde $d=14$ (DistilBERT) hasta $d=101$ (conjunto de datos Crime), cubriendo dominios de aprendizaje profundo (imagen y texto) y datos tabulares.

• Precisión: OddSHAP alcanzó consistentemente el Error Cuadrático Medio (MSE) más bajo y el mejor rango promedio en los benchmarks, particularmente cuando el presupuesto de muestreo $m$ era suficiente para detectar interacciones ($m > \eta \cdot d$).
• Comparación con FFD: OddSHAP superó al Diseño Factorial Fraccionario de Presupuesto Fijo (FFD-RD) en arquitecturas de aprendizaje profundo (ViT, DistilBERT), donde las interacciones de orden superior son significativas. Por el contrario, FFD-RD funcionó ligeramente mejor en conjuntos de datos tabulares basados en árboles donde las interacciones de orden superior decaen rápidamente, validando los compromisos específicos del dominio.
• Estudios de Ablación:
  • Pareado vs. No Pareado: El muestreo por pares superó consistentemente al muestreo no pareado.
  • Impar vs. Todas las Interacciones: Bajo el muestreo por pares, incluir interacciones pares no proporcionó ningún beneficio y degradó ligeramente el rendimiento al consumir el presupuesto de interacción con términos que se cancelan matemáticamente.
  • Dispersión: La incorporación de un número moderado de interacciones impares (controlado por el factor de variable de regresión $\eta$) redujo significamente el error en comparación con las líneas base lineales, aunque ocurrió sobreajuste con demasiadas interacciones.

Significado y Reivindicaciones

El artículo afirma que OddSHAP ofrece un marco de presupuesto flexible que se adapta robustamente a través de diversas estructuras de interacción. Su principal significancia radica en:

1. Resolución de una Conjetura Abierta: Proporciona el mecanismo teórico fundamental que explica por qué funciona el muestreo por pares, yendo más allá de la observación empírica hacia la prueba estructural.
2. Escalabilidad: Retiene el poder expresivo de las aproximaciones de orden superior sin incurrir en sus costos combinatorios prohibitivos al restringirse al subespacio impar.
3. Robustez: A diferencia de los métodos que dependen de supuestos de truncamiento rígidos (como FFD), OddSHAP sigue siendo efectivo en dominios complejos de aprendizaje profundo donde las interacciones de alto orden no son despreciables, manteniendo al mismo tiempo su competitividad en dominios tabulares dispersos.

Los autores señalan limitaciones, específicamente que el tiempo de ejecución del algoritmo escala cúbicamente con el presupuesto debido al costo de regresión cuadrática de las interacciones seleccionadas, y que el muestreo por pares reduce el número efectivo de muestras independientes, lo que podría inflar la varianza. Sin embargo, concluyen que el método representa un enfoque de vanguardia para la estimación del valor de Shapley en entornos agnósticos al modelo.