Resumo Técnico: PolySHAP – Estendendo o KernelSHAP com Regressão Polinomial Informada por Interações

Declaração do Problema

Os valores de Shapley são uma ferramenta central da teoria dos jogos em IA Explicável (XAI) para atribuir a previsão de um modelo às suas características de entrada. No entanto, calcular os valores de Shapley exatamente exige avaliar o modelo em todos os $2^d$ subconjuntos possíveis de características, o que é computacionalmente inviável para modelos com um grande número de características $d$.

O KernelSHAP (Lundberg & Lee, 2017) surgiu como um método líder para aproximar os valores de Shapley de forma eficiente. Ele formula o problema como uma regressão de mínimos quadrados ponderados, aproximando o jogo cooperativo $\nu$ com uma função linear ajustada a uma amostra de subconjuntos aleatórios de características. Embora eficaz, essa aproximação linear assume inerentemente a aditividade das características, falhando em capturar interações não lineares entre elas. Consequentemente, o KernelSHAP pode produzir estimativas subótimas quando o jogo subjacente exibe interações de ordem superior significativas.

Metodologia: PolySHAP

Os autores propõem o PolySHAP, uma generalização do KernelSHAP que aproxima o jogo $\nu$ usando polinômios de grau superior em vez de uma função linear. Essa abordagem modela explicitamente interações não lineares entre características.

Mecanismo Central

1. Representação Informada por Interações: Em vez de ajustar um modelo linear $\sum \phi_i \mathbb{1}[i \in S]$, o PolySHAP ajusta um polinômio de grau $k$ sobre os indicadores binários de características $\mathbb{1}[i \in S]$. A aproximação inclui uma "fronteira de interação" $\mathcal{I}$, um subconjunto de termos de interação (subconjuntos de características com tamanho $\ge 2$).
   $$\hat{\nu}(S) \approx \sum_{T \in \mathcal{D} \cup \mathcal{I}} \phi_T \prod_{j \in T} \mathbb{1}[j \in S]$$
   onde $\mathcal{D}$ representa características individuais e $\mathcal{I}$ representa termos de interação.

2. Formulação de Regressão: O PolySHAP resolve um problema de mínimos quadrados ponderados semelhante ao KernelSHAP, mas com uma matriz de projeto expandida contendo colunas tanto para efeitos principais quanto para termos de interação selecionados. O objetivo minimiza a perda ponderada $\ell_2$ entre os valores do jogo amostrados $\nu(S_\ell)$ e a aproximação polinomial.

3. Extração dos Valores de Shapley: Um resultado teórico chave (Teorema 4.3) demonstra que os valores de Shapley do jogo original podem ser recuperados diretamente dos coeficientes da aproximação polinomial. Especificamente, o valor de Shapley para a característica $i$ é a soma do coeficiente para o efeito principal $\phi_i$ e dos coeficientes de todos os termos de interação que contêm $i$, divididos pelo tamanho desses conjuntos de interação:
   $$\phi_i^{SV} = \phi_i + \sum_{S \in \mathcal{I}: i \in S} \frac{\phi_S}{|S|}$$

4. Estratégias de Amostragem: O método suporta amostragem padrão e amostragem em pares (amostrando subconjuntos $S$ e seus complementos $D \setminus S$). Os autores utilizam amostragem por pontuação de alavancagem (leverage score) para melhorar a qualidade da estimativa, observando que, para interações de ordem superior, as pontuações de alavancagem de ordem 1 (uniformes sobre os tamanhos dos subconjuntos) funcionam bem na prática.

Contribuições Principais

1. Consistência Teórica e Extensão

O artigo prova que o PolySHAP fornece estimativas consistentes dos valores de Shapley. À medida que o número de amostras $m$ se aproxima do número total de subconjuntos $2^d$, as estimativas do PolySHAP convergem exatamente para os verdadeiros valores de Shapley (Teorema 4.3). Isso contrasta com alguns métodos de aproximação baseados em árvores (por exemplo, RegressionMSR) que exigem etapas adicionais de ajuste de regressão para alcançar consistência.

2. Equivalência Teórica entre Amostragem em Pares e 2-PolySHAP

Uma contribuição teórica majoritária é a prova de que o KernelSHAP com amostragem em pares é matematicamente equivalente ao 2-PolySHAP (Teorema 5.1).

• Quando os subconjuntos são amostrados em pares ($S$ e $D \setminus S$), a solução de regressão linear do KernelSHAP produz exatamente as mesmas aproximações de valores de Shapley que uma regressão polinomial de segunda ordem (2-PolySHAP).
• Essa descoberta fornece a primeira justificativa teórica forte para o sucesso empírico da amostragem em pares, explicando que ela captura implicitamente todas as interações de segunda ordem sem ajustar explicitamente um polinômio de grau 2.

3. Desempenho Empírico

Experimentos extensos em 15 jogos de explicação local (abrangendo domínios tabulares, de imagem e de linguagem) demonstram que:

• Precisão de ordem superior: Aumentar o grau do polinômio (por exemplo, 3-PolySHAP) melhora consistentemente a qualidade da aproximação (medida por MSE, Precision@5 e correlação de Spearman) em comparação com o KernelSHAP (1-PolySHAP) e a Amostragem por Permutação, desde que o orçamento de amostragem seja suficiente.
• Eficiência da Amostragem em Pares: Sob amostragem em pares, o KernelSHAP alcança desempenho comparável ao 2-PolySHAP, validando a equivalência teórica.
• Resultados state-of-the-art: Em configurações de dimensão baixa a moderada, o PolySHAP (especificamente o 3-PolySHAP) frequentemente supera outras bases, incluindo o RegressionMSR (que depende de aproximações XGBoost) e o SVARM.

Significado e Alegações

O artigo alega oferecer uma extensão principiada do amplamente utilizado framework KernelSHAP. Ao migrar de aproximações lineares para polinomiais, o PolySHAP aborda a limitação de ignorar interações entre características, levando a explicações mais precisas para modelos complexos.

Crucialmente, o trabalho preenche uma lacuna entre práticas heurísticas e teoria. Ao provar que a heurística popular de "amostragem em pares" é equivalente à modelagem de interações de segunda ordem, os autores fornecem uma base rigorosa para entender por que essa estratégia de amostragem funciona tão bem na prática. Os autores observam modestamente que, embora interações de ordem superior melhorem a precisão, elas exigem orçamentos de amostragem maiores e, em configurações de dimensão muito alta ($d \ge 60$), os ganhos são mais modestos devido à explosão combinatória dos termos de interação.

O artigo conclui que o PolySHAP é um método robusto, consistente e empiricamente superior para estimativa de valores de Shapley, particularmente quando o jogo subjacente envolve interações não lineares entre características.