Neural gas

Neural gas är ett artificiellt neuralt nätverk , inspirerat av den självorganiserande kartan och introducerades 1991 av Thomas Martinetz och Klaus Schulten . Neuralgasen är en enkel algoritm för att hitta optimala datarepresentationer baserat på funktionsvektorer . Algoritmen myntades som "neural gas" på grund av dynamiken hos funktionsvektorerna under anpassningsprocessen, som distribuerar sig själva som en gas i datautrymmet. Det används där datakomprimering eller vektorkvantisering är ett problem, till exempel taligenkänning , bildbehandling eller mönsterigenkänning . Som ett robust konvergerande alternativ till k-medelklustringen används det också för klusteranalys .

Algoritm

Givet en sannolikhetsfördelning $P(x)$ av datavektorer $x$ och ett ändligt antal funktionsvektorer $w_{i}, i=1,\cdots ,N$ .

Med varje tidssteg $t$ presenteras en datavektor $x$ slumpmässigt vald från ${\displaystyle P(x)} . Därefter$ bestäms avståndsordningen för egenskapsvektorerna till den givna datavektorn ${\displaystyle x} .$ Låt $i_{0}$ beteckna indexet för den närmaste egenskapsvektorn, $i_{1}$ indexet för den näst närmaste egenskapsvektorn, och $i_{N- 1}$ indexet för objektsvektorn längst bort från $x$ . Sedan anpassas varje egenskapsvektor efter

w_{i_{k}}^{t +1}=w_{i_{k}}^{t}+\varepsilon \cdot e^{-k/\lambda }\cdot (x-w_{i_{k}}^{t}),k=0 ,\cdots ,N-1

med $\varepsilon$ som anpassningsstegstorleken och $\lambda$ som det så kallade grannskapsintervallet. $\varepsilon$ och $\lambda$ reduceras med ökande $t$ . Efter tillräckligt många anpassningssteg täcker egenskapsvektorerna datautrymmet med minimalt representationsfel.

Neuralgasens anpassningssteg kan tolkas som gradientnedgång på en kostnadsfunktion . Genom att anpassa inte bara den närmaste egenskapsvektorn utan alla av dem med en stegstorlek som minskar med ökande avståndsordning, jämfört med (online) k-betyder klustring, kan en mycket mer robust konvergens av algoritmen uppnås. Neuralgasmodellen tar inte bort en nod och skapar inte heller nya noder.

Varianter

Ett antal varianter av neuralgasalgoritmen finns i litteraturen för att mildra några av dess brister. Mer anmärkningsvärt är kanske Bernd Fritzkes växande neurala gas, men man bör också nämna ytterligare utarbetningar som nätverket Growing When Required och även den inkrementellt växande neurala gasen. Ett prestationsorienterat tillvägagångssätt som undviker risken för överanpassning är Plastic Neural Gas-modellen.

Växande nervgas

Fritzke beskriver den växande neurala gasen (GNG) som en inkrementell nätverksmodell som lär sig topologiska relationer genom att använda en " Hebb -liknande inlärningsregel", bara, till skillnad från neuralgasen, har den inga parametrar som förändras över tiden och den kan kontinuerligt lärande, dvs lärande på dataströmmar. GNG har använts i stor utsträckning inom flera domäner, vilket visar dess förmåga att klustera data stegvis. GNG:n initieras med två slumpmässigt placerade noder som initialt är anslutna till en nollålderskant och vars fel är satta till 0. Eftersom indata i GNG presenteras sekventiellt en efter en, följs följande steg vid varje iteration:

Det beräknas felen (avstånden) mellan de två noderna närmast de aktuella indata.
Felet för vinnarnoden (endast den närmaste) ackumuleras.
Vinnarnoden och dess topologiska grannar (anslutna med en kant) rör sig mot den aktuella ingången med olika bråkdelar av sina respektive fel.
Åldern för alla kanter som är anslutna till vinnarnoden ökas.
Om vinnarnoden och den andra vinnaren är förbundna med en kant, sätts en sådan kant till 0. Annars skapas en kant mellan dem.
Om det finns kanter med en ålder som är större än en tröskel tas de bort. Noder utan anslutningar elimineras.
Om den aktuella iterationen är en heltalsmultipel av en fördefinierad frekvensskapande tröskel, infogas en ny nod mellan noden med det största felet (av alla) och dess topologiska granne som presenterar det högsta felet. Länken mellan de förra och de senare noderna elimineras (deras fel minskar med en given faktor) och den nya noden kopplas till dem båda. Felet för den nya noden initieras som det uppdaterade felet för den nod som hade det största felet (av alla).
Det ackumulerade felet för alla noder minskas med en given faktor.
Om stoppkriteriet inte uppfylls tar algoritmen en följande ingång. Kriteriet kan vara ett givet antal epoker, dvs ett förinställt antal gånger där all data presenteras, eller räckvidden för ett maximalt antal noder.

Inkrementellt växande neuralgas

En annan neuralgasvariant inspirerad av GNG-algoritmen är den inkrementella växande neurala gasen (IGNG). Författarna föreslår att den största fördelen med denna algoritm är att "lära sig ny data (plasticitet) utan att försämra det tidigare tränade nätverket och glömma den gamla indata (stabilitet)."

Växer när det behövs

Att ha ett nätverk med en växande uppsättning noder, som den som implementerades av GNG-algoritmen sågs som en stor fördel, men en viss begränsning av inlärningen sågs genom introduktionen av parametern λ, där nätverket bara skulle kunna växa när iterationer var en multipel av denna parameter. Förslaget för att mildra detta problem var en ny algoritm, Growing When Required-nätverket (GWR), som skulle få nätverket att växa snabbare genom att lägga till noder så snabbt som möjligt när nätverket identifierade att de befintliga noderna inte skulle beskriva ingången väl tillräckligt.

Plast neuralgas

Möjligheten att bara utöka ett nätverk kan snabbt introducera överanpassning; å andra sidan, att ta bort noder enbart på basis av ålder, som i GNG-modellen, säkerställer inte att de borttagna noderna faktiskt är oanvändbara, eftersom borttagning beror på en modellparameter som noggrant bör anpassas till "minneslängden" för strömmen av indata.

"Plastic Neural Gas"-modellen löser detta problem genom att fatta beslut om att lägga till eller ta bort noder med hjälp av en oövervakad version av korsvalidering, som styr en likvärdig uppfattning om "generaliseringsförmåga" för den oövervakade inställningen.

Även om metoderna för enbart odling endast tillgodoser scenariot med inkrementell inlärning , är förmågan att växa och krympa lämpad för det mer allmänna problemet med strömmande data .

Genomföranden

För att hitta rangordningen $i_{0},i_{1},\ldots ,i_{N-1}$ av funktionsvektorerna, involverar neuralgasalgoritmen sortering, vilket är en procedur som inte lämpar sig lätt för parallellisering eller implementering i analog hårdvara. Implementeringar i både parallell mjukvara och analog hårdvara designades dock faktiskt.

Vidare läsning

T. Martinetz, S. Berkovich och K. Schulten. "Neural-gas" nätverk för vektorkvantisering och dess tillämpning på tidsserieprediktion. IEEE-Transactions on Neural Networks, 4(4):558-569, 1993.
Martinetz, T.; Schulten, K. (1994). "Topologi som representerar nätverk". Neurala nätverk . 7 (3): 507–522. doi : 10.1016/0893-6080(94)90109-0 .

externa länkar

DemoGNG.js Javascript-simulator för neuralgas (och andra nätverksmodeller)
Java Competitive Learning Applications Oövervakade neurala nätverk (inklusive självorganiserande karta) i Java med källkoder.
formell beskrivning av neuralgasalgoritm
En implementering av GNG och GWR Classifier i Matlab