SOM - den självorganiserande kartan

Få artificiella neurala nätverk, med undantag av de olika feed-forwardnäten med varianter av algoritmen ”back propagation of error”, har fått så många praktiska tillämpningar som Teuvo Kohonens ”Self-Organising Map”, eller SOM. Detta nätverk bygger på idén att representera de väsentliga likheterna mellan inputs med hjälp av färre dimensioner - oftast två - än vad inputs har från början. För att uppnå detta använder Kohonen ett nätverk där noderna har en rumslig (t.ex. tvådimensionell) närhetsrelation till varandra. Träningsalgoritmen jämkar vikterna hos rumsligt näraliggande noder till att också ligga nära varann, vilket resulterar i att liknande inputs till slut representeras intill varann i nätverket: en karta över inputdomänen har konstruerats. Det finns många metoder för oövervakad klassifikation (“clustering” av data), men SOM har unika egenskaper, kanske särskilt som instrument för visualisering av strukturen i data.

Låt oss se på några detaljer i detta användbara nätverk (det kan vara en fördel att först ha läst igenom avsnittet Vektorer och matriser). SOM har två lager enheter. Inputlagret har lika många noder som antalet komponenter i inputvektorerna. Varje inputnod har förbindelser med varje nod i det andra, kompetitiva lagret (också kallat Kohonenlagret), och vikterna mellan lagren slumpas ut vid träningens start. Kohonenlagret är som sagt organiserat i en rumslig struktur. Vi ska nu beskriva först hur det aktiveras och sedan hur den inlärning går till, som gör SOM till en rumslig karta över inputmängden.

SOM aktiveras som följer: när en inputvektor presenteras får den av Kohonen-noderna aktiviteten 1 vars vektor av vikter från inputlagret mest liknar inputvektorn ifråga, medan alla de andra noderna får aktiviteten 0. (Kohonen-noderna sägs vara “kompetetiva” just därför att de på detta sätt konkurrerar om inputs.) Maximal likhet definieras genom att det euklidiska avståndet mellan vektorerna (mätt med Pythagoras’ sats!) ska vara så litet som möjligt. Vi säger att den Kohonen-nod som får aktiviteten 1 (”vinnarnoden”) representerar input ifråga; andra vanliga beskrivningar är att vinnarnodens viktvektor är en ”kodvektor” eller ”typvektor” för denna input. Närmast en illustration av ett SOM med 5 inputs och 64 (8x8) kompetitiva enheter. Det har just fått en input, och en vinnarnod har utsetts:

 

Uppenbarligen kan en Kohonen-nod i princip vara en kodvektor för en hel grupp av inputs. Man talar om ”vektorkvantisering”, eftersom en potentiellt oändlig mängd inputvektorer på detta sätt kan få en förenklad representation i en ändlig mängd av typvektorer. Metoden anknyter till den teori om mental representation som brukar kallas ”templat-teorin”, enligt vilken igenkänning av mönster i den mänskliga hjärnan just tillgår som så att ett inputmönster matchas med avseende på sin likhet med ett antal typvektorer (templates). Men kan detta gå till exakt på det sättet som Kohonen stipulerar för sitt SOM? Beräknar det mänskliga nervsystemet euklidiskt avstånd mellan en inputvektor och en uppsättning viktvektorer, och utser det en vinnare där detta avstånd är minst?

Nej, den grundläggande algoritm som används i SOM (och för övrigt även i LVQ, Lerning Vector Quantisation) har knappast en exakt biologisk motsvarighet, men det är lätt att ange en alternativ algoritm som gör ungefär samma sak. Under förutsättning att alla inblandade vektorer har någorlunda lika längd speglar nämligen storleken på skalärprodukterna mellan inputvektorn och de olika viktvektorerna ganska bra euklidisk närhet mellan inputvektorn och dessa viktvektorer. Tänk på formeln för sambandet mellan skalärprodukt och vinkeln a mellan två vektorer v1 och v2 som har längden l(v1) respektive l(v2):

v1 * v2 = l(v1) · l(v2) · cos

och på att cos har maximum när = 0. Detta betyder, allt annat lika, att två vektorer som bildar en liten vinkel med varann (dvs. pekar åt ungefär samma håll) har en större skalärprodukt än om de bildar en större vinkel. Överensstämmelsen mellan skalärprodukt och euklidisk närhet blir exakt om alla vektorer är normerade till en viss längd, exempelvis 1. Om input har två dimensioner betyder normering till enhetslängden att alla vektorer ligger på enhetscirkeln. Vinkeln mellan två vektorer på denna cirkel bestämmer med andra ord entydigt deras skalärprodukt.

Låt oss tänka oss att vi ger normerade inputvektorer till ett SOM där vi bytt ut det vanliga Kohonen-lagret mot ett som fungerar enligt normala ANN-principer. Skalärprodukten mellan inputvektorn och en viktvektor som tillhör en Kohonen-nod är ju då inget annat än den nettoinput som kommer till denna nod! Om noderna har en positivt linjär eller sigmoid aktiveringsfunktion, kommer den nod i Kohonenlagret vars viktvektor ligger närmast inputvektorn därför att få den högsta aktiviteten. Det är sedan inte svårt att designa en biologiskt någorlunda realistisk algoritm som genom ömsesidig inhibition resulterar i att just denna nod – vinnaren - slutligen får aktiviteten 1, medan övriga noder får aktiviteten 0.

Om input- och viktvektorer inte är normerade kommer det biologiska nätverket som vi just skisserat inte att fungera precis som SOM, men dess verkningssätt kommer att påminna om SOM: det kommer att göra en alternativ naturlig klassifikation.

Låt oss därmed, efter att ha givit det grundläggande funktionssättet hos Kohonen-noderna ett slags biologisk motivering, gå in på träningsalgoritmen för den självorganiserande kartan. Träningen går till som följer; steget (4) är det verkligt unika för SOM.

(1) En input presenteras
(2) En vinnare utses (minimalt avstånd mellan input och viktvektor)
(3) Vikterna hos vinnarnoden makas närmare inputvektorn ifråga
(4) Vikterna hos vinnarnodens grannar makas också (lite) närmare denna inputvektor.

En “granne” till en nod är en nod i den rumsliga omgivningen (definierad på ett specifikt sätt; flera alternativ finns) av den första.

Proceduren upprepas (med mindre och mindre steg, och med en del modifikationer och tillägg som vi inte ska gå in på här) till dess att vikterna stabiliserats.

Vad leder då detta till? Steget (3) i algoritmen gör en vinnarnod ännu bättre på att representera den input som den just “vann”, och åstadkommer (genom konkurrens bland inputs om samma nod) bland annat att varje kodvektor till slut hamnar ungefär ”i mitten” av den grupp av inputvektorer som den då representerar. Steget (4) får vinnarens grannskapsnoder att bli något bättre på att representera inputs som liknar den just aktuella, oavsett hur dåliga de var på att representera sådana inputs förut. Det uppkommer en tendens som går ut på att liknande inputs till slut kommer att representeras om inte av samma nod, så av grannar i nätverket. Det är just så som ”kartan” över inputdomänen uppkommer.

En av metodens stora fördelar är som antytts att den erbjuder inte bara en dimensionell klassificering, utan också en visualisering av klassifikationen och därmed av inputdomänen. Här är ett exempel, där ett antal (artificiella) biologiska organismer som varierar i fem dimensioner lagts ut i en 8 x 8-karta:

 

 

Exemplet finns i övningsmaterialet som en laboration. En viktig princip som man lär sig i detta övningsexempel, men som också bör nämnas här i texten, är kodningens betydelse. Beroende på vilka måttenheter man använder för de olika inputdimensionerna kan man få mycket varierande resultat av en klassifikation med SOM. (Detsamma gäller många andra algoritmer för icke-styrd klassifikation.) Man kan lätt förstå varför det är så genom att meditera över om A ligger närmast B eller C (i den euklidiska meningen) i följande exempel:

A är 2 meter lång och väger 99543 gram
B är 1,9 meter lång och väger 99500 gram
C är 1,8 meter lång och väger 99520 gram

En Kohonen-nod som får input kodad på det nämnda sättet skulle fästa mycket stor vikt vid skillnaderna i gram, och säga att B ligger längre från A än vad C gör. Kodar man däremot om metrarna till millimetrar och grammen till kilo blir resultatet naturligtvis det motsatta.

En speciellt rolig applikation av SOM är dess användning för att föreslå lösningar av ett klassiskt optimeringsproblem, nämligen TSP, the Travelling Salesman Problem. TSP innebär att man skall hitta den kortaste resvägen genom ett antal städer på en karta. För att man skall kunna använda SOM här måste städerna vara kodade med sina geometriska koordinater, inte med en avståndstabell. Man gör ett endimensionellt SOM med lika många Kohonen-noder som städer, och låter input vara = städernas respektive två koordinater. Med 13 städer (som i övningslaborationen) ser det ut så här:

 

Hur fungerar detta? Jo, SOM tenderar ju att lägga liknande inputs, och därmed också liknande kodvektorer, nära varann i kartan. Låt oss då tolka kodvektorernas vikter efter träningen som koordinater hos städer som skall besökas, och omedelbar rumslig närhet på kartan som att städerna ifråga skall besökas omedelbart efter varann! Detta ger en elegant lösning av TSP. Man kan dock behöva “maka” kodvektorerna närmare de verkliga städerna.


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.