🤖 AI

Beyond Shapley: Efficient Computation of Asymmetric Shapley Values

Este artículo introduce algoritmos eficientes para computar Valores de Shapley Asimétricos aprovechando los grafos causales, demostrando que el cálculo exacto es posible en tiempo polinomial para árboles dirigidos con raíz y proponiendo un método de aproximación uniforme basado en muestreo para DAGs causales arbitrarios para superar la complejidad #P-dura de los cálculos estándar del valor de Shapley.

Autores originales: Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola

Publicado 2026-06-25

📖 4 min de lectura☕ Lectura para el café

CC BY 4.0

Autores originales: Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que tienes un equipo de jugadores (características) trabajando juntos para ganar un juego (realizar una predicción). Quieres saber exactamente cuánto crédito merece cada jugador por la victoria. En el mundo de la IA, esto se llama Explicabilidad.

La forma más famosa de hacer esto se llama Valores de Shapley. Piensa en esto como un árbitro justo que observa cada orden posible en la que los jugadores podrían haber entrado al juego. Si el Jugador A entra primero, segundo o al último, el árbitro calcula cuánto cambió la puntuación del equipo gracias a él. La puntuación final para el Jugador A es el promedio de todos estos cambios.

El Problema con la Forma Antigua
El problema es que calcular esto para cada una de las órdenes posibles es una pesadilla. Si tienes 20 jugadores, hay miles de millones de órdenes que revisar. Para modelos de IA complejos, este cálculo es tan difícil que es prácticamente imposible de realizar de forma exacta.

Además, el método antiguo trata a todos los jugadores como iguales. Si el Jugador B es una copia del Jugador A, reciben la misma puntuación. Pero en la vida real, a veces un jugador hace que el otro actúe. Si el Jugador A causa que el Jugador B se mueva, el Jugador A es el verdadero jefe. El método antiguo pierde esta relación de "causa y efecto".

La Nueva Solución: Valores de Shapley Asimétricos (ASV)
Este artículo presenta un árbitro más inteligente llamado Valores de Shapley Asimétricos (ASV). En lugar de mirar todas las órdenes posibles, este árbitro solo observa las órdenes que tienen sentido según un Mapa Causal (un diagrama que muestra quién causa a quién).

La Analogía: Imagina una línea de ensamblaje de una fábrica. No puedes pintar un coche antes de construir el chasis. El Mapa Causal dice: "Primero el chasis, luego la pintura". El árbitro de ASV ignora cualquier orden donde alguien intente pintar antes de construir. Solo cuenta las órdenes lógicas de causa y efecto.
El Beneficio: Esto proporciona una explicación más honesta de quién causó realmente el resultado. También, sorprendentemente, hace que las matemáticas sean más fáciles en algunos casos donde el método antiguo era imposible.

Cómo lo Hicieron Rápido (Los Trucos de Magia)
Incluso con el Mapa Causal, revisar cada orden válida aún puede ser demasiado lento. Los autores idearon dos trucos ingeniosos para acelerar esto:

El Truco de "Agrupación" (Clases de Equivalencia):
Imagina que estás contando de cuántas maneras pueden alinearse las personas. Te das cuenta de que, para el propósito del cálculo, no importa si dos personas intercambian sus lugares si ambos están parados después del jefe principal. Están en el mismo "grupo".
Los autores encontraron una forma de agrupar miles de órdenes similares en "cubetas" únicas (llamadas clases de equivalencia). En lugar de revisar 1,000,000 de órdenes, podrían necesitar revisar solo 500 grupos. Esto convierte una tarea imposible en una rápida, especialmente si el Mapa Causal parece un árbol simple (como un árbol genealógico).
El Truco de "Muestreo" (Adivinar con una Muestra):
Si el mapa es demasiado desordenado para agruparlo nítidamente, utilizan un método de muestreo. En lugar de revisar cada orden válida, eligen al azar unos pocos cientos de órdenes que sigan las reglas y calculan el promedio.

La Analogía: En lugar de probar cada grano de arroz en una olla gigante para ver si está salada, tomas una cucharada de diferentes lugares. Si las cucharadas saben saladas, sabes que toda la olla está salada. El artículo muestra que este método de la "cucharada" es rápido y da una muy buena estimación.

Qué Probaron
Los autores probaron estas ideas en estructuras de datos del mundo real (como redes utilizadas para predecir el cáncer o el desarrollo infantil) y en estructuras de árboles inventadas.

Descubrieron que para estructuras tipo árbol, su método de "Agrupación" fue increíblemente rápido, reduciendo el trabajo millones de veces en comparación con la forma antigua.
Para estructuras más desordenadas, su método de "Muestreo" fue lo suficientemente rápido y preciso como para ser útil.

La Conclusión
Este artículo demuestra que, al respetar las reglas de "causa y efecto" de los datos, podemos explicar los modelos de IA de manera más precisa y más rápida. Demostraron que, para ciertos tipos de datos, un método que antes era imposible de calcular exactamente, ahora puede realizarse rápidamente; y para otros, una estimación rápida y precisa es fácil de obtener.

Resumen Técnico: Más allá de Shapley: Computación Eficiente de Valores de Shapley Asimétricos

Planteamiento del Problema

El artículo aborda los desafíos computacionales y de interpretabilidad asociados con la atribución de características en la IA Explicable (XAI). Si bien los valores de Shapley (y su instanciación en aprendizaje automático, SHAP) proporcionan un método teóricamente fundamentado para distribuir la predicción de un modelo entre las características de entrada, sufren de dos limitaciones principales:

Intratabilidad Computacional: Calcular los valores de Shapley exactos suele ser #P-duro, particularmente para modelos expresivos (por ejemplo, redes neuronales) o cuando la distribución de datos subyacente es compleja (por ejemplo, distribuciones de Naive Bayes).
Déficits de Interpretabilidad: Los valores de Shapley estándar tratan todas las características de forma simétrica. Esto no logra capturar las relaciones causales, lo que puede asignar una importancia igual a una causa y a su efecto determinista, ocultando así el verdadero proceso generador de datos.

Para abordar este segundo problema, se propusieron los Valores de Shapley Asimétricos (ASV), los cuales restringen el cálculo a permutaciones de características que respetan un grafo causal dado (un Grafo Acíclico Dirigido o DAG). Sin embargo, la complejidad computacional de los ASV no había sido investigada exhaustivamente. Este artículo investiga si la incorporación de restricciones causales puede, de hecho, hacer que la computación de las puntuaciones de atribución sea más tratable que los valores de Shapley estándar en contextos específicos.

Metodología

Los autores proponen un conjunto de algoritmos para calcular los ASV de forma exacta y aproximada, aprovechando la estructura del grafo causal y la distribución de probabilidad subyacente (modelada como una Red Bayesiana).

1. Análisis de Tractabilidad Teórica

Los autores establecen un resultado teórico respecto a la complejidad de los ASV bajo distribuciones de Naive Bayes. Demuestran que, mientras que el cálculo de los valores de Shapley estándar es intratable para ciertas familias de modelos bajo distribuciones de Naive Bayes, el cálculo de los ASV es tratable en tiempo polinomial para las mismas familias si el grafo causal utilizado para los ASV es idéntico a la estructura de la red de Naive Bayes. Esto sugiere que las restricciones causales impuestas por la distribución pueden romper las simetrías que, de otro modo, harían que el problema fuera difícil.

2. Computación Exacta mediante Clases de Equivalencia

Para extender la tractabilidad a estructuras causales más generales, específicamente árboles dirigidos con raíz, los autores introducen un método para reducir el espacio de búsqueda de las permutaciones:

Clases de Equivalencia: Definen una relación de equivalencia sobre el conjunto de ordenamientos topológicos del grafo causal. Dos ordenamientos son equivalentes con respecto a una característica $x$ si el conjunto de características que preceden a $x$ es idéntico en ambos ordenamientos.
Algoritmo: En lugar de iterar a través de todos los ordenamientos topológicos (que puede ser exponencial), el algoritmo calcula el conjunto de clases de equivalencia ( $\Lambda_x^C$ ) y el tamaño de cada clase. El ASV se calcula entonces sumando las contribuciones marginales ponderadas por el tamaño de cada clase de equivalencia.
Complejidad: Para árboles dirigidos con raíz, el número de clases de equivalencia está acotado por $h \cdot l + 1$ (donde $h$ es la profundidad y $l$ es el número de hojas). Los autores proporcionan un algoritmo de tiempo polinomial (en términos del número de clases de equivalencia) para calcular estas clases y sus tamaños.

3. Computación Aproximada mediante Muestreo

Para DAGs causales arbitrarios donde la computación exacta puede ser inviable, los autores proponen un esquema de aproximación basado en muestreo.

Muestreo de Ordenamientos Topológicos: El método se basa en el muestreo de ordenamientos topológicos de forma uniforme al azar. Los autores implementan dos enfoques:
1. Un algoritmo de conteo recursivo para politrees (grafos con al menos un camino entre cualquier par de nodos) que cuenta los ordenamientos topológicos para ponderar correctamente los nodos fuente.
2. Un algoritmo basado en caminatas aleatorias (basado en Bubley & Dyer, 1999) para DAGs generales.
Límites de Error: Formalizan que si el muestreador de ordenamiento topológico está $\epsilon_{samp}$ -cerca de la uniformidad y la función característica (valor esperado del modelo) se aproxima con un error $\epsilon_{\nu}$ , la estimación resultante de los ASV tiene un error aditivo de $O(\epsilon_{samp} + \epsilon_{\nu})$ .

Resultados Clave

Los autores evaluaron sus métodos en redes Bayesianas del mundo real (Cancer, Child) y estructuras artificiales (árboles balanceados, Naive Bayes, múltiples caminos).

Reducción del Espacio de Búsqueda: El enfoque de clases de equivalencia reduce significativamente la carga computacional en comparación con la enumeración de todos los órdenes topológicos. En la red "Child", el número de ordenamientos topológicos era $\approx 7.41 \times 10^{11}$ , mientras que el número de clases de equivalencia fue de solo $\approx 2003$ en promedio.
Eficiencia del Tiempo de Ejecución:
- El cálculo de las clases de equivalencia para tamaños de grafo prácticos tomó menos de un segundo.
- El tiempo de ejecución del algoritmo exacto estaba fuertemente correlacionado con el número de clases de equivalencia, lo que permite que la precomputación de los conteos de clases sirva como predictor del costo computacional.
- La enumeración de todos los ordenamientos topológicos se volvió inviable para grafos más grandes, mientras que el método de clases de equivalencia se mantuvo tratable.
Desempeño del Muestreo:
- El algoritmo de muestreo recursivo personalizado para politrees fue eficiente, con un escalado no lineal relativo al número de muestras debido a la generación paralela de candidatos.
- El uso de 1,000 muestras produjo un error relativo promedio de aproximadamente el 8% para los valores de ASV. El error fue menor para valores de ASV grandes y mayor para valores verdaderos muy pequeños.

Significancia y Reivindicaciones

El artículo sostiene que los ASV son un marco viable y potencialmente superior para la explicabilidad cuando la estructura causal es relevante, ya que captura dependencias que el SHAP estándar omite. La contribución principal es demostrar que las restricciones causales pueden transformar un problema intratable en uno tratable para pares específicos de modelo-distribución (por ejemplo, árboles de decisión bajo Naive Bayes).

Los autores enfatizan que, si bien los ASV ofrecen estos beneficios teóricos y prácticos, su escalabilidad depende fuertemente de la topología del grafo causal:

Para árboles dirigidos con raíz y politrees, la computación exacta es factible mediante clases de equivalencia.
Para DAGs densos o grandes, el número de clases de equivalencia aún puede crecer demasiado, lo que requiere el uso de aproximaciones basadas en muestreo.

El trabajo concluye que los ASV son una dirección prometedora para la XAI, siempre que el grafo causal sea conocido y la estructura del grafo permita la enumeración o el muestreo eficiente de los ordenamientos topológicos. Se sugiere como trabajo futuro generalizar los algoritmos exactos a clases más amplias de grafos (por ejemplo, politrees generales) y optimizar los mecanismos de muestreo.