Perceptron konvergenssætning

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 26. januar 2021; checks kræver 2 redigeringer .

Perceptronkonvergenssætningen er en sætning beskrevet og bevist af F. Rosenblatt (med deltagelse af Blok, Joseph, Kesten og andre forskere, der arbejdede med ham). Den viser, at en elementær perceptron trænet ved fejlkorrektionsmetoden (med eller uden kvantisering), uanset vægtkoefficienternes begyndelsestilstand og sekvensen af fremkomsten af stimuli, altid vil føre til opnåelse af en løsning i en begrænset periode på tid. F. Rosenblatt fremlagde også beviser for en række beslægtede teoremer, hvis konsekvenser gjorde det muligt at konkludere, hvilke betingelser arkitekturen af kunstige neurale netværk og deres træningsmetoder skulle opfylde.

Løsningseksistenssætninger for universelle perceptroner

Før han beviste perceptronens hovedkonvergenssætning, viste F. Rosenblatt, at perceptronens arkitektur er tilstrækkelig til at opnå en løsning på ethvert tænkeligt klassifikationsproblem , det vil sige, at perceptronen således er et "universelt system".

Sætning 1.
Givet en nethinde med to tilstande af indgangssignaler (Ja og Nej). Så er klassen af elementære perceptroner, for hvilke der findes en løsning for enhver klassifikation C(W) af mulige miljøer W, ikke tom.

Yderligere viste og beviste F. Rosenblatt i sætning 2 , at de nødvendige, men endnu ikke tilstrækkelige betingelser for eksistensen af en løsning er følgende:

hver stimulus skal excitere mindst ét A-element;
der bør ikke være nogen undersekvens af stimuli indeholdende mindst én stimulus af hver klasse, der ville resultere i den samme bias-koefficient for hvert A-element i sættet af A-elementer, der reagerer på den undersekvens.

Den anden betingelse trænger til afklaring. F. Rosenblatt kaldte bias-faktoren for A-elementet forholdet mellem antallet af stimuli i træningsprøven, der tilhører en klasse og exciterer dette A-element til antallet af stimuli, der tilhører en anden klasse, men også exciterer det samme A. -element. Overtrædelse af den anden betingelse gør forholdet konstant for A-elementer, der reagerer på stimuli fra en sådan specifik undersekvens af fremkomsten af stimuli ved perceptronens input. Og på grund af dette, som bevist i sætning 2 , vil mindst en af stimuli blive klassificeret forkert. $n_i^+/n_i^-$ $n_i^+/n_i^-$

Rosenblatt viste også, at disse forhold ikke ville være nok, med følgende eksempel

Stimulus	Spænder A-elementer	hører til klassen
nr. 1	nr. 1	nr. 1 (positiv)
nr. 2	nr. 2	nr. 1 (positiv)
Nummer 3	nr. 3 og nr. 4	nr. 1 (positiv)
nr. 4	nr. 1, nr. 2 og nr. 3	nr. 2 (negativ)
nr. 5	nr. 1, nr. 2 og nr. 4	nr. 2 (negativ)

A er et element	Forskydningsfaktor
nr. 1	1/2
nr. 2	1/2
Nummer 3	1/1
nr. 4	1/1

Dette eksempel opfylder to nødvendige betingelser, men har stadig ingen løsning. For at få den rigtige klassificering til første klasse skal du bruge:

For den korrekte klassificering af stimulus nr. 1, således at vægten af A-element nr. 1 ville være positiv;
For den korrekte klassificering af stimulus #2 ville vægten af A-element #2 være positiv;
For den korrekte klassificering af stimulus nr. 3, således at summen af vægtkoefficienterne for A-elementer nr. 3 og nr. 4 ville være positiv.

For at få den rigtige klassifikation til anden klasse, skal du bruge:

For den korrekte klassificering af stimulus #4 ville summen af vægtene af A-elementerne #1, #2 og #3 være negativ
For en korrekt klassificering af stimulus #5 ville summen af vægtene af A-elementer #1, #2 og #4 være negativ

Dette viser, at hvis vi har positive vægtkoefficienter for A-elementer nr. 1 og nr. 2, og mindst én af vægtkoefficienterne for A-elementer nr. 3 og nr. 4 er positiv, så kan vi opnå, at summen af vægt nr. 1 (+), nr. 2(+) og nr. 3(-) ville være negativ, men i dette tilfælde er vi tvunget til at lade vægten af nr. 4 være positiv, og derefter summen af nr. 1(+), nr. 2(+) og nr. 4(+) kan aldrig være negative. Så enten stimulus #4 eller stimulus #5 vil blive fejlklassificeret. Dette kaldes manglen på konvergens , når man løser klassifikationen.

I sin rene form beskriver Rosenblatt de tilstrækkelige betingelser først senere i følgende sætning foreslået af Joseph:

Sætning 9.
Der gives en elementær perceptron og en klassifikation C(W). Den nødvendige og tilstrækkelige betingelse for, at en løsning kan nås ved hjælp af fejlkorrektionsmetoden i en endelig tid og fra en vilkårlig begyndelsestilstand, er, at der ikke skal være en vektor , der ikke er nul, således at forskydningseksponenten for alle i

X^{{**}}

b_i(X^{**})=0

men da dette er en matematisk repræsentation, skønt mere elegant, men ikke desto mindre siger lidt om, hvilke betingelser der skal opfyldes med hensyn til perceptronens arkitektur, beviser Rosenblatt først følgende sætning:

Sætning 3.
Givet en elementær perceptron, et stimulusrum W og en eller anden klassifikation C(W). Så for eksistensen af en løsning for C(W) er det nødvendigt og tilstrækkeligt, at der eksisterer en eller anden vektor u, der ligger i samme orthant som C(W) og en eller anden vektor x, således at Gx=u.

Men tre følger af denne teorem er praktisk talt signifikante:

Hvis G er en speciel perceptronmatrix , det vil sige en matrix, der ikke har en invers (dette sker, når dens determinant er nul), så kan der være en eller anden klassifikation, der ikke har nogen løsning. I dette tilfælde vil der ikke være nogen konvergens ved træning af perceptronen.
Hvis antallet af stimuli i træningsprøven er større end antallet af A-elementer i den elementære perceptron, så er der også en eller anden klassifikation, der ikke har nogen løsning. Således bestemmes den øvre grænse for antallet af formelle neuroner i det skjulte lag. Det er dog praktisk talt nok at have 60-80 % (og mindst 50 %) af dette antal, afhængigt af antallet af klasser, som incitamenter skal klassificeres i.
Sandsynligheden for eksistensen af en løsning til en tilfældigt valgt klassifikation har en tendens til nul, når antallet af stimuli stiger (hvilket ifølge den anden konsekvens direkte fører til en stigning i antallet af A-elementer). I praksis betyder det, at hvis perceptronen har omkring 1000 A-elementer, er sandsynligheden for, at dens G-matrix vil være speciel, tæt på nul, og når antallet af A-elementer stiger, har denne sandsynlighed en tendens til nul.

Grundlæggende konvergenssætning

I hovedkonvergenssætningen viser F. Rosenblatt, at de eksisterende mulige løsninger kan opnås præcist ved at anvende indlæringsalgoritmen med fejlkorrektion:

Sætning 4.
Givet en elementær perceptron, et stimulusrum W, og en eller anden klassifikation C(W), for hvilken der vides at eksistere en løsning. Lad os antage, at alle stimuli fra W optræder i en hvilken som helst sekvens, men på betingelse af, at hver stimulus dukker op igen efter et begrænset tidsinterval. Så vil en fejlkorrigerende læreproces (med eller uden forstærkningskvantisering) startende fra en vilkårlig starttilstand altid føre til en løsning for C(W) inden for et begrænset tidsinterval. I dette tilfælde vil alle inputsignaler til R - elementer nå en værdi, der mindst er lig med en eller anden vilkårlig værdi d >= 0.

Yderligere konvergenssætninger

I en række af de følgende sætninger viser F. Rosenblatt, hvilke egenskaber en læringsalgoritme skal have for at nå frem til en løsning.

I sætning 5 viser han, at fejlkorrektionsmetoden med et tilfældigt forstærkningstegn, selvom den er ringere end fejlkorrektionsmetoden i hastighed, alligevel kan nå en løsning.
Sætning 6 beviser, at der med S-guidet læring kan opnås en løsning, men den kan vise sig at være ustabil. Og med R-guidet læring giver det overhovedet ingen mening at tale om sandsynligheden for konvergens af læreprocessen.
Sætning 7 viser, at metoden til korrektion ved tilfældige forstyrrelser (faktisk korrektionsmetoden uden lærer), som også er ringere i hastighed end metoden med fejlkorrektion, gør det muligt at opnå en løsning på en begrænset tid.
Sætning 8 viser, at for en gamma-perceptron (en perceptron, hvor vægten af alle aktive bindinger først ændres med lige meget, og derefter trækkes en anden værdi fra vægten af alle bindinger, lig med den samlede ændring i vægtene af alle aktive obligationer divideret med antallet af alle obligationer) kan der eksistere en løsning, som han ikke kan nå.

Minskys sætning

Der er ingen endelig automat, der udfører funktionen at gange to binære tal a og b med vilkårlig kapacitet

Kritik af Minsky

Marvin Minsky gav en række af sine beviser for perceptronkonvergenssætningen. Men hans beviser gjorde det muligt at bedømme størrelsen af vægtkoefficienterne, som er afgørende for at gemme dem i computerens hukommelse, samt antallet af nødvendige korrektioner af vægtkoefficienterne, hvilket er vigtigt i vurderingen af perceptronens indlæringshastighed .

For at estimere den hukommelseskapacitet, der kræves til lagring af vægtkoefficienter, gik Minsky ud fra følgende overvejelser, når man løser træningen af paritetsprædikatet. For enhver ensartet repræsentation af koefficienterne kræves bits for hver, hvor er antallet af punkter på nethinden af perceptronen. Dette følger af, at dette skal være vægten af den største koefficient for at opfylde betingelserne for, at der findes en løsning. Og det nødvendige antal koefficienter (det maksimale krævede) . Derfor skal der lidt til . Hvis vi sammenligner dette tal med, hvad der sker, hvis vi husker alle mulige billeder, der kan påføres perceptronens nethinde, så har vi brug for kapacitet = . Under disse antagelser viser det sig, at perceptronen kræver næsten lige så mange kapacitetsvægte, som det tager at gemme alle mulige billeder. $|R| - en$ $|R|$ $2^{|R|}$ $(|R|-1)*2^{|R|}$ $|R|*2^{|R|-1}$

For at estimere antallet af iterationer , der kræves for en elementær perceptron til at bestemme vægtene, analyserede Minsky indlæringen af paritetsprædikatet, som er en af de mest teoretisk vanskelige for en perceptron. Samtidig tog han en perceptron med det mindst mulige antal A-elementer, og følgelig med det mindste antal vægtkoefficienter, og for dette tilfælde bestemte han den nedre og øvre grænse for antallet af korrektioner: , hvor er antallet af punkter på nethinden af perceptronen. $5^{|R|} < n < 10^{|R|}$ $|R|$

Derfor indikerer Minskys kritik af perceptronkonvergens, at:

hvis du skal arbejde med en ret høj opløsning af billeder, for eksempel 800x600 pixels,
og det er nødvendigt at løse en eller anden matematisk funktion, der afhænger helt af alle punkter (for eksempel paritetsprædikatet, som ikke kan siges, om det er lige eller ej, før alle punkter i rummet er analyseret sekventielt)

så vil perceptronen kræve en urealistisk stor computerhukommelse og lang træningstid, selvom konvergenssætningen siger om et endeligt antal iterationer.

Her skal det kun tilføjes, at for de fleste problemer med genkendelse af virkelige billeder er det ikke nødvendigt at finde sådanne matematiske funktioner, og de karakteristiske træk ved billeder af forskellige klasser kan kun findes givet et lille område, for eksempel bestående af 20 punkter ud af 8000 mulige. Efter at have bygget sådanne prædikater fra 20 elementer (prædikaterne svarer til A-elementer), er det muligt at klassificere billeder uden at tage hensyn til alle deres funktioner (som regel er antallet af sådanne prædikater, som nævnt ovenfor, inden for 60-80 % af antallet af alle billeder). Dette peger på, at antallet af meningsfulde billeder i en bestemt dimension er flere størrelsesordener mindre end antallet af alle mulige billeder. Hvis du ikke kræver udførelse af en matematisk funktion (forskydning, rotation) på sådanne meningsfulde billeder, bliver det klart, at perceptronen ikke kun optimalt kan gemme et antal billeder til klassificering, men også fungere i en vis forstand som en tabsgivende billedkomprimering algoritme , der præcist tildeler dem til den påkrævede klasse.

Litteratur

Frank Rosenblatt. Principper for neurodynamisk: perceptroner og teorien om hjernemekanismer. - M . : "Mir", 1965.

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

Se også

perceptron