A paramétereiben lineáris modellek a neuronhálók témakörén belül is kitüntetett fontosságúak. Ekkor, továbbá, ha négyzetes hibafüggvényt alkalmazunk, kvadratikus hibafelületet kapunk, amelynek a minimumpontjához tartozó paramétervektor meghatározása a cél.

A négyzetes hibafelületre vonatkozó eljárásokat és eredményeket az

$y=w^{T}x$ (2.48)

lineáris kapcsolat feltételezésével fogjuk megvizsgálni, de az eredmények értelemszerűen alkalmazhatók a (2.46)-ben megfogalmazott általánosabb kapcsolat esetére is.

Ha kritériumként az átlagos négyzetes hibát tekintjük, a minimalizálandó összefüggés:

$\begin{array}{c}C\text{(}w\text{)}=E\left\{{\left(d-w^{T}x\right)}^2\right\}\\ =E\left\{d^2\right\}-2E\left\{d{x}^T\right\}w+w^{T}E\left\{x{x}^T\right\}w\\ =E\left\{d^2\right\}-2p^{T}w+w^{T}Rw,\end{array}$ (2.49)

ahol $R=E\left\{x{x}^T\right\}$ a bemenet autokorrelációs mátrixa, $p=E\left\{dx\right\}$ pedig egy olyan oszlopvektort jelöl, amely a kívánt kimenet és a bemenet közötti keresztkorrelációt mutatja.

A szélsőérték a C(w) négyzetes hiba w szerinti

$\nabla C\left(w\right)=\frac{\partial C\text{(}w\text{)}}{\partial w}=2\text{(}Rw-p\text{)}$ , (2.50)

parciális deriváltjának nulla értékéhez tartozik, amelyből − amennyiben $R^{-1}$ létezik − az optimális paraméterkészlet a Wiener-Hopf egyenlet szerint határozható meg:

$w^{\ast }=R^{-1}p.$ (2.51)

A (2.51) összefüggés szerint az átlagos négyzetes hiba minimumát biztosító megoldásvektor analitikusan is meghatározható, ha a d_i kívánt válaszok és az x_i bemenetek statisztikai jellemzői, R és p ismertek, ami a gyakorlatban a legritkább esetben teljesül. Ha csak a mintapontok állnak rendelkezésünkre, az analitikus összefüggés alkalmazásához előbb R-et és p-t a véges számú mintapont alapján becsülnünk kell. Ennek, továbbá a (2.51) összefüggés szerinti mátrix invertálásnak az elkerülése érdekében a továbbiakban olyan módszereket fogunk vizsgálni, amelyek vagy eleve kevesebb ismeret meglétét igénylik, vagy amelyek a tanítópontokból iteratív úton igyekeznek minél több ismeretet összegyűjteni (pontosítani).

Mielőtt azonban ezekre rátérnénk, a [Wid85] irodalmat követve bemutatjuk a fentiekben vázolt, ideálisnak tekinthető megoldás néhány lényeges tulajdonságát.

Először a (2.51) összefüggést a (2.49) hibakifejezésbe helyettesítve megkapjuk az elérhető négyzetes hiba minimumát:

$C_{\text{min}}=E\left\{d^2\right\}-p^T{R}^{-1}p=E\left\{d^2\right\}-p^T{w}^{\ast }.$ (2.52)

Sokszor előnyös, ha egy paraméter tényleges értéke helyett az ideális paraméter-értéktől való eltéréssel, azaz a paraméter-hibával dolgozunk. Ezért alakítsuk át ennek megfelelően a (2.49) összefüggést (2.52) felhasználásával. A hiba

$C\left(w\right)=C_{\text{min}}+{\text{(}w-w^{\ast }\text{)}}^{T}R{\text{(}w-w^{\ast }\text{)}}^T=C_{\text{min}}+v^{T}Rv$ (2.53)

alakba írható, ahol $v=w-w^{\ast }$ . A (2.53) összefüggés jól mutatja, hogy a kritériumfüggvény a W paramétertér felett egy kvadratikus hibafelülettel jellemezhető, amelynek − ha R pozitív definit − a $w=w^{\ast }$ mellett minimumpontja van.

A (2.49) és a (2.53) összefüggésekből kiindulva ebben a formába is felírható a gradiens vektor:

$\nabla C\left(v\right)=\frac{\partial C\left(v\right)}{\partial v}=2Rv=2R\text{(}w-w^{\ast }\text{)}=2\text{(}Rw-p\text{)}$ (2.54)

Az átlagos négyzetes hiba (2.53) szerinti összefüggése tömör formában jelzi, hogy a kritériumfüggvény paraboloid hibafelületet ír le, melynek jellemzőit az R mátrix határozza meg. Ebből egyértelműen arra a következtetésre juthatunk, hogy a (2.49) összefüggéssel definiált hiba a négyzetes jelleg megtartása mellett csak a bemeneti jeltől, pontosabban annak korrelációs mátrixától függ. A későbbiekben látni fogjuk, hogy a szélsőérték-kereső eljárások hatékonyságát befolyásolják a hibafelület tulajdonságai − a hibafelület alakja −, ezért ezzel a kérdéssel most kiemelten foglalkozunk.

Elsőként − kétdimenziós paramétertér feltételezése mellett − gondolatban rajzoljuk fel a paraméterek síkján a (2.53) összefüggés szerinti hibafelület "szintvonalait". A szintvonalak − az ún. izokritérium görbék − egy görbesereget alkotnak. A görbesereg egy eleme − egy izokritérium görbe − azon pontok mértani helyét adja meg, amelyekhez (egy adott) állandó kritériumfüggvény-érték tartozik. Minden ilyen görbe egy-egy ellipszist jelöl ki, amely a síkban általános helyzetben (de egymáshoz képest kötötten), helyezkedik el a sík koordináta tengelyeihez képest. Egy ilyen ellipszis előállítható úgy is, hogy a paraboloid hibafelületet egy, a paraméterek síkjával párhuzamos, ettől a síktól a rögzített négyzetes hiba értéknek megfelelő távolságra lévő síkkal elmetszünk. Különböző hibaértékekhez különböző, de koncentrikus, azaz olyan ellipsziseket kapunk, melyek főtengely irányai egybeesnek (ld. 2.12 ábra). Ez a geometriai kép tetszőleges dimenzióra általánosítható. Könnyen belátható, hogy a metszék-ellipszisek (ill. ellipszoidok) főtengelyei kitüntetett irányok. A hibafelület ezen irányokban található bármely pontjánál ugyanis a gradiens irányok egybeesnek a főtengely irányokkal, azaz mindig a középpont felé mutatnak. Így ezen pontokból kiindulva a gradiensek mentén közvetlenül a középpont felé mozoghatunk, illetve ennek megfelelően a hibafelületen a minimumhely felé "ereszkedhetünk". A mértani helyet tovább vizsgálva arra az érdekes következtetésre juthatunk, hogy a főtengely irányokat az R mátrix sajátvektorai jelölik ki, tehát a későbbiekben jól felhasználható eredményre vezet az R mátrix sajátérték/sajátvektor rendszere. Ha feltesszük, hogy a sajátértékek multiplicitása egy és az R mátrix egy N×N-es mátrix (N a bemeneti vektorok dimenziója), akkor R felírható az alábbi formában

$R\text{=}Q\Lambda Q^{-1}$ , (2.55)

ahol $\Lambda =\text{diag}\langle \lambda {\text{}}_{\text{0}},\lambda {\text{}}_{\text{1}},\dots ,\lambda {\text{}}_{N\text{-1}}\rangle$ a sajátértékekből képezett diagonál mátrix, Q pedig a sajátvektorok mátrixa. Ha a sajátvektorokat egységnyi hosszúságúra normáljuk, és felhasználjuk azt a tulajdonságot, hogy a szimmetrikus négyzetes mátrixok sajátvektorai ortogonálisak (vagyis Q ortonormált), akkor:

$Q^{-1}=Q^T,\text{azaz}R\text{=}Q\Lambda Q^T.$ (2.56)

Behelyettesítve a (2.56) kifejezést a (2.53) összefüggésbe, a hibára

$\begin{array}{c}C\left(v\right)=C_{\text{min}}+v^{T}Rv=C_{\text{min}}{v}^T\left(Q\Lambda Q^T\right)v=C_{\text{min}}+{\left(Q^{T}v\right)}^T\Lambda \left(Q^{T}v\right)=\\ =C_{\text{min}}+v{\text{'}}^T\Lambda v\text{'}\end{array}$ (2.57)

adódik. Az új kifejezésben v'-t egy forgatási transzformációval kaphatjuk meg v-ből, amit értelmezhetünk úgy, hogy a hibafelület "alatt" elforgattuk a paraméterek koordináta-rendszerét olyan mértékben, hogy a koordinátatengelyek éppen főtengely irányúak legyenek. Ebben a koordinátarendszerben a (2.54) összefüggésnek megfelelő gradiens vektor a következőre adódik:

$\nabla C\text{(}{v}^{\prime }\text{)}=\frac{\partial C\text{(}{v}^{\prime }\text{)}}{\partial v^{\prime }}=2\Lambda v^{\prime }=2\left[\begin{array}{cccc}\lambda {}_0{v^{\prime }}_0& \lambda {}_1{v^{\prime }}_1& \mathrm{....}& \lambda {}_{N-1}{v^{\prime }}_{N-1}\end{array}\right]$ (2.58)

A gradiens komponensei tehát a megfelelő sajátértékek és a paraméterhiba-komponensek szorzataként számíthatók. A sajátértékekhez szemléletes jelentés is rendelhető, ugyanis a főtengely-irányokban számított második derivált komponensek az R mátrix sajátértékeinek kétszeresei lesznek:

$\frac{{\partial }^{2}C\left(v^{\prime }\right)}{\partial {v^{\prime }}_i{}^2}=2\lambda {}_i$ . $$ (2.59)

Mindezekből képet alkothatunk a paraboloid hibafelület geometriai tulajdonságairól. Ha a bemeneti jel autokorrelációs mátrixának sajátértékei jelentősen eltérnek egymástól, akkor a paraboloid hibafelület a különböző főtengely irányokban is jelentősen eltérő meredekségű lesz. Ez a tulajdonság − mint látni fogjuk − általában kedvezőtlen az ún. gradiens-alapú szélsőérték-kereső eljárások szempontjából. A 2.12 ábra nemcsak a hibafelületet jellemző izokritérium görbéket, hanem a w, v és v’ koordinátarendszereket is mutatja.

Ha a gradiens

$\nabla C\left(w\right)=2R\left(w-w^{\ast }\right)$ (2.60)

szerinti felírását balról megszorozzuk $\frac{1}{2}{R}^{-1}$ -gyel, akkor átrendezés után a

$w^{\ast }=w-\frac{1}{2}{R}^{-\text{1}}\nabla C\text{(}w\text{)}$ (2.61)

alakot kapjuk, amely négyzetes hibafelület esetén tetszőleges kiinduló w mellett közvetlenül megadja az optimális megoldást.

Ha a hibafelület nem négyzetes, a (2.61) összefüggés akkor is alkalmas kiindulás egy iteratív eljárásra. (Nem kvadratikus függvényeknél tekinthetjük úgy, mintha ezek másodfokú Taylor-sorával dolgoznánk, annál is inkább, mivel a megoldás − a minimumhely − közelében a nem másodfokú függvények jó közelítéssel úgy viselkednek, mint a négyzetes függvények.) Az iteratív eljárásoknál lépésenként módosítjuk a megoldást: az épp érvényes megoldásból kiindulva, annak korrekciójával kapjuk a következő lépés érvényes megoldását.

A Newton eljárás iteratív összefüggése, ha az egyes iterációs lépések indexét k-val jelöljük

$w\text{(}k+1\text{)}=w\text{(}k\text{)}-\mu R^{-1}\nabla C\left(k\right)$ . (2.62)

ahol $\nabla C\left(k\right)=\nabla C\left(w\text{(}k\text{)}\right)$ a gradiensvektort jelöli a k-adik lépésben érvényes paramétervektor mellett, míg 0 < μ < 1 az ún. tanulási tényező (learning rate), amelyet négyzetes esetben az egylépéses konvergenciához 1/2-re kell választani. Megjegyezzük, hogy a μ tanulási tényezőt bátorsági tényezőnek is szokás nevezni, mivel értéke befolyásolja, hogy adott gradiens irányában mekkora lépésekben haladunk. Ha az utóbbi összefüggésben visszaírjuk a derivált (2.60) szerinti alakját, és mindkét oldalból levonjuk w*-ot, akkor a

$w\left(k+1\right)-w^{\ast }=\left(1-2\mu \right)\left(w\left(k\right)-w^{\ast }\right)={\left(1-2\mu \right)}^{k+1}\left(w\left(0\right)-w^{\ast }\right),$ (2.63)

összefüggést, illetve az ennek megfelelő

$v\left(k+1\right)={\left(1-2\mu \right)}^{k+1}v\left(0\right)$ (2.64)

iterációs kapcsolatot kapjuk, amely konvergens, ha 0 < μ < 1, és négyzetes hibafelületnél egy lépésben optimumot ad, ha $\mu =1/2$ .

Ez a módszer a negatív gradiens irányában"ereszkedik" a hibafelületen. Iteratív összefüggése:

$w\text{(}k+1\text{)}=w\text{(}k\text{)}+\mu \left(-\nabla C\text{(}k\text{)}\right).$ (2.65)

A (2.65) összefüggésben a fentiekhez hasonlóan visszaírva a gradiens (2.60) szerinti alakját, és ismét mindkét oldalból levonva $w^{\ast }$ -ot, a

$w\text{(}k+1\text{)}-w^{\ast }=\left(I-2\mu R\right)\left(w\text{(}k\text{)}-w^{\ast }\right)={\left(I-2\mu R\right)}^{k+1}\left(w\text{(}0\text{)}-w^{\ast }\right)$ , (2.66)

illetve az ennek megfelelő

$v\text{(}k+1\text{)}={\text{(}I-2\mu R\text{)}}^{k+1}v\left(0\right)$ (2.67)

összefüggést kapjuk. Ez utóbbi kifejezésből látható, hogy ennél az eljárásnál a μ tanulási tényező megválasztása függ R-től. Ha áttérünk a főtengely-irányú koordinátákra, mint ahogy azt korábban a (2.57) összefüggésben tettük, akkor (2.67) helyére a

$v^{\prime }\text{(}k+1\text{)}={\text{(}I-2\mu \Lambda \text{)}}^{k+1}{v}^{\prime }\text{(}0\text{)}$ (2.68)

összefüggés írható, amely lehetővé teszi, hogy a paraméter-hibákat komponensenként vizsgáljuk. A (2.68) összefüggésből jól látható, hogy a konvergencia feltétele ekkor:

$0<\mu <\frac{1}{\lambda {}_{\text{max}}}$ , (2.69)

ahol ${\lambda }_{\text{max}}$ R legnagyobb sajátértéke.

A (2.62), és (2.65) összefüggések összevetéséből látszik, hogy a Newton módszer szerinti iterációban elkerülhetetlen R ismerete, míg a gradiens menti iteráció R ismeretét közvetlenül nem igényli. A μ tanulási tényező helyes megválasztásához azonban mégis kell valamennyi ismeret a bemeneti jelről. Sokszor megfelelő a

$\lambda {}_{\text{max}}\le {\displaystyle \sum _{n=1}^N\lambda {}_n=\text{tr(}\Lambda \text{)=tr}\left(R\right)}$ (2.70)

összefüggés használata, amellyel a

$0<\mu <\frac{1}{\text{tr(}R\text{)}}$ (2.71)

előírás adódik, ahol tr(R), az autokorrelációs mátrix nyoma, amelyet a mintapontokból az alábbi módon becsülhetünk:

$\text{tr(}R\text{)}\approx {\displaystyle \sum _{j=1}^N\frac{1}{l}{\displaystyle \sum _{i=1}^l{x}_{ij}^2}}$ . (2.72)

Itt x_ij az i-edik bemeneti vektor j-edik komponense (i=1, 2, …, l ; j=1, 2, …, N). A tanulási tényező megválasztása a szélsőérték-keresés igen kritikus lépése, mert közvetlenül befolyásolja az eljárás stabilitását, ill. a konvergencia sebességét.

A (2.69) összefüggésből látható, hogy a konvergencia sebessége a bemeneti jel korrelációs mátrixától, pontosabban annak sajátértékeitől függ. Az is látható, hogy az eljárás konvergenciájának biztosításához a tanulási tényezőre felső korlát adható. A felső korlát azonban valóban csak a konvergencia tényét garantálja, miközben az eljárás gyakorlati alkalmazása szempontjából a konvergencia sebessége is fontos.

Az előzőekben láttuk, hogy a ${\lambda }_i$ sajátértékekhez szemléletes jelentés is rendelhető. A paraboloid hibafelület főtengely irányait R sajátvektorai adják meg. Az i-edik sajátvektor, q_i irányában a hibafelület második deriváltja viszont arányos a sajátvektorhoz tartozó ${\lambda }_i$ sajátértékkel. Minél nagyobb egy sajátérték, annál nagyobb a hibafelület adott irány menti meredekség-változása, azaz a görbülete. A konvergenciára vonatkozó (2.69) összefüggés a konvergencia tényét még a hibafelület legmeredekebb iránya mentén is garantálja, viszont más irányok mentén még nagyobb μ mellett is garantált lenne a konvergencia. A főtengely irányok mentén az adott sajátvektorhoz tartozó sajátérték reciproka jelenti a konvergenciát még biztosító tanulási tényező felső korlátját.

A (2.69) által megfogalmazott korlát betartása azért szükséges, mert általában nem ismerjük, hogy a hibafelület mely pontjából indulunk ki, így a konvergencia csak akkor garantálható, ha az a kiindulási ponttól függetlenül minden körülmény mellett fennáll. A hibafelület kevésbé meredek részein a túl kis tanulási tényező ugyanakkor a lehetségesnél kisebb konvergencia-sebesség elérését eredményezi. A konvergencia-sebesség szempontjából tehát az a kedvező, ha a sajátértékek egyformák vagy közel azonosak, vagyis ha $\Lambda \approx I$ . Különösen kedvezőtlen esettel állunk szemben, ha a legkisebb és a legnagyobb sajátértékek aránya, ${\lambda }_{\text{max}}/{\lambda }_{\text{min}}>>1$ . Ez egy keskeny hibafelületet jelent. Keskeny hibafelületnél kedvezőtlen kiinduló pont mellett a konvergencia nagyon lassú is lehet.

Felmerül a kérdés, hogy ilyen esetekben lehet-e valami olyan módosítást tenni, ami a konvergencia-sebesség növelését eredményezi. A válasz pozitív. Ha a bemeneteket olyan módon transzformáljuk, hogy a transzformált bemenetek autokorrelációs mátrixa közel egységmátrix, a sajátértékek közel egyformák lesznek, így kiindulóponttól függetlenül a legkedvezőbb tanulási tényező választható. Ennél a megoldásnál a legmeredekebb lejtő gradiens eljárást a „transzformált” térben végezzük. A módszer részletesebb bemutatását a későbbiekben a transzformált tartománybeli LMS eljárásnál adjuk meg.

A (2.51) összefüggés a w paraméterekre nézve egy lineáris egyenletrendszer megoldása, amelyhez az R mátrix inverze szükséges. Az

$R{w}^{\ast }=p$ (2.73)

egyenlet megoldása egyszerűsíthető az ún. konjugált irányok ismeretében. A konjugált irányokat azok a $q_{\mathrm{0,}}{q}_{\mathrm{1,}}\mathrm{....,}{q}_{N-1}$ vektorok jelölik ki, amelyekre fennáll, hogy

$q_i^{T}R{q}_j=0,i\ne j.$ (2.74)

Könnyen belátható, hogy a $\left\{q_i\right\}$ vektorok lineárisan függetlenek és egy olyan bázist alkotnak, amely kifeszíti a $\left\{w\left(k\right)\right\}$ paraméterek terét, így segítségükkel előállítható a paraméterek terének az a vektora is, amely a $w_0$ vektorból elvezet a $w^{\ast }{}^{}$ vektorba:

$w^{\ast }-w_0={\displaystyle \sum _{j=0}^{N-1}{\alpha }_j{q}_j}.$ (2.75)

Itt $\left\{{\alpha }_j\right\}$ a lineáris kombináció súlytényező készletét jelöli. Ha a (2.75) összefüggés mindkét oldalát megszorozzuk balról $q_j^{T}R$ -rel, és $R{w}^{\ast }$ helyére behelyettesítjük p-t ((2.73) alapján), akkor a konjugált irányok (2.74) feltétele miatt az ${\alpha }_j$ -re nézve N-ismeretlenes lineáris (2.75) egyenletrendszer "szétesik", és ${\alpha }_j$ -k közvetlenül megadhatók lesznek (és egyben nyilvánvalóvá válik a konjugált q vektorok használatának az előnye is):

${\alpha }_j=\frac{q_j^T\left(p-Rw\left(0\right)\right)}{q_j^{T}R{q}_j}$ . (2.76)

Ezek után definiálhatunk egy iteratív eljárást w(k+1) számítására:

$w\left(k+1\right)=w\left(k\right)+{\alpha }_k{q}_k,$ (2.77)

ahol

$w\left(k\right)=w\left(0\right)+{\displaystyle \sum _{j=0}^{k-1}{\alpha }_j{q}_j}\text{}\text{},\text{és }w\left(N\right)=w^{\ast },$ (2.78)

tehát N lépésben elérjük az optimumot.

A (2.77) összefüggésben szereplő ${\alpha }_k$ tényező egy alternatív kifejezése nyerhető, ha felhasználjuk a (2.74) és (2.78) összefüggéseket annak igazolására, hogy

$q_k^{T}Rw\left(k\right)=q_k^{T}Rw\left(0\right).$ (2.79)

Ekkor ugyanis a (2.76) összefüggésben w(0) w(j)-re cserélhető, és így (2.60) felhasználásával

${\alpha }_j=-\frac{1}{2}\frac{q_j^T\nabla C\left(j\right)}{q_j^{T}R{q}_j}$ (2.80)

adódik.

A $\left\{q_i\right\}$ konjugált gradiens irányok meghatározása iteratívan történik úgy, hogy a kezdőérték $q_0=-\nabla C{\left(0\right)}_{}$ , azaz a kezdőpontban érvényes negatív gradiens adja a legelső irányt, majd a következő irányok rendre az aktuális gradiens és a megelőző irány lineáris kombinációjaként kerülnek kiszámításra:

$q_{k+1}=-\nabla C\left(k+1\right)+{\beta }_k{q}_k,$ (2.81)

Ha ezt a kifejezést jobbról megszorozzuk $R{q}_k$ -val, megkapjuk ${\beta }_k$ ahhoz szükséges új értékét, hogy az új irány konjugált irány legyen:

${\beta }_k=\frac{\nabla C^T\left(k+1\right)R{q}_k}{q_k^{T}R{q}_k}.$ (2.82)

Mivel (2.60) és (2.77) felhasználásával

$\nabla C\left(k+1\right)-\nabla C\left(k\right)={\alpha }_{k}R{q}_k,$ (2.83)

a (2.82) összefüggésből $R{q}_k$ kiejthető és így ${\beta }_k$ -ra a következő kapható

${\beta }_k=\frac{\nabla C^T\left(k+1\right)\left(\nabla C\left(k+1\right)-\nabla C\left(k\right)\right)}{q_k^T\left(\nabla C\left(k+1\right)-\nabla C\left(k\right)\right)}$ . (2.84)

Az algoritmus tehát a kezdőpontbeli negatív gradiens, mint kezdeti irány választása mellett számolja az új paramétert a (2.77) egyenlet szerint úgy, hogy olyan ${\alpha }_k$ értéket vesz, melynél a hibakritérium értéke minimális (az ${\alpha }_k$ szerinti derivált nulla; ún. vonalmenti keresés, line search módszer). Erre azért van szükség, mert az esetek többségében R ismeretének hiányában ${\alpha }_k$ (2.80) alapján nem számolható közvetlenül. Ezután az új paraméterhez tartozó gradienst számítjuk, amelynek birtokában (2.82) alapján új ${\beta }_k$ -t határozunk meg. Ezzel az új irány (2.81)-ból számítható.

Meg kell jegyezni, hogy a ${\beta }_k$ együtthatók meghatározására léteznek egyéb módszerek is, melyek más kifejezésre vezetnek. Ennek jelentősége abban rejlik, hogy azon esetben, ha az egymás után következő gradiensek különbsége nullává válik (vagyis az (2.84) szerinti összefüggés használhatatlan lesz a nevező nullává válása miatt), a konjugált gradiens módszer akkor is használható a ${\beta }_k$ -kra vonatkozó más kifejezés alkalmazásával. Vizsgálatokat végeztek annak meghatározására is, hogy különböző feladattípusoknál a ${\beta }_k$ -k meghatározásának melyik módszere a legjobb.

A módszer fontos jellemzője, hogy kvadratikus, N-dimenziós kritériumfelület esetén a (2.78) összefüggés értelmében a konjugált gradiensek módszere N lépésben konvergál. A gyorsabb konvergencia annak tudható be, hogy minden egyes lépésnél a (2.77), (2.78) és (2.80) egyenletek által meghatározott új w(k) a (2.49) egyenletben definiált négyzetes hibafüggvényt minimalizálja w szerint az addigi irányok (q₀, q₁,...,q_k) által kifeszített altér felett. (Bizonyítható, hogy az algoritmus szerint számított gradiens irányok mindig merőlegesek a korábbi lépésekben meghatározott q irányokra. Ebből az ortogonalitásból pedig következik az előbbi kijelentés [Joh92]. Ezzel szemben a többi gradiens alapú eljárásnál, mint pl. a legmeredekebb lejtő módszernél, az új irány menti minimalizálás ″leronthatja″ a korábbiak hatását. Ezt illusztrálja a 2.13 ábra, ahol a konjugált gradiens módszeren (c) kívül a legmeredekebb lejtő módszer esetére is láthatunk két példát. Amennyiben a lépésnagyság az egyes iterációknál kicsi (kis μ tanulási tényezőt használunk), sok lépésben, de a trajektória (az ideális útvonal) mentén közelítjük meg a minimumhelyet (a), míg nagyobb lépésnagyság mellett láthatóan felesleges paraméterváltoztatásokra is sor kerül (b).

Összefoglalva az algoritmus a következő iterációs lépésekből áll:

A konjugált gradiens eljárást, vagy az eljárás valamilyen változatát kedvező konvergencia tulajdonságai miatt gyakran alkalmazzák neuronhálók tanításánál. Egyes neuronhálóknál kedvelt az ún. momentum módszer, amely a konjugált gradiens eljáráshoz hasonló heurisztikus gradiens alapú eljárás. A hasonlóság abban áll, hogy a paramétermódosítás adott iterációbeli iránya itt is a gradiens és az előző iterációban alkalmazott irány súlyozott összegeként határozható meg. A módosítás irányának meghatározása tehát itt is a (2.81) összefüggéshez formailag hasonló módon történik, azzal a különbséggel, hogy a súlyozó együtthatók meghatározása nem (2.84) alapján, hanem tapasztalati úton történik. Ennek megfelelően a momentum módszer egyes lépéseiben használt irányok nem is lesznek konjugált irányok. A momentum módszerrel részletesebben a 4. fejezetben foglakozunk.

Az eddigi eljárások mind a (2.49) összefüggésben definiált hibakritériumból, vagyis a négyzetes hiba várható értékéből indultak ki. A várhatóérték-képzés következtében a kapott eljárások közvetlen vagy közvetett formában igényelték az R autokorrelációs mátrix ismeretét. Neuronhálóknál általában a tanító mintapont-készleten kívül más ismeretünk nincs, így az autokorrelációs mátrix is csak a mintapontokból becsülhető. A becslés viszonylag nagy számításigénye, továbbá az R mátrixszal történő további műveletek számításigénye miatt hatékonyabb lenne egy olyan eljárás, ami R ismerete nélkül is alkalmazható. A Bernard Widrow által javasolt LMS (Least Mean Squares) algoritmus épp ezt teszi. Az LMS algoritmus és az eddigi gradiens alapú eljárásokközötti alapvető különbség az, hogy az LMS eljárás a (2.49)-ben definiált átlagos négyzetes hiba, mint kritériumfüggvény helyett a pillanatnyi hiba alapján dolgozik.

Az LMS eljárásnál a hibakritériumot, mint a pillanatnyi hiba négyzetét definiáljuk:

$C\left(w\text{(}k\text{)}\right)={\epsilon }^2\left(k\right)=\left(d\left(k\right)-x^T\left(k\right)w\left(k\right)\right){}^2$ . (2.85)

A pillanatnyi hiba alapján – gradiens módszert alkalmazva – a paramétermódosítás a kritériumfüggvény „pillanatnyi” gradiense alapján történhet.

$\widehat{\nabla }C\left(k\right)=\frac{\partial \epsilon {}^2\left(k\right)}{\partial w\left(k\right)}=-2\epsilon \left(k\right)x\left(k\right).$ (2.86)

Az LMS eljárás alapgondolata tehát az, hogy az átlagos négyzetes hiba helyett a pillanatnyi négyzetes hibából indulunk ki. Természetesen meg kell vizsgálnunk, hogy a várhatóérték-képzés elhagyásának milyen következményei lesznek.

Könnyen belátható, hogy (2.86) várható értéke megegyezik a gradiens vektor (2.54) összefüggésével [Wid85]. A pillanatnyi gradiens vektorral a "legmeredekebb lejtő" módszert alkalmazva a paraméter változtatás összefüggésére a következőt kapjuk:

$w\left(k+1\right)=w\left(k\right)-\mu \widehat{\nabla }C\left(k\right)=w\left(k\right)+2\mu \epsilon \left(k\right)x\left(k\right)$ . (2.87)

Az is megmutatható, hogy a paraméterváltoztatás eredményeképpen kapott megoldás várható értéke

$\begin{array}{l}E\left\{w\left(k+1\right)\right\}=E\left\{w\left(k\right)\right\}+2\mu \left(p-RE\left\{w\left(k\right)\right\}\right)\\ =\left(I-2\mu R\right)E\left\{w\left(k\right)\right\}+2\mu R{w}^{\ast }\end{array}$ (2.88)

amelyből, ha áttérünk az R sajátvektorai által meghatározott koordinátarendszerre, adódik, hogy

$E\left\{v\text{'}\left(k\right)\right\}=\left(I-2\mu \Lambda \right){}^{k}v\text{'}\left(0\right).$ (2.89)

Fentiekből látszik, hogy ha k minden határon túl nő, az LMS megoldás várható értéke megegyezik az optimális megoldással (ami a zérus vektor a sajátvektor koordináta-rendszerben, vagyis az eredeti koordinátarendszerben épp a $w^{\ast }$ ), ha (2.89) jobb oldala nullához konvergál. E feltétel pedig azonos a legmeredekebb lejtő módszer konvergenciájának (2.69)-ben megfogalmazott feltételével, vagyis a tanulási tényezőre vonatkozó konvergencia-feltétel az LMS algoritmusnál is

$0<\mu <\frac{1}{\lambda {}_{\text{max}}}$ . (2.90)

Az LMS eljárás legnagyobb előnye az eddig látott eljárásokkal szemben, hogy alkalmazásához a mintapontokon kívül másra nincs szükség, továbbá, hogy nagyon egyszerűen megvalósítható. Az eljárás egyszerűsége mellett azonban azt is látni kell, hogy a konvergencia feltételének megfelelő tanulási tényező megválasztásához itt is ismerni kell $\lambda {}_{\text{max}}$ -ot (vagy legalább annak (2.70) alapján nyerhető felső becslését), sőt a megfelelően gyors konvergenciához most is szükség van arra, hogy a $\lambda {}_{\text{max}}$ / $\lambda {}_{\text{min}}\cong$ 1 arány teljesüljön. Meg kell jegyezni, hogy a sajátértékek becslésének viszonylag nagy számításigénye miatt a gyakorlati alkalmazások többségében a tanulási tényezőt tapasztalati úton határozzák meg.

Rendkívüli egyszerűsége következtében az LMS eljárást igen elterjedten használják. Az a tény azonban, hogy minden lépésben a pillanatnyi gradiens irányában korrigálunk, az optimum közelében problémákat okozhat. E problémák jellegét érzékelhetjük, ha az ideális gradienstől való eltérés statisztikai jellemzőit vizsgáljuk. Az eltérést modellezzük egy $\left\{n\left(k\right)\right\}$ zaj folyamattal, amivel

$\widehat{\nabla }C\text{(}k\text{)}=\nabla C\text{(}k\text{)}+n\text{(}k\text{)}.$ (2.91)

Ha elegendően kicsi μ tanulási tényezővel dolgozunk, akkor elég jól megközelíthetjük az optimális $w^{\ast }$ értéket, ahol már $\nabla C\text{(}k\text{)}\cong 0$ , így

$n\left(k\right)\cong \widehat{\nabla }C\text{(}k\text{)}=-2\epsilon \left(k\right)x\left(k\right)$ . (2.92)

Az $\left\{n\left(k\right)\right\}$ zaj kovarianciája

$E\left\{n\left(k\right)n^T\left(k\right)\right\}=4E\left\{{\epsilon }^2\left(k\right)x\left(k\right)x^T\left(k\right)\right\}.$ (2.93)

A (2.51) összefüggés segítségével és felhasználva, hogy

$\epsilon \left(k\right)=\left(d\left(k\right)-x^T\left(k\right)w\left(k\right)\right)$ (2.94)

belátható, hogy az optimum közelében $E\left\{\epsilon \left(k\right)x\left(k\right)\right\}\cong 0$ , ezért (2.93) átírható a következő alakba:

$E\left\{n\left(k\right)n^T\left(k\right)\right\}=4E\left\{\epsilon {}^2\left(k\right)\right\}\text{E}\left\{x\left(k\right)x^T\left(k\right)\right\}\cong 4C_{\text{min}}R.$ (2.95)

Ha ennek a varianciának a hatását nyomon követjük az iterációk során, akkor a paraméter hiba-vektor (v(k)) kovarianciáját is becsülhetjük. A levezetés részletezése nélkül

$E\left\{v\left(k\right)v^T\left(k\right)\right\}\cong \mu C_{\text{min}}I,$ (2.96)

azaz a paraméter hiba kovarianciavektora egyenesen arányos a tanulási tényezővel, ami azt jelenti, hogy a varianciát úgy tudjuk alacsony szinten tartani, hogy az optimum közelében kis μ értékkel dolgozunk.

A paraméter hiba kovarianciája a 2.14 ábrán látható módon lehetetlenné teszi a minimum elérését. A paraboloid hibafelület tulajdonságai következtében ugyanis a bekövetkező hibának nem $C_{\text{min}}$ a várható értéke. A (2.57) összefüggésre alapozva és felhasználva a $C_{\text{min}}$ (2.52) összefüggését a $C_{\text{min}}$ -t meghaladó komponensre − az ún. többlet átlagos négyzetes hibára (excess mean-square error, EMSE) − a következő adódik:

$EMSE=E\left\{{v^{\prime }}^T\left(k\right)\Lambda v^{\prime }\left(k\right)\right\}\approx \mu C_{\text{min}}\text{tr}\left(R\right)$ , (2.97)

amelynek felhasználásával a hiba elérhető minimuma

${C^{\prime }}_{\text{min}}=C_{\text{min}}\left(1+\mu \text{tr}\left(R\right)\right)$ (2.98)

lesz. A pillanatnyi gradiens alkalmazásának következménye önmagában is kifejezhető:

$M=\frac{EMSE}{C_{\text{min}}}=\mu \text{tr}\left(R\right).$ (2.99)

M értékét, amelyet az irodalomban „beállítatlanságnak” (misadjustment) neveznek, tehát a többlet hibának és a Wiener-Hopf megoldáshoz tartozó hibának (a minimális átlagos négyzetes hibának) az arányaként definiáljuk.

A továbbiakban az LMS eljárás néhány további változatával foglalkozunk: előbb az LMS és a Newton algoritmus ötvözeteként származtatható algoritmust mutatjuk be röviden, majd egy olyan változat főbb jellemzőit foglaljuk össze, amelynek során egy kedvezőtlen konvergencia tulajdonságú eset a bemeneti mintatér transzformálásával kedvezőbb esetté alakítható.

Ez az algoritmus a Newton és az LMS algoritmus egyes elemeit együttesen magába építi. A Newton algoritmus paramétermódosító algoritmusát a (2.62) összefüggés adta meg és láttuk, hogy amennyiben mind a gradiens, mind $R^{-1}$ ismert, akkor egy lépésben is elérhető a w* megoldás. Ha $R^{-1}$ -et nem ismerjük, és az iterációnkénti pontos gradiens helyett csak a pillanatnyi gradiens áll rendelkezésünkre, akkor az LMS eljárás alkalmazható. Az LMS/Newton algoritmusnálfeltételezzük, hogy $R^{-1}$ ismert, de a pillanatnyi gradiens alapján számolunk. Így az iterációs összefüggés a (2.62) és a (2.86) összefüggések kombinálásából származtatható, vagyis a Newton algoritmusban a gradiens értékét a pillanatnyi gradienssel helyettesítjük:

$w\left(k+1\right)=w\left(k\right)+2\mu R^{-1}\epsilon \left(k\right)x\left(k\right)$ . (2.100)

A kapott összefüggés csak annyiban tér el az LMS algoritmustól, hogy a súlymódosító részben $R^{-1}$ is szerepel. Ha R azonos ${\lambda }_{av}$ sajátértékekkel rendelkező diagonálmátrix lenne, akkor ${\lambda }_{av}$ $R^{-1}$ =I-re adódna, vagyis, ha μ helyett ${\lambda }_{av}$ μ-t használnánk, lényegében visszakapnánk az LMS algoritmust, ahol μ-t a sajátérték reciprokánál kisebbre kell választanunk. Alkalmazzuk ezt a választást akkor is, ha $R^{-1}$ nem diagonálmátrix, sőt a sajátértékek sem egyformák. Ekkor legyen ${\lambda }_{av}$ az R mátrix sajátértékeinek az átlaga. Az így kapott algoritmus az LMS/Newton algoritmus:

$w\left(k+1\right)=w\left(k\right)+2\mu {\lambda }_{av}{R}^{-1}\epsilon \left(k\right)x\left(k\right)$ . (2.101)

Mindamellett, hogy az LMS/Newton algoritmust kedvező tulajdonságai miatt szokták "ideális adaptív algoritmusnak" is nevezni, a gyakorlati esetek többségében nem alkalmazható, mert $R^{-1}$ pontos ismeretét igényli. Létezik azonban olyan, a gyakorlatban is használható módosítása, amelyben rekurzívan becsüljük az $R$ , ill. $R^{-1}$ mátrixot. A (2.100) összefüggés módosításával

$w\left(k+1\right)=w\left(k\right)+2\mu R^{-1}\left(k+1\right)\epsilon \left(k\right)x\left(k\right).$ (2.102)

ahol ( $0<\eta \le \mathrm{1,}0<\nu \le 1$ feltételezésével)

$R\left(k+1\right)=\eta R\left(k\right)+\nu x\left(k\right)x^T\left(k\right),$ (2.103)

a korrelációs mátrix becsült értéke a (k+1)-edik időpillanatban, $R^{-1}\text{(}k+1\text{)}$ pedig az ún. mátrix inverziós lemma (ld. Függelék) felhasználásával az alábbi formában adható meg:

$R^{-1}\left(k+1\right)=\frac{1}{\eta }\left(R^{-1}\left(k\right)-\frac{R^{-1}\left(k\right)x\left(k\right)x^T\left(k\right)R^{-1}\left(k\right)}{\frac{\eta }{\nu }+x^T\left(k\right)R^{-1}\left(k\right)x\left(k\right)}\right)$ . (2.104)

A (2.103) összefüggésben szereplő konstansok kapcsolata gyakran $\eta =1-\nu$ . (Továbbá gyakori ajánlás η-ra a [0.9...0.99] közötti érték). A (2.102)-(2.104) összefüggésekkel jellemzett algoritmusnak léteznek további változatai, amelyek között érdemi különbség csak az R mátrix rekurzív becslésében van. Formai szempontból a (2.102)-(2.104) összefüggések az iteratív, gradiens alapú szélsőérték-kereső eljárások széles családját lefedik.

A legmeredekebb lejtő módszer tárgyalásánál láttuk, hogy a konvergencia-sebességet az R mátrix sajátértékeinek alakulása nagymértékben befolyásolja. A konvergencia-sebesség szempontjából a legkedvezőbb eset, ha az összes sajátérték azonos, és különösen kedvezőtlen, ha a legkisebb és a legnagyobb sajátérték nagymértékben különböző, vagyis ha ${\lambda }_{\text{max}}/{\lambda }_{\text{min}}>>1$ . Láttuk azt is, hogy a konvergencia-sebesség szempontjából azért kedvezőtlen a sajátértékek nagyfokú különbözősége, mert ilyenkor a hibafelület különböző részein a felület meredeksége jelentősen eltér, így a ${\lambda }_{\text{max}}$ alapján választott tanulási tényező – bár a konvergenciát biztosítja – az esetek jelentős részében a szükségesnél óvatosabb lépések megtételét eredményezi. Minél meredekebb szakaszán mozgunk a hibafelületnek, annál kisebb a megengedhető μ. Ha nem tudjuk, hogy a hibafelület mely szakaszán haladunk, akkor a μ megválasztása szempontjából a legrosszabb esetet kell feltételeznünk, vagyis azt, mintha a felület legmeredekebb részén mozognánk. Ezt fejezi ki a (2.69) összefüggéssel megadott felső korlát, amely szerint μ -t a legnagyobb sajátérték reciprokánál kisebbre kell választani.

A hibafelület alakját az R mátrix jellemzi, ami a bemeneti mintákból számítható. A konvergencia-sebesség szempontjából kedvezőbb helyzet tehát úgy teremthető, ha a bemeneteket módosítjuk. A módosításnak arra kell irányulnia, hogy a módosított bemenetek autokorrelációs mátrixa minél inkább az egységmátrix legyen. A bemenetek módosítása valamilyen alkalmas transzformációval lehetséges. A transzformáció az $\left\{x\left(k\right)\right\}$ bemeneti mintapontokból $\left\{X\left(k\right)\right\}$ transzformált mintapontokat állít elő. A transzformáció következtében természetesen az eredeti probléma megoldásában szerepet játszó w paramétervektor helyett az ugyancsak megfelelő módon transzformált w’ paramétervektor fog szerepelni [Nar83].

A szélsőérték-keresési probléma a transzformált bemenetekre is megfogalmazható, így az eddig bemutatott eljárások mindegyike alkalmazható transzformált esetben is.

Megfelelően választott transzformációt és azt követő normalizálást alkalmazva biztosítható a ${\lambda }_{\text{max}}/{\lambda }_{\text{min}}=1$ arány. Jelölje T az x(k) és X(k) közötti transzformációt leíró mátrixot:

X(k)=Tx(k). (2.105)

Ha a kiinduló bemenetek autokorrelációs mátrixa $R_{xx}=E\left\{x{x}^T\right\}$ , a transzformált bemenetek autokorrelációs mátrixát

$R_{XX}=E\left\{X{X}^T\right\}=E\left\{Tx{x}^T{T}^T\right\}=T{R}_{xx}{T}^T$ (2.106)

formában kapjuk (a kétféle autokorrelációs mátrix megkülönböztetése miatt alkalmazzuk a bemenet autokorrelációs mátrixára az $R_{xx}$ jelölést az eddigi R helyett és az $R_{XX}$ jelölést a transzformált bementek autokorrelációs mátrixára). Legyen T egy ortonormált transzformáció, vagyis teljesüljön a TT^T=I összefüggés. Ha még azt is előírjuk, hogy T=Q^T, ahol Q az $R_{xx}$ mátrix normált sajátvektoraiból képezett mátrix, akkor (2.55)-et figyelembevéve

$R_{XX}=Q^T{R}_{xx}Q=\Lambda$ , (2.107)

vagyis a transzformált bemenetek autokorrelációs mátrixa az $R_{xx}$ sajátértékeiből képezett diagonálmátrix. A diagonálmátrixból egységmátrix megfelelő normalizálással nyerhető. Ezért, ha a transzformáció mátrixát $T={\Lambda }^{-1/2}{Q}^T$ -ra választjuk, a transzformált bemenet autokorrelációs mátrixára

$R_{XX}=E\left\{X{X}^T\right\}=E\left\{Tx{x}^T{T}^T\right\}=T{R}_{xx}{T}^T={\Lambda }^{-1/2}{Q}^T{R}_{xx}Q{\Lambda }^{-1/2}=I$ (2.108)

adódik, vagyis minden sajátérték azonos és egységnyi lesz.

Az autokorrelációs mátrix sajátvektoraiból képezett Q mátrixszal elvégzett ún. főtengely transzformációt Karhunen-Loève transzformációnak (KL transzformáció, KLT) is nevezik. A kitűzött feladat szempontjából ez az optimális transzformáció, hiszen ha a főtengely transzformáció után a sajátértékek reciprokával (2.108) szerint még normalizálunk is, a kitűzött célt el is érjük, a sajátvektorok azonosak lesznek.

A konvergencia-sebesség növelésére a KL transzformációt, annak viszonylag jelentős számításigénye miatt, ritkán használják. Helyette könnyebben számítható ortogonális transzformációkat, például a diszkrét Fourier transzformációt vagy a diszkrét koszinusz transzformációt szokás alkalmazni. Ha a KL transzformációtól eltérő ortogonális transzformációt alkalmazzuk, meg kell vizsgálnunk, hogy ennek milyen hatása lesz a ${\lambda }_{\text{max}}/{\lambda }_{\text{min}}$ arány alakulására.

Írjuk fel ehhez komponensenként a transzformált tartománybeli LMS eljárás súlymódosítását:

${w^{\prime }}_i\left(k+1\right)={w^{\prime }}_i\left(k\right)+2{\mu }_i\epsilon \left(k\right)X_i\left(k\right),$ (2.109)

ahol a ${w^{\prime }}_i$ értékek a transzformált tartománybeli súlyokat jelölik. A súlymódosításnál most minden komponens esetén más-más tanulási tényezőt ( ${\mu }_i$ ) alkalmazhatunk. Ha a

${\mu }_i=\frac{\mu }{E\left\{X_i^2\left(k\right)\right\}},i=\mathrm{0,1,...,}N-1$ (2.110)

választással élünk, akkor ez a transzformált tartományban normálást is jelent.

A súlymódosítást vektorosan is felírhatjuk, ha bevezetjük a $\widehat{\Lambda }$ N × N-es diagonálmátrixot, melynek az (i,i)-dik eleme $E\left\{X_i^2\left(k\right)\right\}$ .

${w^{\prime }}_i\left(k+1\right)={w^{\prime }}_i\left(k\right)+2\mu {\widehat{\Lambda }}^{-1}\epsilon \left(k\right)X\left(k\right)$ . (2.111)

A transzformált tartományban a konvergencia sebessége ${\widehat{\Lambda }}^{-1}{R}_{XX}$ sajátértékeinek szóródásától vagy a legnagyobb és legkisebb sajátértékének arányától függ.

Ennek az aránynak a becsléséhez felhasználjuk, hogy egy A mátrix ${\lambda }_{\text{max}}/{\lambda }_{\text{min}}$ aránya felülről becsülhető:

$\frac{{\lambda }_{\text{max}}}{{\lambda }_{\text{min}}}\le \frac{\text{Tr}\left(A\right)}{\text{Det}\left(A\right)}$ , (2.112)

mivel az A mátrix maximális sajátértéke a mátrix nyomával majorálható, minimális sajátértéke pedig a mátrix determinánsával minorálható:

${\lambda }_{\text{max}}\le \text{Tr}\left(A\right)$ , (2.113)

illetve, ha N>2

${\lambda }_{\text{min}}\ge \text{Det}\left(A\right)$ . (2.114)

Ha feltételezzük, hogy $E\left(x^2\left(k\right)\right)=1$ , akkor

$\text{Tr}\left({\widehat{\Lambda }}^{-1}{R}_{XX}\right)=\text{Tr}\left(R_{xx}\right)=N$ , (2.115)

továbbá

$\text{Det}\left({\widehat{\Lambda }}^{-1}{R}_{XX}\right)=\text{Det}\left({\widehat{\Lambda }}^{-1}\right)\text{Det}\left(R_{XX}\right)=\text{Det}\left({\widehat{\Lambda }}^{-1}\right)\text{Det}\left(R_{xx}\right)$ . (2.116)

és

$\frac{\text{Tr}\left({\widehat{\Lambda }}^{-1}{R}_{XX}\right)}{\text{Det}\left({\widehat{\Lambda }}^{-1}{R}_{XX}\right)}=\text{Det}\left({\widehat{\Lambda }}^{}\right)\frac{\text{Tr}\left(R_{xx}\right)}{\text{Det}\left(R_{xx}\right)}$ . (2.117)

Mivel $\text{Tr}\left(\widehat{\Lambda }\right)=N$ , ezért feltételezhető, hogy $\text{Det(}\widehat{\Lambda }\text{)}$ legfeljebb 1 lehet, ezért

$\frac{\text{Tr}\left({\widehat{\Lambda }}^{-1}{R}_{XX}\right)}{\text{Det}\left({\widehat{\Lambda }}^{-1}{R}_{XX}\right)}\le \frac{\text{Tr}\left(R_{xx}\right)}{\text{Det}\left(R_{xx}\right)}$ , (2.118)

tehát megfelelően megválasztott transzformációnál – bár (2.118) erre feltétlen garancát nem ad – esély van arra, hogy a sajátérték-arány csökkenjen és így kedvezőbb feltételeket biztosítson a gyorsabb konvergenciához. A transzformált tartományra való áttérés hatását illusztrálja a 2.15 ábra.

Az ábra a hibafelület izokritérium görbéit mutatja a paramétertérben az eredeti bemenőjelre (a), a transzformált tartományban, normalizáció nélkül (b) és a transzformált tartományban normalizációval (c). Megjegyezzük, hogy az optimális transzformációt jelentő KL transzformáció esetén a kvadratikus hibafelület izokritérium görbéi koncentrikus körök lesznek.

A fentiek után még azt kell megnéznünk, hogy eredményként mit kapunk, ha a transzformált bemeneti térben alkalmazzuk a legmeredekebb lejtő módszert vagy az LMS algoritmust. Láttuk, hogy az eredeti bemeneti tartományban végzett LMS eljárás a (2.51) Wiener-Hopf egyenlet által megadott súlyvektorhoz tart

$w^{\ast }=R_{xx}^{-1}{p}_{xd}$ . (2.119)

ahol $p_{xd}$ a bemenet és a kívánt kimenet keresztkorrelációs vektora.

Könnyen belátható, hogy

${w^{\prime }}^{\ast }=R_{XX}^{-1}{p}_{Xd}=T{R}_{xx}^{-1}{p}_{xd}=T{w}^{\ast }$ , (2.120)

ahol $R_{XX}$ , mint (2.107)-ben megadtuk a transzformált bemenet autokorrelációs mátrixa, $p_{Xd}$ pedig a transzformált bemenet és a kívánt válasz keresztkorrelációs vektora. Tehát a transzformált bemenetekre alkalmazott LMS eljárás eredményeképpen kapott súlyvektor az eredeti súlyvektor transzformáltja lesz.

Az eddigiekben feltételeztük, hogy kvadratikus kritériumfelülettel van dolgunk, amit a legegyszerűbben az $y=w^{T}x$ lineáris kapcsolat és a négyzetes hibafüggvény biztosíthat. A súlytér felett azonban akkor is kvadratikus kritériumfelületet kapunk, ha a vizsgált leképezést $y=w^T\phi \text{(}x\text{)}$ alakban adhatjuk meg. Ekkor valójában először a bemeneti vektorok $\phi \text{(}x\text{)}$ általi (nemlineáris) transzformációja történik, a transzformált térről a kimeneti térre pedig már lineáris leképezést valósítunk meg. Az optimális paramétervektor meghatározása szempontjából azonban ez az eset nem különbözik az eddig tárgyalttól, hiszen a modellünk most is a paramétervektor lineáris függvénye. Egyes neuronhálók (pl. a radiális bázisfüggvényes – RBF – hálózatok) leképezése ez utóbbi általános formulával írható le, míg más hálóknál – pl. az MLP-knél – a nemlineáris leképezés már a paraméterekben is nemlineáris kapcsolattal történik. Ez utóbbi esetben – még ha négyzetes hibafüggvényt alkalmazunk is – a kritériumfüggvény nem lesz a paraméterek kvadratikus függvénye, sőt még az sem garantálható, hogy a kritériumfüggvény konvex függvény legyen. Ilyen esetekre az előzőekben bevezetett gradiens alapú eljárásokat és az eljárások eredményét külön kell értékelnünk.

A paramétereiben nemlineáris modellek egyik legfőbb jellemzője, hogy a hibafelület nem unimodális: a hibafelületen nem csak egy – globális – szélsőérték (maximum vagy minimum) található, hanem számos – lokális – szélsőérték is lehet. Vagyis a

$\nabla C\left(w\right)=\frac{\partial C\text{(}w\text{)}}{\partial w}=0$ (2.121)

feltételt nemcsak a globális szélsőértékhez tartozó w* paramétervektor, hanem egyéb paramétervektorok is biztosíthatják. Sőt, általános esetben az is előfordulhat, hogy egy egész paramétertartományban a felület gradiense zérus, ami azt jelenti, hogy a hibafelületen valamekkora kiterjedésű „lapos” terület is található.

A gradiens alapú eljárások ilyenkor is alkalmazhatók, az eredményeket azonban külön értékelni kell. A gradiens eljárásokkal kapott eredmény nem feltétlenül jelenti a legkisebb kritériumértékhez tartozó megoldást, így az eredmény minősége – a kritériumérték – alapján mérlegelni kell, hogy a kapott megoldásvektor a hibafelület globális minimumpontját adja meg, vagy csupán egy lokális minimumpontot. A megoldást még ezen utóbbi esetben is elfogadhatjuk, ha a kapott kritériumérték az adott alkalmazást tekintve elegendően kicsi. Ha nem, akkor újabb (lokális) minimumpontot kell keresni, ami szerencsés esetben egyben a globális minimumpont is lehet.

A nemkvadratikus hibafelületek további következménye, hogy olyan eljárásoknál, ahol a konvergenciához szükséges lépések száma kvadratikus hibafelület mellett meghatározható, most ez sem lesz érvényes. A konjugált gradiens eljárásnál például nem kvadratikus hibafelület mellett N iteráció után az algoritmus nem állítható le. Ilyenkor az az általánosan javasolt eljárás, hogy N iterációnként indítsuk újra az egész algoritmust egy új kezdeti gradiens meghatározásával. Meg kell azonban jegyeznünk, hogy valóságos esetekben az N-lépéses konvergencia még kvadratikus hibafelület mellett sem biztosított, hiszen numerikus problémák miatt a gradiens értékére sohasem fogunk nullát kapni. Ilyenkor az algoritmus leállítása sem történhet meg a gradiens értéke alapján. Helyette vagy egy adott iterációszám, vagy ha az egymást követő iterációkhoz tartozó kritériumértékek különbsége megfelelően kicsi jelentheti a leállás feltételét. A tapasztalat szerint azonban a konjugált gradiens módszer még nem ideális esetben (numerikus problémák, vagy nem "teljesen" négyzetes hibafelület) és az optimumtól távol is kedvezőbb konvergenciát mutat, mint a direkt gradiens módszerek.

Az előzőekben láttuk, hogy egyes eljárások, mint a Newton, a Newton/LMS, de a konjugált gradiens módszer is a hibafelületről az R mátrix figyelembevétele által a gradiensen túl további információt is felhasználnak. Kvadratikus hibafelület esetén R a hibafelület második parciális deriváltjaiból képezett H ún. Hesse mátrixszal egyezik meg, tehát R valójában a hibafelület görbületéről szolgál információval. Kvadratikus hibafelületet – mint láttuk – paramétereiben lineáris modell és négyzetes hibafüggvénymellett kapunk. A hibafelületre vonatkozó járulékos információ a konvergenciasebességet jelentősen megnöveli a csupán a gradiens felhasználásával dolgozó LMS eljáráshoz képest. A Newton módszerrel pl. négyzetes hibafelület mellett akár egy lépésben is eljuthatunk a hibafelület minimumpontjába.

A Newton illetve a Newton/LMS eljárások előnyös konvergencia tulajdonságai ellenére számos nehézséget is rejtenek. Egyrészt alkalmazásukhoz kell, hogy R pozitív definit legyen, másrészt R^-1 számításigényes. További gondot jelenthet, ha a hibafelület nem négyzetes. Az alábbiakban bemutatott Levenberg-Marquardt eljárás ezekre a nehézségekre igyekszik megoldást találni.

A nemkvadratikus kritériumfelület kezelhető olyan módon hogy a C(w) kritériumfüggvényt Taylor-sorának első néhány tagjával közelítjük. Ha az első és másodfokú tagokat vesszük figyelembe, akkor egy nemkvadratikus kritériumfelület kvadratikus közelítésével dolgozunk.

$C\left(w\right)\cong C\left(w\left(k\right)\right)+\nabla C{\left(w\left(k\right)\right)}^T\left(w-w\left(k\right)\right)+\frac{1}{2}{\left(w-w\left(k\right)\right)}^{T}H\left(w-w\left(k\right)\right)$ (2.122)

ahol

$H=\frac{\partial \nabla C\left(w\left(k\right)\right)}{\partial w}$ (2.123)

a kritériumfelület második parciális deriváltjaiból felépített Hesse-féle mátrix. A (2.122) összefüggésnek a (2.53) összefüggéssel való összevetéséből látszik, hogy a H mátrix az R mátrixnak feleltethető meg.

Ha a (2.122) összefüggés minimumát w szerinti deriválással keressük, akkor a közelítő négyzetes hibafelület minimumpontját egy lépésben is elérhetjük. Ehhez a

$\nabla C\left(w\left(k+1\right)\right)=0=\nabla C\left(w\left(k\right)\right)+H\left(w\left(k\right)\right)\left(w\left(k+1\right)-w\left(k\right)\right)$ (2.124)

feltételt kell kielégítenünk, amelyből a Newton módszert (lásd (2.61)) kapjuk:

$w\left(k+1\right)=w\left(k\right)-H{\left(w\text{(}k\text{)}\right)}^{-1}\nabla C\left(w\text{(}k\text{)}\right).$ (2.125)

Az 1/2-es szorzó a korrekciós tagból most hiányzik, mert a (2.122) összefüggés jobboldalának harmadik tagjában a (2.61) összefüggéssel ellentétben $H^{-1}$ szerepel. Az így kapott eljárás nemkvadratikus hibafelület esetén nem feltétlenül jobb, mint a gradiens alapú eljárás. Ezért hatékonyabb lehet, ha a Newton eljárás és az egyszerű gradiens alapú eljárás „keverékét” alkalmazzuk. Ezt javasolja a Newton módszer Levenberg-Marquardt félemódosítása:

$w\left(k+1\right)=w\left(k\right)-{\left(H\left(w\text{(}k\text{)}\right)+\lambda \left(k\right)I\right)}^{-1}\nabla C\left(w\text{(}k\text{)}\right).$ (2.126)

Látható, hogy a (2.126) összefüggés valójában a legmeredekebb lejtő módszer és a Newton eljárás kombinációja, ahol a kétféle eljárás arányát a λ(k) lépésfüggő együttható szabja meg. Ha λ(k) nagy, a (2.126) alapján történő súlymódosítás a legmeredekebb lejtő módszert, míg ha λ(k) kicsi, a Newton eljárást közelíti. A λ(k)I beépítése az eljárásba regularizációként is értelmezhető, ami a mátrix invertálhatóságát akkor is biztosítja, ha H közel szinguláris.

A neurális hálózatok tanításánál hatékonynak bizonyult a H mátrix egy közelítése, amely a következő gondolatmeneten alapszik. Tételezzük fel, hogy a kritériumfüggvény önmagában négyzetes, de a paraméterfüggés nemlineáris, tehát

$C\left(w\right)=\frac{1}{2}E\left\{{\left(d-y\left(w\right)\right)}^2\right\}=\frac{1}{2}E\left\{{\epsilon }^{\text{2}}\right\}$ . (2.127)

Ekkor a gradiens vektor

$\nabla C\left(w\right)=-E\left\{\epsilon \nabla y\left(w\right)\right\}$ (2.128)

alakban írható, illetve ennek minden sorát deriválva minden paraméter szerint megkapjuk a H mátrixot:

$H=E\left\{\nabla y\left(w\right)\nabla y{\left(w\right)}^T-\epsilon \left[\frac{{\partial }^{2}y\left(w\right)}{\partial w_i\partial w_j}\right]\right\}$ , (2.129)

ahol a szögletes zárójelben szereplő kifejezés y(w) másodrendű parciális deriváltjainak mátrixát szimbolizálja. Mivel a (2.129) kifejezés második tagja ε-nal szorzódik, a H mátrix az optimumhoz közeledve egyre inkább az első tagtól függ, hiszen akkor általában mind ε, mind y(w) görbülete egyre kisebb, ezért felvethető a

$H\cong E\left\{\nabla y\left(w\right)\nabla y{\left(w\right)}^T\right\}$ (2.130)

közelítés. Ha H (2.130) szerinti közelítését (2.126)-ban alkalmazzuk, akkor számítási hatékonyság szempontjából kedvezőbb megoldást nyerünk, hiszen a Hesse mátrix (2.130) szerinti becslése jóval kisebb számításigényű, mintha a valódi második deriváltak alapján számítanánk. Meg kell jegyezni, hogy sok sikeres alkalmazás fűződik egy olyan megoldáshoz, ahol az I egységmátrix helyett egy olyan Ω diagonálmátrixot alkalmazunk, melynek elemei megegyeznek H (2.130) szerinti becslésének diagonális elemeivel. Az így kapott eljárást az irodalomban Levenberg-Marquardt módszernek nevezik [Mor77].

Neuronhálók, illetve egyes tanuló rendszerek konstrukciójánál az optimális paraméterkészlet meghatározása sokszor feltételes szélsőérték-keresési eljárásra vezet. Ilyen esetekkel találkozunk például, ha a leképezés hibájára vonatkozó kritérium vagy kockázat minimalizálását bizonyos mellékfeltételek teljesülése mellett kell elvégeznünk. Mint az egyes hálóarchitektúráknál látni fogjuk, ilyen mellékfeltétel lehet a háló leképezésére megfogalmazott valamilyen simasági feltétel, vagy a paraméterekre vonatkozó megkötés: a paraméterek értékei a lehető legkisebbek legyenek, vagy a paramétervektor komponenseinek összege legyen egy adott érték, tipikusan 1. A mellékfeltételek megfogalmazásának egy lehetséges módja a 2.1 részben bemutatott regularizáció is.

A feltételes szélsőérték problémák gyakran a következő formában fogalmazhatók meg: keressük egy skalár értékű konvex C(w) kritériumfüggvény extrémumához tartozó w*-ot azzal a feltétellel, hogy egyidejűleg a g(w)=0 formában adott mellékfeltétel is teljesüljön.

Az ilyen típusú feltételes szélsőérték-keresési problémák hatékony megoldására szolgál a Lagrange multiplikátoros módszer. A Lagrange multiplikátoros eljárásnál meg kell fogalmazni egy módosított kritériumfüggvényt, amely mind az eredeti kritériumfüggvényt, mind a mellékfeltételt magában foglalja:

$L\text{(}w,\lambda \text{)}=C\text{(}w\text{)}+\lambda g\text{(}w\text{)}$ (2.131)

A feltételes szélsőérték a $\nabla L\text{(}w,\lambda \text{)}=0$ megoldásából adódik.

Amennyiben nem egyenlőség, hanem egyenlőtlenség formájában vannak mellékfeltételeink, vagy az egyenlőség típusú feltételek mellett egyenlőtlenség típusú mellékfeltételeink is vannak, a Karush-Kuhn-Tucker (KKT) elmélet alkalmazásával kaphatunk megoldást, amely elmélet a Lagrange módszer kiterjesztésének tekinthető.

Mind a Lagrange, mind a KKT elmélet rövid összefoglalását a Függelékben adjuk meg.

Véletlen kereső módszereknél a paraméterértékek véletlenszerű megváltoztatásával próbálkozunk. Ha egy próbálkozás eredményeképpen kapott paraméterhez tartozó kritériumérték az előző pontbelinél kisebb, az új pontot tekintjük a következő lépés kiinduló pontjának, ellenkező esetben a régi paraméterértéket tartjuk meg és a keresést tovább folytatjuk. A véletlen keresési eljárásoknak − a hatékonyság növelése érdekében − különböző változatait dolgozták ki. Az alábbiakban a véletlen keresés alapeljárásának és egy módosított változatának fő lépéseit foglaljuk össze.

Mátyás véletlen optimalizálási módszere [Mát65] 1 valószínűséggel biztosítja a globális minimumhoz való konvergenciát, abban az esetben, ha a keresési tér kompakt (korlátos és zárt). Jelölje W a kompakt keresési teret, w(k) pedig a keresési tér egy pontját.

A módszer a következő lépésekből áll:

A konvergencia gyorsítható, ha a 3. lépést az alábbival helyettesítjük:

$m\left(k+1\right)=\mathrm{0,2}m\left(k\right)+\mathrm{0,4}\xi \left(k\right)$ legyen,

ha $C\left[w\left(k\right)+\xi \left(k\right)\right]\ge C\left[w\left(k\right)\right]$ és $C\left[w\left(k\right)-\xi \left(k\right)\right]$ < $C\left[w\left(k\right)\right]$ , akkor:

$w\left(k+1\right)=w\left(k\right)-\xi \left(k\right)$ és $m\left(k+1\right)=m\left(k\right)-\mathrm{0,4}\xi \left(k\right)$ legyen,

egyébként pedig

$w\left(k+1\right)=w\left(k\right)\text{ és }m\left(k+1\right)=\mathrm{0,5}m\left(k\right)$ , ahol m(k) a Gauss valószínűségi vektorváltozó várható értéke a k-adik lépésben.

A módosított eljárás tehát változó várható értékű Gauss véletlen vektort használ. Kezdetben a várható érték itt is nulla: m(0)=0. Bizonyítható [Sol81], hogy a módosított eljárás is 1 valószínűséggel konvergens és a globális minimumhoz konvergál, ha a keresési tér kompakt.

Neurális hálózatokra való alkalmazásnál általában nem biztosítható, hogy a keresési tér kompakt legyen. A súlyértékek nem szükségszerűen korlátos tartományban vehetnek fel csak értékeket. Ez azt jelenti, hogy a véletlen keresési módszerek nem feltétlenül konvergálnak a globális minimumhoz. Abban az esetben azonban, ha a keresési teret korlátozzuk, akkor e tartományon belül a globális minimumhoz való 1 valószínűségű konvergencia igaz. E nehézség ellenére, alkalmazástól függően a véletlen keresési módszerekkel más eljárásoknál gyorsabb konvergencia is elérhető.

A véletlen keresési módszerek sok esetben sikerrel alkalmazhatók egyéb szélsőérték-kereső eljárásokkal, pl. gradiens alapú módszerekkel kombinálva. Ilyenkor a gradiens módszert alkalmazzuk mindaddig, amíg a kritériumfüggvény értékének csökkenése egy adott korlátnál kisebb nem lesz, majd áttérünk a véletlen keresésre. A kritériumcsökkenés lelassulása vagy megállása annak jele, hogy a hibafelület meredeksége nagyon lecsökkent, esetleg lokális minimumhelyet értünk el. A minimumhelyben való bennragadás elkerülésére alkalmazzuk most a véletlen keresést, mindaddig, amíg a hibafelületen meredekebb részre nem érünk ismét, ahol célszerűen visszatérünk a gradiens alapú módszerre.

A genetikus algoritmusok [Hol75], [Gol89a] az evolúció számítógépes modelljei, a természetes szelekciót utánozzák. Az evolúció a természetes kiválasztódással központi szerepet tölt be a biológiában. A mesterséges intelligencia témakörében, a mesterséges intelligens rendszerek létrehozásánál az utóbbi időben egyre gyakrabban alkalmazzák a természetes kiválasztódás modelljét.

A genetikus algoritmusok sztochasztikus keresési algoritmusoknak tekinthetők, ahol a paramétertér feltérképezése és az iterációnként egyre jobb megoldások előállítása az eddigi eljárásoktól gyökeresen eltérő módon történik. Az eddigi szélsőérték-keresési eljárások − akár a gradiens módszerek, akár a véletlen keresés − a paramétertérben egy pontot mozgattak és a pont minden egyes állapotában − ami egy lehetséges megoldásnak felelt meg − kiértékelték a kritériumfüggvényt, majd ennek eredményétől függően folytatták az eljárást. Az alapvető eltérés e két módszer között csak az egymást követő pontok meghatározásában volt.

A genetikus algoritmusok ezzel szemben nem különálló pontokban vizsgálják a kritériumfelületet, hanem egyszerre több ponton értékelik ki, tehát egy lépésben a megoldások egész halmazával dolgoznak. Genetikus algoritmusoknál a megoldások egy adott lépésben érvényes halmazát populációnak nevezik. A populáció elemei különböző sikerrel oldják meg a feladatot, ami szélsőérték-keresésnél azt jelenti, hogy a populáció elemei a kritériumfüggvény különböző pontjait határozzák meg. E pontok között lesznek olyanok, amelyek a globális minimumhoz közelebb esnek − ahol a kritériumfüggvény értéke kisebb −, és lesznek a megoldástól távolabb eső pontok is. A populáció elemei tehát a feladat szempontjából eltérő tulajdonságúak, képességűek. A genetikus algoritmusoktól azt várjuk, hogy a természetes szelekció mintájára egy látszólag spontán fejlődés során egy adott populációból olyan újabb populációt, ill. olyan újabb és újabb populációkat hozzanak létre, amelyekben a jó megoldáshoz közeli megoldások egyre nagyobb számban lesznek megtalálhatók, és amelyekben a gyenge eredményt szolgáltató elemek egyre ritkulnak. Ez azt jelenti, hogy valójában a genetikus algoritmusok is egy hálót helyeznek a kritériumfelületre, azonban e háló nem rögzített felbontású, hanem lépésenként változik. Ezen túl a kritériumfüggvény kiértékelése a háló rácspontjaiban nem egyenként történik, hanem minden egyes lépésben a lépéshez tartozó háló összes rácspontjában. A kiértékelés eredményeképpen egy új háló jön létre, amelynek lehetnek közös rácspontjai az előző hálóval, de alapvető jellemzője, hogy miközben egyes régi rácspontok eltűnnek, új rácspontokkal is fog rendelkezni, és ezen rácspontok a kritériumfüggvény kedvezőbb tartományain sűrűsödnek: a rácspontok sűrűsége arányos lesz az adott tartomány jóságával. Bizonyos szempontból tehát a genetikus algoritmus a véletlen kereséssel rokonítható, hiszen itt is a teljes keresési tér valamilyen feltérképezéséről van szó. A genetikus algoritmus azonban − szemben a véletlen kereséssel − nem vakon keres. A keresés az egymást követő lépésekben egyre inkább a kritériumfüggvény minimumhelyei környezetére koncentrálódik.

Az egymást követő populációkat − biológiai mintára − generációknak nevezzük, tehát az algoritmus az egymást követő generációk során egyre jobb megoldás-halmazokat állít elő. E folyamat követhető a 2.16 ábrán. Az egydimenziós paramétertérben az egyre későbbi generációk során a populáció jobb megoldást adó elemei a kritériumfüggvény minimumhelyei közelében sűrűsödnek.

Egy populáció elemeinek tulajdonságait valamilyen módon reprezentálni kell. E reprezentáció – megint csak biológiai szóhasználattal élve – kromoszómákkal történik, amely jelen esetben olyan bitfüzéreket – stringeket – jelent, amelyekben minden egyes bit egy tulajdonságot reprezentál. Ha a string egy adott pozícióján 1 található, az adott elem a kérdéses tulajdonsággal rendelkezik, míg a 0 érték e tulajdonság hiányát jelenti. A megoldások egy populációja tehát a kromoszómák, bináris stringek egy populációját jelenti, és az algoritmus lényegében az egymást követő string-populációk fejlődése során jut el a megfelelő megoldásig. A megoldási tér (paraméter tér) minden egyes pontjának egy kromoszóma felel meg.

Az eddigiek alapján összefoglalhatjuk a genetikus algoritmusok fő jellemzőit:

Hogy az egymást követő populációk egyre jobb tulajdonságú stringeket tartalmazzanak, a stringek valamilyen kiértékelésére van szükség. Minden stringhez hozzárendelhetünk egy "jóság" (fitness) értéket, ami lényegében annak mértéke, hogy egy adott string által képviselt megoldás milyen kritériumfüggvény-értéket eredményez. Minél kisebb a kritériumfüggvény-érték, annál jobb a megoldás, tehát a fitness érték annál nagyobb.

A genetikus algoritmus a kromoszómák generációival dolgozik. A megfelelő működést az jelenti, ha az újabb generációk átlagos jósága (fitness-értéke) egyre nagyobb, de legalábbis nem csökken. Tehát az egyes lépések során a jó kromoszómák által hordozott információt kell tovább örökíteni a következő generációra.

A generációk közötti átmenet valószínűségi operátorokkal történik. A legegyszerűbb genetikus algoritmus a következő alap-operátorokkal rendelkezik:

A reprodukció (reproduction) az a folyamat, amikor egy string a következő generáció részeként is megjelenik, vagyis egy megoldás a következő generáció megoldás-halmazának is része marad. Egy adott stringnél a reprodukció, vagyis a túlélés bekövetkezésének valószínűsége a string jóságával van kapcsolatban. Minél nagyobb egy kromoszóma jósága az egy populációba tartozó kromoszómák átlagos jóságához viszonyítva, annál nagyobb számban fog reprodukálódni a kromoszóma, vagyis annál nagyobb számban fog előfordulni a következő generációban. A reprodukciónak ezt a módját arányos kiválasztási mechanizmusnak nevezzük.

A keresztezésnél (crossover) egy generáció két kromoszómája – a szülő kromoszómák – a tulajdonságaik keresztezése révén hoznak létre új tulajdonságú utódokat. Ilyenkor a szülők bitmintái kereszteződnek új bitkombinációkat hozva létre. Az utódok bitkombinációi részben az egyik szülő, részben a másik szülő bitkombinációit fogják tartalmazni. A keresztezés operátor legegyszerűbb formája az ún. egypontos keresztezés, amikor az adott generáció bitfüzérei páronként úgy hoznak létre utódokat, hogy egy bitfüzér-pár mindkét tagja egy véletlenszerűen kiválasztott pontnál szétválik, és az így létrejövő részstringek keresztbe kapcsolódva hoznak létre új stringeket. A folyamatot a 2.17 ábrán követhetjük. Megjegyezzük, hogy a szülő kromoszómákból az utód kromoszómák létrehozásánál a keresztezés a legegyszerűbb operáció. Bár a természetben nem található erre minta, genetikus algoritmusoknál a szülő kromoszómák komplex összekeverése is lehetséges. Ezen komplex operációkat rekombinációnak hívják, amelyek egy speciális, egyszerű esete a keresztezés [Rad93].

A mutáció (mutation) során egy string egy bitje véletlenszerűen, általában igen kis valószínűséggel megváltozik. A mutáció következtében teljesen új bitkombinációk jöhetnek létre, így megakadályozhatják a további, fejlődésre képtelen, egyöntetű populáció létrejöttét. Az új bitkombinációk a megoldási tér olyan területeit is feltérképezhetik, amelyekre az eddigi populációk nem terjedtek ki.

Fentiek alapján az algoritmus a következő lépésekből áll:

A három operátor hatását az alábbi egyszerű példán követhetjük.

2.4 Példa

Tekintsünk egy 4 kromoszómából álló populációt, melyben az egyes kromoszómák ( $k_i$ ) 10 bitesek. Legyen az egyes bitstringek jósága ( $f_i,i=\mathrm{1,}\mathrm{2,}\mathrm{3,}4$ ) rendre 0,9; 0,6; 0,6 és 0,3. Ekkor a populáció átlagos jósága $\overline{f}$ = 0,6 az egyes kromoszómák jóságainak az átlagos jósághoz viszonyított értékei ( $f_i/\overline{f}$ ) pedig rendre 1,5; 1,0; 1,0 és 0,5-re adódnak. Ha a kiválasztás ezen értékekkel arányos valószínűség szerint történik, akkor az egyes stringek reprodukciójának valószínűségei ( $p_i=\left(1/n\right)\left(f_i/\overline{f}\right)$ , n=4) 0,375; 0,25; 0,25 és 0,125.

A szelekció – arányos kiválasztási mechanizmust alkalmazva – ezek után a következőképpen zajlik. Határozzuk meg az egyes kromoszómák relatív jóságait – a $p_i$ értékeket – a populációt jellemző összeg-jósághoz viszonyítva. Osszuk fel a [0,1] intervallumot ezen relatív jóságoknak megfelelő intervallumokra. Generáljunk a [0,1] intervallumban egyenletes eloszlású véletlen számokat és attól függően reprodukáljuk az egyes kromoszómákat, hogy a véletlen szám a [0,1] intervallum mely részintervallumába esik.

Mivel a részintervallum-hosszak arányosak az egyes kromoszómák relatív jóságával, a reprodukció valószínűsége is arányos lesz ezekkel az értékekkel, vagyis az arányos kiválasztási mechanizmust valósítottuk meg és az egyes kromoszómák $p_i$ -vel arányos számban reprodukálódnak. A szelekciót követően a kromoszómák átlagos jósága növekedett: $\overline{f}$ =0,75.

A kromoszómák alakulását az egyes operátorok alkalmazása után a 2.1 táblázat mutatja. Ugyancsak a táblázatból látható a keresztezés (egypontos: az ötödik és a hatodik bit között) és a mutáció hatása. A táblázatból az is látható, hogy a keresztezés hatására az eddigieknél jobb képességű egyed (P3: f₁=1) keletkezhet, de az is, hogy a keresztezés a populáció átlagos jóságának stagnálását, a mutáció pedig az átlagos jóság stagnálását ill. csökkenését is eredményezheti ( $\overline{f}$ =0,75 ill. $\overline{f}$ =0,6).

A genetikus algoritmusok valódi teljesítőképessége jobban megérthető, ha bevezetjük a szkéma vagy hasonló mintázat fogalmát [Hol75]. Ha két vagy több string hasonló képességekkel rendelkezik, akkor a stringek egy vagy több pozíciójában egyezés található. A stringek közötti lényeges hasonlóságok kezelésére vezethető be a hasonló mintázat vagy szkéma elnevezés, amely egy olyan részstringet jelöl, amelyben a 0 és 1 értékű biteken kívül don't care, közömbös bitek is lehetnek. Pl. a 8 hosszúságú 1*0*01** szkéma mindazon stringeket képviselni fogja, amelyekben 1 található az első és a hatodik pozícióban, 0 a harmadikban és az ötödikben. A szkémák hossza megegyezhet a string hosszával, de legtöbbször annál kisebb. A szkéma fogalmának bevezetésével lehetőség nyílik annak bemutatására, hogy generációról generációra a jó tulajdonságú stringek száma – vagyis azon stringek száma, amelyekben jó tulajdonságú szkéma található – az egyes populációkban hogyan növekszik.

Vizsgáljuk meg, hogyan hatnak az egyes operátorok egy S szkéma előfordulási gyakoriságára a generációk függvényében. Ehhez vezessük be a következő jelöléseket: jelölje m(S,k) azon stringek számát, amelyek a k-adik generációban tartalmazzák az S szkémát, o(S) a szkéma rendjét (order), ami a szkémán belüli rögzített értékű bitek száma és $\delta \left(S\right)$ a szkéma meghatározó hosszát (definitive length), ami az első és utolsó rögzített bit pozíciói közötti távolság. Pl. az előző szkéma (1*0*01**) estében o(S)=4, δ(S) =5. A reprodukció során egy kromoszóma annál nagyobb valószínűséggel kerül kiválasztásra, minél nagyobb az adott kromoszóma jósága az egész populáció kromoszómáinak átlagos jóságához viszonyítva.

Ha $f_i$ az i-edik kromoszóma jóságát jelöli, a reprodukció során egy stringet (kromoszómát)

$$ $p_i=\frac{f_i}{{\displaystyle \sum _j{f}_j}}$ (2.136)

valószínűséggel választunk ki. Ekkora valószínűséggel lesz tehát az i-edik kromoszóma eleme a következő generációnak. Ha kiválasztunk n kromoszómát a régi populációból, akkor az n elemű új populációban egy S szkémát tartalmazó stringek számát a következő összefüggés adja meg:

$m\left(S,k+1\right)=m\left(S,k\right)n\frac{f\left(S\right)}{{\displaystyle \sum _j{f}_j}}=m\left(S,k\right)\frac{f\left(S\right)}{\overline{f}}$ (2.137)

mivel $\overline{f}=\frac{1}{n}{\displaystyle \sum _j{f}_j}$ az n elemű új populáció átlagos jósága. Itt f(S) az S szkéma

jóságát, vagyis azon stringek átlagos jóságát jelöli, melyekben az S szkéma megtalálható. Ez azt jelenti, hogy azok a szkémák, amelyek jósága nagyobb, mint a populáció átlagos jósága, az új generáció kromoszómáiban növekvő számban lesznek megtalálhatók, míg az átlagosnál gyengébb képességű szkémák jelenléte az új generációban csökken. Ha f(S)=(1+c) $\overline{f}$ , ahol c konstans, akkor k generációt követően az S szkémát tartalmazó kromoszómák száma:

m(S, k)=m(S,0) ${\left(1+c\right)}^k$ , (2.138)

vagyis a szkémák túlélése a generációk függvényében exponenciálisan nő (c>0) vagy csökken (c<0).

A szkémák előfordulási gyakoriságát befolyásolja a további két operátor is. Mind a kereszteződés, mind a mutáció következtében egy szkémát alkotó bitstring megváltozhat, a szkéma széteshet, aminek következtében egyes kromoszómákból az addig meglévő szkéma eltűnik. Egy szkéma túléli a kereszteződést, ha a kereszteződési pont kívül esik a szkéma bitcsoportján. Ha l a kromoszóma hossza és $p_c$ a keresztezés bekövetkezésének valószínűsége, az egypontos keresztezésnél a túlélési valószínűség :

$p_{sc}\ge 1-p_c\frac{\delta \left(S\right)}{l-1}$ . (2.139)

A mutáció is elronthat egy szkémát azáltal, hogy a szkéma egy rögzített bitjét megváltoztatja. Ha $p_m$ egy bit véletlen megváltozásának valószínűsége, akkor a túlélési valószínűség:

$p_{sm}={\left(1-p_m\right)}^{o\left(S\right)}\approx 1-o\left(S\right)p_m$ (2.140)

mivel $p_m$ <<1.

Feltételezve, hogy a keresztezés és a mutáció azon hatása, hogy egy szkémát elrontanak egymástól független, valamint elhanyagolva a $p_m{p}_c$ –t tartalmazó tagot, a három alap-operátor hatását figyelembe véve egy adott S szkéma előfordulása a következő generációban az alábbi összefüggéssel adható meg:

$m\left(S,k+1\right)\ge m\left(S,k\right)\frac{f\left(S\right)}{\overline{f}}\left[1-p_c\frac{\delta \left(S\right)}{l-1}-o\left(S\right)p_m\right]$ . (2.141)

A (2.141) összefüggést, ami Holland szkéma elméletének eredménye, a genetikus algoritmus alaptételének nevezzük.

A mutáció, illetve a keresztezés hatására azon szkémák esnek szét nagyobb valószínűséggel, amelyek rendje, illetve meghatározó hosszúsága nagyobb. Ha egy szkémát tartalmazó kromoszóma jósága az átlag jóságnál nagyobb és a szkéma rövid, továbbá, ha szkéma rendje is kicsi, akkor a szkémát tartalmazó kromoszómák száma a generációk függvényében közel exponenciálisan nő.

A reprodukció és a keresztezés operátorok hatása az evolúció során a 2.18 ábrán követhető. Az ábrán eltérő árnyalatú bitcsoportok jelölik a szkémákat. Az egyes bitsorozatok mellé írt értékek a stringek jóságát jelentik. A legkevésbé megfelelő stringek – amelyek jósága a legkisebb – nem kerülnek át a következő generációba; az ábrán X jelöli ezen kromoszómákat. Az ábra azt is illusztrálja, hogy egy stringen belül több szkéma is előfordulhat. Ha több, kedvező tulajdonságokat reprezentáló szkéma a keresztezés hatására egy utód stringben együtt jelenik meg, lehetséges, hogy a keresztezés hatására a szülő stringeknél nagyobb jóságú utód jön létre.

A genetikus algoritmusok alkalmazása különösen ott célszerű, ahol a keresési tér nagy, komplex és kevéssé ismert, illetve, ahol a kritériumfüggvény jellege olyan, hogy más, pl. gradiens alapú eljárások nem alkalmazhatók. A keresési tér mérete ugyanakkor befolyásolja a genetikus algoritmus számításigényét, hiszen nyilvánvaló, hogy nagyobb keresési tér több elemű populációt igényel.

Tipikus feladatoknál a populáció elemszáma néhányszor tíztől több ezerig is terjedhet. A viszonylag nagy elemszám számos területen gátja a genetikus algoritmusok alkalmazásának. A populáció elemszámának meghatározásán túl fontos kérdés az algoritmus egyéb paramétereinek megválasztása. Ilyen további paraméterek pl. a keresztezés típusa (egypontos vagy többpontos keresztezés) és valószínűsége $p_c$ , a mutáció valószínűsége $p_m$ , stb. A paraméterek megválasztására általános eredmények jelenleg nincsenek. A paraméterválasztás alkalmazástól függően, tapasztalati úton történik. Ugyancsak alkalmazástól függ, hogy hogyan képezzük le egy adott problémánál a feladat paramétereit számfüzérekké, kromoszómákká.

Fontos kérdés még az algoritmus leállítása. A leállítás megtörténhet adott számú generáció után, illetve, ha az eredmény már elég jó, vagyis az utolsó generáció kromoszómáinak átlagos jósága egy adott értéknél nagyobb. Az algoritmust azonban le kell állítani akkor is, ha egy populáció stringjei nagymértékű hasonlóságot, homogenitást mutatnak. Ebben az esetben – függetlenül a populáció átlagos jóságától – a kromoszómák jósága a további generációk során már nem fog javulni, az algoritmus megreked.

A túl korai konvergenciát eredményező egyöntetű populáció kialakulásának esélyét a reprodukció előbb említett módja – vagyis amikor egy kromoszóma továbbélése annak jóságával arányos – növeli. Ennek megakadályozására számos módosított eljárást dolgoztak ki, melyek közös jellemzője, hogy nagyobb esélyt adnak a rossz stringek továbbélésének. E módszerek részletes ismertetésére itt nincs módunk, az érdeklődő olvasó a részleteket az irodalomban pl. [Gre87], [Gal89], [Mon89] megtalálja.

Feladatok

2.1 Mutassa meg, hogy az N-dimenziós térben a lineáris szeparáló függvények VC-dimenziója h=N+1.

2.2 Adjon szemléletes példát, amely azt mutatja, hogy az $y=\text{sin(}ax\text{)}$ , a>0 függvények VC-dimenziója végtelen.

2.3 Tekintsük a négyszögletes indikátorfüggvények osztályát, ahol egy indikátorfüggvényt a következőképpen definiálunk:

$f\text{(}x,c,d\text{)}=1\text{ akkor és csak akkor}\text{, ha }\left|x_i-c_i\right|\le d_{i}i=\mathrm{1,2,}\dots N$

ahol c egy középpont-vektor, d pedig a koordináta tengelyekkel párhuzamos elhelyezkedésű négyszög szélességvektora. Mutassa meg, hogy ennek a függvényosztálynak a VC-dimenziója h=2N.

2.4 Mutassa meg, hogy a legmeredekebb lejtő módszerrel dolgozó szélsőérték-kereső eljárás konvergens, ha $0<\mu <\frac{1}{\lambda {}_{\max }}$ . Van-e a konvergenciasebesség szempontjából optimális μ? Ha igen, határozza meg.

2.5 Az LMS eljárás a pillanatnyi gradiens alapján dolgozik. Mutassa meg, hogy az LMS eljárás eredménye torzítatlan becslése a legmeredekebb lejtő eljárással kapott eredménynek, vagyis a súlyvektor várható értéke a Wiener-Hopf megoldáshoz tart.

2.6 Az LMS eljárásnál a bemenet autokorrelációs mátrixa a következő:

$R=\left[\begin{array}{cc}1& \mathrm{0,5}\\ \mathrm{0,5}& 1\end{array}\right]$

Határozza meg a tanulási tényező, μ konvergenciatartományát.

2.7 A következő regularizált kritériumfüggvényt alkalmazza:

$C_r\text{(}w\text{)}={\displaystyle \sum _k\text{(}{d}^{\text{(}k\text{)}}-}{y}^{\text{(}k\text{)}}{\text{)}}^2+\lambda {\displaystyle \sum _i{w}_i^2}$

ahol d^(k) a kívánt válasz és y^(k) a kimenet a k-adik tanítópontra k=1,…, P. Határozza meg a pillanatnyi gradiens alapú tanítási összefüggést, ha egy y=sgm(w^Tx) kapcsolatot megvalósító rendszer paramétervektorát kell tanítania.

2.8 Hogyan befolyásolja az LMS eljárás konvergencia-sebességét a ${\lambda }_{\text{max}}/{\lambda }_{\text{min}}$ arány, ha ${\lambda }_{\text{max}}\text{ és }{\lambda }_{\text{min}}$ a bemeneti jel autokorrelációs mátrixának legnagyobb illetve legkisebb sajátértéke?

2.9 Milyen esetben és hogyan alkalmazható a Karhunen-Loève transzformáció az LMS eljárás konvergencia-sebességének növelésére?

2.10 A genetikus algoritmus alaptétele ((2.141) egyenlet) megadja az S szkémát tartalmazó kromószómák számának alakulását a generációk függvényében. Az összefüggés arányos kiválasztási mechanizmust alkalmazó reprodukció mellett származtatható. Definiáljon más kiválasztási mechanizmust és határozza meg a megfelelő módosított alaptételt.

2.11 Genetikus algoritmus szimulációjával határozza meg az $f\left(x\right)=x+\left|\sin 32x\right|$ függvény maximális értékét, ha $x\in \left[\mathrm{0,}\pi \right]$ .