O valor de Shapley é um conceito de solução na teoria dos jogos cooperativos que fornece um método para distribuir de forma justa os ganhos ou custos totais entre um grupo de jogadores que colaboraram. Nomeado em homenagem a Lloyd Shapley, que o introduziu em 1951, ele responde à pergunta de quanto crédito ou culpa cada participante merece quando um resultado coletivo é produzido. O método calcula a contribuição marginal média de cada jogador em todas as coalizões possíveis, garantindo uma distribuição que satisfaz quatro propriedades fundamentais: eficiência, simetria, aditividade e a propriedade do jogador nulo. Além de suas origens na economia, o valor de Shapley tornou-se uma pedra angular do aprendizado de máquina interpretável, onde é usado para atribuir as previsões de modelos complexos a características individuais de entrada.
A ideia central é avaliar como o resultado geral muda quando um jogador se junta a cada subconjunto possível de outros jogadores e, em seguida, calcular a média dessas mudanças em todos os subconjuntos e em todas as ordens possíveis de entrada. Essa abordagem leva em conta as interações entre os jogadores, reconhecendo que uma contribuição pode depender de quem já está na coalizão. Por ser a única regra de distribuição que satisfaz simultaneamente as quatro propriedades axiomáticas, é frequentemente descrito como a única maneira justa de dividir ganhos cooperativos.
Definição
Em um jogo coalicional, um conjunto de jogadores \(N\) pode formar coalizões \(S \subseteq N\), e uma função de valor \(v(S)\) atribui o pagamento total que os membros de \(S\) podem obter ao cooperar. O valor de Shapley para o jogador \(i\) é dado pela fórmula:
\[\varphi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|! (n - |S| - 1)!}{n!} (v(S \cup \{i\}) - v(S))\]
onde \(n\) é o número total de jogadores. O termo \(v(S \cup \{i\}) - v(S)\) é a contribuição marginal do jogador \(i\) para a coalizão \(S\). O peso combinatório \(\frac{|S|! (n - |S| - 1)!}{n!}\) contabiliza o número de permutações em que os jogadores em \(S\) precedem \(i\) e os jogadores restantes o seguem. Uma formulação equivalente calcula a média da contribuição marginal sobre todas as \(n!\) ordens possíveis dos jogadores, onde \(P_i^R\) denota o conjunto de jogadores que precedem \(i\) na ordem \(R\):
\[\varphi_i(v) = \frac{1}{n!} \sum_R \left[ v(P_i^R \cup \{i\}) - v(P_i^R) \right]\]
Essa interpretação imagina a coalizão sendo formada um jogador por vez, com cada jogador recebendo sua contribuição marginal como compensação, e então calcula a média sobre todas as sequências de formação possíveis.
Propriedades Axiomáticas
O valor de Shapley é caracterizado de forma única por quatro axiomas, que são amplamente aceitos como definidores de uma distribuição justa:
- Eficiência: A soma dos valores de Shapley de todos os jogadores é igual ao valor total da grande coalizão, \(\sum_{i \in N} \varphi_i(v) = v(N)\). Isso garante que nenhum valor seja perdido ou criado.
- Simetria: Se dois jogadores \(i\) e \(j\) contribuem de forma idêntica para toda coalizão (ou seja, \(v(S \cup \{i\}) = v(S \cup \{j\})\) para todo \(S\) que não contenha nenhum deles), eles recebem partes iguais.
- Aditividade: Para dois jogos \(v\) e \(w\), o valor de Shapley do jogo combinado \(v+w\) é a soma dos valores de Shapley individuais, \(\varphi_i(v+w) = \varphi_i(v) + \varphi_i(w)\). Essa propriedade suporta a decomposição de problemas complexos.
- Jogador nulo: Se um jogador \(i\) não adiciona valor a nenhuma coalizão (ou seja, \(v(S \cup \{i\}) = v(S)\) para todo \(S\)), seu valor de Shapley é zero.
Esses axiomas foram formalizados no artigo de Shapley de 1951 e posteriormente refinados em sua publicação de 1953. Eles garantem que o valor não seja arbitrário, mas siga critérios razoáveis de justiça.
Aplicações em Economia e Negócios
Na teoria dos jogos cooperativos, o valor de Shapley tem sido usado para alocar custos e benefícios em diversos contextos econômicos. Por exemplo, em uma parceria de negócios, os parceiros podem usá-lo para dividir lucros com base em suas contribuições marginais para diferentes combinações de projetos. Ele foi aplicado à alocação de custos em joint ventures, como o compartilhamento do custo de uma infraestrutura comum entre múltiplos usuários. Na gestão da cadeia de suprimentos, ajuda a determinar preços justos para componentes quando empresas colaboram para produzir um produto final. O método também é usado na análise de poder de voto, onde mede a influência de cada eleitor em um sistema de votação ponderada, embora o índice de poder de Banzhaf, intimamente relacionado, seja às vezes preferido nesse contexto.
Valores de Shapley em Aprendizado de Máquina
No aprendizado de máquina, o valor de Shapley foi adaptado para explicar previsões individuais de modelos, um campo conhecido como atribuição de características. Os jogadores são as características de entrada, e a função de valor \(v(S)\) é a previsão do modelo quando apenas as características no subconjunto \(S\) são conhecidas, tipicamente marginalizando as outras características. O valor de Shapley de uma característica mede sua contribuição média para a previsão, levando em conta interações com todas as outras características. Essa abordagem é agnóstica ao modelo, o que significa que pode ser aplicada a qualquer modelo preditivo, incluindo redes de aprendizado profundo, conjuntos de redes neurais e sistemas de modelos de linguagem de grande escala.
Uma implementação prática fundamental é o SHAP (SHapley Additive exPlanations), introduzido por Scott Lundberg e Su-In Lee em 2017. O SHAP fornece algoritmos eficientes para aproximar valores de Shapley para modelos complexos, pois o cálculo exato é exponencial no número de características. O método tornou-se uma ferramenta padrão para interpretabilidade de modelos, ajudando cientistas de dados e reguladores a entender por que um modelo tomou uma decisão específica.
Desafios Computacionais e Aproximações
O valor de Shapley exato requer a soma sobre \(2^n\) subconjuntos, o que é computacionalmente inviável para modelos com muitas características. Para um modelo com 30 características, existem mais de um bilhão de coalizões possíveis. Várias técnicas de aproximação foram desenvolvidas:
- Amostragem de Monte Carlo: Amostrar aleatoriamente permutações ou subconjuntos e calcular a média das contribuições marginais. Isso fornece uma estimativa não enviesada com variância controlável.
- SHAP com TreeSHAP: Para modelos baseados em árvores, como florestas aleatórias e gradient boosting, o TreeSHAP calcula valores de Shapley exatos em tempo polinomial explorando a estrutura das árvores.
- KernelSHAP: Um método agnóstico ao modelo que usa regressão linear ponderada para aproximar valores de Shapley, frequentemente usado para modelos de caixa-preta.
- Métodos baseados em gradientes: Para modelos diferenciáveis, aproximações podem ser calculadas usando gradientes, embora possam não satisfazer todos os axiomas exatamente.
Essas aproximações tornaram os valores de Shapley práticos para aplicações do mundo real, incluindo pontuação de crédito, diagnóstico médico e processamento de linguagem natural.
Relação com Outros Métodos de Atribuição
O valor de Shapley é frequentemente comparado a outras técnicas de atribuição de características. Ao contrário de métodos simples, como importância por permutação ou mapas de saliência baseados em gradientes, os valores de Shapley levam em conta interações entre características e satisfazem a propriedade de eficiência, garantindo que as atribuições somem à saída do modelo. No entanto, ele assume que as características são independentes ao marginalizar, o que pode levar a amostras irreais se as características forem altamente correlacionadas. Alternativas como o LIME (Local Interpretable Model-agnostic Explanations) são mais rápidas, mas não garantem as mesmas propriedades axiomáticas. Na teoria dos jogos cooperativos, o valor de Shapley é um dos vários conceitos de solução, incluindo o nucleolus e o core, mas é o único que satisfaz todos os quatro axiomas simultaneamente.
Extensões e Variantes
Várias extensões do valor de Shapley foram propostas para diferentes contextos. O valor de Shapley ponderado permite que os jogadores tenham pesos diferentes, refletindo poder de barganha desigual. O índice de poder de Shapley-Shubik aplica o valor a jogos de votação, medindo a probabilidade de um jogador ser decisivo. No aprendizado de máquina, variantes como índices de interação de Shapley decompõem a atribuição total em efeitos principais e efeitos de interação entre características. Para dados de séries temporais, valores de Shapley dinâmicos levam em conta dependências temporais. Essas extensões preservam a ideia central de média justa de contribuições marginais, adaptando-se a estruturas de problemas específicas.
Limitações e Críticas
Apesar de seu apelo teórico, o valor de Shapley tem limitações. A suposição de independência das características em aplicações de aprendizado de máquina pode produzir atribuições enganosas quando as características são correlacionadas. O custo computacional exponencial, mesmo com aproximações, pode ser proibitivo para dados de alta dimensionalidade. Além disso, a função de valor em modelos preditivos nem sempre é bem definida, pois marginalizar características requer uma distribuição sobre o espaço de características, que pode não ser conhecida. Críticos argumentam que as propriedades axiomáticas, embora elegantes, podem nem sempre se alinhar com noções humanas de justiça em cenários práticos. No entanto, o valor de Shapley permanece um conceito fundamental tanto na teoria dos jogos quanto na IA interpretável, com pesquisa ativa abordando esses desafios.
Contexto Histórico
Lloyd Shapley introduziu o valor em 1951 enquanto estava na RAND Corporation, e foi formalmente publicado em 1953. Seu trabalho baseou-se em ideias anteriores na teoria dos jogos cooperativos, particularmente o trabalho de John von Neumann e Oskar Morgenstern. Shapley posteriormente recebeu o Prêmio Nobel Memorial de Ciências Econômicas em 2012, conjuntamente com Alvin Roth, por suas contribuições à teoria dos jogos. A adoção do valor de Shapley no aprendizado de máquina começou na década de 2010, impulsionada pela necessidade de interpretabilidade de modelos à medida que os sistemas de IA se tornaram mais complexos. Hoje, é uma ferramenta padrão no kit de ferramentas de cientistas de dados e está implementado em bibliotecas importantes como SHAP e scikit-learn.