Introdução àsRedes Neurais Artificiais

Perceptrons de Camada Única

Prof. João Marcos Meirelles da Silva

www.professores.uff.br/jmarcos

Departamento de Engenharia de Telecomunicações

Escola de Engenharia

Universidade Federal Fluminense

Prof. João Marcos Meirelles da Silva – p. 1/35

Créditos autorais

Este curso e estes slides são parcialmente adaptados da bibliografiacitada e das aulas do professor Luiz Pereira Calôba - COPPE/UFRJ

www.lps.ufrj.br

Prof. João Marcos Meirelles da Silva – p. 2/35

Sumário

• Introdução

• Modelo do Perceptron

• Classes Linearmente Separáveis

• Hiperplano de Decisão

• Treinamento do Perceptron

• Teorema de Convergência

• Algoritmo de Treinamento

• Exemplo

Prof. João Marcos Meirelles da Silva – p. 3/35

Introdução

• McCulloch e Pitts (1943) → Modelo do neurônio;

• Rosenblatt (1958) → Perceptron (aprendizado supervisionado)

• Objetivo → Classificar corretamente o conjunto de estímulosexternos (padrões) x = [x1, x2, . . . , xm]T em uma de duasclasses possíveis: C1 ou C2.

x ∈

C1, se y = +1

C2, se y = −1

Prof. João Marcos Meirelles da Silva – p. 4/35

Modelo do Perceptron

Figure 1: Neurônio de McCulloch e Pitts.

v =

m∑

i=1

ωixi + b, ϕ(v) = sign(v) (1)

Prof. João Marcos Meirelles da Silva – p. 5/35

Classes Linearmente Separáveis

Perceptrons de camada única são bons para resolver problemas declassificação onde as classes são linearmente separáveis.

Figura 2: Definição de Separabilidade.

Prof. João Marcos Meirelles da Silva – p. 6/35

Hiperplano de Decisão

Haverá então duas regiões de decisão separadas por um hiperplano,chamado de hiperplano de decisão, definido por:

m∑

i=2

ωixi + b = 0 (2)

Prof. João Marcos Meirelles da Silva – p. 7/35

Hiperplano de Decisão

Figura 3: Hiperplano de decisão.

Prof. João Marcos Meirelles da Silva – p. 8/35

Treinamento do Perceptron

A pergunta agora é:

Como treinar o neurônio perceptron? Como posicionar o hiperplanode forma a separar as duas classes: C1 e C2?

Prof. João Marcos Meirelles da Silva – p. 9/35

Treinamento do Perceptron

Para responder à pergunta, utilizaremos um paradigma deaprendizado conhecido como aprendizado por correção de erro. Seja:

x(n) = [+1, x1(n), x2(n), . . . , xm(n)]T (3)

e

ω(n) = [b(n), ω1, ω2, . . . , ωm]T (4)

Logo:

⇒ v(n) =m

∑

i=0

ωi(n)xi(n) = ωT (n)x(n) (5)

Prof. João Marcos Meirelles da Silva – p. 10/35

Treinamento do Perceptron

Figura 4: Aprendizado supervisionado.

Prof. João Marcos Meirelles da Silva – p. 11/35

Treinamento do Perceptron

• Objetivo: Minimizar a norma do erro.

minω

e2i

= |yi− y

i|2 (6)

A correção dos pesos das sinapses é dada então pora:

∆ω(n) = ηeT (n)x(n) (7)

aNotação vetorial.

Prof. João Marcos Meirelles da Silva – p. 12/35

Treinamento do Perceptron

Seja:

ωT x > 0,∀x ∈ C1 (8)

ωT x ≤ 0,∀x ∈ C2 (9)

O problema de treinamento resume-se a encontrar os valores do vetorde pesos ω, de modo que as duas inequações acima sejam sempreverdadeiras.

Prof. João Marcos Meirelles da Silva – p. 13/35

Treinamento do Perceptron

O algoritmo de adaptação do vetor de pesos para a rede perceptronde camada única pode ser formulada como se segue:

1 Se o n-ésimo vetor do conjunto de vetores de treinamento, x(n),for corretamente classificado através do vetor de pesos atual,ω(n), nenhuma correção é feita ao vetor de pesos;

ω(n + 1) = ω(n), se ωT (n)x(n) > 0 ∧ x(n) ∈ C1

ω(n + 1) = ω(n), se ωT (n)x(n) ≤ 0 ∧ x(n) ∈ C2

(10)

Prof. João Marcos Meirelles da Silva – p. 14/35

Treinamento do Perceptron

2 Se houver um erro de classificação, então:

ω(n + 1) = ω(n) − η(n)x(n), se ωT (n)x(n) > 0 ∧ x(n) ∈ C2

ω(n + 1) = ω(n) + η(n)x(n), se ωT (n)x(n) ≤ 0 ∧ x(n) ∈ C1

(11)

Prof. João Marcos Meirelles da Silva – p. 15/35

Teorema de Convergência

Teorema:

Sejam os subconjuntos de vetores de treinamento H1 e H2

linearmente independentes. Sejam os vetores apresentados aoperceptron, oriundos destes dois subconjuntos. O perceptronconverge após n0 iterações, de forma que:

ω(n0) = ω(n0 + 1) = ω(n0 + 2) = . . . (12)

é um vetor solução para n0 ≤ nmax.

Prof. João Marcos Meirelles da Silva – p. 16/35

Teorema de Convergência

Prova (para η constante):

Suponha que ω(0) = 0, η = 1 e ωT (n)x(n) < 0, para n = 1, 2, . . . , eque o vetor de entrada x(n) pertence à subclasse H1. ⇒ classificaçãoerrônea !

ω(n + 1) = ω(n) + x(n), x(n) ∈ C1 (13)

⇒ Podemos utilizar recorrência na equação acima...

Prof. João Marcos Meirelles da Silva – p. 17/35

Teorema de Convergência

Como ω(0) = 0, temos:

ω(1) = ω(0) + x(0)

ω(2) = ω(1) + x(1)

ω(3) = ω(2) + x(2)

(14)

Logo, para ω(n + 1), teremos:

ω(n + 1) = x1 + x2 + · · · + x(n) (15)

Prof. João Marcos Meirelles da Silva – p. 18/35

Teorema de Convergência

Como é assumido que as classes C1 e C2 são linearmente separáveis,então existe um vetor de pesos ω0 que é solução para ωT x(n) > 0

para os vetores x1, . . . , xnpertencentes à classe H1.

A partir de ω0 podemos definir um número positivo α da seguinteforma:

α = minx(n)∈H1

ωT

0 x(n) (16)

Prof. João Marcos Meirelles da Silva – p. 19/35

Teorema de Convergência

Multiplicando ambos os lados da equação (15) pelo vetor linha ωT0 ,

temos:

ωT

0 ω(n + 1) = ωT

0 x(1) + ωT

0 x(2) + · · · + ωT

0 x(n)

Utilizando a equação (16), temos:

ωT

0 ω(n + 1) ≥ nα (17)

Prof. João Marcos Meirelles da Silva – p. 20/35

Teorema de Convergência

Definição: Inequação de Cauchy-Schwarz

A inequação de Cauchy-Schwarz diz que:

‖ ω0 ‖2‖ ω(n + 1) ‖2≥ [ωT

0 ω(n + 1)]2 (18)

onde ‖ · ‖ representa o operador norma Euclidiana, e o produtointerno ωT

0 ω(n + 1) é um valor escalar.

Prof. João Marcos Meirelles da Silva – p. 21/35

Teorema de Convergência

A partir da equação (17), notamos que [ωT0 ω(n + 1)]2 é maior ou igual

a n2α2. A partir da equação(18), notamos que ‖ ω0 ‖2‖ ω(n + 1) ‖2 émaior ou igual a ‖ ωT

0 ω(n + 1) ‖2. Temos então:

‖ ω0 ‖2‖ ω(n + 1) ‖2≥ n2α2 (19)

Prof. João Marcos Meirelles da Silva – p. 22/35

Teorema de Convergência

Ou, de forma equivalente:

‖ ω(n + 1) ‖2≥n2α2

‖ ω0 ‖2(20)

⇒ Este é o primeiro resultado parcial da prova...

Agora, vamos reescrever a equação (13) na forma

ω(k + 1) = ω(k) + x(k) (21)

para k = 1, . . . , n e x(k) ∈ C1.

Prof. João Marcos Meirelles da Silva – p. 23/35

Teorema de Convergência

Tomando o quadrado da norma Euclidiana em ambos os lados daequação (21), temos:

‖ ω(k + 1) ‖2=‖ ω(k) ‖2 + ‖ x(k) ‖2 +2ωT (k)x(k) (22)

Porém, como foi assumido que o perceptron classificou a entrada x(k)

erroneamente como pertencendo à classe H1, temos queωT (k)x(k) < 0. Deduzimos da equação (22), para todo k = 1, . . . , n,que:

‖ ω(k + 1) ‖2≤‖ ω(k) ‖2 + ‖ x(k) ‖2

Prof. João Marcos Meirelles da Silva – p. 24/35

Teorema de Convergência

ou, de forma equivalente:

‖ ω(k + 1) ‖2 − ‖ ω(k) ‖2≤‖ x(k) ‖2 (23)

Somando todas estas inequações para k = 1, . . . , n e relembrandoque ω(0) = 0, temos:

‖ ω(n + 1) ‖2 ≤

n∑

k=1

‖ x(k) ‖2

≤ ηβ (24)

Prof. João Marcos Meirelles da Silva – p. 25/35

Teorema de Convergência

onde β é um número positivo definido por:

β = maxx(k)∈H1

‖ x(k) ‖2 (25)

Prof. João Marcos Meirelles da Silva – p. 26/35

Teorema de Convergência

As equações (20) e (24), repetidas aqui apenas por conveniência

‖ ω(n + 1) ‖2≥n2α2

‖ ω0 ‖2

‖ ω(n + 1) ‖2≤ ηβ

indicam que há uma contradição entre elas, pois a primeira nos mostraque o quadrado da norma Euclidiana do vetor peso ω(n + 1) crescemais linearmente (com o passar das iterações n) do que a segunda.

Prof. João Marcos Meirelles da Silva – p. 27/35

Teorema de Convergência

Podemos afirmar ainda que n não pode ser maior do que um certovalor, nmax, para o qual as equações (20) e (24) são ambas satisfeitasatravés do sinal de igualdade. Ou seja, nmax é a solução da equaçãoabaixo:

n2max

α2

‖ ω0 ‖2= nmaxβ (26)

Resolvendo para nmax, dado um vetor inicial ω0, temos:

nmax =β ‖ ω0 ‖2

α2(27)

Prof. João Marcos Meirelles da Silva – p. 28/35

Teorema de Convergência

Provamos então que para η = 1,∀n, ω(0) = 0 e dado que as classesC1 e C2 sejam separáveis, a regra de treinamento das sinapses doperceptron de camada única deve convergir em até nmax iterações.

Observação:

Podemos observar das equações (16), (25) e (27) que não hásomente um único valor para ω0 e nmax !

Prof. João Marcos Meirelles da Silva – p. 29/35

Teorema de Convergência

• O uso do valor inicial ω(0) 6= 0, apenas resulta em um númeromaior ou menor de iterações necessários para convergir,dependendo de como ω(0) se relaciona com ω0.

• Independentemente do valor atribuído a ω(0), o Teorema deConvergência assegura o resultado final (desde que as classessejam linearmente separáveis).

Prof. João Marcos Meirelles da Silva – p. 30/35

Algoritmo de Treinamento

1. Inicialização: Faça ω(0) = 0. Em seguida, realize os próximospassos para n = 1, 2, . . .

2. Ativação: No instante de tempo n, ative o perceptronapresentando o valor de entrada x(n) e a resposta desejaday(n)

3. Cálculo da resposta atual: Calcule a resposta atual doperceptron:

y(n) = sign[ωT (n)x(n)]

Prof. João Marcos Meirelles da Silva – p. 31/35

Algoritmo de Treinamento

4 Alteração dos pesos das sinapses: Atualize o vetor de pesos doperceptron:

ω(n + 1) = ω(n) + η[y(n) − y(n)]x(n)

onde

y(n) =

+1 se x(n) ∈ C1

−1 se x(n) ∈ C2

5 Continuação: Incremente n de uma unidade e retorne ao passo2.

Prof. João Marcos Meirelles da Silva – p. 32/35

Algoritmo de Treinamento

Quando parar o treinamento?

• Quando ∆ω ≈ 0, ou

• Quando atingir um número máximo de iteraçõespré-determinado, ou

• Quando a norma do erro (6) for menor ou igual a um valorpré-determinado (e2

max):

e2i≤ e2

max(28)

Prof. João Marcos Meirelles da Silva – p. 33/35

Referências

1. Haykin, S., “Neural Networks - A Comprehensive Foundation,”2nd edition - Prentice Hall, 1999.

2. Fausett, L., “Fundamental of Neural Networks - Architectures,Algorithms and Applications,” Prentice Hall, 1994.

3. Theodoris, S., Koutroumbas, K, “Pattern Recognition,” 4th

edition, Academic Press.

Prof. João Marcos Meirelles da Silva – p. 34/35

FIM

Prof. João Marcos Meirelles da Silva – p. 35/35