AULA03
PERCEPTRON
(CONTINUAÇÃO)
Perceptron de duas entradas e um bias
w0=b
x0=+1
w0
f(u)
u
x1
w1
x2
w2
y

 f (u)  1 se u  0
y  f (w1 x1  w2 x2  w0 ), sendo 
 f (u)  0 se u  0
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
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
w 1. x 1 + w 2 . x 2 = q
–
b) pontos em um lado da linha tem coordenadas tais que
w1 . x 1 + w2 . x 2 < q
–
c) pontos no outro lado da linha tem coordenadas tais que
w1 . x 1 + w2 . x2 > q .
Nota: bias b = - q
pois
y  f (w1 x1  w2 x2  w0 ), onde w0  b
Exemplo
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
x2
2.0
(0.0,2.0)
(1.0,2.0)
linha
2 x1 + 3 x2 = 6
1.5
1.0
(1.0,1.0)
(2.0,1.0)
(2.0,0.66)
0.5
x1
(2.0,0.0)
0.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
Posição dos pontos em função da linha 2 x1 + 3 x2 = 6 de delimitação.
Linha:
2 x1 + 3 x2 = 6
Acima:
2 x1 + 3 x2 > 6
Abaixo:
2 x1 + 3 x2 < 6
q=6
Problema do XOR (ou-exclusivo)
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.
x2
(1,0)
(1,1)
(0,0)
(1,0)
Função xor
x1
y=0
y=1
Conclui-se que um neurônio do tipo perceptron não implementa uma função
ou-exclusivo ( constatado por Minsky & Papert, em 1969).
É 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:
w1 .0  w2 .1  q para o ponto (0,1), e
w1 .1  w2 .0  q para o ponto (1,0).
significando que os dois pontos ficam num lado da linha L1.
Mas, somando as duas inequações tem-se:
w1 .1  w2 .1  q
o que significa que (1,1) estaria no mesmo lado da linha L1, o que é indesejável.
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
(x1 or x2 ) and (not (x1 and x2 )).
x1 OR x2
y
AND
NOT
x2
x1 AND x2
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).
x2
(0,1)
x1
( 1,1)
C
1
x1 OR x2
y
AND
D
NOT
x2
Linha L2
x1 AND x2
Linha L1
A
(1,0)
( 0,0 )
0
0
B
1
x1
Delimitação de um cluster usando 3 separações
no espaço de entradas
x1
N1
y
N2
N4
x2
x2
100
N3
L3
L1 L2 L3
110
100
101
111
010
011
L1
001
L2
x1
Delimitação de 2 clusteres disjuntos
x2
x1
L2
N1
N2
L3
N7
L1
y
N3
N9
L6
N4
N5
L4
N8
L5
x2
N6
x1
Delimitação de um cluster circular
x2
x1
Infinitos neurônios na camada escondida
Dualidade entre o espaço de entradas e espaço
de pesos
x2
pesos
para
f (x) = 1
entrada x
classe
A
não-classe
A
x0
hiperplano
de peso
w2
peso w
x1
w0
w1
pesos
para
f(x) = 0
hiperplano
de entrada
Um valor no espaço de entradas determina uma separação linear no espaço de
pesos, e vice-versa.
Exemplos de pontos no espaço de entrada
delimitando uma região no espaço de pesos
x2
x2
x2
(1,1)
(0,1)
(1,0)
x1
w2
x1
w2
w2
w2
w1+w2 >= 1
x
w1 < 1
x
w2 <1
x
w1
w1
x1w1 +x2w2 >= 1 x1w1 +x2w2 < 1
Entrada = (1,1)
x1
Entrada = (1,0)
w1
w1
x1w1 +x2w2 < 1
Entrada = (0,1)
Inequações para a função
AND, com w0 = -1
Equação das linhas: x1w1 +x2w2 + w0=0
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):
entrada (0,1):
entrada (1,0):
entrada (1,1):
0.w2 + 0.w1 +1.w0 <0,
1.w2 + 0.w1 +1.w0 <0,
0.w2 + 1.w1 +1.w0 <0,
1.w2 + 1.w1 +1.w0 >=0,
saída y = 0
saída y = 0
saída y = 0
saída y = 1.
• Essas inequações definem quatro planos que passam pela origem:
Plano 1:
Plano 2:
Plano 3:
Plano 4:
w0 = 0
w2 + w0 = 0
w1 + w0 = 0
w2 + w1 + w0 = 0
Polítopo para a função AND
Plano 1: w0 = 0
Plano 2: w2 + w0 = 0
Plano 3: w1 + w0 = 0
Plano 4: w2 + w1 + w0 = 0
Para a função AND:
w0 < 0
w2 + w0 < 0
w1 + w0 < 0
w2 + w1 + w0 >= 0
w1
w2
-0.5
-1
solução para
w0 = -0.5
solução para
w0 = -1
w1 + w0 = 0
w2 + w0 = 0
w0
w2 + w1+ w0 = 0
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
Erro = 0
com w0 = -1
erro
2
1
1
0
w2
0
0
w1
1
número
de erros
w2
w2
2
1
2
Passos iterativos
durante o
Treinamento
w(0)
w(1)
w (3) = w*
0
w* é o vetor
solução
w(2)
1
1
w1
2
w1
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
1100
1101
0101
0101
0100
1100
Plano 2
Plano 3
f(1,0)
1110
Plano 2
f(0,1)
1010
1111
0111
0001
1011
0011
0011
0000
0010
1000
1010
Plano 3
Plano 1
Plano 1
Plano 4
Plano 4
f(0,0)
f(1,1)
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).
Projeção no plano
L4
f15
L1
raio de
projeção
L3
f13
A
f12
f5
f4
NAND
NOR
f0
AND
f2
f3
A'
f10
plano de
projeção
f11
f14 = OR
f1 = NOR
f8 = AND
f7 = NAND
L2
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.
OR
perceptrons com camadas escondidas
N3
plano 3
x2
N1
N2
N1
101
N4
111
011
plano 1
100
110
010
000
N2
plano2
N3
x1
esfera dos vetores de
entrada normalizados
Nota-se que cada neurônio da camada escondida divide o espaço de entrada
em duas hemisferas, considerando vetores de entrada normalizados.
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.
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.
x2
x2
x1
x2
x1
x1
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.
x2
x1
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):
entrada (0,1):
entrada (1,0):
entrada (1,1):
0.w2 + 0.w1
1.w2 + 0.w1
0.w2 + 1.w1
1.w2 + 1.w1
+1.w0 = 0
+1.w0 = 0
+1.w0 = 0
+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
f1
f7
f4
f8
f1
f2
f1
f7
f1
f8
f1
f2
f4
f2
f11
f14
f13
f14
f11
f4
f2
f11
f2
f4
f13
f7
f14
f13
f8
f11
f8
f13
f4
f14
f7
f8
f14
f11
f13
f2
f14
f7
f4
f8
f13
f7
f11
Possíveis combinações para XOR
usando 2 neurônios escodidos
0
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
f0
0
1
f4
2
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.
f1
f1
f14
f2
f13
f3
3
4
f14
f4
f13
5
f5
6
f6
7
f2
f8
f7
8
f1
f2
f8
9
f9
10
f10
11
f11
f7
f11
f12
12
13
f11
f7
14
f8
f13
f14
f4
f15
15
f0
f1
f2
f3
f4
f5
f6
f7
f8
f9 f10 f11 f12 f13 f14 f15
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)
hiperplano
w1
•
região 1
Caso bi-dimensional ( n = 2) : o hiperplano
é uma reta.
região 2
w0
m =1
x1
w1
w1
•
Cada novo hiperplano divide o cone definido pelos
hiperplanos anteriores gerando mais 2
novas regiões.
m=2
w0
região 1
região 4
w0
região 2
região 3
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:
w0
para m = 1  2 regiões
para m = 2  4 regiões
x1
w1
para m = 3  8 regiões
w2
(m = número de hiperplanos)
x2
• Generalizando, n hiperplanos de dimensão n-1, em espaço ndimensional, 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.
Proposição 1
Seja 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, m  1. Para n  1 e m > 1 tem-se
n 1
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 n  2 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 = 4
c)
Agora, m + 1 hiperplanos de dimensão n-1 são dados em espaço n-dimensional e
posição genérica ( n  2 ). 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.
m=3
m+1 = 4
6 regiões novas
R(m,n-1)=R(3,2)
Cálculo recursivo de R(m,n)
dimensão
m
n
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
Nota-se que:
a) R(m,n) = 2m para m  n , 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 2
Para n  1
, 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 .
 m  1

R(m, n)  2 
i 
i 0 
n 1
Uma 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.)
 m  1

R(m, n)  2 
i 
i 0 
n 1
•
•
•
•
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.
Comparação do número de funções booleanas e funções computáveis de
n entradas com dois limites superiores diferentes.
n
1
22
n
4
T ( 2 n , n)

R ( 2 2 , n) 2 n
4
4
2
1

/ n!
4
2
3
4
16
256
65.536
14
104
1.882
14
128
3.882
16
170
5.461
5
4.3x109
94.572
412.736
559.240
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
N  R(2 n1 , n). R(2 n1 , n). R(4,3)
Isso significa que N é limitado por uma função da ordem de
Se o número F de funções booleanas de n entradas é
encontrar n que satisfaça F > N.
2
2n
2
2 ( n 1) 2
é possível
Visualização geométrica
Sejam
P  2 e N  2
dois conjuntos de pontos a serem separados.
x2
p1
pe
r
to
pe
r
to
e
v
vetores em
p2
P
ve
n1
x1
n1
vetores em
N
x0
so
so
p2
p1
x2
n2
n2
Espaço de entrada sem bias
x1
Espaço de entrada com bias
Um vetor peso w deve ser encontrado tal que w.x > 0 para todo x  P
e w.x < 0 para todo x  N
•
•
•
O algoritmo de treinamento do perceptron começa com um vetor w0
aleatoriamente escolhido.
Se o vetor x  P é 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 x  N é 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.
Ilustração gráfica
L
x1
x1
w0
L
w1
x2
w0 x2
x3
x3
Configuração inicial
x1
Após correção com x1
L
L
x1
w3
x2
w2
x3
Após correção com x3
x2
x3
Após correção com x1
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 hx, onde h é uma constante.
– O vetor peso pode também ser normalizado. Assumindo que uma solução
existe, w* é a solução.
Prova da convergência
•
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 r entre wt+1 e w* é
w * .w t 1
cos r 
w t 1
Para a expressão do numerador sabe-se que
w * .w t 1  w * . (w t  p i )
 w * . w t  w * .pi
 w * . wt  
com
  min{w * .p | p  P'}
Cont.
Vimos que:
e
•
w * .w t 1
cos r 
w t 1
w * .w t 1  w * . w t  
onde
  min{w * .p | p  P'}
Se o vetor peso w* define uma separação linear absoluta entre P e N sabese que  > 0. Por indução obtem-se
w * .wt 1  w * .w0  (t  1)
Por outro lado para o termo do denominador sabe-se que
w t 1
2
 (w t  p i ).(w t  p i )
 wt
2
 2w t .p i  p i
2
Se w t .p i é negativo ou zero (caso contrário não teria sido feita a correção)
deduz-se que
w t 1
2
 wt
2
 pi
 wt
2
1
2
pois os vetores em P são normalizados.
Cont.
•
w t 1  w t
2
vimos que:
A indução diz que
w t 1
2
 w0
2
2
1
 (t  1)
Lembrando que
w * .w t 1
cos r 
w t 1
tem-se
cos r 
w * .wt 1  w * .w0  (t  1)
e
w * .w 0  (t  1)
w0
2
 (t  1)
O termo à direita cresce proporcionalmente a
t
e se  é positivo
pode tornar-se arbitrariamente grande.
Contudo, se cos r  1 , t deve ser limitado por um valor máximo.
Portanto, o número de correções para o vetor peso deve ser finito.