Proxy-Based Approximation of Shapley and Banzhaf Interactions

Resumo Técnico: Aproximação Baseada em Proxy de Interações de Shapley e Banzhaf

Declaração do Problema
Aplicações modernas de aprendizado de máquina dependem cada vez mais da teoria dos jogos cooperativos para interpretar o comportamento de modelos, utilizando especificamente valores de Shapley e Banzhaf para atribuir contribuições a características individuais. No entanto, entender dinâmicas complexas e não lineares frequentemente requer a análise de interações de ordem superior (subconjuntos de características) em vez de apenas efeitos de singleton. O cálculo exato de índices de interação cardinal-probabilísticos é computacionalmente intratável para grandes números de características ($n$) devido ao crescimento exponencial do espaço de coalizões ($2^n$).

Os estimadores existentes enfrentam um compromisso crítico entre velocidade e precisão:

• Métodos baseados em amostragem (por exemplo, SHAP-IQ, KernelSHAP-IQ) são frequentemente precisos, mas exigem orçamentos de amostra impraticáveis para ajustar o vasto número de termos de ordem superior, sofrendo de alta variância que escala mal com a ordem da interação.
• Métodos baseados em proxy (por exemplo, ProxySPEX) oferecem velocidade, mas dependem de extração baseada em Fourier a partir de surrogatos de árvores. Essa abordagem sofre de complexidade exponencial relativa à profundidade da árvore e frequentemente requer truncamento agressivo que compromete a precisão. Além disso, os métodos de proxy existentes tipicamente retornam interações do proxy em vez da função de valor subjacente, introduzindo viés.

Metodologia: ProxySHAP
Os autores propõem o ProxySHAP, um framework que reconcilia a eficiência de amostragem de modelos proxy baseados em árvores com um caminho principiado para consistência via correção de resíduo. O método decompõe o índice de interação alvo $\phi^p_S(\nu)$ em dois componentes:
$$\phi^p_S(\nu) = \underbrace{\phi^p_S(\hat{\nu}_T)}_{\text{Proxy Exato}} + \underbrace{\phi^p_S(\nu - \hat{\nu}_T)}_{\text{Resíduo}}$$

1. Ajuste do Proxy (Fase 1): Um modelo baseado em árvores (por exemplo, XGBoost, LightGBM) ou um modelo linear com características de interação é treinado em coalizões amostradas para aproximar a função de valor subjacente $\nu$.
2. Extração Exata do Proxy (Fase 2): Diferentemente de métodos anteriores que extraem coeficientes de Fourier, o ProxySHAP introduz uma generalização de tempo polinomial do TreeSHAP intervencional. Isso permite o cálculo exato de qualquer índice de interação cardinal-probabilístico (incluindo Shapley e Banzhaf) diretamente da estrutura da árvore.
   • O método aproveita a representação de Möbius de jogos de indicador definidos pelas folhas da árvore.
   • Evita a complexidade exponencial $O(4^d)$ da extração baseada em Fourier (onde $d$ é a profundidade da árvore), alcançando tempo de execução $O(n_{nodes})$ por interação.
3. Ajuste de Resíduo: Para corrigir o viés introduzido pelo proxy não corresponder perfeitamente a $\nu$, o método estima as interações do jogo residual $(\nu - \hat{\nu}_T)$ usando Reutilização Máxima de Amostra (MSR).
   • O artigo fornece uma análise teórica mostrando que a variância do estimador MSR para interações de ordem $k$ escala como $O(n^{k-1}/|T|)$.
   • Consequentemente, os autores derivam condições sob as quais o ajuste MSR é benéfico: principalmente para configurações de baixa dimensionalidade ($n < 30$) ou quando o orçamento de amostragem $|T|$ é suficientemente grande em relação a $n^{k-1}$. Para interações de ordem superior em jogos grandes, a variância da correção pode superar a redução de viés.

Contribuições Principais

1. Framework ProxySHAP: Uma estratégia de estimação inovadora que combina um proxy baseado em árvores com correção de resíduo, permitindo aproximação eficiente e precisa de interações de ordem superior.
2. Avanço Teórico:
   • Derivação de um algoritmo de tempo polinomial em forma fechada para extrair índices exatos de interação cardinal-probabilístico de ensembles de árvores, contornando a dependência exponencial da profundidade de métodos anteriores baseados em Fourier.
   • Caracterização formal do crescimento da variância do MSR para interações de ordem superior, estabelecendo condições explícitas (em termos de $n$, orçamento e ordem de interação $k$) sob as quais o ajuste de resíduo melhora ou degrada o desempenho.
3. Desempenho Empírico: Benchmarking extensivo em 47 conjuntos de dados (tabulares, visão, linguagem, grafos e visão-linguagem) demonstra que o ProxySHAP estabelece um novo padrão de última geração. Alcança o menor erro tanto em regimes de orçamento pequeno (onde supera o ProxySPEX) quanto em regimes de orçamento grande (onde supera o KernelSHAP-IQ).

Resultados

• Precisão: O ProxySHAP supera consistentemente as linhas de base (KernelSHAP-IQ, ProxySPEX, SHAP-IQ) em termos de Erro Quadrático Médio Relativo (MSE). Em aplicações em grande escala com milhares de características (por exemplo, Bioresponse com $n=1776$), o ProxySHAP permanece eficaz onde outros métodos se tornam computacionalmente inviáveis ou imprecisos.
• Eficiência: O algoritmo de extração de tempo polinomial fornece acelerações de ordens de magnitude (10x a 1000x) em comparação com a extração baseada em Fourier, particularmente à medida que a profundidade da árvore aumenta.
• Tarefas a Jusante: Em uma aplicação específica para explicar o modelo de visão-linguagem SigLIP-2 (jogo FIxLIP), o ProxySHAP demonstrou fidelidade superior (medida pela Área sob a curva de Inserção-Deleção) em comparação com linhas de base de regressão linear e ProxySPEX.
• Sensibilidade a Hiperparâmetros: O estudo destaca que a qualidade do proxy é crítica. A otimização de hiperparâmetros (HPO) melhora significativamente o desempenho, e uma configuração padrão "informada por HPO" (usando muitas árvores rasas) é proposta para equilibrar custo e precisão.

Significado e Alegações
O artigo alega que o ProxySHAP resolve o compromisso de longa data entre velocidade e precisão na estimação de interações. Ao fornecer um mecanismo de extração exata para proxies de árvores e uma estratégia teoricamente fundamentada para correção de resíduo, permite a quantificação escalável de dependências complexas em sistemas de IA modernos. Os autores enfatizam que seu método é particularmente valioso para:

• Aplicações em grande escala: Lidar com conjuntos de dados com milhares de características onde o cálculo exato é impossível.
• Interações de ordem superior: Fornecer estimativas confiáveis para interações além de efeitos pares, que são cruciais para entender dependências cruzadas de modalidades (por exemplo, em modelos de visão-linguagem) e sinergias complexas de características.
• Implantação prática: Oferecer um estimador de "última geração" que é robusto a restrições variáveis de orçamento e tipos de modelos, apoiado por uma implementação escalável em C++.

Os autores observam modestamente limitações, especificamente que a qualidade da aproximação depende do proxy ajustado (requerendo ajuste cuidadoso de hiperparâmetros) e que a variância da correção de resíduo limita sua utilidade em configurações de dimensão muito alta para interações de ordem superior. Sugere-se trabalho futuro para explorar classes alternativas de proxy e estimadores de resíduo que escalem de forma mais graciosa.