Amortized Linear-time Exact Shapley Value for Product-Kernel Methods

Resumo Técnico: Valor de Shapley Exato em Tempo Linear Amortizado para Métodos de Kernel de Produto

Declaração do Problema
Os métodos de kernel são amplamente adotados em aprendizado de máquina e estatística devido à sua flexibilidade e poder expressivo, no entanto, sua natureza de "caixa preta" dificulta a adoção em aplicações de alto risco. Embora os métodos de atribuição baseados em valor de Shapley (por exemplo, SHAP, RKHS-SHAP) ofereçam um framework principiado para explicabilidade, o cálculo exato dos valores de Shapley é geralmente intratável devido ao número exponencial de subconjuntos de características ($2^d$). As abordagens existentes dependem de aproximações (por exemplo, amostragem de Monte Carlo, estimadores baseados em regressão) que incorrem em erros de estimativa inevitáveis, os quais crescem com a dimensionalidade. Além disso, as funções de valor padrão frequentemente exigem amostragem de distribuições marginais ou condicionais ou estimativa de densidade, introduzindo encargos computacionais adicionais e dependências de dados de fundo.

Metodologia
O artigo introduz o PKeX-Shapley, um algoritmo projetado para calcular valores de Shapley exatos para todas as $d$ características de métodos de kernel de produto (por exemplo, Máquinas de Vetores de Suporte, Regressão de Ridge em RKHS) em tempo quadrático em relação ao número de características ($O(d^2)$), ou tempo linear amortizado por característica.

A metodologia repousa sobre três componentes principais:

1. Operador de Remoção Livre de Distribuição: Os autores focam na subclasse de modelos que empregam kernels de produto, onde a função de kernel fatora como $k(x, x') = \prod_{j=1}^d k_j(x_j, x'_j)$. Eles identificam um operador de remoção natural intrínseco a essa estrutura: remover uma característica $j$ corresponde a substituir seu fator de kernel $k_j$ pela identidade multiplicativa ($1$). Essa escolha preserva a estrutura de produto, não requer distribuição de fundo e induz uma função de valor livre de parâmetros.

   • Diferentemente das funções de valor intervencionais ou observacionais que exigem amostragem, esta função de valor é definida via decomposição funcional.
   • A função de valor para uma coalizão $S$ é dada por $v_x(S) = \alpha^\top k_S(X_S, x_S) - f_\emptyset$, onde $f_\emptyset$ é um termo constante que se cancela nas contribuições marginais. Esta formulação não requer amostragem ou estimativa de densidade.

2. Decomposição Funcional: Aproveitando o operador de remoção, o modelo $f(x)$ é decomposto unicamente em uma soma de componentes indexados por subconjuntos de características: $f(x) = \sum_{S \subseteq D} f_S(x_S)$. Os componentes são derivados via inversão de Möbius no reticulado de subconjuntos, resultando em uma forma fechada: $f_S(x_S) = \sum_{i=1}^n \alpha_i \prod_{j \in S} (k_j(x_j, x^{(i)}_j) - 1)$.

3. Cálculo Recursivo via Polinômios Simétricos Elementares (PSEs):

   • O valor de Shapley para uma única característica é expresso como uma soma ponderada de contribuições marginais, que se fatora em termos envolvendo Polinômios Simétricos Elementares (PSEs) das avaliações do kernel.
   • O cálculo direto dos PSEs para cada característica seria ineficiente. Os autores derivam uma formulação recursiva baseada nas identidades de Newton.
   • Para calcular todos os $d$ valores de Shapley conjuntamente, eles empregam uma construção prefixo–sufixo. Eles definem polinômios geradores para o prefixo (características antes de $j$) e o sufixo (características após $j$) do conjunto de características. Ao multiplicar esses polinômios, recuperam os PSEs para o conjunto leave-one-out $Z_{-j}$.
   • Isso permite o cálculo de todos os valores de Shapley em tempo $O(d^2 n)$, onde $n$ é o número de amostras. O algoritmo é numericamente estável, dependendo apenas de adições e multiplicações elemento a elemento, evitando a instabilidade numérica associada a métodos de interpolação polinomial (por exemplo, interpolação de Chebyshev ou Fourier) usados em outros métodos exatos como o TreeSHAP quando aplicados a altas dimensões.

Extensão para Discrepâncias Estatísticas
O framework é estendido além da modelagem preditiva para discrepâncias estatísticas baseadas em kernel, especificamente:

• Discrepância de Média Máxima (MMD): Usada para medir a proximidade distribucional. O operador de remoção produz uma função de valor que aloca a discrepância geral entre duas distribuições para variáveis individuais.
• Critério de Independência Hilbert–Schmidt (HSIC): Usado para medir dependência entre variáveis aleatórias. O método fornece uma decomposição funcional do HSIC, permitindo a atribuição de dependência a características específicas.

Resultados
O artigo valida o PKeX-Shapley através de experimentos em conjuntos de dados sintéticos e do mundo real:

• Precisão vs. Aproximação: Em explicações locais, o PKeX-Shapley (exato) supera significativamente aproximações baseadas em amostragem (por exemplo, Kernel SHAP, RKHS-SHAP). À medida que a dimensionalidade aumenta (por exemplo, $d=50$), métodos baseados em amostragem exigem tamanhos de coalizão proibitivamente grandes para alcançar baixo erro, enquanto o PKeX-Shapley fornece resultados exatos independentemente da dimensionalidade.
• Seleção de Características: Na análise de sensibilidade global usando HSIC, o PKeX-Shapley identifica efetivamente características ativas em tarefas de regressão sintética com funções alvo polinomiais e exponenciais, superando ou igualando baselines como RKHS-SHAP, GEMFIX e BiSHAP.
• Eficiência Computacional: O algoritmo escala para 1.000 características em segundos, enquanto o cálculo por força bruta é limitado a ~20 características. É consistentemente mais rápido que métodos baseados em amostragem, mesmo quando esses métodos usam um pequeno número de amostras de coalizão.
• Estabilidade Numérica: Experimentos comparando diferentes estratégias de agregação de PSEs (recursão quadrática vs. interpolação FFT/Chebyshev) mostram que, embora os métodos de interpolação sejam rápidos, eles sofrem de instabilidade numérica catastrófica em dimensões moderadas ($d \approx 50$). A recursão quadrática proposta permanece estável até $d=1000$.

Significado e Alegações
O artigo alega que o PKeX-Shapley aborda os dois principais desafios do cálculo de valores de Shapley para métodos de kernel:

1. Exatidão sem Aproximação: Fornece uma função de valor em forma fechada e livre de parâmetros que elimina a necessidade de amostragem e estimativa de densidade, removendo assim o erro de estimativa.
2. Escalabilidade: Alcança tempo linear amortizado por característica ($O(dn)$) para cálculo exato, uma melhoria significativa sobre o custo exponencial da força bruta ou a alta variância de métodos de amostragem em configurações de alta dimensionalidade.

Os autores enfatizam que, embora o método seja restrito a kernels de produto, essa restrição estrutural é necessária para o cálculo exato tratável. A extensão do framework para MMD e HSIC fornece novas ferramentas para análise estatística interpretável, permitindo a atribuição de diferenças distribucionais e dependências a variáveis específicas sem depender de aproximações heurísticas. Os autores observam que o método não se estende naturalmente para atribuição estocástica (por exemplo, variância de valores de Shapley em Processos Gaussianos) da mesma forma que métodos para GPs FANOVA, pois a ortogonalidade não se mantém geralmente para kernels de produto.