Optimized Sequential Testing for Binary Ensemble Classifiers

Planteamiento del Problema
Los clasificadores de ensamble, como los bosques aleatorios (random forests), combinan las predicciones de múltiples modelos base (por ejemplo, árboles de decisión) mediante el voto de la mayoría para lograr una alta precisión. Sin embargo, los ensambles más grandes incurren en costos computacionales significativos durante la inferencia, lo cual es problemático para dispositivos de baja potencia o aplicaciones de alta frecuencia. El problema central abordado es cómo reducir el costo computacional de tiempo de prueba de los clasificadores de ensamble binarios sin degradar significativamente su precisión. Específicamente, los autores investigan estrategias para detener la evaluación de los modelos base secuencialmente una vez que emerge una "mayoría clara", en lugar de ejecutar los $N$ modelos. El objetivo es minimizar el número esperado de modelos base ejecutados (tiempo de ejecución) mientras se controla estrictamente la "tasa de desacuerdo" —la probabilidad de que el ensamble con parada temprana arroje un resultado diferente al del ensamble completo.

Metodología
El artículo formaliza el problema de la parada temprana como una tarea de prueba secuencial donde el estado se define por $(i, j)$, representando $i$ modelos base ejecutados y $j$ votos positivos. Los autores asumen que los modelos base se ejecutan en un orden aleatorio, lo que permite el uso de una distribución hipergeométrica para modelar la probabilidad de alcanzar cualquier estado, sin asumir independencia entre los modelos base.

Para encontrar estrategias de parada óptimas, los autores proponen tres marcos de optimización distintos, todos formulados como programas lineales (LP) para asegurar la eficiencia computacional:

1. Minimax: Minimiza el peor de los casos del tiempo de ejecución esperado sujeto a una restricción de tasa de desacuerdo en el peor de los casos. Este enfoque no requiere conocimiento previo de la distribución de los votos positivos ($n$).
2. Minimean: Minimiza el tiempo de ejecución esperado sujeto a una restricción de tasa de desacuerdo esperada, asumiendo una distribución conocida o estimada $\hat{D}$ para $n$.
3. Minimixed: Minimiza el tiempo de ejecución esperado sujeto a una tasa de desacuerdo en el peor de los casos, asumiendo una distribución para $n$.

Los autores demuestran que los problemas de optimización no lineales originales pueden reformularse utilizando variables de decisión de probabilidad condicional ($p_{ij}, \pi_{ij}, \bar{\pi}_{ij}$). Esta reformulación transforma el problema en un programa lineal con $O(N^3)$ variables de decisión, resoluble eficientemente incluso para ensambles con cientos de árboles. Las estrategias resultantes son mayoritariamente deterministas, siguiendo una regla de "sobre" (envelope) simple: detener si el número de votos positivos supera un umbral superior o cae por debajo de un umbral inferior en un paso $i$ específico.

Contribuciones Clave

• Formulación Teórica: El artículo proporciona un marco matemático riguroso para la parada temprana en ensambles de voto de mayoría, definiendo formalmente las estrategias de parada y las métricas (tiempo de ejecución y tasa de desacuerdo).
• Soluciones Óptimas de Programación Lineal: Los autores muestran que las estrategias de parada óptimas para tres nociones distintas de optimalidad (minimax, minimean, minimixed) pueden encontrarse resolviendo programas lineales. Esto contrasta con trabajos previos que a menudo dependían de heurísticas o asumían independencia entre los modelos base.
• Sin Suposición de Independencia: A diferencia de otros métodos de prueba secuencial para ensambles (por ejemplo, Schwing et al., 2011), este enfoque no asume que los modelos base sean independientes, lo que lo hace directamente aplicable a los bosques aleatorios donde las predicciones de los árboles están correlacionadas.
• Estrategias Precomputables: Los autores precomputaron estrategias óptimas para varios tamaños de ensamble y tasas de desacuerdo permitidas (ADR), lo que permite su aplicación inmediata sin necesidad de reoptimización para cada nuevo conjunto de datos (particularmente para el enfoque minimax).

Resultados Empíricos
Los métodos fueron evaluados en 27 conjuntos de datos del mundo real del repositorio UCI Machine Learning Repository y en benchmarks propuestos por Grinsztajn et al., utilizando bosques aleatorios con $N=101$ árboles.

• Aceleración (Speed-up): En la mayoría de los conjuntos de datos, los métodos propuestos lograron aceleraciones de 4 veces o más (reduciendo el tiempo de ejecución al 10–20% del ensamble completo) manteniendo una tasa de desacuerdo de 0.1% ($10^{-3}$).
• Varianza del Desempeño: El enfoque Minimean (usando un conjunto de calibración para estimar la distribución de votos) generalmente ofreció las mayores aceleraciones, seguido de Minimixed, siendo Minimax el más conservador.
• Características del Conjunto de Datos: La efectividad de la parada temprana se correlacionó con la distribución de los votos de los árboles. Los conjuntos de datos donde los árboles votaron abrumadoramente por una clase (distribución bimodal) permitieron una parada temprana agresiva. Por el contrario, los conjuntos de datos con altas tasas de error base y distribuciones de votos centralizadas (por ejemplo, "Dota2" y "Hospitalization") mostraron aceleraciones menores, ya que el consenso era más difícil de alcanzar tempranamente.
• Comparación: Los métodos propuestos superaron al método base de Schwing et al. (2011), el cual depende de bandas de confianza binomiales y supuestos de independencia.

Significancia y Reivindicaciones
El artículo afirma presentar el primer método para lograr estrategias de parada temprana probablemente óptimas para clasificadores de ensamble de clasificación binaria basados en voto de mayoría sin asumir independencia entre los modelos base. Los autores enfatizan que su enfoque permite entrenar ensambles más grandes y precisos, y confiar en la estrategia de parada para utilizar solo los recursos computacionales necesarios para cada inferencia específica.

El artículo señala modestamente sus limitaciones: el método está restringido a la clasificación binaria y a ensambles de voto de mayoría no ponderados. No puede aplicarse directamente a problemas de clasificación múltiple, regresión o ensambles donde los modelos base tengan pesos específicos u órdenes de ejecución requeridos. Además, los autores sugieren que, aunque el método es compatible con la poda (pruning), las ganancias podrían ser menos dramáticas para bosques podados, ya que la poda busca reducir la redundancia (votos correlacionados) que hace efectiva la parada temprana. Se sugiere como trabajo futuro la extensión de la teoría a la clasificación múltiple y ensambles ponderados.