El valor de Shapley es un concepto de solución en la teoría de juegos cooperativos que proporciona un método para distribuir de manera justa las ganancias o costos totales entre un grupo de jugadores que han colaborado. Nombrado en honor a Lloyd Shapley, quien lo introdujo en 1951, responde a la pregunta de cuánto crédito o culpa merece cada participante cuando se produce un resultado colectivo. El método calcula la contribución marginal promedio de cada jugador en todas las coaliciones posibles, asegurando una distribución que satisface cuatro propiedades fundamentales: eficiencia, simetría, aditividad y la propiedad del jugador ficticio. Más allá de sus orígenes en economía, el valor de Shapley se ha convertido en una piedra angular del Machine learning interpretable, donde se utiliza para atribuir las predicciones de modelos complejos a características de entrada individuales.
La idea central es evaluar cómo cambia el resultado general cuando un jugador se une a cada subconjunto posible de otros jugadores, y luego promediar estos cambios sobre todos los subconjuntos y todos los órdenes de unión posibles. Este enfoque tiene en cuenta las interacciones entre jugadores, reconociendo que una contribución puede depender de quién más ya está en la coalición. Debido a que es la única regla de distribución que satisface simultáneamente las cuatro propiedades axiomáticas, a menudo se describe como la forma justa única de dividir las ganancias cooperativas.
Definición
En un juego coalicional, un conjunto de jugadores \(N\) puede formar coaliciones \(S \subseteq N\), y una función de valor \(v(S)\) asigna el pago total que los miembros de \(S\) pueden obtener al cooperar. El valor de Shapley para el jugador \(i\) viene dado por la fórmula:
\[\varphi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|! (n - |S| - 1)!}{n!} (v(S \cup \{i\}) - v(S))\]
donde \(n\) es el número total de jugadores. El término \(v(S \cup \{i\}) - v(S)\) es la contribución marginal del jugador \(i\) a la coalición \(S\). El peso combinatorio \(\frac{|S|! (n - |S| - 1)!}{n!}\) tiene en cuenta el número de permutaciones en las que los jugadores en \(S\) preceden a \(i\) y los jugadores restantes lo siguen. Una formulación equivalente promedia la contribución marginal sobre todos los \(n!\) órdenes posibles de los jugadores, donde \(P_i^R\) denota el conjunto de jugadores que preceden a \(i\) en el orden \(R\):
\[\varphi_i(v) = \frac{1}{n!} \sum_R \left[ v(P_i^R \cup \{i\}) - v(P_i^R) \right]\]
Esta interpretación imagina que la coalición se forma de un jugador a la vez, recibiendo cada jugador su contribución marginal como compensación, y luego promediando sobre todas las secuencias de formación posibles.
Propiedades Axiomáticas
El valor de Shapley se caracteriza de manera única por cuatro axiomas, que son ampliamente aceptados como definitorios de una distribución justa:
- Eficiencia: La suma de los valores de Shapley de todos los jugadores es igual al valor total de la gran coalición, \(\sum_{i \in N} \varphi_i(v) = v(N)\). Esto asegura que no se pierda ni se cree valor.
- Simetría: Si dos jugadores \(i\) y \(j\) contribuyen de manera idéntica a cada coalición (es decir, \(v(S \cup \{i\}) = v(S \cup \{j\})\) para todo \(S\) que no contenga a ninguno de ellos), reciben partes iguales.
- Aditividad: Para dos juegos \(v\) y \(w\), el valor de Shapley del juego combinado \(v+w\) es la suma de los valores de Shapley individuales, \(\varphi_i(v+w) = \varphi_i(v) + \varphi_i(w)\). Esta propiedad apoya la descomposición de problemas complejos.
- Jugador ficticio: Si un jugador \(i\) no añade valor a ninguna coalición (es decir, \(v(S \cup \{i\}) = v(S)\) para todo \(S\)), su valor de Shapley es cero.
Estos axiomas fueron formalizados en el artículo de Shapley de 1951 y refinados posteriormente en su publicación de 1953. Aseguran que el valor no sea arbitrario, sino que siga criterios de equidad razonables.
Aplicaciones en Economía y Negocios
En la teoría de juegos cooperativos, el valor de Shapley se ha utilizado para asignar costos y beneficios en diversos entornos económicos. Por ejemplo, en una sociedad empresarial, los socios pueden usarlo para dividir las ganancias según sus contribuciones marginales a diferentes combinaciones de proyectos. Se ha aplicado a la asignación de costos en empresas conjuntas, como compartir el costo de una infraestructura común entre múltiples usuarios. En la gestión de la cadena de suministro, ayuda a determinar precios justos para los componentes cuando las empresas colaboran para producir un producto final. El método también se utiliza en el análisis del poder de voto, donde mide la influencia de cada votante en un sistema de votación ponderada, aunque el índice de poder de Banzhaf, estrechamente relacionado, a veces se prefiere en ese contexto.
Valores de Shapley en el Aprendizaje Automático
En Machine learning, el valor de Shapley se ha adaptado para explicar predicciones individuales de modelos, un campo conocido como atribución de características. Los jugadores son las características de entrada, y la función de valor \(v(S)\) es la predicción del modelo cuando solo se conocen las características del subconjunto \(S\), típicamente marginalizando las otras características. El valor de Shapley de una característica mide su contribución promedio a la predicción, teniendo en cuenta las interacciones con todas las demás características. Este enfoque es agnóstico al modelo, lo que significa que se puede aplicar a cualquier modelo predictivo, incluidos los Deep learning, los conjuntos de Neural network y los sistemas de Large language model.
Una implementación práctica clave es SHAP (SHapley Additive exPlanations), introducido por Scott Lundberg y Su-In Lee en 2017. SHAP proporciona algoritmos eficientes para aproximar los valores de Shapley en modelos complejos, ya que el cálculo exacto es exponencial en el número de características. El método se ha convertido en una herramienta estándar para la interpretabilidad de modelos, ayudando a los científicos de datos y reguladores a entender por qué un modelo tomó una decisión particular.
Desafíos Computacionales y Aproximaciones
El valor de Shapley exacto requiere sumar sobre \(2^n\) subconjuntos, lo que es computacionalmente inviable para modelos con muchas características. Para un modelo con 30 características, hay más de mil millones de coaliciones posibles. Se han desarrollado varias técnicas de aproximación:
- Muestreo de Monte Carlo: Muestrear aleatoriamente permutaciones o subconjuntos y promediar las contribuciones marginales. Esto proporciona una estimación insesgada con una varianza controlable.
- SHAP con TreeSHAP: Para modelos basados en árboles como bosques aleatorios y boosting de gradiente, TreeSHAP calcula valores de Shapley exactos en tiempo polinómico explotando la estructura del árbol.
- KernelSHAP: Un método agnóstico al modelo que utiliza una regresión lineal ponderada para aproximar los valores de Shapley, a menudo utilizado para modelos de caja negra.
- Métodos basados en gradientes: Para modelos diferenciables, se pueden calcular aproximaciones utilizando gradientes, aunque pueden no satisfacer todos los axiomas exactamente.
Estas aproximaciones han hecho que los valores de Shapley sean prácticos para aplicaciones del mundo real, incluida la calificación crediticia, el diagnóstico médico y el procesamiento del lenguaje natural.
Relación con Otros Métodos de Atribución
El valor de Shapley se compara a menudo con otras técnicas de atribución de características. A diferencia de métodos simples como la importancia por permutación o los mapas de prominencia basados en gradientes, los valores de Shapley tienen en cuenta las interacciones entre características y satisfacen la propiedad de eficiencia, asegurando que las atribuciones sumen la salida del modelo. Sin embargo, asume que las características son independientes al marginalizar, lo que puede llevar a muestras poco realistas si las características están altamente correlacionadas. Alternativas como LIME (Local Interpretable Model-agnostic Explanations) son más rápidas pero no garantizan las mismas propiedades axiomáticas. En la teoría de juegos cooperativos, el valor de Shapley es uno de varios conceptos de solución, incluidos el nucleolo y el núcleo, pero es el único que satisface los cuatro axiomas simultáneamente.
Extensiones y Variantes
Se han propuesto varias extensiones del valor de Shapley para diferentes contextos. El valor de Shapley ponderado permite que los jugadores tengan diferentes pesos, reflejando un poder de negociación desigual. El índice de poder de Shapley-Shubik aplica el valor a juegos de votación, midiendo la probabilidad de que un jugador sea decisivo. En el aprendizaje automático, variantes como los índices de interacción de Shapley descomponen la atribución total en efectos principales y efectos de interacción entre características. Para datos de series temporales, los valores de Shapley dinámicos tienen en cuenta las dependencias temporales. Estas extensiones preservan la idea central del promedio justo de contribuciones marginales mientras se adaptan a estructuras de problemas específicas.
Limitaciones y Críticas
A pesar de su atractivo teórico, el valor de Shapley tiene limitaciones. La suposición de independencia de características en aplicaciones de aprendizaje automático puede producir atribuciones engañosas cuando las características están correlacionadas. El costo computacional exponencial, incluso con aproximaciones, puede ser prohibitivo para datos de muy alta dimensionalidad. Además, la función de valor en modelos predictivos no siempre está bien definida, ya que marginalizar características requiere una distribución sobre el espacio de características, que puede no ser conocida. Los críticos argumentan que las propiedades axiomáticas, aunque elegantes, pueden no alinearse siempre con las nociones humanas de equidad en escenarios prácticos. No obstante, el valor de Shapley sigue siendo un concepto fundamental tanto en la teoría de juegos como en la IA interpretable, con investigación activa que aborda estos desafíos.
Contexto Histórico
Lloyd Shapley introdujo el valor en 1951 mientras estaba en la Corporación RAND, y fue publicado formalmente en 1953. Su trabajo se basó en ideas anteriores de la teoría de juegos cooperativos, particularmente el trabajo de John von Neumann y Oskar Morgenstern. Shapley recibió posteriormente el Premio Nobel Memorial de Ciencias Económicas en 2012, junto con Alvin Roth, por sus contribuciones a la teoría de juegos. La adopción del valor de Shapley en el aprendizaje automático comenzó en la década de 2010, impulsada por la necesidad de interpretabilidad de modelos a medida que los sistemas de IA se volvían más complejos. Hoy en día, es una herramienta estándar en el arsenal de los científicos de datos y está implementado en bibliotecas importantes como SHAP y scikit-learn.