Resumo Técnico: Um Estimador Ímpar para Valores de Shapley

Declaração do Problema

O valor de Shapley é o framework padrão para atribuição em aprendizado de máquina, utilizado para importância de características, avaliação de dados e inferência causal. No entanto, sua computação exata é geralmente intratável devido ao número exponencial de coalizões ($2^d$) necessárias para a avaliação. Embora existam métodos de aproximação, os estimadores mais eficazes frequentemente dependem de "amostragem pareada" (amostrar uma coalizão $S$ e seu complemento $S^c$), um heurístico que melhora empiricamente a precisão, mas carece de uma justificativa teórica rigorosa sobre o porquê de funcionar, particularmente em relação a interações de ordem superior. Além além disso, os métodos existentes de regressão polinomial de ordem superior (ex: PolySHAP) enfrentam um gargalo de escalabilidade onde o custo computacional cresce quadraticamente com o tamanho da base polinomial, limitando sua aplicação em cenários de alta dimensionalidade.

Metodologia

Os autores propõem o OddSHAP, um novo estimador que aproveita uma propriedade estrutural fundamental do valor de Shapley: ele depende exclusivamente do componente ímpar da função de valor $f$.

Fundamentação Teórica

1. Decomposição Ímpar-Par: Qualquer função de conjunto $f$ pode ser decomposta unicamente em um componente ímpar ($f_{odd}$) e um componente par ($f_{even}$), onde $f_{odd}(S) = -f_{odd}(S^c)$ e $f_{even}(S) = f_{even}(S^c)$.
2. Propriedade do Valor de Shapley: Os autores provam que $\phi_i(f) = \phi_i(f_{odd})$ para todos os jogadores $i$. O componente par contribui com zero para o valor de Shapley.
3. Mecanismo de Amostragem Pareada: O artigo fornece a primeira justificativa teórica geral para a amostragem pareada. Ao amostrar pares $(S, S^c)$ com pesos simétricos, o problema de regressão de mínimos quadrados ponderados ortogonaliza (desacopla) em problemas de otimização independentes para os componentes ímpares e pares. Como o componente par é irrelevante, a amostragem pareada efetivamente isola o sinal necessário para os valores de Shapley. Isso resolve uma conjectura de que a amostragem pareada com um ajuste de ordem-$k$ (para $k$ ímpar) é equivalente a um ajuste de ordem-$(k+1)$.

Design do Algoritmo: OddSHAP

Para explorar essa percepção evitando a explosão combinatória de ajustar todos os termos de ordem superior, o OddSHAP opera na base de Fourier em vez da base de unanimidade.

• Vantagem da Base de Fourier: Na base de Fourier, uma função de base $\chi_T$ é ímpar se, e somente se, a cardinalidade $|T|$ é ímpar. Isso permite uma separação limpa entre termos ímpares e pares, ao contrário da base de unanimidade.
• Processo de Duas Etapas:
  1. Triagem de Interação (Interaction Screening): Um modelo de proxy baseado em Árvores de Boosting de Gradiente (GBT) é ajustado às coalizões amostradas. Usando um método como o ProxySPEX, o algoritmo extrai um conjunto esparso de coeficientes de Fourier de ordem ímpar de alto impacto. Isso evita a necessidade de ajustar todas as interações possíveis.
  2. Regressão Ímpar: Uma regressão de mínimos quadrados ponderados é realizada estritamente nos termos de base de Fourier de ordem ímpar selecionados (mais termos lineares), restrita para corresponder à função de valor nos conjuntos vazio e total.
• Eficiência: Ao restringir a regressão ao subespaço ímpar e usar um proxy para selecionar os termos, o método alcança complexidade de tempo polinomial relativa ao orçamento de amostragem, contornando a escala $O(d^k)$ dos métodos de ordem fixa.

Principais Contribuições

1. Unificação Teórica da Amostragem Pareada: O artigo prova que a amostragem pareada desacopla implicitamente o objetivo de regressão em componentes ímpares e pares, fornecendo uma explicação rigorosa para o seu sucesso empírico e generalizando descobertas anteriores limitadas a interações de baixa ordem.
2. O Estimador OddSHAP: Um estimador consistente que realiza regressão polinomial apenas em uma seleção esparsa de funções de base de Fourier de ordem ímpar. Ele filtra componentes pares irrelevantes e identifica interações de alto impacto via um modelo de proxy.
3. Desempenho de Estado da Arte: Benchmarks extensivos demonstram que o OddSHAP alcança uma precisão de estimativa superior aos métodos existentes (incluindo RegressionMSR, LeverageSHAP e PolySHAP) sob orçamentos de amostragem maiores, particularmente em cenários de alta dimensionalidade.

Resultados Experimentais

Os autores avaliaram o OddSHAP em oito funções de valor variando de $d=14$ (DistilBERT) a $d=101$ (dataset Crime), cobrindo domínios de aprendizado profundo (imagem e texto) e tabulares.

• Precisão: O OddSHAP consistentemente alcançou o menor Erro Quadrático Médio (MSE) e o melhor ranking médio entre os benchmarks, particularmente quando o orçamento de amostragem $m$ era suficiente para detectar interações ($m > \eta \cdot d$).
• Comparação com FFD: O OddSHAP superou o Design Fatorial Fracionário de Orçamento Fixo (FFD-RD) em arquiteturas de aprendizado profundo (ViT, DistilBERT), onde interações de ordem superior são significativas. Por outro lado, o FFD-RD teve um desempenho ligeiramente superior em datasets tabulares baseados em árvores, onde as interações de ordem superior decaem rapidamente, validando os trade-offs específicos de domínio.
• Estudos de Ablação:
  • Pareado vs. Não-Pareado: A amostragem pareada superou consistentemente a amostragem não-pareada.
  • Ímpar vs. Todas as Interações: Sob amostragem pareada, incluir interações pares não trouxe benefícios e degradou levemente o desempenho ao consumir o orçamento de interação com termos que se cancelam matematicamente.
  • Esparsidade: Incorporar um número moderado de interações ímpares (controlado pelo fator de variável de regressão $\eta$) reduziu significativamente o erro em comparação com baselines lineares, embora tenha ocorrido overfitting com excesso de interações.

Significância e Alegações

O artigo afirma que o OddSHAP oferece um framework de orçamento flexível que se adapta robustamente através de diversas estruturas de interação. Sua principal significância reside em:

1. Resolução de uma Conjectura Aberta: Fornece o mecanismo teórico fundamental que explica por que a amostragem pareada funciona, indo além da observação empírica para a prova estrutural.
2. Escalabilidade: Mantém o poder expressivo de aproximações de ordem superior sem incorrer em seus custos combinatórios proibitivos, ao restringir o modelo ao subespaço ímpar.
3. Robustez: Diferente de métodos que dependem de suposições de truncamento rígidas (como FFD), o OddSHAP permanece eficaz em domínios complexos de aprendizado profundo onde interações de ordem alta não são desprezíveis, mantendo simultaneamente a competitividade em domínios tabulares esparsos.

Os autores observam limitações, especificamente que o tempo de execução do algoritmo escala cubicamente com o orçamento devido ao custo de regressão quadrática nas interações selecionadas, e que a amostragem pareada reduz o número efetivo de amostras independentes, o que pode inflar a variância. No entanto, eles concluem que o método representa uma abordagem de estado da arte para a estimativa do valor de Shapley em configurações agnósticas ao modelo.