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

Sintesi Tecnica: EPR-C3 per la Selezione di Sottogruppi ad Alta Dimensionalità nella Regressione Lineare Multipla

Definizione del Problema
La selezione del sottogruppo di caratteristiche nella Regressione Lineare Multipla (MLR) presenta una doppia sfida nei regimi di dati ad alta dimensionalità: un'esplosione combinatoria di possibili sottogruppi di predittori e il rischio di generare modelli statisticamente inadmissibili a causa di multicollinearità, overfitting o insignificanza dei coefficienti. Sebbene la regressione esaustiva "all-subsets" garantisca l'identificazione del modello globalmente ottimale secondo un criterio scelto, il suo costo computazionale cresce esponenzialmente con il numero di predittori ($d$) e la dimensione massima del modello ($w$), rendendola impraticabile per grandi valori di $d$. Al contrario, le alternative esistenti — come le procedure stepwise greedy, la regressione penalizzata (Lasso, Ridge, Elastic Net), lo screening filter-wrapper e le meta-euristiche stocastiche (ad esempio, gli Algoritmi Genetici) — soffrono spesso di limitazioni che includono l'intrappolamento in ottimi locali, la sensibilità alle decisioni precoci, la modifica della funzione obiettivo dei Minimi Quadrati Ordinari (OLS) o una mancanza di riproducibilità. Esiste una necessità pratica di un metodo che operi all'interno del framework nativo OLS, che imponga vincoli statistici e di multicollinearità direttamente durante la ricerca e che rimanga computazionalmente trattabile in contesti ad alta dimensionalità senza fare affidamento sull'enumerazione esaustiva.

Metodologia: L'Algoritmo EPR-C3
Il documento introduce EPR-C3, un'euristica deterministica di ricerca nel vicinato con multi-start, progettata per la selezione di sottogruppi consapevole dei vincoli in MLR basata su OLS. L'algoritmo non modifica la funzione obiettivo OLS (a differenza della regressione penalizzata) né enumera tutte le combinazioni. Si affida invece a una traiettoria di ricerca strutturata definita da quattro componenti principali:

1. Inizializzazione Multi-Start: La ricerca inizia da molteplici piccoli sottogruppi di predittori (semi). Sebbene la generazione dei semi possa essere randomizzata, la successiva traiettoria è interamente deterministica dato un elenco di semi fisso e uno stato casuale, garantendo la riproducibilità.
2. Operatori di Vicinato: Ogni traiettoria itera attraverso una sequenza di modifiche locali:
   • Expand (Espansione): Aggiunge il predittore inattivo che produce il maggior miglioramento nella metrica target (ad esempio, $R^2$), soggetto a limiti di dimensione del modello.
   • Perturb (Perturbazione): Esegue scambi uno-a-uno tra predittori attivi e inattivi per sfuggire agli ottimi locali.
   • Reduce (Riduzione): Testa le rimozioni di singole variabili, accettandole se mantengono o migliorano il punteggio target, favorendo così la parsimonia.
3. Raffinamento C3 Consapevole dei Vincoli: Una caratteristica unica dell'algoritmo è l'integrazione dei vincoli di ammissibilità direttamente nel flusso di lavoro della ricerca piuttosto che come filtri post-hoc. Questo blocco comprende:
   • Correlation Cleanup (Pulizia della Correlazione): Identifica coppie di predittori attivi che superano una soglia di correlazione definita dall'utente ($\tau_r$) e rimuove quella che risulta in un punteggio target schermato migliore.
   • Replacement Recovery (Recupero della Sostituzione): Rivaluta i predittori rimossi durante la pulizia della correlazione per testare se le mosse di sostituzione schermate possano recuperare o migliorare il punteggio target.
   • VIF Pruning (Potatura VIF): Rimuove iterativamente i predittori con Fattori di Inflazione della Varianza (VIF) elevati che superano una soglia ($\tau_{VIF}$), qualora la loro esclusione migliori il punteggio schermato.
4. Filtraggio di Ammissibilità: I modelli candidati sono valutati utilizzando la stima standard OLS. Un sottogruppo è memorizzato come modello "riportabile" solo se soddisfa un insieme rigoroso di vincoli: dimensione massima del modello ($w$), soglia della metrica target ($\tau_f$), limiti di correlazione a coppie ($\tau_r$), limiti VIF ($\tau_{VIF}$) e livelli di significatività dei coefficienti ($\alpha$).

Contributi Chiave
Il documento delinea sei contributi primari:

1. Formulazione Algoritmica: L'introduzione di EPR-C3 come euristica deterministica multi-start che incorpora vincoli di ammissibilità statistica (correlazione, VIF, significatività) direttamente nella ricerca nel vicinato.
2. Operatori di Ricerca Espliciti: La definizione di specifici operatori di espansione, perturbazione, riduzione e raffinamento C3 all'interno di un framework di selezione di sottogruppi OLS.
3. Benchmarking rispetto alla Ricerca Esaustiva: Una valutazione della capacità di EPR-C3 di recuperare i sottogruppi con il ranking più alto identificati dalla regressione all-subsets su diversi livelli di complessità combinatoria ($d$ e $w$).
4. Analisi Comparativa: Una dimostrazione che EPR-C3 raggiunge un rapporto di efficienza di recupero superiore rispetto alle procedure stepwise, alla preselezione tramite regressione penalizzata, allo screening filter-wrapper e agli algoritmi genetici e ai metodi branch-and-bound (Leaps).
5. Soglia di Utilità Empirica: La proposta di una soglia empirica ($U$) per guidare gli analisti su quando la ricerca euristica diventa preferibile alla enumerazione esaustiva. La soglia è approssimata da $U = (8.2w - 31) \times 10^6$ per $w \geq 4$, rappresentando il numero di sottogruppi candidati sopra il quale EPR-C3 supera la ricerca esaustiva in termini di tempo di CPU.
6. Validazione Applicata: Un caso di studio su un dataset pubblico di modellazione pKa che dimostra il recupero riproducibile di un'equazione MLR nota con un tempo di esecuzione ridotto rispetto all'approccio esaustivo originale.

Risultati

• Performance di Recupero: In scenari di benchmark con conteggi di predittori fino a $d=60$ e dimensioni del modello fino a $w=10$ (spazi di ricerca superiori a $2.8 \times 10^8$ sottogruppi), EPR-C3 con 1.000 semi ha recuperato oltre il 95% dei primi 100 sottogruppi di riferimento identificati dalla regressione esaustiva all-subsets.
• Efficienza Computazionale: EPR-C3 diventa computazionalmente vantaggioso rispetto all'enumerazione esaustiva quando il numero di sottogruppi candidati supera la soglia di utilità empirica. Ad esempio, a $d=35$ e $w=10$, EPR-C3 è stato circa 12,7 volte più veloce della ricerca esaustiva mantenendo alti tassi di recupero.
• Superiorità Comparativa:
  • Metodi Stepwise/Filter: Il metodo forward stepwise e lo screening filter-wrapper (CSR-AS) non sono riusciti a recuperare alcuno dei primi 100 sottogruppi di riferimento, evidenziando i limiti degli approcci greedy o di screening marginale.
  • Regressione Penalizzata: Metodi come Lasso, Ridge ed Elastic Net hanno fornito un recupero modesto (10–23%) ma hanno richiesto un carico computazionale significativo per la preselezione e la successiva rinfestazione OLS.
  • Stocastici/Branch-and-Bound: Mentre gli Algoritmi Genetici e l'algoritmo Leaps (branch-and-bound) hanno ottenuto un recupero superiore (65–68%), erano o computazionalmente costosi (Algoritmi Genetici) o soffrivano di "perdita di ammissibilità post-hoc" (Leaps), dove i sottogruppi con alto ranking venivano scartati dopo la ricerca perché violavano vincoli non imposti durante la ricerca stessa. EPR-C3 ha ottenuto il recupero più elevato (95%) con un tempo di CPU relativo inferiore sia rispetto all'Algoritmo Genetico che a Leaps.
• Caso di Studio: Nel dataset pKa ($d=53$), EPR-C3 ha recuperato l'esatto set di predittori e l'equazione pubblicata in circa 2,5 volte meno tempo rispetto alla regressione all-subsets utilizzata nello studio originale.

Significato e Rivendicazioni
Il documento posiziona EPR-C3 non come un sostituto dell'enumerazione esaustiva quando questa è fattibile, ma come un'alternativa deterministica necessaria nei regimi ad alta dimensionalità dove la ricerca esaustiva è computazionalmente proibitiva. La sua importanza risiede nel colmare il divario tra l'interpretabilità e il rigore statistico di OLS e la fattibilità computazionale richiesta dai dati ad alta dimensionalità.

Integrando le decisioni consapevoli dei vincoli (pulizia della correlazione, potatura VIF, filtraggio della significatività) direttamente nella traiettoria di ricerca, EPR-C3 evita la "perdita di ammissibilità post-hoc" comune nei metodi branch-and-bound o stocastici. Gli autori sostengono che questo approccio permetta di recuperare modelli MLR statisticamente difendibili, interpretabili e riproducibili senza l'intero onere combinatorio dell'enumerazione esaustiva. Il metodo è presentato come uno strumento pratico per i flussi di lavoro di data science in cui la trasparenza del modello e l'adesione alle assunzioni statistiche sono critiche quanto la performance predittiva. Il documento rimane modesto, riconoscendo che EPR-C3 è un'euristica le cui garanzie di recupero sono validate solo entro i regimi in cui la ricerca esaustiva è ancora computazionalmente fattibile, e che potrebbero essere necessari budget di semi più ampi per spazi combinatori ancora più estremi.