Resumo Técnico: PINE – Poda de Conjuntos de Árvores Reforçadas com Equivalência de Predição Conformal em Distribuição

1. Declaração do Problema

Métodos de conjuntos de árvores, como Florestas Aleatórias, Árvores de Decisão Reforçadas por Gradiente (GBDT) e XGBoost, são amplamente utilizados para dados tabulares devido ao seu forte desempenho preditivo e interpretabilidade. No entanto, conjuntos grandes acarretam altos custos de inferência e ocupação de memória, complicando tarefas subsequentes como verificação de robustez e verificações de equidade.

A poda de conjuntos post-hoc é uma solução padrão, mas os métodos existentes enfrentam um trade-off entre compressão e fidelidade (equivalência de predição):

• Poda orientada à precisão: Métodos que otimizam os trade-offs entre precisão e compressão frequentemente alteram um subconjunto de predições. Essa falta de fidelidade pode interromper a consistência decisória em domínios de alto risco (por exemplo, medicina, finanças), onde fluxos de trabalho subsequentes dependem de saídas específicas do modelo.
• Poda fiel: Métodos como FIPE (Emine et al., 2025) e Conjuntos de Árvores Born-Again (Vidal & Schiffer, 2020) garantem equivalência exata de predição para todas as entradas em todo o espaço de entrada. Embora isso garanta consistência decisória, a exigência de preservar predições mesmo para entradas raras ou fora de distribuição (OOD) limita severamente a taxa de compressão alcançável.

O problema central abordado é como alcançar taxas de compressão mais altas mantendo alta fidelidade, sem o ônus restritivo de garantir equivalência em entradas OOD que raramente são observadas na prática.

2. Metodologia: PINE

Os autores propõem o PINE (Poda com Equivalência em Distribuição), um framework de poda que garante equivalência de predição apenas dentro de uma região em distribuição (ID) calibrada, $X_{ID}(\alpha)$.

Conceito Central

O PINE relaxa a restrição da poda fiel ao restringir a garantia de equivalência a entradas que são "plausíveis" sob a distribuição de dados. Ele introduz um único hiperparâmetro, $\alpha$ (nível de não cobertura), que controla o tamanho dessa região. O método garante que, para uma entrada futura amostrada da mesma distribuição, a probabilidade de o modelo podado corresponder à predição do modelo original seja de pelo menos $1-\alpha$.

Pipeline Algorítmico

O PINE baseia-se no framework iterativo Pruner-Oracle utilizado pelo FIPE, mas modifica o espaço de busca do Oracle:

1. Definição de Pontuação Plausível: Uma função de pontuação $s(x)$ é definida de modo que pontuações mais baixas indiquem maior plausibilidade (probabilidade) sob a distribuição de dados. A região em distribuição é definida como $X_{ID}(\alpha) = \{x \in \mathcal{X} \mid s(x) \leq \tau(\alpha)\}$.
2. Pontuação da Árvore de Chow-Liu: O artigo adota o log-verossimilhança negativa de uma árvore de Chow-Liu como pontuação plausível. Características contínuas são discretizadas em bins, e a árvore de Chow-Liu aproxima a distribuição conjunta como uma estrutura de árvore. Essa escolha é crítica porque o log-verossimilhança negativa se decompõe em uma forma aditiva (marginal da raiz + termos condicionais de arestas), permitindo que a restrição $s(x) \leq \tau(\alpha)$ seja codificada eficientemente como uma restrição de Programação Linear Inteira Mista (MILP).
3. Calibração Conformal: Usando um conjunto de calibração $D_{cal}$, o limiar $\tau(\alpha)$ é determinado via predição conformal dividida. Isso garante que, sob a suposição de trocabilidade, a região $X_{ID}(\alpha)$ cubra entradas futuras com probabilidade de pelo menos $1-\alpha$.
4. Poda Iterativa:
   • Podador: Atualiza os pesos das árvores para satisfazer a equivalência de predição em um conjunto crescente de restrições.
   • Oracle: Busca contraexemplos (entradas onde as predições diferem), mas restringe sua busca apenas à região $X_{ID}(\alpha)$.
   • O processo se repete até que nenhum contraexemplo seja encontrado dentro da região ID.

Garantias Teóricas

• Equivalência Probabilística: Sob a suposição de trocabilidade, o PINE fornece um limite inferior de $1-\alpha$ na probabilidade de a predição do modelo podado corresponder à do modelo original para uma entrada futura.
• Complexidade: O número de estados discretos que o Oracle deve explorar é limitado superiormente por $e^{\tau(\alpha)}$. Como $\tau(\alpha)$ é monótono em $\alpha$, aumentar $\alpha$ (permitindo uma taxa de não cobertura maior) reduz exponencialmente o espaço de busca, facilitando maior compressão.

3. Contribuições Principais

1. Framework PINE: Um método de poda inovador que troca a fidelidade global estrita por fidelidade em distribuição de alta probabilidade, permitindo taxas de compressão significativamente maiores do que as linhas de base de poda fiel.
2. Integração Conformal: A primeira aplicação de predição conformal dividida para definir uma região em distribuição garantida para poda de conjuntos, fornecendo um limite probabilístico rigoroso sobre a equivalência de predição.
3. Codificação de Pontuação em MILP: A proposta de usar o log-verossimilhança negativa da árvore de Chow-Liu como pontuação plausível, que é tanto expressiva para capturar dependências de características quanto computacionalmente eficiente para codificação em MILP.
4. Controle Sistemático de Trade-off: Um mecanismo para ajustar sistematicamente o trade-off fidelidade-compressão via o parâmetro único $\alpha$.

4. Resultados Experimentais

Os autores avaliaram o PINE em 12 conjuntos de dados tabulares públicos (por exemplo, Adult, COMPAS, Pima-Diabetes) usando conjuntos XGBoost ($M=30$ árvores, profundidade $D=2$).

• Compressão vs. Fidelidade: O PINE supera significativamente as linhas de base de poda fiel (FIPE). À medida que $\alpha$ aumenta de 0,05 para 0,8, a taxa média de poda aumenta de ~45% para ~68%, enquanto a fidelidade média permanece alta (99,15%–99,96%). Em contraste, o FIPE alcança uma taxa média de poda de ~44% com 100% de fidelidade.
• Comparação com Métodos Orientados à Precisão: Embora métodos orientados à precisão (IC, DREP, MDEP) possam manter a precisão de teste, eles exibem quedas substanciais de fidelidade (frequentemente <90%) mesmo dentro da região em distribuição. O PINE mantém fidelidade quase perfeita dentro da região calibrada.
• Validação de Cobertura: A cobertura empírica de teste $\hat{\pi}_{ID}$ acompanha de perto o alvo $1-\alpha$, validando a eficácia da calibração conformal dividida.
• Escalabilidade: O método é mais sensível à profundidade da árvore ($D$) do que ao número de árvores ($M$). Árvores mais profundas reduzem a compressão alcançável devido a regiões decisórias mais localizadas, enquanto conjuntos maiores aumentam principalmente o tempo de execução da otimização.

5. Significado e Alegações

O artigo alega que o PINE aborda uma lacuna crítica na compressão de modelos: a incapacidade de métodos fiéis existentes de comprimir modelos efetivamente sem sacrificar a consistência decisória, e a incapacidade de métodos de poda padrão de garantir consistência.

• Impacto Prático: O PINE permite que praticantes comprimam modelos em até 30% a mais do que as linhas de base fiéis, preservando a consistência decisória em entradas futuras prováveis. Isso é particularmente valioso para domínios de alto risco, onde saídas de modelos acionam fluxos de trabalho subsequentes ou requerem auditabilidade.
• Limitações: Os autores modestamente reconhecem que a garantia depende da suposição de trocabilidade (sem mudança de distribuição). Se a distribuição de dados mudar, a garantia pode enfraquecer. Além disso, o custo computacional está ligado à resolução de MILPs, o que pode ser caro para configurações multiclasse ou árvores muito profundas.
• Conclusão: O PINE oferece uma abordagem verificável e probabilística para poda que equilibra os objetivos concorrentes de eficiência e confiabilidade, indo além da escolha binária entre "preciso mas inconsistente" e "consistente mas não comprimido".