< Terug naar vorige pagina

Project

Automatische Algoritme Selecite Uitbreiden naar de Online Setting

Het doel van dit doctoraat is om de methodologie van automatische algoritme selectie uit te breiden naar de online setting. Het doel van automatische algoritme selectie is om automatisch het beste algoritme te selecteren om een probleem mee op te lossen. Dit onderzoeksveld wordt gemotiveerd door de observatie dat er voor vele problemen in artificiële intelligentie en operationeel onderzoek geen duidelijk best algoritme bestaat. In plaats daarvan doet elk algoritme het goed op sommige probleeminstanties maar niet op andere. Voorbeelden van succesvolle toepassingsdomeinen zijn constraint satisfaction, combinatorische optimalisatie en machine-learning (waar het bekend staat onder de noemer meta-learning)

 

Leren welk algoritme het beste is voor welk type instantie gebeurt aan de hand van instantie-eigenschappen. Dit zijn probleemeigenschappen die gecorreleerd zijn met de performantie van de algoritmes. Eenmaal zulke eigenschappen geïdentificeerd zijn, wordt elk algoritme losgelaten op een set traininginstanties. De performantie van elk algoritme wordt bijgehouden en deze trainingdata wordt gebruikt om een selectiemap te maken. Deze selectiemap beeldt vectoren van instantie-eigenschap-waarden af op algoritmes. Die selectiemap wordt gebruikt om te voorspellen welk algoritme best is voor nieuwe instanties.

 

Bij huidige aanpakken voor automatische algoritme selectie verandert de selectiemap nooit meer na de trainingfase. Dit doctoraat wordt voornamelijk geïnspireerd door de observatie dat wanneer de selectiemap gebruikt wordt om te voorspellen welk algoritme best is voor nieuwe instanties, bijkomende data beschikbaar komt. Voor elke instantie wordt een algoritme geselecteerd om hem mee op te lossen en de performantie van het gekozen algoritme op die instantie wordt gekend. Het hoofddoel van dit doctoraat is om een methodologie voor te stellen om deze data te gebruiken om de selectiemap te verbeteren terwijl hij gebruikt wordt en om die methodologie te onderzoeken. In andere woorden: het doel is om automatische algoritme selectie uit te breiden zodanig dat ook tijdens de online setting bijgeleerd wordt.

 

Een nevendoel is om de exploratie vs. exploitatie trade-off te onderzoeken die optreedt wanneer automatische algoritme selectie uitgebreid wordt naar de online setting. Bij standaard offline algoritme selectie zal steeds het beste algoritme gekozen worden. Elke andere keuze resulteert in een verlies in verwachte performantie. Deze redenering gaat niet op in de online setting. Het selecteren van een algoritme beïnvloedt niet enkel de performantie op de huidige instantie maar ook de data die beschikbaar wordt voor latere voorspellingen. Het kan op lange termijn voordelig zijn om een niet als best voorspeld algoritme te selecteren als dit onmiddellijk verlies in verwachte performantie voldoende gecompenseerd wordt door verbeterde latere beslissingen. Er moet een trade-off gevonden worden tussen steeds het als best voorspelde algoritme selecteren (exploitatie) en alternatieven overwegen (exploratie)

 

Onderzoek naar de exploratie vs. expoitatie trade-off wordt onder meer verricht binnen de multi-armed bandit cmmunity. Een hypothesis van dit doctoraat is dat het probleem van automatische algoritme selectie gemodelleerd kan worden als een contextueel multi-armed bandit problem. Als dit waar blijkt te zijn, kunnen methodes uit de multi-armed bandit literatuur aangewend worden om dit probleem op te lossen. Deze methodes hebben het voordeel dat ze bepaalde garanties hebben in verband met de maximale spijt door incorrecte selecties. Een selectie is incorrect als het geselecteerde algoritme voor een instantie niet het beste was voor die instantie.

 

Er zullen enkele methodes uit de multi-armed bandit literatuur getest worden op algemeen aanvaarde algoritme selectie benchmarks. Het doel is om gebruikers van algoritme selectie methodes een goed werkende strategie aan te reiken voor de online data die gratis beschikbaar wordt bij het gebruiken van algoritme selectie methodes.

 

De methode zal bovendien ook getest worden op nieuwe problemen, waarop algoritme selectie nog niet toegepast werd.

Datum:2 sep 2014 →  15 sep 2018
Trefwoorden:Online learning, Algorithm Selection, Automatic Algorithm Selection, Multi-armed bandits
Disciplines:Toegepaste wiskunde, Computerarchitectuur en -netwerken, Distributed computing, Informatiewetenschappen, Informatiesystemen, Programmeertalen, Scientific computing, Theoretische informatica, Visual computing, Andere informatie- en computerwetenschappen, Artificiële intelligentie, Cognitieve wetenschappen en intelligente systemen
Project type:PhD project