Perceptronin konvergenssilause

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 26. tammikuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Perceptronin konvergenssilause on F. Rosenblattin kuvaama ja todistama lause (johon osallistuivat Blok, Joseph, Kesten ja muut hänen kanssaan työskennelleet tutkijat). Se osoittaa, että virheenkorjausmenetelmällä (kvantisoinnilla tai ilman) harjoitettu alkeisperceptroni , riippumatta painokertoimien alkutilasta ja ärsykkeiden esiintymisjärjestyksestä, johtaa aina ratkaisun saavuttamiseen rajallisessa jaksossa. aika. F. Rosenblatt esitti myös todisteita useista toisiinsa liittyvistä teoreemoista, joiden seurauksista voitiin päätellä, mitä ehtoja keinohermoverkkojen arkkitehtuurin ja niiden koulutusmenetelmien tulee täyttää.

Ratkaisun olemassaololauseet universaaleille perceptroneille

Ennen perceptronin pääkonvergenssilauseen todistamista F. Rosenblatt osoitti, että perceptronin arkkitehtuuri on riittävä ratkaisun saamiseksi mihin tahansa ajateltaviin luokitteluongelmaan , eli perceptroni on siis "universaali järjestelmä".

Lause 1.
Annettu verkkokalvo, jossa on kaksi tulosignaalin tilaa (Kyllä ja Ei). Tällöin alkeisperceptronien luokka, jolle on olemassa ratkaisu mahdollisten ympäristöjen W luokittelulle C(W), ei ole tyhjä.

Edelleen F. Rosenblatt osoitti ja osoitti lauseessa 2 , että välttämättömät, mutta eivät vielä riittävät ehdot ratkaisun olemassaololle ovat seuraavat:

jokaisen ärsykkeen on viritettävä vähintään yksi A-elementti;
ei pitäisi olla ärsykkeiden osasarjaa, joka sisältää vähintään yhden ärsykkeen kustakin luokasta, joka johtaisi samaan bias-kertoimeen kullekin A-elementtijoukolle, joka vastaa tähän osasekvenssiin.

Toinen ehto kaipaa selvennystä. F. Rosenblatt kutsui A-elementin bias-tekijäksi suhdetta harjoitusnäytteessä yhteen luokkaan kuuluvien ja tämän A-elementin viritteiden määrään toiseen luokkaan kuuluvien ärsykkeiden määrään, mutta samalla myös herättää samaa A:ta. -elementti. Toisen ehdon rikkominen tekee suhteesta vakion A-elementeille, jotka vastaavat ärsykkeisiin sellaisesta erityisestä ärsykkeiden esiintymisen osajaksosta perceptronin tuloissa. Ja tämän vuoksi, kuten Lause 2 osoittaa , ainakin yksi ärsykkeistä luokitellaan väärin. $n_i^+/n_i^-$ $n_i^+/n_i^-$

Rosenblatt osoitti myös, että nämä ehdot eivät riittäisi seuraavalla esimerkillä

Ärsyke	Kiihottaa A-elementtejä	kuuluu luokkaan
Nro 1	Nro 1	Nro 1 (positiivinen)
Nro 2	Nro 2	Nro 1 (positiivinen)
Numero 3	Nro 3 ja nro 4	Nro 1 (positiivinen)
Nro 4	Nro 1, nro 2 ja nro 3	Nro 2 (negatiivinen)
Nro 5	Nro 1, nro 2 ja nro 4	Nro 2 (negatiivinen)

A on elementti	Siirtymäkerroin
Nro 1	1/2
Nro 2	1/2
Numero 3	1/1
Nro 4	1/1

Tämä esimerkki täyttää kaksi välttämätöntä ehtoa, mutta siihen ei silti ole ratkaisua. Saadaksesi oikean luokituksen ensimmäiselle luokalle tarvitset:

Ärsykkeen nro 1 oikealle luokittelulle, jotta A-elementin nro 1 paino olisi positiivinen;
Ärsykkeen #2 oikeaa luokittelua varten A-elementin #2 paino olisi positiivinen;
Ärsykkeen nro 3 oikeaan luokitukseen, jotta A-elementtien nro 3 ja nro 4 painokertoimien summa olisi positiivinen.

Saadaksesi oikean luokituksen toiselle luokalle tarvitset:

Jotta ärsykkeen #4 luokittelu olisi oikea, A-elementtien #1, #2 ja #3 painojen summa olisi negatiivinen
Ärsykkeen #5 oikean luokituksen saamiseksi A-elementtien #1, #2 ja #4 painojen summa olisi negatiivinen

Tämä osoittaa, että jos meillä on positiiviset painokertoimet A-elementeillä nro 1 ja nro 2 ja ainakin yksi A-elementtien nro 3 ja nro 4 painokertoimista on positiivinen, voimme saavuttaa tämän summan. painojen nro 1 (+), nro 2(+) ja nro 3(-) olisi negatiivinen, mutta tässä tapauksessa meidän on jätettävä painon nro 4 paino positiiviseksi ja sitten numeron nro summa. 1(+), nro 2(+) ja nro 4(+) ei voi koskaan olla negatiivinen. Joten ärsyke #4 tai ärsyke #5 luokitellaan väärin. Tätä kutsutaan konvergenssin puutteeksi luokittelua ratkaistaessa.

Puhtaassa muodossaan Rosenblatt kuvaa riittävät ehdot vasta myöhemmin seuraavassa Josephin ehdottamassa lauseessa:

Lause 9.
Esitetään alkeisperceptroni ja luokitus C(W). Välttämätön ja riittävä ehto, että ratkaisu voidaan saavuttaa virheenkorjausmenetelmällä äärellisessä ajassa ja mielivaltaisesta alkutilasta, on se, että ei saa olla nollasta poikkeavaa vektoria , niin että kaikille i on siirtymäeksponentti

X^{{**}}

b_i(X^{**})=0

mutta koska tämä on matemaattinen esitys, vaikkakin elegantimpi, mutta ei silti kerro juurikaan siitä, mitkä ehdot perceptronin arkkitehtuurin kannalta on täytettävä, Rosenblatt todistaa ensin seuraavan lauseen:

Lause 3.
Annettu alkeisperceptroni, ärsykeavaruus W ja jokin luokitus C(W). Tällöin C(W):n ratkaisun olemassaoloon on välttämätöntä ja riittävää, että on olemassa jokin vektori u, joka sijaitsee samassa ortantissa kuin C(W), ja jokin vektori x, jolloin Gx=u.

Mutta kolme tämän lauseen seurausta ovat käytännössä merkittäviä:

Jos G on erityinen perceptronimatriisi , eli matriisi, jolla ei ole käänteislukua (tämä tapahtuu, kun sen determinantti on nolla), voi olla jokin luokittelu, jolla ei ole ratkaisua. Tässä tapauksessa perceptronin koulutuksessa ei tapahdu konvergenssia.
Jos ärsykkeiden määrä harjoitusnäytteessä on suurempi kuin A-elementtien määrä alkeisperceptronissa, on olemassa myös luokittelu, jolla ei ole ratkaisua. Siten määritetään piilokerroksen muodollisten neuronien lukumäärän yläraja. Käytännössä riittää kuitenkin, että tästä määrästä on 60-80 % (ja vähintään 50 %) riippuen siitä, mihin luokkiin kannustimet on luokiteltava.
Ratkaisun olemassaolon todennäköisyys satunnaisesti valitulle luokittelulle pyrkii olemaan nolla ärsykkeiden määrän kasvaessa (mikä toisen seurauksen mukaan johtaa suoraan A-elementtien määrän kasvuun). Käytännössä tämä tarkoittaa, että jos perceptronissa on noin 1000 A-alkiota, todennäköisyys, että sen G-matriisi on erityinen, on lähellä nollaa, ja A-alkioiden määrän kasvaessa tämä todennäköisyys pyrkii nollaan.

Peruskonvergenssilause

Pääkonvergenssilauseessa F. Rosenblatt osoittaa, että olemassa olevat mahdolliset ratkaisut voidaan saavuttaa tarkasti soveltamalla oppimisalgoritmia virheenkorjauksella:

Lause 4.
Annettu alkeisperceptroni, ärsykeavaruus W ja jokin luokitus C(W), jolle tiedetään olevan ratkaisu. Oletetaan, että kaikki W:n ärsykkeet esiintyvät missä tahansa järjestyksessä, mutta sillä ehdolla, että jokainen ärsyke ilmaantuu uudelleen jonkin äärellisen aikavälin jälkeen. Tällöin virheenkorjaava oppimisprosessi (vahvistuskvantisoinnilla tai ilman), joka alkaa mielivaltaisesta alkutilasta, johtaa aina ratkaisuun C(W):lle rajallisen aikavälin sisällä. Tässä tapauksessa kaikki R - elementtien tulosignaalit saavuttavat arvon, joka on vähintään yhtä suuri kuin jokin mielivaltainen arvo d >= 0.

Muita konvergenssilauseita

Useissa seuraavista lauseista F. Rosenblatt osoittaa, mitkä ominaisuudet oppimisalgoritmilla on oltava, jotta se saavuttaa ratkaisun.

Lauseessa 5 hän osoittaa, että virheenkorjausmenetelmä satunnaisella vahvistusmerkillä, vaikka se onkin nopeudeltaan huonompi kuin virheenkorjausmenetelmä, voi kuitenkin saavuttaa ratkaisun.
Lause 6 osoittaa, että S-ohjatulla oppimisella voidaan saada ratkaisu, mutta se voi osoittautua epävakaaksi. Ja R-ohjatussa oppimisessa ei ole mitään järkeä puhua oppimisprosessin konvergenssin todennäköisyydestä.
Lause 7 osoittaa, että satunnaishäiriöiden korjausmenetelmä (itse asiassa korjausmenetelmä ilman opettajaa), joka on myös nopeudeltaan huonompi kuin menetelmä virheenkorjauksella, mahdollistaa ratkaisun saamisen äärellisessä ajassa.
Lause 8 osoittaa, että gamma-perceptronille (perceptronille, jossa kaikkien aktiivisten sidosten painot muuttuvat ensin yhtä suurella määrällä ja sitten kaikkien sidosten painoista vähennetään toinen arvo, joka on yhtä suuri kuin sidosten painojen kokonaismuutos. kaikki aktiiviset sidokset jaettuna kaikkien joukkovelkakirjojen lukumäärällä) voi olla ratkaisu, jota hän ei voi saavuttaa.

Minskyn lause

Ei ole olemassa äärellistä automaattia, joka kertoisi kaksi mielivaltaista kapasiteettia olevaa binaarilukua a ja b

Minskyn kritiikki

Marvin Minsky esitti useita todisteita perceptronin konvergenssilauseesta. Mutta hänen todistuksensa mahdollistivat painokertoimien suuruuden, mikä on välttämätöntä niiden tallentamiseksi tietokoneen muistiin, sekä painokertoimien tarvittavien korjausten lukumäärän, mikä on tärkeää perceptronin oppimisnopeuden arvioinnissa. .

Painokertoimien tallentamiseen tarvittavan muistikapasiteetin arvioimiseksi pariteettipredikaatin harjoittelua ratkaistessaan Minsky lähti seuraavista näkökohdista. Kertoimien tasaiseen esitykseen tarvitaan bittejä jokaiselle, missä on pisteiden lukumäärä perceptronin verkkokalvolla. Tämä johtuu siitä, että tämän tulisi olla suurimman kertoimen paino, jotta ratkaisun olemassaolon ehdot täyttyvät. Ja tarvittava määrä kertoimia (maksimi vaadittu) . Siksi vähän tarvitaan . Jos vertaamme tätä lukua siihen, mitä tapahtuu, jos muistamme kaikki mahdolliset kuvat, joita voidaan soveltaa perceptronin verkkokalvoon, tarvitsemme kapasiteettia = . Näillä oletuksilla käy ilmi, että perceptron vaatii lähes yhtä paljon kapasiteettipainoja kuin se vaatii kaikkien mahdollisten kuvien tallentamiseen. $|R| - yksi$ $|R|$ $2^{|R|}$ $(|R|-1)*2^{|R|}$ $|R|*2^{|R|-1}$

Arvioidakseen alkeisperceptronilta painojen määrittämiseen tarvittavien iteraatioiden lukumäärän Minsky analysoi pariteettipredikaatin oppimista, joka on yksi teoreettisesti vaikeimmista perceptronille. Samalla hän otti perceptronin, jolla oli pienin mahdollinen määrä A-elementtejä ja siten pienimmällä määrällä painokertoimia, ja tätä varten hän määritti korjausten lukumäärän ala- ja ylärajat: , missä on perceptronin verkkokalvon pisteiden lukumäärä. $5^{|R|} < n < 10^{|R|}$ $|R|$

Siksi Minskyn kritiikki perceptronin konvergenssista osoittaa, että:

jos sinun on työskenneltävä melko korkealla resoluutiolla, esimerkiksi 800x600 pikseliä,
ja tarvitaan ratkaisemaan jokin matemaattinen funktio, joka riippuu täysin kaikista pisteistä (esimerkiksi pariteettipredikaatti, jota ei voida sanoa, onko se parillinen vai ei, ennen kuin kaikki avaruuden pisteet on analysoitu peräkkäin)

silloin perceptroni vaatii epärealistisen suuren tietokonemuistin ja pitkän harjoitusajan, vaikka konvergenssilause sanookin äärellisestä määrästä iteraatioita.

Tässä on lisättävä vain, että useimpiin todellisten kuvien tunnistusongelmiin ei vaadita tällaisia matemaattisia funktioita, ja eri luokkien kuvien erityispiirteet löytyvät vain pieneltä alueelta, joka koostuu esimerkiksi 20 pisteestä. 8000 mahdollisesta. Kun tällaiset predikaatit on rakennettu 20 elementistä (predikaatit vastaavat A-elementtejä), on mahdollista luokitella kuvat ottamatta huomioon kaikkia niiden ominaisuuksia (yleensä tällaisten predikaattien lukumäärä, kuten edellä mainittiin, on 60-80 % kaikkien kuvien määrästä). Tämä viittaa siihen, että merkityksellisten kuvien määrä tietyssä ulottuvuudessa on useita suuruusluokkia pienempi kuin kaikkien mahdollisten kuvien lukumäärä. Jos et vaadi joidenkin matemaattisten funktioiden (siirto, kierto) suorittamista tällaisissa merkityksellisissä kuvissa, käy selväksi, että perceptroni ei voi vain tallentaa optimaalisesti useita kuvia luokittelua varten, vaan se toimii myös tavallaan häviöllisenä kuvanpakkauksena . algoritmi , joka määrittää ne tarkasti vaadittuun luokkaan.

Kirjallisuus

Frank Rosenblatt. Neurodynaamisen periaatteet : perceptronit ja aivojen mekanismien teoria. - M . : "Mir", 1965.

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

Katso myös

perceptron