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

Resumo Técnico: EPR-C3 para Seleção de Subconjuntos de Alta Dimensionalidade em Regressão Linear Múltipla

Declaração do Problema
A seleção de subconjuntos de características em Regressão Linear Múltipla (MLR) apresenta um desafio duplo em regimes de dados de alta dimensionalidade: uma explosão combinatória de possíveis subconjuntos de preditores e o risco de gerar modelos estatisticamente inadmissíveis devido à multicolinearidade, sobreajuste (overfitting) ou insignificância dos coeficientes. Embora a regressão exaustiva de "todos os subconjuntos" garanta a identificação do modelo globalmente ótimo sob um critério escolhido, seu custo computacional cresce exponencialmente com o número de preditores ($d$) e o tamanho máximo do modelo ($w$), tornando-a inviável para grandes valores de $d$. Por outro lado, as alternativas existentes — como procedimentos de passo a passo (stepwise) gananciosos, regressão penalizada (Lasso, Ridge, Elastic Net), triagem de filtro-envelope (filter-wrapper) e metaheurísticas estocásticas (ex: Algoritmos Genéticos) — frequentemente sofrem de limitações que incluem o aprisionamento em ótimos locais, sensibilidade a decisões precoces, modificação do objetivo de Mínimos Quadrados Ordinários (OLS) ou falta de reprodutibilidade. Há uma necessidade prática de um método que opere dentro do arcabouço nativo de OLS, imponha restrições estatísticas e de multicolinearidade diretamente durante a busca e permaneça computacionalmente tratável em cenários de alta dimensionalidade sem depender de enumeração exaustiva.

Metodologia: O Algoritmo EPR-C3
O artigo introduz o EPR-C3, uma heurística de busca de vizinhança, determinística e de múltiplas inicializações (multi-start), projetada para a seleção de subconjuntos consciente de restrições em MLR baseada em OLS. O algoritmo não modifica a função objetivo de OLS (ao contrário da regressão penalizada) nem enumera todas as combinações. Em vez disso, ele se baseia em uma trajetória de busca estruturada definida por quatro componentes principais:

1. Inicialização de Múltiplas Inicializações (Multi-Start): A busca começa a partir de vários pequenos subconjuntos de preditores (sementes). Embora a geração das sementes possa ser aleatória, a trajetória subsequente é totalmente determinística dado um conjunto de sementes fixo e um estado aleatório, garantindo a reprodutibilidade.
2. Operadores de Vizinhança: Cada trajetória percorre uma sequência de modificações locais:
   • Expandir (Expand): Adiciona o preditor inativo que gera o maior melhoria na métrica alvo (ex: $R^2$), sujeito a limites de tamanho de modelo.
   • Perturbar (Perturb): Realiza trocas de um-por-um entre preditores ativos e inativos para escapar de ótimos locais.
   • Reduzir (Reduce): Testa remoções de uma variável, aceitando-as se mantiverem ou melhorarem a pontuação alvo, favorecendo assim a parcimônia.
3. Refinamento C3 Consciente de Restrições: Um recurso único do algoritmo é a integração de restrições de admissibilidade diretamente no fluxo de trabalho da busca, em vez de filtros post-hoc. Este bloco compreende:
   • Limpeza de Correlação (Correlation Cleanup): Identifica pares de preditores ativos que excedem um limiar de correlação definido pelo usuário ($\tau_r$) e remove aquele que resulta em uma melhor pontuação de triagem alvo.
   • Recuperação de Substituição (Replacement Recovery): Reavalia preditores removidos durante a limpeza de correlação para testar se movimentos de substituição triados podem recuperar ou melhorar a pontuação alvo.
   • Poda de VIF (VIF Pruning): Remove iterativamente preditores com Fatores de Inflação de Variância (VIF) elevados que excedem um limiar ($\tau_{VIF}$), caso sua exclusão melhore a pontuação triada.
4. Filtragem de Admissibilidade: Candidatos a modelos são avaliados usando estimativa OLS padrão. Um subconjunto é armazenado como um modelo "reportável" apenas se satisfizer um conjunto rigoroso de restrições: tamanho máximo do modelo ($w$), limiar da métrica alvo ($\tau_f$), limites de correlação pareada ($\tau_r$), limites de VIF ($\tau_{VIF}$) e níveis de significância dos coeficientes ($\alpha$).

Principais Contribuições
O artigo delineia seis contribuições primárias:

1. Formulação Algorítmica: A introdução do EPR-C3 como uma heurística determinística de múltiplas inicializações que incorpora restrições de admissibilidade estatística (correlação, VIF, significância) diretamente na busca de vizinhança.
2. Operadores de Busca Explícitos: A definição de operadores específicos de expansão, perturbação, redução e refinamento C3 dentro de um arcabouço de seleção de subconjuntos OLS.
3. Benchmarking Contra Busca Exaustiva: Uma avaliação da capacidade do EPR-C3 de recuperar os subconjuntos de classificação superior identificados pela regressão de todos os subconjuntos em níveis variados de complexidade combinatória ($d$ e $w$).
4. Análise Comparativa: Uma demonstração de que o EPR-C3 alcança um equilíbrio superior entre eficiência de recuperação e custo computacional em comparação com procedimentos de passo a passo, pré-seleção de regressão penalizada, triagem de filtro-envelope e algoritmos genéticos.
5. Limiar de Utilidade Empírica: A proposta de um limiar empírico ($U$) para orientar analistas sobre quando a busca heurística torna-se computacionalmente preferível à enumeração exaustiva. O limiar é aproximado por $U = (8.2w - 31) \times 10^6$ para $w \geq 4$, representando o número de subconjuntos candidatos acima do qual o EPR-C3 supera a busca exaustiva em tempo de CPU.
6. Validação Aplicada: Um estudo de caso em um conjunto de dados de modelagem de pKa demonstrando a recuperação reprodutível de uma equação de MLR conhecida com tempo de execução reduzido em relação à abordagem exaustiva original.

Resultos

• Desempenho de Recuperação: Em cenários de teste com contagens de preditores até $d=60$ e tamanhos de modelo até $w=10$ (espaços de busca excedendo $2.8 \times 10^8$ subconjuntos), o EPR-C3 com 1.000 sementes recuperou mais de 95% dos 100 subconjuntos de referência de classificação superior identificados pela regressão exaustiva de todos os subconjetos.
• Eficiência Computacional: O EPR-C3 torna-se computacionalmente vantajoso sobre a enumeração exaustiva quando o número de subconjuntos candidatos excede o limiar de utilidade empírica. Por exemplo, em $d=35$ e $w=10$, o EPR-C3 foi aproximadamente 12,7 vezes mais rápido que a busca exaustiva, mantendo altas taxas de recuperação.
• Superioridade Comparativa:
  • Métodos de Passo a Passo/Filtro: O método de passo a passo para frente (forward stepwise) e a triagem de filtro-envelope (CSR-AS) falharam em recuperar qualquer um dos 100 subconjuntos de referência, destacando as limitações de abordagens gananciosas ou de triagem marginal.
  • Regressão Penalizada: Métodos como Lasso, Ridge e Elastic Net forneceram uma recuperação modesta (10–23%), mas exigiram um alto custo computacional para pré-seleção e subsequente reajuste de OLS.
  • Estocásticos/Branch-and-Bound: Embora os Algoritmos Genéticos e o algoritmo Leaps (branch-and-bound) tenham alcançado uma recuperação maior (65–68%), eles foram ou computacionalmente caros (Algoritmos Genéticos) ou sofreram de "perda de admissibilidade post-hoc" (Leaps), onde subconjuntos de alta classificação foram descartados após a busca porque violaram restrições não impostas durante a busca. O EPR-C3 alcançou a maior recuperação (95%) com um tempo de CPU relativo menor do que tanto o Algoritmo Genético quanto o Leaps.
• Estudo de Caso: No conjunto de dados de pKa ($d=53$), o EPR-C3 recuperou o conjunto de preditores e a equação publicados exatamente em aproximadamente 2,5 vezes menos tempo do que a regressão de todos os subconjuntos usada no estudo original.

Significância e Alegações
O artigo posiciona o EPR-C3 não como um substituto para a enumeração exaustiva quando esta é viável, mas como uma alternativa determinística necessária para regimes de alta dimensionalidade onde a busca exaustiva é computacionalmente proibitiva. Sua significância reside em preencher a lacuna entre a interpretabilidade e o rigor estatístico do OLS e a viabilidade computacional exigida por dados de alta dimensionalidade.

Ao incorporar decisões conscientes de restrições (limpeza de correlação, poda de VIF, filtragem de significância) diretamente na trajetória de busca, o EPR-C3 evita a "perda de admissibilidade post-hoc" comum em métodos de branch-and-bound ou estocásticos. Os autores alegam que essa abordagem permite a recuperação de modelos de MLR estatisticamente defensáveis, interpretáveis e reprodutíveis sem o ônus combinatório total da enumeração exaustiva. O método é apresentado como uma ferramenta prática para fluxos de trabalho de ciência de dados onde a transparência do modelo e a adesão aos pressupostos estatísticos são tão críticas quanto o desempenho preditivo. O artigo permanece modesto, reconhecendo que o EPR-C3 é uma heurística cujas garantias de recuperação são validadas apenas dentro de regimes onde a busca exaustiva ainda é computacionalmente viável, e que orçamentos de sementes maiores podem ser necessários para espaços combinatórios ainda mais extremos.