EPR-C3: A Deterministic Constraint-Aware Heuristic for High-Dimensional Subset Selection in Multiple Linear Regression

Resumen Técnico: EPR-C3 para la Selección de Subconjuntos de Alta Dimensionalidad en Regresión Lineal Múltiple

Planteamiento del Problema
La selección de subconjuntos de características en la Regresión Lineal Múltiple (MLR) presenta un desafío dual en regímenes de datos de alta dimensionalidad: una explosión combinatoria de posibles subconjuntos de predictores y el riesgo de generar modelos estadísticamente inadmisibles debido a la multicolinealidad, el sobreajuste o la insignificancia de los coeficientes. Si bien la regresión exhaustiva de "todos los subconjuntos" garantiza la identificación del modelo globalmente óptimo bajo un criterio elegido, su costo computacional crece exponencialmente con el número de predictores ($d$) y el tamaño máximo del modelo ($w$), lo que la hace inviable para valores grandes de $d$. Por el contrario, las alternativas existentes —como los procedimientos paso a paso (stepwise) codiciosos, la regresión penalizada (Lasso, Ridge, Elastic Net), el cribado de filtro-envolvente y las metaheurísticas estocásticas (por ejemplo, Algoritmos Genéticos)— suelen sufrir limitaciones que incluyen el atrapamiento en óptimos locales, la sensibilidad a las decisiones tempranas, la modificación del objetivo de Mínimos Cuadrados Ordinarios (OLS) o la falta de reproducibilidad. Existe una necesidad práctica de un método que opere dentro del marco nativo de OLS, que imponga restricciones estadísticas y de multicolinealidad directamente durante la búsqueda y que sea computacionalmente tratable en entornos de alta dimensionalidad sin depender de la enumeración exhaustiva.

Metodología: El Algoritmo EPR-C3
El artículo presenta EPR-C3, una heurística de búsqueda de vecindad, determinista y de inicio múltiple, diseñada para la selección de subconjuntos consciente de las restricciones en la MLR basada en OLS. El algoritmo no modifica la función objetivo de OLS (a diferencia de la regresión penalizada) ni enumera todas las combinaciones. En su lugar, se basa en una trayectoria de búsqueda estructurada definida por cuatro componentes principales:

1. Inicialización de Inicio Múltiple (Multi-Start): La búsqueda comienza desde múltiples subconjuntos de predictores pequeños (semillas). Aunque la generación de semillas puede ser aleatorizada, la trayectoria subsiguiente es totalmente determinista dado un listado de semillas fijo y un estado aleatorio, lo que garantiza la reproducibilidad.
2. Operadores de Vecindad: Cada trayectoria itera a través de una secuencia de modificaciones locales:
   • Expandir (Expand): Añade el predictor inactivo que produzca la mayor mejora en la métrica objetivo (por ejemplo, $R^2$), sujeto a límites de tamaño del modelo.
   • Perturbar (Perturb): Realiza intercambios de uno por uno entre predictores activos e inactivos para escapar de los óptimos locales.
   • Reducir (Reduce): Prueba eliminaciones de una sola variable, aceptándolas si mantienen o mejoran la puntuación objetivo, favoreciendo así la parsimonia.
3. Refinamiento C3 Consciente de las Restricciones: Una característica única del algoritmo es la integración de las restricciones de admisibilidad directamente en el flujo de trabajo de la búsqueda en lugar de como filtros post-hoc. Este bloque comprende:
   • Limpieza de Correlación (Correlation Cleanup): Identifica pares de predictores activos que exceden un umbral de correlación definido por el usuario ($\tau_r$) y elimina el que resulte en una mejor puntuación de cribado de la métrica objetivo.
   • Recuperación por Reemplazo (Replacement Recovery): Reevalúa los predictores eliminados durante la limpieza de correlación para probar si los movimientos de reemplazo cribados pueden recuperar o mejorar la puntuación objetivo.
   • Poda de VIF (VIF Pruning): Elimina iterativamente los predictores con Factores de Inflación de la Varianza (VIF) elevados que exceden un umbral ($\tau_{VIF}$) si su exclusión mejora la puntuación cribada.
4. Filtrado de Admisibilidad: Los modelos candidatos se evalúan utilizando la estimación estándar de OLS. Un subconjunto se almacena como un modelo "reportable" solo si satisface un conjunto estricto de restricciones: tamaño máximo del modelo ($w$), umbral de la métrica objetivo ($\tau_f$), límites de correlación por pares ($\tau_r$), límites de VIF ($\tau_{VIF}$) y niveles de significancia de los coeficientes ($\alpha$).

Contribuciones Clave
El artículo describe seis contribuciones primarias:

1. Formulación Algorítmica: La introducción de EPR-C3 como una heurística de inicio múltiple y determinista que incorpora restricciones de admisibilidad estadística (correlación, VIF, significancia) directamente en la búsqueda de vecindad.
2. Operadores de Búsqueda Explícitos: La definición de operadores específicos de expansión, perturbación, reducción y refinamiento C3 dentro de un marco de selección de subconjuntos de OLS.
3. Evaluación frente a la Búsqueda Exhaustiva: Una evaluación de la capacidad de EPR-C3 para recuperar los subconjuntos mejor clasificados identificados por la regresión de todos los subconjuntos ante diversos niveles de complejidad combinatoria ($d$ y $w$).
4. Análisis Comparativo: Una demostración de que EPR-C3 logra un equilibrio superior entre recuperación y eficiencia en comparación con los procedimientos paso a paso, la preselección por regresión penalizada, el cribado de filtro-envolvente y los métodos de rama y bóveda (Leaps).
5. Umbral de Utilidad Empírica: La propuesta de un umbral empírico ($U$) para guiar a los analistas sobre cuándo la búsqueda heurística es computacionalmente preferible a la enumeración exhaustiva. El umbral se aproxima mediante $U = (8.2w - 31) \times 10^6$ para $w \geq 4$, que representa el número de subconjuntos candidatos por encima del cual EPR-C3 supera a la búsqueda exhaustiva en tiempo de CPU.
6. Validación Aplicada: Un estudio de caso sobre un conjunto de datos de modelado de pKa que demuestra la recuperación reproducible de una ecuación de MLR conocida con un tiempo de ejecución reducido en comparación con el enfoque exhaustivo original.

Resultados

• Desempeño de Recuperación: En escenarios de referencia con recuentos de predictores de hasta $d=60$ y tamaños de modelo de hasta $w=10$ (espacios de búsqueda que superan $2.8 \times 10^8$ subconjuntos), EPR-C3 con 1,000 semillas recuperó más del 95% de los 100 subconjuntos de referencia mejor clasificados identificados por la regresión exhaustiva de todos los subconjos.
• Eficiencia Computacional: EPR-C3 resulta computacionalmente ventajoso sobre la enumeración exhaustiva cuando el número de subconjuntos candidatos supera el umbral de utilidad empírica. Por ejemplo, con $d=35$ y $w=10$, EPR-C3 fue aproximadamente 12.7 veces más rápido que la búsqueda exhaustiva manteniendo altas tasas de recuperación.
• Superioridad Comparativa:
  • Métodos Paso a Paso/Filtro: El método forward stepwise y el cribado de filtro-envolvente (CSR-AS) no lograron recuperar ninguno de los 100 subconjuntos de referencia, resaltando las limitaciones de los enfoques codiciosos o de cribado marginal.
  • Regresión Penalizada: Métodos como Lasso, Ridge y Elastic Net proporcionaron una recuperación modesta (10–23%) pero requirieron una carga computacional significativa para la preselección y el posterior reajuste de OLS.
  • Estocásticos/Rama y Bóveda: Aunque los Algoritmos Genéticos y el algoritmo Leaps (rama y bóveda) lograron una mayor recuperación (65–68%), estos eran o bien computacionalmente costosos (Algoritmos Genéticos) o sufrían de "pérdida de admisibilidad post-hoc" (Leaps), donde los subconjuntos de alto rango eran descartados después de la búsqueda porque violaban restricciones no aplicadas durante la búsqueda. EPR-C3 logró la mayor recuperación (95%) con un tiempo de CPU relativo menor que tanto el Algoritmo Genético como Leaps.
• Estudio de Caso: En el conjunto de datos de pKa ($d=53$), EPR-C3 recuperó el conjunto de predictores y la ecuación publicados exactamente en aproximadamente 2.5 veces menos tiempo que la regresión de todos los subconjuntos utilizada en el estudio original.

Significado y Reivindicaciones
El artículo posiciona a EPR-C3 no como un reemplazo de la enumeración exhaustiva cuando esta es factible, sino como una alternativa determinista necesaria para regímenes de alta dimensionalidad donde la búsqueda exhaustiva es computacionalmente prohibitiva. Su importancia radica en cerrar la brecha entre la interpretabilidad y el rigor estadístico de OLS y la viabilidad computacional requerida para datos de alta dimensionalidad.

Al integrar decisiones conscientes de las restricciones (limpieza de correlación, poda de VIF, filtrado de significancia) directamente en la trayectoria de búsqueda, EPR-C3 evita la "pérdida de admisibilidad post-hoc" común en los métodos de rama y bóveda o estocásticos. Los autores afirman que este enfoque permite la recuperación de modelos de MLR interpretables, estadísticamente defendibles y reproducibles sin la carga combinatoria total de la enumeración exhaustiva. El método se presenta como una herramienta práctica para flujos de trabajo de ciencia de datos donde la transparencia del modelo y el cumplimiento de los supuestos estadísticos son tan críticos como el rendimiento predictivo. El artículo mantiene la modestia, reconociendo que EPR-C3 es una heurística cuyos beneficios de recuperación se validan solo dentro de regímenes donde la búsqueda exhaustiva aún es computacionalmente factible, y que se podrían requerir presupuestos de semillas más grandes para espacios combinatorios aún más extremos.