Resumo Técnico: Árvores de Decisão Ternárias com Zonas de Incerteza Localmente Adaptativas

Declaração do Problema

As árvores de decisão padrão, particularmente aquelas baseadas no algoritmo CART, particionam o espaço de características usando limiares binários rígidos. Esse mecanismo atribui confiança idêntica a instâncias independentemente de sua proximidade em relação ao limite de decisão. Consequentemente, uma instância localizada longe do limiar ótimo $\theta$ é tratada com a mesma certeza que uma que está diretamente sobre ele. Esse "comprometimento rígido" cria uma fraqueza conhecida: ele superestima a certeza para instâncias próximas aos limites onde a divisão aprendida é menos confiável, falhando em sinalizar a aplicações a jusante que uma previsão pode ser ambígua.

Abordagens existentes para lidar com a incerteza frequentemente dependem de especificações externas de ruído (por exemplo, erros conhecidos de sensores) ou limiares globais derivados de estatísticas ao nível do conjunto de dados. Esses métodos não se adaptam localmente à qualidade específica da divisão ou à distribuição de dados em cada nó. Além disso, abordagens como árvores de decisão difusas ou árvores de decisão suaves frequentemente carecem de uma zona de incerteza explícita e interpretável derivada de estatísticas locais de divisão.

Metodologia

O artigo introduz Árvores de Decisão Ternárias, que aumentam as divisões binárias padrão com uma zona de incerteza localmente adaptativa de meia-largura $\delta$ centrada no limiar ótimo $\theta^*$.

A Avaliação Ternária

Para uma característica $x_f$ e limiar $\theta^*$, a lógica de decisão é definida como:

• Verdadeiro (Decisivo): $x_f > \theta^* + \delta$
• Falso (Decisivo): $x_f \leq \theta^* - \delta$
• Indec (Limite-Incerto): $\theta^* - \delta < x_f \leq \theta^* + \delta$

Instâncias que caem na zona Indec não se abstêm de prever. Em vez disso, elas recebem uma previsão formada por uma combinação ponderada pela distância das saídas de probabilidade de ambas as subárvores filhas. Crucialmente, essas instâncias são sinalizadas como "incertas no limite", permitindo que sistemas a jusante as tratem de forma diferente (por exemplo, roteamento para revisão humana) sem reter uma previsão de classe.

Cálculo de $\delta$ Localmente

A contribuição técnica central é derivar $\delta$ localmente em cada nó usando estatísticas já computadas durante a busca de divisão padrão do CART, não exigindo dados externos ou modelos de ruído. O artigo propõe e avalia cinco métodos:

1. Platô de Qualidade ($\delta_{QP}$): Mede a largura do "platô" na curva do critério de divisão (por exemplo, ganho de Gini) ao redor de $\theta^*$. Um platô largo indica que os dados não restringem precisamente a localização ótima da divisão.
2. Sobreposição de Classes ($\delta_{CO}$): Calcula a largura da região onde as distribuições de características condicionais às classes se sobrepõem, com base em percentis empíricos.
3. Razão de Ganho ($\delta_{GR}$): Escala inversamente o intervalo da característica pela razão de ganho (Ganho de Informação relativo à entropia da divisão). Razões de ganho baixas indicam divisões ambíguas, levando a um $\delta$ maior.
4. Bootstrap de Nó ($\delta_{NB}$): Mede o desvio padrão do limiar ótimo $\theta^*$ através de reamostragens bootstrap dos dados de treinamento do nó. Isso quantifica diretamente a instabilidade do limiar.
5. Margem ($\delta_{M}$): Inspirado em Máquinas de Vetor de Suporte, isso define $\delta$ como a distância de $\theta^*$ até o exemplo de treinamento de classe cruzada mais próximo (o "vetor de suporte" naquele nó). Se a divisão for perfeitamente limpa, usa a lacuna física entre pontos de dados adjacentes.

Arquiteturas de Roteamento

Duas arquiteturas foram avaliadas para propagar instâncias incertas:

• Roteamento Probabilístico: A estrutura da árvore permanece binária. Durante a previsão, instâncias na zona de incerteza são roteadas para ambas as crianças com pesos inversamente proporcionais à sua distância do limiar, e as saídas são combinadas.
• Ramo Médio Rígido: Um terceiro nó filho é adicionado à estrutura da árvore, treinado exclusivamente em instâncias dentro da zona de incerteza.
  Os resultados experimentais indicaram que o roteamento probabilístico geralmente superou a abordagem de meio rígido, pois esta última remove exemplos incertos dos conjuntos de treinamento dos ramos esquerdo e direito, degradando sua qualidade.

Principais Contribuições

1. Estrutura: Introdução de árvores de decisão ternárias que fornecem uma zona de incerteza principista e localmente adaptativa para cada divisão.
2. Cinco Métodos de Estimação: Derivação de cinco métodos distintos para calcular $\delta$ usando apenas estatísticas padrão de divisão do CART, eliminando a necessidade de modelos de ruído externos.
3. Avaliação de Roteamento: Análise comparativa de roteamento probabilístico versus de meio rígido, demonstrando a superioridade da combinação probabilística para a maioria dos métodos.
4. Avaliação Empírica Extensa: Avaliação em 72 conjuntos de dados OpenML-CC18, três benchmarks sintéticos de Breiman (com erros de Bayes conhecidos) e quatro conjuntos de dados médicos/financeiros de alto risco.
5. Estrutura de Diagnóstico: Introdução da razão Indeciso/Bayes (U/B) para avaliar o quão bem a taxa de sinalização de um método se alinha com o erro irreduzível teórico de um conjunto de dados.

Resultados

Validade Amplo (OpenML-CC18)

Em 72 conjuntos de dados, todos os cinco métodos usando roteamento probabilístico superaram significativamente a linha de base CART padrão na Precisão Decidida (precisão restrita a instâncias não incertas) com $p \leq 0.001$.

• Método Margem: Alcançou a melhor eficiência (ganho de precisão por unidade de taxa de sinalização, $\eta = 0.104$). Venceu em 42 dos 72 conjuntos de dados, sinalizou apenas 16,7% das instâncias como incertas e não exigiu hiperparâmetros adicionais.
• Sobreposição de Classes e Razão de Ganho: Alcançaram alta precisão decidida, mas sinalizaram uma grande proporção de instâncias (71% e 58%, respectivamente), resultando em menor eficiência.
• Bootstrap de Nó: Desempenhou-se bem, mas foi computacionalmente caro e foi excluído de conjuntos de dados com $N > 20.000$.

Análise Teórica (Benchmarks de Breiman)

Em conjuntos de dados sintéticos com erros de Bayes conhecidos:

• Margem: Mostrou comportamento de auto-calibração em dados geometricamente limpos, sinalizando muito poucas instâncias como incertas (razões U/B < 0,5), comportando-se efetivamente como CART quando o limite é claro.
• Bootstrap de Nó e Platô de Qualidade: Mostraram calibração proporcional, sinalizando mais instâncias em conjuntos de dados mais difíceis (maior erro de Bayes), embora todos os métodos tenham sinalizado em excesso em relação ao erro de Bayes teórico (U/B > 1).
• Lacuna de Calibração: Nenhum método alcançou uma razão U/B de 1,0, indicando que a incerteza local do limiar não corresponde diretamente ao erro de Bayes global.

Aplicações Domésticas

• Mamografia: O Bootstrap de Nó sinalizou 10,8% dos casos como incertos, enquanto melhorou a precisão decidida em 0,71% sobre o CART. Isso é valioso para identificar casos que precisam de revisão secundária.
• Diabetes: O Bootstrap de Nó alcançou um ganho de precisão de +9,8%, mas sinalizou 63,4% dos pacientes, sugerindo um compromisso entre precisão e taxa de sinalização. O Método Margem ofereceu um ponto de operação mais conservador e prático (+0,4% de ganho, 9,5% de sinalização).
• Limitações: No pequeno conjunto de dados de doença cardíaca de Cleveland ($N=303$), o Bootstrap de Nó teve desempenho inferior devido a estimativas de variância pouco confiáveis. No conjunto de dados de crédito alemão, o Método Margem teve desempenho inferior à linha de base, sugerindo limitações com interações complexas de características econômicas.

Significado e Alegações

O artigo afirma estabelecer a árvore ternária como um primitivo principista para classificação consciente da incerteza. Seu significado reside em:

• Utilidade Prática: Fornecer um mecanismo para sinalizar previsões incertas no limite sem se abster, permitindo que sistemas a jusante (por exemplo, triagem médica, subscrição de crédito) apliquem diferentes estratégias de manuseio.
• Tratabilidade Computacional: Derivar zonas de incerteza de estatísticas de divisão existentes sem exigir dados externos ou retreinamento complexo.
• Fundamentação Teórica: Oferecer uma estrutura onde o veredito "Indec" é um qualificador na confiança da previsão, e não uma rejeição da própria previsão.

Os autores observam modestamente que, embora os métodos melhorem a precisão decidida, eles ainda não calibram perfeitamente a taxa de sinalização ao erro de Bayes teórico, identificando essa calibração como um problema aberto concreto para trabalhos futuros.