Probabilistische zoekalgoritmen voor kenmerkselectie in hoogdimensionale ruimten

Probleemstelling

Wetenschappers in toegepaste disciplines zoals bioinformatica, tekst en web mining, netwerken en biomedische ingenieurswetenschappen worden meer en meer geconfronteerd met hoogdimensionale datasets. Om domeinexperts meer inzicht te verschaffen in de gemodelleerde processen dient gekeken te worden welke van al deze dimensies de relevante informatie voor het te modelleren probleem bevatten.

Kenmerkselectietechnieken zijn een efficiente en effectieve manier om met deze hoogdimensionale datasets om te gaan, en worden aanzien als een belangrijke preprocessing stap in vele domeinen, zoals statistiek, patroonherkenning, machine learning en data mining. De belangrijkste voordelen van kenmerkselectietechnieken zijn o.a. a) de mogelijkheid om meer performante modellen op te bouwen, b) het ontwerpen van snellere en meer efficiente modellen, en c) het vermogen om meer inzicht te krijgen in de processen die door de data beschreven worden.

Om op een efficiente manier het zoekprobleem naar de optimale deelruimte te bepalen dienen heuristische zoekmethoden gebruikt te worden, vermits een volledige opsomming van alle mogelijkheden computationeel niet haalbaar is. Estimation of Distribution Algorithms (EDA) zijn een efficiente stochastische iteratieve samplingmethode, die gebruik maakt van probabilistische grafische modellen om sneller tot een betere oplossing te komen voor een zoekprobleem. Deze technieken hebben de laatste jaren bewezen dat ze zeer geschikt zijn om moeilijke optimalisatieproblemen op te lossen.

Doelstelling

In deze thesis zal de student onderzoeken in welke mate EDAs kunnen gebruikt worden om de relevante deelruimte van hoogdimensionale datasets te bepalen. Belangrijke punten die in deze context onderzocht kunnen worden zijn:

• De keuze van de evaluatiefunctie die het zoekproces stuurt. In het conventionele geval - kenmerkselectie voor classificatie - bestaat deze functie meestal uit het trainen en testen van een classificatiemodel in de gegeven deelruimte.
• Het onderzoeken van de schaalbaarheid van de evaluatiefunctie naar hoogdimensionale ruimten, in het bijzonder de ontwikkeling van efficiente en betrouwbare schattingen van de relevantie van een bepaalde deelruimte. Mogelijks kunnen hiervoor reeds bestaande maten op basis van informatietheorie gebruikt en aangepast worden.
• Onderzoeken in welke mate de bekomen kenmerkselectietechnieken robuust zijn.

Contactpersonen

• Promotor: Yvan Saeys en Gert De Cooman
• Begeleiders: Yvan Saeys en Gert De Cooman

Referentiemateriaal

• Introductie tot kenmerkselectie
• Introductie tot EDAs
• P. Larrañga and J.A. Lozano (Eds.). Estimation of distribution algorithms: A new tool for evolutionary computation. Kluwer Academic Publishers, Boston, 2002.