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. Foi introduzido por Lloyd Shapley em 1951 e, desde então, tornou-se uma ferramenta fundamental na economia, na ciência política e, mais recentemente, no aprendizado de máquina para interpretar previsões de modelos. O valor atribui a cada jogador uma parcela do pagamento total com base em sua contribuição marginal média em todas as coalizões possíveis de outros jogadores. É a distribuição única que satisfaz quatro propriedades-chave: eficiência, simetria, aditividade e a propriedade do jogador nulo, tornando-o um padrão amplamente aceito para alocação justa.
No contexto do aprendizado de máquina, o valor de Shapley é usado para explicar previsões individuais, atribuindo a contribuição de cada característica à saída do modelo. Essa abordagem, frequentemente chamada de SHAP (SHapley Additive exPlanations), fornece uma estrutura unificada para importância de características que é tanto teoricamente fundamentada quanto praticamente aplicável. A complexidade computacional de calcular valores de Shapley exatos cresce exponencialmente com o número de características, levando ao desenvolvimento de vários métodos de aproximação.
Definição e Fórmula
Formalmente, considere um jogo cooperativo com um conjunto de jogadores \( N \) e uma função de valor \( v \) que atribui um número real a cada subconjunto (coalizão) \( S \subseteq N \). O valor de Shapley para o jogador \( i \) é definido como:
\[ \phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|! (n - |S| - 1)!}{n!} (v(S \cup \{i\}) - v(S)) \]
onde \( n = |N| \). Esta fórmula pode ser interpretada como a contribuição marginal média do jogador \( i \) em todas as ordens possíveis em que a coalizão pode ser formada. Uma formulação equivalente soma sobre todas as \( n! \) permutações de jogadores, onde \( P_i^R \) é o conjunto de jogadores que precedem \( i \) na ordem \( R \):
\[ \phi_i(v) = \frac{1}{n!} \sum_R \left[ v(P_i^R \cup \{i\}) - v(P_i^R) \right] \]
A função de valor \( v(S) \) representa o pagamento total que a coalizão \( S \) pode alcançar ao cooperar. O valor de Shapley distribui o valor total \( v(N) \) entre todos os jogadores, garantindo que cada jogador receba sua contribuição média para o resultado geral.
Propriedades
O valor de Shapley é o único conceito de solução que satisfaz os seguintes quatro axiomas, considerados essenciais para uma distribuição justa:
- Eficiência: A soma de todos os valores de Shapley é igual ao valor total da grande coalizão, \( \sum_{i \in N} \phi_i(v) = v(N) \). Isso garante que todo o pagamento seja distribuído.
- Simetria: Se dois jogadores \( i \) e \( j \) contribuem igualmente para todas as coalizões (ou seja, \( v(S \cup \{i\}) = v(S \cup \{j\}) \) para todo \( S \subseteq N \setminus \{i,j\} \)), então eles recebem o mesmo valor de Shapley. Isso garante justiça entre contribuintes idênticos.
- Aditividade: Para quaisquer dois jogos \( v \) e \( w \), o valor de Shapley do jogo combinado \( v + w \) é a soma dos valores de Shapley dos jogos individuais, \( \phi_i(v + w) = \phi_i(v) + \phi_i(w) \). Essa propriedade permite a decomposição de jogos complexos.
- Propriedade do 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 \subseteq N \setminus \{i\} \)), então \( \phi_i(v) = 0 \). Isso garante que jogadores que não contribuem não recebam nada.
Essas propriedades tornam o valor de Shapley um método único e fundamentado para alocar crédito ou custo entre os participantes.
Aplicações em Aprendizado de Máquina
No aprendizado de máquina, o valor de Shapley é aplicado para interpretar previsões de modelos, tratando cada característica como um jogador e a saída do modelo como a função de valor. Para uma determinada previsão, o valor de Shapley de uma característica quantifica sua contribuição para a diferença entre a saída do modelo e a previsão média. Essa abordagem, conhecida como SHAP, foi popularizada por Scott Lundberg e Su-In Lee em 2017. Os valores SHAP fornecem uma medida unificada de importância de características que é consistente com os axiomas do valor de Shapley, tornando-os uma ferramenta confiável para interpretabilidade de modelos.
O uso de valores de Shapley no aprendizado de máquina cresceu significativamente, particularmente em campos onde entender decisões de modelos é crítico, como finanças, saúde e sistemas autônomos. Por exemplo, na pontuação de crédito, os valores SHAP podem revelar quais fatores mais influenciam uma decisão de aprovação de empréstimo, auxiliando na conformidade regulatória e em auditorias de justiça. No diagnóstico médico, eles ajudam os clínicos a entender por que um modelo prevê uma determinada condição, aumentando a confiança em decisões assistidas por IA.
Desafios Computacionais
Calcular valores de Shapley exatos requer avaliar a função de valor para todas as \( 2^n \) coalizões possíveis, o que é computacionalmente inviável para modelos com muitas características. Para um modelo com \( n \) características, a complexidade é \( O(2^n) \), tornando o cálculo exato impraticável além de algumas dezenas de características. Para resolver isso, vários métodos de aproximação foram desenvolvidos:
- Amostragem de Monte Carlo: Amostrar aleatoriamente permutações de características e calcular a média das contribuições marginais, fornecendo uma estimativa não enviesada com variância controlável.
- TreeSHAP: Um algoritmo especificamente projetado para modelos baseados em árvores (por exemplo, florestas aleatórias, gradiente boosting) que calcula valores de Shapley exatos em tempo polinomial, explorando a estrutura das árvores de decisão.
- KernelSHAP: Um método agnóstico de modelo que usa regressão linear ponderada para aproximar valores de Shapley, adequado para qualquer modelo de caixa-preta.
- Métodos baseados em gradiente: Para redes neurais, aproximações usando gradientes ou mecanismos de atenção podem fornecer estimativas rápidas, embora possam não satisfazer todos os axiomas de Shapley.
Essas aproximações tornaram viável aplicar valores de Shapley a modelos de aprendizado de máquina em larga escala, incluindo redes neurais profundas e grandes modelos de linguagem, onde a interpretabilidade é cada vez mais importante.
Conceitos Relacionados e Extensões
O valor de Shapley foi estendido e adaptado de várias maneiras para atender a diferentes necessidades. Na teoria dos jogos cooperativos, o índice de poder Shapley-Shubik e o índice de poder Banzhaf são aplicações especializadas para jogos de votação. No aprendizado de máquina, o SHAP foi estendido para lidar com interações entre características, fornecendo atribuições de segunda ordem que capturam efeitos sinérgicos. Além disso, o conceito foi aplicado para explicar o comportamento de grandes modelos de linguagem, onde ajuda a identificar quais partes do texto de entrada mais influenciam a saída gerada.
O valor de Shapley também está relacionado a outros métodos de atribuição, como LIME (Local Interpretable Model-agnostic Explanations), mas oferece garantias teóricas mais fortes devido à sua base axiomática. Enquanto o LIME foca na fidelidade local, o SHAP garante consistência e precisão local, tornando-o uma escolha preferida em muitas aplicações práticas.
Contexto Histórico
Lloyd Shapley introduziu o conceito em seu artigo de 1951 "A Value for n-Person Games", que lançou as bases para a teoria dos jogos cooperativos. Seu trabalho lhe rendeu o Prêmio Nobel Memorial em Ciências Econômicas em 2012, compartilhado com Alvin Roth, por contribuições à teoria de alocações estáveis e à prática de design de mercado. O valor de Shapley desde então se tornou uma pedra angular da teoria econômica, influenciando campos como alocação de custos, divisão de lucros e análise de redes.
Na década de 2010, o avanço do aprendizado de máquina e a necessidade de interpretabilidade de modelos trouxeram o valor de Shapley para o centro das atenções. Pesquisadores reconheceram que os axiomas de justiça em jogos cooperativos se alinham com os requisitos para explicar previsões de modelos, levando ao desenvolvimento do SHAP e sua adoção generalizada. Hoje, o valor de Shapley é uma ferramenta padrão no kit de ferramentas de cientistas de dados e pesquisadores de IA, preenchendo a lacuna entre a teoria dos jogos e a inteligência artificial moderna.
Veja Também
- Aprendizado de Máquina
- Inteligência Artificial
- Aprendizado Profundo
- Rede Neural
- Poda de Modelo
- Aumento de Dados
Referências
- Shapley, L. S. (1951). "A Value for n-Person Games." In Contributions to the Theory of Games, volume II.
- Lundberg, S. M., & Lee, S.-I. (2017). "A Unified Approach to Interpreting Model Predictions." Advances in Neural Information Processing Systems.
- Strumbelj, E., & Kononenko, I. (2014). "Explaining Prediction Models and Individual Predictions with Feature Contributions." Knowledge and Information Systems.