1

TÉCNICAS DE OTIMIZAÇÃO NÃOTÉCNICAS DE OTIMIZAÇÃO NÃO--LINEAR IRRESTRITA APLICADAS AO LINEAR IRRESTRITA APLICADAS AO TREINAMENTO DE REDES NEURAIS TREINAMENTO DE REDES NEURAIS

DE MÚLTIPLAS CAMADASDE MÚLTIPLAS CAMADAS

IA353 - Redes NeuraisLeandro Nunes de CastroFernando José Von Zuben

FEEC/Unicamp – 2001

Material Complementar ao Tópico 6 do Material Complementar ao Tópico 6 do Curso Curso IA353IA353 –– 1s20071s2007

2

Tópicos• Introdução (motivação)• Redes de múltiplas camadas• Algoritmo de retropropagação• Treinamento e critérios de parada• Superfícies de erro e mínimos locais• Abordagem (forma de análise)• Aproximação de funções• Algoritmos de otimização• Detalhes de implementação e variações• Taxas de aprendizagem globais• Algoritmos• Exemplos de aplicação

3

Motivação• Estímulo inicial• Potencial de aplicação na análise e síntese de problemas não-

lineares• Aplicação de redes MLP a problemas de mundo real

• Utilização de técnicas de otimização não-linear irrestrita para o treinamento de redes do tipo MLP

Garantia de convergência

Taxa de convergência

Teoria deotimização

Aproximação de funções

Teoria de análise numérica

Áreas de atuação científica a serem abrangidas 4

Redes de múltiplas camadasMLP - Multilayer Perceptron

… …

Camadade entrada

Primeiracamada

escondida

Segundacamada

escondida

Camadade saída

Propagação do sinal

Retro-propagação do erro

5

Abordagem matricial para o algoritmo de retro-propagação (backpropagation)

f1

W1

b1

∑u1

x

1f2

W2

b2

∑u2

y1

1f3

W3

b3

∑u3

y2

1

y3

f1. f2. f3.

Propagação dos sinais

π ππ 2 (y – s)

δ3δ2δ1

Retro-propagaçãodas sensibilidades

π π

(W2)T (W3)T

δ2 δ3

6

Treinamento e critérios de parada

• Treinamento:– Local (on-line): atualização imediatamente após a

apresentação de cada amostra.– Em lote (off-line, batch): atualização após a

apresentação de todo o conjunto de dados.

• Critérios de parada:– ||∇J(θ)|| < ε1

– ∆J(θ) < ε2

– J(θ) < ε3

– Outras funções de custo

2

7

Superfícies de erro e mínimos locais (I)

*

| |∇ J( θ ) || = 0

x0

ε d esejad o

m ín im oglob a l da

su p erfícied e e rro

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2-20

-15

-10

-5

0

5

10

Mínimo local

Mínimo global

Critérios de parada

Mínimos locais

8

Série de Taylor

...*)()(*)(21*)()(*)()(

*2

*+−∇−+−∇+=

==xxxxxxxxxx

xxxxTTT FFFF

T

nF

xF

xF

xF

∂∂

∂∂

∂∂

=∇ )()()()(21

xxxx K

T

nnn

n

n

Fx

Fxx

Fxx

Fxx

Fx

Fxx

Fxx

Fxx

Fx

F

∂∂

∂∂∂

∂∂∂

∂∂∂

∂∂

∂∂∂

∂∂∂

∂∂∂

∂∂

=∇

)()()(

)()()(

)()()(

)(

2

2

2

2

1

2

2

2

22

2

12

21

2

21

2

21

2

2

xxx

xxx

xxx

x

L

MMM

L

L

9

Aproximação em Taylor - Exemplo)cos()( xxF =

Expansão em Taylor para F(x) em torno do ponto x = 0:

L++−= 42241

211)( xxxF

-6 -3 0 3 6-2

-1

0

1

2

x

cos(x)

-6 -3 0 3 6-2

-1

0

1

2

F0(x)

F4(x)

F2(x)

10

Mínimos• Local: O ponto x* é um mínimo local de F(x) se existe um escalar δ > 0,tal que F(x*) < F(x + ∆x) para todo ∆x tal que 0 < ||∆x|| < δ.

• Global: O ponto x* é um mínimo global único de F(x) se F(x*) < F(x + ∆x) para todo ∆x ≠ 0.

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2-20

-15

-10

-5

0

5

10

Mínimo local

Mínimo global

11

Exemplos de comportamento local

12

1 1

x y

w01

w11

v01

w12

v02

v11

v21

Superfícies de erro e mínimos locais (II)

0 5 10 15 20 25 30 35 40 450.25

0.3

0.35

0.4

0.45

0.5

0.55

0.6

0.65

0.7

0.75

Função a ser aproximada Rede para aproximação

3

13

-5 0 5 10 15-5

0

5

10

15

Superfícies de erro e mínimos locais (III)

-50

510

15

-5

0

510

150

2

4

6

8

10 Vales

Platô

Superfície do erro quadrático e seu contorno em relação aos pesos v11 e w11

14

Superfícies de erro e mínimos locais (IV)

-10 -8 -6 -4 -2 0 2 4 6 8 10-10

-8

-6

-4

-2

0

2

4

6

8

10

-10-5

05

10

-10

-5

05

100

0.5

1

1.5

Mínimo global Mínimo local

Superfície do erro quadrático e seu contorno em relação aos limiares v01 e w01

15

Abordagem

• Representar o treinamento sob a forma de aproximação de funções minimização de um funcional de erro (J)

• Aproximação quadrática do funcional J (Taylor)

• Objetivo: • Processo iterativo de solução:

)θθ)(θ()θθ()θθ()θ()θ()θ( 2ii

Tii

Tiiquad JJJJ −∇−+−∇+=

)θ(J∇

)θ(2J∇

vetor gradientematriz hessiana

0,αθθ 1 ≥+=+ iiiii d

)θ(minarg*θθ

JPℜ∈

=

16

• Aproximar: g(.): X ⊂ ℜm → ℜr

• Modelo: :X × ℜP → ℜr, onde θ ∈ ℜP (P finito)

• Dados: amostrados da forma

• θ* ∈ ℜP tal que dist(g(.), ) ≤ dist(g(.), ), para todo θ ∈ ℜP

• Nível de aproximação:

• Otimização:

• Erros:– representação (bias)– generalização (variância)– otimização

Aproximação de funções

( ){ }Nlll 1, =sx lll g ε+= )(xs

)θ(.,g

)θ(.,g*)θ(.,g

( )∑=

−=N

lgg

NJ

1

2)θ,(ˆ)(1)θ( xx

)θ(minarg*θθ

JPℜ∈

=

17

Algoritmos de otimização• Algoritmo padrão (BP)• Método do gradiente (GRAD)• Método de Newton (MN)• Método de Levenberg-Marquardt (LM)• Método do gradiente conjugado (GC)• Método de Fletcher & Reeves (FR)• Método de Polak-Ribière (PR)• Gradiente conjugado escalonado (SCG)• Davidon-Fletcher-Powell (DFP)• Broyden-Fletcher-Goldfarb-Shanno (BFGS)• One-Step Secant (OSS)

1a ordem

2a ordem

2a ordem (grad. conjugado)

2a ordem (quase-Newton)

2a ordem

18

Algoritmos de otimização

ESTRATÉGIAS DE TREINAMENTO

SEM DIFERENCIAÇÃO 1a ORDEM 2a ORDEM EMPÍRICOS

GA SA BP GRAD CG QNN-LM QP MOD.

SCG FR PR DFP BFGS

OSS

4

19

• Algoritmo padrão (BP)– passo fixo

Métodos de 1a ordem (I)

• Método do gradiente (GRAD)– Busca simples do passo

0,θβ.α.θθ 11 ≥∆++= −+ iiiii d

)θ()θ(

JJ

∇∇

−=d

momento

)θ()θ(αθθ 1

i

iiii J

J∇∇

−=+

20

flops/iteração Memória paralelizabilidade

BP ∝ (N l) ∝ (2P + N) Boa

GRAD ∝ (N l + P) ∝ (2P + N) Boa

NM ∝ (NP + 3P2) ∝ (2P + N + P2) Pobre

LM ∝ (NP + 2P2) ∝ (2P + N + P2) Pobre

DFP ∝ (NP + P2) ∝ (2P + N + P2) Pobre

BFGS ∝ (NP + P2) ∝ (2P + N + P2) Pobre

OSS ∝ (NP + 2P) ∝ (3P + N) Média

PR ∝ (NP + 2P) ∝ (3P + N) Média

FR ∝ (NP + 2P) ∝ (3P + N) Média

SCGM ∝ (NP + P) ∝ (3P + N) Média

QUICK ∝ (NP + 2P) ∝ (3P + N ) Média

Complexidade ComputacionalP: graus de liberdade do modelo l: número de unidades naN: número de amostras camada intermediária

21

Detalhes de implementação/Variações• Os métodos de segunda ordem (QN & GC) foram

projetados para problemas quadráticos

• Momento de segunda ordem:

• Variação do ganho da função de ativação:

• Normalização dos dados de entrada:

Busca unidimensional

Reinicializaçãodo algoritmo

0,θγθβαθθ 211 ≥∆+∆++= −−+ iiiiii d3

1βγ −=

γ tanh(βx)xe

xf β1γ)( −+

=

i

inini

xxx

σ,

,−

= ∑ == N

n nii xN

x 1 ,1

∑ = −−

= Nn ninii xx

N 12

,, )(1

1σ

22

• Minimizar:• Mínimo: f (2, 1) = 0• Ponto inicial: (x1, x2) = (0, 0)• Estratégias:

– método do gradiente (GRAD)– método de Newton (MN)– método de Davidon-Fletcher-Powell (DFP)– método de gradiente conjugado (GC)

Algoritmos de otimização não-linear irrestrita

Exemplo 2: Propriedades de convergência2

214

121 )2()2(),( xxxxxf −+−=

23

0 1 2 3 4 50

1

2

3

4

5

X1

X2

0 1 2 3 40

0.5

1

1.5

2

2.5

3

3.5

4

X1

X2

0 1 2 3 40

0.5

1

1.5

2

2.5

3

3.5

4

X1

X2

0 1 2 3 4 5 60

1

2

3

4

5

6

X1

X2

Algoritmos de otimização

(139)GRAD

(1)MN

(9)GC

(13)DFP

24

• Determinação da taxa• Busca inexata

– simples

Taxas de Aprendizagem Globais (I)

TAX AS DE APRE NDIZ AGEM G LOB AIS

DETERM IN AÇÃ O(FIXA/D E C R E S CE NT E )

BUSC A

SIM PLES INTERV ALO DEINCERTE ZAS

M INIM IZAÇÃODA FU NÇ ÃO

• Busca exata– método de Fibonacci– método da Seção Áurea– método da Falsa Posição

5

25

• Garantia de ajustes minimizantes• Encontrar um valor ótimo para αi ∈ (0, ]• Subproblema: J(θi + αidi)• Busca unidimensional: d ∈ ℜP fixo

-10-5

05

10

-10

-5

05

100

0.5

1

1.5

Taxas de Aprendizagem Globais (II)

α

]α,0(α ∈imin

26

1. iai t αα = ; )θ()θ(αθθ 1

i

iii

pi J

J∇∇

−=+; calcule ( )p

iJ 1θ +

2. Enquanto ( )piJ 1θ + ≥ J(θi) faça:

2.1. iri t αα =

2.2. )θ()θ(αθθ 1

i

iii

pi J

J∇∇

−=+

3. pii θθ ←

4. Teste a condição de parada.

Algoritmos• Busca Simples

• Falsa posição1. Escolha um valor arbitrário para dN (critério de parada)

2. Enquanto i

ii

θθ- θ 1−

≥ dN faça:

2.1. )θ()θ(

θθ).θ(θθ1

11

ii

iiiii JJ

J∇−∇

−∇−=

−

−+

3. Teste a condição de parada

27

Taxas de Aprendizagem Globais (III)Exemplo 3: Busca simples

0 5 10 15 20 25 30 350

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4Taxa de Aprendizagem

Épocas

fAlfa

28

Algoritmos - Seção Áurea1. (a1, b1) - intervalo inicial de incertezas

2. Escolha um valor arbitrário para dN (critério de parada)

3. α = 618.02

15=

− - razão áurea

4. ( )( )1111 α1λ aba −−+= e ( )1111 αµ aba −+=

5. J(λ1) e J(µ1)

6. Enquanto 2- 1 1 ba

≥ dN faça:

6.1. Se J(λi) > J(µi), vá para 6.1.1; e se J(λi) ≤ J(µi), vá para 6.1.2

6.1.1. Faça:

• ai+1 = λi e bi+1 = bi

• λi+1 = µi e ( )1111 αµ ++++ −+= iiii aba

• J(µi+1)

6.1.2. Faça:

• ai+1 = ai e bi+1 = µi

• µi+1 = λi e ( )( )1111 α1λ ++++ −−+= iiii aba

• J(λi+1)

7. Teste a condição de parada

29

Taxas de Aprendizagem Globais (IV)

Exemplo 4: Redução do intervalo de incertezas

( ) ( )2214

121 22),( xxxxxf −+−=

• Problema: min f(xi + αidi) s.a. α ∈ (0, 1]• Onde:• Mínimo: f (2, 1) = 0• Ponto inicial: (x1, x2) = (0, 0) e d = [1, -1]• Estratégias:

– método da Seção Áurea (GOLD)– método de Fibonacci (FIB)– método da Falsa Posição (FP)

30

Taxas de Aprendizagem Globais (V)

Exemplo 4:

0 1 2 3 4-1

0

1

2

3

4

5

6

7

8

Pontos no intervalo

Valor

da

fun

ção

Avaliações

0 1 2 3 4-1

0

1

2

3

4

5

6

7

8

Pontos no intervalo

Valor

da

fun

ção

Avaliações

0 1 2 3 4

0

5

10

15

20

Pontos no intervalo

Valor

da

fun

ção

Avaliações(20)Fibonacci

(20)Seção áurea

(6)Falsa posição

6

31

Exemplo – 2 entradasAtualização em lote: 625 amostras

npEQMSSESSEnp

EQM ..1 2=→=

32

ÉPOCAS ||∇J(θ)|| T(seg.) flops × 106

BP 1083 1.1706 208.25 369.99

GRAD 408 1.3187 82.26 155.18

FR 89 6.9876 94.01 168.64

PR 95 4.1929 108.31 182.46

OSS 87 6.3663 101.60 170.36

SCGM 35 7.3035 47.77 96.47

DFP 57 6.7290 94.01 168.64

BFGS 47 4.5784 50.20 99.86

Parâmetros:nh = 10; minerr = 0.64; maxep = 1000; val = 0.5;dn = 0.001; cm = 0.9;

Exemplo – 2 entradas

33

0

50

100

150

200

250

Tempo (seg.)

Exemplo – 2 entradas

0

50

100

150

200250

300

350

400

Flops(xe6)

BPGRADFRPROSSSCGMDFPBFGS

34

Exemplo – 2 entradas

0 20 40 60 80 100

100

101

102

103

104SSE

Epochs

GRAD

BPM

PR

FR

BFGS

DFP

SCGM

OSS

Legenda:

Comportamento do SSE (soma dos erros quadráticos)

35

Referências (I)• Barnard, E., “Optimization for Training Neural Nets”, IEEE Trans. on Neural

Networks, vol. 3, n° 2, 1992.• Battiti, R., “First- and Second-Order Methods for Learning: Between Steepest

Descent and Newton’s Method”, Neural Computation, vol. 4, pp. 141-166, 1992.• Battiti, R., “Learning with First, Second, and no Derivatives: A Case Study in

High Energy Physics”, Neurocomputing, NEUCOM 270, vol. 6, pp. 181-206, 1994, URL: ftp:// ftp.cis.ohio-state.edu/pub/neuroprose/ battiti.neuro-hep.ps.Z.

• Castro, L.N., “Análise e Síntese de Estratégias de Aprendizagem para redes Neurais Artificiais”, Tese de Mestrado, FEEC/UNICAMP, Outubro de 1998.

• Fahlman, S.E., “An Empirical Study of Learning Speed in Back-PropagationNetworks”, Technical Report, September 1988, URL: ftp://archive.cis.ohio-state.edu/pub/neuroprose/ fahlman.quickprop-tr.ps.Z

• Fiesler, E., “Comparing Parameterless Learning Rate Adaptation Methods,” Proceedings of the ICNN’97, pp. 1082-1087, 1997.

• Finschi, L., “An Implementation of the Levenberg-Marquardt Algorithm”,Technical Report, April 1996, URL: http://www.ifor.math.ethz.ch/staff/finschi/Papers/ LevMar.ps.gz.

• Groot, C. de & Würtz, D., “Plain Backpropagation and Advanced OptimizationAlgorithms: A Comparative Study”, NEUCOM 291, vol. 6, pp.153-161, 1994. 36

• Haygan, M.T., “Training Feedforward Networks with the MarquardtAlgorithm”, IEEE Trans. on Neural Networks, vol. 5, n° 6, pp. 989-993, 1994.

• Jacobs, R.A., “Increased Rates of Convergence Through Learning Rate Adaptation”, Neural Networks, vol. 1, pp. 295-307, 1988, URL: http://www.cs.umass.edu/Dienst/UI/2.0/Describe/ncstrl.umassa_cs %2fUM-CS-1987-117

• Jondarr, C.G.H., “Back Propagation Family Album”, Technical ReportC/TR96-5, 1996, URL: ftp://ftp.mpce.mq.edu.au/pub/comp/techreports/96C005.gibb.ps.

• Joost, M. & Schiffman, W., “Speeding Up Backpropagation Algorithms byUsing Cross-Entropy Combined With Pattern Normalization”, InternationalJournal of Uncertainty, Fuzzyness and Knowledge-Based Systems, 1993, URL: http://www.uni-koblenz.de/~schiff/ cenprop_eng.ps.gz

• Moller, M.F., “A Scaled Conjugate Gradient Algorithm for Fast SupervisedLearning”, Neural Networks, vol. 6, pp. 525-533, 1993.

• Pearlmutter, B.A., “Fast Exact Calculation by the Hessian”, Neural Computation, vol. 6, pp. 147-160, 1994, URL: ftp://ftp.cis.ohio-state.edu/pub/neuroprose/pearlmutter. hessian.ps.Z.

Referências (II)

7

37

• Shepherd, A.J., “Second-Order Methods for Neural Networks – Fast andReliable Methods for Multi-Layer Perceptrons”, Springer, 1997.

• Shewchuk, J.R., “An Introduction to the Conjugate Gradient Method Withoutthe Agonizing Pain”, Technical Report, 1994, URL: http://www.cs.cmu.edu/ afs/cs/project/quake/public/papers/painless-conjugate-gradient.ps.

• Schiffman, W., Joost, M., & Werner, R., “Optimization of theBackpropagation Algorithm for Training Multilayer Perceptrons”, TechnicalReport, 1994, URL: ftp://archive.cis.ohio-state.edu/pub/neuroprose/schiff. bp_speedup.ps.Z.

• Stäger, F., & Agarwal, M., “Three Methods to Speed up the Training of Feedforward and Feedback Perceptrons”, Neural Networks, vol. 10, n° 8, pp. 1435-1443, 1997.

• Van Der Smagt, P., P, “Minimization Methods for Training FeedforwardNeural networks,” Neural Networks, vol 1, n° 7, 1994, URL: http://www.op.dlr.de/~smagt/ papers/SmaTB92.ps.gz

• Von Zuben, F.J., “Modelos Paramétricos e Não-Paramétricos de Redes neurais Artificiais e Aplicações”, Tese de Doutorado, Faculdade de Engenharia Elétrica, Unicamp, 1996.

Referências (III)