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).
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
Hx≥0
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
Hx≤0
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
=6x−2y=0
∂f
∂y
=6 y
2
−2x=0,
(E.3)
melyek megoldása
x
* =
y *
=0
vagy
x
*
=1/27
,
y
*
=1/9
.
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(3x−2y)
, é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
(x−y/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
.
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
c−a=b−d=α(b−a)
és
d−c=β⋅(b−a)
. Így
1= (b−d)+(d−c)+(c−a)
b−a
=α+β+α,
ebből pedig
β=1−2α.
(E.4)
A hosszakat úgy kell megválasztani, hogy a rekurzió folytatható
legyen, vagyis a következő feltétel teljesüljön:
d−c
b−c
=
c−a
b−a
,
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.
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ó.
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.
