Készítette: Méhes Zsolt MEZOAAG.KEFO
Vizsgakérdések 2008-2009. tanév, ıszi félév
Intelligens rendszerek 1. Az alakzatalakzat-felismerés feladatköre, 1D és 2D alkalmazási példák, egy jelfelismerı rendszer tipikus felépítése. Jel, vektor, vektortér, távolság, norma, skaláris szorzat, bázis, ortonormált ortonormált bázis, reprezentáció. Az alakzat-felismerés feladatköre: az a tudományterület, ami objektumok valamely kategóriába vagy osztályba sorolásával foglalkozik.
Fontosabb alkalmazások: • • •
• • • •
Optikai karakterfelismerés Beszédfelismerés Biometriai alapú személy-azonosítás o hang, ujjnyomat, tenyérkép, kézírás o írisz, retina, DNS, ... Döntéstámogatás (orvosi diagnosztika, gazdaság) Orvosi, biológiai, ipari, mezıgazdasági célú képosztályozás Távérzékelés (például termésbecsléshez) ...
Jelfelismerı rendszer felépítése: mintatér
Mérés, elıfeldolgozás
lényegtér
Lényegkiemelés
osztályozási tér
Osztályba sorolás
Bemenı jel
Döntés
Jel: olyan információhordozó fizikai jellemzı, ami mérhetı és matematikai módszerekkel modellezhetı →jelmodell. Jelek csoportosítása: Nagy/kevés Folytonos/diszkrét jel Determinisztikus/sztocinformációtartalmú jel hasztikus/kaotikus jel Az alakzat-felismerésben elsısorban sztochasztikus (véletlen) jeleket használnak. Jeltér: speciális jelhalmaz, amire jellemzı, hogy elemei véges energiájú jelek -> lineáris, metrikus, skalárszorzat tér. Vektor: irányított szakasz.
x0 Vektortér: a rendezett szám N-esek tere (oszlopvektorok): x = ... . x N −1
-1-
Készítette: Méhes Zsolt MEZOAAG.KEFO
Távolság: vektorok távolsága egymástól. Fajtái:
∑ (xi − yi ) . N −1
Euklideszi-távolság: d ( x, y ) =
•
2
i =0
N −1
Manhattan távolság: d ( x, y ) =
∑x −y Max-távolság: d ( x, y ) = max{ x − y }
• •
i
i =0
i
i
.
i
Norma: a vektort saját maga transzponáltjával skalár-szorozzuk: x =
(x, x ) . T
Skaláris szorzat: két vektor szorzata, a második egy transzponált vektor, eredményül egy konstanst kapunk:
(x, y ) T
y0T = ∑ xi ⋅ yiT = ( x0 ,...x N −1 ) ... = x0 ⋅ y0T + ... + x N −1 ⋅ y TN −1 . i =0 yT N −1
(
N −1
)
(
)
Bázis: a vektorrendszer bázist alkot ha a vektorok lineárisan függetlenek. Ezt a vektorokból felírt determinánsból határozhatjuk meg, ha a determináns értéke nem 0, akkor lineárisan függetlenek a vektorok. Ortonormált bázis: megvizsgáljuk, hogy a vektorrendszer ortogonális-e (merılegesek-e egymásra: az összes vektor pár skalárszorzata 0), normáltak-e (hosszuk egységnyi) és bázist alkotnak-e (a vektorok lineárisan függetlenek). Ha ezek a feltételek teljesülnek akkor a vektorrendszer ortonormált bázist alkot. i=0,1,2,…,N-1. x =
Reprezentáció: az x {ui} –beli reprezentációja: ai
N −1
N −1
i =0
i =0
∑ ( x, u i ) ⋅ u i = ∑ a i ⋅ u i .
2. Mátrix sajátértékei, sajátvektorai. Adatrendszer, kovariancia kovarianciaariancia-mátrix. A KLT mátrixa. Kovarianciamátrix a transzformált térben KLT esetén. Mátrix sajátértékei, sajátvektorai: A ⋅ v = λ ⋅ v , ahol ’A’ egy NxN-es mátrix, λ a sajátérték, v pedig a λ sajátértékhez tartozó súlyvektor.
A ⋅ v = λ ⋅ v ⇒ A ⋅ v − λ ⋅ v = 0 ⇒ A ⋅ v − ( Eλ ) ⋅ v = 0 ⇒ ( A − Eλ ) ⋅ v = 0 .
Mivel v≠0 ezért a
( A − Eλ ) ⋅ v = 0 feltétel csak akkor teljesül, ha det( A − Eλ ) = 0 . A
sajátértékek egy N-ed fokú egyenlet gyökei.
1 2 − 4 3 . − 1 1 − 1 2
Adatrendszer: M darab N dimenziós vektor halmaza. Pl.: M=4, N=2 esetben: A 2D-s adatrendszer jellemzıi: Koordináta
β=
1 M
x T = (α , β ) , az adatrendszer egyes vektorai: (αi,βi). α =
átlag:
M −1
∑β i =0
i
. 2
Kovarianciák: cα ,β
(
)
(
2 1 N −1 1 N −1 2 , s = ∑ ∑ β N i =0 α i −α N i =0 β i − β 1 N −1 = ∑ α i − α β i − β és cα,β=cβ,α N i =0
Szórásnégyzet: sα =
(
)(
)
2
)
2
.
1 M
M −1
∑α i =0
i
Készítette: Méhes Zsolt MEZOAAG.KEFO
sα2 Kovariancia mátrix: K = c β ,α
cα ,β . s β2
Dimenzió-csökkentés KLT-vel: 1. Adott az N dimenziós mintatérbeli vektorból álló X adatrendszer 2. A K kovariancia-mátrix számítása az adatrendszerbıl 3. A kovariancia-mátrix N db sajátértékének és rendre a hozzájuk sajátvektoroknak a számítása 4. A sajátértékek nagyság szerint sorbarendezése 5. Eszerint véve a sajátvektorokat, mint sorvektorokat, megalkotjuka T transzformációs mátrixot (NxN-es mátrix) 6. T-vel transzformáljuk az adatrendszer vektorait 7. A transzformált térben meghagyjuk az elsı M
0 − 0 .1 0 .4 1 1 .5 − 0,707 0,707 , , X = T-mátrix: T = 0 − 0 .1 0 .4 1 1 .5 0,707 0,707 0 0 0 0 0 . Az adatrendszer Transzformált adatrendszer: X 1 = 0 − 0,141 0,566 1,414 2,121 Pl.:
adatrendszer:
tagjait megszorozzuk a T-mátrix megfelelı sorával.
Általánosított kovarianciamátrix: a teljes osztályba sorolási feladatra, adott: • • •
az osztályok száma (L) mindegyik osztály esetén az osztályreprezentáns-pontokból kovariancia-mátrixa mindegyik osztály elıfordulási (a priori) valószínősége
álló
adatrendszer
L −1
K (Ω ) = ∑ P (ωl ) ⋅ K (ωl ) . l =0
3. Lényegkiemelés dimenziócsökkentéssel, PCA, lényegkiemelés diszkrét ortogonális transzformációkkal, transzformációkkal, összehasonlítás a KLTKLT-vel. Lényegkiemelés diszkrét ortogonális transzformációkkal: A KLT-nél megismert algoritmus követhetı, de adott a transzformáció mátrixa. Mi legyen a dimenziócsökkentı eljárás? (pl. a legkisebb abszolút értékő összetevık elhagyása, stb.)
4. A diszkriminanciadiszkriminancia-függvény fogalma, osztályokat elválasztó hiperfelületek. A lineáris diszkriminanciadiszkriminancia-függvény származtatása, osztályokat elválasztó hipersíkok. Osztályba sorolás lineáris diszkriminanciadiszkriminancia-függvénnyel. Minden egyes osztályhoz tartozik egy diszkriminancia-függvény, amely a feladatpont osztályba sorolásához a következıképpen használható:
ωk = g ω (x ) . k
A k-adik osztályt az l-ediktıl
elválasztó tartományt azon pontok halmaza adja, ahol a fenti döntési szabályban egyenlıség van (egyik osztályba sem sorolható a feladatpont):
g ω k ( x ) = g ωl ( x ) .
A lineáris diszkriminancia-függvény meghatározása: Minden egyes osztályhoz tartozik egy súlyvektor úgy, hogy ennek és a feladatpont kiegészítésével kapott vektornak a skalárszorzata a
3
Készítette: Méhes Zsolt MEZOAAG.KEFO
lineáris
wω k
diszkriminancia-függvény:
c0ωk c1ωk = 1 ωk T ωk − c ⋅c 2
( )
g ω k ( x ) = wω k
T
⋅ x* .
ωk . Két osztályt elválasztó hipersík: w
( )
T
x0 x * = x1 , 1
Ha
( )
⋅ x * = wωl
T
akkor
⋅ x* .
Osztályba sorolás a lineáris diszkriminancia-függvénnyel: • • • •
Határozzuk meg minden egyes osztály esetén a prototípuspontokból a centrumpontot. A centrumpont ismeretében határozzuk meg minden egyes osztályhoz a súlyvektort és a lineáris diszkriminancia-függvényt. A feladatpont ismeretében számítsuk ki minden egyes osztály esetében a lineáris diszkriminancia-függvény értékét. Abba az osztályba soroljuk a feladatpontot, amelynek a diszkriminancia-függvénye a legnagyobb értékő.
5. A legközelebbi szomszédszomszéd-elvő és a kk-NN osztályozó. Osztályba sorolás statisztikai jellemzıkkel, BayesBayes-döntés. Az osztályba sorolás hibája. k-legközelebbi szomszéd (k-NN, Nearest Neighbor) 1.: • • • •
Adott az egyes osztályok prototípuspontjaiból álló adatrendszer. Adott egy távolság-definíció a pontok távolságának számítására, és a k páratlan pozitív egész szám. Az x feladatpont körül a lényegtérbenaddig növesztünk egy gömböt, amíg összesen k prototípuspont nem lesz benne. A feladatpontot abba az osztályba soroljuk, amelybıl több prototípuspont található a gömbben.
k-legközelebbi szomszéd (k-NN, Nearest Neighbor) 2.: • •
Adott az egyes osztályok prototípuspontjaiból álló adatrendszer. Adott egy távolság-definíció a pontok távolságának számítására, és a k pozitív egész szám. • Minden egyes osztály esetén k db legközelebbi szomszédot keresünk, és az adott osztályt ezek átlagával jellemezzük. • A feladatpontot abba az osztályba soroljuk, amelynél a fenti távolság a legkisebb. Osztályba sorolás statisztikai jellemzıkkel: a feladatnál adott az osztályok száma (K), mindegyik osztály (ωk) esetén az f ( x | ω k ) valószínőség sőrőség-függvény, ahol x egy N dimenziós vektor. Továbbá mindegyik osztály esetén a
P(ω k ) osztály-elıfordulási valószínőség az osztályozási
feladat során (a priori valószínőség). Kérdés: x feladatpontot melyik osztályba soroljuk úgy, hogy a hiba valószínősége a legkisebb legyen? Ezt Bayes-döntéssel oldhatjuk meg: P (ω k ) ⋅ f ( x | ω k ) > P ω j ⋅ f x | ω j , ∀j ≠ k ⇒ x ∈ ω k . Rendelkezésünkre áll P (ωk ) és f ( x | ω k ) ,
( ) (
)
f (ω k | x ) -re van szükségünk. Ez Bayes-tétel alkalmazásával megadható: f ( x | ω k ) ⋅ P(ω k ) f (ω k | x ) = , mivel f ( x ) minden osztály esetében szerepel a feltételes f (x )
de
nekünk
valószínőség nevezıjében, a relációk vizsgálatában nem játszik szerepet.
4
Készítette: Méhes Zsolt MEZOAAG.KEFO
6. Klaszterezés a kk-közép eljárással, a klaszterezés jósága. Klaszter: a prototípus-alakzatok olyan csoportja, amelyben az egyes alakzatok egymáshoz "közel vannak", illetve "hasonlóak".
Feladatok: • • •
Hogyan kell elvégezni a klaszterekre bontást úgy, hogy az valamilyen szempontból "jó" legyen? Ha már léteznek klaszterek, mi legyen a klaszter középpontja (centrumpontja) ?
Centrumképzési módszerek: o MINIMAX-centrum:
a klaszter azon pontja, amely esetén a tıle legtávolabbi klaszter-beli ponttól mért távolság a legkisebb
o
súlypont jellegő centrum: a klaszter azon pontja, amelyre a többi elemtıl vett átlagos távolság a legkisebb
Klaszterezı algoritmus: 1) Adott az adathalmaz, klaszterek száma, és egy ε>0 hibakorlát. 2) Vegyünk fel N db tetszıleges kiinduló klaszter-középpontot. 3) Képezzünk n db klasztert úgy, hogy mindegyik prototípuspontot hozzárendeljük a legközelebbi klaszter-középponthoz (N). 4) Határozzuk meg a kapott klaszterek középpontját (centrumpontját). 5) Ha a kapott centrumot ε>0 hibakorlátnál kevésbé térnek el az elızı iterációban kapott centrumtól, akkor vége a folyamatnak. 6) Egyébként lépjünk vissza a 2). pontra.
Klaszterezés jósága: 1) Meghatározzuk az átlagos, klaszterek közötti távolságot (dkk): kiszámítjuk az összes lehetséges klaszterpárosítás esetén az összes lehetséges távolságot, majd elosztjuk az összes távolság darabszámával (i),
d kk =
∑d . i
2) Kiszámítjuk az átlagos, klaszteren belüli távolságokat: meghatározzuk minden klaszteren belüli pontpárnak a távolságát, majd ezek átlagát vesszük. 3) Klaszterek jóságának számítása (dkb): az átlagos, klaszteren belüli távolságok összegét elosztjuk a klaszterek számával. 4) Végül meghatározzuk a klaszterezés jóságát:
β=
d kk d kb
7. A mesterséges neuronhálózatok alapfogalmai. Az adalineadaline-hálózat és a RosenblattRosenblattféle perceptron hálózat felépítése, tanítása és alkalmazása. ANN (Artificial Neural Network), mesterséges neuronhálózat, mesterséges neurális hálózat, mesterséges ideg(sejt)hálózat: •
•
definíció (1988: DARPA (Defense Advanced Research Project Agency)): A mesterséges neuronhálózat olyan rendszer, amely nagyszámú, egyszerő, párhuzamosan mőködı feldolgozó elembıl áll. A rendszer funkcióját a hálózati struktúra, a kapcsolatok erıssége és az egyes feldolgozó elemek által végzett mővelet határozza meg. definíció (1994, 1999: Haykin): A mesterséges neuronhálózat erısen párhuzamos, elosztott processzor, amely képes a kísérleti eredmények tárolására és elıhívására. Az emberi agyhoz két dologban hasonlít: o a hálózat a "tudását" tanulási folyamattal szerzi meg,
5
Készítette: Méhes Zsolt MEZOAAG.KEFO o
a "tudást" a mesterséges neuronok közötti kapcsolatok erıssége, az ún. szinaptikus súlyok tárolják.
Tipikus feldolgozó elem (PE): X0 w0
X1
w1
XN-1
N −1
1
X0
wN-1
Bemenı vektor
w0
X1
∑w
−ϑ
i =0
* i
⋅ xi*
w1
N −1
lin nemlin PE y = f ∑ wi ⋅ xi − ϑ i =0 XN-1 wN-1 PE 1 1 x w 0 0 Kimeneti függvény x* = w* = ... ... (nemlinearitás) x w N −1 N −1 ϑ Szinaptikus súlyvektor
((
)
T N −1 * * y = f ∑ wi ⋅ xi = f w* ⋅ x* i =0
Szinaptikus küszöbérték
)
Tipikus kimenetei nemlinearitások: f(x) 1
f(x) 1 x
1
f(x) 1
f(x) 1 x
-1 1
-1
Szigmoid függvény: f ( x ) =
x
x
-1
1 1 + e−x
Tangens
hiperbolikusz
f ( x ) = tanh ( x ) =
sh( x ) e − e = ch( x ) e x + e − x x
függvény:
−x
Mesterséges neuronhálózat az elemi feldolgozóegységekbıl: Bemenete az x vektor, kimenete az y vektor. Több rétegbıl áll: bemeneti réteg, rejtett réteg(ek), kimeneti réteg. Fajtái: • •
Elırecsatolt: nincs visszacsatolás. Általános: lehet visszacsatolás rétegen belül és rétegek között is.
6
Készítette: Méhes Zsolt MEZOAAG.KEFO
Ellenırzött tanulás, tanítóval történı tanulás (supervised learning): Cél: a rendelkezésre álló osztályreprezentáns pontokból (prototípuspontokból) kiindulva a tanuló algoritmus segítségével az egyes feldolgozó elemek (neuronok) súlyvektorainak meghatározása.
Hogyan lesz ebbıl algoritmus? tanulás→valamit "jól" tud (optimalitás)→kritérium-függvény→feltétel nélküli szélsıérték keresési eljárások→algoritmusok Tipikus kritérium-függvény: négyzetes hibakritérium Szélsıérték keresési eljárások: kimerítı keresés, "legmeredekebb lejtı" módszer stb. A tanulási folyamat során a prototípuspontokhoz adott még az is, hogy mi az egyes kimeneti rétegbeli PE-k (neuronok) elvárt értéke (célérték). Ezért képezhetı a jelenlegi érték yk és elvárt érték tk különsége, ek=tk-yk minden egyes kimeneti neuron esetében. Eltérésvektor négyzete: 2
K −1
E = e = e ⋅ e = ∑ (t k − y k ) → min . 2
T
k =0
A kimerítı keresés számítási idı igényes: az E=f(w) kritériumfüggvényt a súlyvektor egyes komponensei által kifeszített N-dimenziós rács minden pontjában ki kell értékelni, és e számok minimumát venni.
Adaline -adaptive linear neuron, adaptive linear element (Widrow, Hoff, 1960): X0 w0
X1
N −1
w1
s = ∑ wi ⋅ xi i =0
PE
XN-1
wN-1
Bemenı vektor
f(x) 1
y ∈ {− 1,1}
-1
e=t-s -
+
t ∈ {− 1,1} Tanítás a lineáris kimeneteknél
Szinaptikus súlyvektor
Bináris célérték
Adaline 2 rétegő hálózatba szervezve:
x0p = 1
Lineáris kimenet Célérték
w0, 0
PE 0
y0p
t 0p
y1p
t1p
w0, N x1p w1, N
x Np
PE1
(
1 M −1 y = w ⋅ x = ∑ w j ,i ⋅ x → E = ⋅ ∑ t jp − y jp 2 j =0 i =0 p p y M −1 t M −1 PE p j
wM −1, N
N
T j
p
p i
p
)
2
M −1
Az adaline tanuló algoritmus: 1) Az egyes neuronok súlyvektorai összetevıinek kezdeti értékadás kis véletlen számokkal. Az αtanulási tényezı felvétele 0 és 1 közé, leállási feltétel megadása kis pozitív ε küszöbszám alapján. 2) A következı prototípusvektor bemutatása és a hozzátartozó kimenti célértékvektor elıvétele. 3) Az egyes neuronok aktuális kimeneteinek számítása.
7
Készítette: Méhes Zsolt MEZOAAG.KEFO 4) Az
w
p j ,i
egyes
neuronok
(n + 1) = w j ,i (n ) + α ⋅ (t
p j
)
súlyvektorai
súlytényezıinek
módosítása:
− y ⋅x p j
p i
5) Ha a leállási feltétel nem teljesül, GOTO 2. 6) STOP Leállási feltétel adható pl. a hálózatra definiált energia változásának abszolút értéke alapján. A Rosenblatt-féle perceptron hálózat (1958): Az adaline a Rosenblatt-féle perceptronhoz hasonló, de ez a nemlinearitás után tanít. Az eredetileg heurisztikus algoritmus formálisan származtatható a
wtj+1 = w tj + α ⋅ (t j − y j )⋅ x adaline-iterációból. A kimeneti érték és a célérték
wtj tj = yj t t +1 vagy +1, vagy -1. Az egyes neuronok súlyvektorának iterációja: w j = w j − 2 ⋅ x t j = −1, y j = +1 . wt + 2 ⋅ x t = +1, y = −1 j j j Az egyrétegő hálózat csak olyan osztályba sorolási feladat esetén használható, amelynél a lényegtér lineárisan szétválasztható az egyes osztályok tartományaira.
8. A többrétegő perceptron hálózat felépítése, tanítása és alkalmazása. A többrétegő perceptron hálózat (MLP) felépítése: X0=1 X1
w0 w1
PE
nemlin y=f(net)
lin
y ∈ (0,1)
XN wN
Bemeneti vektor
f (x ) =
N
Súlyvektor
net = ∑ wi ⋅ xi i =0
8
1 1 + e−x
Készítette: Méhes Zsolt MEZOAAG.KEFO
Az MLP tanuló algoritmus f=th(x) esetén: 1) Az egyes neuronok súlyvektorai összetevıinek kezdeti értékadás kis véletlen számokkal. Az α csillapítási tényezı és az η tanulási tényezı felvétele 0 és 1 közé, leállási feltétel megadása kis pozitív ε küszöbszám alapján.
net j = ∑ wi , j ⋅ xi és h j = th(net j ) számítása. N
2)
i =0 N
3)
net k = ∑ wi ,k ⋅ xi és hk = th(net k ) számítása. i =0
1 M −1 4) E = ⋅ ∑ (t k − y k ) számítása a leállási feltételhez. 2 k =0 5) δ k = (t k − y k ) ⋅ (1 + y k ) ⋅ (1 − y k ) számítása.
δ 'j = ∑ δ k ⋅ w j ,k δ j = δ j' ⋅ (1 + h j )⋅ (1 − h j ) számítása (ez a hiba visszaterjesztés, BP). M −1
6)
k =0
7)
w
' j ,k
= α ⋅ w j ,k + η ⋅ δ k ⋅ h j wi' , j = α ⋅ wi , j + η ⋅ δ j ⋅ xi számítása.
8) Ha a leállási feltétel teljesül, STOP, egyébként GOTO 2.
9. Tanító nélküli tanítás mesterséges neuronhálózatokkal, a versengı tanulás. A Kohonenvektor--kvantálás. Kohonen-hálózat felépítése, tanítása és alkalmazása, a tanuló vektor Tanító nélküli tanulás, felügyelı nélküli tanulás (unsupervised learning) –klaszterezés: versengı tanulás (competitive learning): kiválogatódik, hogy melyik neuron reagáljon a megtanult súlyvektora alapján a feladat alakzatra
(Kohonen-térkép; Self Organinzing feature Maps, SOM, Kohonen, 1982, 1989): a versengı tanulás olyan változata, amelyben a egyszerre tanítjuk az egymással topológiai szomszédságban lévı neuronokat
Vektor-kvantálás: A skalár kvantálás egy intervallumhoz rendel egyetlen belsı pontot, a vektor kvantálás egy Ndimenziós térrészhez rendel egyetlen N-dimenziós térbeli belsı pontot (azaz N-dimenziós vektort).
Versengı tanulás (competitive learning): 0. Adott a K darab N dimenziós referencia-vektor (w, súlyvektorok), adott P darab prototípusvektor az osztályazonosító nélkül, adott egy hasonlósági mérték (pl. az Euklideszi távolság), adott a T iterációszám és a tanulási tényezı. 1. A referencia-vektorok kezdeti értékének beállítása kis álvéletlen számokkal. 2. Az alábbi lépések ismétlése T-szer: 2.1. Az új prototípuspont és az egyes neuronok távolságának számítása. 2.2. Kijelöljük azt a neuront, amelynél a távolság a legkisebb. 2.3. Ezen neuron súlyvektorát úgy változtatjuk, hogy a prototípus ponthoz közelebb kerüljön, a többi neuron súlyvektorát nem változtatjuk. 2.4. GOTO 2.1.
Alapalgoritmus iterációs lépései:
α 0 1 − t 0 < t < T1 w j (t + 1) = w j (t ) + α (t ) ⋅ (x − w j (t )) , 0 < α (t ) < 1 , α (t ) = α 0 ; α (t ) = T1 . t ≥ T1 α1 Az alap algoritmus optimalitása: a súlyvektorhoz "közeli" "gyakori" x-ekre" "jobban" válaszol a neuron, az algoritmus az
E = ∫ x − w j ⋅ p ( x )dx kifejezést minimalizálja a wj-k elıállítása során. 2
9
Készítette: Méhes Zsolt MEZOAAG.KEFO Más elnevezés:a wj-k a kódszótár vektorai, az eljárás pedig vektor kvantálás (VQ, Vector Quantization). Kohonen-térkép (Self Organinzing feature Maps, SOM, Kohonen, 1982, 1989): a versengı tanulás olyan változata, amelyben egyszerre tanítjuk az egymással topológiai szomszédságban lévı neuronokat. Eredménye, hogy a "hasonló" bemenı vektorokra (pontokra, mintákra) a geometriailag közel lévı PE-k válaszolnak "gyıztes"-ként. Neurobilógiai analógia: az agy mőködése során megfigyelhetı, hogy az érzékszervek jelei meghatározott agykérgi területeken váltanak ki aktivitást (pl. tonotopikus leképezés a hallás esetén). A neuron szomszédsági halmaza: pl. négyzetrács, hatszöglető rács
24-es szomszédság 6-os szomszédság 8-as szomszédság Hj a j-edik neuron szomszédsági halmaza. A szomszédságot az a neuron jelöli ki, amelyhez a prototípuspont a legközelebb van. Minden lépésben csak a szomszédsági halmazba tartozó neuronok súlytényezıit módosítja, e halmazon kívüliekét nem. A súlytényezı módosítása a wi (t
w (t ) + α (t ) ⋅ ( x(t ) − wi (t )) i ∈ H j (t ) + 1) = i i ∉ H j (t ) wi (t )
kifejezéssel végezhetı el. A szomszédsági halmaz is változhat az iteráció elıre haladtával. Cél: wj optimális elhelyezése 1. A wj súlyvektorok kezdeti beállítása a SOM algoritmussal. 2. A wj vektorok osztályokhoz rendelése ismert osztályba tartozó vektorok segítségével ("kalibrálás") 3. Az x-hez legközelebbi, kódszótárbeli wj finomítása súlytényezı-módosítással (az alábbiak ismétlése T-szer)
w (t ) + α (t ) ⋅ (x(t ) − w j (t )) ha x − et helyesen osztályozza w j (t + 1) = j A többi kódszótárbeli wi (t ) − α (t ) ⋅ ( x(t ) − wi (t )) ha x − et tévesen osztályozza
vektort nem változtatjuk.
A Kohonen-térkép alkalmazása: fonetikus írógép (SOM és LVQ): a fonéma alapú CSR finn és japán nyelvre. 1. akusztikai elı-feldolgozás (antia-aliasing szőrı, fH=5,3 kHz, 12 bit ADC, spektrális elemzés Hamming-ablakkal [N=256 FFT], 15 sávban teljesítményszámítás, a 15 dimenziós vektorok normalizálása átlag és szórás alapján) 2. SOM + LVQ (8x12-es hatszög rács [96 neuron], kézi fonémaszegmentálás nélküli tananyagon SOM elıtanítás, ismert stacionárius fonémákkal kalibrálás és LVQ finomhangolás) felismerési pontosság: 80-90% 3. a felismerés pontosságának növelése korrekciós nyelvtani szabályokkal felismerési pontosság: 92-97%
10
Készítette: Méhes Zsolt MEZOAAG.KEFO
10. A HopfiedHopfied-hálózat és a HammingHamming-MAXNET hálózat, mint bináris, asszociatív memória (felépítés, tanítás és alkalmazás). Asszociatív memória: tartalommal címezhetı (CAM, Content Addressable Memory) - auto-asszociatív: a bemeneti mintázat megtalálható-e a rendszerben? - hetero-asszociatív: a bemeneti mintázathoz rendelt bitsorozat megtalálható-e a rendszerben? A hetero-asszociatív esetben a tanítás a <minta|mintához tartozó bitsorozat> párokkal történik, az elıhívás csak a <minta> alapján →a stabil hálózat kimeneteibıl olvasható le, a <mintához tartozó bitsorozat> válasz is
Megoldandó feladatok: - a minták tárolása a hálózat súlyvektoraiban - a tárolt minták elıhívásának módja - fontos jellemzı: a tárolható minták száma (kapacitás)
Az asszociatív memóriának két fı típusa van: Hopfield-hálózat: elosztottan tárolja a
Hamming-hálózat: koncentráltan tárolja a
mintákat, nem mondható meg, hogy a minta pontosan melyik neuron súlyvektorában van
mintákat, pontosan tudható, hogy a minta melyik neuron súlyvektorában van
A Hopfield-hálózat: N dimenziós bináris vektorok: xi ∈ {− 1,+1}
+ 1 s ≥ 0 − 1 s < 0
Kimeneti nemlinearitás: f (s ) = Egy neuron:
Visszacsatolt hálózat: N −1
x0 x = xi x n−1
s = ∑ w j ,i ⋅ xi
w j = w j ,i
i =0
a
y j = f (s )
w0
PE0
a0
wj
PEj
aj
wN-1
PEN-1
aN-1
a
a
A tárolt minta az elıhívás után legyen stabil, amia j-edik neuron kimenetére felírva:
1 N −1 w j ,i = f ∑ w j ,i ⋅ ai = a j , a j ∈ {− 1,+1} . Ha N i =0 N −1 N −1 1 N −1 1 1 f ∑ ⋅ a j ⋅ ai ⋅ ai = f ∑ ⋅ a j ⋅ ai2 = f a j ⋅ ∑ = f (a j ) = a j . i =0 N i =0 N i =0 N A
tárolás
w(jP,i ) = w (j P,i −1) +
algoritmusa:
a
P.
bináris
P
1 (P ) (P ) 1 ⋅ a j ⋅ ai = ∑ a (j p ) ⋅ ai( p ) . N N p =1 11
mintázat
⋅ a j ⋅ ai ,
hozzátanítása
akkor:
után:
Készítette: Méhes Zsolt MEZOAAG.KEFO
Az elıhívás algoritmusa (aszinkron változat, a neuronok nem egyszerre, hanem sorban egymás után váltanak értéket): Feladat: annak megállapítása, hogy a b bemenı minta benne van-e a hálózatban; a megoldás módja: a Hopfield-hálózat, mint rendszer válaszának számítása 1. Adott a b kiindulási kimenı érték vektor és a T iteráció szám. 2. A hálózat b*, kimenı érték vektorának számítása sorban egymás után. 3. Ha a kimenı érték vektor T iteráció után nem változik, akkor STOP, egyébként GOTO 2. Legyen a leállás utáni kimenı érték vektor b*. Ha b=b*, akkor "benne van", egyébként "nincs benne". A hálózat kapacitása: egy N neuronból álló Hopfield-hálózat esetén a tárolható minták száma kb.
N N max ≈ . Kis számú tárolt minta esetén a tárolt mintától "kicsit távolabb" lévı mintával ln ( N ) indulva is a tárolt mintához jutunk →a tárolt mintának "vonzáskörzete" van →a Hopfield-hálózat képes "hiányos", "zajos" minták "helyreállítására", "felismerésére".
A Hamming-hálózat: • N dimenziós bináris vektorok: xi ∈ {− 1,+1} •
Hamming-távolság: d H ( p, x ) =
•
A
N −1 1 ⋅ N − ∑ pi ⋅ xi , pi , xi ∈ {− 1,+1} 2 i =0
Hamming-távolság N −1
eltérése
a
dimenziótól:
N −1
1 p N N − d H = N − N − ∑ pi ⋅ xi = ∑ i ⋅ xi − − 2 2 i =0 i =0 2 •
A küszöbértékkel rendelkezı neuron egyenletével összehasonlítva: w =
p N , ϑ=− . 2 2
Tárolás: minden neuron egy-egy ideális mintát tárol a fenti súlyvektorban. Kimenet számítása a MAXNET-hálózattal -oldalirányú gátlás (lateral inhibition):
x>N N f (x ) = x 0 ≤ x ≤ N 0 x<0
Elıhívás: a MAXNET-iterációval 1. A bemeneti vektor és az egyes neuronok súlyvektoraiban tárolt ideális prototípuspontoknak a lehetı legnagyobb Hamming-távolságtól (N) való eltérésének számítása
12
Készítette: Méhes Zsolt MEZOAAG.KEFO 2. Alkalmas leállási feltételig az 1. pont kiinduló értékeivel az alábbi iteráció számítása
y k (0 ) = f − ϑk + wkT ⋅ x , y k (t + 1) = f y k (t ) − ε ⋅ ∑ y j (t ) . Az elnevezés oka az, hogy az j ≠k
(
)
iteráció végén a legnagyobb kezdeti értékő neuron kimenete nem nulla.
A Hamming-hálózat zajos minták esetén: Kapacitás(legfeljebb
ennyi képes
vektort
N
dimenziós tárolni):
N max = 2πNα (1 − α ) ⋅ e N ⋅G (α ) G (α ) = ln(2) + α ln(α ) + (1 − α )ln(1 − α ) .
Alkalmazási példa: IFK mérés nagy entrópiájú jelek esetén.
11. Az RBFRBF-hálózat felépítése, tanítása és alkalmazása. Radiális bázisfüggvényes (RBF) hálózatok: g1(x)
x1
w1
g2(x)
w0
w2
x2
wN
gN(x)
Adottak a radiális függvények középpontjai
y
c0 ci i0 és a szélessége 2 ⋅ σ 2 = k , ahol k egy ci
konstans szám. Ezekbıl meghatározható a függvény:
g i (x ) = e
− x −ci 2⋅σ 2
2
. w0 a küszöbérték,
amit nem kötelezı megadni. Az y értéke a következıképpen alakul mindegyik bemeneti variáció N
esetén:
y = w0 + ∑ g i ⋅ wi .
Az
i =1
w0 w0 egyenletrendszer vagy mátrix w0 w 0 de egyszerőbben kifejezve G ⋅ w = d * + pszeudo-inverzzel, w = G ⋅ d , ha a
összes
g11 ( x ) g12 ( x ) g13 ( x ) g14 ( x )
bemeneti
... ... ... ...
variációra
meghatározott
y-okat
g 1N ( x ) d w0 1 2 g N (x ) d 2 ⋅ ... = alakban is felírhatjuk, g N3 ( x ) d 3 wN d g iN4 ( x ) 4
alakra is hozhatjuk, ahol d a bináris, elvárt érték. Megoldás
G ⋅ w* = d is teljesül, akkor elfogadjuk a megoldást.
13
