Perceptrons konvergenssats

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 26 januari 2021; kontroller kräver 2 redigeringar .

Perceptronkonvergenssatsen är ett teorem som beskrivits och bevisats av F. Rosenblatt (med deltagande av Blok, Joseph, Kesten och andra forskare som arbetat med honom). Den visar att en elementär perceptron tränad med felkorrigeringsmetoden (med eller utan kvantisering), oavsett det initiala tillståndet för viktkoefficienterna och sekvensen av uppkomsten av stimuli, alltid kommer att leda till att en lösning uppnås inom en begränsad period av tid. F. Rosenblatt presenterade också bevis för ett antal besläktade satser, vars konsekvenser gjorde det möjligt att dra slutsatser om vilka villkor arkitekturen hos artificiella neurala nätverk och deras träningsmetoder borde uppfylla.

Lösningsexistenssatser för universella perceptroner

Innan han bevisade perceptronens huvudsakliga konvergenssats, visade F. Rosenblatt att perceptronens arkitektur är tillräcklig för att få en lösning på alla tänkbara klassificeringsproblem , det vill säga att perceptronen alltså är ett "universellt system".

Sats 1.
Givet en näthinna med två tillstånd av insignaler (Ja och Nej). Då är klassen av elementära perceptroner för vilken det finns en lösning för någon klassificering C(W) av möjliga miljöer W inte tom.

Vidare visade och bevisade F. Rosenblatt i sats 2 att de nödvändiga, men ännu inte tillräckliga förutsättningarna för existensen av en lösning är följande:

varje stimulus måste excitera minst ett A-element;
det bör inte finnas någon undersekvens av stimuli som innehåller minst en stimulus av varje klass som skulle resultera i samma förspänningskoefficient för varje A-element i uppsättningen av A-element som svarar på den undersekvensen.

Det andra villkoret behöver förtydligas. F. Rosenblatt kallade biasfaktorn för A-elementet för förhållandet mellan antalet stimuli i träningsprovet som tillhör en klass och exciterar detta A-element till antalet stimuli som tillhör en annan klass, men även exciterar samma A -element. Brott mot det andra villkoret gör förhållandet konstant för A-element som svarar på stimuli från en sådan specifik undersekvens av uppkomsten av stimuli vid perceptronens ingångar. Och på grund av detta, som bevisats i sats 2 , kommer åtminstone ett av stimuli att klassificeras felaktigt. $n_i^+/n_i^-$ $n_i^+/n_i^-$

Rosenblatt visade också att dessa villkor inte skulle vara tillräckliga, med följande exempel

Stimulans	Exciterar A-element	tillhör klassen
Nr 1	Nr 1	Nr 1 (positiv)
Nr 2	Nr 2	Nr 1 (positiv)
Nummer 3	nr 3 och nr 4	Nr 1 (positiv)
Nr 4	nr 1, nr 2 och nr 3	Nr 2 (negativ)
Nr 5	nr 1, nr 2 och nr 4	Nr 2 (negativ)

A är ett element	Förskjutningsfaktor
Nr 1	1/2
Nr 2	1/2
Nummer 3	1/1
Nr 4	1/1

Detta exempel uppfyller två nödvändiga villkor, men har fortfarande ingen lösning. För att få rätt klassificering för den första klassen behöver du:

För korrekt klassificering av stimulans nr 1, så att vikten av A-element nr 1 skulle vara positiv;
För korrekt klassificering av stimulus #2 skulle vikten av A-element #2 vara positiv;
För korrekt klassificering av stimulans nr 3, så att summan av viktkoefficienterna för A-element nr 3 och nr 4 skulle vara positiv.

För att få rätt klassificering för den andra klassen behöver du:

För korrekt klassificering av stimulus #4 skulle summan av vikterna av A-elementen #1, #2 och #3 vara negativ
För en korrekt klassificering av stimulus #5 skulle summan av vikterna av A-element #1, #2 och #4 vara negativ

Detta visar att om vi har positiva viktkoefficienter för A-element nr 1 och nr 2, och åtminstone en av viktkoefficienterna för A-element nr 3 och nr 4 är positiv, så kan vi uppnå att summan av vikterna nr 1 (+), nr 2(+) och nr 3(-) skulle vara negativa, men i det här fallet tvingas vi lämna vikten av nr 4 positiv, och sedan summan av nr. 1(+), nr 2(+) och nr 4(+) kan aldrig vara negativa. Så antingen stimulus #4 eller stimulus #5 kommer att felklassificeras. Detta kallas bristen på konvergens när man löser klassificeringen.

I sin rena form beskriver Rosenblatt de tillräckliga villkoren först senare i följande teorem som föreslagits av Joseph:

Sats 9.
En elementär perceptron och en klassificering C(W) ges. Det nödvändiga och tillräckliga villkoret för att en lösning kan nås med metoden för felkorrigering på en ändlig tid och från ett godtyckligt initialtillstånd är att det inte ska finnas en vektor som inte är noll , så att förskjutningsexponenten för alla

X^{{**}}

b_i(X^{**})=0

men eftersom detta är en matematisk representation, om än mer elegant, men ändå säger lite om vilka villkor som måste uppfyllas när det gäller perceptronens arkitektur, bevisar Rosenblatt först följande teorem:

Sats 3.
Givet en elementär perceptron, ett stimulusrum W och någon klassificering C(W). För att det ska finnas en lösning för C(W) är det nödvändigt och tillräckligt att det finns någon vektor u som ligger i samma ort som C(W) och någon vektor x så att Gx=u.

Men tre följder av denna teorem är praktiskt taget betydelsefulla:

Om G är en speciell perceptronmatris , det vill säga en matris som inte har en invers (detta händer när dess determinant är noll), så kan det finnas någon klassificering som inte har någon lösning. I detta fall kommer det inte att finnas någon konvergens vid träning av perceptronen.
Om antalet stimuli i träningsprovet är större än antalet A-element i den elementära perceptronen, så finns det också någon klassificering som inte har någon lösning. Således bestäms den övre gränsen för antalet formella neuroner i det dolda lagret. Det räcker dock praktiskt taget att ha 60-80 % (och minst 50 %) av detta antal, beroende på antalet klasser som incitamenten måste klassificeras i.
Sannolikheten för att det finns en lösning för en slumpmässigt vald klassificering tenderar att bli noll när antalet stimuli ökar (vilket, enligt den andra följden, direkt leder till en ökning av antalet A-element). I praktiken betyder det att om perceptronen har cirka 1000 A-element är sannolikheten att dess G-matris kommer att vara speciell nära noll, och när antalet A-element ökar tenderar denna sannolikhet till noll.

Grundläggande konvergenssats

I huvudkonvergenssatsen visar F. Rosenblatt att de befintliga möjliga lösningarna kan uppnås exakt genom att tillämpa inlärningsalgoritmen med felkorrigering:

Sats 4.
Givet en elementär perceptron, ett stimulusrum W och någon klassificering C(W) för vilken det är känt att det finns en lösning. Låt oss anta att alla stimuli från W uppträder i vilken sekvens som helst, men under förutsättning att varje stimulus dyker upp igen efter ett begränsat tidsintervall. Då kommer en felkorrigerande inlärningsprocess (med eller utan förstärkningskvantisering) som utgår från ett godtyckligt initialtillstånd alltid att leda till en lösning för C(W) inom ett begränsat tidsintervall. I detta fall kommer alla insignaler till R - element att nå ett värde som är minst lika med något godtyckligt värde d >= 0.

Ytterligare konvergenssatser

I ett antal av följande satser visar F. Rosenblatt vilka egenskaper en inlärningsalgoritm måste ha för att den ska nå en lösning.

I sats 5 visar han att felkorrigeringsmetoden med ett slumpmässigt förstärkningstecken, även om den är underlägsen felkorrigeringsmetoden i hastighet, ändå kan nå en lösning.
Sats 6 bevisar att med S-guidad inlärning kan en lösning erhållas, men den kan visa sig vara instabil. Och med R-styrt lärande är det ingen mening alls att tala om sannolikheten för konvergens av inlärningsprocessen.
Sats 7 visar att metoden för korrigering genom slumpmässiga störningar (i själva verket metoden för korrigering utan lärare), som också är sämre i hastighet än metoden med felkorrigering, gör att man kan få en lösning på en begränsad tid.
Sats 8 visar att för en gamma-perceptron (en perceptron där vikten av alla aktiva bindningar först ändras med lika mycket, och sedan ett annat värde subtraheras från vikterna av alla bindningar, lika med den totala förändringen i vikterna av alla aktiva obligationer dividerat med antalet alla obligationer) kan det finnas en lösning som han inte kan nå.

Minskys teorem

Det finns ingen finit automat som utför funktionen att multiplicera två binära tal a och b med godtycklig kapacitet

Kritik av Minsky

Marvin Minsky gav ett antal av sina bevis för perceptronkonvergenssatsen. Men hans bevis gjorde det möjligt att bedöma storleken på viktkoefficienterna, vilket är avgörande för att lagra dem i datorns minne, såväl som antalet nödvändiga korrigeringar av viktkoefficienterna, vilket är viktigt för att bedöma perceptronens inlärningshastighet .

För att uppskatta den minneskapacitet som krävs för att lagra viktkoefficienter, när man löser träningen av paritetspredikatet, utgick Minsky från följande överväganden. För varje enhetlig representation av koefficienterna krävs bitar för varje, där är antalet punkter på perceptronens näthinna. Detta följer av att detta bör vara vikten av den största koefficienten för att tillgodose förutsättningarna för att en lösning ska finnas. Och det erforderliga antalet koefficienter (det högsta som krävs) . Därför krävs det lite . Om vi jämför detta antal med vad som händer om vi kommer ihåg alla möjliga bilder som kan appliceras på perceptronens näthinna, då behöver vi kapacitet = . Under dessa antaganden visar det sig att perceptronen kräver nästan lika mycket kapacitetsvikter som det krävs för att lagra alla möjliga bilder. $|R| - ett$ $|R|$ $2^{|R|}$ $(|R|-1)*2^{|R|}$ $|R|*2^{|R|-1}$

För att uppskatta antalet iterationer som krävs för att en elementär perceptron ska bestämma vikterna, analyserade Minsky inlärningen av paritetspredikatet, vilket är ett av de teoretiskt svåraste för en perceptron. Samtidigt tog han en perceptron med minsta möjliga antal A-element, och följaktligen med det minsta antalet viktkoefficienter, och för detta fall bestämde han de nedre och övre gränserna för antalet korrigeringar: , där är antalet punkter på perceptronens näthinna. $5^{|R|} < n < 10^{|R|}$ $|R|$

Därför indikerar Minskys kritik av perceptronkonvergens att:

om du behöver arbeta med en ganska hög bildupplösning, till exempel 800x600 pixlar,
och det krävs för att lösa någon matematisk funktion som helt beror på alla punkter (till exempel paritetspredikatet, som inte kan sägas om det är jämnt eller inte förrän alla punkter i rymden analyseras sekventiellt)

då kommer perceptronen att kräva ett orealistiskt stort datorminne och lång träningstid, även om konvergenssatsen säger om ett ändligt antal iterationer.

Här bör det bara tilläggas att för de flesta problem med igenkänning av verkliga bilder krävs det inte att hitta sådana matematiska funktioner, och de särdrag som kännetecknar bilder av olika klasser kan hittas med endast ett litet område, till exempel bestående av 20 punkter av 8000 möjliga. Efter att ha byggt sådana predikat från 20 element (predikaten motsvarar A-element), är det möjligt att klassificera bilder utan att ta hänsyn till alla deras egenskaper (som regel är antalet sådana predikat, som nämnt ovan, inom 60-80 % av antalet av alla bilder). Detta pekar på det faktum att antalet meningsfulla bilder i en viss dimension är flera storleksordningar mindre än antalet av alla möjliga bilder. Om du inte kräver att någon matematisk funktion (skift, rotation) utförs på sådana meningsfulla bilder, blir det tydligt att perceptronen inte bara optimalt kan lagra ett antal bilder för klassificering, utan också fungera i en mening som en bildkomprimering med förlust. algoritm som korrekt tilldelar dem till den obligatoriska klassen.

Litteratur

Frank Rosenblatt. Principer för neurodynamisk: perceptroner och teorin om hjärnmekanismer. - M . : "Mir", 1965.

M. Minsky, S. Papert. Perceptroner = Perceptroner. - M . : "Mir", 1971.

Se även

perceptron