Optimalisering av nettverkstopologi.
Eit Nevralt Nett (NN) er ein veldig forenkla modell av eit biologisk nervesystem beståande av modell-nevroner som kommuniserer med kvarandre. Eit slikt nett kan vi bruka til mange ting, for eksempel mønstergjenkjenning, og talegjenkjenning. Kor godt det fungerer er avgengig av mange ting, inkludert topologien, dvs. korleis nevronenen i nettet er kobla saman og kor mange det er av dei.
Her skal vi sjå på ein bestemt måte å finna den beste topologien på, nemlig Genetiske Algoritmar. Ein Genetisk Algoritme etterliknar evolusjonen i naturen. Og sidan hjernen vår har utvikla seg gjennom evolusjon, og sidan det er grunn til å tru at dei viktigaste strukturane i hjernen er bestemt av genene våre, så er det freistande å prøva å la ein GA utvikla nevrale nett.
EIT ENKELT EKSEMPEL:
Det første vi må gjera for å få det til, er ein måte å representera strukturen i eit nevralt nett som eit kromoson, dvs. som ein streng som vi kan la den genetiske algoritmen virka på. Den enklaste måten å gjera det på er å bruka nettets koblingsmatrise.
Hvis vi nummererer kvart nevron i eit nett frå 1 til N, der N er det totale antalet, så kan vi laga oss ein N x N matrise som fortel kva nevroner som er kobla til kva. La oss sjå på eit enkelt eksempel med 8 nevroner: tre input, tre skjulte og to output. Det gir oss totalt N = 8 nevroner. Den enklaste (og vanligaste) konfigurasjonen er eit såkalt feedforward nett. Det ser slik ut: (Alle koblingar går frå venstre mot høgre)
Figur: Eit feedforward nett. Alle input-noder er kobla til alle skjulte nodar, som igjen er kobla til alle output-nodar.
Koblingsmatrisa til dette nettet ser slik ut: (eit ett-tal betyr at koblingen er "på", 0 betyr ingen kobling)
På venstre sida har vi "frå"-nevronane, og på høgre sida "til"-nevronane. Den nederste raden er koblingane frå nevron nr. 1, det nest-nederste frå nr 2 osv. Når felt nr. 4,5 og 6 er på så betyr dette at nevron nr. 1 er kobla vidare til nevron nr 4, 5 og 6. No kan vi "bretta ut" denne matrisa til ein streng ved å la rad 1 bli første del av strengen, rad 2 den neste osv. Då får vi denne strengen, eller det som vi kallar et kromosom:
(0000000000000000000000110000001100000011000111000001110000011100)
Men det er mange måtar å kobla eit nett med åtte nevroner på. Anta at vi går baklengs no og startar med dette kromosomet.
(0000000000000000000100110000000000000111000101000001010000010100)
Hvis vi brettar tilbake får vi følgande koblingsmatrise:
Denne matrisa representerer et nett som ser slik ut:
Merk at node nr. 5 hverken har kobling inn eller ut. Det betyr i praksis at den ikkje eksisterer. Dette er ikkje eit feedforward nett, sidan vi har koblingar mellom nevron 4 og 6 i begger retningar, altså ein loop. Og det kan vera lurt i noen tilfelle. For å testa kva som er best, trenar vi dei først opp på eit sett med treningsdata, og så testar vi dei på eit sett med testdata. Det som presterer best på treningssettet får best Fitness.
KRYSSING:
Når alle nett er testa, har vi fitness-verdiar på alle kromosomene våre, og då kan vi starta den Genetiske Algoritmen. Det første vi vil gjera då er å kryssa / mutera kromosomene, og få nye kromosomer. Eksempelvis kan ein krysning av kromosom ein og to skje mellom plass 31 og 32. Då får det nye kromosoment altså 31 gener frå det eine (det gule) og dei 33 siste frå det andre (det grøne) Kromosomet vårt vil i så fall bli sjåande slik ut:
(0000000000000000000100110000000100000011000111000001110000011100)
Det nye kromosomet blir til ei matrise som ser slik ut.
Og denne matrisa representerer eit nytt nett som ser slik ut.
Vi har fått tilbake alle koblingane til nevron nr. 5, pluss ein av dei frå dette nevronet, slik at no lever dette nevronet. (Merk at hvis krysningspunktet hadde vore mellom plass 32 og 33 i kromosoma, så hadde vi ikkje fått med denne siste koblinga, og då hadde ikkje nevron nr 5 ha vore bruk for) Men vi har mista koblinga frå nevron 4 til nevron 6 slik at no er loopen borte. Så dette er igjen eit feedforward-nett, men eit som egentlig skulle ha vore tegna med to skjulte lag.
MUTASJONAR:
Den enklaste form for mutasjon vi kan gjera er å endra ein 1 til ein 0 eller omvendt. Dette svarar til å fjerna ein eksisterande kobling eller laga ein ny kobling. Men hvis vi nøyer oss med det, så får vi alltid eit nett med 8 nodar eller mindre, og det er slett ikkje sikkert det er det optimale. Derfor kan det vera lurt å ha ein ny type mutasjon som enten fjernar ein node, eller lagar ein ny. Det kan vi gjerna ved å sletta ei rad og ei kolonne i koblingsmatrisa, eller å setta inn ein rad og ei kolonne.
Vi kan også løysa dette ved å ha kromosomer med ulik lengde i populasjonen vår, og innføra restriksjonar på kryssing. Dette svarer til ulike "artar" som ikkje blandar seg. Eit anna alternativ er å rett og slett kjøre algoritmen mange gonger med ulike lengde på kromsosomene. Men dette virkar litt uelegant!
FITNESS
Når vi utviklar nettverkstopologi med Genetiske Algoritmar, så har vi lagt trening av nettverk inn under denne GA. Det betyr at kvar gong vi treng å finna ein fitness-verdi for eit nytt kromosom, så må vi "pakka ut" kromosomet på denne måten, og konstruera eit Nevralt Nett som så må trenast og testast. Vi kjører altså ein læringsalgoritme på nettet, og så testar vi det på eit (for nettet) ukjent datasett. Og det er kor godt det scorar på denne testen som avgjer fitness.
EVOLUSJONEN
:Gjennom å gjera dette gjentatte gonger, gjennom mange generasjonar, havnar vi til slutt opp med ein nettverksstruktur som fungerer best i forhold til den gitte oppgåva. Poenget er at to ulike datasett kan gi heilt ulike nettverkstopologiar. Slik kan ei kjøring sjå ut:
Figur: her har den Genetiske Algoritme kjørt i 240 generasjonar, og vi ser korleis fitness har auka i rykk og napp.
Denne måten kan fungera på små nett. Men det er fleire ulemper. For det første er mange nett ganske luftige. Dei har mange nullar i koblingsmatrisa, og det kan gi litt ineffektiv algoritme. For det andre har vi ingen garanti for at eit tilfeldig kromosom er kobla saman i det heile. Det kan godt henda at det er nodar som er isolerte, eller maglar output/input, og i verste fall er ikkje inputnodane kobla til output, og nettet er ubrukelig.
ALTERNATIVE KODINGAR:
Det første problemet kan vi løysa ved å laga ein ny representasjon. Hvis vi feks har ein struktur som er slik:
[1,4,5,6; 2,4,5,6;3,4,5,6;4,7,8;5,7,8;6,7,8]
For å dekoda dette kromosomet les vi bare frå venstre mot høgre til første semikolon: node 1 koblar til node 4,5 og 6. Node 2 koblar til dei same, osv. Då ser vi at dette er det same nettet som i den øverste figuren. Men no har vi skaffa oss fleire problem! For det første blir kryssing meir komplisert, og for det andre er ikkje kromosomene av samme lengde.
Det andre problemet kan vi løysa enten ved å leggja inn meir logikk i krysnings- og mutasjons-operatorane våre, slik at dei alltid produserer samankobla nett, eller vi kan ha ein enkel test på grad av samankobling før vi startar trening og testing av dei resulterande netta. Dette er det mest naturlige. For i verkeligheten vil mange mutasjonar vera "ubrukelige", og det oppdagar naturen fort. (dei dør). På same måten kan vi luka ut ukobla nett før vi prøver å trena dei opp, for det tar lang tid.
FOR MYKJE KOMPLEKSITET:
Men så spørs det om det er slik naturen har løyst oppgaven med å laga struktur i dei biologiske nevrale netta. Og svaret er at det har den heilt sikkert ikkje! For eksempel menneskehjernen har alt for mange koblingar i forhold til antalet gener i kromosoma våre til at det kan gå opp. Og for store nevrale nett, vil det bli ei altfor tung jobb å simulera dette. Det blir rett og slett for mykje kompleksitet. Derfor bør ei framtidig utvikling av nevrale nett med Genetiske Algoritmar ell. også prøva å etterlikna korleis hjernen utviklar seg frå unnfangelsen av. Ein måte å gjera dette på er å bruka såkalte Lindenmayersystem (også kalla L-system)