Novel GPU Boruta algorithms for feature selection from high-dimensional data

Technische Samenvatting: Nieuwe GPU-Boruta-algoritmen voor Feature Selection uit Hoogdimensionele Data

Probleemstelling
Feature selection is een kritieke stap bij het ontwikkelen van robuuste Artificial Intelligence for Science (AI4S)-modellen, met name in gebieden zoals bio-informatica en materiaalontdekking, waar data een hoge dimensionaliteit en complexe onderlinge correlaties tussen features vertoont. Hoewel wrapper-methoden zoals het Boruta-algoritme effectief zijn bij het identificeren van relevante features door interacties tussen features te beschouwen, lijden ze onder een hoge computationele complexiteit. Het originele Boruta-algoritme, dat berust op Random Forests, heeft een tijdscomplexiteit die evenredig is met het product van attributen en objecten, waardoor het inefficiënt is voor grootschalige datasets wanneer het wordt uitgevoerd op CPU-gebaseerde platforms. Deze inefficiëntie beperkt de toepasbaarheid van rigoureuze feature selection in moderne wetenschappelijke data-analyse van hoogdimensionale data.

Methodologie
Om de computationele bottleneck aan te pakken, stellen de auteurs twee GPU-versnelde varianten van het Boruta-algoritme voor, waarbij gebruik wordt gemaakt van de cuML-bibliotheek voor de implementatie van Random Forests op NVIDIA-GPU's. Beide varianten behouden de kernlogica van het originele Boruta-algoritme – het vergelijken van de belangrijkheid van originele features met gerandomiseerde "shadow features" – maar verschillen in hoe de feature-importance wordt gekwantificeerd:

1. Boruta-TreeImp: Deze variant kwantificeert feature-importance op basis van impurity-reductie (Gini-impurity of vergelijkbare metrieken) die wordt opgebouwd over alle bomen in de Random Forest. Het algoritme versnelt de constructie van de Random Forest op de GPU en berekent de importance door de boomstructuren te traverseren om de gain-waarden op te tellen.
2. Boruta-Permut: Deze variant kwantificeert feature-importance op basis van permutatie. Het meet de verandering in voorspelfout van het model (Mean Squared Error voor regressie; KL-divergentie voor classificatiekansen) wanneer de feature-waarden willekeurig worden geschud. Deze methode wordt volledig op de GPU geïmplementeerd om parallelisme te maximaliseren tijdens de fasen van voorspelling en verliesberekening.

De auteurs leveren een analyse van de computationele complexiteit, waarbij zij opmerken dat hoewel beide methoden worden gedomineerd door de trainingstijd van de Random Forest $O(M \cdot m \cdot n \cdot \log n)$, de GPU-parallelisatie de wandkloktijd aanzienlijk reduceert. Zij stellen vast dat Boruta-TreeImp over het algemeen efficiënter is voor grote feature-sets ($m$), terwijl Boruta-Permut mogelijk de voorkeur verdient voor kleinere feature-sets, hoewel het hogere kosten met zich meebrengt vanwege de noodzaak van $m$ afzonderlijke voorspellingen per iteratie.

Belangrijkste Bijdragen

• GPU-implementatie: De succesvolle aanpassing van de Boruta-wrapper-methode aan GPU-architecturen met behulp van cuML, waarbij twee distincte implementaties worden gecreëerd (TreeImp en Permut).
• Kosten-batenanalyse: Een rigoureuze vergelijking van computationele kosten met behulp van huurprijzen voor cloudservers, die aantoont dat GPU-uitvoering aanzienlijk goedkoper is dan multi-core CPU-uitvoering voor deze taken.
• Algoritmische vergelijking: Een gedetailleerde evaluatie van de afwegingen tussen op impurity gebaseerde en op permutatie gebaseerde importance-metrieken binnen het versnelde Boruta-framework.

Experimentele Resultaten
De auteurs evalueerden de voorgestelde algoritmen op een zelfgeconstrueerde synthetische dataset en vier publieke datasets (CT, NEWS, ENERGY, MADELON), waarbij ze deze vergeleken met de originele CPU-gebaseerde Boruta (scikit-learn) en het BorutaShap-algoritme.

• Synthetische Data: Op een dataset met 10 bekende relevante features en 40 ruisfeatures identificeerden zowel Boruta als Boruta-Permut correct alle 10 features. Boruta-TreeImp identificeerde er correct 9, maar slaagde er niet in één feature te selecteren (feature-18), die als derdemachtswortel in de objectieve functie werd opgenomen. De auteurs schrijven dit toe aan de bekende beperking van op impurity gebaseerde importance, die de importance van willekeurige features kan overschatten, wat leidt tot een conservatieve selectie in deze specifieke context.
• Bias en Multicollineariteit: Experimenten toonden aan dat sample-bias (schaarse samples voor een relevante feature) ertoe leidde dat alle algoritmen faalden bij het selecteren van die feature. In aanwezigheid van multicollineariteit selecteerde Boruta-Permut minder redundante lineair gecorreleerde features in vergelijking met de originele Boruta.
• Publieke Datasets: Over de CT-, NEWS-, ENERGY- en MADELON-datasets behielden de GPU-versnelde versies een feature-selectie-effectiviteit die vergelijkbaar was met die van de originele Boruta (gemeten aan de hand van modelprestatie-metrieken zoals MSE, MAE, $R^2$ en Accuracy).
• Efficiëntiewinsten: De meest significante bevinding was de reductie in tijd en kosten. Bijvoorbeeld, op de NEWS-dataset duurde de originele Boruta ongeveer 22 minuten (met kosten van ongeveer $1,77), terwijl Boruta-TreeImp ongeveer 7,5 minuten nodig had (met kosten van ongeveer $0,015). Op de MADELON-dataset voltooide Boruta-TreeImp de taak in minder dan 5 minuten voor een kostenplaatje van ongeveer $0,01, vergeleken met ongeveer 10 minuten en ongeveer $0,80 voor de originele versie.

Betekenis en Claims
Het artikel claimt dat het uitvoeren van Boruta feature selection op GPU's een effectieve en kostenefficiënte oplossing biedt voor grootschalige data-analyse. De auteurs benadrukken dat hun methoden de computationele efficiëntie sterk verbeteren terwijl ze een feature-selectie-accuraatheid behouden die vergelijkbaar is met die van het originele Boruta-algoritme.

De studie concludeert bescheiden dat hoewel de GPU-versnelling het schaalbaarheidsprobleem oplost, de keuze tussen de twee varianten afhangt van de data-eigenschappen. Specifiek merken zij op dat de op impurity gebaseerde versie (Boruta-TreeImp) soms de importance van shadow features kan overschatten of features met complexe, niet-lineaire bijdragen kan missen (zoals het voorbeeld van de derdemachtswortel), wat suggereert dat de op permutatie gebaseerde versie (Boruta-Permut) in bepaalde scenario's robuuster kan zijn, ondanks de hogere computationele overhead. Het werk positioneert deze algoritmen als een praktische stap richting het mogelijk maken van rigoureuze feature engineering voor AI4S-modellen die omgaan met massale datasets.