Sztuczne sieci neuronowe

Małgorzata Kr towska

Katedra Oprogramowania

e-mail: [e-mail]

Wykład 4: Algorytmy optymalizacji

Sztuczne sieci neuronowe

2

Plan wykładu

• Algorytmy gradientowe optymalizacji

– Algorytm najwi kszego spadku
– Algorytm zmiennej metryki
– Algorytm gradientów sprz onych

• Algorytmy doboru współczynnika uczenia

– adaptacyjny dobór współczynnika uczenia
– dobór współczynnika przez minimalizacj kierunkow
– reguła delta-bar-delta
– metoda gradientów sprz onych z regularyzacj

• Algorytmy heurystyczne

– algorytm Quickprop
– algorytm RPROP

Sztuczne sieci neuronowe

3

Uczenie z nauczycielem

• Minimalizacja funkcji celu E

• Zakładaj c ci gł funkcj aktywacji, minimalizacja odbywa si

metodami gradientowymi

• W ka dym kroku uczenia wyznacza si tzw. kierunek minimalizacji p

(W(k))

• Korekcja wag odbywa si według wzoru:

gdzie

η jest współczynnikiem uczenia z przedziału [0, 1].

))

(

(

)

(

)

1

(

k

W

p

k

W

k

W

η

+

=

+

Sztuczne sieci neuronowe

4

Algorytmy gradientowe optymalizacji

Algorytmy gradientowe bazuj na rozwini ciu w szereg Taylora funkcji

celu E(

W) w najbli szym s siedztwie znanego rozwi zania W=

[w

1

,w

2

, ..., w

n

]

T

(na starcie algorytmu jest to punkt pocz tkowy W

0

):

gdzie:

+

+

+

=

+

p

W

H

p

p

W

g

W

E

p

W

E

T

T

)

(

2

1

)]

(

[

)

(

)

(

T

n

W

E

W

E

W

E

E

W

g

∂

∂

∂

∂

∂

∂

=

∇

=

,

,

,

)

(

2

1

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

=

n

n

n

n

W

W

E

W

W

E

W

W

E

W

W

E

W

H

1

1

1

1

)

(

Sztuczne sieci neuronowe

5

Algorytmy gradientowe optymalizacji

• Punkt W=W

k

jest punktem optymalnym funkcji E(W), je li

– g(W

k

)=0

– hesjan H(W

k

) jest dodatnio okre lony

• W praktyce ( ze wzgl du na na sko czon dokładno oblicze ) zakłada

si , e punkt W

k

jest punktem optymalnym, je eli:

gdzie

τ przyj ta dokładno oblicze

(

)

(

)

(

)

)

(

1

)

(

1

)

(

1

)

(

)

(

3

1

1

k

k

k

k

k

k

k

k

W

E

W

g

W

W

W

W

E

W

E

W

E

+

≤

+

≤

−

+

≤

−

−

−

τ

τ

τ

Sztuczne sieci neuronowe

6

Ogólny algorytm optymalizacji

Zakładamy W

0

=W

k

• Test: je eli W

k

spełnia warunki testowe jest punktem optymalnym to

ko czymy obliczenia, w przeciwnym przypadku pkt. 2

• Wyznaczanie wektora kierunku poszukiwa p

k

w punkcie W

k

.

• Minimalizacja kierunkowa funkcji E(W) na kierunku p

k

w celu

wyznaczenia takiej warto ci

η

k

, aby E(W

k

+

η

k

p

k

) < E(W

k

)

• Wyznaczenie nowego rozwi zania W

k+1

=W

k

+

η

k

p

k

oraz odpowiadaj cej

mu warto ci E(W

k

), g(W

k

) ( i ew. H(W

k

)) i powrót do pkt 1.

Ró nice: wyznaczanie kierunku poszukiwa p oraz kroku

η.

Sztuczne sieci neuronowe

7

Algorytm najwi kszego spadku

Ograniczenie do liniowego przybli enia funkcji E(W) w najbli szym

s siedztwie znanego rozwi zania W:

aby E(W

k+1

)<E(W

k

) wystarczy aby [g(W

k

)]

T

p < 0

Wektor kierunkowy w metodzie najwi kszego spadku przyjmuje posta :

p

k

=-g(W

k

)

)

(

)]

(

[

)

(

)

(

2

h

O

p

W

g

W

E

p

W

E

T

+

+

=

+

Sztuczne sieci neuronowe

8

Algorytm najwi kszego spadku

• Podej cie klasyczne

• Metoda momentu

Uwagi:

– na płaskich odcinkach

(dla =0.9 oznacza to 10 krotne przyspieszenie procesu uczenia)

– pozwala na wyj cie z minimów lokalnych
– nale y kontrolowa warto E

k

k

k

W

W

W

∆

+

=

+1

k

k

p

W

η

=

∆

)

(

1

−

−

+

=

∆

k

K

k

k

W

W

p

W

α

η

k

k

p

W

α

η

−

=

∆

1

Sztuczne sieci neuronowe

9

Algorytm najwi kszego spadku

Wykres wpływu działania momentu na proces uczenia

• Metoda „weight decay”

zabezpiecza przez zbytnim wzrostem wag

k

k

k

W

p

W

β

η

−

=

∆

k

k

k

W

p

W

β

η

−

=

∆

Sztuczne sieci neuronowe

10

Algorytm zmiennej metryki (quasi-Newtona)

Kwadratowe przybli enie funkcji E(W) w s siedztwie znanego

rozwi zania W

k

:

kierunek p jest wyznaczony ze wzoru:

Problemy:

– wymóg dodatniej okre lono ci hesjanu w ka dym kroku

Rozwi zanie

– zastosowanie przybli enia hesjanu przy u yciu metody zmiennej metryki

)

(

)

(

2

1

)]

(

[

)

(

)

(

3

h

O

p

W

H

p

p

W

g

W

E

p

W

E

T

T

+

+

+

=

+

)

(

)]

(

[

1

k

k

k

W

g

W

H

p

−

−

=

Sztuczne sieci neuronowe

11

Algorytm zmiennej metryki (quasi-Newtona)

Przybli enie hesjanu polega na modyfikacji hesjanu z kroku poprzedniego

o pewn poprawk , która powoduje, e aktualna warto hesjanu G(W

k

)

przybli a krzywizn funkcji celu E zgodnie z zale no ci :

G(W

k

)(W

k

-W

k-1

)=g(W

k

)-g(W

k-1

)

Na podstawie powy szego zało enia mo na otrzyma wzory okre laj ce

hesjan w kroku k-tym:

gdzie s

k

=W

k

-W

k-1

;

r

k

=g(W

k

)-g(W

k-1

);

V

l

=[G(W

k

)]

-1

.

k

T
k

T
k

k

k

k

T

k

k

k

T
k

T

k

k

k

T
k

k

k

T

k

k

k

r

s

s

r

V

V

r

s

r

s

s

s

r

s

r

V

r

V

V

1

1

1

1

1

−

−

−

−

+

−

+

=

Sztuczne sieci neuronowe

12

Algorytm zmiennej metryki (quasi-Newtona)

• warto startowa V

0

=1

• pierwsza iteracja zgodnie z algorytmem najwi kszego spadku
• odtwarzana macierz hesjanu jest w ka dym kroku dodatnio okre lona

(st d g(W

k

)=0 odpowiada rozwi zaniu problemu optymalizacji)

• metoda uwa ana za jedn z najlepszych metod optymalizacji funkcji

wielu zmiennych

Wady:
• stosunkowo du a zło ono obliczeniowa (n

2

elementów hesjanu)

• du e wymagania co do pami ci przy przechowywaniu macierzy hesjanu

Sztuczne sieci neuronowe

13

Metoda gradientów sprz onych

• rezygnacja z bezpo redniej informacji o hesjanie
• nowy kierunek poszukiwa ma by ortogonalny i sprz ony z poprzednim

kierunkami p

0

, p

1

, ..., p

k-1

, st d:

co mo na upro ci do postaci:

współczynnik sprz enia (g

k

=g(W

k

)):

Zbiór wektorów p

i

jest wzajemnie sprz ony wzgl dem macierzy H, je eli

−

=

+

−

=

1

0

)

(

k

j

j

kj

k

k

p

W

g

p

β

1

1

)

(

−

−

+

−

=

k

k

k

k

p

W

g

p

β

1

1

1

1

)

(

−

−

−

−

−

=

k

T

k

k

k

T
k

k

g

g

g

g

g

β

j

i

Hp

p

j

T

i

≠

= ,

0

Sztuczne sieci neuronowe

14

Metoda gradientów sprz onych

• metoda mniej skuteczna od metody zmiennej metryki, ale bardziej

skuteczna ni metoda najwi kszego spadku

• stosuje si j do optymalizacji przy bardzo du ej liczbie zmiennych

• ze wzgl du na bł dy zaokr gle w trakcie zatraca si własno

ortogonalno ci mi dzy wektorami kierunków minimalizacji. Po

wykonaniu n iteracji przeprowadza si jej ponowny start ( w I kroku

zgodnie z algorytmem najwi kszego spadku)

Sztuczne sieci neuronowe

15

Metody doboru współczynnika uczenia

Po okre leniu wła ciwego kierunku p

k

minimalizacji, nale y dobra

odpowiedni warto współczynnika uczenia, aby nowy punkt W

k+1

le ał mo liwie najbli ej minimum funkcji E(W) na kierunku p

k

k

k

k

k

p

W

W

η

+

=

+1

Sztuczne sieci neuronowe

16

Stały współczynnik uczenia

• Stały współczynnik uczenia

– stosuje si głównie w poł czeniu z metod najwi kszego spadku
– sposób najmniej efektywny, gdy nie uzale nia warto ci współczynnika od

od wektora gradientu oraz kierunku poszukiwa

p w danej iteracji

– algorytm ma skłonno utykania w minimach lokalnych
– cz sto dobór współczynnika odbywa si oddzielnie dla ka dej warstwy,

przyjmuj c

gdzie n

i

liczba wej i-tego neuronu w warstwie

≤

i

n

1

min

η

Sztuczne sieci neuronowe

17

Adaptacyjny dobór współczynnika uczenia

• zmiany współczynnika uczenia dopasowuj si do aktualnych zmian

warto ci funkcji celu w czasie. Warto bł du

ε w i-tej iteracji:

okre la strategi zmian warto ci współczynnika uczenia.

• Przyspieszenie procesu uczenia uzyskuje si poprzez ci głe zwi kszanie

współczynnika

η sprawdzaj c jednocze nie czy nie zacznie wzrasta w

porównaniu z bł dem obliczonym przy poprzedniej warto ci

η

(

)

=

−

=

M

j

j

j

d

y

1

2

ε

Sztuczne sieci neuronowe

18

Adaptacyjny dobór współczynnika uczenia

Adaptacja współczynnika uczenia:

gdzie:
ε

i-1

,

ε

i

- bł d odpowiednio w (i-1)-szej iteracji oraz w i-tej iteracji

η

i-1

;

η

i

- współczynnik uczenia w kolejnych iteracjach

k

w

- dopuszczalny współczynnik wzrostu bł du

ρ

d

- współczynnik zmniejszania warto ci

ρ

i

- współczynnik zwi kszaj cy warto

Przykładowe warto ci współczynników: k

w

= 1,04;

ρ

d

=0.7;

ρ

i

= 1.05

≤

>

=

−

−

+

1

1

1

i

w

i

i

i

i

w

i

d

i

i

k

gdy

k

gdy

ε

ε

ρ

η

ε

ε

ρ

η

η

Sztuczne sieci neuronowe

19

Adaptacyjny dobór współczynnika uczenia

Wpływ adaptacyjnego doboru współczynnika uczenia na proces uczenia

Sztuczne sieci neuronowe

20

Dobór współczynnika uczenia przez

minimalizacj kierunkow

• Polega na minimalizacji kierunkowej funkcji celu na wyznaczonym

wcze niej kierunku p

k

.

• Cel: takie dobranie warto ci η

k

aby nowy punkt W

k+1

=W

k

+

η

k

p

k

odpowiadał minimum funkcji celu na danym kierunku

– Je eli η

k

odpowiada dokładnie minimum funkcji na danym kierunku p

k

to

pochodna kierunkowa w punkcie W

k+1

=W

k

+

η

k

p

k

musi by równa 0

• W praktyce wyznaczony punkt W

k+1

odpowiada tylko w przybli eniu

rzeczywistemu punktowi minimalnemu na danym kierunku.

Sztuczne sieci neuronowe

21

Dobór współczynnika uczenia przez

minimalizacj kierunkow

W celu „regulacji” dokładno ci wyznaczenia współczynnika uczenia

wprowadza si współczynnik 0<

γ

2

<1, który stanowi ułamek pochodnej

funkcji celu na kierunku p

k

w punkcie wyj ciowym W

k

.

Algorytm pozwalaj cy na wyznaczenie optymalnej warto ci

η

k

przeprowadza si dopóty, dopóki spełnione s nast puj ce warunki:

oraz

przyj cie 0

≤ γ

1

≤ γ

2

< 1 gwarantuje jednoczesne spełnienie obu tych

warunków.

[

]

[

]

k

T

k

k

T

k

k

k

p

W

g

p

p

W

g

)

(

)

(

2

γ

η

≥

+

[

]

k

T

k

k

k

k

k

k

p

W

g

W

E

p

W

E

)

(

)

(

)

(

1

η

γ

η

≥

−

+

Sztuczne sieci neuronowe

22

Minimalizacja kierunkowa

• Metody bezgradientowe

– informacje o warto ciach funkcji celu
– wyznaczanie minimum poprzez kolejne podziały zało onego na wst pie

zakresu warto ci wektora W

• Metody gradientowe

– wykorzystuj zarówno warto funkcji jak te jej pochodn wzdłu

wektora kierunku p

k

.

– znaczne przyspieszenie wyznaczenia minimum na danym kierunku

informacja o kierunku spadku)

Sztuczne sieci neuronowe

23

Przykład metody bezgradientowej

• Metoda bazuje na aproksymacji funkcji celu na kierunku p

k

, a nast pnie

wyznacza minimum otrzymanej w ten sposób funkcji jednej zmiennej

η

• Wielomian aproksymuj cy:

P(

η)=a

2

η

2

+a

1

η +a

0

gdzie a

2

,a

1

,a

0

- współczynniki wielomianu okre lane w ka dym cyklu

optymalizacyjnym

• Wyznaczanie współczynników wielomianu

– wybór trzech dowolnych punktów W

1

, W

2

, W

3

le cych na kierunku p

k

, tzn.

W

1

=W+

η

1

p

k

;

W

2

=W+

η

2

p

k

;

W

3

=W+

η

3

p

k

;

(W - poprzednie rozwi zanie);

– E

1

=E(W

1

); E

2

=E(W

2

); E

3

=E(W

3

); wówczas

P(

η

1

)= E

1

; P(

η

2

)= E

2

; P(

η

3

)= E

3

;

– Rozwi zuj c układ równa otrzymujemy współczynniki wielomianu

• Porównuj c pochodn wielomianu do zera otrzymujemy

η

mi

n

=(-a

1

/2a

2

)

• Po okre leniu s sprawdzane warunki. Je li algorytm ma by kontynuowany to

wybiera si kolejne punkty le ce na kierunku p

k

w pobli u punktu W+

η

mi

n

p

k

.

Sztuczne sieci neuronowe

24

Inne metody doboru współczynnika uczenia

• Reguła delta-bar-delta

– jest metod adaptacyjn opracowan dla kwadratowej definicji funkcji celu

i metody najwi kszego spadku

– ka dej wadze W

ij

jest przyporz dkowany indywidualnie dobrany

współczynnik uczenia

– Wada: du a zło ono obliczeniowa
– Zaleta: przyspieszenie procesu uczenia i zwi kszenie prawdopodobie stwa

osi gni cia minimum globalnego

• Metoda gradientów sprz onych z regularyzacj

– odmiana zwykłej metody gradientów sprz onych ł cz c jednocze nie

wyznaczanie kierunku p oraz optymalnego kroku

Sztuczne sieci neuronowe

25

Algorytm Quickprop

• odmiana algorytmu gradientowego zawiera elementy metody

newtonowskiej i wiedzy heurystycznej

• zawiera elementy zabezpieczaj ce przez utkni ciem w płytkim

minimum lokalnym (ze wzgl du na nasycenie neuronu)

• Zmiana wagi w k-tym kroku

• Zalety: szybka zbie no dla wi kszo ci trudnych problemów
• kilkusetkrotne przyspieszenie procesu uczenia (w porównaniu z

algorytmem najwi kszego spadku)

• małe prawdopodobie stwo utkni cia w minimum lokalnym

)

1

(

)

(

))

(

(

)

(

−

∆

+

+

∂

∂

−

=

∆

k

W

k

W

W

k

W

E

k

W

ij

k

ij

ij

ij

k

ij

α

γ

η

Sztuczne sieci neuronowe

26

Algorytm RPROP

(ang. Resilent backPROPagation)

gdzie

– a=1.2; b=0.5
η

min

;

η

max

- minimalna i maksymalna warto współczynnika uczenia (10

-6

; 50)

Zalety

– przyspieszenie procesu uczenia w obszarach gdzie nachylenie funkcji celu

jest niewielkie

∂

∂

−

=

∆

ij

k

ij

ij

W

k

W

E

k

W

))

(

(

sgn

)

(

)

(

η

(

)

(

)

<

−

>

−

=

−

−

−

h

przypadkac

h

pozostalyc

w

k

S

k

S

dla

b

k

S

k

S

dla

a

k

ij

ij

ij

k

ij

ij

ij

k

ij

k

ij

)

1

(

min

)

1

(

max

)

1

(

)

(

0

)

1

(

)

(

,

max

0

)

1

(

)

(

,

min

η

η

η

η

η

η

ij

ij

W

k

W

E

k

S

∂

∂

=

))

(

(

)

(