211service.com
Evolutionair algoritme presteert beter dan deep-learningmachines bij videogames
Met alle opwinding over neurale netwerken en diepgaande leertechnieken, is het gemakkelijk voor te stellen dat de wereld van de informatica uit weinig anders bestaat. Neurale netwerken beginnen immers beter te presteren dan mensen in taken zoals object- en gezichtsherkenning en in games zoals schaken, Go en verschillende arcade-videogames.
Deze netwerken zijn gebaseerd op de manier waarop het menselijk brein werkt. Niets kan meer potentieel hebben dan dat, toch?
Niet helemaal. Een heel ander type computergebruik heeft het potentieel om aanzienlijk krachtiger te zijn dan neurale netwerken en deep learning. Deze techniek is gebaseerd op het proces dat het menselijk brein heeft gecreëerd: evolutie. Met andere woorden, een opeenvolging van iteratieve verandering en selectie die de meest complexe en capabele machines heeft voortgebracht die de mensheid kent: het oog, de vleugel, de hersenen, enzovoort. De kracht van evolutie is een wonder om te zien.
Dat is de reden waarom computerwetenschappers lang hebben geprobeerd de mogelijkheden ervan te benutten. Zogenaamd evolutionair computergebruik heeft een aantal opmerkelijke prestaties geleverd in de 30 jaar sinds het voor het eerst werd gebruikt om fabrieksproductielijnen voor tractoren te optimaliseren.
Maar in de afgelopen jaren heeft dit gebied van informatica de tweede viool moeten spelen na deep-learning machines en hun enorme succes.
Vandaag lijken de rollen te gaan draaien dankzij het werk van Dennis Wilson en enkele collega's van de Universiteit van Toulouse in Frankrijk. Deze jongens hebben laten zien hoe evolutionair computergebruik de prestaties van deep-learningmachines kan evenaren op de emblematische taak die hen in 2013 voor het eerst beroemd maakte: het vermogen om beter te presteren dan mensen in arcade-videogames zoals Pong, Breakout en Space Invaders. Het werk suggereert dat evolutionair computergebruik net zo breed zou moeten worden gevierd als zijn op diep leren gebaseerde relaties.
Evolutionair computergebruik werkt op een heel andere manier dan neurale netwerken. Het doel is om computercode te maken die een specifiek probleem oplost met een benadering die enigszins contra-intuïtief is.
De conventionele manier om code te maken is om het te schrijven vanuit de eerste principes met een specifiek doel voor ogen.
Evolutionaire computing gebruikt een andere benadering. Het begint met volledig willekeurig gegenereerde code. En niet slechts één versie ervan, maar veel versies, soms honderdduizenden willekeurig samengestelde stukjes code.
Elk van deze codes wordt getest om te zien of het het vereiste doel bereikt. En natuurlijk is alle code verschrikkelijk omdat deze willekeurig wordt gegenereerd.
Maar toevallig zijn sommige stukjes code iets beter dan andere. Deze stukken worden vervolgens gereproduceerd in een nieuwe generatie code, die meer kopieën van de betere codes bevat.
De volgende generatie kan echter geen identieke kopie van de eerste zijn. In plaats daarvan moet het op de een of andere manier veranderen. Deze wijzigingen kunnen het verwisselen van twee termen in de code inhouden - een soort puntmutatie. Of ze kunnen betrekking hebben op twee codes die doormidden worden gesneden en de helften worden verwisseld, zoals seksuele recombinatie.
Elk van de nieuwe generatie wordt vervolgens getest om te zien hoe goed het werkt. De beste stukjes code worden bij voorkeur in een andere generatie gereproduceerd, enzovoort.
Op deze manier evolueert de code. Na verloop van tijd wordt het beter, en na vele generaties, als de omstandigheden goed zijn, kan het beter worden dan welke menselijke codeur ook kan ontwerpen.
Computerwetenschappers hebben met succes evolutionaire benaderingen toegepast op problemen, variërend van het ontwerpen van robots tot het bouwen van vliegtuigonderdelen.
Maar het is uit de gratie geraakt door de grote belangstelling voor deep learning. Een belangrijke vraag is dus of het de prestaties van deep learning-machines kan evenaren. Om daar achter te komen, gebruikten Wilson en co de aanpak om code te ontwikkelen die arcade-computerspellen uit de jaren tachtig en negentig kon besturen.
Deze games zijn beschikbaar in een database genaamd de Arcade Learning Environment, die steeds vaker wordt gebruikt om het leergedrag van verschillende soorten algoritmen te testen. De database bestaat uit 61 Atari-spellen, zoals Pong, Space Invaders, Breakout en Kung Fu Master.
De taak is om een algoritme te maken dat een spel als Pong kan spelen door alleen naar de uitvoer van het scherm te kijken, net zoals mensen dat spelen. Het algoritme moet dus elke spelpositie analyseren en vervolgens beslissen hoe te bewegen om de score te maximaliseren.
De besturing voor alle games is hetzelfde. Deze komen overeen met de acht richtingen waarin de controller kan worden bewogen (omhoog, omlaag, naar links en naar rechts plus vier diagonale richtingen), een druk op de knop, dezelfde acht bewegingen gecombineerd met een druk op de knop, en helemaal niets doen. Niet alle spellen gebruiken alle 18 mogelijke combinaties, en sommige gebruiken er maar vier.
De code moet eerst worden aangemaakt. De evolutionaire benadering vereist een vocabulaire van termen die aaneengeschakeld kunnen worden om computercode te vormen. De termen variëren van eenvoudige acties zoals ADD (x+y)/2 tot meer complexe acties, zoals de 1-element x-vector retourneren als x een scalaire waarde is.
De keuze van de termen waaruit dit vocabulaire bestaat, is belangrijk, en Wilson en co gebruiken een verzameling die al is gedefinieerd voor Cartesiaanse genetische programmering (zoals hun techniek wordt genoemd).
Het proces begint met het willekeurig maken van een code met 40 termen. Dit is het genoom van het programma. Dit genoom wordt vervolgens getest om te zien hoe goed het het spel speelt, beoordeeld aan de hand van de score. Afhankelijk van hoe goed het presteert, wordt het genoom vervolgens met mutaties gereproduceerd en opnieuw getest, enzovoort. In totaal heeft het team op deze manier 10.000 genomen getest.
De resultaten zorgen voor interessante lectuur. In het begin zijn de genomen slecht in het spelen van het spel. Maar na verloop van tijd worden ze beter. En na vele generaties spelen ze goed, soms beter dan mensen.
Veel genomen speelden uiteindelijk geheel nieuwe spelstrategieën, vaak complexe. Maar soms vonden ze eenvoudige die mensen over het hoofd hadden gezien.
Bij het spelen van Kung Fu Master ontdekte het evolutionaire algoritme bijvoorbeeld dat de meest waardevolle aanval een hurkstoot was. Crouching is veiliger omdat het de helft van de op de speler gerichte kogels ontwijkt en ook alles in de buurt aanvalt. De strategie van het algoritme was om deze manoeuvre herhaaldelijk te gebruiken zonder andere acties. Achteraf gezien is het logisch om uitsluitend de hurkstoot te gebruiken.
Dat verraste de menselijke spelers die bij het onderzoek betrokken waren. Door deze strategie met de hand toe te passen, behaalde hij een betere score dan het spel normaal te spelen, en de auteur gebruikt nu uitsluitend gehurkte stoten bij het aanvallen in dit spel, zeggen Wilson en co.
Over het algemeen speelde de geëvolueerde code veel van de games goed, zelfs beter dan mensen in games zoals Kung Fu Master. Net zo belangrijk is dat de geëvolueerde code net zo goed is als veel deep-learning benaderingen en beter presteert dan ze in games als Asteroids, Defender en Kung Fu Master.
Het levert ook sneller resultaat op. Hoewel de programma's relatief klein zijn, kunnen veel controllers concurreren met de modernste methoden voor de Atari-benchmarkset en hebben ze minder trainingstijd nodig, zeggen Wilson en co.
De geëvolueerde code heeft nog een ander voordeel. Omdat het klein is, is het gemakkelijk te zien hoe het werkt. Daarentegen is een bekend probleem met deep-learningtechnieken dat het soms onmogelijk is om te weten waarom ze bepaalde beslissingen hebben genomen, en dit kan praktische en juridische gevolgen hebben.
Over het algemeen is dit interessant werk dat computerwetenschappers die zich uitsluitend op deep learning richten, zou moeten suggereren dat ze misschien een truc missen. De evolutionaire benadering is een krachtig alternatief dat in een groot aantal situaties kan worden toegepast.
Sommige onderzoekers zijn het inderdaad gaan gebruiken om betere machines voor diep leren te ontwikkelen. Wat zou er mis kunnen gaan?
Referentie: https://arxiv.org/abs/1806.05695 : Evoluerende eenvoudige programma's voor het spelen van Atari-spellen