Resumo Técnico: Árvores e Florestas de Inferência Condicional para Seleção de Atributos

Declaração do Problema

As árvores (CIT) e florestas (CIF) de inferência condicional abordam o "viés de seleção de divisão" inerente às árvores CART clássicas, onde atributos com muitos pontos de corte admissíveis são preferencialmente selecionados devido à otimização conjunta de atributo e limiar. Embora o framework de inferência condicional separe com sucesso a seleção de atributos (Estágio A) da otimização do limiar (Estágio B) para mitigar esse viés, ele introduz custos computacionais significativos. Esses custos surgem de testes de permutação repetidos e buscas exaustivas de limiares em cada nó.

O artigo investiga se CIT e CIF são eficazes como métodos de ranking de top-k atributos para tarefas de predição subsequentes. Especificamente, questiona:

1. Os rankings derivados de árvores e florestas posicionam as variáveis preditivas precocemente o suficiente para melhorar modelos subsequentes fixos?
2. Hiperparâmetros de tempo de execução podem ser ajustados para reduzir a computação sem degradar a qualidade do ranking?
3. Onde esses métodos falham em configurações de alta dimensionalidade ($p$) ou sintéticas, particularmente em relação à amostragem de atributos em florestas?

Metodologia

Estrutura Algorítmica

A metodologia central baseia-se no processo de inferência condicional de dois estágios em cada nó $t$:

• Estágio A (Seleção de Atributos): Testa atributos para associação com a resposta usando permutações de rótulos de Monte Carlo. Na regra de referência "exhaustive fixed-B", cada atributo no conjunto disponível $F_t$ é testado contra um orçamento de permutação fixo $B$. Um atributo é selecionado se seu $p$-valor mínimo passar por um limiar corrigido por Bonferroni.
• Estágio B (Busca de Limiar): Uma vez que um atributo é selecionado, os limiares são buscados apenas para esse atributo. O limiar que minimiza a impureza ponderada da criança (ou maximiza a diminuição da impureza) é escolhido.

Florestas de Inferência Condicional (CIF) agregam essas árvores. Para a seleção de atributos, a CIF soma as importâncias de divisão normalizadas (diminuições de impureza) através de todas as árvores no ensemble. Crucialmente, a CIF utiliza rankings de importância de divisão em vez de $p$-valores brutos do Estágio A. Isso difere da importância do estilo CART, onde atributos com mais limiares têm uma vantagem inerente; na CIF, o Estágio A filtra os atributos antes da busca de limiar, reduzendo esse viés de cardinalidade.

Desenho Experimental

Os autores conduziram um benchmark abrangente utilizando:

• Benchmarks de Dados Reais: 23 conjuntos de dados de classificação e 8 de regressão. Aprendizes subsequentes (Regressão Logística, SVM, KNN, Ridge, SVR) foram ajustados sobre prefixos top-$k$ dos rankings de atributos. O desempenho foi medido por acurácia balanceada (classificação) e $R^2$ (regressão).
• Experimentos Sintéticos: Conjuntos de dados com atributos informativos conhecidos e estruturas de ruído controladas para avaliar as taxas de recuperação de atributos.
• Ablações de Tempo de Execução: Remoção ou modificação sistemática de hiperparâmetros (ex: parada adaptativa, busca de limiar exata vs. histograma, supressão de atributos, amostragem de bootstrap) para medir os impactos no tempo de ajuste e na qualidade do ranking.
• Análise de Alta Dimensionalidade: Experimentos com $p > 100$ para estudar como a amostragem de atributos em florestas afeta a utilização de atributos informativos.

Contribuições Principais

1. Benchmark de Dados Reais: Uma avaliação sistemática da CIF como um método de ranking de atributos contra 17 baselines de classificação e 18 de regressão (incluindo ctree, cforest, XGBoost, LightGBM, Boruta e vários filtros de permutação).
2. Garantia Teórica: O Teorema 1 e o Corolário 1 estabelecem que, sob a "nulidade de permutação completa por nó", se o conjunto de atributos testados e o orçamento de permutação forem fixos independentemente das respostas do nó, os $p$-valores de permutação Monte Carlo corrigidos por Bonferroni $+1$ controlam a taxa de rejeição por nó. Isso fornece uma garantia local para o Estágio A, embora o artigo note que isso não se estende ao controle de erro da árvore ou floresta completa.
3. Trade-offs entre Tempo de Execução e Qualidade: O estudo quantifica o custo computacional de configurações específicas da CIF. Identifica que a parada adaptativa e a busca de limiar exata são os principais drivers de tempo de execução, enquanto sua remoção tem impacto mínimo nos scores subsequentes.
4. Diagnósticos de Amostragem de Atributos: O artigo demonstra que, em configurações esparsas e de alta dimensionalidade, a amostragem padrão de atributos em florestas pode causar a exclusão de atributos informativos de muitas decisões de divisão, potencialmente degradando a recuperação de top-$k$.

Resultados

Desempenho em Dados Reais

• Qualidade de Ranking: A CIF classificou-se em 4º lugar de 17 métodos em classificação e 3º lugar de 18 em regressão.
• Comparação com Baselines: A CIF superou consistentemente seus contrapartes de inferência condicional (ctree, cforest, CIT) em comparações diretas par a par. Também permaneceu competitiva contra fortes baselines de ensemble como Random Forests, ExtraTrees e árvores impulsionadas (XGBoost, LightGBM).
• Estabilidade: Análises de leave-one-dataset-out (LODO) confirmaram que a configuração selecionada da CIF é estável entre os datasets.

Ablações de Tempo de Execução

• Parada Adaptativa: Desativar a parada adaptativa aumentou o tempo de ajuste da CIF em 4,0–8,4× (mediana) com mudanças nos scores subsequentes de $\le 0,006$.
• Busca de Limiar: Alternar de busca baseada em histograma (256 bins) para busca de limiar exata aumentou o tempo em 1,9–10,8×, com mudanças nos scores subsequentes de $\le 0,011$.
• Tamanho da Floresta: Reduzir a floresta para uma única árvore causou a maior queda na qualidade do ranking (ex: $-0,552$ em $R^2$ de regressão), indicando que a agregação de ensemble é crítica para a estabilidade do ranking.

Achados de Alta Dimensionalidade e Sintéticos

• Recuperação de Atributos: Em tarefas sintéticas, a CIF recuperou atributos informativos dentro da lista top-$k$ de forma mais confiável do que posicionou um único atributo informativo no rank 1.
• Limitações de Amostragem: Em simulações esparsas de alto $p$, a CIF padrão (com subamostragem de atributos) utilizou atributos informativos em apenas 33,2% das divisões, comparado a 91,7% para a CIF-all (que avalia todos os atributos). Isso sugere que, em configurações muito esparsas, a amostragem padrão de atributos pode omitir sinais informativos frequentemente.

Significância e Alegações

O artigo alega que a CIF é um método robusto de ranking de atributos top-k para predição subsequente, particularmente em tarefas de classificação. Sua significância reside em:

1. Redução de Viés: Oferece uma alternativa estatisticamente fundamentada às árvores clássicas que reduz o viés de seleção de divisão sem sacrificar a utilidade preditiva em modelos subsequentes.
2. Eficiência Prática: Os estudos de ablação fornecem orientações concretas para profissionais: usar parada adaptativa e limiares de histograma reduz significativamente o tempo de execução com perda negligenciável na qualidade do ranking.
3. Consciência Diagnóstica: Os autores alertam modestamente que a CIF não deve ser tratada como um método de "descoberta do primeiro atributo" em configurações esparsas de alta dimensionalidade sem monitorar a amostragem de atributos. Eles recomendam verificar se os atributos informativos estão sendo realmente usados em divisões, pois a amostragem padrão de florestas pode obscurecê-los.

O artigo conclui que, embora a garantia teórica seja local (por nó), a evidência empírica apoia a CIF como uma abordagem competitiva e livre de viés para seleção de atributos em pipelines práticos de aprendizado de máquina.