40
Perceptron Ruy Luiz Milidiú

Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Embed Size (px)

Citation preview

Page 1: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Perceptron

Ruy Luiz Milidiú

Page 2: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Resumo ObjetivoExaminar o modelo do perceptron,

seu algoritmo de aprendizado e limitações

Sumário O Perceptron Aprendizado Limitações

Page 3: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

O Perceptron Rosenblatt

50’s

Page 4: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

O Perceptron

“oito”

Page 5: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

O Perceptron

“dois”

Page 6: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

O Perceptron de Rosenblat Exemplos

(x1, y1), (x2, y2), … , (xn, yn) xi {0,1}n , yi {0,1}

Neurônio Não-linear a= w0 . 1 + w1. x ativação linear ŷ = f(a) disparo não-linear w0 , w1 = ?

Desempenho E Erro = (ŷ1 – y1)2 + … + (ŷn – yn)2

Page 7: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Disparo por Limiar Se a < 0 w0 limiar

f(a) = 0 não dispara

Se a 0 w0 limiar f(a) = 1 dispara

f(a) = [sign(a) + 1]/2

Page 8: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Disparo por Limiar

0

0.5

1

-7 -5 -3 -1 1 3 5 7

Page 9: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Disparo Sigmóide

0

0.5

1

-7 -5 -3 -1 1 3 5 7

Page 10: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Disparo Sigmóide f(a) = 1 / (1+exp(-k.a)) f(a) 0 f(-) = 0 f(0) = ½ f() = 1 f’(a) = k.exp(-k.a) / (1+exp(-k.a))2

f’(a) = k.f(a).[1-f(a)] f’(a) 0 f’(0) = k/4

f’’(a) = k2.f(a).[1-f(a)].[1-2.f(a)] f’’(0) = k2.f(0).[1-f(0)].[1-2.1/2] = 0 inflexão

Page 11: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Disparo Sigmóidef(a) = 1 / (1+exp(-k.a))

f’(a) = k.f(a).[1-f(a)]

f’’(a) = k2.f(a).[1-f(a)].[1-2.f(a)]

Page 12: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Aprendizado para Sigmóide

Minimizar Erro … E(w) = (ŷ1 – y1)2 + … + (ŷn – yn)2

E(w) = [f(w.xi) – yi]2

Diferenciando…E/w = 2. [f(w.xi) – yi].f’(w.xi).xi

E/w = 2.k. [f(w.xi) – yi].f(w.xi).[1 – f(w.xi)].xi

wn = wn-1 + .[yn- f(wn-1.xi)].f(wn-1.xi).[1 – f(wn-1.xi)].xnT

Page 13: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Da Sigmóide para a Limiar

Minimizar Erro … E(w) = (ŷ1 – y1)2 + … + (ŷn – yn)2

E(w) = [f(w.xi) – yi]2

Diferenciando…E/w = 2. [f(w.xi) – yi].f’(w.xi).xi

f’(w.xi) ≈ 1

wn = wn-1 + .[yn- f(wn-1.xi)].f(wn-1.xi).[1 – f(wn-1.xi)].xnT

Page 14: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Da Sigmóide para a Limiar

Minimizar Erro … E(w) = (ŷ1 – y1)2 + … + (ŷn – yn)2

E(w) = [f(w.xi) – yi]2

Diferenciando…E/w = 2. [f(w.xi) – yi].f’(w.xi).xi

f’(w.xi) ≈ 1

wn = wn-1 + .[yn- f(wn-1.xi)].f(wn-1.xi).[1 – f(wn-1.xi)].xnT

Page 15: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Aprendizado para Limiar

Minimizar Erro … E(w) = (ŷ1 – y1)2 + … + (ŷn – yn)2

E(w) = [f(w.xi) – yi]2

Regra do Perceptron…

wn = wn-1 + [yn- f(wn-1.xn)].xnT

Page 16: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Regra do Perceptron

wn = wn-1 + [yn- f(wn-1.xn)].xnT

yn = f(wn-1.xn)wn = wn-1 + 0.xn

T

wn = wn-1

yn = 0 e f(wn-1.xn) = 1 yn = 1 e f(wn-1.xn) = 0wn = wn-1 + (-1).xn

T wn = wn-1 + (1).xnT

Page 17: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Binary Classification Two classes

Y or N 0 or 1 -1 or 1 or

Page 18: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Linear Classifier

w.x + b = 0

w.x + b < 0

w.x + b > 0

y(x) = sign(wT.x + b)

Page 19: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Linear Separators Training instances

x m

y {-1, 1}

Hyperplane <w,x> = 0 w1x1 + w2x2 … + wmxm = 0

w m

Decision functionf(x) = sign(<w,x>)

Page 20: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Algoritmo do Perceptronw 0error TRUEwhile error

error FALSEfor i := 1 to n

if yi.<w,xi> 0 erradow w + yi.xi

error TRUE

Page 21: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Convergência Perceptron Disparo por limiar Aprendizado

Regra do Perceptron Teorema do Perceptron

Separabilidade Linear Teorema

Page 22: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Separabilidade linear

1 1

11

1 1 1

1 111

11

1

1 00

0000

0000

0

0

0

00

0

0

0

0

Page 23: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

OR1

10

1

Page 24: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

AND1

00

0

Page 25: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Learningexampl

ex0 x1 x2 y

I -1 0 0 0

II -1 0 1 0

III -1 1 0 0

IV -1 1 1 1

Page 26: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Round 1ŷ w0 w1 w2 x0 x1 x2 y 0 1 2

1 0 0 0 -1 0 0 0 1 0 00 1 0 0 -1 0 1 00 1 0 0 -1 1 0 00 1 0 0 -1 1 1 1 -1 1 1

0 1 1

Page 27: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Round 2ŷ w0 w1 w2 x0 x1 x2 y 0 1 2

0 0 1 1 -1 0 0 01 0 1 1 -1 0 1 0 1 0 -11 1 1 0 -1 1 0 0 1 -1 00 2 0 0 -1 1 1 1 -1 1 1

1 1 1

Page 28: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Round 3ŷ w0 w1 w2 x0 x1 x2 y 0 1 2

0 1 1 1 -1 0 0 01 1 1 1 -1 0 1 0 1 0 -10 2 1 0 -1 1 0 00 2 1 0 -1 1 1 1 -1 1 1

1 2 1

Page 29: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Round 4ŷ w0 w1 w2 x0 x1 x2 y 0 1 2

0 1 2 1 -1 0 0 01 1 2 1 -1 0 1 0 1 0 -11 2 2 0 -1 1 0 0 1 -1 00 3 1 0 -1 1 1 1 -1 1 1

2 2 1

Page 30: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Round 5ŷ w0 w1 w2 x0 x1 x2 y 0 1 2

0 2 2 1 -1 0 0 00 2 2 1 -1 0 1 01 2 2 1 -1 1 0 0 1 -1 00 3 1 1 -1 1 1 1 -1 1 1

2 2 2

Page 31: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Round 6 and 6.5ŷ w0 w1 w2 x0 x1 x2 y 0 1 2

0 2 2 2 -1 0 0 01 2 2 2 -1 0 1 0 1 0 -10 3 2 1 -1 1 0 01 3 2 1 -1 1 1 10 3 2 1 -1 0 0 00 3 2 1 -1 0 1 0

Page 32: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Teorema do Perceptron w* define um separador linear

|w*| = 1 y.(w*.x) y=sign(w*.x)

|x| ≤ Rentão

cos(n) = w*.wn / |wn| n . / R

n R2 / 2

Page 33: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Teorema do Perceptron

1 1

11

1 1 1

1 111

11

1

1 00

0000

0000

0

0

0

00

0

0

0

0

R

w

Page 34: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

w*.wn

w*.(wn-1 + yn.xn)w*.wn-1 + yn.w*.xn

w*.wn-1 + sign(w*.xn).w*.xn

w*.wn-1 + |w*.xn| w*.wn-1 + w*.0 + n.

w*.wn n.

Page 35: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

wn.wn

(wn-1 + yn.xn)T.(wn-1 + yn.xn)T

wn-1T.wn-1 + 2.yn.(wn-1

T.xn ) + yn2.xn

T.xnwn-1

T.wn-1 + 2.yn.(wn-1T.xn ) + xn

T.xn wn-1

T.wn-1 + xnT.xn

wn-1T.wn-1 + R2

0.0 + n.R2 = n.R2

|wn| R.n

Page 36: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

cos()

n . / R ≤ w*.wn / |wn|

por Cauchy-Schwarz n . / R ≤ |w*|.|wn| / |wn| = 1.|wn|/|wn| n . / R ≤ 1

n R2 / 2

Page 37: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Limitações Minsky & Papert 69

XOR Padrões de conectividade

Aprendizado p/multicamadas não disponível

Lacuna de 20 ano$$$$ …

Page 38: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

XOR1

01

0

Page 39: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

Padrões de Conectividade

L + C + R < T

L’ + C + R > T

L + C + R’ > T

L’ + C + R’ > L + C + R’ > T

0

1

1

1

Page 40: Perceptron Ruy Luiz Milidiú Resumo Objetivo Examinar o modelo do perceptron, seu algoritmo de aprendizado e limitações Sumário O Perceptron Aprendizado

XORy = XOR(x1, x2)

y = x1+x2 – 2.x1.x2

quadrática

duas camadas

aprendizado?

-0.5

-1.5

-0.5

1

-11

1

1

1

X1

X2

Y