🤖 machine learning

Quadrature-TreeSHAP: Depth-Independent TreeSHAP and Shapley Interactions

O artigo apresenta o Quadrature-TreeSHAP, um método numericamente estável e independente da profundidade que reformula o Path-Dependent TreeSHAP usando quadratura de Gauss-Legendre para calcular eficientemente valores de Shapley e interações de alta ordem, com ganhos significativos de velocidade tanto em CPU quanto em GPU.

Autores originais: Ron Wettenstein, Rory Mitchell, Peng Yu

Publicado 2026-05-07

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Ron Wettenstein, Rory Mitchell, Peng Yu

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você tem uma máquina de tomada de decisões muito inteligente, mas complicada (como uma árvore que cresceu com milhares de galhos). Você quer saber exatamente por que ela fez uma previsão específica. Ela decidiu "Sim" por causa da Característica A? Ou foi um esforço conjunto entre a Característica B e a Característica C?

Para responder a isso, cientistas de dados usam uma ferramenta matemática chamada SHAP. Pense no SHAP como uma maneira de dividir justamente o "crédito" pela previsão entre todas as características, como dividir uma pizza com base em quem trouxe mais ingredientes.

Por muito tempo, a maneira padrão de fazer isso (chamada TreeSHAP) tinha três problemas principais:

Era lenta: Quanto mais profunda a árvore crescia, mais tempo levava para calcular os créditos. Era como tentar contar cada folha individualmente em um carvalho gigante, uma por uma.
Era instável: À medida que as árvores ficavam mais profundas, a matemática começava a ficar confusa e imprecisa, como tentar equilibrar uma torre de blocos de Jenga que fica oscilando.
Perdia a visão geral: Era ótima para explicar características individuais, mas muito lenta e desajeitada ao tentar explicar como as características funcionavam juntas (interações).

Os autores deste artigo introduziram um novo método chamado Quadrature-TreeSHAP. Eis como ele funciona, usando analogias simples:

1. O "Instantâneo" vs. O "Filme"

Os métodos antigos tentavam calcular o crédito percorrendo cada caminho individual da árvore, passo a passo. Se a árvore fosse profunda, isso levava uma eternidade.

O Quadrature-TreeSHAP muda o jogo. Em vez de percorrer toda a árvore, ele trata o cálculo como um filme. Ele percebe que a matemática por trás da árvore é, na verdade, uma curva suave e previsível (um polinômio).

Em vez de assistir a todo o filme quadro a quadro, este novo método tira 8 "instantâneos" específicos (matematicamente chamados de pontos de quadratura) da curva.

A Magia: Os autores provaram que, para esses modelos de árvore, tirar apenas 8 instantâneos é suficiente para reconstruir todo o filme com precisão perfeita.
O Resultado: Não importa se a árvore tem 10 níveis de profundidade ou 100 níveis. O método ainda precisa apenas desses mesmos 8 instantâneos. Ele ignora completamente a profundidade, tornando-o incrivelmente rápido e consistente.

2. A "Ponte Estável"

O método antigo era como construir uma ponte com tábuas instáveis e irregulares. À medida que a ponte ficava mais longa (árvores mais profundas), as tábuas se deslocavam e a matemática colapsava (instabilidade numérica).

O novo método constrói a ponte usando concreto liso e sólido. Ao calcular a resposta nesses 8 pontos fixos, ele evita completamente as "tábuas instáveis". O resultado é um cálculo que permanece perfeitamente estável, mesmo nas árvores mais profundas e complexas.

3. O Superpoder de "Trabalho em Equipe"

O método antigo lutava para explicar como as características funcionavam juntas (por exemplo, "A Característica A e a Característica B juntas causaram o resultado"). Era como tentar contar quantas pessoas estão em uma sala pedindo que elas se alinhem em pares, depois em grupos de três, depois em grupos de quatro — ficava exponencialmente mais lento.

O Quadrature-TreeSHAP lida com isso sem esforço. Como usa o mesmo truque dos "8 instantâneos" para grupos de qualquer tamanho, ele pode calcular interações complexas de trabalho em equipe (de 3 vias, 4 vias ou até 6 vias) quase instantaneamente.

A Velocidade: Em seus testes, calcular essas interações complexas foi até 1.200 vezes mais rápido do que o melhor método anterior.

4. A "Linha de Montagem" (Eficiência de Hardware)

Finalmente, os autores tornaram este método amigável para chips de computador modernos (CPUs e GPUs).

A Analogia: Imagine uma linha de montagem de fábrica. O método antigo era como um trabalhador que tinha que parar e pensar sobre cada item individualmente de maneira diferente. O novo método é como uma máquina que processa 8 itens ao mesmo tempo em um ritmo perfeito.
O Resultado: Como a matemática é tão regular, ela roda com super eficiência tanto em computadores padrão quanto em placas gráficas poderosas (GPUs), levando a acelerações de até 10x em computadores padrão e 7x em placas gráficas.

Resumo dos Resultados

Os autores testaram isso em 12 conjuntos de dados reais diferentes (como prever preços de imóveis ou identificar objetos em fotos).

Velocidade: É consistentemente mais rápido do que os métodos antigos, às vezes por um fator de 10.
Estabilidade: Não quebra nem fica impreciso, mesmo em árvores muito profundas onde os métodos antigos falhavam.
Adoção: Eles já integraram isso ao XGBoost, uma das ferramentas de aprendizado de máquina mais populares do mundo. Se você usar o XGBoost no futuro, essa nova maneira mais rápida e estável de explicar seus modelos já estará incorporada.

Em resumo: o Quadrature-TreeSHAP é como fazer um upgrade de uma calculadora manual, lenta e instável para um computador digital de alta velocidade e superestável que pode resolver quebra-cabeças complexos de trabalho em equipe num piscar de olhos.

Resumo Técnico: Quadrature-TreeSHAP

Declaração do Problema

A explicabilidade para modelos de ensemble de árvores (por exemplo, XGBoost, Random Forests) depende fortemente dos valores de Shapley. Embora o SHAP Dependente do Caminho seja a abordagem padrão devido à sua eficiência, os métodos existentes enfrentam compromissos significativos em relação ao tempo de execução dependente da profundidade, estabilidade numérica e suporte para interações de ordem superior.

Os métodos atuais do estado da arte exibem limitações específicas:

TreeSHAP e GPUTreeSHAP operam com uma complexidade de tempo de $O(MTLD^2)$ (onde $M$ são amostras, $T$ árvores, $L$ folhas, $D$ profundidade).
FastTreeSHAP v2 e Woodelf reduzem a complexidade para $O(MTLD)$, mas introduzem etapas de pré-processamento exponenciais na profundidade, tornando-os impraticáveis para árvores profundas.
Linear TreeSHAP alcança $O(MTND)$, mas sofre de instabilidade numérica devido a operações na base de monômios.
TreeGrad-Shap melhora a estabilidade via formulações de gradiente, mas é limitado a atribuições de primeira ordem.
TreeSHAP-IQ estende-se para interações de ordem superior, mas possui uma complexidade de $O(MTLD \binom{F-1}{s-1})$ , que escala mal conforme o número de recursos ( $F$ ) e a ordem de interação ( $s$ ) aumentam.

Metodologia

Os autores propõem o Quadrature-TreeSHAP, uma reformulação do TreeSHAP Dependente do Caminho baseada em quadratura de Gauss–Legendre e um polinômio de interação Banzhaf ponderado.

1. Fundamentação Teórica

O método aproveita a relação entre os valores de Shapley e os valores Banzhaf ponderados.

Polinômio Banzhaf Ponderado: Para uma folha $v$ de uma árvore de decisão, o valor de interação Banzhaf ponderado dependente do caminho para um subconjunto de recursos $S$ na probabilidade de inclusão $p$ é expresso como um polinômio $B^{(S)}_{p,v}$ . Este polinômio é derivado da estrutura do caminho da folha e dos pesos das arestas.
Recuperação por Integral: Os valores de interação de Shapley são recuperados integrando esses polinômios Banzhaf sobre a probabilidade de participação $p \in [0, 1]$ :
$SII^{(S)}(f_v) = \int_0^1 B^{(S)}_p(f_v) \, dp$
Aproximação por Quadratura: Em vez de integração simbólica, os autores avaliam esta integral usando quadratura de Gauss–Legendre. A integral é aproximada como uma soma ponderada do polinômio avaliado em nós fixos $t_m$ :
$SII^{(S)}_v \approx \sum_{m=1}^n w_m B^{(S)}_{t_m, v}$

2. Implementação Algorítmica

Formulação de Ponto Fixo: O algoritmo realiza uma única travessia em profundidade (DFS) da árvore. Durante a travessia, ele propaga os valores do polinômio do caminho em um conjunto fixo de nós de Gauss–Legendre (tipicamente 8) em vez de expandir polinômios simbolicamente.
Redução de Complexidade:
- Teoricamente, o grau do integrando para interações de ordem- $s$ é no máximo $d-s$ (onde $d$ é o número máximo de recursos únicos em um caminho).
- Na prática, os autores demonstram que 8 pontos de quadratura fixos são suficientes para atingir precisão de máquina (float32) mesmo para árvores muito profundas.
- Isso remove a dependência da profundidade da árvore $d$ do cálculo interno, reduzindo a complexidade efetiva de $O(MTN \lceil d/2 \rceil)$ para $O(MTN)$ para primeira ordem, e de $O(MTN d^s)$ para $O(MTN d^{s-1})$ para interações de ordem- $s$ .
Aceleração por Hardware: Como o cálculo envolve avaliar o mesmo conjunto fixo de pontos para cada caminho, a aritmética é regular. Isso permite a execução eficiente de SIMD (Instrução Única, Dados Múltiplos) em CPUs e SIMT (Instrução Única, Threads Múltiplos) em GPUs, eliminando a sobrecarga de empacotamento de binários e agendamento exigida pelo GPUTreeSHAP.

Contribuições Principais

Algoritmo de Interação de Qualquer Ordem: O artigo apresenta um algoritmo para calcular valores de interação de Shapley de qualquer ordem que melhora a complexidade do estado da arte do TreeSHAP-IQ de $O(MTLD \binom{F-1}{s-1})$ para $O(MTN d^s)$ . Isso produz ganhos substanciais quando o número de recursos excede a profundidade da árvore ( $F > D \ge d$ ).
Reformulação Baseada em Quadratura: Os autores fornecem uma análise teórica e empírica mostrando que 8 pontos de Gauss–Legendre são suficientes para atingir precisão de máquina para valores de Shapley e interações, desacoplando efetivamente o tempo de execução da profundidade da árvore na prática.
Estabilidade Numérica: Ao avaliar o polinômio de resumo em nós limitados e positivos em vez de expandir coeficientes em uma base de monômios, o método evita cancelamento catastrófico. Os autores afirmam que o Quadrature-TreeSHAP é mais numericamente estável que o TreeSHAP, particularmente para ensembles profundos.
Implementação Eficiente em Hardware: O método é implementado em C++ para CPU e integrado ao XGBoost para GPU. Ele explora a vetorização (4 pontos na CPU, 32 na GPU) para alcançar acelerações significativas sobre implementações existentes.
Integração de Código Aberto: A implementação é de código aberto e integrada à biblioteca XGBoost (substituindo o backend TreeSHAP), acessível via chamadas de API padrão (pred_contribs=True e pred_interactions=True).

Resultados Experimentais

Os autores avaliaram o Quadrature-TreeSHAP em 12 ensembles de referência do XGBoost (Adult, CalHousing, CovType, Fashion-MNIST) em regimes pequenos, grandes e esparsos.

Primeira Ordem (Valores de Shapley):
- CPU: 1,06× a 10,59× mais rápido que o TreeSHAP (mediana 3,84×).
- GPU: 1,84× a 6,95× mais rápido que o GPUTreeSHAP.
Segunda Ordem (Interações Pareadas):
- CPU: 3,80× a 58,11× mais rápido que o TreeSHAP (mediana 12,86×).
- GPU: Até 6,65× mais rápido que o GPUTreeSHAP (embora o GPUTreeSHAP tenha permanecido competitivo em cargas de trabalho específicas de baixa profundidade).
Interações de Ordem Superior (Benchmarks em Python):
- Comparado ao TreeSHAP-IQ em interações de terceira ordem, o Quadrature-TreeSHAP foi 18,73× a 26,49× mais rápido.
- No conjunto de dados CovType-esparso, a aceleração sobre o TreeSHAP-IQ aumentou com a ordem de interação, atingindo 1209,37× na ordem 6.
Estabilidade Numérica:
- No benchmark Fashion-MNIST-esparso com aumento da profundidade da árvore, o TreeSHAP tornou-se instável além da profundidade 32. O Quadrature-TreeSHAP permaneceu estável, com 6–8 pontos alcançando alta precisão.

Significado

O artigo afirma que o Quadrature-TreeSHAP oferece uma reformulação numericamente estável, eficiente em hardware e consciente de interações do SHAP Dependente do Caminho. Ao mudar da aritmética polinomial simbólica para quadratura de ponto fixo, o método resolve o compromisso entre dependência da profundidade e estabilidade numérica. Ele permite o cálculo eficiente de interações de alta ordem em árvores profundas, uma tarefa anteriormente prejudicada pela complexidade exponencial ou instabilidade de métodos anteriores. A integração no XGBoost garante utilidade prática imediata para usuários da biblioteca e do pacote shap mais amplo.