211service.com
Evolusjonær algoritme utkonkurrerer dyplæringsmaskiner på videospill
Med all spenningen over nevrale nettverk og dyplæringsteknikker, er det lett å forestille seg at informatikkverdenen består av lite annet. Nevrale nettverk har tross alt begynt å utkonkurrere mennesker i oppgaver som objekt- og ansiktsgjenkjenning og i spill som sjakk, Go og ulike arkadevideospill.
Disse nettverkene er basert på måten den menneskelige hjernen fungerer på. Ingenting kan ha mer potensial enn det, ikke sant?
Ikke helt. En helt annen type databehandling har potensial til å være betydelig kraftigere enn nevrale nettverk og dyp læring. Denne teknikken er basert på prosessen som skapte den menneskelige hjernen – evolusjon. Med andre ord, en sekvens av iterativ endring og seleksjon som produserte de mest komplekse og dyktige maskinene kjent for menneskeheten – øyet, vingen, hjernen og så videre. Evolusjonens kraft er et under å se.
Det er derfor informatikere lenge har forsøkt å utnytte dens evner. Såkalt evolutionary computing har oppnådd noen bemerkelsesverdige bragder i løpet av de 30 årene siden den ble tatt i bruk for å optimalisere fabrikkens produksjonslinjer for traktorer.
Men de siste årene har dette området av informatikk måttet spille andrefiolin til dyplæringsmaskiner og deres enorme suksess.
I dag ser det ut til å snu takket være arbeidet til Dennis Wilson og noen få kolleger ved universitetet i Toulouse i Frankrike. Disse gutta har vist hvordan evolusjonær databehandling kan matche ytelsen til dyplæringsmaskiner på emblematisk oppgave som først drev dem til berømmelse i 2013 – evnen til å overgå mennesker i arkadevideospill som Pong, Breakout og Space Invaders. Arbeidet antyder at evolusjonær databehandling bør hylles like bredt som dens dype læringsbaserte relasjoner.
Evolusjonær databehandling fungerer på en helt annen måte enn nevrale nettverk. Målet er å lage datakode som løser et spesifikt problem ved å bruke en tilnærming som er noe kontraintuitiv.
Den konvensjonelle måten å lage kode på er å skrive den fra første prinsipper med et spesifikt mål i tankene.
Evolusjonær databehandling bruker en annen tilnærming. Det starter med kode generert helt tilfeldig. Og ikke bare én versjon av den, men mange versjoner, noen ganger hundretusenvis av tilfeldig sammensatte kodebiter.
Hver av disse kodene testes for å se om den oppnår det nødvendige målet. Og selvfølgelig er all koden forferdelig fordi den er tilfeldig generert.
Men ved en tilfeldighet er noen kodebiter litt bedre enn andre. Disse bitene blir deretter reprodusert i en ny generasjon kode, som inkluderer flere kopier av de bedre kodene.
Neste generasjon kan imidlertid ikke være en identisk kopi av den første. I stedet må det endres på en eller annen måte. Disse endringene kan innebære å bytte to termer i koden - en slags punktmutasjon. Eller de kan involvere to koder som deles i to og halvdelene byttes ut – som seksuell rekombinasjon.
Hver av den nye generasjonen blir deretter testet for å se hvor godt den fungerer. De beste kodebitene blir fortrinnsvis reprodusert i en annen generasjon, og så videre.
På denne måten utvikler koden seg. Over tid blir det bedre, og etter mange generasjoner, hvis forholdene er riktige, kan det bli bedre enn noen menneskelig koder kan designe.
Dataforskere har med suksess brukt evolusjonære tilnærminger til problemer som spenner fra å designe roboter til å bygge flydeler.
Men det har falt i unåde på grunn av den enorme interessen for dyp læring. Så et viktig spørsmål er om den kan matche ytelsen til dyplæringsmaskiner. For å finne det ut brukte Wilson og co tilnærmingen til å utvikle kode som kunne kontrollere arkadedataspill fra 1980- og 1990-tallet.
Disse spillene er tilgjengelige i en database kalt Arcade Learning Environment, som i økende grad blir brukt til å teste læringsatferden til algoritmer av ulike slag. Databasen består av 61 Atari-spill, som Pong, Space Invaders, Breakout og Kung Fu Master.
Oppgaven er å lage en algoritme som kan spille et spill som Pong ved kun å se på utdataene fra skjermen, på samme måte som mennesker spiller. Så algoritmen må analysere hver spillposisjon og deretter bestemme hvordan den skal flytte for å maksimere poengsummen.
Kontrollene for alle spill er de samme. Disse tilsvarer de åtte retningene kontrolleren kan flyttes (opp, ned, venstre og høyre pluss fire diagonale retninger), et knappetrykk, de samme åtte bevegelsene kombinert med et knappetrykk, og ikke gjøre noe i det hele tatt. Ikke alle spill bruker alle 18 mulige kombinasjoner, og noen bruker så få som fire.
Koden må først opprettes. Den evolusjonære tilnærmingen krever et vokabular av termer som kan settes sammen for å danne datakode. Begrepene spenner fra enkle handlinger som ADD (x+y)/2 til mer komplekse, som å returnere 1-elementet x-vektoren hvis x er en skalar.
Valget av termer som utgjør dette vokabularet er viktig, og Wilson og co bruker et sett som allerede er definert for kartesisk genetisk programmering (som teknikken deres kalles).
Prosessen begynner med å tilfeldig lage en kode som inneholder 40 termer. Dette er genomet til programmet. Dette genomet blir deretter testet for å se hvor godt det spiller spillet, bedømt av poengsummen. Avhengig av hvor godt det fungerer, reproduseres genomet med mutasjoner og testes på nytt, og så videre. Totalt testet teamet 10 000 genomer på denne måten.
Resultatene gir interessant lesning. Til å begynne med er genomene forferdelige til å spille spillet. Men over tid blir de bedre. Og etter mange generasjoner spiller de bra, noen ganger bedre enn mennesker.
Mange genomer endte opp med å spille helt nye spillstrategier, ofte komplekse. Men noen ganger fant de enkle som mennesker hadde oversett.
For eksempel, når du spilte Kung Fu Master, oppdaget den evolusjonære algoritmen at det mest verdifulle angrepet var en crouch-punch. Crouching er tryggere fordi det unngår halvparten av kulene rettet mot spilleren og angriper også alt i nærheten. Algoritmens strategi var å gjentatte ganger bruke denne manøveren uten andre handlinger. I ettertid er det fornuftig å bruke crouch-punch utelukkende.
Det overrasket de menneskelige aktørene som var involvert i studien. Ved å bruke denne strategien for hånd oppnådde man en bedre poengsum enn å spille spillet på vanlig måte, og forfatteren bruker nå krøkende slag utelukkende når han angriper i dette spillet, sier Wilson og co.
Totalt sett spilte den utviklede koden mange av spillene godt, til og med bedre enn mennesker i spill som Kung Fu Master. Like betydelig er den utviklede koden like god som mange dyplæringsmetoder og overgår dem i spill som Asteroids, Defender og Kung Fu Master.
Det gir også et resultat raskere. Mens programmene er relativt små, konkurrerer mange kontrollere med toppmoderne metoder for Atari benchmark-settet og krever mindre treningstid, sier Wilson og co.
Den utviklede koden har en annen fordel. Fordi den er liten, er det lett å se hvordan den fungerer. Derimot er et velkjent problem med dyplæringsteknikker at det noen ganger er umulig å vite hvorfor de har tatt bestemte avgjørelser, og dette kan ha praktiske og juridiske konsekvenser.
Totalt sett er dette interessant arbeid som burde antyde for informatikere som utelukkende fokuserer på dyp læring at de kanskje mangler et triks. Den evolusjonære tilnærmingen er et kraftig alternativ som kan brukes i et bredt sett av situasjoner.
Noen forskere har faktisk begynt å bruke den til å utvikle bedre dyplæringsmaskiner. Hva kan gå galt?
Ref: https://arxiv.org/abs/1806.05695 : Utvikler enkle programmer for å spille Atari-spill