Acest exemplu îndeplinește două condiții necesare, dar totuși nu are nicio soluție. Pentru a obține clasificarea dorită pentru prima clasă, aveți nevoie de:
- Pentru a clasifica corespunzător stimulul nr. 1, greutatea elementului A nr. 1 ar fi pozitivă;
- Pentru a clasifica corespunzător stimulul nr. 2, greutatea elementului A nr. 2 ar fi pozitivă;
- Pentru a clasifica corespunzător stimulul nr. 3, suma coeficienților de greutate ai elementelor A din Nr. 3 și Nr. 4 ar fi pozitivă.
Pentru a obține clasificarea dorită pentru a doua clasă, aveți nevoie de:
- Pentru clasificarea corectă a stimulului nr. 4, suma coeficienților de greutate ai elementelor A Nr. 1, Nr. 2 și Nr. 3 ar fi negativă
- Pentru clasificarea corectă a stimulului nr. 5, suma coeficienților de greutate ai elementelor A Nr. 1, Nr. 2 și Nr. 4 ar fi negativă
Acest lucru arată că, dacă avem greutățile pentru A-elementul numărul 1 și numărul 2 sunt pozitive, iar cel puțin una dintre ponderilor pentru-elemente un număr de 3 și numărul 4 este pozitiv, putem astfel asigura că suma numărului greutăților 1 (+), № 2 (+) și № 3 (-) ar fi negativ, dar trebuie, în acest caz, greutatea № 4 lăsa un pozitiv, iar apoi suma № 1 (+), № 2 (+) și № 4 (+) nu poate fi negativ în nici un fel. Astfel, stimulul nr. 4 sau stimulul nr. 5 vor fi clasificate incorect. Aceasta se numește absența convergenței atunci când se decide clasificarea.
Într-o formă pură, Rosenblatt descrie suficiente condiții doar mai târziu în următoarea teoremă propusă de Joseph:
Teorema 9.
Elementul perceptron elementar și clasificarea C (W) sunt date. O condiție necesară și suficientă pentru ca o soluție să fie corectată pentru o perioadă finită și pentru o stare inițială arbitrară este aceea că nu ar trebui să existe un vector nonzero X * *>. astfel încât pentru toți i exponentul părtinire b i (X * *) = 0 (X ^) = 0>
dar din moment ce aceasta este o reprezentare matematică, deși mai elegant, dar încă nu suficient vorbesc despre ceea ce este necesar pentru a îndeplini condițiile din punct de vedere al arhitecturii Perceptronul, Rosenblatt de mai sus demonstrează următoarea teoremă:
Teorema 3.
Perceptronul elementar, spațiul stimulilor W și o anumită clasificare a C (W) sunt date. Apoi, pentru existența unei soluții pentru C (W), este necesar și suficient să existe un vector u situat în același ortant ca C (W) și un vector x astfel încât Gx = u.
Dar trei consecințe ale acestei teoreme sunt practic semnificative:
- Dacă G este o matrice a unui perceptron care este singular, adică o matrice care nu are un caracter invers (aceasta se întâmplă atunci când determinantul său este zero), atunci poate exista o clasificare care nu are o soluție. În acest caz, nu va exista o convergență în formarea perceptronului.
- Dacă numărul de stimuli din eșantionul de formare este mai mare decât numărul de elemente A din perceptronul elementar, atunci există și o clasificare care nu are nicio soluție. Astfel, limita superioară a numărului de neuroni formali din stratul ascuns este determinată. Cu toate acestea, este aproape suficient să existe 60-80% (și nu mai puțin de 50%) din acest număr, în funcție de numărul de clase pentru care ar trebui clasificate stimulentele.
- Probabilitatea existenței unei soluții pentru o clasificare aleasă aleatoriu cu o creștere a numărului de stimuli (care, în mod direct, conform celui de-al doilea corolar, conduce la o creștere a numărului de elemente A) tinde la zero. În practică, aceasta înseamnă că, în prezența unui perceptron de ordinul a 1000 de elemente A, probabilitatea ca matricea lui G să fie în mod special aproape de zero, iar cu creșterea numărului de elemente A această probabilitate tinde la zero.
Principala teoremă de convergență
În teorema de bază a convergenței, F. Rosenblatt arată că soluțiile posibile existente pot fi realizate tocmai prin aplicarea algoritmului de învățare cu corecția de eroare:
Teorema 4.
Dăm un perceptron elementar, un spațiu de stimuli W și o clasificare C (W), pentru care se știe că există o soluție. Să presupunem că toți stimulii din W apar în orice secvență, dar cu condiția ca fiecare stimul să apară în mod repetat, într-un interval de timp finit. Apoi procesul de învățare cu corecție de eroare (cu sau fără cuantizare a armăturii), pornind de la o stare inițială arbitrară, va duce întotdeauna la o soluție pentru C (W) pentru o perioadă finită de timp. În acest caz, toate semnalele de intrare către elementele R ating o valoare cel puțin egală cu o valoare arbitrară d> = 0.
Teoreme de convergență suplimentare
Într-o serie de teoreme, F. Rosenblatt arată ce caracteristici trebuie să aibă algoritmul de învățare pentru a ajunge la o soluție.
- În Teorema 5, el arată că metoda corecției erorilor cu un semn de întărire aleatorie, deși inferioară metodei cu corecția de eroare pentru viteză, dar, totuși, poate ajunge la o soluție.
- În Teorema 6 se demonstrează că pentru învățarea controlată de S se poate obține o soluție, dar se poate dovedi a fi instabilă. Și cu învățarea R-ghidată, nu are nici un sens să vorbim despre probabilitatea de convergență a procesului de învățare.
- Teorema 7 arată că metoda corecției prin perturbații aleatorii (de fapt, metoda de corecție fără un profesor), care dă și viteză metodei cu corecția de eroare, permite obținerea unei soluții în timp finit.
- Teorema 8 arată că poate exista gamma-Perceptron (perceptron în care greutățile tuturor conexiunilor active este mai întâi modificată cu o valoare egală, iar apoi din greutățile tuturor linkurile scade o altă cantitate egală cu variația totală greutățile tuturor conexiunilor active împărțit la numărul de obligațiuni) o decizie pe care nu o va putea realiza.
Nu există niciun automat finit care să îndeplinească funcția de multiplicare a două numere binare a și b de lățime arbitrară
Marvin Minsky a dat o serie de dovezi ale teoriei convergenței unui perceptron. Dar dovezile lui ne-au permis să judecăm valoarea coeficienților de greutate, esențială pentru stocarea lor în memoria calculatorului, precum și numărul de corecții necesare la coeficienții de greutate, ceea ce este important atunci când se evaluează viteza de antrenament perceptron.
Pentru a evalua capacitatea memoriei necesare pentru stocarea coeficienților de ponderare atunci când rezolvarea predicatul de formare „paritate“ Minsk a pornit de la următoarele considerente. Pentru o reprezentare uniformă a coeficienților, R | - 1 bit pentru fiecare, unde | R | - numărul de puncte pe retina perceptronului. Acest lucru rezultă din faptul că aceasta ar trebui să fie ponderea celui mai mare coeficient, astfel încât să fie îndeplinite condițiile pentru existența soluției. Și numărul necesar de coeficienți (cât mai mult posibil) 2 | R |>. Prin urmare, avem nevoie de (| R | - 1) * 2 | R |> bit. Dacă vom compara acest număr cu ceea ce se întâmplă dacă vom memora toate imaginile posibile care pot fi depuse pe retina perceptronului, atunci avem nevoie de o capacitate = | R | * 2 | R | - 1>. Sub aceste ipoteze, se pare că perceptronul pentru coeficienții de greutate al capacității este necesar aproape la fel de mult ca la stocarea tuturor imaginilor posibile.
Pentru a estima numărul de iterații. necesară pentru un perceptron elementar pentru a determina coeficienții de ponderare, Minsky a analizat predarea predicatului "paritate", care este una dintre cele mai teoretic dificile pentru perceptron. În același timp, el a luat un perceptron cu cel mai mic număr posibil de elemente A și, prin urmare, 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: 5 | R |
Prin urmare, critica din Minsk privind convergența perceptronului indică faptul că:
- dacă doriți să lucrați cu o rezoluție destul de mare a imaginii, de exemplu 800x600 pixeli,
- și este necesară rezolvarea unei anumite funcții matematice care depinde în totalitate de toate punctele (de exemplu, paritatea predicatelor, care nu poate fi spus dacă este adevărat sau nu până când toate punctele din spațiu sunt analizate secvențial)
perceptronului ar avea nevoie de memorie nerealist de mare calculator și timp de formare mult timp, în ciuda faptului că teorema de convergență sugerează un număr finit de iterații.
Aici, ar trebui să adăugați numai că nu este necesară pentru a găsi astfel de funcții matematice și caracteristici distinctive ale diferitelor clase de date de imagine poate fi găsit doar o suprafață mică, de exemplu, format din 20 de puncte din 8000 posibile pentru majoritatea sarcinilor reale de recunoaștere a imaginii. Astfel de predicate Constructing 20 elemente (predicate corespund-elementele A) se pot clasifica imaginile fără a considera toate caracteristicile lor (de obicei, numărul de predicat, așa cum sa menționat mai sus, este în termen de 60-80% din toate imaginile). Acest lucru indică faptul că numărul de imagini semnificative într-o anumită dimensiune este mai multe ordine de mărime mai mică decât numărul tuturor imaginilor posibile. Dacă nu necesită îndeplinirea anumitor funcții matematice (deplasare, rotație) ale unor astfel de imagini semnificative, devine clar că perceptronului nu poate aminti doar în mod optim pentru a clasifica o serie de imagini, dar, de asemenea, pentru a lucra într-o imagine sens algoritmi de compresie lossy. legându-le exact la clasa cerută.