Resumo Técnico: PACE (Modelos de Ensemble Poda-e-Compressão)

Declaração do Problema

Modelos de ensemble, particularmente aqueles baseados em árvores de decisão (por exemplo, Florestas Aleatórias, Boosting), alcançam desempenho preditivo de última geração, mas frequentemente sofrem com tamanho excessivo devido à agregação de um grande número de aprendizes fracos. Essa redundância cria barreiras significativas para a implantação em ambientes sensíveis à latência e com recursos limitados, aumenta a pegada de memória e complica tarefas subsequentes, como verificação de robustez e interpretabilidade.

As soluções existentes geralmente se enquadram em duas categorias:

1. Poda: Descartar aprendizes redundantes de um ensemble treinado por reponderação ou remoção. Embora eficaz, a poda é limitada porque não pode gerar novos aprendizes para substituir os descartados, potencialmente limitando o potencial de compressão.
2. Compressão: Gerar novos aprendizes do zero para aproximar o ensemble original. Embora isso possa alcançar alta compressão, muitos métodos perdem a fidelidade (acordo exato de previsão) ou exigem a geração de aprendizes mais complexos que a família original, quebrando as restrições estruturais do modelo.

O desafio central é unificar esses paradigmas para alcançar forte compressão enquanto mantém garantias rigorosas de fidelidade (preservando as previsões do ensemble original) sem ser excessivamente restringido por regiões de dados irrelevantes.

Metodologia: O Framework PACE

O PACE (Ensemble Poda-e-Compressão) introduz uma estratégia de duas fases que intercala a geração ativa de aprendizes com a poda, unificada sob um framework de controle de fidelidade.

1. Estratégia de Duas Fases

• Fase 1: Geração Ativa de Aprendizes (Compressão): Em vez de começar com um conjunto fixo de aprendizes, o PACE gera ativamente novos aprendizes para enriquecer o ensemble inicial. Esta fase utiliza técnicas de Geração de Colunas. O objetivo é encontrar "aprendizes melhoradores" que reduzam o valor ótimo de um problema de poda relaxado (usando um substituto de norma $\ell_1$).
  • O processo identifica aprendizes $h$ que melhoram o potencial para esparsificação a jusante.
  • Um problema de precificação é resolvido para detectar se existe algum novo aprendiz que possa melhorar estritamente a relaxação. Se nenhum tal aprendiz existir ($L(h) = \emptyset$), a fase de geração termina, garantindo que o ensemble enriquecido contenha todos os aprendizes necessários para alcançar o melhor valor de relaxação possível.
• Fase 2: Poda: Uma vez que o ensemble é enriquecido, o PACE resolve o problema original de poda (minimizando a norma $\ell_0$ dos pesos) neste conjunto aumentado. Isso permite a seleção de um subconjunto esparsos de pesos de um grupo maior e mais diversificado de aprendizes, frequentemente resultando em um ensemble final menor do que podar apenas o conjunto original.

2. Gerenciamento de Fidelidade

O PACE introduz uma definição matizada de fidelidade que vai além de impor acordo exato sobre todo o espaço de amostras ou um conjunto empírico fixo. Ele impõe fidelidade apenas sobre uma região de interesse prático, $X_\eta \cap X_\delta$, definida por dois parâmetros:

• Região de Confiança ($X_\eta$): Amostras onde o ensemble original prevê com uma margem de confiança $\eta$ maior que as classes alternativas. Isso evita impor fidelidade em regiões de baixa confiança onde a escolha do modelo original pode ser arbitrária.
• Região de Plausibilidade ($X_\delta$): Amostras com uma pontuação de plausibilidade $\ge \delta$ em relação à distribuição de dados, calculada via uma Floresta de Isolamento. Isso exclui outliers e amostras fora da distribuição onde preservar a previsão original é de relevância prática limitada.

Para impor isso, o PACE emprega Programação por Restrições (CP) para buscar iterativamente "amostras separadoras" (amostras onde o modelo atual discorda do original). Se uma amostra separadora for encontrada dentro da região definida, ela é adicionada ao conjunto de restrições e os pesos são reotimizados. Este ciclo se repete até que não existam amostras separadoras na região-alvo.

Contribuições Principais

1. Framework Unificado: O artigo demonstra que poda e compressão são complementares. O PACE unifica-os enriquecendo primeiro o ensemble via geração ativa e depois podando o resultado, aproveitando os pontos fortes de ambas as abordagens.
2. Geração de Colunas para Enriquecimento: Os autores fornecem uma estratégia principiante usando geração de colunas para gerar novos aprendizes. Isso inclui um critério de parada teórico garantindo que não existam mais aprendizes melhoradores, maximizando assim o potencial para poda subsequente.
3. Fidelidade Flexível: O artigo estende a noção de fidelidade para visar apenas regiões significativas (alta confiança e alta plausibilidade). Essa troca permite compressão mais forte do que a imposição de fidelidade exata, evitando ao mesmo tempo as armadilhas de aproximações arbitrárias.
4. Separação Baseada em Restrições: O PACE utiliza uma formulação baseada em restrições para encontrar amostras separadoras, que os autores mostram ser computacionalmente superior às formulações baseadas em objetivos usadas em trabalhos anteriores.

Resultados Experimentais

Os autores avaliaram o PACE em vários conjuntos de dados (por exemplo, COMPAS, FICO, Diabetes, Ionosphere) usando ensembles de Floresta Aleatória e AdaBoost.

• Desempenho de Compressão: O PACE supera consistentemente métodos anteriores de apenas poda (como FIPE) e variantes ablatadas (apenas geração ou apenas poda). Em muitos casos, o ensemble final consiste quase inteiramente de aprendizes recém-gerados em vez dos originais.
• Controle de Fidelidade: Relaxar a fidelidade via parâmetros $\eta$ e $\delta$ reduz significativamente o tamanho final do ensemble. Por exemplo, no conjunto de dados FICO, aumentar $\eta$ reduziu o ensemble de 58 árvores para 3, uma redução não alcançável com fidelidade estrita.
• Eficiência Computacional: A abordagem de separação baseada em restrições usada no PACE alcança acelerações substanciais (até 37$\times$ em configurações específicas de Floresta Aleatória) em comparação com a separação baseada em objetivos usada em métodos de última geração como o FIPE.
• Estudos de Ablação: Experimentos confirmam que nem geração nem poda sozinhos correspondem ao desempenho do framework completo PACE, validando a necessidade da abordagem de duas fases.

Significado e Alegações

O artigo afirma que o PACE oferece uma abordagem principiante e flexível para compressão de ensemble. Seu significado principal reside em:

• Compressão Superior: Alcançar tamanhos de ensemble menores do que métodos existentes, mantendo fidelidade preditiva em regiões relevantes.
• Garantias Teóricas: Fornecer garantias rigorosas sobre fidelidade dentro de regiões específicas definidas pelo usuário, em vez de depender de aproximações heurísticas.
• Avanços Computacionais: Demonstrar que a programação por restrições é uma ferramenta altamente eficiente para o problema de separação inerente à poda de ensemble, superando abordagens tradicionais de programação linear inteira mista (MILP) neste contexto.

Os autores reconhecem limitações, observando que o PACE tem um custo computacional mais alto do que métodos de apenas poda devido à natureza combinatória da norma $\ell_0$ e à fase de geração. Eles também notam a restrição atual a aprendizes baseados em árvores, embora o framework seja teoricamente extensível a outras famílias se modelos matemáticos apropriados puderem ser estabelecidos. Sugere-se trabalho futuro na otimização do problema de precificação para geração de aprendizes e no refinamento de métricas de complexidade além de contagens simples de aprendizes.