E. függelék - Optimalizáció

Tartalom

Feltétel nélküli optimalizálás
Numerikus módszerek
Feltételes optimalizálás
Egyenletekkel adott feltételek
Egyenlőtlenségekkel adott feltételek

Az optimalizáció függvények maximumának illetve minimumának megkeresésére szolgáló módszer. Az adatbányászatban azért fontos a szerepe, mert sok feladat megfogalmazható optimalizációs problémaként. A 8.2.1. szakaszban leírt K -közép klaszterező algoritmus célja például a klaszterek egy olyan halmazának megkeresése, mely a négyzetes hibát (SSE, lásd a D. függeléket) minimalizálja. Hasonlóan, a D.2.1. szakaszban tárgyalt legkisebb négyzetek módszere arra alkalmas, hogy megtanulja azokat a regressziós együtthatókat, amelyek minimalizálják a modell SSE-jét. Jelen szakasz egy rövid áttekintését adja az optimalizáció során használatos különböző módszereknek.

Feltétel nélküli optimalizálás

Legyen f(x) egy egyváltozós függvény, folytonos első- és másodrendű deriváltakkal. Egy feltétel nélküli optimalizáció feladata olyan x * érték megtalálása, melyben az f(x) függvény maximális vagy minimális. Ilyenkor x * -ra nem teszünk kikötést. A stacionárius pontként is nevezett x * megoldást úgy kereshetjük meg, hogy f(x) első deriváltját nullával tesszük egyenlővé, és a kapott egyenletet megoldjuk:

df dx | x= x * =0.

Az f( x * ) lesz -- a második deriválttól függően -- a maximális vagy a minimális érték, vagy az inflexiós pont:

  • - x * maximumhely, ha d 2 f d x 2 0 az x= x * pontban.

  • - x * minimumhely, ha d 2 f d x 2 0 az x= x * pontban.

  • - x * inflexiós pont, ha d 2 f d x 2 =0 az x= x * pontban.

Az E.1. ábra egy olyan függvényt szemléltet, amely mindhárom típusú stacionárius ponttal rendelkezik (maximummal, minimummal és inflexiós ponttal is).

E.1. ábra - Egy függvény stacionárius pontjai

Egy függvény stacionárius pontjai

Ez a definíció kiterjeszthető többváltozós f ( x 1 , x 2 , , x d ) függvényre is, ebben az esetben az x * = [ x 1 * , x 2 * ,, x d * ] T stacionárius pont meghatározására szolgáló feltételek:

f x i | x i = x i * =0,    i=1,2,,d. (E.1)

Többváltozós függvények esetén azonban nehezebb a stacionárius pont típusát meghatározni. A nehézség abban áll, hogy minden lehetséges i,j indexpárra tekintenünk kell a 2 f d x i d x j parciális deriváltakat. Ezek összességét a Hesse mátrix adja meg:

H(x)=[ 2 f x 2 x 1 2 f x 2 x 2 2 f x 1 x d 2 f x 2 x 1 2 f x 2 x 2 2 f x 2 x d 2 f x d x 1 2 f x d x 2 2 f x d x d ]. (E.2)

  • A H Hesse mátrix pontosan akkor pozitív definit, ha x T Hx0 minden nemnulla x vektorra. Ha H( x * ) pozitív definit, akkor x * minimumhely.

  • A H Hesse mátrix pontosan akkor negatív definit, ha x T Hx0 minden nemnulla x vektorra. Ha H( x * ) negatív definit, akkor x * maximumhely.

  • A Hesse mátrix indefinit, ha x T Hx egyes vektorokra pozitív, másokra negatív. Egy indefinit Hesse mátrixhoz tartozó stacionárius pontot nyeregpontnak nevezünk.

E.1. Példa.

Tekintsük az f(x,y)=3 x 2 +2 y 3 2xy függvényt. Az E.2. ábra szemlélteti f(x,y) -t. Ebben az esetben a stacionárius pontot szolgáltató feltételek:

f x =6x2y=0

f y =6 y 2 2x=0, (E.3)

melyek megoldása x * = y * =0 vagy x * =1/27 , y * =1/9 .

E.2. ábra - Az f(x,y)=3 x 2 +2 y 3 2xy függvény grafikonja

Az f(x,y)=3 x 2 +2 y 3 −2xy függvény grafikonja

Az f függvény Hesse mátrixa

H(x,y)=[ 6 2 2 12y ]

Az x=y=0 pontban

H(0,0)=[ 6 2 2 0 ].

Mivel [x  y]  H(0,0)   [x  y] T =6 x 2 4xy=2x(3x2y) , és ez lehet mind pozitív, mind negatív, a Hesse mátrix indefinit, így (0,0) nyeregpont.

Az x=1/27 , y=1/9 pontban

H(1/27,1/9)=[ 6 2 2 12/9 ].

Mivel [x  y]  H(1/27,1/9)   [x  y] T =4 x 2 2xy+4 y 2 /3=4 (xy/4) 2 +13 y 2 /4 0 minden nemnulla x és y értékpárra, a Hesse mátrix pozitív definit. Ezért az (1/27,1/9) minimumhely. A minimum értéke 0,0014 .

Numerikus módszerek

Az előző szakaszban leírt megközelítés csak akkor használható, ha az (E.1.) egyenlet x * -ban analitikusan megoldható. Sok esetben ez nehezen -- vagy akár egyáltalán nem -- kivitelezhető. Ilyenkor numerikus módszerek használatára szorulunk. Egy függvény minimumának megtalálására szolgáló numerikus módszer többek között az aranymetszés-módszer, a Newton-módszer és a gradiens módszer. Bár az itt bemutatott módszereket az f(x) célfüggvény minimalizálására használjuk, természetesen ezen módszerek a maximum megkeresésére is alkalmasak, tekintve, hogy f(x) maximumát megtalálni annyit jelent, mint f(x) minimumát meghatározni.

Aranymetszésen alapuló keresés

Tekintsünk egy unimodális (tehát egy minimummal vagy maximummal rendelkező) eloszlást, mint például amilyet az E.3. ábra mutat. A minimumot a és b fogja közre. Az aranymetszésen alapuló eljárás iteratívan keres fokozatosan egyre kisebb olyan intervallumokat, amelyek tartalmazzák a minimumhelyet, egészen addig, míg az utolsó intervallum egészen kicsivé válik a stacionárius pont megközelítéséhez. Egy új intervallum meghatározásához két újabb pont, c és d szükséges. Ezeket úgy választjuk, hogy (a;c) és (d;b) (és így (a;d) és (c;b) ) egyenlő hosszúak legyenek. Legyen ca=bd=α(ba) és dc=β(ba) . Így

1= (bd)+(dc)+(ca) ba =α+β+α,

ebből pedig

β=12α. (E.4)

E.3. ábra - Példa egy unimodális függvényre

Példa egy unimodális függvényre

A hosszakat úgy kell megválasztani, hogy a rekurzió folytatható legyen, vagyis a következő feltétel teljesüljön:

dc bc = ca ba ,

vagy, ami ugyanez:

β 1α =α. (E.5)

Az (E.4) és (E.5) egyenletek együtt már megoldhatóak és a megoldásuk α=0,382 , β=0,236 . Az f(c) és f(d) értékeket összehasonlítva eldönthető, hogy a minimum az (a,d) vagy (c,b) intervallumban van-e. A minimumot tartalmazó intervallum aztán a következő iterációs lépés kiinduló intervalluma lesz, amíg az intervallum hossza elég kicsi nem lesz ahhoz, hogy kielégítően közelítse a minimumhelyet. alg:golden. algoritmus mutatja az eljárás lépéseit.

E.1. algoritmus Aranymetszésen alapuló keresés

1: c=a+0,382(ba)

2: while baε do

3: d=b0,382(ba)

4: if f(d)f(c) then

5: b=d

6: else

7: a=c , c=d

8: end if

9: end while

10: return c

A bemutatott eljárás nem tételez fel semmit az f(x) függvényről azon túl, hogy annak unimodálisnak és folytonosnak kell lennie [a,b] -ben. A lépések lineárisan közelítik a minimumot.

A Newton-módszer

Newton módszere az f(x) függvény négyzetes közelítésén alapul. Az f(x) -et x 0 körül Taylor-sorba fejtve a következő kifejezést kapjuk:

f(x)f( x 0 )+(x x 0 )f'( x 0 )+ (x x 0 ) 2 2 f''( x 0 ). (E.6)

Vegyük most a fenti deriváltját és tegyük egyenlővé nullával:

f'(x)=f'( x 0 )+(x x 0 )f''( x 0 )=0,

x= x 0 f'( x 0 ) f''( x 0 ) . (E.7)

Az (E.7.) egyenlet használható arra, hogy x -szel iteratívan közelítsük a minimumhelyet. Megmutatható, hogy a Newton-módszer -- ha használható -- másodrendben konvergens. Bizonyos esetekben előfordulhat, hogy az x 0 kezdőpont olyan távol van a minimumhelytől, hogy a módszer nem működik. A módszer leírása az E.2. algoritmusban található.

E.2. algoritmus A Newton-módszer

1: Legyen x 0 a kezdőpont

2: while |f'( x 0 )|ε do

3: x= x 0 f'( x 0 ) f''( x 0 )

4: x 0 =x

5: end while

6: return x

Newton módszere kiterjeszthető többváltozós függvényre is, ha az f'(x) deriváltat a f(x) gradiens operátorral helyettesítjük és a másodrendű f''(x) deriváltat pedig a H Hesse mátrixszal:

x=x H 1 f(x).

A Hesse mátrix inverzének meghatározása helyett könnyebb a

Hz=f(x)

egyenletet z -re megoldani. A stacionárius pont megtalálására szolgáló iterációs formulában ekkor az x=x+z helyettesítéssel kell élnünk.

Gradiens módszer

Newton módszere egy a különböző növekményes módszerek közül, melyek az

x=x+λg(x), (E.8)

egyenlettel lépésről lépésre meghatározott újabb x értékekkel egyre közelítik a stacionárius pontot. A g(x) határozza meg azt az irányt, mely felé a keresésnek haladnia kell, λ pedig megadja a lépés hosszát.

A gradiens módszer megköveteli, hogy az f(x) függvény differenciálható legyen, és a stacionárius pontot a következő egyenlettel közelíti:

x=xλf(x). (E.9)

Ennél a módszernél az x -et a legmeredekebb csökkenés irányába léptetjük. Az 5.4.2. szakasz leírja, hogyan használható ez a módszer egy mesterséges neurális háló súlyparamétereinek tanulásához. Az eljárás összegzése . algoritmus alatt található. Megjegyezzük, hogy ez az algoritmus nagyon hasonló . algoritmushoz, egyetlen különbség a léptetésben van.

E.2. algoritmus Gradiens módszer

1: Legyen x 0 a kezdőpont

2: while f( x 0 ) ε do

3: x= x 0 λf(x)

4: x 0 =x

5: end while

6: return x