Resumo Técnico: Aproximação do Valor de Shapley Baseada em Jogos k-Aditivos

Declaração do Problema

O valor de Shapley é a solução padrão para problemas de divisão justa, amplamente adotado em IA Explicável (XAI) para quantificar a contribuição individual de recursos ou pontos de dados para o desempenho de um modelo. No entanto, seu cálculo exato requer a avaliação de todas as $2^n$ coalizões possíveis de $n$ jogadores, resultando em complexidade computacional exponencial. Isso torna o cálculo exato inviável para modelos com um número moderado de recursos ou ao avaliar modelos complexos e intensivos em recursos. Consequentemente, métodos de aproximação são necessários, mas as abordagens existentes frequentemente lutam para equilibrar a eficiência computacional com a precisão das pontuações de importância resultantes.

Metodologia: SVAkADD

Os autores propõem o SVAkADD (Aproximação do Valor de Shapley sob k-aditividade), um método inovador que aproxima os valores de Shapley ajustando um jogo substituto k-aditivo estruturado a um subconjunto amostrado de valores de coalizão.

Conceito Central: k-Aditividade

Em vez de estimar o valor de Shapley diretamente via amostragem Monte Carlo de contribuições marginais, o SVAkADD assume que o jogo subjacente pode ser aproximado por um jogo k-aditivo. Em tal jogo, os índices de interação (interações de Shapley) para coalizões maiores que o tamanho $k$ são assumidos como zero.

• Representação: A função de valor $\nu_k$ do jogo substituto é expressa como uma transformação linear dos índices de interação de Shapley $I(B)$ para todas as coalizões $B$ onde $|B| \leq k$.
• Redução de Parâmetros: Essa suposição reduz drasticamente o número de parâmetros necessários para definir o jogo de $2^n$ para um número polinomial (por exemplo, $O(n^k)$), tornando a otimização tratável.

Framework de Otimização

O método formula a aproximação como um problema de mínimos quadrados ponderados com restrições:

1. Objetivo: Minimizar o erro quadrático ponderado entre os valores de coalizão observados $\nu(A)$ do jogo original e os valores previstos pelo substituto k-aditivo $\nu_k(A)$.
2. Restrições: A otimização impõe o axioma de eficiência, garantindo que a soma dos valores de Shapley do substituto seja igual à diferença entre o valor da coalizão grande e o valor do conjunto vazio ($\nu(N) - \nu(\emptyset)$).
3. Ponderação: Os autores derivam analiticamente pesos específicos $w^*_A = \binom{n-2}{|A|-1}^{-1}$ para o problema de mínimos quadrados. Eles provam que, se todas as coalizões fossem observadas, resolver essa otimização específica produz os valores de Shapley exatos, independentemente de o jogo original ser verdadeiramente k-aditivo.

Algoritmo

O algoritmo SVAkADD procede da seguinte forma:

1. Amostragem: Avalia deterministicamente o conjunto vazio $\emptyset$ e a coalizão grande $N$. Em seguida, amostra $T-2$ coalizões adicionais do conjunto das partes (excluindo $\emptyset$ e $N$) com base em uma distribuição de probabilidade proporcional aos pesos derivados $w^*_A$.
2. Ajuste: Resolve o problema de mínimos quadrados ponderados com restrições usando os dados amostrados para estimar os índices de interação $I(B)$ para $|B| \leq k$.
3. Extração: Os valores de Shapley para o jogo substituto são obtidos imediatamente como os índices de interação de singleton ($I(\{i\})$), que servem como estimativas para o jogo original.

Contribuições Principais

1. Método de Aproximação Inovador: Introdução do SVAkADD, que ajusta um jogo substituto k-aditivo a dados amostrados, oferecendo uma alternativa estruturada à amostragem direta de contribuições marginais.
2. Fundamentação Teórica: Prova analítica de que, para $k=1, 2, 3$, a otimização de mínimos quadrados ponderados proposta produz os valores de Shapley exatos quando o conjunto completo de coalizões é observado. Isso estabelece que a k-aditividade é uma ferramenta para aproximação e não uma suposição restritiva sobre a estrutura do jogo.
3. Agnosticismo de Modelo e Domínio: O método não requer propriedades estruturais específicas da função de valor, tornando-o aplicável a qualquer jogo cooperativo, incluindo explicações de recursos locais e globais em aprendizado de máquina.
4. Avaliação Empírica: Comparação abrangente contra baselines de última geração (KernelSHAP, SVARM Estratificado, Amostragem Estratificada) em diversos conjuntos de dados e tipos de explicação (global, local, não supervisionado).

Resultados Experimentais

Os autores avaliaram o SVAkADD em conjuntos de dados variando de 9 a 14 recursos em tarefas globais, locais e não supervisionadas.

• Convergência: O método demonstra desempenho competitivo. Embora possa exibir erro mais alto em orçamentos de amostra muito baixos em comparação com algumas baselines, ele converge mais rapidamente para os valores de Shapley exatos à medida que o orçamento aumenta, particularmente para tarefas de atribuição local nos conjuntos de dados Adult e ImageNet.
• Escolha de $k$: Os experimentos destacam um compromisso entre flexibilidade e velocidade de convergência.
  • $k$ baixo (1 ou 2) frequentemente converge lentamente devido à flexibilidade insuficiente para modelar interações complexas de recursos.
  • $k$ mais alto (3 ou 4) geralmente converge significativamente mais rápido e supera modelos de ordem inferior após algumas amostras.
  • Os autores sugerem $k=3$ como padrão preferível, oferecendo um bom equilíbrio entre redução de erro e o número de parâmetros necessários.
• Comparação: O SVAkADD consistentemente compete ou supera o KernelSHAP e o SVARM Estratificado, particularmente em cenários que exigem alta precisão com orçamentos de amostra moderados.

Significado e Alegações

O artigo afirma que o SVAkADD fornece uma abordagem fundamentada teoricamente e praticamente eficaz para a aproximação do valor de Shapley. Ao aproveitar a estrutura dos jogos k-aditivos, o método transforma o problema de estimação em uma otimização de tempo polinomial que garante recuperação exata sob condições de ponderação específicas.

Os autores enfatizam que sua abordagem é agnóstica ao modelo e independente do domínio, capaz de lidar com qualquer formulação de jogo cooperativo. Eles concluem que, embora nenhum método de aproximação único domine em todos os cenários (dependendo do conjunto de dados, tarefa e orçamento), o SVAkADD oferece uma alternativa robusta que aproveita as propriedades teóricas das interações de Shapley para alcançar alta precisão. O artigo também observa que o método fornece naturalmente estimativas para efeitos de interação (redundância ou complementaridade) quando $k \geq 2$, oferecendo interpretabilidade adicional além da importância individual dos recursos.