Resumen Técnico: Estimación Aproximada del Valor de Shapley Mediante Muestreo Sin Reposición y Nuevos Estimadores de Varianza por Bootstrap

1. Planteamiento del Problema

El marco clásico de KernelSHAP (Lundberg y Lee, 2017) tiene como objetivo reducir el coste computacional de la estimación del valor de Shapley mediante el muestreo de un subconjunto de coaliciones en lugar de evaluar la función de contribución para todas las $2^p$ posibles combinaciones. Sin embargo, las implementaciones existentes suelen muestrear coaliciones con reposición. Este enfoque introduce desafíos estadísticos específicos:

1. Ineficiencia de Muestreo: El muestreo con reposición conduce a una versión ponderada del Probleio del Coleccionista de Cupones, donde obtener coaliciones únicas se vuelve cada vez más difícil a medida que crece el tamaño de la muestra, particularmente para coaliciones de bajo peso.
2. Limitaciones en la Estimación de la Varianza: Los métodos de bootstrap tradicionales asumen muestras independientes e idénticamente distribuidas (i.i.d.). Esta suposición se ve violada cuando se muestrea sin reposición de una población finita (el conjunto de todas las coaliciones posibles). En consecuencia, las técnicas de bootstrap estándar pueden producir estimaciones de varianza incorrectas para los valores de Shapley, al no tener en cuenta la restricción de la población finita donde la varianza debería teóricamente aproximarse a cero si se evaluaran todas las coaliciones.

El artículo aborda estos problemas proponiendo un marco que utiliza el muestreo sin reposición e introduce nuevas metodologías de bootstrap compatibles con la teoría de poblaciones finitas para estimar con precisión la varianza de los valores de Shapley aproximados.

2. Metodología

2.1 Muestreo Sin Reposición mediante la Distribución de Wallenius

El algoritmo propuesto modifica el procedimiento KernelSHAP para muestrear coaliciones sin reposición. El proceso consta de dos pasos principales:

1. Estratificación: Las coaliciones se agrupan por el número de características (tamaño) que contienen.
2. Determinación de los Tamaños de Muestra: En lugar de muestrear coaliciones una a una de forma estocástica, el algoritmo calcula el número esperado de coaliciones que se extraerán de cada grupo utilizando la distribución hipergeométrica no central de Wallenius. Esta distribución modela el muestreo sesgado sin reposición donde los elementos tienen diferentes pesos.
   • El algoritmo utiliza los valores esperados de esta distribución, redondeados al entero más cercano, para determinar el número de coaliciones a muestrear de cada estrato.
   • Una vez determinados los conteos, las coaliciones se muestrean sin reposición dentro de cada grupo.
   • Estrategia de Emparejamiento: Para reducir aún más la varianza, el método emplea una estrategia de emparejamiento (Kroese et al., 2013). Si se muestrea una coalición $S$, su complemento $S^c$ también se incluye en el cálculo, asegurando que la suma de las características en los grupos emparejados permanezca constante.

2.2 Estimación de la Varianza mediante Métodos de Bootstrap

El artículo evalúa tres enfoques para estimar la desviación estándar de los valores de Shapley bajo el nuevo diseño de muestreo:

1. Método Intuitivo Inválido: Un estimador de varianza de Horvitz-Thompson estándar aplicado directamente al problema de mínimos cuadrados ponderados. El autor demuestra que esto es inválido porque no tiene en cuenta las dependencias específicas introducidas por la estrategia de emparejamiento y la estructura de la matriz $Z^T W Z$ en el contexto de KernelSHAP.
2. Bootstrap de Mitad Doble (Antal y Tillé, 2014): Un método conocido para poblaciones finitas donde las unidades se seleccionan mediante muestreo de Bernoulli y las unidades no seleccionadas se seleccionan dos veces al azar. Este método se implementa para comparación.
3. Bootstrap Simétrico (Nueva Contribución): Un nuevo método de bootstrap desarrollado específicamente para este contexto.
   • Mecanismo: En cada muestra de bootstrap, cada unidad de la muestra original puede aparecer 0, 1 o 2 veces.
   • Simetría: El método asegura que el número total de unidades que aparecen 0 veces sea igual al número total de unidades que aparecen 2 veces.
   • Probabilidades: Las probabilidades para que una unidad $k$ aparezca $S_k$ veces se definen como:
     • $Pr(S_k = 0) = Pr(S_k = 2) = \frac{1}{2}(1 - \frac{n}{N})$
     • $Pr(S_k = 1) = \frac{n}{N}$
   • Propiedades: Esta construcción asegura que el valor esperado $E(S_k) = 1$ y la varianza $Var(S_k) = 1 - \frac{n}{N}$, satisfaciendo las condiciones necesarias para una estimación de varianza válida en el muestreo de poblaciones finitas (consistencia de Horvitz-Thompson).
   • Gestión de No Enteros: Cuando el número esperado de ocurrencias "0" o "2" no es un entero, se introduce una variable aleatoria de Bernoulli para alternar entre los valores enteros adyacentes, asegurando que el procedimiento sea totalmente automático.

2.3 Implementación Computacional

La función de contribución $v(S)$ se estima mediante regresión sobre las coaliciones muestreadas. La implementación aprovecha matrices dispersas y la descomposición de Cholesky (paquete Matrix) para manejar modelos lineales de manera eficiente, siendo capaz de estimar medias de 65,000 modelos lineales en un solo núcleo en cuestión de minutos (Aanes, 2025).

3. Principales Contribuciones

1. Marco de Muestreo: Integración de la distribución hipergeométrica no central de Wallenius en el marco de KernelSHAP para permitir un muestreo sin reposición eficiente, evitando las ineficiencias del Problema del Coleccionista de Cupones inherentes al muestreo con reposición.
2. Bootstrap Simétrico: La introducción de un nuevo método de bootstrap, computacionalmente eficiente, diseñado para el muestreo sin reposición en poblaciones finitas. Este satisface las condiciones de momento necesarias (media y varianza) para una estimación de varianza insesgada en este contexto.
3. Análisis de la Estimación de la Varianza: Una comparación rigurosa de los estimadores de varianza, demostrando que el bootstrap estándar es inválido para este diseño específico y que el nuevo bootstrap Simétrico supera o iguala al existing doubled half bootstrap (Antal y Tillé, 2014).

4. Resultados

Se realizaron dos estudios de simulación utilizando el conjunto de datos "Life Expectancy" de Kaggle, comparando el nuevo método contra el estado del arte, el paquete de R shapr (versión 1.0.7), que muestrea con reposición.

• Estudio de Simulación Pequeño (5 características, 16 coaliciones):
  • El nuevo método de muestreo produjo estimaciones de los valores de Shapley con desviaciones estándar comparables a las de shapr.
  • El bootstrap de Antal-Tillé funcionó mal, produciendo frecuentemente matrices de rango no completo ($Z^T W Z$) y estimaciones de varianza inexactas.
  • El bootstrap Simétrico funcionó significativamente mejor que el de Antal-Tillé, aunque ocasionalmente produjo desviaciones estándar ligeramente "liberales" (menores) en comparación con la verdad de campo (remuestreo de todas las coaliciones).
• Estudio de Simulación Grande (16 características, 402 coaliciones):
  • Los métodos de Bootstrap Simétrico y Antal-Tillé produjeron estimaciones de desviación estándar indistinguibles.
  • Ambos nuevos métodos de bootstrap funcionaron ligeramente mejor que el procedimiento de bootstrap integrado en shapr, que tendía a subestimar las desviaciones estándar para varias variables.
  • El nuevo algoritmo de muestreo (sin reposición) funcionó de manera similar al método shapr (con reposición) en términos de la precisión de las estimaciones de los valores de Shapley en sí.

5. Significado y Conclusión

El artículo concluye que el algoritmo propuesto, que combina el muestreo sin reposición mediante la distribución de Wallenius con el nuevo bootstrap Simétrico, ofrece una alternativa robusta a las implementaciones existentes de KernelSHAP.

• Rendimiento: El nuevo método realiza un desempeño "similar" al método KernelSHAP mejorado del paquete shapr en cuanto a las estimaciones de punto.
• Estimación de la Varianza: El bootstrap Simétrico se destaca como un método "muy rápido computacionalmente y fácil de entender" que funciona bien, particularmente en estudios de simulación más grandes. Aborda el vacío en la literatura para un método de bootstrap "por defecto" para el muestreo aleatorio sin reposición en poblaciones finitas.
• Limitaciones: El autor señala modestamente que, en el estudio más pequeño, el bootstrap Simétrico produjo ocasionalmente desviaciones estándar que eran ligeramente pequeñas ("liberales") para ciertas variables, aunque capturó consistentemente las desviaciones estándar más grandes.
• Aplicabilidad: El método está diseñado para escenarios donde la función de contribución se estima mediante modelos lineales o modelos lineales generalizados (donde las predicciones son lineales en una escala transformada), aprovechando técnicas de computación rápida.

El trabajo establece que la teoría de poblaciones finitas puede aplicarse con éxito a la estimación de los valores de Shapley para mejorar la eficiencia del muestreo y proporcionar estimaciones de varianza válidas, superando las limitaciones teóricas de los supuestos tradicionales de bootstrap i.i.d. en este dominio.