Paláncz Béla - Soft Computing - 2011 - 1. Adatok közelítése
1. Adatok közelítése Bevezetés
A természettudományos feladatok megoldásához, a vizsgált jelenségek, folyamatok főbb jellemzői közötti összefüggések ismeretére, azaz modelljére van szükség. Gyakran ezek az összefüggések az általános természeti törvények alapján, elméleti alapon levezethetők. Vannak azonban olyan esetek is, amikor ilyen összefüggések közvetlenül nem, vagy csak részben ismertek. Ilyenkor közvetlen, tapasztalati ismeretekre kell támaszkodnunk. A tapasztalati ismeretekből történő információ kinyerésével és ennek alapján történő modell alkotással a mesterséges tanulás elmélete foglakozik. Ide tartozik a mintákon történő tanulás módszerével törtő modellalkotás, az az eset amikor nagyszámú mérési vagy egyéb tapasztalati adat áll rendelkezésünkre és ezen adatok közötti kapcsolatokat kell modell formájában meghatározni. A keresett modellt egy függvénnyel reprezentáljuk. A függvény típusát, formáját felvesszük, kiválasztjuk, majd a függvényben szereplő paramétereket úgy határozzuk meg az adatok alapján, hogy azok legjobb közelítését kapjuk.
1- 1 A közelítő függvény
Matematikailag a tanulás problémáját úgy fogalmazhatjuk meg, hogy keresünk egy olyan, a “valóságos modellt” közelítő f függvényt, amely f:XØY ahol rendelkezésünkre állnak a felállítandó modell bemeneti-kimeneti változóira vonatkozó adatok {xHiL , yHiL }, i = 1,...,m és xHiL œX és yHiL œY. Mivel a valódi modell, azaz a közelítendő függvény ismeretlen, az f közelítő függvénynek olyannak kell lennie, hogy bármilyen függvényt, bármilyen mértékben -másszóval tetszőlegesen kicsiny hibával -képes legyen közelíteni. Azt modjuk, hogy a közelítő függvénynek univerzális approximátornak kell lennie. A legismertebb ilyen függvény típus a polinom. A klasszikus Weierstrass- tétel szerint az összes polinomok [a, b] intervallumon értelmezett halmaza P@a,bD ,a n
p HxL = ‚wi xi i =0
alakú algebrai polinomok sűrűek az [a, b] intervallumon folytonos függvények C[a, b] halmazán. Más szóval egy adott f œ C[a, b] függvény és egy e > 0 érték esetén létezik egy polinom pœ P@a,bD , úgy, hogy †p (x) - f (x)§ < e
2
Adatok_közelítése_01_2011.nb
minden x œ [a, b] esetén. Vannak azonban más függvény típusok is, amelyek szintén univerzális approximátorok. A későbbiekben a neurális hálózatok megismerése során ezekre látunk majd példákat. A modell típusának megválasztása után a modell paramétereit kell meghatároznunk a rendelkezésre álló adatok alapján.
1- 2 A közelítés mértéke
Figyelembevéve, hogy a mérési adatok hibával terheltek, nem kívánjuk meg, hogy f IxHiL M - yHiL = 0 legyen, hiszen nem akarjuk megtanítani a modellnek a mérési hibákat (túltanulás jelensége), de megkívánjuk, hogy f IxHiL M º yHiL azaz a modell “jól” közelítse a mérési adatokat. A közelítés minőségének kvantitatív jellemzésére a különböző normákat alkalmazhatunk. Többváltozós függvény esetén azaz ha pl. Y Õ n legáltalánosabb az ún. Hölder- vagy pnorma, amely alapján a közelítés hibája: 1
n
p
‚°f j - y j •
p
j=1
ahol a j index a vektorok j-edik komponensére utal. A leggyakrabban alkalmazott az Euklideszi norma, azaz p = 2, n
‚°f j - y j •
2
j=1
Ha a mérési pontokban ezeknek a hibáknak a számtani átlaga, az ún. rezidium (maradék) kicsi akkor a függvény jól közelít a mérési pontokban.
1- 3 A közelítés általánosítása
A keresett f függvénynek azonban még egy másik nagyon fontos tulajdonsággal is rendelkeznie kell. Nevezetesen, jó közelítést várunk el tőle olyan xœX pontokban is, amelyek nem mérési pontok, azaz ahol x ∫ xHiL egyetlen i-re sem. Ez persze természetes, hiszen éppen ebből a célból alkalmazunk közelítő függvényt. Miként ellenőrizzük a függvény ezen tulajdonságát, amikor ebben az esetben nem rendelkezünk adatokkal?! A megoldás az, hogy a rendelkezésre álló adatok halmazát két részhalmazra bontjuk, nagyjából 2/3 - 1/3 arányban. A nagyobb részhalmazt tanuló halmaznak nevezzük és ennek segítségével határozzuk meg a paramétereket, majd az így előállított közelítő függvényt ellenőrizzük a kisebb ún. validációs halmazon. Abban az esetben, ha a hiba (rezidium) a tanuló és a validációs halmazon közelítően megegyezik, akkor a közelítő függvény jó generalizácós (általánosító) képességgel rendelkezik. Nézzünk egy egyszerű polinomiális közelítést. 1.1. Példa Ebben az esetben a fokszám növelésével csökkenthetjük a hibát a tanuló halmazon (szélső esetben interpolációvá alakul a közelítés). Azonban ezzel egyidejűleg nő a közelítés hibája a validációs halmazon. Az alábbi ábrák az alultanulás, a megfelelő tanulás és a túltanulás esetét szemléltetik. Mathematica
Adatok_közelítése_01_2011.nb
6 Ñ Ñ 4
Ñ Ñ Ñ
2 Ñ Ñ
0
-2 -4
0
-2
2
4
1.1. ábra A tanuló (Ñ) és a validációs (Ñ) halmaz pontjai
Lineáris közelítés Mathematica
y = 2.67188 + 0.78125 x 6 Ñ Ñ 4
Ñ Ñ Ñ
2 Ñ Ñ
0
-2 -4
-2
0
2
4
1.2. ábra Alul tanulás esete. A rezidium a tanuló halmazon (Ñ) , QT = 1.36, a validációs halmazon ( Ñ ), QV = 0.79 Mathematica
Másodfokú közelítés Mathematica
y = 2.26221 + 0.787061 x + 0.106255 x2
3
4
Adatok_közelítése_01_2011.nb
6 Ñ Ñ 4
Ñ Ñ Ñ
2 Ñ Ñ
0
-2 -4
0
-2
2
4
1.3. ábra Megfelelő tanulás esete. A rezidium a tanuló halmazon (o) , QT = 1.16, a validációs halmazon ( Ñ ), QV = 0.97 Mathematica
Harmadfokú közelítés Mathematica
y = 2.1863 + 1.46114 x + 0.112071 x2 - 0.0793749 x3 6 Ñ Ñ 4
Ñ Ñ Ñ
2 Ñ Ñ
0
-2 -4
-2
0
2
4
1.4. ábra Túltanulás esete. A rezidium a tanuló halmazon (Ñ) , QT = 1.06, a validációs halmazon ( Ñ ), QV = 1.97 Mathematica
Megjegyzés A fenti példánál a függvény a keresett paraméterekben lineáris volt, azaz például másodrendű közelítést tekintve, y HxL = w2 x2 + w1 x + w0 ahol a wi paramétereket direkt módon meghatározhatjuk, hiszen ennek érdekében egy túlhatározott lineáris egyenletrendszert kell csak megoldanunk, y1 = w2 x1 2 + w1 x1 + w0 ... ... ... ... ... ... ... ... ... ... ... ... .. yi = w2 xi2 + w1 xi + w0 ... ... ... ... ... ... ... ... ... ... ... .... yn = w2 xn2 + w1 xn + w0 ahol (xi , yi) az i-edik adatpár. Vagyis az együtthatókra vonatkozó lineáris egyenletrendszer,
Adatok_közelítése_01_2011.nb
5
w2 A w1 = y w0 ahol A egy n × 3 méretű mátrix és y egy n elemű vektor. A direkt megoldás azt jelenti, hogy a keresett együtthatókat véges számú aritmetikai művelettel - a kerekítési hibáktól eltekintve- pontosan meghatározhatjuk.
1- 4 A paraméterek meghatározása, mint globális optimalizáció
Mint láttuk, a függvény típusának megválasztása után, annak paramétereit úgy kell meghatározni, hogy a közelítés hibája, azaz a rezidiuma kicsi legyen. Ez egy optimalizációs feladat megoldását jelenti. Abban az esetben ha a paraméterekben (wiL a függvény lineáris, n
f HxL = ‚wi gi HxL j=1
ahol a gi(x) ún. bázisfüggvények akár nemlineárisak - a feladat egy lineáris regresszióra egyszerűsödik, amely direkt módon megoldható (lásd korábbi Megjegyzés). Azonban ha a közelítő függvény a paramétereket nemlineáris formában tartalmazza, a feladat, mint nemlineáris optimalizáció csak iterációval oldható meg, közelítő pontossággal. Ezzel kapcsolatban a probléma kettős. Egyrészt általában nem ismerjük az iteráció megfelelő kezdőértékeit, így az iterációs eljárás esetleg nem lesz konvergens. Másrészt, mivel több lokális minimum is lehetséges, még konvergencia esetén sem biztosított, hogy a globális minimumot találtuk meg. 1.2. Példa Tekintsük az f (x) = 2.5 sin (1.5 x) függvényt. Állítsunk elő zajos "mérési" pontokat az xœ[-2, 8] intervallumban! Mathematica
3
2
1
0
-1
-2
-3 0
2
4
6
8
1.5 ábra A függvény és a "zajos mérési adatok"
Keressük a közelítő függvényt az alábbi alakban, f (x) = a sin (b x) A paraméterek meghatározása a közelítő függvény és a mérési adatok közötti eltérés minimalizációján alapul. Az
6
Adatok_közelítése_01_2011.nb
A paraméterek meghatározása a közelítő függvény és a mérési adatok közötti eltérés minimalizációján alapul. Az eltérés nagyságának meghatározása, mint láttuk különböző mértékek alkalmazásával lehetséges: a) a legkisebb négyzetek módszere értelmében, azaz n
G Ha, bL = ‚H fi - a sin Hb xiLL2 i=1
Ezt p2 normának nevezik és akkor célszerű alkalmazni, ha a hibák eloszlása normális HGaussL eloszlást követ. b) az abszolút értékek összege alapján, n
G Ha, bL = ‚†H fi - a sin Hb xiLL§ i=1
Ezt p1 normának nevezik és akkor célszerű alkalmazni, ha kieső, hibás méréseink vannak HlehetnekL. c) a legnagyobb eltérés alapján G Ha, bL =
max †H fi - a sin Hb xiLL§
iœ1,...,n
Ezt p¶ normának HCsebisevL nevezik. Ha a hibák eloszlása egyenletes eloszlást követ, akkor ezt célszerű használni Hmin - max feladatL. Alkalmazzuk most a legkisebb négyzetek módszerét. Ekkor a minimalizálandó függvény, n
G Ha, bL = ‚H fi - a sin Hb xiLL2 i=1
Mathematica
1.6 ábra A minimalizálandó hibafüggvény az p2 norma esetén
A szintvonalas ábrázolási módban jól kivetők a lokális minimumok helyei, Mathematica
Adatok_közelítése_01_2011.nb
1.7 ábra A hibafüggvény lokális minimumai
Látjuk, hogy több lokális minimum is van! 1.1 Táblázat
Kezdő érték Minimumhely A hibafüggvényértéke 8a0 , b0 < 8a, b< f Ha, bL 81.0, 0.5< 80.967419, 0.557085< 63.312 81.0, 2.5< 80.691571, 2.41307< 67.1169 82.5, 1.5< 82.57973, 1.49742< 2.01497 Attól függően más-más minimumot kapunk, hogy honnan indult a lokális minimumkereső módszer iterációja! Mathematica
7
8
Adatok_közelítése_01_2011.nb
1.8 ábra A hibafüggvény globális minimuma (æ)
A globális minimum helye a =2.57973 és b =1.49742. A globális minimum meghatározása nehéz feladat! A következőkben olyan globális optimalizációs módszereket ismertetünk, amelyek algoritmusai maguk is valamilyen mesterséges tanulási módszerre vezethetők vissza és hatékonyan alkalmazhatók még nagyszámú paraméter esetén is anélkül, hogy igényelnék a paraméterek közelítő értékeit, mint kezdeti értéket.
