Resumo Técnico: Árvores de Adiamento de Múltiplos Estágios para Interpretabilidade Híbrida

Declaração do Problema

O desafio central na aprendizagem automática interpretável é construir modelos que igualem o desempenho preditivo de estado da arte enquanto permanecem transparentes. Embora árvores de decisão esparsas bem otimizadas possam alcançar isso em domínios ruidosos, uma lacuna significativa entre precisão e interpretabilidade persiste em muitos cenários. Nesses casos, ensembles complexos (ex: Random Forests, XGBoost) são necessários para alta precisão, mas carecem de interpretabilidade. Abordagens híbridas existentes tentam preencher essa lacuna usando um modelo simples para prever na maioria dos dados e adiando amostras difíceis para uma caixa-preta. No entanto, os métodos atuais frequentemente lutam para manter a precisão da caixa-preta sem adiar a vasta maioria das amostras, ou falham em recuperar a interpretabilidade para o subconjunto adiado.

Metodologia

Os autores introduzem as Árvores de Adiamento de Múltiplos Estágios (MDTs - Multistage Defer Trees), uma classe de modelo que aloca complexidade de forma adaptativa, roteando entradas através de uma sequência de árvores de decisão esparsas antes de potencialmente adiar para uma caixa-preta.

Definições Principais

• Árvore de Adiamento (Defer Tree): Uma árvore binária onde as folhas são rotuladas com uma previsão de classe ou uma ação de adiamento (defer). Se uma folha adia, a previsão é passada para um modelo de fallback $B$.
• Árvore de Adiamento de Múltiplos Estágios (MDT): Uma sequência ordenada de árvores de adiamento $(T_1, \dots, T_K)$. Uma entrada $x$ é avaliada por $T_1$. Se $T_1$ prevê, o processo para. Se $T_1$ adia, $x$ é passado para $T_2$, e assim por diante. Se todas as árvores adiarem, o modelo de fallback final $B$ (que pode ser uma caixa-preta ou um modelo esparso) realiza a previsão.

Algoritmo de Treinamento

O procedimento de treinamento utiliza uma estratégia de otimização alternada iterativa, de cima para baixo:

1. Inicialização: Começa com um modelo de fallback $B$ treinado no conjunto de dados completo.
2. Treinamento de Estágio Iterativo: Para o estágio $j$, treina-se uma árvore de adiamento $T_j$ no subconjunto de dados adiados pelos estágios anteriores. A função objetivo penaliza erros de classificação, complexidade da árvore (número de divisões/splits) e adiamentos para o modelo de fallback atual.
3. Atualização do Fallback: Após o treinamento de $T_j$, o conjunto adiado é atualizado. O modelo de fallback $B$ é retreinado no conjunto de dados completo usando pesos baseados em distância.
   • Pontos adiados recebem peso total.
   • Pontos não adiados são desponderados com base em sua distância à região de adiamento (medida no espaço de quantis). Isso permite que o modelo de fallback "tome emprestada a força" de pontos próximos, melhorando a generalização na região de adiamento e evitando o sobreajuste (overfitting) a amostras específicas de adiamento.
4. Rastreamento da Região Viável: O algoritmo rastreia a interseção geométrica das regiões de adiamento (hiperretângulos alinhados aos eixos) para filtrar divisões que são irrelevantes para a atual região de adiamento, melhorando a eficiência.
5. Terminação: O processo para quando o conjunto adiado torna-se vazio, para de encolher ou excede orçamentos de complexidade (ex: total de folhas ou tamanho de árvore única expandida).

Compressão e Representação

Uma contribuição teórica fundamental é a Representação de Lista de Regras das MDTs. O Teorema 1 estabelece que uma MDT com $K$ estágios pode ser representada como uma lista de regras onde cada folha de não-adiamento em qualquer estágio contribui com exatamente um antecedente. Isso resulta em uma representação compacta significativamente menor do que listas de regras derivadas de ensembles padrão (como Random Forests), onde os antecedentes podem crescer com a soma das profundidades de todas as árvores.

Os autores também fornecem algoritmos para comprimir a MDT em uma única árvore de adiamento, expandindo recursivamente as folhas de adiamento e podando divisões que são garantidas para avaliar da mesma forma dentro da subregião específica dos dados de adiamento.

Principais Contribuições

1. Classe de Modelo: Introdução das Árvores de Adiamento de Múltiplos Estágios, que alocam complexidade de forma adaptativa baseada na dificuldade de diferentes regiões do espaço de características.
2. Algoritmo de Treinamento: Desenvolvimento de um algoritmo iterativo que estreita sucessivamente a região de adiamento enquanto utiliza o reponderamento baseado em distância para melhorar a generalização do modelo de fallback.
3. Técnicas de Compressão: Algoritmos para comprimir MDTs em representações de lista de regras ou árvore esparsa única, e métodos para comprimir o modelo de fallback (se este for um ensemble de árvores) especificamente para o subconjunto adiado.
4. Garantias Teóricas: Provas relativas ao tamanho da representação de lista de regras e a melhoria monotônica da função objetivo durante o treinamento.

Resultados Experimentais

Os autores avaliaram as MDTs contra ensembles de árvores de estado da arte (XGBoost, Random Forest), modelos aditivos esparsos (FIGS) e baselines híbridos existentes (variantes de HyRS e CORELS) em 24 conjuntos de dados.

• Precisão vs. Adiamento: As MDTs consistentemente igualaram o desempenho de ensembles de caixa-preta complexos (XGBoost) enquanto adiavam uma proporção pequena de amostras (ex: $\le 25\%$). Em muitos conjuntos de dados, as MDTs alcançaram precisão dentro do intervalo de confiança de 95% do melhor método de caixa-preta com taxas de adiamento significativamente menores do que os modelos híbridos concorrentes.
• Interpretabilidade: O componente interpretável das MDTs (a sequência de árvores) exigiu muito poucas decisões de divisão por amostra (frequentemente $\le 5,5$ divisões em média) para atingir o desempenho próximo ao da caixa-preta.
• Compressão: Quando o modelo de fallback era um ensemble de árvores, os autores demonstraram que comprimir o fallback especificamente para a região de adiamento resultou em reduções significativas no número de divisões e folhas necessárias, sem sacrificar a precisão naquela região.
• Comparação com Baselines: As MDT superaram árvores únicas não-adiantes e métodos híbridos existentes (como HyRS e FLMM) no trade-off precisão-adiamento, particularmente em regimes onde uma única árvore é insuficiente.

Significância e Alegações

O artigo afirma que as MDTs expandem a fronteira precisão–interpretabilidade. Os autores argumentam que, mesmo quando modelos complexos são necessários para atingir a precisão de estado da arte, eles não precisam ser totalmente opacos. Ao rotear a maioria dos dados através de um pequeno número de árvores esparsas e confinar a dependência de modelos complexos a uma região altamente restrita do espaço de características, as MDTs permitem que os profissionais mantenam alta precisão enquanto garantem que a maioria das decisões permaneça interpretável. O método demonstra que o trade-off entre precisão e interpretabilidade não é necessariamente global; ele pode ser gerenciado localmente, com a complexidade alocada apenas onde modelos simples comprovadamente falham.