Mašinsko učenje je naučna disciplina koja se bavi stvaranjem i proučavanjem algoritama koji mogu da uče iz podataka. Takvi algoritmi funkcionišu gradeći model baziran na ulazima, i koriste ga da naprave predviđanja ili odluke (umesto zakucanih programskih instrukcija). Neuralne mreže su model inspirisan radom mozga. Predstavljaju se kao sistem međusobno povezanih neurona, koji mogu da računaju svoje vrednosti u zavisnosti od ulaza.

Neuro-evolucija sa menjajućim topologijama (Neuro-evolution with augmenting topologies, NEAT) je tehnika treniranja neuralne mreže genetskim algoritmom. Pored treniranja težina grana, NEAT omogućuje i treniranje samih topologija mreže. Na početku, topologija je minimalna (ulazni čvorovi povezani sa izlaznim čvorovima), ali mutacijama mogu nastati novi neuroni ili veze. Pri stvaranju novih neurona i veza pamte se dodatni podaci, da bi, u slučaju da ista mutacija nastane u drugoj jedinci, znali da se radi baš o njoj. To omogućava ukrštanje različitih topologija. Pošto počinje od minimalne topologije, NEAT teži da nađe najmanju neuralnu mrežu koja rešava problem. Sve ovo neodoljivo podseća na prirodu, u kojoj se organizmi razmnožavaju i mutiraju, i vremenom postaju složeniji.

Ova tehnika je implementirana na igrici Racer, priloženoj uz rad. To je trka u kojoj igrač kontroliše svoje vozilo. Bot se može trenirati na odabranoj mapi, i može se pratiti razvoj kroz generacije. Takođe se može gledati neuralna mreža izabrane jedinke i igrati protiv nje.

U prvom delu diplomskog rada ukratko je opisan klasični pogled na neuralne mreže i genetske algoritme. Zatim je dat detaljni opis NEAT tehnike i njene implementacije. Poslednji deo rada sadrži eksperimentalne rezultate testiranja performansi na klasičnim problemima (benčmark), uključujući i igricu Racer.

Neuralne mreže

Programeri su već dugo vremena inspirisani ljudskim mozgom. 1943. Voren Mek Kulok (neurolog) i Volter Pits (logičar) su razvili prvi koncept neuralne mreže. U njihovom radu “Logički račun ideja koji se dešava pri neuralnoj aktivnosti”, oni objašnjavaju koncept neurona, ćelije koja živi u mreži ćelija, koja prima ulaze, procesira te ulaze i generiše izlaz.

Njihov rad, i rad mnogih potonjih naučnika i istraživača, nije imao za cilj da tačno opiše kako mozak radi. Umesto toga, veštačka neuralna mreža je dizajnirana kao računski model baziran na mozgu koji može da reši određene vrste problema.

Jasno je da postoje problemi koji su izuzetno laki za kompjuter, ali teški za čoveka. Na primer, kompjuter u trenu izračuna koren veoma velikog broja. Isto tako, postoje problemi koji su za ljude izuzetno jednostavni, ali ne tako laki za kompjuter. Svako dete zna da razlikuje mačku od psa. Ako upoznamo stranca jednog dana vrlo verovatno bi ga prepoznali u gomili ljudi dan posle. Ali kako mašina da uradi ove zadatke? Neki naučnici su proveli čitave karijere istražujući i implementirajući složena rešenja.

Najčešća upotreba neuralnih mreža danas je upotreba u ovim “lakim za čoveka teškim za kompjuter” zadacima, kao prepoznavanje oblika. Primena varira od prepoznavanja teksta sa slike do prepoznavanja lica. Takođe, koriste se u predviđanju budućih događaja u odnosu na prošle, izbacivanju šuma iz signala, kontrolisanju autonomnih jedinica (na primer kola ili dronova), prepoznavanju anomalija itd.

Ovo je jedan primer kako bi mogla da izgleda neuralna mreža. Sastoji se od neurona i veza između njih. Svaki pojedinačni neuron u mreži je jednostavan. Čita ulaze, procesira ih i generiše izlaz. Mreža puno neurona međutim može pokazati izuzetno bogata i inteligentna ponašanja.

Jedan od ključnih elemenata neuralne mreže je njena mogućnost učenja. Neuralna mreža nije samo složen sistem, nego složen sistem koji je prilagodljiv, što znači da može da menja unutrašnju strukturu bazirano na informacijama koje teku kroz nju. Ovo se tipično ostvaruje prilagođavanjem težina. Videćemo da je takođe moguće prilagođavati i same topologije mreže. U slici iznad, svaku vezu opisuje težina, broj koji kontroliše protok signala između dva neurona. Ako mreža generiše dobre izlaze, nema potrebe da se menja. Međutim, ako mreža generiše loše izlaze, greške, onda se sistem prilagođava, menjajući težine (ili topologije) sa ciljem da popravi rezultate. Postoji nekoliko strategija učenja:

Nadgledano učenje

U suštini, ova strategija uključuje učitelja koji je pametniji nego sama mreža. Na primer, prepoznavanje lica. Učitelj pokazuje mreži gomilu lica, i učitelj već zna ime čoveka sa svake slike. Mreža pravi pretpostavke, a onda učitelj mreži daje odgovore. Mreža može da uporedi svoje odgovore sa tačnim odgovorima i da se prilagođava na osnovu njenih grešaka.

Nenadgledano učenje

Potrebno kada ne postoji skup podataka sa poznatim odgovorima. Zamislite potragu za skrivenim obrascem u skupu podataka. Primer za ovo učenje je grupisanje, tj. podela skupa elemenata u grupe prema nekom, unapred nepoznatom, obrascu.

Pojačano učenje

Strategija bazirana na posmatranju. Neuralna mreža pravi odluke koje utiču na okruženje, i posmatra okruženje. Ako je zapažanje negativno, mreža može da se prilagodi tako da napravi drugačiju odluku sledeći put. Pojačano učenje je uobičajno u robotici. Da li je robot udario u zid? Ili je ispunio dati zadatak?

Sposobnost mreže da uči, i da se vremenom prilagođava, je ono što je čini korisnom u polju veštačke inteligencije.

Perceptron

Perceptron je najjednostavnija neuralna mreža – mreža sasatavljena od jednog neurona. Sastoji od nekoliko ulaza, neurona i jednog izlaza. Prođimo kroz posao perceptrona korak po korak.

Primi ulaze

Recimo da imamo dva ulaza .

Daj težine ulazima

Svaki ulaz poslat u mrežu množi se sa težinskim koeficijentom. Kada pravimo mrežu, tipično počinjemo sa nasumično izabranim težinama. Recimo . Dakle, .

Saberi otežale ulaze

Generiši izlaz

Izlaz se generiše tako što se suma prosledi kroz aktivacionu funkciju. Postoje razne aktivacione funkcije. Po standardnoj definiciji perceptrona, aktivaciona funkcija je , u našem slučaju .

Šta možemo da uradimo sa perceptronom? Na primer, možemo da napravimo mrežu koja za ulaze x i y govori na kojoj je strani tačka od date linije (-1 ispod 1 iznad 0 na pravoj).

Međutim, na datoj slici perceptrona postoji ozbiljan problem. Pogledajmo tačku (0, 0). Ako damo ulaze mreži, kakve god da su težine grana suma će svakako biti 0, što znači da prava mora da prolazi kroz tu tačku. To nije ono što želimo. Razmotrimo sledeći perceptron:

Da bi izblegao ovakav problem, našem perceptronu treba dodatni ulaz, obično poznat kao bias. Bias je speciijalan ulaz koji uvek ima vrednost 1. Sada, u tački (0, 0), naša suma . Ovakav model omogućava opis bilo koje prave.

Složena mreža

Perceptron može da ima puno ulaza, ali to je i dalje jedan usamljeni neuron. Prava moć neuralnih mreža dolazi u međusobnim odnosima unutar mreže. Perceptroni mogu da reše samo linaerne probleme. Njima možemo da podelimo podatke pravom linijom (levo), ali ne možemo da opišemo kompleksniji model (desno).

Takođe, “logičko i” i “logičko ili” su linearno rešivi problemi. “Eksluzivno ili” nije. U njegovom slučaju nije moguće povući pravu liniju koja deli pozitivne i negativne primere. Najmanja mreža koja opisuje eksluzivno ili izgleda ovako:

Sada, osim ulaza, izlaza i biasa, postoje i skriveni neuroni. Tako se zovu jer nisu povezani ni sa ulazima ni sa izlazima direktno. Njihovi ulazi su izlazi od neurona pre njih u mreži. Bias neuroni uvek imaju izlaznu vrednost 1. Ulazni neuroni ne rade računanje, i njihova izlazna vrednost je sam ulaz koji predstavljaju. Skriveni i izlazni neuroni računaju izlaznu vrednost kroz aktivaciona funkciju sume otežalih ulaza, kao što smo videli kod perceptrona. Ovakva struktura omogućava bogatu i složenu analizu ulaza.

Takođe, perceptron kao aktivacionu funkciju koristi koja kao izlaz daje vrednosti -1, 0 i 1. Ovaj diskretan opis je dosta štur, jer ako je izlaz -1 gubimo podatak da li je -2 ili -∞. Zato se koriste druge aktivacione funkcije. Najčešće sigma funkcija tako nazvana zbog izgleda koji podseća na grčko slovo sigma. Ovakvom funkcijom prenosimo više informacija u dalje neurone mreže, ili na izlaz (koji ne mora biti diskretan).

Zaustavimo se sada ovde. Opisali smo kako izgleda mreža i kako funkcioniše. Još nismo objasnili kako se trenira, kako se dolazi do željene topologije mreže i težina grana. U poglavlju o neuro-evoluciji sa menjajućim topologijama videćemo kako možemo da iskoristimo ovu tehniku da treniramo mrežu, i naučimo je da daje korisne izlaze. Sada pogledajmo kako možemo da simuliramo evoluciju pri optimizovanju rešenja raznih problema.

Genetski algoritmi

Računarske simulacije procesa evolucije datiraju još iz 1950-ih. Veći deo onoga što smatramo genetskim algoritmima razvio je Džon Holand, profesor sa univerziteta Mičigen, čija je knjiga “Prilagođavanje u prirodi i veštačkim sistemima” započela istraživanje genetskih algoritama. Danas, genetski algoritmi deo su šireg polja istraživanja, češće nazivanog evoluciono računastvo.

Pri objašnjavanju genetskih algoritama, možda bi bilo zgodno vratiti se na majmune. Izmišljene majmune koji kucaju ceo Šekspirov opus.“Beskonačna majmunska teorema” glasi ovako: majmun koji nasumično pritiska tastere na mašini za kucanje će u jednom trenutku otkucati sve Šekspirove radove (ako mu je dato beskonačno puno vremena). Problem sa ovom teoremom je taj da je verovatnoća da pomenuti majmun zaista iskuca Šekspira tako niska, da je jako mala verovatnoća da bi Hamlet postojao čak i da je kucanje počeo sa Velikim praskom.

Pojednostavimo, majmun nasumično kuca na mašini koja ima 30 slova i razmak (31 mogućnost). Koja je verovatnoća da otkuca: “biti ili ne biti pitanje je sad”? Ta rečenica ima 31 karakter. Dakle, verovatnoća da majmun otkuca ovu rečenicu tačno je 1 u 31³¹ pokušaja.

Poenta ovog primera nije da nas zbuni, nego da demonstrira da rešavanje čistom silom (brute force) nije razumna strategija za nasumično stizanje do “biti ili ne biti pitanje je sad”. Bolji način je genetski algoritam, sa kojim možemo početi od nasumičnih rečenica i naći rešenje simulirajući evoluciju. Verovatno izgleda čudno što genetskim algoritmom pokušavamo da dobijemo rečenicu koju već znamo, ali koristimo ovaj primer samo da bi objasnili kako algoritam funkcioniše. Kada to uradimo, možemo ga koristiti za neke zaista korisne stvari: nalaženje nepoznatih rešenja raznih problema.

Prirodna selekcija

Pre nego što prođemo kroz genetski algoritam, opišimo tri osnovna principa Darvinove teorije evolucije koji će nam biti potrebni za naš algoritam. Da bi se prirodna selekcija dešavala kao u prirodi, ovi elementi moraju biti prisutni:

Nasleđivanje

Mora postojati proces u kojem deca poprimaju osobine svojih roditelja. Ako jedinka uspe da se razmnožava, onda se njene osobine prenose na njenu decu u sledećoj generaciji jedinki.

Različitost

Mora postojati različitost u osobinama koje postoje u populaciji, ili način na koji različitost može da se izazove. Na primer, postoji populacija buba u kojoj su sve bube apsolutno iste: ista boja, ista veličina, isti raspon krila, sve isto. Bez neke različitosti u populaciji, deca će uvek ostati ista sa roditeljima, i međusobno. Nove kombinacije osobina ne mogu da se dese i evolucija nema smisla.

Selekcija

Mora postojati mehanizam kojim neki deo populacije ima šanse da bude roditelj i prenese dalje genetsku informaciju a neki ne. Ovo se često naziva preživljavanje najprilagođenijih. Na primer, recimo da postoji populacija gazela koje jure lavovi svaki dan. Brže gazele imaju više šanse da pobegnu lavovima i samim tim da žive duže i da se razmnožavaju i prenesu svoje gene na njihovu decu. Termin prilagodljiv, međutim, može izazvati zabunu. To ne znači da je data jedinka bolja (to je subjektivni osećaj). Znači da je bliža rešenju za dati problem. Na primer, prilagodljiviji majmun za naš problem je onaj koji je otkucao rečenicu bližu: “biti ili ne biti pitanje je sad”.

Sada, naoružani osnovnim znanjem Darvinove teorije evolucije, možemo da pričamo o tome kako genetski algoritmi rade.

Inicijalna populacija

U kontekstu problema kucajućeg majmuna, populacija rečenica. Nameće se pitanje: kakva je inicijalna populacija? Ovde je važan Darvinov princip različitosti. Pojednostavimo, ako hoćemo da evoluiramo reč pas i imamo inicijalnu popuaciju 3 reči:

ker

loš

sat

Svakako, postoji različitost u ove tri reči, ali ako izmešamo slova iz tih reči nikada nećemo dobiti reč pas. Ne postoji dovoljno velika različitost da bi optimalno rešenje evoluiralo. Međutim, ako bismo imali populaciju od hiljadu reči, sve generisane nasumično, verovatno će neke reči imati p kao prvi karakter, neke a kao drugi, neke s kao treći. Velika populacija će nam verovatno doneti dovoljnu različitost da kvalitetno rešenje evoluira. Dakle: Kreiraj populaciju nasumično generisanih jedinki.

Ovo nas dovodi do drugog važnog pitanja: šta je jedinka? Jednostavno, jedinka je jedno rešenje problema, na našem primeru jedna rečenica koju je majmun iskucao. Svaka jedinka ima virtuelni DNK, skup gena (koje izazivaju neke osobine) koje opisuju kako jedinka izgleda ili se ponaša. U slučaju kucajućeg majmuna, DNK je prosto niz karaktera.

U genetici, postoji važna razlika između koncepta genotipa i fenotipa. Genetski kod je genotip jedinke. To je ono što se prenosi sa generacije na generaciju. Fenotip, međutim, je izraz tih genetskih podataka u okruženju. Na primer, jedan izraz je boja očiju, i ona zavisi od jednog (ili više) gena iz genotipa. Ili brzina već pomenute gazele.

Fina stvar našeg primera majmuna koji kuca je to što nema razlike između genotipa i fenotipa. DNK je niz karaktera i njegov izraz je rečenica, sastavljena od tih karaktera.

Selekcija

Ovde primenjujemo Darvinove principe selekcije. Treba da ocenimo populaciju i odlučimo koji članovi su dovoljno prilagođeni da budu izabrani kao roditelji za sledeću generaciju. Proces izbora možemo podeliti na dva dela.

Ocena prilagodljivosti

Da bi naš genetski algoritam funkcionisao, moramo da stvorimo nešto što se zove funkcija prilagođenja. Funkcija daje broj koji opisuje koliko je prilagođena data jedinka. Ovo, naravno, ne liči na pravi svet. Jedinke nemaju skor, one jednostavno prežive ili ne. Ali za naš genetski algoritam, mi treba da budemo sposobni da brojem ocenimo svako dato rešenje.

Pogledajmo opet našeg kucajućeg majmuna, i opet, pojednostavimo scenario tako da tražimo reč pas. Imamo sledeće reči u populaciji: par, kos, loš. Očigledno, par je najprilagođenija reč jer ima dva tačna karaktera, kos samo jedan, loš nijedan. Nameće nam se funkcija prilagođenja:

Takođe, možemo menjati brzinu rasta ove funkcije, na primer:

Ili

Izbor jedinki za razmnožavanje

Kad je prilagođenje izračunato za sve jedinke, možemo da biramo koje jedinke su prihvatljive da budu roditelji. Postoji nekoliko različitih pristupa. Na primer, možemo da prihvatimo elitistički metod i kažemo da su otac i majka cele sledeće generacije dve najprilagođenije jedinke, međutim to je u suprotnosti sa Darvinovim principom raznovrsnosti. Ako se samo dve jedinke iz populacije razmnožavaju, sledeća generacija će imati malu raznovrsnost i to može zakočiti proces evolucije. Umesto toga možemo da kažemo da će da se razmnožava veći deo, recimo 50% populacije, na primer 500 od 1000. Ovo takođe neće doneti optimalne rezultate. U ovom slučaju, najbolje jedinke će imati istu verovatnoću da budu izabrane kao roditelj kao one pri sredini liste. I zašto jedinka 500 ima šansu da se razmnožava a jedinka 501 nema?

Bolje rešenje je upotreba metoda zasnovanog na verovatnoći, koji možemo zvati kolo sreće, ili češće rulet metoda. Ova metoda garantuje da su najbolji elementi najčešće razmnožavati. Takođe, ne eliminiše različitost u populaciji. Čak i najmanje prilagođena jedinka ima šanse da prenese njenu genetsku informaciju u sledeću generaciju. Moguće je (i često je to slučaj) da čak i najmanje prilagođene jedinke imaju mali deo genetskog koda koji je zaista koristan i ne bi trebalo biti kompletno eliminisan iz populacije. Recimo da imamo sledeće jedinke:

A: biti ili ne biti pitanje je koš

B: biti ili ne biti pitanje je los

C: đđđđđđđđđđđđđđđđđđđđđđđđđđđđsad

Kao što vidimo, jedinke A i B su mnogo prilagođenije, ali nijedna od njih nema potrebne karaktere za kraj rečenice. Jedinka C, iako vrlo malo prilagođena, ima dobre genetske podatke za kraj rečenice. Tako da, iako želimo da A i B stvore većinu sledeće generacije, želimo i da C ima malu šansu da učestvuje u procesu razmnožavanja.

Razmnožavanje

Sada kad smo odlučili kako biramo roditelje, treba da odredimo kako da koristimo razmnožavanje da napravimo sledeću generaciju populacije, pazeći na Darvinov princip nasleđivanja – da deca nasleđuju osobine od roditelja. Ponovo, postoji nekoliko različitih tehnika koje bi mogli iskoristiti. Na primer, razumna strategija je aseksualno razmnožavanje, što znači da biramo samo jednog roditelja i kreiramo dete koje je kopija roditelja. Standardan pristup je izbor dva roditelja i kreiranje deteta koje ima deo genetskog koda jednog i deo drugog roditelja.

Ukrštanje

Ukrštanjem stvaramo genetski kod deteta od kodova roditelja. Svaki gen u detetu je tačna kopija gena ili prvog ili drugog roditelja. Recimo da imamo sledeće jedinke koje se ukrštaju:

A: biririli ne bili pisanje je kad

B: biti ili ne bitifpitfnje je sat

Opet, možemo izabrati gene deteta iz gena roditelja na različite načine. Na primer, za svaki gen nasumično biramo da li će biti preuzet od prve ili druge jedinke. Ili možemo reći do gena x svi geni se uzimaju od jedinke A, posle njega od jedinke B. Ovo je prihvatljivije u slučajevima kada je redosled gena važan za fenotip (osobine) jedinke. Ukrštanjem na prvi način od ova dve jedinke može nastati:

C: bitirili ne bili pitanje je kad

C: biri ili ne bili pisanje je sad

C: biririli ne bilifpisfnje je kat

itd.

Mutacija

Kada smo kreirali DNK deteta, radimo poslednji korak pre ubacivanja deteta u novu generaciju – mutaciju. Ona postoji zbog Darvinovog principa različitosti. Kreirali smo inicijalnu populaciju nasumično, trudeći se da počnemo sa različitim jedinkama. Međutim, postoji granica koliko različitosti može da bude u prvoj generaciji. Takođe vremenom, izborom najboljih i njihovim razmnožavanjem, različitost će se smanjivati kako se osobine jedinki u populaciji budu približavale jer su nastajale od zajedničkih roditelja u prošlosti, i mutacija nam dozvoljava unesemo dodatnu različitost u sam evolucioni proces.

Mutacija se opisuje procentima. Određeni genetski algoritam može imati mutaciju od 5%, ili 1%, ili 0.1% itd. Pretpostavimo da smo završili sa ukrštanjem i imamo dete:

C: biri ili ne bili pisanje je sad

Ako imamo mutaciju 1%, to znači da za svaki gen (u ovom slučaju karakter) postoji 1% šanse da mutira. Šta znači da karakter mutira? U ovom slučaju, definišemo da se umesto njega pojavi nasumični karakter. 1% je mala mutacija, i u većini slučajeva u našem primeru neće se ni desiti (zapravo šansa da se desi bar u jednom genu u našem primeru je 1 – 0,99³¹ = 26,8%). Međutim, kada se desi karakter je zamenjen drugim, nasumičnim karakterom.

U nekim drugim primenama, mutacija ne bi morala značiti zamenu gena nasumičnim genom, nego mala promena gena. Na primer, ako je gen predstavljen realnim brojem, mutacija bi mogla biti dodavanje ili oduzimanje nasumičnog malog broja. U svakom slučaju, mutacija menja izabrani gen.

Verovatnoća mutacije može jako uticati na ponašanje sistema. Veoma visoka mutacija (na primer 80%) bi negirala sam evolucioni proces. Ako je većina gena deteta kreirana nasumično, onda ne možemo garantovati da će se prilagođeniji geni dešavati češće u sledećim generacijama. Premala mutacija bi mogla da uguši evoluciju nedostatkom različitosti.

Proces izbora i reprodukcije se ponavlja iznova, sve dok ne dobijemo novu populaciju od n jedinki. Tada nova populacija postaje trenutna populacija, u kojoj ocenjujemo prilagođenje i izvršavamo izbor i razmnožavanje.

Sada kada smo opisali kako genetski algoritam radi, možemo da idemo dalje i pogledamo kako možemo da ga iskoristimo da treniramo neuralne mreže. Stižemo do same teme ovog rada, neuro-evolucije sa menjajućim topologijama.