Met reductieregels grote datasets te lijf

Share this post:

In de nabije toekomst kunnen we sneller het exacte antwoord van een berekening vinden, bijvoorbeeld bij het filteren van informatie uit Big Data. Bart Jansen analyseert in zijn onderzoek in hoeverre berekeningen kunnen worden versneld door de dataset van tevoren te versimpelen, zonder de uitkomst aan te tasten. Voor zijn baanbrekende proefschrift ontving hij op 25 juni de Christiaan Huygens Wetenschapsprijs 2014 voor Informatie- en Communicatietechnologie.

Deze wetenschapsprijs wordt uitgereikt aan een onderzoeker van een Nederlandse universiteit die een belangrijke bijdrage aan de wetenschap heeft geleverd, bij voorkeur met een duidelijke maatschappelijke relevantie. De prijs gaat elk jaar naar onderzoek op een ander vakgebied. Dit jaar is dat de Informatie- en Communicatietechnologie (ICT). De prijs heeft daarnaast als doel om de contacten tussen universiteiten en bedrijfsleven te bevorderen en de instroom van studenten in de bètawetenschappen positief te beïnvloeden. IBM steunt graag baanbrekend onderzoek met maatschappelijke en economische waarde en is daarom de sponsor van de Christiaan Huygensprijs voor ICT.

Efficiëntere methode
Bart Jansen ontving de prijs voor zijn onderzoek The Power of Data Reduction: Kernels for Fundamental Graph Problems. Hierin bestudeert hij de complexiteit van verschillende fundamentele soorten berekeningen voor het analyseren van netwerken. Voor dergelijke berekeningen geeft hij efficiënte algoritmen om een netwerk te verkleinen en te versimpelen, zonder het antwoord te veranderen. Doordat het zoeken naar het antwoord in de verkleinde dataset minder tijd kost, bespaar je rekenkracht. Bart Jansen: “We wisten al dat we met gegevensreductie een vraagstelling vaak sneller kunnen oplossen. Er was alleen geen wiskundige verklaring voor. In mijn onderzoek geef ik een manier om te kwantificeren hoe complex een dataset is en geef ik reductieregels die grote datasets van relatief lage complexiteit kunnen vereenvoudigen. Daardoor kan mijn theorie verklaren op wat voor soort datasets de reductieregels effect hebben en waarom; op dat punt verheft mijn aanpak het gebruik van reductieregels van kunst tot wetenschap.”

Snellere berekening
Jansen maakt het mogelijk om berekeningen in de toekomst sneller uit te voeren. Wat betekent dat concreet? Jansen: “Neem nou een pakketbezorgdienst: via welke route kan dit bedrijf pakketjes het snelst en met minimaal brandstofverbruik bezorgen? Het kost een computer veel rekentijd om de beste route te vinden, omdat deze alle volgorden van afleveradressen probeert. Wanneer je voor elk mogelijke volgorde de hele wegenkaart doorrekent, kost dat veel tijd. Met gegevensreductie kun je wegen uit het wegennetwerk weglaten waarvan wiskundige argumenten aantonen dat ze niet gebruikt worden in een optimale bezorgroute. Je kunt daarna dus de route plannen zonder deze wegen, waardoor het vinden van een route sneller gaat. Een computer heeft hier namelijk minder rekenkracht en geheugen voor nodig.”

Exacte berekening
Er zijn andere methoden om een berekening te versnellen: door vuistregels te gebruiken om een antwoord te vinden dat bij benadering klopt of door een steekproef te nemen van de dataset en alleen die gegevens te analyseren. Deze methoden worden in de praktijk vaak toegepast wanneer het vinden van het exacte antwoord teveel tijd kost. Ze bieden alleen geen zekerheid. De gegevensreductiemethode van Jansen wel. De rekenmethode van Jansen is dus sneller in exacte berekeningen. “Mijn reductieregels kunnen bijvoorbeeld worden toegepast om het vinden van lange reactiekettingen te versnellen. Om de celbiologie van een organisme te analyseren, worden netwerken gemaakt waarin elk eiwit een knooppunt is met verbindingen tussen eiwitten die samen een reactie aangaan. Door lange kettingen van reacties in deze netwerken te vinden, kan je vaststellen welke eiwitten belangrijk zijn voor een proces.” Het vinden van reactiekettingen is een tijdrovend proces. Daarom passen onderzoekers soms vuistregels toe om sneller tot een onderzoeksresultaat te komen. Ze weten dan alleen niet zeker of het resultaat volledig klopt. Door gegevensreductie toe te passen, krijgen ze gegarandeerd een betrouwbaar onderzoeksresultaat in kortere tijd. Dit levert een beter begrip op van de eiwitreacties, wat bijvoorbeeld nuttig is bij het maken van medicijnen.

De toekomst van algoritmiek
Voor veel soorten berekeningen lijkt het op theoretische en praktische gronden hopeloos om binnen afzienbare tijd het exacte antwoord te vinden. Jansen stelt echter dat, voordat vuistregels of steekproeven voor benaderingen worden gebruikt, er moet worden gekeken naar de eigenschappen van de dataset. Als er parameters zijn die de complexiteit in een bepaalde dimensie begrenzen, is het wellicht mogelijk de dataset met reductieregels te verkleinen waardoor het exacte antwoord binnen korte tijd vindbaar is. “Voor de lange termijn betekent het dat de ontwikkeling in het ontwerp van algoritmen belangrijker is dan technologische vooruitgang. Hoewel de wet van Moore suggereert dat de rekenkracht elke paar jaar verdubbelt, kan een beter algoritme een versnelling van een factor duizend geven. Zeker omdat de grenzen van verbeteringen in chipdesign in zicht lijken te komen, is het juist de theorie van algoritmiek waar in de toekomst in geïnvesteerd moet worden.”

Het onderzoek van Jansen heeft een belangrijke maatschappelijke waarde. In veel belangrijke maatschappelijke scenario’s komen immers optimalisatieproblemen voor waarvoor huidige computerprogramma’s het exacte antwoord niet kunnen berekenen binnen afzienbare tijd: van de meest efficiënte inzet van ambulances in een regio tot het analyseren van de werking van een medicijn. Daarom worden benaderingen gebruikt. De techniek van gegevensreductie helpt deze problemen exact op te lossen binnen kortere tijd. Dat levert de maatschappij aanzienlijke besparingen op qua tijd, geld en effectiviteit. De kans is dus groot dat de gegevensreductiemethode van Jansen ons in de toekomst op verschillende gebieden veel oplevert. Jansen: “De toepassing van gegevensreductie staat nog in de kinderschoenen, maar de mogelijkheden zijn legio. Mijn onderzoek is dan ook eerder een begin- dan een eindpunt.”