Resumo Técnico: Valores de Shapley e Interações Tratáveis via Redes de Tensores

Declaração do Problema

Explicar previsões de aprendizado de máquina via valores de Shapley e suas generalizações de ordem superior (Índices de Interação de Shapley, SII) é fundamental para o suporte à decisão e interpretabilidade. No entanto, computar esses índices é computacionalmente proibitivo para modelos com $n$ características, pois tradicionalmente exige a enumeração de $O(2^n)$ coalizões. As soluções existentes enfrentam trade-offs significativos:

• Suposições Estruturais: Métodos como TreeSHAP ou aqueles para Modelos Aditivos Generalizados (GAMs) são exatos apenas para arquiteturas específicas (ex: árvores, modelos lineares).
• Aproximações Baseadas em Amostragem: Abordagens como KernelSHAP ou SHAP-IQ dependem de amostragem pesada, exigindo um ajuste delicado de variância e frequentemente falhando em escalar para interações de ordem superior sem custos computacionais massivos.
• Estimativa Amortizada: Métodos que treinam modelos auxiliares frequentemente incorrem em um overhead de treinamento significativo e podem carecer de garantias teóricas sobre a fidelidade da explicação.

O desafio central é computar valores de Shapley e interações de forma exata (ou com erro controlado) para preditores gerais sem a enumeração exponencial ou amostragem excessiva.

Metodologia: TN-SHAP

Os autores propõem o TN-SHAP, um método que substitui a enumeração exaustiva de coalizões por um esquema de poucas avaliações em um surrogate de Rede de Tensores (TN). A abordagem aproveita três insights fundamentais para reduzir a complexidade de $O(2^n)$ para $O(n \cdot \text{poly}(\chi))$, onde $\chi$ é a dimensão de ligação máxima da rede de tensores.

1. Representação Multilinear e Extração de Coeficientes

O método assume que o preditor $f$ pode ser bem aproximado por uma função multilinear $g$ em um espaço de características elevado (lifted feature space). Em uma expansão multilinear, $f(x) = \sum_{T \subseteq N} c_T \prod_{j \in T} x_j$, os valores das coalizões correspondem a combinações lineares de coeficientes tensoriais. Crucialmente, os valores de Shapley dependem apenas de contribuições marginais agregadas por tamanho (somas de contribuições para coalizões de tamanho $s$), e não de membros de coalizões específicos.

2. Seletores Diagonais e Interpolação Polinomial

Em vez de consultar $2^n$ coalizões, o TN-SHAP utiliza matrizes de seletores diagonais $S_r(t) = \text{Diag}(t, 1)$ aplicadas a características elevadas $\tilde{x}_r = [\phi(x_r), 1]^\top$.

• Ao avaliar o surrogate $g$ em pontos onde as características são escalonadas por um parâmetro $t$, o método agrega todas as coalizões de tamanho $s$ no coeficiente de $t^s$ em um polinômio resultante $P(t)$.
• Especificamente, para uma característica alvo $i$, uma função de sonda $G_i(t)$ é construída para isolar a contribuição marginal de $i$ através de todos os subconjuntos de outras características.
• Isso transforma o problema combinatório em interpolação polinomial. Ao avaliar $G_i(t)$ em $n$ pontos distintos (ex: nós de Chebyshev-Gauss), o sistema resolve um sistema linear de Vandermonde para recuperar as contribuições marginais agregadas por tamanho $\{m_s^{(i)}\}$.
• O valor de Shapley é então computado como uma soma ponderada desses coeficientes recuperados.

3. Surrogates de Redes de Tensores

Para tornar a avaliação do mapa multilinear tratável em escala, o tensor de coeficientes é fatorizado em uma Rede de Tensores (TN) (ex: Tensor Train ou Árvore Hierárquica) com dimensão de ligação $\chi$.

• Mapas de Características: Para lidar com dados não lineares do mundo real, as características escalares são elevadas via mapas aprendidos ou manuais $\phi_i: \mathbb{R} \to \mathbb{R}^{d_i-1}$ antes de entrarem na TN. Isso preserva a multilinearidade no espaço elevado enquanto permite que o surrogate modele não-linearidades no espaço de entrada original.
• Eficiência: Cada passagem direta (forward pass) através da TN custa $O(\text{poly}(\chi))$. Como apenas $O(n)$ avaliações são necessárias para a interpolação, a complexidade total para computar interações de ordem-$k$ torna-se polinomial em $n$.

Principais Contribuições

1. Esquema Unificado de Sonda-Interpolação: Um algoritmo exato para computar valores de Shapley e interações de $k$-vias em um surrogate multilinear TN usando apenas $O(n)$ passagens diretas estruturadas, evitando $O(2^n)$ consultas.
2. Surrogates Aprimorados por Mapas de Características: Um framework demonstrando como elevações de características aprendidas preservam a multilinearidade necessária para o cálculo exato enquanto melhoram a fidelidade do surrogate para modelos não lineares.
3. Garantias Teóricas:
   • Exatidão: O método computa valores de Shapley exatamente no surrogate multilinear ajustado.
   • Erro de Aproximação: O erro em relação ao modelo original é limitado pelo erro de aproximação de coalizão de pior caso do surrogate ($\epsilon$). Para valores de Shapley, $|\phi^g_i - \phi^f_i| \leq 2\epsilon$.
   • Tratabilidade: Redução provada de tempo exponencial para polinomial: $O(n \cdot \text{poly}(\chi) + n^2)$.

Resultados Experimentais

Os autores avaliaram o TN-SHAP em funções multilineares sintéticas e conjuntos de dados de regressão UCI do mundo real (Concrete, Diabetes, Energy) utilizando professores MLP.

• Validação Sintética: Em funções exatamente multilineares, o TN-SHAP alcançou exatidão teórica com tempos de execução na escala de milissegundos, superando o KernelSHAP-IQ por ordens de magnitude (ex: 3,5ms vs 18,7ms para $n=10$; 19,7ms vs 447,3ms para $n=50$).
• Acurácia no Mundo Real: Em datasets UCI com professores MLP:
  • O TN-SHAP alcançou acelerações de 25–1000× em tempo de execução (wall-clock) sobre o KernelSHAP-IQ com acurácia comparável.
  • Para atribuições de primeira ordem ($k=1$), o TN-SHAP alcançou similaridade de cosseno quase perfeita (0,994) com o ground truth.
  • Para interações de ordem superior ($k=2, 3$), o TN-SHAP manteve acurácia competitiva enquanto as bases de comparação baseadas em amostragem lutavam com variância ou exigiam muito mais tempo de computação para atingir fidelidade semelhante.
• Ablação de Rank: Experimentos mostraram que um rank de estudante TN de $r=5-6$ foi suficiente para recuperar todas as ordens de interação com $R^2 > 0,99$ quando o professor tinha um rank de 16. Ranks menores subestimam as interações de ordem superior.
• Estabilidade de Alta Dimensão: Em configurações sintéticas de alta dimensão ($D=50, 100$), o TN-SHAP manteu alta fidelidade de surrogate ($R^2 > 0,95$) e forte recuperação de características Top-$k$ sob orçamentos de consulta de custo linear.

Significância e Alegações

O artigo afirma que o TN-SHAP preenche a lacuna entre o rigor teórico do cálculo exato de Shapley e a necessidade prática de eficiência. Ao alavancar a estrutura algébrica de funções multilineares e a eficiência das redes de tensores, o método:

• Transforma um problema de enumeração exponencial em um pequeno número de avaliações estruturadas.
• Fornece garantias estruturais (via limites de rank) que abordam problemas de fidelidade comuns em métodos de surrogate local não restritos como o LIME.
• Unifica explicações de Shapley locais com estruturas aditivas globais (GAMs), pois o ajuste de um surrogate de ordem-$k$ resulta em coeficientes $k$-SII exatos que correspondem aos termos de GAM correspondentes.
• Oferece uma alternativa escalável aos métodos baseados em amostragem, particularmente para interações de ordem superior onde a variância da amostragem é tipicamente alta.

Os autores observam que o desempenho do método depende da qualidade do ajuste do surrogate TN e da escolha dos mapas de características, mas resultados empíricos sugerem que até elevações de características e ranks tensoriais modestos são suficientes para capturar estruturas coalicionais complexas na prática.