Teorema de convergență a perceptronului

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 26 ianuarie 2021; verificările necesită 2 modificări .

Teorema de convergență a perceptronului este o teoremă descrisă și dovedită de F. Rosenblatt (cu participarea lui Blok, Joseph, Kesten și alți cercetători care au lucrat cu el). Arată că un perceptron elementar antrenat prin metoda de corectare a erorilor (cu sau fără cuantizare), indiferent de starea inițială a coeficienților de greutate și de succesiunea de apariție a stimulilor, va duce întotdeauna la realizarea unei soluții într-o perioadă finită de timp. F. Rosenblatt a prezentat și dovezi ale unui număr de teoreme înrudite, ale căror consecințe au făcut posibilă concluzia ce condiții ar trebui să îndeplinească arhitectura rețelelor neuronale artificiale și metodele lor de antrenament.

Teoreme de existență soluție pentru perceptronii universali

Înainte de a demonstra teorema principală de convergență a perceptronului, F. Rosenblatt a arătat că arhitectura perceptronului este suficientă pentru a obține o soluție la orice problemă de clasificare imaginabilă , adică perceptronul este astfel un „sistem universal”.

Teorema 1.
Având în vedere o retină cu două stări ale semnalelor de intrare (Da și Nu). Atunci clasa de perceptroni elementari pentru care există o soluție pentru orice clasificare C(W) a posibilelor medii W nu este goală.

În plus, F. Rosenblatt a arătat și a demonstrat în teorema 2 că condițiile necesare, dar încă insuficiente pentru existența unei soluții sunt următoarele:

fiecare stimul trebuie să excite cel puțin un element A;
nu ar trebui să existe o subsecvență de stimuli care să conțină cel puțin un stimul din fiecare clasă care ar avea drept rezultat același coeficient de părtinire pentru fiecare element A din setul de elemente A care răspund la acea subsecvență.

A doua condiție necesită clarificări. F. Rosenblatt a numit factorul de părtinire pentru elementul A raportul dintre numărul de stimuli din eșantionul de antrenament care aparțin unei clase și excită acest element A și numărul de stimuli aparținând altei clase, dar și excită același A. -element. Încălcarea celei de-a doua condiții face ca raportul să fie constant pentru elementele A care răspund la stimuli dintr-o astfel de secvență specifică a apariției stimulilor la intrările perceptronului. Și din această cauză, așa cum s-a dovedit în teorema 2 , cel puțin unul dintre stimuli va fi clasificat incorect. $n_i^+/n_i^-$ $n_i^+/n_i^-$

Rosenblatt a mai arătat că aceste condiții nu ar fi suficiente, cu următorul exemplu

Stimul	Emotionează elementele A	aparține clasei
numarul 1	numarul 1	nr. 1 (pozitiv)
nr. 2	nr. 2	nr. 1 (pozitiv)
Numărul 3	Nr. 3 și Nr. 4	nr. 1 (pozitiv)
nr. 4	Nr. 1, Nr. 2 și Nr. 3	nr. 2 (negativ)
nr. 5	Nr. 1, Nr. 2 și Nr. 4	nr. 2 (negativ)

A este un element	Factorul de deplasare
numarul 1	1/2
nr. 2	1/2
Numărul 3	1/1
nr. 4	1/1

Acest exemplu îndeplinește două condiții necesare, dar încă nu are o soluție. Pentru a obține clasificarea corectă pentru prima clasă, aveți nevoie de:

Pentru clasificarea corectă a stimulului nr. 1, astfel încât ponderea elementului A nr. 1 să fie pozitivă;
Pentru clasificarea corectă a stimulului #2, ponderea elementului A #2 ar fi pozitivă;
Pentru clasificarea corectă a stimulului nr. 3, astfel încât suma coeficienților de greutate ai elementelor A nr. 3 și nr. 4 să fie pozitivă.

Pentru a obține clasificarea corectă pentru a doua clasă, aveți nevoie de:

Pentru clasificarea corectă a stimulului #4, suma ponderilor elementelor A #1, #2 și #3 ar fi negativă
Pentru o clasificare corectă a stimulului #5, suma ponderilor elementelor A #1, #2 și #4 ar fi negativă

Aceasta arată că dacă avem coeficienți de greutate pozitivi pentru elementele A nr. 1 și nr. 2 și cel puțin unul dintre coeficienții de greutate pentru elementele A nr. 3 și nr. 4 este pozitiv, atunci putem realiza ca suma a greutăților nr. 1 (+), nr. 2(+) și nr. 3(-) ar fi negative, dar în acest caz suntem nevoiți să lăsăm pozitivă ponderea nr. 4, iar apoi suma nr. 1(+), nr. 2(+) și nr. 4(+) nu pot fi niciodată negative. Deci, fie stimulul #4, fie stimulul #5 vor fi clasificați greșit. Aceasta se numește lipsă de convergență la rezolvarea clasificării.

În forma sa pură, Rosenblatt descrie condițiile suficiente abia mai târziu în următoarea teoremă propusă de Joseph:

Teorema 9.
Sunt date un perceptron elementar și o clasificare C(W). Condiția necesară și suficientă ca o soluție să poată fi atinsă prin metoda corectării erorilor într-un timp finit și dintr-o stare inițială arbitrară este ca să nu existe un vector diferit de zero , astfel încât pentru tot i exponentul deplasării

X^{{**}}

b_i(X^{**})=0

dar deoarece aceasta este o reprezentare matematică, deși mai elegantă, dar spune totuși puțin despre condițiile care trebuie îndeplinite în ceea ce privește arhitectura perceptronului, Rosenblatt demonstrează mai întâi următoarea teoremă:

Teorema 3.
Având în vedere un perceptron elementar, un spațiu de stimul W și o anumită clasificare C(W). Atunci pentru existența unei soluții pentru C(W) este necesar și suficient să existe un vector u situat în același orthant cu C(W) și un vector x astfel încât Gx=u.

Dar trei corolare ale acestei teoreme sunt practic semnificative:

Dacă G este o matrice de perceptron specială , adică o matrice care nu are inversă (acest lucru se întâmplă când determinantul său este zero), atunci poate exista o clasificare care nu are soluție. În acest caz, nu va exista o convergență în antrenamentul perceptronului.
Dacă numărul de stimuli din eșantionul de antrenament este mai mare decât numărul de elemente A din perceptronul elementar, atunci există și o clasificare care nu are soluție. Astfel, se determină limita superioară a numărului de neuroni formali din stratul ascuns. Cu toate acestea, este practic suficient să aveți 60-80% (și cel puțin 50%) din acest număr, în funcție de numărul de clase în care trebuie clasificate stimulente.
Probabilitatea existenței unei soluții pentru o clasificare aleasă aleatoriu tinde spre zero pe măsură ce numărul de stimuli crește (ceea ce, conform celui de-al doilea corolar, duce direct la creșterea numărului de elemente A). În practică, aceasta înseamnă că dacă perceptronul are aproximativ 1000 de elemente A, probabilitatea ca matricea sa G să fie specială este aproape de zero și, pe măsură ce numărul de elemente A crește, această probabilitate tinde spre zero.

Teorema de bază a convergenței

În teorema principală de convergență, F. Rosenblatt arată că soluțiile posibile existente pot fi realizate tocmai prin aplicarea algoritmului de învățare cu corectarea erorilor:

Teorema 4.
Având în vedere un perceptron elementar, un spațiu de stimul W și o clasificare C(W) pentru care se știe că există o soluție. Să presupunem că toți stimulii de la W apar în orice secvență, dar cu condiția ca fiecare stimul să reapară după un interval de timp finit. Apoi, un proces de învățare de corectare a erorilor (cu sau fără cuantizare de întărire) pornind de la o stare inițială arbitrară va duce întotdeauna la o soluție pentru C(W) într-un interval de timp finit. În acest caz, toate semnalele de intrare către elementele R vor atinge o valoare cel puțin egală cu o valoare arbitrară d >= 0.

Teoreme suplimentare de convergență

Într-un număr din următoarele teoreme, F. Rosenblatt arată ce caracteristici trebuie să aibă un algoritm de învățare pentru ca acesta să ajungă la o soluție.

În teorema 5 , el arată că metoda de corectare a erorilor cu semn de întărire aleatoriu, deși inferioară metodei de corectare a erorilor în viteză, poate totuși să ajungă la o soluție.
Teorema 6 demonstrează că prin învățarea ghidată S, se poate obține o soluție, dar se poate dovedi instabilă. Și cu învățarea ghidată de R, nu are deloc sens să vorbim despre probabilitatea de convergență a procesului de învățare.
Teorema 7 arată că metoda corectării prin perturbații aleatoare (de fapt, metoda corectării fără profesor), care este de asemenea inferioară ca viteză față de metoda cu corectarea erorilor, permite obținerea unei soluții într-un timp finit.
Teorema 8 arată că pentru un gamma-perceptron (un perceptron în care ponderile tuturor legăturilor active sunt mai întâi modificate cu o cantitate egală, iar apoi se scade o altă valoare din ponderile tuturor legăturilor, egală cu modificarea totală a ponderilor toate legăturile active împărțite la numărul tuturor legăturilor) poate exista o soluție la care nu poate ajunge.

Teorema lui Minsky

Nu există un automat finit care să îndeplinească funcția de a înmulți două numere binare a și b de capacitate arbitrară

Critica lui Minsky

Marvin Minsky a oferit o serie de dovezi ale teoremei de convergență a perceptronului. Dar dovezile sale au făcut posibilă aprecierea mărimii coeficienților de greutate, care este esențială pentru stocarea lor în memoria computerului, precum și a numărului de corecții necesare ale coeficienților de greutate, ceea ce este important în evaluarea ratei de învățare a perceptronului. .

Pentru a estima capacitatea de memorie necesară pentru stocarea coeficienților de greutate, la rezolvarea antrenării predicatului de paritate, Minsky a pornit de la următoarele considerații. Pentru orice reprezentare uniformă a coeficienților, sunt necesari biți pentru fiecare, unde este numărul de puncte de pe retina perceptronului. Aceasta rezultă din faptul că aceasta ar trebui să fie ponderea celui mai mare coeficient pentru a îndeplini condițiile de existență a unei soluții. Și numărul necesar de coeficienți (maximul necesar) . Prin urmare, este necesar un pic . Dacă comparăm acest număr cu ceea ce se întâmplă dacă ne amintim toate imaginile posibile care pot fi aplicate pe retina perceptronului, atunci avem nevoie de capacitate = . În conformitate cu aceste ipoteze, se dovedește că perceptronul necesită aproape atâtea greutăți de capacitate cât este nevoie pentru a stoca toate imaginile posibile. $|R| - unu$ $|R|$ $2^{|R|}$ $(|R|-1)*2^{|R|}$ $|R|*2^{|R|-1}$

Pentru a estima numărul de iterații necesare unui perceptron elementar pentru a determina ponderile, Minsky a analizat învățarea predicatului de paritate, care este una dintre cele mai dificile din punct de vedere teoretic pentru un perceptron. În același timp, a luat un perceptron cu cel mai mic număr posibil de elemente A și, în consecință, cu cel mai mic număr de coeficienți de greutate, și pentru acest caz a determinat limitele inferioare și superioare ale numărului de corecții: , unde este numărul de puncte de pe retina perceptronului. $5^{|R|} < n < 10^{|R|}$ $|R|$

Prin urmare, critica lui Minsky asupra convergenței perceptronului indică faptul că:

dacă trebuie să lucrați cu o rezoluție destul de mare a imaginilor, de exemplu 800x600 pixeli,
și se cere să se rezolve o funcție matematică care depinde în întregime de toate punctele (de exemplu, predicatul de paritate, care nu poate fi spus dacă este par sau nu până când toate punctele din spațiu nu sunt analizate secvenţial)

atunci perceptronul va necesita o memorie de computer nerealist de mare și un timp lung de antrenament, chiar dacă teorema de convergență spune despre un număr finit de iterații.

Aici trebuie adăugat doar că pentru majoritatea problemelor de recunoaștere a imaginilor reale nu este necesară găsirea unor astfel de funcții matematice, iar caracteristicile distinctive ale imaginilor din diferite clase pot fi găsite având în vedere doar o zonă mică, de exemplu, constând din 20 de puncte. din 8000 posibile. După ce au construit astfel de predicate din 20 de elemente (predicatele corespund elementelor A), este posibil să se clasifice imaginile fără a lua în considerare toate caracteristicile lor (de regulă, numărul de astfel de predicate, așa cum s-a menționat mai sus, este între 60-80). % din numărul tuturor imaginilor). Acest lucru indică faptul că numărul de imagini semnificative într-o anumită dimensiune este cu câteva ordine de mărime mai mic decât numărul tuturor imaginilor posibile. Dacă nu aveți nevoie de performanța unei anumite funcții matematice (deplasare, rotație) pe astfel de imagini semnificative, devine clar că perceptronul nu numai că poate stoca în mod optim un număr de imagini pentru clasificare, dar poate funcționa și într-un anumit sens ca o compresie a imaginii cu pierderi . algoritm care le atribuie cu precizie clasei necesare.

Literatură

Frank Rosenblatt. Principiile neurodinamice: perceptronii și teoria mecanismelor creierului. - M. : „Mir”, 1965.

M. Minsky, S. Papert. Perceptroni = Perceptrons. - M . : „Mir”, 1971.

Vezi și

perceptron