Generalisering - En sentral egenskap hos nevrale nettverk

Martin Kermit

Nevrale nettverk er en relativ ung fagdisiplin hvor den matematiske bakgrunnen har et svakt fundament i forhold til mer etablerte fagfelt innen gjenkjenning av mønstre. Statistiske metoder for klasseseparasjon og tilpasning til funksjoner er godt analysert og forstått mens et nevralt nettverk fungerer mer som en mystisk svart boks hvor man ikke kjenner virkemåten. På grunn av manglende teoretisk bakgrunn er det ofte slik at det ikke er mulig å bestemme på forhånd hvilket nevralt nettverk som vil være optimalt i forhold til en gitt problemstilling. Derfor blir gjerne den beste løsningen det nettverket som gir det beste resultatet etter prøving og feiling.

Generalisering

Selv om forskjellige nevrale nettverk har forskjellig virkemåte på ulike problemstillinger, finnes likevel en fellesnevner som man ønsker at ethvert nettverk skal ivareta, nemlig evnen til å kunne trekke en generell beslutning ut fra data som nettverket tidligere har trent seg på. Denne evnen kalles for generalisering, og er avgjørende for at nettverket skal fungere tilfredsstillende i forhold til problemstillingen nettverket er trent til å løse. Et eksempel på generalisering, er å gjenkjenne håndskrift.

Figur 1: Håndskrevne tegn som mønstre og ønsket klasseindeling Et menneske er godt trent til dette, og klarer å lese de fleste typer håndskrift uten større vansker. Mennesket klarer å abstrahere fra formen på bokstavene og fokuserer heller på sammenhengen i teksten, slik at håndskriften gir mening. For et nevralt nettverk er dette vanskelig, men ikke umulig, fordi håndskrevne bokstaver kan ha svært forskjellig form og samtidig bety det samme.

Nevrale nettverk til bruk i mønstergjenkjenning

Mønstergjenkjenning består av å finne sammenhengen mellom to datamengder. Den ene datamengden inneholder mønstre som ønskes klassifisert, og den andre mengden er klassetilhørigheten. For å bruke eksempelet med håndskrift, er mønstrene bildene av de håndskrevne bokstavene, mens klassetilhørigheten er de gjenkjente bokstavene. Dette illustreres i Figur 1.
Et nevralt nettverk som benyttes til gjenkjenning av mønstre, trenes opp til å danne et polynom som relaterer inputmønstrene til ønsket klassifisering. Det dannes så en diskriminantfunksjon, eller beslutningsflate som separerer klassene i mønsterrommet. Som regel skjer dette ved styrt læring, som består av å la det nevrale nettverket trene med mønster som har en kjent klassifisering, og så gi ‘ris’ eller ‘ros’ til nettverket etter hvert som nettverket klassifiserer galt eller riktig. Når tilstrekkelig mange av treningsmønstrene klassifiseres riktig, kan man så teste nettverket med nye mønstre som nettverket ikke har sett før. Dersom evnen til generalisering er god, vil nettverket kunne klassifisere de nye mønstrene fornuftig.

Tospiral-problemet

I denne artikkelen skal vi se på en teoretisk problemstilling som ofte hentes frem for å teste et nevralt nettverks evne til generalisering.
Problemstillingen ble første gang formulert av the MITRE corp. [1] i 1988, og refereres til i litteraturen som tospiral-problemet. Som navnet tilsier, består problemstillingen av to spiraler som slynger seg rundt hverandre i tre omløp. Fra disse to spiralene velges det ut 96 punkter spredt jevnt på hver spiral, som da utgjør data for to forskjellige mønster. Disse punktene vises i Figur 2.

Figur 2: To motsatte spiraler som utgjør hvert sitt mønster.

Treningspunktene benyttes så til trening av det nevrale nettverket. Etter at nettverket er trent tilstrekkelig, dvs. slik at nettverket klarer å klassifisere de fleste av de totalt 192 punktene som utgjør de to spiralene riktig, testes nettverket med punkter fra hele x-y planet. Nettverket vil da måtte vise sin generaliseringsevne siden det nå må ta stilling til punkter som ligger utenfor datamengden som nettverket er trent for. Dersom nettverket har en god evne til generalisering, vil punktene i planet klassifiseres til den spiralen som ligger nærmest, etter prinsippet om «nearest neighbour», på samme måte som et menneske vil oppfatte inndelingen av planet. Vi skal nå se hvordan fire forskjellige nevrale nettverk løste problemet med de to spiralene.

Back Propagation-Nettverk

Et standard Back Propagation nettverk er utvilsomt det mest benyttede nevrale nettverket, men samtidig også det mest utskjelte (i likhet med en viss programvare-gigant som vi ikke skal nevne ved navn). Backpropagation, eller bare Backprop, er et nettverk av feedforward-typen og fungerer ved at treningsdata sendes inn i nettverket og videreføres etter multiplikasjon med tilhørende vekter til et lag av nevroner for prosessering gjennom en ikkelineær funksjon. I et Backprop-nettverk er denne funksjonen, også kalt aktiveringsfunksjon, typisk en sigmoidefunksjon:
f(x) = 1/(1 + exp(- lx))

Output fra denne funksjonen benyttes enten til nettverkets totale output, eller sendes videre til et nytt nevronlag via nye vekter for videre prosessering. Dette laget kalles også for skjult lag. Fra nettverkets output beregnes så feilen i forhold til ønsket output. Denne feilen sendes så tilbake til nettverket for at vektene skal oppdateres i forhold til størrelsen på feilen.
Fordelen med et slikt nevralt nettverk, er at det er enkelt å implementere, og gir ofte brukbare resultater. Bakdelen er at det som regel tar relativt lang tid å trene opp vektene. For en bedre referanse om Backprop-nettverk, se ref. [2].
Når vi så testet Backprop-nettverket på problemet med de to spiralene, ble det trent etter en 2-10-1 struktur, altså to input som tilsvarte x og y koordinatene til de to spiralene, 10 nevroner i et mellom-liggende skjult lag, og et nevron på utgangen som gir ut enten 1 eller -1 for de to spiralene. Som ventet hadde backprop-nettverket store problemer med å lære mønstrene, og avsluttet treningen etter 200.000 iterasjoner som var stoppekravet i vår implementasjon av dette nettverket. På dette tidspunktet av treningen klassifiserte nettverket 38 av de 192 punktene galt, og testingen av hele x-y planet ga resultatet i Figur 3, hvor svart og hvit markerer de to klassene basert på de to spiralene som treningsgrunnlag for inndeling av to klasser.
Vi ser av testresultatet i Figur 3 at Backprop-nettverket ikke takler spiralenes sirkularitet, men heller prøver å trekke rette linjer som separerer klassene i mønsterrommet. Dette viser nettverkets svake generaliseringsevne.

Figur 3:Testresultat fra Backprop-nettverket anvendt på tospiralproblemet.

Shortcut-Nettverk

For å bedre Backprop-nettverkets noe ‘stive’ tankegang, designet Lang og Witbrock [3] i 1988 et Backprop-nettverk med tre mellomliggende skjulte lag etter en 2-5-5-5-1 struktur. Dette nettverket er uvanlig fordi det i tillegg har koblinger mellom alle lag som utgjør ‘snarveier’. Det betyr at nevronet i outputlaget mottar totalt 17 input som kommer fra alle lagene i nettverket. Ellers trenes nettverket på samme måte som et standard Backprop-nettverk. Filosofien var at disse ‘snarveiene’ skulle gi polynomet som dannet beslutningsflaten flere kryssledd, noe som burde gi en mer harmonisk struktur. Dette nettverket er relativt komplisert å implementere, fordi det må holdes styr på et stort antall vekter som må få det tilbakeførte feilsignalet fra riktig nevronlag. Siden ingen studenter ønsket denne oppgaven som prosjekt høsten 1997, måtte artikkelforfatteren implementere nettverket på egenhånd.
I artikkelen til Lang og Witbrock, ref. [3] rapporteres det om en tilfredsstillende løsning på tospiral-problemet med shortcut-nettverket etter 200.000 iterasjoner. Vår implementasjon av det samme nettverket stoppet allerede etter 121.000 iterasjoner, da alle de 192 treningspunktene var korrekt klassifisert til hver sin spiral. Testing med hele x-y planet vises i Figur 4, og viser at dette nettverket har en glattere beslutningsflate som skiller de to spiralene.

Figur 4: Testresultat fra Shortcut-nettverket anvendt på tospiralproblemet. Bakdelen med Shortcut-nettverket er at den fullkoblede strukturen gjør det nesten håpløst å analysere nettverkets virkemåte, samt at treningen går enda saktere enn for Backprop-nettverket. Hver iterasjon tar mellom tre og fire ganger så lang tid hos Shortcut-nettverket i forhold til standard Backpropagation.

Cascade-Correlation Nettverk

Cascade-Correlation nettverket var det første av en rekke nevrale nettverk i kategorien dynamiske nettverk, eller selvvoksende nettverk. I et selvvoksende nettverk bestemmes ikke strukturen på forhånd, men nettverket legger selv til nevroner etter behov. Cascade-Correlation nettverket ble utviklet av Fahlman og Lebiere [4] i 1990 som et alternativ til Backprop-nettverket. I et Backprop-nettverk vil alle vektene oppdateres synkront, noe som fører til at alle nevronene konkurrerer om å få mest inflytelse, i stedet for å samarbeide. Problemet er at nevronene i samme lag ikke ‘ser’ hverandre, og vil derfor danse frem og tilbake uten å bestemme seg. Dette problemet er kjent som The Moving Target problem.
I et Cascade-Correlation nettverk trenes et og et nevron i hvert sitt skjulte lag ferdig, vektene fryses, og output fra det ferdigtrente nevronet føres da til output-nevronene som trenes inntil feilen ikke avtar mer. Det hektes så på et nytt nevron som mottar input fra alle tidligere eksisterende nevroner. Slik fortsetter treningen til en akseptabel feilgrense er nådd. Siden kun et nevron trenes om gangen, går treningen svært raskt, og ofte med bedre resultat enn Backprop-nettverket.
Implementasjonen av denne algoritmen er til dels tidkrevende, og er gjort av artikkelforfatteren i samarbeid med E. Nilssen, Geco-Prakla Inc. og A. Søraunet, Simrad A/S. Vår implementasjon testet på tospiral-problemet, klassifiserte alle de 192 treningspunktene korrekt, og gav testresultatet vist i Figur 5.

Figur 5: Testresultat fra Cascade-Correlation nettverket anvendt på tospiral-problemet.

Projection Pursuit Learning Nettverk

En av bakdelene ved Cascade-Correlation nettverket, er at når nevronene trenes en og en, vil hvert nevron spesialiseres for mye, og dermed ha dårlig generaliseringsevne. Hwang et. al. beskriver dette i ref. [5]. Nevronene går i metning i stedet for å arbeide i den aktive regionen av mønsterrommet. Hwang et. al presenterer derfor et alternativt nevralt nettverk, kjent som projection pursuit learning network (PPLN) [6]. Dette nettverket er utviklet med alle de positive egenskapene fra Cascade-Correlation nettverket, samt en mengde nye løsninger. PPLN er et dynamisk feedforward nettverk som bygger nye nevroner i et skjult lag en etter en. Nevronene har trenbare aktiveringsfunksjoner som beregnes optimalt i forhold til vektene til nevronet etter Gauss-Newton algoritmen. For å få nevronene til å arbeide i den aktive regionen, glattes aktiveringsfunksjonene ved bruk av normaliserte høyere ordens Hermite-polynomer. Output fra nevronene sendes så via et nytt sett vekter til output-laget av nevroner, hvor output, og dermed også feilen, beregnes. Treningen fortsetter så med å syklisk optimere vektene til det skjulte laget basert på den nylig trente aktiveringsfunksjonen, selve aktiveringsfunksjonen, og til slutt vektene til nevronene i outputlaget. Denne syklusen fortsetter til feilen ikke endres mer, og det legges så til et nytt nevron. Etter hvert som nye nevroner vokser frem, vil nettverket syklisk gå tilbake og trene tidligere nevroner som beskrevet ovenfor, slik at alle nevronene tilpasser seg hverandre på best mulig måte.

Figur 6: Testresultat fra PPLN anvendt på tospiral-problemet.

Dette nettverket har nok ikke så stor biologisk relevans, men er det mest matematisk korrekte av nettverkene beskrevet her.
Implementasjonen av dette nettverket er svært infløkt, og krever raske rutiner for Gauss-Newton og Hermite-interpolasjon, samt nøyaktig kalkulering av inverterte matriser samt beregninger av residuer. Implementasjonen er gjort etter tillatelse fra Prof. Hwang, University of Washington, som også bisto med verdifulle tips. Tospiral-problemet ble løst med 15 nevroner som benyttet Hermite-polynomer av 13de grad. Til sammenlikning av ressursbruk, vil det være urettferdig å telle antallet iterasjoner, som i dette tilfellet ligger rundt 100, fordi PPLN arbeider på en helt annen måte. Derimot viste MATLAB’s stoppeklokke at PPLN benyttet omtrent dobbelt så lang tid i sekunder som Cascade-Correlation nettverket på det samme problemet.

Konklusjon

Konklusjonen etter å ha testet fire ulike nettverk, viser ved tospiral-problemet at dynamiske nettverk er bedre egnet enn nettverk av Backpropagation-typen. Dette begrunnes i den svingete beslutningsflaten som dette problemet krever. Derimot kunne dette problemet enkelt vært løst av et nesten hvilket som helst nettverk ved bruk av fornuftig preprosessering. Dersom x-y koordinatene blir transformert til polare koordinater, r-f, vil problemet bli redusert til seks parallelle linjer, noe ethvert nevralt nettverk kunne løst med få iterasjoner. Dette understreker verdien av grundig pre-prosessering før man benytter et nevralt nettverk. Uten kjennskap til problemstillingen er det ofte vanskelig å gjøre fornuftig pre-prosessering, og et nevralt nettverk må da ha fleksibilitet nok til å kunne lære en vanskelig problemstilling med god generaliseringsevne, slik vi har sett hos PPLN.

Referanser

[1] Wieland (1988), the MITRE Corp. Not published.

[2] Zurada (1992) Introduction to Artificial Neural Systems, West publishing company

[3] Lang and Witbrock (1988) «Learning to tell Two Spirals Apart» in Proceedings of the 1988 Connectionists Models Summer School, Morgan Kaufmann.

[4] Fahlman and Lebiere (1990) «The cascaded-correlation learning architecture» Advances in Neural Information Processing Systems II, edited by Touretzky, pp.524-532, Morgan Kaufmann.

[5] Hwang, You, Lay and Jou (1995) «What’s wrong with a cascaded correlation learning network: A projection pursuit learning perspective» IEEE Transactions on Neural Networks.

[6] Hwang, Lay, Maechler, Martin and Schimert (1994) «Regression modeling in backpropagation and projection pursuit learning» IEEE Transactions on Neural Networks, 5(3):342-353, May 1994.

HØit Nr. 1-98