Perceptron Simples e Variantes
Prof. Júlio Cesar Nievola
PPGIA – PUCPR
Especialização em Inteligência Computacional – 2004
Perceptron - Características
• O perceptron é usado para conjuntos de treinamento
linearmente separáveis:
p
• Inclusão de tendência (“bias”): S W0 W j .u j
j 1
• No algoritmo de aprendizagem do Perceptron busca-se um
vetor W que tenha projeção positiva (produto interno) com
todos os exemplos positivos e projeção negativa com todos
os exemplos negativos.
• A aprendizagem do perceptron sempre tem sucesso em
tempo finito para um conjunto de treinamento finito e
separável de exemplos de treinamento.
Prof. Júlio Cesar Nievola
PPGIA - PUCPR
Especialização em Inteligência Computacional Redes
Neurais Artificiais
2
Algoritmo do Perceptron
• 1. Fazer W ser o vetor nulo.
• 2. Selecionar um exemplo de treinamento Ek (com a
correspondente classificação Ck). Isto pode ser feito de maneira
cíclica (em ordem) através dos exemplos de treinamento ou
pegando um exemplo aleatoriamente.
• 3. Se W classifica Ek corretamente, isto é, se:
{W.Ek  0 e Ck = +1} ou se {W.Ek < 0 e Ck = -1}
– Então: não fazer nada.
– Senão Passo de alteração: Modificar W somando ou
subtraindo Ek de acordo com a saída correta ser +1 ou -1:
W’ = W + CkEk.
• 4. Ir ao passo 2.
Prof. Júlio Cesar Nievola
PPGIA - PUCPR
Especialização em Inteligência Computacional Redes
Neurais Artificiais
3
Perceptron - conclusões
 Para um conjunto finito de exemplos de treinamento E, com
componentes inteiros (ou racionais), o algoritmo de
aprendizagem do perceptron, em tempo finito:
– Produzirá um vetor peso que satisfaz todos os exemplos de
treinamento (se e somente se E é separável); ou
– Abandonará e reutilizará um vetor peso (se e somente se E
é não-separável).
 Se um conjunto de exemplos de treinamento E é nãoseparável, então por definição não existe um vetor de pesos W
que classifique corretamente todos os exemplos de treinamento
em E utilizando o algoritmo de aprendizagem do perceptron. A
alternativa mais natural é encontrar um vetor de pesos W* que
classifique tantos exemplos de treinamento quanto possível de
E. Tal conjunto de pesos é chamado de ótimo.
Prof. Júlio Cesar Nievola
PPGIA - PUCPR
Especialização em Inteligência Computacional Redes
Neurais Artificiais
4
Perceptron - conclusões
 O algoritmo de aprendizagem do perceptron tem
comportamento pobre: se o algoritmo é terminado, mesmo
após um grande número de iterações, não se tem garantia da
qualidade dos pesos que são produzidos, já que o mesmo usa
somente reforço negativo, ignorando totalmente os exemplos
que são corretamente classificados.
 O algoritmo do bolso leva em conta as classificações corretas
mantendo um conjunto de pesos em separado Wbolso “no
bolso”, juntamente com o número de iterações consecutivas
para a qual Wbolso classificou corretamente os exemplos de
treinamento escolhidos.
Prof. Júlio Cesar Nievola
PPGIA - PUCPR
Especialização em Inteligência Computacional Redes
Neurais Artificiais
5
Algoritmo do Bolso
• 0. Ajustar W como o vetor nulo.
• 1. Selecionar um exemplo de treinamento, Ek, aleatoriamente
(com a correspondente classificação Ck).
• 2. Se W classifica Ek corretamente, isto é, {W.Ek  0 e Ck =
+1} ou {W.Ek < 0 e Ck = -1}
• Então:
– 2a. Se a seqüência atual de classificações corretas com W é
maior que seqüência de classificações corretas para o vetor peso
Wbolso no bolso:
» 2aa. Substitua os pesos no bolso Wbolso por W e grave o
número de vezes que ela é correta.
– Senão:
– 2b. Passo de alteração: Modifique W somando ou subtraindo Ek
em função da saída correta Ck ser +1 ou -1: W’= W + CkEk.
• 3. Vá para o passo 2.
Prof. Júlio Cesar Nievola
PPGIA - PUCPR
Especialização em Inteligência Computacional Redes
Neurais Artificiais
6
Algoritmo do Bolso
 Para problemas de tamanho médio e grande o algoritmo do
bolso normalmente não produz pesos ótimos após um razoável
número de iterações, mas produz bons pesos.
 Na execução do algoritmo do bolso não há nada que previna
um mau conjunto de pesos de ter uma “seqüência feliz” de
respostas corretas e acabe substituindo um bom conjunto de
pesos no bolso. Pior ainda, se a “seqüência feliz” for longa
então o conjunto de maus pesos pode permanecer no bolso por
um grande número de iterações.
 Para evitar isto, utiliza-se o algoritmo do bolso com catraca, no
qual, para conjuntos finitos de exemplos de treinamento tem-se
melhores resultados.
Prof. Júlio Cesar Nievola
PPGIA - PUCPR
Especialização em Inteligência Computacional Redes
Neurais Artificiais
7
Algoritmo do Bolso com Catraca
• 0. Ajustar W como o vetor nulo.
• 1. Selecionar um exemplo de treinamento, Ek, aleatoriamente
(com a correspondente classificação Ck).
• 2. Se W classifica Ek corretamente, isto é, {W.Ek  0 e Ck =
+1} ou {W.Ek < 0 e Ck = -1}, então:
– 2a. Se a seqüência atual de classificações corretas com W é
maior que seqüência de classificações corretas para o vetor peso
Wbolso no bolso:
» 2aa. Se W classifica corretamente mais exemplos de
treinamento que Wbolso :
» 2aaa. Substitua os pesos no bolso Wbolso por W e grave o
número de vezes que ela é correta.
– Senão:
– 2b. Passo de alteração: Modifique W somando ou subtraindo Ek
em função da saída correta Ck ser +1 ou -1: W’= W + CkEk.
• 3. Vá para o passo 1.
Prof. Júlio Cesar Nievola
PPGIA - PUCPR
Especialização em Inteligência Computacional Redes
Neurais Artificiais
8