Resumo Técnico: QuadraSHAP

Declaração do Problema

Os valores de Shapley são uma ferramenta fundamental para explicar previsões de aprendizado de máquina, oferecendo atribuições de características fundamentadas na teoria dos jogos cooperativa. No entanto, o cálculo exato é geralmente intratável, exigindo a avaliação de exponencialmente muitas coalizões de características ($2^{d-1}$). Embora métodos específicos do modelo (por exemplo, TreeSHAP, RKHS-SHAP) explorem propriedades estruturais para alcançar tempo polinomial, eles frequentemente enfrentam um trade-off persistente entre estabilidade numérica e eficiência computacional.

Especificamente, métodos que dependem de interpolação polinomial (como Linear TreeSHAP) sofrem de instabilidade numérica rápida à medida que o grau do polinômio aumenta (governado pela profundidade da árvore ou pela contagem de características) devido ao mau condicionamento das inversas de Vandermonde. Por outro lado, métodos de recursão algébrica (por exemplo, para modelos de kernel de produto) oferecem estabilidade, mas incorrem em custos aritméticos substancialmente mais altos. Este artigo aborda a necessidade de um método que seja simultaneamente exato (ou quase exato), numericamente estável e computacionalmente eficiente para uma ampla classe de modelos que exibem estrutura multiplicativa.

Metodologia

O artigo introduz o QuadraSHAP, um método para calcular valores de Shapley para jogos de produto — jogos cooperativos onde o valor da coalizão fatora como um produto de termos por jogador ($v(S) = \prod_{j \in S} u_j$). Essa estrutura surge naturalmente em modelos baseados em árvores e métodos de kernel com kernels de produto.

1. Representação Integral

A contribuição teórica central é reformular o valor de Shapley de um jogo de produto de uma soma ponderada sobre $2^{d-1}$ subconjuntos para uma integral unidimensional exata. Ao utilizar a representação da função Beta dos pesos de Shapley, os autores derivam:
$$\phi_i(v) = (u_i - 1) \int_0^1 \prod_{j \neq i} \left( (1-t) + t u_j \right) dt$$
Essa transformação elimina a necessidade de enumeração de subconjuntos ou recuperação de coeficientes baseada em interpolação.

2. Quadratura de Gauss–Legendre

A integral é avaliada usando quadratura de Gauss–Legendre.

• Exatidão: Se o número de nós de quadratura $m_q$ satisfaz $m_q \ge \lceil d/2 \rceil$, o método recupera o valor exato de Shapley.
• Aproximação: Se $m_q < \lceil d/2 \rceil$, o método fornece uma aproximação quase exata. O erro é provado decair geometricamente em relação a $m_q$, especificamente limitado por $O(\rho^{-2m_q})$ para um parâmetro de elipse de Bernstein $\rho > 1$. Empiricamente, algumas centenas de nós são suficientes para estimativas de alta precisão, mesmo com milhares de características, muito abaixo do limiar de exatidão teórica.

3. Implementação Numericamente Estável e Eficiente

Para abordar desafios computacionais práticos, os autores propõem otimizações algorítmicas específicas:

• Avaliação em Espaço Logarítmico: Para evitar overflow e underflow em altas dimensões, os produtos são avaliados no espaço logarítmico com rastreamento explícito de sinais. O estimador é calculado como:
  $$\hat{\phi}_i(v) = (u_i - 1) \sum_{q=1}^{m_q} \omega_q \cdot \text{sgn}(P_q)\text{sgn}(T_{q,i}) \exp\left( \log|P_q| - \log|T_{q,i}| \right)$$
  onde $P_q$ é o produto completo dos termos e $T_{q,i}$ é o termo para a característica $i$.
• Cálculo Compartilhado: Em vez de recompute o produto "leave-one-out" para cada característica, o produto completo é computado uma vez, e o fator específico para a característica $i$ é dividido. Isso reduz a complexidade de $O(d^2 m_q)$ para $O(d m_q)$.
• Paralelização: O cálculo utiliza primitivas de varredura associativa (somas de prefixo) para computar as reduções no espaço logarítmico em tempo paralelo de $O(\log d)$.

Contribuições Principais

1. Formulação Integral Exata: O artigo estabelece que os valores de Shapley para jogos de produto admitem uma representação integral exata, permitindo o uso da quadratura de Gauss–Legendre.
2. Estabilidade e Eficiência: O QuadraSHAP resolve o trade-off estabilidade-eficiência. Ele evita a instabilidade numérica de métodos baseados em interpolação (como Linear TreeSHAP) enquanto é significativamente mais rápido que métodos de recursão algébrica para modelos de kernel de produto.
3. Garantias Teóricas: O método fornece exatidão provável para $m_q \ge \lceil d/2 \rceil$ e limites de convergência geométrica para regimes aproximados.
4. Algoritmos Escaláveis: Os autores derivam algoritmos com trabalho sequencial de $O(d m_q)$ e tempo paralelo de $O(\log d)$, tornando o método escalável para problemas de alta dimensão (milhares de características).

Resultados Experimentais

Os autores avaliam o QuadraSHAP contra baselines de última geração (TreeSHAP, Linear TreeSHAP, FastTreeSHAP, shapiq e PKeX-Shapley) em conjuntos de dados sintéticos e do mundo real.

• Ensembles de Árvores:
  • Velocidade: O QuadraSHAP é o método numericamente estável mais rápido em todas as configurações testadas. Em grandes ensembles ($10^5$ folhas), ele supera o TreeSHAP em 3–5$\times$ e o FastTreeSHAP em 2–2.7$\times$.
  • Estabilidade: Em regimes de árvores profundas (profundidade até 100), concorrentes como Linear TreeSHAP e TreeSHAP exibem violações catastróficas do axioma de eficiência de Shapley (erros atingindo $10^{186}$ ou superiores). O QuadraSHAP mantém precisão no nível dos limites de ponto flutuante ($\sim 10^{-13}$).
• Métodos de Kernel de Produto:
  • Escalabilidade: Para Regressão de Ridge com kernels de produto, o QuadraSHAP é uma ordem de magnitude mais rápido que a baseline exata atual (PKeX-Shapley).
  • Altas Dimensões: Enquanto o PKeX-Shapley excede o tempo limite (limite de 300s) para dimensões de características $d \ge 2000$, o QuadraSHAP completa explicações em segundos (por exemplo, 7,6s para $d=5000$).
• Qualidade da Aproximação: Experimentos confirmam que o erro de aproximação decai geometricamente com o número de nós $m_q$. Para $d=5000$, usando apenas 400 nós (bem abaixo do limiar de exatidão de 2500) produz precisão próxima à de máquina.

Significado e Alegações

O artigo alega que o QuadraSHAP fornece um framework unificado e robusto para atribuição de características em modelos com estruturas multiplicativas. Ao aproveitar a representação integral e a quadratura de Gauss–Legendre, ele alcança:

• Robustez Numérica: Mantém-se estável em configurações de alta dimensão e árvores profundas onde métodos baseados em interpolação falham.
• Superioridade Computacional: Igual ou supera a velocidade dos métodos existentes mais rápidos, mantendo exatidão ou aproximação controlada.
• Generalidade: A formulação unifica ensembles de árvores e métodos de kernel de produto sob um único paradigma computacional.

Os autores posicionam o QuadraSHAP como o método numericamente estável mais rápido para essas classes específicas de modelos, oferecendo uma solução prática para explicabilidade em sistemas complexos de aprendizado de máquina de alta dimensão.