2.4.5 XOR-problém, skrytá vrstva NN
2.4.3 Algoritmus učenia perceptróna
2.4 Perceptrón - najjednoduch¹ia neurónová sieť

Obsah

2.4.4 Veta o konvergencii perceptrónu

Predpokladajme, že separujúca nadrovina existuje, tj. triedy sú separovateľné. Cieľom tejto èasti je dokázať, ¾e JPR po koneènom poète krokov, tj. ak dostane "k" rôznych vstupov^2.3 z mno¾iny ${\bf X^n}$, $k~<~S$, kde S je koneèné prirodzené èíslo, dosiahne stabilný stav, tj. u¾ bude vedieť klasifikovať hocijaký vstup z mno¾iny X správne, t.j. váhy JPR sa nebudú meniť. Výsledkom dôkazu bude tie¾ horný odhad pre poèet krokov k. Pre jednoduchosť celý dôkaz realizujeme vo vektorovom tvare. Predpokladajme, že rovnica hľadanej nadroviny bola nájdená, tj. bol nájdený vektor váh v, ktorý je rie¹ením. To znamená, ¾e u¾ nedôjde k zmene váh, tj. platí ${\bf v x}(t) > 0$ pre t = 1, 2, .... Predpokladajme, ¾e nastáva situácia, ¾e v t-tom kroku je nesprávna klasifikácia teda prípad ( 2.20), tj.

$${\bf w}(t+1) = {\bf w}(t) + {\bf z}(t)$$ (2.22)

èo je mo¾né upraviť odčítaním výrazu $\phi {\bf v}$ od obidvoch strán rovnice, teda

$${\bf w}(t+1) - \phi {\bf v} = {\bf w}(t) - \phi {\bf v} + {\bf z}(t)$$ (2.23)

kde $\phi$ je kladná kon¹tanta. Pre výpoèet normy vektora na pravej strane platí

$$\Vert{\bf w}(t+1)-\phi {\bf v}\Vert^2 = \Vert{\bf w}(t) -... ...\bf z}(t)({\bf w}(t) - \phi {\bf v}) + \Vert{\bf z}(t)\Vert^2$$ (2.24)

Preto¾e z(t) je klasifikované nesprávne, platí ${\bf z}(t){\bf w}(t) \leq 0$, a teda

$$\Vert{\bf w}(t+1)-\phi {\bf v}\Vert^2 \leq \Vert{\bf w}(t... ... \Vert^2 - 2 \phi {\bf v} {\bf z}(t) + \Vert{\bf z}(t)\Vert^2$$ (2.25)

Zaveďme nasledujúce oznaèenie

$$\alpha = min_{j=0,\dots,k}( {\bf v z}(j) )$$ (2.26)

$\alpha$ je zrejme kladné èíslo, preto¾e ${\bf z}(t){\bf v} > 0$. Nech

$$\beta = max_i \Vert{\bf z} (i)\Vert$$ (2.27)

Nerovnosť ( 2.25) je mo¾né upraviť nasledujúcim spôsobom

$$\Vert{\bf w}(t+1)-\phi {\bf v}\Vert^2 \leq \Vert{\bf w}(t) - \phi {\bf v} \Vert^2 - 2 \phi \alpha + \beta^2$$ (2.28)

Ak vyberieme $\phi$ dostatoène veľké, napríklad $\phi = \beta^2/ \alpha$, dostaneme

$$\Vert{\bf w}(t+1)-\phi {\bf v}\Vert^2 \leq \Vert{\bf w}(t) - \phi {\bf v} \Vert^2 - \beta^2$$ (2.29)

Teda druhá mocnina vzdialenosti medzi w(t) a $\phi {\bf v}$ je redukovaná aspoò o $\beta^2$ pri ka¾dej úprave. Po k úpravách potom dostávame nerovnosti

$$0\leq\Vert{\bf w}(t+1)-\phi {\bf v}\Vert^2 \leq \Vert{\bf w}(0) - \phi {\bf v} \Vert^2 - k\beta^2$$ (2.30)

Z toho vyplýva, ¾e postupnosť úprav musí skonèiť najviac po konečnom počte $k_0$ krokov, kde

$$k_0 = \Vert{\bf w}(0)-\phi {\bf v}\Vert^2 /\beta^2$$ (2.31)

Veľkosť $k_0$ je závislá od $\alpha$ a $\beta$, pri vypočte ktorých sa vyskytne znovu hodnota $k_0$. Ak sú však známe odhady $\alpha$ a $\beta$, potom $k_0$ je možné určiť hneď. Teda ak rie¹enie existuje, je dosiahnuteľné po koneènom poète krokov. Predpokladajme znovu, ¾e poèiatoèné nastavenie váh je nulové. Tým predchádzajúcu rovnicu zjednodu¹íme

$$k_0 = \phi^2\Vert {\bf v}\Vert^2 /\beta^2$$ (2.32)

Na základe (2.32) sme dokázali, ¾e $k$ existuje a je to koneèné èíslo, a tým mô¾eme vysloviť nasledovné tvrdenie :

Majme trénovaciu mno¾inu vektorov X, ktoré mô¾u patriť len do dvoch rôznych tried CL1 a CL2, ktoré sú lineárne separovateľné. Perceptrón po realizovaní "${\bf k_0}$" omylov sa urèite dostane do stavu, keď nebude meniť svoje SV, kedy konverguje . To znamená, ¾e bude spoľahlivo klasifikovať vektory do príslu¹ných tried.

CIG Homepage(E-mail us!)