Resumo Técnico: WOODELF++

Declaração do Problema

Os conjuntos de árvores de decisão são onipresentes em aplicações do mundo real, mas interpretar suas previsões permanece um desafio crítico para a confiança e a tomada de decisões. Três ferramentas principais para interpretar esses modelos são os Gráficos de Dependência Parcial (PDPs), os Gráficos de Dependência Parcial Conjunta (Joint-PDPs) e os Valores de Interação de Dependência Parcial (PDIVs).

• PDPs visualizam como uma única característica afeta a previsão média do modelo.
• Joint-PDPs estendem isso para pares de características para revelar efeitos combinados.
• PDIVs (especificamente a tarefa "Any-Order") quantificam efeitos de interação em todos os subconjuntos possíveis de características para cada linha em um conjunto de dados.

Os métodos atuais de última geração, como os do scikit-learn e o algoritmo FastPD (implementado no pacote GLEX), sofrem de complexidade computacional proibitiva. Abordagens ingênuas escalam linearmente com o número de amostras e características, mas exponencialmente com a profundidade da árvore e o número de características envolvidas nas interações. Para grandes conjuntos de dados (por exemplo, 400.000 linhas) e tarefas de interação complexas (Any-Order-PDIVs), os métodos existentes são ou impraticavelmente lentos (levando dias ou anos) ou dependem de aproximações que podem ignorar comportamentos críticos do modelo, como descontinuidades abruptas.

Metodologia

Os autores apresentam o WOODELF++, um framework unificado e eficiente para calcular PDPs, Joint-PDPs e Any-Order-PDIVs em conjuntos de árvores de decisão. A abordagem baseia-se no trabalho anterior dos autores, WOODELF, que calcula eficientemente valores SHAP modelando conjuntos de árvores de decisão como funções Pseudo-Booleanas (PB) representadas na Forma Normal Disjuntiva Ponderada (WDNF).

As inovações técnicas centrais incluem:

1. Unificação via WDNF e Linearidade:
   Os autores formulam as tarefas PDP, Joint-PDP e PDIV como métricas de jogos cooperativos sobre fórmulas WDNF. Ao aproveitar a propriedade de linearidade dessas métricas, eles podem calcular explicações globais complexas agregando resultados de "cubos" individuais (conjunções de literais) dentro da representação WDNF. Isso evita a necessidade de reavaliar o modelo para cada combinação amostra-característica individualmente.

2. Construção Eficiente de Conjuntos de Dados Consumidores:
   Para calcular PDPs e Joint-PDPs eficientemente, os autores constroem conjuntos de dados "consumidores" ($C$) compactos que permitem que algoritmos de atribuição local calculem gráficos de dependência globais.

   • Para PDPs, eles constroem um conjunto de dados com $k$ linhas representando valores de características amostrados.
   • Para Joint-PDPs, eles introduzem uma construção inovadora que reduz o tamanho do conjunto de dados de $O(k^2 f)$ para $O(k^2 \log f)$ codificando índices de características em binário e usando operações np.tile e np.repeat para garantir que todas as combinações de valores em pares sejam representadas sem linhas redundantes.

3. PDPs Completas:
   Reconhecendo que PDPs padrão com valores amostrados ($k$) podem perder picos estreitos ou efeitos de valor único (por exemplo, um modelo de fraude sinalizando um salário específico de inadimplência), os autores propõem PDPs Completas. Em vez de amostragem arbitrária, as PDPs Completas usam todos os limiares de divisão dos nós da árvore como valores do eixo x. Como as previsões de árvores de decisão são constantes por partes entre os limiares, este método captura o comportamento exato do conjunto com pontos de avaliação mínimos.

4. Redução de Complexidade para Any-Order-PDIVs:
   A contribuição teórica mais significativa é a redução da complexidade para Any-Order-PDIVs.

   • Ingênuo/FastPD: O FastPD processa árvores independentemente, resultando em uma dependência de complexidade de $2^{2D}$ (onde $D$ é a profundidade da árvore) no pior caso.
   • WOODELF++: Ao processar cada caminho da raiz até a folha separadamente e utilizar a estrutura específica da métrica PDIV na WDNF, a dependência de complexidade é reduzida para $4^D$. Isso representa uma melhoria exponencial em relação ao estado da arte.

5. Aproximação e Suporte a GPU:
   O framework suporta naturalmente aproximações Dependentes do Caminho (equivalentes a definir o conjunto de dados de fundo como vazio) e é implementado em Python puro com suporte para aceleração por GPU.

Principais Contribuições

1. Aceleração em PDP e Joint-PDP: O WOODELF++ alcança uma aceleração de aproximadamente 6× sobre o FastPD e até cinco ordens de grandeza sobre o scikit-learn para tarefas PDP e Joint-PDP em grandes conjuntos de dados.
2. Melhoria Exponencial de Complexidade para Any-Order-PDIVs: Os autores demonstram que, para árvores balanceadas, a complexidade muda de exponencial no tamanho da entrada ($2^{2D}$ do FastPD) para polinomial no tamanho da entrada ($4^D$ do WOODELF++). Empiricamente, isso reduz o tempo de execução para Any-Order-PDIVs em 400.000 amostras de um estimado 1.000.000 de anos (FastPD) para 5 minutos (WOODELF++).
3. Introdução de PDPs Completas: Um método inovador para capturar a estrutura completa constante por partes de conjuntos de árvores, permitindo a detecção de sobreajuste e violações de monotonicidade que PDPs amostradas ignoram.
4. Framework Unificado: O artigo estabelece uma conexão simples entre PDPs aproximadas, PDPs exatas e SHAP Dependente do Caminho, unificando-os sob um único framework algorítmico.

Resultados Experimentais

Os autores avaliaram o WOODELF++ em dois grandes conjuntos de dados amplamente utilizados: IEEE-CIS (472k linhas, 397 características) e KDD Cup 1999 (4,9M linhas, 127 características). Os modelos foram treinados usando HistGradientBoostingRegressor com 100 árvores e uma profundidade máxima de 6.

• Desempenho PDP: No IEEE-CIS, o WOODELF++ calculou PDPs Exatas (k=5) em 13,1 segundos (GPU) comparado a 99 segundos para o FastPD e 58,5 minutos para o scikit-learn.
• Desempenho Joint-PDP: Para Joint-PDPs (k=5), o WOODELF++ levou 25 segundos (GPU) versus 130 segundos para o FastPD e um estimado 35 dias para o scikit-learn.
• Any-Order-PDIVs: No IEEE-CIS com 10.000 amostras, o WOODELF++ concluiu a tarefa em 22,6 segundos (GPU). Estima-se que o FastPD exigiria 60.000 anos.
• Correção: Os autores verificaram que as saídas do WOODELF++ correspondem ao scikit-learn e a cálculos diretos de PDIV com uma diferença máxima de 0,00001.

Significado

O artigo afirma que o WOODELF++ muda fundamentalmente a viabilidade de interpretar conjuntos de árvores de decisão. Ao reduzir a complexidade de Any-Order-PDIVs de intratável para prática, ele permite a análise de interações de características de alta ordem que anteriormente eram computacionalmente impossíveis. Além disso, a introdução de PDPs Completas permite que profissionais visualizem os limites de decisão exatos de modelos de árvore, indo além das limitações de aproximações amostradas. Os autores posicionam o WOODELF++ como uma ferramenta necessária para IA escalável e confiável em domínios que exigem compreensão profunda do modelo, como saúde, finanças e ecologia.