Vezessük be a következő jelöléseket. Jelölje $X^{\left(1\right)}$ azon bemeneti mintapontok halmazát, amelyek az (1) osztályba, $X^{\left(2\right)}$ pedig azon bemeneti mintapontok halmazát, amelynek elemei a (2) osztályba tartoznak, és tételezzük fel, hogy mind $X^{\left(1\right)}$ , mind $X^{\left(2\right)}$ véges számú vektort tartalmaz. Jelöljön továbbá $w^{\ast }$ egy olyan súlyvektort, amely mellett a hálózat jól osztályoz, vagyis $w^{\ast T}x$ >0, ha $x\in X^{\left(1\right)}$ és $w^{\ast T}x$ <0, ha $x\in X^{\left(2\right)}$ .

A hálózat tanítását a következőképpen végezzük: egyenként vegyük sorra az összes bemeneti mintapontot, határozzuk meg mindegyik lépésben a hálózat válaszát, és az alábbi összefüggés szerint módosítsuk a súlyvektort:

$w\left(k\right)=w\left(k-1\right)+\alpha \left(d\left(k\right)-y\left(k\right)\right)x\left(k\right)=w\left(k-1\right)+\alpha \epsilon \left(k\right)x\left(k\right)$ (3.3)

A súlymódosítás (3.3) összefüggése formailag megegyezik az előző fejezetben bemutatott LMS algoritmussal, ha az itt szereplő α-t megfeleltetjük az LMS algoritmus μ tanulási tényezőjének. Az egyezés azonban csak formai, ahogy ez a következőkből kiderül. Amennyiben mind d(k), mind y(k) csak két értéket (±1 vagy 0 és 1) vehet fel, és α értékét 1-re választjuk, hibás válasz esetén ε(k) abszolút értéke is csak két lehetséges konstans érték (2, ill. 1) egyike lehet, míg a hiba előjele a tényleges értékektől függően változik; vagyis valójában a pillanatnyi bemenőjel konstans-szorosával történik a súlykorrekció:

$w\left(k\right)=w\left(k-1\right)+\alpha \left(k\right)x\left(k\right)$ , (3.4)

ahol α(k) értéke ±2, ill. ±1 lehet.

A súlymódosítás ez utóbbi formája mutatja, hogy a formai hasonlóság ellenére itt valóban nem az LMS algoritmussal van dolgunk, vagyis a súlymódosítás nem egy hibafelület negatív gradiensének irányában történik, hanem a súlyvektort egyszerűen a helytelenül osztályozott bemenővektorral arányosan módosítjuk. Ez a módosítás szemléletesen azt jelenti, hogy a súlyvektort a hibásan osztályozott bemeneti vektor irányában (vagy azzal ellentétes irányban) elforgatjuk, s így a módosítás után a skalár szorzat a kívánt értékhez közelít.

A tanító lépés során a súlyvektort olyan módon változtatjuk, hogy a módosított súlyvektorral a hálózat válasza a helyes értékhez közelítsen. A tanítás hatását a súlyvektorok terében a 3.2 ábrán követhetjük nyomon. A súlyvektorok terében minden bemenővektor egy hipersíkot (kétdimenziós súlytérben egy egyenest) határoz meg. Az egyenes pontjai egyben azon súlyvektorokat is megadják, amelyek mellett a bemenővektor és a súlyvektor skalár szorzata zérus, vagyis az egyenes merőleges a bemeneti mintavektorra. (Másképp fogalmazva a mintavektort a súlytérben olyan hipersíkkal reprezentáljuk, amelynek normálvektora épp a mintavektor.) A hipersík (egyenes) negatív oldalán elhelyezkedő súlyvektorok esetén a hálózat kimenete -1 lesz, míg ha a súlyvektor az egyenes pozitív oldalán található, akkor a hálózat válasza +1.

Súlymódosításra akkor van szükség, ha az aktuális súlyvektor egy tanítópont által meghatározott hipersíknak (egyenesnek) nem a tanítópont osztályának megfelelő oldalán helyezkedik el, vagyis a skalár szorzat nem megfelelő előjelű. Ilyenkor a súlyvektort olyan módon változtatjuk, hogy a skalár szorzat a módosított súlyvektorral megfelelő előjelű legyen − a súlyvektor a hipersík megfelelő oldalára kerüljön −, vagy legalábbis a súlyvektort a helyes irányba mozdítsuk.

Az ábra azt a feltételezett esetet mutatja, amikor három tanítópontunk van, amelyek közül x₁ és x₃ $X^{\left(1\right)}$ elemei, míg x₂ $X^{\left(2\right)}$ eleme, vagyis $w^{\ast T}{x}_i$ > 0, ha i=1 és 3, ill. $w^{\ast T}{x}_i$ < 0, ha i=2. A $w^{\ast }$ megoldásvektornak tehát a súlytérben az x₁ és x₃ tanító pontokat reprezentáló egyenesek (1 és ₃) pozitív oldalán, míg az x₂-t reprezentáló egyenes (₂) negatív oldalán kell elhelyezkednie. Ezeket a feltételeket a súlytérben árnyékoltan jelölt területet pontjai elégíti ki, tehát a megoldásvektornak ezen területen belül kell lennie.

A súlyvektor lépésenkénti módosítását az ábrán követhetjük. x₂ esetében pl. módosításra van szükség, hiszen $w^T\text{(}1\text{)}{x}_2$ > 0, holott $x_2\in X^{\left(2\right)}$ , tehát negatív eredményt kellett volna kapnunk. A súlyvektor értékét x₂-vel arányosan csökkentenünk kell. E módosítás következtében létrejött w(2) súlyvektor viszont rosszul osztályozza x₃-at, tehát ismételt módosításra van szükség, ezúttal a súlyvektorhoz egy, az x₃-mal arányos vektort kell hozzáadnunk. Az eljárást így kell folytatnunk mindaddig, míg az összes tanító vektorral megfelelő előjelű skalár szorzatot nem kapunk, vagyis, amíg a megoldás-tartományon belülre nem kerül a súlyvektor. Az ábrán ez w(5)-nél következik be.

A továbbiakban megmutatjuk, hogy a perceptron a lineáris szeparáló felületet véges számú tanuló lépés alatt megtalálja.

A bizonyítás azon alapul, hogy ${\Vert w\left(k\right)\Vert }^2$ növekedése két korlát közé szorítható: egyrészt ${\Vert w\left(k\right)\Vert }^2$ < ${\alpha }^2$ kM, másrészt ${\Vert w\left(k\right)\Vert }^2\ge \frac{{\alpha }^2{k}^2{b}^2}{{\Vert w^{\ast }\Vert }^2}$ , ahol M a bemeneti mintavektorok normanégyzetének felső korlátja: ${\Vert x_i\Vert }^2\le M$ , b pedig a megoldás-súlyvektorra vonatkozó

$w^{\ast T}{x}_i\ge b>\mathrm{0,}$ ha $x_i\in X^{\left(1\right)}$

és

$w^{\ast T}{x}_i\le -b<\mathrm{0,}$ ha $x_i\in X^{\left(2\right)}$

feltételek kis pozitív konstansa.

Az egyszerűbb tárgyalás kedvéért a kiinduló tanítópontokból alakítsunk ki egy módosított mintahalmazt, ${\text{X}}^{(\ast )}$ -ot, ami az ${\text{X}}^{\left(1\right)}$ -beli pontokból és az ${\text{X}}^{\left(2\right)}$ -beli pontok mínusz egyszereséből áll. Ez azt jelenti, hogy $\forall x\in {\text{X}}^{(\ast )}$ -ra $w^{\ast T}x\ge b$ > 0 kell teljesüljön, vagyis a módosított tanítóhalmaz min-den elemére igaz, hogy a megoldás súlyvektor által meghatározott sík pozitív felén fog elhelyez-kedni.

Tanító lépésre akkor van szükség, ha a pillanatnyi súlyvektor a bemenetre kerülő mintavektort nem megfelelő osztályba sorolja, vagyis, ha bármely $x\in {\text{X}}^{(\ast )}$ -ra a pillanatnyi súlyvektorral végzett skalár szorzat $w{\text{(}k-1\text{)}}^{T}x\le 0$ . A módosított mintahalmazzal végzett tanítás esetén

$w\left(k\right)=w\left(k-1\right)+\alpha x\left(k\right)$ , (3.5)

ahol x(k) tehát a k-adik tanító lépésben a perceptronra kerülő olyan minta, amit az aktuális súlyvektor mellett a perceptron rosszul osztályoz. Minden korrekciós lépésben a pillanatnyi (módosított) bemenővektor konstansszorosát adjuk a súlyvektorhoz, ahol most már α > 0.

A módosított tanító pontok felhasználása során képezzünk egy képzeletbeli listát, amelybe csak azok a tanító pontok tartoznak, amelyeket az adott lépésben a hálózat hibásan osztályoz. Ez azt jelenti, hogy ha w(k-1) jelöli a k-adik lépésben az aktuális súlyvektort és x(k) a képzeletbeli listának azt az elemét, amit a k-adik lépésben veszünk elő, akkor $w^T\left(k-1\right)x\left(k\right)\le 0$ adódik, tehát súlymódosításra van szükség. A tanítás során a listában az eredeti mintahalmaz minden eleme akárhányszor előfordulhat.

Kövessük végig a súlyvektor alakulását feltételezve, hogy a kiinduló érték $w\left(0\right)=0$ . Az első, a második, ill. a k-adik lépésben kialakuló súlyvektor ennek megfelelően:

$w\left(1\right)=\alpha x\left(1\right)$

$\begin{array}{l}w\left(2\right)=w\left(1\right)+\alpha x\left(2\right)=\alpha \left[x\left(1\right)+x\left(2\right)\right]\\ ⋮\end{array}$ (3.6)

$w\left(k\right)=w\left(k-1\right)+\alpha x\left(k\right)=\alpha {\displaystyle \sum _{i=1}^{k}x\left(i\right)}$

Képezzük a $w^T\left(k\right)w^{\ast }$ skalár szorzatot:

$w^T\left(k\right)w^{\ast }=\alpha \left(x{\left(1\right)}^T{w}^{\ast }+x{\left(2\right)}^T{w}^{\ast }+\mathrm{...}+x{\left(k\right)}^T{w}^{\ast }\right)\ge \alpha kb$ , (3.7)

Felhasználva a Schwartz egyenlőtlenséget

${\Vert w\left(k\right)\Vert }^2{\Vert w^{\ast }\Vert }^2\ge {\left(w^T\left(k\right)w^{\ast }\right)}^2\ge {\alpha }^2{k}^2{b}^2$ (3.8)

amiből adódik, hogy:

${\Vert w\left(k\right)\Vert }^2\ge \frac{{\alpha }^2{k}^2{b}^2}{{\Vert w^{\ast }\Vert }^2}$ (3.9)

vagyis, a súlyvektor normanégyzete legalább a lépésszám négyzetével arányosan nő.

A súlyvektor normanégyzetére ugyanakkor felső korlát is állítható, ugyanis

$w\left(k\right)=w\left(k-1\right)+\alpha x\left(k\right)$ , (3.10)

így felírható, hogy

${\Vert w\left(k\right)\Vert }^2={\Vert w\left(k-1\right)\Vert }^2+2\alpha \left(w^T\left(k-1\right)x\left(k\right)\right)+{\alpha }^2{\Vert x\left(k\right)\Vert }^2$ . (3.11)

Mivel tanító lépésre azért van szükség, mert $w^T\left(k-1\right)x\left(k\right)\le 0$ , ebből következik, hogy

${\Vert w\left(k\right)\Vert }^2-{\Vert w\left(k-1\right)\Vert }^2\le {\alpha }^2{\Vert x\left(k\right)\Vert }^2$ . (3.12)

Amennyiben a kezdeti súlyvektor hossza nulla, vagyis $w\left(0\right)=0$ , a fentiekből adódik, hogy

${\Vert w\left(k\right)\Vert }^2\le {\alpha }^2{\displaystyle \sum _{i=1}^k{\Vert x\left(i\right)\Vert }^2\le {\alpha }^{2}kM}$ , (3.13)

feltéve, hogy kiinduló megállapításunk, miszerint az összes tanító vektor normanégyzete felülről korlátos, igaz. Ez azt jelenti, hogy a vektor normanégyzete nem nőhet a lépésszámmal arányosnál gyorsabban. A két korlát összevetéséből következik, hogy véges számú lépés után az eljárásnak le kell állnia.

A tanító lépések számának felső korlátja, $k_{\text{max}}$ arányos a bemeneti vektor dimenziójával, de nem függ a tanítópontok számától. Természetesen egy tényleges tanító eljárásnál a konvergencia ideje függ a tanítópontok számától, hiszen minél több tanítópontunk van, annál több pontra kell elvégezni az ellenőrzést, hogy vajon a pillanatnyi súlyvektor mellett a hálózat már helyesen működik-e. Azt is látnunk kell, hogy a konvergencia ténye nem függ α értékétől, hiszen csupán annyit kötöttünk ki, hogy legyen α > 0. A konvergencia sebességét azonban már befolyásolja α megválasztása. Így a perceptron tanulásnak különböző változatai alakultak ki, melyek α megválasztásában térnek el. Az eddig bemutatott tanulásnál α előre rögzített konstans, ezért ezt szokás fix növekményes tanulási szabálynak is nevezni, szemben a lépésenként változó α-t használó módszerekkel. Minthogy elvi különbség ezen módszerek között nincs, a változó növekményes eljárásokat nem részletezzük. A különböző perceptron tanulási változatok részletes bemutatása megtalálható pl. a következő irodalmakban: [Nil65], [Has95], [Vee95].

Mint a neurális hálózatok többsége, a perceptron is felfogható, mint egy asszociatív memória. A hálózatnak bizonyos bemenetekre kell jó válaszokat adnia, asszociálnia, amelyet úgy érünk el, hogy a hálózat súlyainak meghatározásához tanítópontokat használunk fel. Valójában tehát a tanítópontok felhasználása úgy is felfogható, mint egy tárolási folyamat, ahol a tanítópontokat valamilyen módon a hálózat súlyaiban tároljuk. Felmerül a kérdés, hogy hány tanítópont tárolható a hálózatban úgy, hogy a háló a megkívánt működést mutassa, illetve általában milyen válaszokat ad a hálózat egy megtanított esetben. Erre a kérdésre ad feleletet a hálózatok kapacitása. Az alábbiakban a perceptron kapacitásátvizsgáljuk [Cov65].

A perceptront eddig úgy mutattuk be, mint egy olyan egyszerű hálózatot, amely az N-dimenziós mintateret egy (N-1)-dimenziós hipersíkkal két tartományra tudja bontani. A perceptron szeparáló képességével kapcsolatban a következő kérdés merül fel: hány, két különböző osztályból származó pontot helyezhetünk el véletlenszerűen egy N-dimenziós mintatérben akkor, ha azt kívánjuk, hogy a két osztály pontjai egy hipersíkkal szétválaszthatók legyenek. Másképp fogalmazva: N-dimenziós bemeneti pontok esetén, P véletlenszerűen kiválasztott pont mellett $2^P$ kétosztályos szeparálás − vagyis amikor a pontok egy részéhez +1-et, a többihez -1-et rendelünk − lehetséges; kérdés, hogy a $2^P$ lehetőség közül hány olyan eset van, amikor a két osztályba tartozó pontok elválasztása hipersíkkal megtörténhet, tehát amikor a szeparálási feladatot egy perceptron meg tudja oldani.

Jelöljük ezen esetek számát L(P,N)-nel. Definiáljuk a perceptron kapacitását úgy, mint a lineárisan szeparálható kétosztályos esetek számának és az összes kétosztályos eset számának arányát, vagyis C(P,N)=L(P,N)/ $2^P$ . Megmutatható, hogy a kapacitás a következő összefüggéssel adható meg:

$C\text{(}P,N\text{)}=\{\begin{array}{c}\begin{array}{l}1\text{ha }P\le N\\ \end{array}\\ \frac{2}{2^P}{\displaystyle \sum _{i=0}^{N-1}\left(\begin{array}{c}P-1\\ i\end{array}\right)\text{ ha}P>N}\end{array}$ (3.14)

A kapacitás meghatározásának részletes bemutatásától eltekintünk (az érdeklődő olvasó a részletes származtatást például a [Her91] irodalomban megtalálja). A kapacitás alakulását a P/(N+1) arány függvényében a 3.3 ábrán mutatjuk be.

Látható, hogy ha N elég nagy, akkor P<2N esetében gyakorlatilag az összes kétosztályos szeparálás lineáris szeparálás, míg ezen érték fölött lineáris szeparálás egyre kevésbé lehetséges: ha P/N>>2 a lineárisan szeparálható esetek száma nullához tart. Az is látható, hogy, ha $P\le N$ , akkor C(P, N)=1, vagyis, ha a mintapontok száma nem nagyobb, mint a bemeneti tér dimenziója és a pontok általános elhelyezkedésűek, a lineáris szeparálás mindig lehetséges, bármilyen módon is rendeljük a pontokat a két osztályhoz. A pontok akkor és csak akkor általános elhelyezkedésűek, ha (*) P>N és a P pontból nem tudunk kiválasztani N+1 olyan pontot, melyek egy (N-1)-dimenziós hipersíkon helyezkednek el; illetve, ha (**) P≤N és a P pont nem helyezkedik el egy N-2 dimenziós hipersíkon.

A perceptron kapacitásra vonatkozó eredmény alapján látható, hogy ha a tanítópontok száma a pontok dimenziójához képest elegendően nagy, akkor a mintapontok lineárisan nem lesznek szeparálhatók. A gyakorlati problémák döntő többsége lineárisan nem szeparálható feladat, vagyis az egyszerű perceptronnal nem megoldható.

A perceptron kapacitásmeghatározásának a jelentősége az, hogy ezáltal megmutatható, hogy a bemeneti szeparálandó pontok számához viszonyítva kellően nagyra választva a bemeneti tér dimenzióját − ami azt is jelenti egyben, hogy kellően nagyra választva a perceptron súlyainak számát − a kétosztályos feladatok lineárisan szeparálható feladatok lesznek. Ezt az eredményt bizonyos hálózatok konstrukciójánál fel is használhatjuk (ld. pl. a bázisfüggvényes hálózatokat, melyeket a 6. fejezet mutat be).