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

Technische Samenvatting: EPR-C3 voor Hoogdimensionele Subverzamelingselectie in Meervoudige Lineaire Regressie

Probleemstelling
De selectie van kenmerkensubverzamelingen (feature subset selection) in Meervoudige Lineaire Regressie (MLR) vormt een dubbele uitdaging in hoogdimensionele dataregimes: een combinatorische explosie van mogelijke voorspellersubverzamelingen en het risico op het genereren van statistisch niet-toelaatbare modellen door multicollineariteit, overfitting of de insignificantie van coëfficiënten. Hoewel exhaustieve "all-subsets" regressie de identificatie van de globaal optimale subset onder een gekozen criterium garandeert, is de computationele kostenstijging exponentieel met het aantal voorspellers ($d$) en de maximale modelgrootte ($w$), wat het onhaalbaar maakt voor grote $d$. Daarentegen kampen bestaande alternatieven—zoals gul (greedy) stepwise procedures, gepenaliseerde regressie (Lasso, Ridge, Elastic Net), filter-wrapper screening en stochastische metaheuristieken (bijv. Genetische Algoritmen)—vaak met beperkingen zoals het vastlopen in lokale optima, gevoeligheid voor vroege beslissingen, modificatie van de Ordinary Least Squares (OLS) doelfunctie, of een gebrek aan reproduceerbaarheid. Er is een praktische behoefte aan een methode die opereert binnen het natuurlijke OLS-kader, statistische en multicollineariteitsbeperkingen direct tijdens de zoektocht afdwingt, en computationeel hanteerbaar blijft in hoogdimensionele settings zonder te vertrouwen op exhaustieve enumeratie.

Methodologie: Het EPR-C3 Algoritme
Het artikel introduceert EPR-C3, een deterministische, multi-start, neighborhood-search heuristiek ontworpen voor beperkingsbewuste (constraint-aware) subsetselectie in OLS-gebaseerde MLR. Het algoritme modificeert de OLS-doelfunctie niet (in tegenstelling tot gepenaliseerde regressie) noch enumereert het alle combinaties. In plaats daarvan vertrouwt het op een gestructureerd zoektraject gedefinieerd door vier kerncomponenten:

1. Multi-Start Initialisatie: De zoektocht begint vanuit meerdere kleine voorspellersubverzamelingen (seeds). Hoewel de generatie van seeds gerandomiseerd kan zijn, is het daaropvolgende traject volledig deterministisch gegeven een vaste lijst met seeds en een random state, wat reproduceerbaarheid waarborgt.
2. Neighborhood Operators: Elk traject iterereert door een sequentie van lokale modificaties:
   • Expand (Uitbreiden): Voegt de inactieve voorspeller toe die de grootste verbetering oplevert in de doelmetriek (bijv. $R^2$), onderworpen aan limieten voor de modelgrootte.
   • Perturb (Verstoren): Voert één-op-één wisselingen uit tussen actieve en inactieve voorspellers om lokale optima te ontsnappen.
   • Reduce (Verminderen): Test verwijderingen van één variabele en accepteert deze als ze de doelscore handhaven of verbeteren, waardoor parsimonie (eenvoud) wordt bevorderd.
3. C3 Constraint-Aware Verfijning: Een uniek kenmerk van het algoritme is de integratie van toelaatbaarheidsbeperkingen direct in de zoekworkflow in plaats van als post-hoc filters. Dit blok bestaat uit:
   • Correlation Cleanup (Correlatie-opschoning): Identificeert paren van actieve voorspellers die een door de gebruiker gedefinieerde correlatiedrempel ($\tau_r$) overschrijden en verwijdert de een die resulteert in een betere gescreende doelscore.
   • Replacement Recovery (Vervangingherstel): Evalueert opnieuw de voorspellers die tijdens de correlatie-opschoning zijn verwijderd om te testen of gescreende vervangingsbewegingen de doelscore kunnen herstellen of verbeteren.
   • VIF Pruning (VIF-snoeien): Verwijdert iteratief voorspellers met hoge Variance Inflation Factors (VIF) die de drempelwaarde ($\tau_{VIF}$) overschrijden, indien hun uitsluiting de gescreende score verbetert.
4. Admissibility Filtering (Toelaatbaarheidsfiltering): Kandidaatmodellen worden geëvalueerd met behulp van standaard OLS-schatting. Een subset wordt opgeslagen als een "rapporteerbare" subset alleen als deze voldoet aan een strikte set beperkingen: maximale modelgrootte ($w$), doelmetriek drempelwaarde ($\tau_f$), pairwise correlatielimieten ($\tau_r$), VIF-limieten ($\tau_{VIF}$), en coëfficiënt significantieniveaus ($\alpha$).

Belangrijkste Bijdragen
Het artikel beschrijft zes primaire bijdragen:

1. Algoritmische Formulering: De introductie van EPR-C3 als een deterministische, multi-start heuristiek die statistische toelaatbaarheidsbeperkingen (correlatie, VIF, significantie) direct in de neighborhood search inbedt.
2. Expliciete Zoekoperators: De definitie van specifieke expansie-, perturbatie-, reductie- en C3-verfijningsoperators binnen een OLS subsetselectie kader.
3. Benchmarking Tegen Exhaustieve Zoektocht: Een evaluatie van het vermogen van EPR-C3 om top-gerangschikte subsets te herstellen die door all-subsets regressie zijn geïdentificeerd over variërende niveaus van combinatorische complexiteit ($d$ en $w$).
4. Vergelijkende Analyse: Een demonstratie dat EPR-C3 een superieur recovery-efficiëntie-evenwicht bereikt ten opzichte van stepwise procedures, gepenaliseerde regressie-preselectie, filter-wrapper screening en genetische algoritmen en branch-and-bound methoden (Leaps).
5. Empirische Bruikbaarheidsdrempel: De voorstel van een empirische drempelwaarde ($U$) om analisten te begeleiden over wanneer heuristische zoektochten computationeel preferabel worden aan exhaustieve enumeratie. De drempel wordt benaderd door $U = (8.2w - 31) \times 10^6$ voor $w \geq 4$, wat het aantal kandidaat-subsets vertegenwoordigt waarboven EPR-C3 de exhaustive search verslaat in CPU-tijd.
6. Toegepaste Validatie: Een casestudy op een gepubliceerde pKa-modelleringsdataset die de reproduceerbare herwinning van een bekende MLR-vergelijking aantoont met een gereduceerde runtime vergeleken met de oorspronkelijke exhaustieve aanpak.

Resultaten

• Recovery Performance: In benchmarkscenario's met voorspellersaantallen tot $d=60$ en modelgroottes tot $w=10$ (zoekruimtes die de $2.8 \times 10^8$ subsets overschrijden), herstelde EPR-C3 met 1.000 seeds meer dan 95% van de top 100 referentie-subsets geïdentificeerd door exhaustieve all-subsets regressie.
• Computationele Efficiëntie: EPR-C3 wordt computationeel voordeliger dan exhaustieve enumeratie wanneer het aantal kandidaat-subsets de empirische bruikbaarheidsdrempel overschrijdt. Bijvoorbeeld, bij $d=35$ en $w=10$ was EPR-C3 ongeveer 12,7 keer sneller dan exhaustive search terwijl het hoge recovery-percentages behield.
• Comparatieve Superieuriteit:
  • Stepwise/Filter Methoden: Forward stepwise en filter-wrapper screening (CSR-AS) slaagden er niet in om een van de top 100 referentie-subsets te herstellen, wat de beperkingen van gul (greedy) of marginaal screening benadrukt in complexe multivariate landschappen.
  • Gepenaliseerde Regressie: Methoden zoals Lasso, Ridge en Elastic Net boden een matige recovery (10–23%), maar vereisten aanzienlijke computationele overhead voor preselectie en daaropvolgende OLS re-fitting.
  • Stochastische/Branch-and-Bound: Terwijl Genetische Algoritmen en het Leaps-algoritme (branch-and-bound) een hogere recovery bereikten (65–68%), waren ze ofwel computationeel duur (Genetische Algoritmen), of leden ze onder "post-hoc admissibility loss" (Leaps), waarbij hoog-gerangschikte subsets werden weggegooid na de zoektocht omdat ze restricties overtraden die niet tijdens de zoektocht werden afgedwongen; EPR-C3 bereikte de hoogste recovery (95%) met een lagere relatieve CPU-tijd dan zowel de Genetische Algoritme als Leaps.
• Casestudy: In de pKa-dataset ($d=53$) herstelde EPR-C3 de exacte gepubliceerde voorspellerset en vergelijking in ongeveer 2,5 keer minder tijd dan de all-subsets regressie die in de oorspronkelijke studie werd gebruikt.

Betekenis en Claims
Het artikel positioneert EPR-C3 niet als een vervanging voor exhaustieve enumeratie wanneer dat haalbaar is, maar als een noodzakelijk, deterministisch alternatief voor hoogdimensionele regimes waar exhaustieve zoektocht computationeel onhaalbaar is. De betekenis ligt in het overbruggen van de kloof tussen de interpreteerbaarheid en statistische strengheid van OLS en de computationele haalbaarheid die vereist is voor hoogdimensionele data.

Door beperkingsbewuste beslissingen (correlatie-opschoning, VIF-snoeien, significantie-filtering) direct in het zoektraject in te bedden, vermijdt EPR-C3 de "post-hoc admissibility loss" die gebruikelijk is bij branch-and-bound of stochastische methoden. De auteurs beweren dat deze aanpak de herwinning van statistisch verdedigbare, interpreteerbare en reproduceerbare MLR-modellen mogelijk maakt zonder de volledige combinatorische last van exhaustieve enumeratie. De methode wordt gepresenteerd als een praktisch hulpmiddel voor data science workflows waar modeltransparantie en naleving van statistische aannames even cruciaal zijn als voorspellende prestaties. Het artikel blijft bescheiden en erkent dat EPR-C3 een heuristiek is waarvan de recovery-garanties alleen gevalideerd zijn binnen regimes waar exhaustieve zoektocht nog steeds computationeel haalbaar is, en dat grotere seed-budgetten vereist kunnen zijn voor zelfs meer extreme combinatorische ruimtes.