Perceptronen

Redan på 1950-talet konstruerade den amerikanske forskaren Rosenblatt ett antal neurala nätverk för mönsterklassifikation, och han bevisade intressanta ting om dem. Mest berömt för eftervärlden blev den enlagrade perceptronen (eller ”perceptronen”, rätt och slätt). Vi ska här beskriva en maximalt förenklad variant av detta nätverk.

Den enlagrade perceptronen innehåller, som namnet antyder, bara ett lager av förbindelser, eller med andra ord två lager av enheter: input- och outputlagret. Enheterna är binära, dvs. deras aktivitet antar bara värdena 1 eller 0. De mönster som man vill klassificera skall alltså vara kodade som binära tal (uppsättningar av 1-or och 0-or). I det enklaste fallet består outputlagret av en enda nod, ”beslutsnoden” – så benämnd för att den signalerar nätverkets beslut om vilken klass den aktuella input tillhör. (Vill man klassificera i mer än två kategorier kan man använda sig av fler outputnoder, men vi behandlar inte det fallet här.) Förbindelserna mellan inputnoder Xi och beslutsnod Y har vikter wi, som från början bestäms slumpvis.



Nettoinput till beslutsnoden beräknas på vanligt sätt som summan av inputnodernas aktiviteter xi viktade med styrkan wi hos respektive förbindelser. Beslutsnoden använder sig sedan av en stegfunktion med en fix tröskel Ø för att besluta om dess aktivitet y skall vara 1 eller 0. Sammanfattningsvis gäller alltså för den enkla perceptronens signaldynamik:

y = 1 om xi wi > Ø

y = 0 om xi wi Ø

Givet att man presenterar en uppsättning inputmönster för en otränad perceptron (dvs en perceptron med slumpvisa vikter) , så ger den en bestämd utsignal, 0 eller 1, för varje enskilt mönster. Nu är det förstås inte i allmänhet så, att denna signal överensstämmer med den klassifikation man vill ha utförd. Perceptronen måste därför tränas att göra rätt. Denna träning går till så, att vikterna i nätverket ändras på ett visst sätt när nätverket gör ”fel”, dvs klassificerar på det icke önskade sättet. Närmare bestämt arbetar perceptronen enligt följande enkla inlärningsregel:

(1) Om responsen är rätt, ändra ingenting.

(2) Om responsen är 1 men skulle vara 0, sänk vikterna på alla aktiva inlinjer.

(3) Om responsen är 0 men skulle vara 1, höj vikterna på alla aktiva inlinjer.

Alla höjningar och sänkningar av vikter sker med en förutbestämd kvantitet a, vars storlek bestämmer inlärningstakten.

Låt oss titta närmare på hur denna regel (”perceptronregeln”) fungerar. Om en viss insignal ger 0 som output när vi önskade att den skulle ge 1, så måste nettoinput till outputnoden vara för låg. Alltså kommer man närmare en ”riktig” respons genom att öka vikterna på alla de införbindelser där mönstret ifråga hade en 1:a i inputnoden (de aktiva inlinjerna). Att öka vikterna på övriga linjer skulle däremot göra vare sig till eller från för responsen för just detta mönster. Det är inte svårt att se att man, om man bara har att göra med ett inputmönster, vid upprepad presentation av mönstret snart får en riktig klassifikation genom att de relevanta vikterna på detta sätt gradvis ökas. Motsvarande resonemang gäller om responsen är 1 men skulle vara 0.

Problemet är bara att man har att göra med många mönster, och de ska läras in på samma gång! Felkorrektionen för ett mönster kommer då att påverka svaret på många andra mönster. Det är inte på något sätt självklart att alla de höjningar och sänkningar av vikter, som blir resultatet av upprepade applikationer av perceptronens inlärningsregel på alla dessa mönster, leder till att alla – eller ens något av dem – någonsin kommer att klassificeras korrekt. Rosenblatts minnesvärda insats var nu att bevisa att perceptronen faktiskt alltid lär sig att klassificera korrekt, förutsatt att klassifikationen ligger inom dess logiska möjligheter. Förbehållet är lika viktigt (och lika berömt) som den positiva delen av resultatet, men låt oss spara det en stund.

Rosenblatts resultat säger, annorlunda uttryckt, att om vi har en uppsättning mönster som är indelade i två klasser, och det finns någon tänkbar tilldelning av vikter till perceptronen som skulle separera mönstren i just de klasserna, så kommer perceptronen alltid att hitta en sådan vikttilldelning om man tränar den enligt ovan. Detta är ett exempel på ett konvergensresultat för inlärning: det säger att om det finns en logiskt möjlig lösning av ett visst problem, så kommer nätverkets vikter, givet en viss inlärningsprocedur, att konvergera mot en sådan lösning. Vi ska senare möta fler sådana konvergensresultat. Låt oss nu istället titta på förbehållet, ”om det finns någon tänkbar tilldelning av vikter som...”. För att på ett enkelt och åskådligt sätt förstå vad detta villkor innebär ska vi ta en titt på en ytterst simpel perceptron som har bara två inputnoder.



Denna maskin har bara fyra möjliga inputs – nämligen (1,1), (1,0), (0,1) och (0,0). Dessa inputs kan man vilja klassificera på olika sätt. Kanske vill man av någon anledning sätta etiketten 1 på input (1,1) och etiketten 0 på de övriga. Det är inte svårt att se att det finns många logiskt möjliga lösningar av detta problem. Exempelvis skulle en perceptron med w1 = w2 = 2/3 klassificera alla inputs på det önskade sättet. En annan fråga är om man kan träna perceptronen till denna lösning. Rosenblatts resultat säger just, att alltid man kan göra det, eftersom det är en logiskt möjlig lösning.

Om man har lite logisk skolning inser man snabbt att det är praktiskt att tänka sig inputs till vår mini-perceptron som olika sanningsvärdestilldelningar till två satser, med 1 = SANN och 0 = FALSK. En given klassifikation av de fyra inputs kan då uppfattas som en sanningsfunktion. Exempelvis motsvaras den nyss nämnda klassifikationen, som ger utsignalen 1 för inputmönstret (1,1) men 0 för övriga, av sanningsfunktionen ”OCH”. Satsen ”p och q” är ju sann, om och endast både p och q är sanna: (S,S) ger S, men (S,F), (F,S) och (F,F) ger F.

Det exempel som vi närmast skall titta på kan analogt uppfattas som sanningsfunktionen för ”uteslutande eller” (eXclusive OR, XOR). Det är den sanningsfunktion som tilldelar (S,F) och (F,S) värdet S, men som i övrigt ger värdet F. Satsen ”p uteslutande-eller q” kräver med andra ord för att vara sann, att en av de två delsatserna skall vara sann, men inte båda. I termer av klassifikation av mönster vill vi alltså att perceptronen ska ge utsignalen 1 för inputmönstren (1,0) och (0,1), men 0 för de två övriga. Vi ska nu bevisa att detta är logiskt omöjligt, och för tydlighetens skull ska vi ge två olika bevis.


Direkt bevis


Antag att det finns två vikter w1 och w2 som ger den önskade klassifikationen. Villkoret för att perceptronen ska ge utsignal 1 är, enligt ovan, att xi wi > Ø. För de två inputs (1,0) och (0,1), som ju ska ge denna utsignal, ger detta:

1 · w1 + 0 · w2 > Ø;
Alltså: w1 > Ø

0 · w1 + 1 · w2 > Ø;
Alltså: w2 > Ø

Nu kan vi förutsätta att Ø 0, för annars skulle input (0,0) också ge output 1. w1 och w2 är alltså > 0. För input (1,1), som skall ge output 0, får vi därför

1 · w1 + 1 · w2 = w1 + w2 > Ø

vilket ger output 1, dvs fel respons.

Vårt ursprungliga antagande var alltså felaktigt. Det går inte ens teoretiskt att hitta någon viktuppsättning som genomför den önskade klassifikationen. Givetvis kan man då inte heller träna perceptronen till att hitta en sådan!


Geometriskt bevis

Det geometriska beviset är mycket användbart eftersom man med dess hjälp kan införa de viktiga begreppen beslutsregion, beslutsgräns och lineär separerbarhet. Man utgår i detta bevis från en representation av inputs i ett cartesianskt koordinatsystem med axlarna x1 och x2, dvs aktivitetsnivåerna i de två inputnoderna. Inputs blir då fyra punkter på en enhetskvadrat:


Betrakta nu återigen perceptronens aktiveringsfunktion, alltså

y = 1 om xi wi > Ø

y = 0 om xi wi Ø

(där q ju är en konstant). Givet två bestämda vikter w1 och w2 avgränsar de här två villkoren var sin beslutsregion i x1-x2-planet, nämligen mängden av de inputs (x1, x2) som uppfyller den första respektive den andra olikheten. Gränsen mellan dessa två beslutsregioner, beslutsgränsen, definieras av villkoret

xi wi = Ø, dvs. x1 w1 + x2 w2 = Ø

(Att beslutsgränsen hör till den ena beslutsregionen hindrar inte att den samtidigt är en gräns mot den andra.) Hur ser nu den här beslutsgränsen ut? Jo, skriver man den på formen

x2 = – x1 · w1/w2 + Ø/w2

inser man (om inte förr) att den är en rät linje, som dessutom (sätt x1 = 0!) skär x2-axeln i punkten Ø/w2. På samma sätt inses att linjen skär x1-axeln i punkten Ø/w1. Linjen kanske t.ex. ser ut ungefär så här:

Linjen för en godtycklig perceptron kan naturligtvis ligga precis var som helst i koordinatsystemet, men alla linjer som kan tänkas lösa XOR-problemet måste ju passera igenom enhetskvadraten på något sätt. Poängen med hela det här framställningssättet är nu att man med hjälp av sin geometriska intuition lättinser, att det inte går att dra linjen så att den löser problemet. För hur man än drar en rät linje linje så att (0,1) och (1,0) båda ligger på dess ena sida, så kan (0,0) och (1,1) uppenbarligen inte båda hamna på den andra sidan! Det finns med andra ord inga vikter w1 och w2 som löser problemet.

Den enkla perceptronen med två inputnoder ger sammnfattningsvis alltid en rät linje som beslutsgräns, och om det inte går att dra en sådan linje mellan de två klasser som man vill separera, så kan inte perceptronen göra separationen ens med ”specialdesignade” vikter, än mindre genom inlärning. XOR-problemet är det enklaste exemplet på sådana icke linjärt separerbara klasser av mönster.

Begreppet linjär separerbarhet kan på ett självklart sätt generaliseras till mönster med fler dimensioner än två, och därmed till enkla perceptroner med flera inputnoder. I fallet med tre inputdimensioner motsvaras således den räta beslutslinjen av ett beslutsplan

x1 w1 + x2 w2 + x3 w3 = Ø

Allt som ligger på ena sidan om detta plan klassificeras av perceptronen ifråga som tillhörigt den ena klassen; allt på den andra sidan av planet hamnar i den andra klassen. Klasser som inte kan separeras av ett dylikt plan är inte lineärt separerbara, i den allmänna betydelsen av denna term, och kan inte separareras av en enkel perceptron.

Till det här utbildningspaketet från Filosofiska institutionen hör också en datormodell av den enkla perceptronen, som Du kan ladda ner och köra på Din egen dator (om Du har en Macintosh, vill säga). Den har sju inputs och klassificerar LCD-siffror kodade som sjusiffriga binära tal. Också i den illustrationen stöter Du på icke lineärt separerbara problem, som alltså är analoga med XOR-problemet fast av högre dimensioner (beslutslinjer motsvaras av sexdimensionella besluts-hyperplan).

Många klassifikationsproblem i levande livet är av icke-linjär karaktär, dvs man behöver dra beslutsgränser som inte är linjer, plan eller hyperplan. Dessutom är det så att inte bara perceptroner, utan också flera klassiska matematiska metoder, enkelt klarar av alla lineärt separerbara problem. Det är alltså motiverat att undra vad man egentligen ska ha perceptroner till!

Det faktum att Rosenblatts enkla perceptroner inte kunde lösa icke lineärt separarerbara problem ledde också till att ledande företrädare för AI-forskningen på 1960-talet uttryckte starka tvivel på de artificiella neurala nätverkens möjligheter. Visserligen hade redan Rosenblatt experimenterat med kraftfullare nätverk som inte hade samma principiella begränsning, utan som också kunde dra mer komplicerade (icke-linjära) beslutsgränser, men han lyckades inte bevisa några viktiga konvergensresultat för dem. Han kunde med andra ord inte bevisa, att hans kraftfullare nätverk kunde tränas till att hitta någon av de icke-linjära lösningar som de i teorin var i stånd att leverera. Först när flera forskare på 1980-talet oberoende av varandra upptäckte ”back-propagation”-algoritmen för flerlagrade nätverk med kontinuerliga, sigmoida aktiveringsfunktioner stod det klart att Rosenblatts intuitioner hade varit riktiga.

De enkla perceptronerna skall ses som ett utvecklingssteg i riktning mot dessa mer komplicerade och verkligt användbara maskiner. Men de har inte bara ett historiskt intresse; de är också en naturlig pedagogisk inkörsport till ANN-området som helhet, och det är därför som vi ägnat dem så pass stor uppmärksamhet.

Till början av sidan
Tillbaka till sidan Artificiella Neurala Nätverk - en kort introduktion

© 2001 Helge Malmgren. Denna sida senast uppdaterad 2 juni 2001 av Helge Malmgren.