Resumo Técnico: ShaplEIG

Declaração do Problema

Os valores de Shapley (SVs) servem como uma medida de atribuição fundamentada na aprendizagem automática interpretável, contudo, sua computação exata é frequentemente intratável. O fardo computacional surge de dois fatores: o crescimento exponencial das coalizões ($2^p$) com o número de jogadores $p$, e o alto custo de avaliar a função de valor $\nu$ para cada coalizão. Em aplicações como importância de características baseada em retreinamento, valoração de dados e importância de hiperparâmetros, as avaliações da função de valor podem envolver o retreinamento completo do modelo ou inferência dispendiosa, limitando severamente o orçamento de avaliação.

Métodos de aproximação existentes, incluindo amostragem de Monte Carlo e abordagens baseadas em substitutos (ex: Kernel SHAP, Regressão MSR), tipicamente dependem de distribuições de amostragem fixas e não adaptativas. Isso levanta a questão de se a precisão da aproximação pode ser melhorada selecionando coalizões para avaliação de forma adaptativa com base em observações anteriores, particularmente em regimes de baixo orçamento. Embora o Design Experimental Bayesiano (BED) ofereça um framework para design sequencial usando o Ganho de Informação Esperada (EIG), sua adoção na estimativa de SV tem sido limitada devido à falta de expressões de EIG em forma fechada e à intratabilidade computacional de estimar o EIG para espaços discretos de alta dimensão.

Metodologia

Os autores propõem o ShaplEIG, uma abordagem de design experimental bayesiano que seleciona coalizões de forma adaptativa para maximizar o ganho de informação em relação aos valores de Shapley.

1. Processo Gaussiano Substituto com Kernel de Hamming

O ShaplEIG modela a função de valor $\nu$ usando um substituto de Processo Gaussiano (GP). Para lidar com o espaço de entrada binário das coalizões (representado como vetores indicadores $z \in \{0, 1\}^p$), o método emprega um kernel de distância de Hamming. Este kernel quantifica a similaridade entre coalizões baseada em distâncias de Hamming ponderadas, com hiperparâmetros de escala de comprimento $\xi$ aprendíveis. O GP fornece uma distribuição posterior sobre a função de valor em todas as $2^p$ coalizões dado um conjunto de dados $D_t$ de avaliações observadas.

2. Estimativa de SV Consistente via Linearidade

Um insight teórico fundamental é a linearidade dos valores de Shapley em relação à função de valor. Os SVs $\phi$ podem ser expressos como uma transformação linear do vetor da função de valor: $\phi = A\nu$, onde $A$ é uma matriz conhecida derivada da fórmula de Shapley. Consequentemente, sob o substituto GP, a distribuição posterior sobre os SVs também é Gaussiana e disponível em forma fechada:
$$\phi | D_t \sim \mathcal{N}_p(A\mu_{\nu|D_t}, A\Sigma_{\nu|D_t}A^\top)$$
Os autores extraem as estimativas de SV a partir da média posterior, $\hat{\phi} = A\mu_{\nu|D_t}$. Crucialmente, para GPs sem ruído (ou quase sem ruído), este estimador é consistente: se todas as $2^p$ coalizões forem avaliadas, as estimativas convergem exatamente para os verdadeiros valores de Shapley.

3. EIG de Forma Fechada

A principal contribuição é derivar uma expressão de forma fechada para o EIG de uma coalizão candidata $z^{(i)}$ em relação aos SVs. Ao enquadrar a seleção sequencial como um problema inverso linear bayesiano onde os SVs são um objetivo linear final, mostra-se que o EIG depende apenas da covariância posterior dos SVs:
$$\text{EIG}^{(t)}_{\phi}(z^{(i)}) \propto -\log \det \left( A \Sigma_{\nu|\nu'(z^{(i)}), D_t} A^\top \right) + C$$
Isso evita as expectativas aninhadas tipicamente exigidas em BED, pois o EIG depende exclusivamente do design experimental (a coalizão selecionada) e não do resultado específico $y(x)$.

4. Computação Eficiente via Polinômios Simétricos Elementares

A computação direta do EIG envolve operações em matrizes de tamanho $2^p \times 2^p$, levando à complexidade exponencial. Os autores propõem um esquema de computação eficiente que reduz a complexidade para tempo polinomial ($O(p^4 + t^3)$) ao explorar a estrutura multiplicativa do kernel de Hamming.

• Os termos necessários para o EIG (especificamente $A\Sigma_{\nu|D_t}e_i$ e $A\Sigma_{\nu|D_t}A^\top$) são reescritos como somas ponderadas de avaliações de kernel.
• Estas somas são identificadas com polinômios simétricos elementares (ESPs) escalonados.
• Ao computar estes polinômios de forma eficiente (usando programação dinâmica e tabelas de prefixo/sufixo), o método evita a enumeração explícita de todas as coalizões.

5. Algoritmo

O algoritmo procede de forma gananciosa (greedy):

1. Inicializa com um design pequeno (ex: amostragem de leverage score).
2. Ajusta o substituto GP e otimiza os hiperparâmetros.
3. Computa o EIG para todas as coalizões candidatas usando o esquema polinomial eficiente.
4. Seleciona a coalizão com o máximo EIG, avalia a função de valor e atualiza o conjunto de dados.
5. Repete até que o orçamento seja esgotado.

Principais Contribuições

1. Framework ShaplEIG: Introdução de um novo método baseado em BED para estimativa de SV que utiliza um substituto GP com kernel de Hamming e seleciona coalizões adaptativamente com base no EIG.
2. EIG de Forma Fechada: Demonstração de que o EIG para valores de Shapley admite uma expressão de forma fechada sob um substituto GP, aproveitando a linearidade dos SV na função de valor.
3. Complexidade Polinomial: Proposta de um esquema de computação eficiente para o EIG que reduz a complexidade de exponencial para polinomial no número de jogadores ($p$) via polinômios simétricos elementares.
4. Estimativa Consistente: Provisão de um estimador de SV consistente que converge para os valores exatos quando todas as coalizões são avaliadas, contrastando com alguns métodos de substitutos baseados em árvores que requerem etapas de ajuste adicionais.

Resultados Experimentais

Os autores avaliam o ShaplEIG através de diversas aplicações dispendiosas envolvendo jogos pequenos a moderadamente grandes ($8 \le p \le 101$):

• Tarefas: Importância global de características (TabPFN), valoração de dados (Random Forest, Gradient Boosting), importância de hiperparâmetros (XGBoost, LCBench) e explicações locais (ResNet, ViT, Random Forest).
• Baselines: Comparação contra Kernel SHAP, Leverage SHAP, Amostragem de Permutação e o estado da arte Regressão MSR (acoplado com XGBoost).
• Ablações: Comparação contra variantes que utilizam o mesmo substituto GP, mas diferentes estratégias de seleção (Aleatória, Amostragem de Incerteza, Amostragem de Leverage Score).

Descobertas:

• Eficiência de Amostra: O ShaplEIG alcança consistentemente a melhor precisão geral (menor Erro Quadrático Médio) no regime de baixo orçamento na maioria das tarefas. Ele frequentemente domina estritamente os concorrentes, particularmente em jogos assimétricos onde as interações entre jogadores não são uniformes.
• Insights de Ablação: O forte desempenho é atribuído primariamente à estratégia de seleção baseada em EIG, e não apenas ao uso de um substituto GP. A Amostragem de Incerteza (US) frequentemente performou pior do que a amostragem aleatória, destacando que maximizar a variância marginal não equivale a maximizar a informação sobre os SVs linearmente transformados.
• Escalabilidade: Para jogos maiores ($p > 16$), o método permanece eficaz mesmo quando o ajuste de hiperparâmetros é realizado em um cronograma, em vez de a cada iteração.
• Custo Computacional: Embora a computação do EIG seja eficiente (segundos), o ajuste de hiperparâmetros pode tornar-se um gargalo para $p$ grande (até 25 minutos por iteração para $p \approx 100$). Os autores observam que o ShaplEIG é mais apropriado quando as avaliações da função de valor são genuinamente caras, justificando o overhead.

Significância e Alegações

O artigo afirma que o ShaplEIG fornece um framework principiado para melhorar a eficiência de amostragem na estimativa de SV para jogos custosos. Ao derivar um EIG de forma fechada e um esquema de computação eficiente de tempo polinomial, os autores superam as principais barreiras para a aplicação de Design Experimental Bayesiano neste domínio.

Os autores afirmam modestamente que, embora o método incorra em overhead computacional devido à otimização repetida do GP, ele oferece ganhos substanciais na precisão da estimativa quando os orçamentos de avaliação são limitados. Eles reconhecem que para jogos muito grandes ou funções de valor menos custosas, o overhead pode ser proibitivo, sugerindo trabalhos futuros focados em melhorias computacionais adicionais para ampliar a aplicabilidade do método. O trabalho não pretende resolver a estimativa de SV para todos os cenários, mas visa especificamente o regime de funções de valor caras onde a seleção adaptativa é crítica.