Optimized Sequential Testing for Binary Ensemble Classifiers

Problema
Classificadores de ensemble, como florestas aleatórias (random forests), combinam as previsões de múltiplos modelos base (por exemplo, árvores de decisão) por meio de votação majoritária para alcançar alta precisão. No entanto, ensembles maiores incorrem em custos computacionais significativos durante a inferência, o que é problemático para dispositivos de baixa potência ou aplicações de alta frequência. O problema central abordado é como reduzir o custo computacional de tempo de teste de classificadores de ensemble binários sem degradar significativamente sua precisão. Especificamente, os autores investigam estratégias para interromper a avaliação de modelos base sequencialmente assim que uma "maioria clara" emerge, em vez de executar todos os $N$ modelos. O objetivo é minimizar o número esperado de modelos base executados (tempo de execução) enquanto controla estritamente a "taxa de discordância" — a probabilidade de o ensemble com interrupção precoce produzir um resultado diferente do ensemble completo.

Metodologia
O artigo formaliza o problema da interrupção precoce (early-stopping) como uma tarefa de teste sequencial onde o estado é definido por $(i, j)$, representando $i$ modelos base executados e $j$ votos positivos. Os autores assumem que os modelos base são executados em uma ordem aleatória, permitindo o uso de uma distribuição hipergeométrica para modelar a probabilidade de atingir qualquer estado, sem assumir independência entre os modelos base.

Para encontrar estratégias de interrupção ideais, os autores propõem três estruturas de otimização distintas, todas formuladas como programas lineares (LPs) para garantir eficiência computacional:

1. Minimax: Minimiza o pior caso do tempo de execução esperado sujeito a uma restrição de taxa de discordância de pior caso. Esta abordagem não requer conhecimento prévio da distribuição de votos positivos ($n$).
2. Minimean: Minimiza o tempo de execução esperado sujeito a uma restrição de taxa de discordância esperada, assumindo uma distribuição conhecida ou estimada $\hat{D}$ para $n$.
3. Minimixed: Minimiza o tempo de execução esperado sujeito a uma taxa de discordância de pior caso, assumindo uma distribuição para $n$.

Os autores demonstram que os problemas de otimização não lineares originais podem ser reformulados usando variáveis de decisão de probabilidade condicional ($p_{ij}, \pi_{ij}, \bar{\pi}_{ij}$). Esta reformulação transforma o problema em um programa linear com $O(N^3)$ variáveis de decisão, solúvel eficientemente mesmo para ensembles com centenas de árvores. As estratégias resultantes são amplamente determinísticas, seguindo uma regra simples de "envelope": interrompa se o número de votos positivos exceder um limite superior ou cair abaixo de um limite inferior em um passo específico $i$.

Principais Contribuições

• Formulação Teórica: O artigo fornece um arcabouço matemático rigoroso para a interrupção precoce em ensembles de votação majoritária, definindo formalmente estratégias de interrupção e métricas (tempo de execução e taxa de discordância).
• Soluções de Programação Linear Ótimas: Os autores mostram que estratégias de interrupção ideais para três diferentes noções de otimalidade (minimax, minimean, minimixed) podem ser encontradas resolvendo programas lineares. Isso contrasta com trabalhos anteriores que frequentemente dependiam de heurísticas ou assumiam independência entre os modelos base.
• Sem Suposição de Independência: Ao contrário de métodos anteriores de teste sequencial para ensembles (ex: Schwing et al., 2011), esta abordagem não assume que os modelos base sejam independentes, tornando-a diretamente aplicável a florestas aleatórias onde as previsões das árvores são correlacionadas.
• Estratégias Pré-computáveis: Os autores pré-computaram estratégias ideais para vários tamanhos de ensemble e taxas de discordância permitidas (ADRs), permitindo aplicação imediata sem necessidade de reotimização para cada novo conjunto de dados (particularmente para a abordagem minimax).

Resultados Empíricos
Os métodos foram avaliados em 27 conjuntos de dados do mundo real do repositório UCI Machine Learning e benchmarks propostos por Grinsztajn et al., utilizando florestas aleatórias com $N=101$ árvores.

• Aceleração (Speed-up): Na maioria dos conjuntos de dados, os métodos propostos alcançaram acelerações de 4x ou mais (reduzindo o tempo de execução para 10–20% do ensemble completo) enquanto mantinham uma taxa de discordância de 0,1% ($10^{-3}$).
• Variância de Desempenho: A abordagem Minimean (usando um conjunto de calibração para estimar a distribuição de votos) geralmente ofereceu as maiores acelerações, seguida pela Minimixed, sendo a Minimax a mais conservadora.
• Características do Conjunto de Dados: A eficácia da interrupção precoce correlacionou-se com a distribuição dos votos das árvores. Conjuntos de dados onde as árvores votaram esmagadoramente para uma classe (distribuição bimodal) permitiram uma interrupção precoce agressiva. Por outro lado, conjuntos de dados com altas taxas de erro base e distribuições de votos centralizadas (ex: "Dota2" e "Hospitalization") mostraram acelerações menores, pois o consenso era mais difícil de ser alcançado precocemente.
• Comparação: Os métodos propostos superaram o método de linha de base de Schwing et al. (2011), que depende de bandas de confiança binomial e suposições de independência.

Significância e Alegações
O artigo afirma apresentar o primeiro método para alcançar estratégias de interrupção precoce provadamente ótimas para classificadores de ensemble de votação majoritária baseados em binários sem assumir independência entre os modelos base. Os autores enfatizam que sua abordagem permite que os usuários treinem ensembles maiores e mais precisos e dependam da estratégia de interrupção para utilizar apenas os recursos computacionais necessários para cada inferência específica.

O artigo nota modestamente suas limitações: o método é restrito à classificação binária e ensembles de votação majoritária não ponderada. Não pode ser aplicado diretamente a problemas multiclasse, regressão ou ensembles onde os modelos base possuem pesos específicos ou ordens de execução exigidas. Além disso, os autores sugerem que, embora o método seja compatível com a poda (pruning), os ganhos podem ser menos dramáticos para florestas podadas, já que a poda visa reduzir a redundância (votos correlacionados) que torna a interrupção precoce eficaz. O trabalho futuro é sugerido para estender a teoria para ensembles multiclasse e ponderados.