Resumen Técnico: Estimación Aproximada Rápida de Valores de Shapley Condicionales con Explicadores Lineales

Planteamiento del Problema

El artículo aborda el cuello de botella computacional asociado con la estimación de los valores de Shapley condicionales para modelos de regresión lineal cuando las covariables son dependientes. Si bien los valores de Shapley proporcionan un desglose basado en la teoría de juegos de la contribución de las características a una predicción específica, calcular sus valores condicionales requiere estimar la salida esperada del modelo para todas las posibles subconjuntos (coaliciones) de características.

Para un modelo con $p$ predictores, existen $2^p$ coaliciones posibles. Los métodos existentes, como los enfoques Secuencial e Iterativo del paquete de R shapr, enfrentan desafíos significativos:

1. Estimación Secuencial: Requiere ajustar $2^p$ modelos de regresión separados, lo que se vuelve computacionalmente intratable a medida que $p$ aumenta.
2. Estimación Iterativa: Muestrea coaliciones hasta que se cumple un criterio de convergencia. Aunque es más rápido cuando bastan pocas coaliciones, aún puede requerir una gran fracción de todas las $2^p$ coaliciones para lograr la convergencia, lo que conduce a tiempos de ejecución largos (horas) comparables al método secuencial en casos difíciles.
3. Dependencia de Características: A diferencia de los valores de Shapley marginales, los valores condicionales deben tener en cuenta la estructura de dependencia entre las covariables, lo que requiere cálculos complejos de esperanza condicional.

Los autores pretenden desarrollar métodos que puedan estimar los coeficientes para todas las $2^p$ sub-modelos simultáneamente y de forma rápida, aprovechando la dispersión de las estructuras matemáticas subyacentes.

Metodología

El enfoque propuesto utiliza la teoría de los Campos Markovianos Gaussianos Restringidos (GMRF) y el álgebra de matrices dispersas para estimar los coeficientes de regresión para todos los sub-modelos de forma conjunta en lugar de secuencial. Los autores derivan tres algoritmos distintos:

1. El Método de Corrección Diagonal (Aproximado)

Este método aproxima la regresión restringida modificando la matriz de precisión ($Q = X^T X$) del modelo completo.

• Mecanismo: Para imponer una restricción donde un coeficiente específico es cero (es decir, la característica es excluida de un sub-modelo), se añade un valor escalar grande $\kappa$ al elemento diagonal correspondiente de la matriz de precisión.
• Base Teórica: Basado en la identidad de la matriz de Woodbury, añadir $\kappa A^T A$ (donde $A$ es una matriz de restricción) a $Q$ aproxima la matriz de covarianza condicional cuando $\kappa \to \infty$.
• Implementación: Se construye una matriz de restricción conjunta $A$ para los $2^p$ modelos. El método resuelve el sistema lineal $(Q_F + \kappa A^T A)^{-1}m$, donde $Q_F$ es una matriz bloque-diagonal que contiene la matriz de precisión del modelo completo repetida $2^p$ veces.
• Ajuste: Requiere un parámetro de ajuste $\kappa$, sugerido como $10^5$ veces el autovalor más grande de la matriz de precisión original.

2. El Método de Proyección (Aproximado)

Este método proyecta el espacio de parámetros para eliminar los parámetros restringidos.

• Mecanismo: Se aplica una matriz de proyección $Z = I - A^T A$ a la matriz de precisión. El modelo restringido se trata como un GMRF intrínseco. Para asegurar la estabilidad numérica (definición positiva), se añade un pequeño escalar $\epsilon$ a la diagonal de la matriz de precisión proyectada ($Z Q Z + \epsilon I$).
• Base Teórica: A medida que $\epsilon \to 0^+$, la solución converge a las estimaciones restringidas exactas.
• Implementación: Resuelve el sistema $Z(Z Q_F Z + \epsilon I)^{-1} Z m$.
• Ajuste: Requiere un pequeño parámetro de ajuste $\epsilon$ (por ejemplo, $10^{-5}$), elegido para ser pequeño en relación con el autovalor más pequeño de $Q$ pero lo suficientemente grande para una descomposición de Cholesky estable.

3. El Método de Transformación Exacta (Exacto)

Este método proporciona una solución exacta sin errores de aproximación ni parámetros de ajuste.

• Mecanismo: En lugar de trabajar en el espacio de parámetros completo y forzar los coeficientes a cero, el método transforma el problema en un espacio de menor dimensión que contiene solo los parámetros activos.
• Implementación: Se construye una matriz de mapeo $E$ para seleccionar solo los parámetros activos para cada sub-modelo. El sistema se resuelve como $(E Q_F E^T)^{-1} E m$.
• Ventaja: Elimina la necesidad de términos de penalización grandes ($\kappa$) o términos de regularización pequeños ($\epsilon$), evitando la posible inestabilidad numérica o el sesgo de aproximación.

Todos los tres métodos utilizan álgebra de matrices dispersas (específicamente la descomposición de Cholesky) para manejar la estimación conjunta de miles de modelos de manera eficiente. La matriz de precisión conjunta es altamente dispersa porque los modelos son independientes (estructura bloque-diagonal), y los ceros fuera de la diagonal indican independencia condicional.

Contribuciones Clave

1. Tres Nuevos Algoritmos: El artículo introduce dos métodos aproximados (Corrección Diagonal, Proyección) y un método exacto (Transformación Exacta) para la estimación conjunta de todos los sub-modelos en regresión lineal.
2. Pruebas de Convergencia: Los autores proporcionan pruebas matemáticas que demuestran que los métodos aproximados convergen a las estimaciones condicionales reales a medida que sus respectivos parámetros de ajuste $\kappa \to \infty$ y $\epsilon \to 0^+$.
3. Eficiencia Computacional: Al explotar la dispersión y la estimación conjunta, los métodos reducen el tiempo de computación de horas (típico de shapr) a segundos o minutos, incluso al enumerar todas las $2^p$ coaliciones.
4. Validación Empírica: Estudios numéricos extensos comparan los nuevos métodos contra el paquete shapr (versiones Secuencial e Iterativa) a través de tres conjuntos de datos: Adult Income, un conjunto de datos Gaussiano simulado y el conjunto de datos WHO Life Expectancy.

Resultados

Los estudios de casos numéricos arrojan los siguientes hallazgos:

• Precisión: Las estimaciones de los valores de Shapley producidas por los nuevos métodos son virtualmente idénticas al método Secuencial de shapr (utilizado como la verdad fundamental para la enumeración completa).
  • En el conjunto de datos Adult ($p=11$), el error absoluto mediano (MedAE) entre los nuevos métodos y el método Secuencial fue del orden de $10^{-9}$.
  • En el conjunto de datos Simulado ($p=21$), el MedAE fue del orden de $10^{-7}$ a $10^{-5}$.
  • En el conjunto de datos WHO ($p=16$), el MedAE fue del orden de $10^{-6}$.
• Velocidad:
  • Conjunto de datos Adult: Los nuevos métodos corrieron en 2.5 a 9 segundos, mientras que shapr (Secuencial e Iterativo) tomó de 17 a 19 minutos.
  • Conjunto de datos Simulado: Los nuevos métodos tomaron 1.4 a 2.5 minutos para estimar todos los $2^{21} \approx 2.1$ millones de modelos. El método Iterativo de shapr fue más rápido (6.48 segundos), pero solo estimó 200 coaliciones, no el conjunto completo.
  • Conjunto de datos WHO: Los nuevos métodos tomaron 1.1 a 1.2 minutos. El método Secuencial de shapr tomó 131 minutos (2.2 horas), y el método Iterativo tomó 16 minutos (paralelo) o 36 minutos (serial).
• Escalabilidad: Los métodos estimaron con éxito más de dos millones de sub-modelos en el estudio simulado en cuestión de minutos. La principal limitación identificada es la restricción de memoria (Maldición de la Dimensionalidad) cuando $p$ supera aproximadamente 21 en hardware estándar, aunque los autores señalan que esto puede mitigarse con más RAM o paquetes de matrices dispersas especializados.

Significancia y Reclamaciones

El artículo afirma que los métodos propuestos ofrecen una mejora sustancial en la eficiencia computacional para la estimación de valores de Shapley condicionales sin sacrificar la precisión.

• Superioridad en la Enumeración Completa: Cuando el método Iterativo de shapr requiere una gran fracción de coaliciones para converger (como se observa en los conjuntos de datos Adult y WHO), los nuevos métodos son "sustancialmente más rápidos" manteniendo una "precisión igual o mejor".
• Enumeración Exhaustiva: A diferencia del enfoque iterativo que muestrea coaliciones, los nuevos métodos proporcionan una enumeración completa de las $2^p$ sub-coaliciones, asegurando que no se pierda información debido a la varianza de muestreo.
• Recomendación: Los autores recomiendan el Método de Transformación Exacta para el uso práctico. Aunque los tres métodos producen resultados comparables, el método Exacto no tiene parámetros de ajuste, eliminando así la necesidad de selección de hiperparámetros y las posibles fuentes de error de aproximación.
• Potencial Futuro: Los autores sugieren que la metodología puede extenderse para manejar splines (por ejemplo, del paquete rms) y que la paralelización (por ejemplo, vía OpenMP) podría reducir aún más los tiempos de ejecución, aunque la implementación actual depende de la ejecución serial para una comparación justa con el paquete shapr paralelizado.

El artículo concluye que estos métodos hacen que el cálculo exacto de los valores de Shapley condicionales para modelos lineales con tipos mixtos de covariables sea factible en escenarios donde antes era computacionalmente prohibitivo.