AULA03

PERCEPTRON

(CONTINUAÇÃO)

Perceptron de duas entradas e um bias

w1

w2

x1

x2

u

w0=b

y

w0x0=+1

0se0)(

0se1)(sendo),( 02211 uuf

uufwxwxwfy

Com os parâmetros w0, w1 e w2, a função f(u) separa o espaço de entradas em duas regiões, usando uma linha reta dada por: w1x1 + w2x2 + w0 = 0

f(u)

Separação Linear• Sabe-se que se formarmos uma combinação linear de duas

variáveis, e igualá-la a um número, então os pontos no espaço bidimensional podem ser divididos em três categorias:

– a) pontos pertencentes à linha com coordenadas tais que

w1. x1 + w2 . x2 =

– b) pontos em um lado da linha tem coordenadas tais que

w1 . x1 + w2 . x2 <

– c) pontos no outro lado da linha tem coordenadas tais que

w1 . x1 + w2 . x2 > .

Nota: bias b = -

bwondewxwxwfy 002211 ),(

pois

Pontos 2x1+3x2 posição

(x1 , x2 ) (0.0, 2.0) 6 linha(1.0, 1.0) 5 abaixo(1.0, 2.0) 8 acima(2.0, 0.0) 4 abaixo(2.0, 0.66) 6 linha(2.0, 1.0) 7 acima

Posição dos pontos em função da linha 2 x1 + 3 x2 = 6 de delimitação.

0.0 0.5 1.0 1.5 2.0 2.5 3.00.0

0.5

1.0

1.5

2.0

2 x1 + 3 x2 = 6linha

(1.0, 2.0)

(1.0, 1.0) (2.0, 1.0)

(2.0, 0.66)

(2.0, 0.0)

(0.0, 2.0)

x2Exemplo

x1

= 6

Linha:

Acima:

Abaixo:

2 x1 + 3 x2 = 6

2 x1 + 3 x2 > 6

2 x1 + 3 x2 < 6

Problema do XOR (ou-exclusivo)

x1

x2

(1,0)

(0,0) (1,0)

(1,1)

y = 0 y = 1

No caso do XOR, não existe uma única reta que divide os pontos (0,0) e (1,1) para um lado, e (0,1) e (1,0) do outro lado.

Conclui-se que um neurônio do tipo perceptron não implementa uma função ou-exclusivo ( constatado por Minsky & Papert, em 1969).

Função xor

É claro que nenhuma combinação linear ou linha reta pode ser traçada tal que as entradas (0, 0) e (1, 1) fiquem numa categoria e (0, 1) e (1, 0) numa outra categoria, conforme demonstração:

Algebricamente tem-se:

).0,1(pontoopara0.1.

e),1,0(pontoopara1.0.

21

21

ww

ww

Mas, somando as duas inequações tem-se:

1.1. 21 ww

o que significa que (1,1) estaria no mesmo lado da linha L1, o que é indesejável.

significando que os dois pontos ficam num lado da linha L1.

PERCEPTRONS MULTICAMADAS

A função XOR está além da capacidade de um perceptron simples.

Contudo, um perceptron simples pode implementar funções lógicas elementares: AND, OR e NOT.

Assim, se uma função pode ser expressa como uma combinação dessas funções lógicas elementares, então essa função pode ser implementada usando mais neurônios.

Por exemplo, XOR pode ser expressa por: (x1 or x2 ) and (not (x1 and x2 )).

x1 OR x2

x1 AND x2

NOT

AND

x1

x2

y

Separação linear para XOR de duas camadas

Em termos de separação linear (demarcação), isso equivale ao traçado de duas linhas.

A parte acima da linha L1 corresponde à função OR, e a parte

abaixo da linha L2 corresponde à função NOT AND.

A área entre as duas linhas corresponde à função XOR, o que corresponde à área ABCD, que contem os pontos (0,1) e ( 1,0).

0 1

0

1

( 0,0 ) (1,0)

(0,1) ( 1,1)

x1

x2

Linha L1

Linha L2

A

B

C

D

x1 OR x2

x1 AND x2

NOT

AND

x1

x2

y

Delimitação de um cluster usando 3 separações no espaço de entradas

100

110

101

001011010

111

x1

x2

L3

L2

L1

L1 L2 L3

1 0 0

N3

N2

N1

N4

x1

x2

y

Delimitação de 2 clusteres disjuntos

N3

N2

N1

N7

x1

N6

N5

N4

N8

x2

N9

y

x1

x2 L3

L5

L1

L2

L4

L6

Delimitação de um cluster circular

x1

x2

Infinitos neurônios na camada escondida

Dualidade entre o espaço de entradas e espaço de pesos

Um valor no espaço de entradas determina uma separação linear no espaço de pesos, e vice-versa.

x2

x1

x0

w2

w1

w0

entrada x

peso w

classe A

não-classeA

hiperplanode peso

hiperplanode entrada

pesospara

f (x) = 1

pesospara

f(x) = 0

Exemplos de pontos no espaço de entrada delimitando uma região no espaço de pesos

x2

x1

x2

x1

w2

w1

w2

w1

x2

x1

w2

w1

w2

w1

w1+w2 >= 1 w1 < 1

w2 <1

(1,1)

(1,0)(0,1)

x1w1 +x2w2 >= 1

Entrada = (1,1) Entrada = (1,0) Entrada = (0,1)

x1w1 +x2w2 < 1 x1w1 +x2w2 < 1 Inequações para a função AND, com w0 = -1

x1w1 +x2w2 + w0=0Equação das linhas:

xxx

Delimitação de regiões no espaço dos pesos

• Se o interesse é procurar os vetores pesos para uma função AND, os pesos w0, w1, e w2 devem obedecer as seguintes inequações:

entrada (0,0): 0.w2 + 0.w1 +1.w0 <0, saída y = 0

entrada (0,1): 1.w2 + 0.w1 +1.w0 <0, saída y = 0

entrada (1,0): 0.w2 + 1.w1 +1.w0 <0, saída y = 0

entrada (1,1): 1.w2 + 1.w1 +1.w0 >=0, saída y = 1.

• Essas inequações definem quatro planos que passam pela origem:

Plano 1: w0 = 0

Plano 2: w2 + w0 = 0

Plano 3: w1 + w0 = 0

Plano 4: w2 + w1 + w0 = 0

Polítopo para a função AND Plano 1: w0 = 0Plano 2: w2 + w0 = 0Plano 3: w1 + w0 = 0Plano 4: w2 + w1 + w0 = 0

Para a função AND:

w0 < 0w2 + w0 < 0w1 + w0 < 0w2 + w1 + w0 >= 0

w2

w1

w0

-1

w2 + w0 = 0

w1 + w0 = 0

w2 + w1+ w0 = 0

-0.5

solução paraw0 = -0.5

solução paraw0 = -1

Existem infinitas soluções para a função AND, delimitadas pelo polítopo.A figura mostra uma região triangular de soluções para w0 = -1 e w0 = -0.5.

Superfície de erro para AND no espaço de pesos

w1

w2

2 1 2

1

0

1

2

w1

w2 w(0)

w(1)

w(2)w (3) = w*

erro

w1

w20

1

0

1

0

1

2

com w0 = -1Erro = 0

Passos iterativosdurante oTreinamento

w* é o vetor solução

número de erros

Funções booleanas de duas variáveis• As 16 possíveis funções de duas variáveis são:

f0(x1,x2) = f0000 (x1,x2) = 0

f1(x1,x2) = f0001 (x1,x2) = ~(x1 v x2)

f2(x1,x2) = f0010 (x1,x2) = x1 ^ ~x2

f3(x1,x2) = f0011 (x1,x2) = ~x2

f4(x1,x2) = f0100 (x1,x2) = ~x1 ^ x2

f5(x1,x2) = f0101 (x1,x2) = ~x1

f6(x1,x2) = f0110 (x1,x2) = xor

f7(x1,x2) = f0111 (x1,x2) = ~(x1 ^ x2)

f8(x1,x2) = f1000 (x1,x2) = x1 ^ x2

f9(x1,x2) = f1001 (x1,x2) = ~xor

f10(x1,x2) = f1010 (x1,x2) = x1

f11(x1,x2) = f1011 (x1,x2) = x1 v~ x2

f12(x1,x2) = f1100 (x1,x2) = x2

f13(x1,x2) = f1101 (x1,x2) = ~x1 v x2

f14(x1,x2) = f1110 (x1,x2) = x1 v x2

f15(x1,x2) = f1111 (x1,x2) = 1

Visualização de todas as funções linearmente separáveis no espaço de pesos

1111 0000

0100

0010

1101

1011

1100 11000101 0101

1010 10100011 0011

1110 0111 0001 1000

Considerando-se os pesos normalizados pode-se visualizar todas as 14 funções linearmente separáveis utilizando 4 planos de separação.

Como tem 16 funções booleanas no caso de entrada bidimensional (x1, x2), as duas funções que faltam são XOR e NOT-XOR (coincidência).

Plano 1f(0,0)

Plano 2 f(0,1)

Plano 4 f(1,1)

Plano 3 f(1,0)

Plano 4 Plano 1Plano 3

Plano 2

Projeção no plano

f13

f4

f0

f2f3 f10

f11

ORNAND NOR AND

f5 f12

f15

raio deprojeção A

A' plano deprojeção

14 regiões

Nota-se que: a) com 3 planos de separação, obtem-se 8 regiões. b) com 4 planos de separação, obtem-se 14 regiões.

f14 = ORf1 = NORf8 = ANDf7 = NAND

L1L4

L3

L2

perceptrons com camadas escondidas

Nota-se que cada neurônio da camada escondida divide o espaço de entrada em duas hemisferas, considerando vetores de entrada normalizados.

111110

100

101

011 010000

plano 3

plano 1

plano2

x2

x1

As saídas da camada escondida são introduzidas no neurônio de saída, que dependendo da região da esfera computa como 1 ou 0.

esfera dos vetores de entrada normalizados

N1

N2

N3

N4

N3

N1

N2

Máximo número de elementos no espaço de entrada separáveis genericamente

Dado um subconjunto S de um espaço de entrada X, usando uma rede que divide esse subconjunto em duas partes, se os elementos de S com valor 0 ficam de um lado e os elementos com valor 1, do outro lado, dizemos que a rede é treinável.

Uma questão importante é qual o máximo número de elementos de um espaço de entrada que uma rede pode classificar, genericamente.

No caso do perceptron de duas entradas esse número é 3, pois dados 3 pontos no espaço de entrada sempre é possível separar esses pontos usando uma linha reta.

x1

x2

x1

x2

x1

x2

Para o caso de 4 elementos nem sempre isso é possível, como por exemplo, o caso do XOR.

Rede com dois neurônios na camada escondida

• Nesse caso, cada neurônio da camada escondida divide a superfície da esfera em dois hemisférios. Portanto, os dois neurônios dividem a superfície da esfera em 4 regiões, codificadas em duas saídas.

• Cada uma dessas saídas são recebidas pelo neurôno de saída, que por sua vez tem a capacidade de realizar 14 funções.

• O problema do XOR pode ser resolvido usando uma dessas 14 funções e em geral, quaisquer 4 elementos do espaço de entrada podem ser divididos em duas classes usando dois neurônios na camada escondida.

• Contudo, 8 elementos no espaço de entrada não são possíveis de serem divididos com dois neurônios escondidos, genericamente.

x1

x2

Dimensão de Vapnik-Chervonenkis

• O número máximo de elementos d de um espaço de entrada, que podem ser sempre separados linearmente, é chamado de dimensão de Vapnik-Chervonenkis, ou simplificadamente dimensão VC.

• Segundo Cover (1968) e Baum e Haussler (1989), a dimensão VC, para uma rede feedforward constituída de neurônios com uma função de ativação degrau, é de O(WlogW) onde W é o número total de parâmetros livres da rede.

• Segundo Koiran e Sontag (1996) a dimensão VC, para uma rede feedforward constituída de múltiplas camadas cujos neurônios utilizam a função de ativação sigmóide, é de O(W2) onde W é o número total de parâmetros livres da rede.

Regiões no espaço de pesos para redes de 2 neurônios escondidos de 2 entradas

Para 2 neurônios escondidos e 1 neurônio de saída, tem-se 9 parâmetros livres:

2 pesos de entrada e 1 bias para cada neurônio.

Cada neurônio divide o espaço de pesos em quatro hiperplanos:

entrada (0,0): 0.w2 + 0.w1 +1.w0 = 0 entrada (0,1): 1.w2 + 0.w1 +1.w0 = 0 entrada (1,0): 0.w2 + 1.w1 +1.w0 = 0 entrada (1,1): 1.w2 + 1.w1 +1.w0 = 0

Se cada neurônio divide o espaço de pesos em 14 regiões, como 3 neurônios,14.14.14 = 2744 regiões ou polítopos são gerados.

Isso significa que o número de regiões de soluções para uma esfera booleana de nove dimensões é de 2744, sendo que 16 dessas regiões são soluções da função XOR.

Possíveis combinações para XOR usando 2 neurônios escodidos

f1

f7

f4

f7

f1

f2

f2

f4

f14

f4

f2

f14

f4

f13

f13

f13

f4

f11

f8

f14

f2

f14

f8

f4

f1

f8

f1

f8

f1

f1

f2

f11

f13

f11

f2

f11

f7

f14

f8

f14

f7

f8

f11

f13

f7

f13

f11

f7

Possíveis combinações para XOR usando 2 neurônios escodidos

f1 f2

f11 f7

f11 f7

f8 f4

f4 f1

f14 f13

f14 f13

f2 f8

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

8

9

10

11

12

13

14

15

0

1

2

3

4

5

6

7

f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15

f8

f9

f10

f11

f12

f13

f14

f15

f0

f1

f2

f3

f4

f5

f6

f7

A figura mostra a distribuição de soluções para XOR, usando uma rede de 2x1 neurônios.

Dependendo de onde o algoritmo de busca começa (pesos iniciais) a solução pode ser mais fácil, ou difícil.

Contagem do número de regiões

• Quantas regiões são definidas usando m hiperplanos de dimensão n-1, num espaço n-dimensional de pesos? (consideramos apenas os hiperplanos passando pela origem)

• Caso bi-dimensional ( n = 2) : o hiperplano é uma reta.

• Cada novo hiperplano divide o cone definido pelos hiperplanos anteriores gerando mais 2 novas regiões.

w0

w1

hiperplano

região 1

região 2

w0

w1 região 1

região 2

região 3

região 4

m =1

m = 2

x1 w1

w0

Contagem do número de regiões (cont.)

• Caso tri-dimensional (n = 3): hiperplano é um plano.

• Para os casos de 1, 2 e 3 hiperplanos, cada hiperplano aumenta o número de regiões por um fator 2:

para m = 1 2 regiões para m = 2 4 regiões para m = 3 8 regiões(m = número de hiperplanos)

• Generalizando, n hiperplanos de dimensão n-1, em espaço n-dimensional, define 2n regiões.

• Para o caso de m = 4, vimos que tem 14 regiões, ou seja: o quarto hiperplano consegue dividir no máximo 6 das 8 regiões previamente geradas por 3 hiperplanos.

x1 w1

w0

x2w2

Proposição 1Seja R(m,n) o número de regiões definidos por m hiperplanos de dimensão n-1, em posição

genérica, num espaço de pesos n-dimensional. Inicia-se com R(1, n) = 2 para e R(m,0) = 0, . Para e m > 1 tem-se

R(m,n) = R(m-1,n) + R(m-1,n-1)

A prova é por indução em m: a) Para m = 2 e n = 1, é válida.b) Para m = 2 e sabe-se que R(2,n) = 4 e a fórmula é válida novamente: R(2,n) = R(1,n) + R(1,n-1) = 2 + 2 = 4c) Agora, m + 1 hiperplanos de dimensão n-1 são dados em espaço n-dimensional e posição genérica ( ). Da hipótese de indução segue que os primeiros m hiperplanos

definem R(m,n) regiões em espaço n-dimensional. O hiperplano m+1 intersecta os primeiros m hiperplanos, em m hiperplanos de dimensão n-2 (se todos estiverem em posição genérica). Esses m hiperplanos dividem o espaço (n-1)-dimensional em R (m,n-1) regiões. Após a separação com o hiperplano m + 1, exatamente R(m,n-1) novas regiões são criadas. O novo número de regiões é portanto R (m+1,n) = R(m,n) + R(m,n-1) e a prova termina.

1n

1m 1n

2n

2n

6 regiões novas R(m,n-1)=R(3,2)

m+1 = 4m = 3

Cálculo recursivo de R(m,n)n

m 0 1 2 3 4

1 0 2 2 2 2

2 0 2 4 4 4

3 0 2 6 8 8

4 0 2 8 14 16

5 0 2 10 22 30

dimensão

Nota-se que:a) R(m,n) = 2m para nm , isto é, o número de regiões cresce

exponencialmente até a dimensão do espaço.

b) Após esse limite (m > n) o crescimento passa a ser polinomial

Para n = 2, R(m,2) = 2m

Para n = 3, R(m,3) = m2-m+2

Proposição 2Para , R(m,n) é um polinômio de grau n-1 na variável m.

A prova é por indução em n:

Denotando P(a,b) um polinômio de grau b na variável a. O polinômio é explicitamente dado para n = 2. (R(m,2) = 2m))

Para a dimensão n + 1 e m = 1 sabe-se que R(1, n+1) = 2. Se m > 1 então R(m,n+1) = R(m-1,n+1) + R(m-1,n)

Se R (m-1, n) é um polinômio de grau n -1 na variável m segue que R(m,n+1) = R(m-1,n+1) + P(m,n-1) Repetindo essa redução m -1 vezes chega-se finalmente a

R(m,n+1) = R(m-(m-1),n+1) + (m-1)P(m,n-1) = 2 + (m-1)P(m,n-1) = P(m,n)

R (m,n+1) é então um polinômio de grau n na variável m .

1n

1

0

12),(n

i i

mnmRUma fórmula útil para R(m,n) é

cuja validade pode ser provada também por indução.

Contagem do número de regiões (cont.) • A fórmula possibilita o cálculo do número de regiões

formados por hiperplanos em posições genéricas.

• No caso de funções booleanas, as entradas sendo booleanas, os hiperplanos não se posicionam genericamente.

• O número de regiões, definido por um espaço 4-dimensional por 8 hiperplanos, é 128. Mas existem somente 104 funções computáveis por um perceptron de 3 entradas, e portanto 4 pesos e 8 possíveis vetores de entrada.

• O número R(m,n) deve ser interpretado como um limite superior sobre o número de funções computáveis para entradas binárias.

1

0

12),(n

i i

mnmR

240.559736.412572.94103.45

461.5882.3882.1536.654

1701281042563

161414162

44441

!/2),2(),2(2

9

122 2

x

nnRnTn nnn

Comparação do número de funções booleanas e funções computáveis de n entradas com dois limites superiores diferentes.

Conseqüências• Primeira consequência:

– O número de funções computáveis num espaço n-dimensional cresce polinomialmente enquanto que o número de possíves funções booleanas cresce exponencialmente.

– A relação entre funções computáveis e o total de funções lógicas tende a zero com o incremento de n.

• Segunda consequência:– Problemas insolúveis para redes com um número pré-determinado de unidades

podem ser fabricadas com o incremento do número de linhas de entrada.

• Exemplo:

Para os neurônios escondidos, o número de entradas considerando o bias é n, e o número de pesos da rede é 2n + 3. O número de diferentes entradas é 2n-1. O número de regiões N no espaço de pesos é dado por

)3,4().,2().,2( 11 RnRnRN nn

Isso significa que N é limitado por uma função da ordem de 2)1(22 n

Se o número F de funções booleanas de n entradas é n22 é possível

encontrar n que satisfaça F > N.

Visualização geométrica

Px

22 e NPSejam dois conjuntos de pontos a serem separados.

n1

n2

p1

p2

vetor p

eso

vetores emN

vetores emP

x1

x2

n1

n2

p1

p2

vetor p

eso

x2

x0

x1

Espaço de entrada sem bias Espaço de entrada com bias

Um vetor peso w deve ser encontrado tal que w.x > 0 para todo

e w.x < 0 para todo Nx

• O algoritmo de treinamento do perceptron começa com um vetor w0 aleatoriamente escolhido.

• Se o vetor é tal que w.x < 0 significa que o ângulo entre os dois vetores é maior que 900. O vetor peso deve ser rotacionado na direção de x para que x fique na metade positiva do espaço definido por w. Isso pode ser feito adicionando x a w, como o algoritmo de treinamento faz.

• Se o vetor é tal que w.x > 0 significa que o ângulo entre os dois vetores é menor que 900. O vetor peso deve ser rotacionado na direção contrária a x para que x fique na metade negativa do espaço definido por w. Isso pode ser feito subtraindo x de w.

• Se existe solução ela é encontrada após um número finito de passos.

• Uma boa heurística é iniciar o peso com a média dos vetores de entrada positivos menos a média dos vetores de entrada negativos.

Nx

Px

Ilustração gráfica

w0

x3

x1

x2

w0

x3

x1

x2

w1

L

x3

x1

x2

w2

L

x3

x1

x2

L

w3

Configuração inicial Após correção com x1

Após correção com x3 Após correção com x1

L

Convergência do algoritmo

• Se os conjuntos P e N são linearmente separáveis, o algoritmo de treinamento atualiza o vetor de pesos wt um número finito de vezes até a convergência.

• Em outras palavras, se os vetores em P e N são testados ciclicamente, um após o outro, um vetor peso wt, que separa os dois conjuntos, é encontrado após um número finito de passos t.

• Para a prova, são feitas 3 simplificações sem prejuízo da generalidade:– Os conjuntos P e N podem ser unidos em P’ =PUN-. Onde N- consiste de

elementos de N negados .– Os vetores em P’ podem ser normalizados, pois se um vetor w é tal que w.x > 0

isso é válido para qualquer outro vetor x, onde é uma constante.– O vetor peso pode também ser normalizado. Assumindo que uma solução

existe, w* é a solução.

• Assume-se que após t+1 passos o vetor peso wt+1 foi computado. Isso significa que no tempo t um vetor pi foi incorretamente classificado pelo vetor peso wt e assim, wt+1 = wt + pi.

• O cosseno do ângulo entre wt+1 e w* é

}'|min{ P p.p*w

1

1cos

t

t

w

.w*w

t

it

itt

w.*w

.p*ww.*w

pwwww )(.*.* 1

Para a expressão do numerador sabe-se que

com

Prova da convergência

Cont.

• Se o vetor peso w* define uma separação linear absoluta entre P e N sabe-se que > 0. Por indução obtem-se

it pw .

22

2

1

.2

)).((

iitt

ititt

ppww

pwpww

)1(01 tt .w*w.w*w

Por outro lado para o termo do denominador sabe-se que

Se é negativo ou zero (caso contrário não teria sido feita a correção) deduz-se que

12

222

1

t

itt

w

pww

pois os vetores em P são normalizados.

}'|min{ P p.p*w tt w.*www 1.*

Vimos que:

onde1

1cos

t

t

w

.w*w

e

Cont.

• A indução diz que

t

)1(

)1(cos

2

0

0

t

t

w

.w*w

)1(2

0

2

1 tt ww

)1(01 tt .w*w.w*w1

1cos

t

t

w

.w*w

Lembrando que

e

tem-se

O termo à direita cresce proporcionalmente a e se é positivo

pode tornar-se arbitrariamente grande.

1cos Contudo, se , t deve ser limitado por um valor máximo.Portanto, o número de correções para o vetor peso deve ser finito.

122

1 tt ww vimos que: