Resumo Técnico: Árvore de Partição: Estimativa de Densidade Condicional sobre Espaços de Resultado Gerais

Declaração do Problema

As árvores de decisão são amplamente valorizadas por sua interpretabilidade e eficiência na previsão pontual (classificação e regressão). No entanto, estender métodos baseados em árvores para estimativa de densidade condicional sobre espaços de resultado gerais (suportando simultaneamente variáveis contínuas e categóricas) permanece desafiador. Abordagens existentes enfrentam limitações específicas:

• Suposições Paramétricas: Métodos como o CADET empregam densidades condicionais paramétricas nos nós folha, o que pode não capturar distribuições complexas e não gaussianas.
• Escalabilidade: Métodos como o CDTree, que otimizam divisões e histogramas por folha conjuntamente, podem ser computacionalmente exigentes, limitando sua aplicabilidade a grandes conjuntos de dados.
• Formulação Unificada: Há uma falta de um quadro unificado que trate classificação e regressão como casos específicos de estimativa de densidade condicional sem impor restrições paramétricas à distribuição-alvo.

Metodologia

1. Quadro Teórico: Formulação Baseada na Teoria da Medida

Os autores propõem a Árvore de Partição, um quadro fundamentado na teoria da medida.

• Particionamento do Espaço Conjunto: Diferentemente das árvores tradicionais que particionam apenas o espaço de covariáveis $X$, a Árvore de Partição constrói uma partição adaptativa aos dados $\pi_N$ do espaço conjunto de covariáveis e resultados $Z = X \times Y$.
• Estimação Constante por Partes: A densidade condicional $f(y|x)$ é modelada como uma função constante por partes definida nessas partições.
• Derivada de Radon–Nikodym: O método define a densidade condicional através da derivada de Radon–Nikodym em relação a uma medida produto $\nu = P_X \otimes \mu_Y$, onde $\mu_Y$ é uma medida de referência (medida de contagem para resultados discretos, Lebesgue para contínuos).
• Estimador: Para uma célula $A = A_X \times A_Y$ na partição, a estimativa de densidade é:
  $$\hat{f}_\pi(z) = \frac{n_{XY}(A)}{n_X(A) \mu_Y(A_Y)}$$
  onde $n_{XY}$ e $n_X$ são contagens empíricas. Esta formulação lida naturalmente com resultados de tipo misto e permite que classificação e regressão surjam como casos especiais.

2. Algoritmo de Construção da Árvore

A árvore é crescida usando uma estratégia gulosa, melhor-primeiro que minimiza diretamente a negação da verossimilhança logarítmica condicional.

• Objetivo: O critério de divisão maximiza o ganho empírico na perda logarítmica:
  $$\hat{G}(\pi', \pi) = \sum_{A' \in \{A_l, A_r\}} \frac{n_{XY}(A')}{N} \log \left( \frac{n_{XY}(A')}{n_X(A') \mu_Y(A'_Y)} \right) - \frac{n_{XY}(A)}{N} \log \left( \frac{n_{XY}(A)}{n_X(A) \mu_Y(A_Y)} \right)$$
• Tipos de Divisão:
  • Divisões de Covariáveis ($X$): Refinam o espaço de covariáveis (divisões padrão de árvores).
  • Divisões de Resultados ($Y$): Refinam os bins de resultados dentro de uma região fixa de covariáveis. Isso permite que a árvore construa adaptativamente histogramas para a distribuição de resultados.
• Eficiência: O algoritmo utiliza técnicas eficientes de ordenação e soma de prefixos para avaliar divisões candidatas em tempo $O(d_Z N \log N)$ (ou $O(d_Z N \log^2 N)$ para árvores balanceadas), igualando a escalabilidade do CART padrão.
• Truncamento: Para resultados contínuos ilimitados, o método emprega um truncamento dependente dos dados (caixa min-max) para garantir medida finita, com garantias teóricas de que o truncamento captura assintoticamente toda a massa de probabilidade.

3. Floresta de Partição

Para melhorar a estabilidade e o desempenho preditivo, os autores introduzem a Floresta de Partição, um método de ensemble. Ele faz a média das estimativas de densidade condicional de múltiplas Árvores de Partição treinadas em amostras bootstrap (bagging), opcionalmente com subamostragem aleatória de características.

4. Garantias Teóricas

O artigo estabelece condições suficientes para a consistência $L^1(\nu)$ do estimador. A consistência é garantida se a sequência de partições satisfizer:

1. O número de células cresce sublinearmente em relação a $N$.
2. A função de crescimento da família de partições satisfaz limites específicos de dimensão VC.
3. O diâmetro das células encolhe para zero.
4. O número de projeções distintas de covariáveis cresce suficientemente devagar em relação a $\sqrt{\log N / N}$.

Contribuições Principais

1. Quadro Unificado: Um único quadro não paramétrico para estimativa de densidade condicional que lida com resultados contínuos, categóricos e de tipo misto sem suposições paramétricas.
2. Otimização Direta: Um algoritmo de construção de árvore que otimiza diretamente a perda logarítmica condicional via busca gulosa melhor-primeiro, evitando os gargalos computacionais da otimização conjunta de divisão-histograma encontrados em trabalhos anteriores.
3. Escalabilidade: Uma implementação com complexidade computacional comparável ao CART padrão, tornando-a viável para grandes conjuntos de dados.
4. Extensão de Ensemble: A introdução da Floresta de Partição, que demonstra melhoria na previsão probabilística sobre árvores únicas.
5. Análise Teórica: Provas rigorosas de consistência para o estimador proposto sob suposições padrão de complexidade e encolhimento.

Resultados Experimentais

Os autores avaliaram a Árvore de Partição e a Floresta de Partição em um conjunto diversificado de benchmarks de classificação e regressão, comparando-os com CART, Florestas Aleatórias, CADET e CDTree.

• Classificação:
  • Árvores Únicas: A Árvore de Partição superou o CART na maioria dos conjuntos de dados (8 de 9) em termos de perda logarítmica.
  • Ensembles: A Floresta de Partição alcançou menor perda logarítmica que as Florestas Aleatórias na maioria dos conjuntos de dados, demonstrando calibração probabilística superior.
• Regressão:
  • Árvores Únicas: A Árvore de Partição forneceu previsões pontuais competitivas e forte desempenho probabilístico. Notavelmente, superou o paramétrico CADET em conjuntos de dados maiores (por exemplo, Air, Power, California, Protein), sugerindo melhor escalabilidade e adaptabilidade ao tamanho da amostra.
  • Ensembles: A Floresta de Partição superou consistentemente as Florestas Aleatórias na maioria dos benchmarks de regressão (8 de 10) em relação à perda logarítmica.
• Robustez:
  • Ruído: O método mostrou robustez a ruídos homoscedásticos e heteroscedásticos, com degradação de desempenho comparável ao CDTree e melhor estabilidade que o CADET.
  • Características Redundantes: Embora o CDTree tenha mostrado estabilidade ligeiramente melhor contra duplicação de características correlacionadas, a Árvore de Partição produziu previsões mais consistentes (menor variância) sob corrupção de características em comparação com o CADET.
• Eficiência: Comparações de tempo de execução no conjunto de dados Physicochemical Protein mostraram que a Árvore de Partição é aproximadamente 5$\times$ mais rápida que o CADET e 25$\times$ mais rápida que o CDTree em $N=10.000$.

Significado e Alegações

O artigo alega que a Árvore de Partição oferece uma alternativa não paramétrica e escalável aos métodos probabilísticos baseados em árvores existentes. Seu significado principal reside em:

• Flexibilidade: A capacidade de modelar distribuições condicionais complexas sobre espaços de resultado gerais sem assumir uma forma paramétrica específica (por exemplo, Gaussiana).
• Interpretabilidade: Manter a interpretabilidade intrínseca das árvores de decisão (via importância de características baseada em ganho e visualização de densidade constante por partes) enquanto fornece saídas probabilísticas completas.
• Desempenho: Demonstrar empiricamente que ensembles de árvores baseados em densidade não paramétrica podem superar tanto ensembles tradicionais de previsão pontual (Florestas Aleatórias) quanto árvores baseadas em densidade paramétrica (CADET), particularmente à medida que o tamanho do conjunto de dados aumenta.

Os autores posicionam a Árvore de Partição como um candidato natural para integração em pipelines de inferência causal e outras aplicações que exigem estimativa de densidade condicional flexível, reconhecendo que trabalhos futuros poderiam explorar frameworks de boosting e estratégias de poda personalizadas.