INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Redes Neurais e Reconhecimento de Padrões
Reconhecimento de Padrões - Conceituação
O que é padrão ?
O que é representação ?
Beale e Jackson ([BEA91]) voltam a atenção para o termo padrão
e procuram realçar seu entrelaçamento com o termo informação:
a maior parte de conteúdo informativo que nossas 'redes neurais'
biológicas absorvem se apresentam na forma de padrões. Assim,
este texto escrito por exemplo, é apresentado em uma forma
complexa de cadeias de caracteres.
Uhr ([UHR73]) procura caracterizar reconhecimento de padrões,
analisando inicialmente os aspectos sobre a captação de
informação que os organismos vivos de modo geral apresentam.
Para Uhr, é de fundamental importância as atividades de sensação
e percepção, pois é através delas que ocorre qualquer interação
entre indivíduo e meio ambiente. É através da sensaçãopercepção que um organismo é capaz de se defrontar com um
determinado objeto (padrão) é associá-lo ao seu significado
dentro de um determinado contexto. O propósito da sensaçãopercepção é o re-conhecimento.
1
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Redes Neurais e Reconhecimento de Padrões
Reconhecimento de padrões pode ser encarado como a atividade
de mapeamento de um conjunto de instâncias de objetos/entidades
para um conjunto de nomes-caracterizadores dos referidos
objetos/entidades. Tipos de padrões de interesse não se limitam
apenas a objetos concretos tais como figuras, letras, dígitos, mas
também entidades abstratas como por exemplo, a beleza de uma
mulher, uma partitura de uma música, a profundidade de um
teorema matemático ou mesmo a aceptividade a um determinado
aroma para uma determinada pessoa.
FU ([FU76]) relata o fato de que reconhecimento de padrões está
intimamente relacionado com a descrição e classificação de
medidas obtidas de processos físicos ou mentais.
Beale e Jackson ([BEA91]) também colocam que o objetivo da
tarefa de reconhecimento de padrões é a classificação.
Jain e Mao ([JAI94]), Andrews ([AND72]), Bezdek ([BEZ81])
entre outros também destacam a classificação como objetivo
primordial da tarefa de reconhecimento de padrões.
2
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Redes Neurais e Reconhecimento de Padrões
Reconhecimento de Padrões – Uma definição ([BEZ81])
"Quite simply, pattern recognition is a search for structure in data."
Na definição acima, Bezdek ressalta três aspectos: a tarefa de
procura ou busca (search), a estrutura (structure) e os dados
(data).
Os dados podem ser de natureza qualitativa, quantitativa ou
ambas; podem ser numéricos, pictoriais, texturais, linguísticos ou
qualquer dessas combinações. Exemplos de dados: registros
médicos, fotos aéreas, posições das galáxias, impressões digitais,
perfil psicológico, componentes químicos, aspectos demográficos,
etc.
A procura ou busca refere-se às técnicas que se utilizam para
processar os dados componentes do padrão. Uma exemplo de
técnica de busca, que é baseada em heurística, é a do
"olhômetro" (eyeball techinique, [BEZ81]). Outro exemplo de
técnica, porém mais rigorosa em termos algorítmicos baseia-se
no uso da análise estatística.
A estrutura representa a maneira em que os dados estarão
organizados, ou seja, como eles estão dispostos. Está, portanto,
ligada à caracterização das relações que envolvem os dados
componentes do padrão.
3
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Redes Neurais e Reconhecimento de Padrões
Padrão: um exemplo - Uma figura de borboleta ([BEZ81])
Os dados são de natureza pictorial. Os dados são os pontos.
Mas os dados por si só não dizem nada, não veiculam
informação alguma
A estrutura do padrão indica a disposição geográfica dos
pontos (dados), caracterizando as intra e inter-relações;
através da estrutura poderiam também ser representadas as
diferentes texturas (caso houvessem) dos dados, etc.
É então o binômio dados-estrutura que apresentará teor
informativo, isto é, permitirá que se faça um mapeamento do
padrão em questão para algum universo representativo de
objetos/entidades.
A busca ou procura de estruturas em dados seria a ponte, o
processo de mapeamento do padrão até o teor informativo
intrínseco a ele. Existem diversas técnicas de procura, cada
uma apresentando suas vantagens e desvantagens.
4
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Redes Neurais e Reconhecimento de Padrões
O processo de reconhecimento de padrões (pattern recognition)
Padrão
Dados (explícitos)
Estrutura (implícito)
Descritor do padrão
Técnicas para explicitação das estruturas do padrão
Caracterização do padrão através de suas estruturas
Técnicas para reconhecimento de padrões [FU82]
Técnicas sintáticas (estrutural)
Técnicas discriminantes (decisão-teórica)
5
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Redes Neurais e Reconhecimento de Padrões
Técnicas sintáticas para reconhecimento de padrões
A idéia nesta abordagem é representar o padrão através de uma
estrutura que se caracterize por ser uma sentença de alguma
linguagem
Formalismos: Gramáticas e Reconhecedores para
representação/descrição do padrão
Exemplo: Gramática para Cromossomos Medianos
Cromossomo mediano
X = cbbbabbbbdbbbbabbbcbbbabbbbdbbbbabbb
Gramática Gm = (VNm, VTm, Pm, S)
onde VNm = {S, A, B, D, H, J, E, F }
VTm = { a, b, c, d } = {∩, |, ∪, ∧}
Pm = { S → AA, A → cB, B → FBE,
B → HDJ, D → FDE, D → d,
F → b, E → b, H → a, J → a }
6
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Redes Neurais e Reconhecimento de Padrões
Técnicas discriminantes para reconhecimento de
padrões
Andrew ([AND72]) descreve o problema de reconhecimento
de padrões como uma transformação a partir do universo P do
padrão em questão, para o universo de características F e daí
para o universo de classificação C
P → F → C
Pré-Processamento do padrão
P - Universo do Padrão
X = ( x1, x2, x3, x4, ... , xn )
n características
Seleção/Extração de r características (r < n)
F - Universo de Características
Y = ( y1, y2, y3, y4, ... , yr )
r características
Base para sistema de tomada de decisão para classificação
C - Universo de classificação
K classes distintas
Redes neurais enquadram-se como técnicas discriminantes
para classificação (reconhecimento) de padrões
7
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Homem e Máquina (computador)
O homem é mais inteligente que a máquina
Mas, por exemplo, um computador calcula a multiplicação de
dois inteiros com 9 dígitos mais rápido que o homem
Já o homem, por exemplo, visualiza e “processa” um cenário
melhor que o computador
Onde está a diferença ? Provavelmente na natureza do “design”
do homem e no “design” do computador
Numa primeira investigação, o cérebro humano é uma
massa cinzenta homogênea
No interior do computador encontram-se inúmeros “chips”
de silício
computador é uma máquina de processamento serial de
altíssima velocidade se comparada com o cérebro humano
que apresenta uma natureza de operação (“processamento”)
em paralelo
Tarefas mais complexas (reconhecimento visual e sonoro p. ex.)
requerem, para melhor performance, processamento paralelo
8
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Redes neurais artificiais - Propósito ⇒ Tentar implementar em
computador as diretrizes que norteiam o processamento (paralelo) de
soluções que o cérebro humano executa para resolver “problemas
complexos”.
Redes neurais artificiais - Aprendizado ⇒ Uma das
características mais marcantes do cérebro humano é o fato de o
mesmo ter aptidão para aprender coisas e fatos por si só. E o
aprendizado é um aspecto desejável na implementação de Redes
Neurais Artificiais.
A Estrutura do Cérebro Humano
O cérebro humano é uma das coisas mais complicadas, bastante
estudada em detalhes, porém muito pouco compreendida.
O cérebro humano: contém aproximadamente dez mil milhões
(1010) de unidades básicas denominadas neurônios.
Cada neurônio se conecta com aproximadamente 10.000 (104)
outros neurônios.
Neurônio ⇒ Unidade básica do cérebro e possui 3 partes:
(1) Corpo da célula (soma)
(2) Dendritos
(3) Axônio
9
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
A Estrutura e Funcionamento dos Neurônios
Os dendritos se conectam ao corpo da célula (soma).
Os dendritos têm por função receber as informações ou
impulsos nervosos oriundos de outros neurônios e conduzi-los
até o soma.
A informação que chega ao soma é “processada” e novos
impulsos nervosos são transmitidos pelo axônio para os
dendritos dos outros neurônios seguintes (aqueles
aproximadamente 104 conectados !!).
Sinapse é o nome do ponto de contato entre o terminal axônico
de um neurônio e o dendrito de outro neurônio.
É pelas sinapses que os neurônios se unem funcionalmente
formando as redes neurais.
As sinapses controlam a transmissão dos impulsos nervosos
entre os nodos (neurônios) da rede neural.
O efeito das sinapses é variável e é esta variação que dá ao
neurônio a capacidade de adaptação e, consequentemente, dá à
rede neural a capacidade de aprender
10
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
A Estrutura e Funcionamento dos Neurônios
11
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
O Processo de Comunicação no Cérebro
A comunicação no cérebro ocorre de duas maneiras:
Sinais químicos através das sinapses
Sinais elétricos dentro do corpo do neurônio (soma)
A membrana que envolve o exterior do soma pode gerar impulsos
nervosos (elétricos).
O corpo do neurônio (soma) ao receber os sinais dos outros
neurônios (os aproximadamente 104 que estão conectados),
combina-os e, se o valor resultante for acima do limiar (threshold)
de excitação do neurônio, um impulso elétrico é produzido e
propagado para os neurônios seguintes.
Há uma diferença de potencial (em Volts) entre o interior e o
exterior do neurônio, ocasionada pela diferença de concentração
de potássio (interno) e de sódio (externo).
No interior do soma, a concentração de íons de potássio cria um
potencial elétrico de –70mV (potencial de repouso) em relação ao
exterior.
12
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
O Processo de Comunicação no Cérebro
Se os impulsos da sinapse reduzirem o potencial de repouso de –
70 mV para –50 mV no soma, o neurônio propaga, através do
axônio, os impulsos nervosos para a região das conexões
sinápticas, que liberarão moléculas neurotransmissoras que
inibirão ou excitarão pulsos elétricos no próximo neurônio.
Assim, o potencial de disparo de um neurônio é determinado pelo
acúmulo de um grande número de entradas inibitórias e
excitatórias, medido pelo soma (corpo da célula) num pequeno
intervalo de tempo.
Depois de gerar um impulso, o neurônio entra num período de
refração, durante o qual retorna ao seu potencial de repouso
enquanto se prepara para a geração de um novo impulso.
13
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Modelando o Neurônio Básico (McCulloch & Pitts, 1943)
A função básica de um neurônio biológico é “somar” as suas
“entradas” (inputs) e produzir uma “saída” (output) se a “soma
das entradas” for maior que um determinado “valor” limiar
(threshold) previamente conhecido do neurônio.
Dendritos = canais de recepção das “entradas”
Axônio
= canal de transmissão da “saída”
Sinapses = Junções dos axônios de vários neurônios com
os dendritos de um determinado neurônio
Na rede neuronal, algumas sinapses são “bons conctores”,
enquanto que outras sinapses são “maus conectores”
Conclusão: O modelo básico de neurônio artificial deve registrar
estas importantes características do neurônio biológico.
O Modelo de McCulloch & Pitts (1943)
A saída (output) do neurônio será ou “on” ou “off”.
A saída (output) depende apenas das entradas (inputs).
As sinapses serão representadas por pesos: assim, uma sinapse
que é “bom conector” terá um peso maior, enquanto que uma
sinapse que é um “mau conector” terá um peso menor
14
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Modelando o Neurônio Básico (McCulloch & Pitts, 1943)
15
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Modelando o Neurônio Básico (McCulloch & Pitts, 1943)
Formulação matemática
Supondo que haja n “inputs”, então existem n pesos associados às
n entradas.
O neurônio calcula a soma ponderada das n entradas:
Soma =
Peso do “input” 1 * “input 1” +
Peso do “input” 2 * “input 2” +
Peso do “input” 3 * “input 3” + .... +
Peso do “input” n * “input n”
= w1 x1 + w2 x2 + w3 x3 + .... + wn xn
=
A soma é comparada com um certo valor do neurônio, o “valor
limiar” (threshold value). Se a soma é maior que o valor
“threshold”, então a saída do neurônio é 1. Se a soma do neurônio
é menor que o valor “threshold”, então a saída do neurônio é 0.
16
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Modelando o Neurônio Básico (McCulloch & Pitts, 1943)
Formulação matemática – Adaptação do valor “threshold”
Uma alternativa para a formulação matemática do neurônio é
representar o “valor limiar” (threshold value) do neurônio como a
entrada 0 (“input” 0) sempre com valor fixo e igual a 1, e o peso
do “input” 0 assumir sempre o valor -θ
θ, onde θ é o valor
“threshold” do neurônio
Desta forma, uma entrada com n inputs será representada por n+1
“inputs”, onde a “input” 0 representará o valor “threshold” do
neurônio
17
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Modelando o Neurônio Básico (McCulloch & Pitts, 1943)
Deve-se ressaltar que o modelo de neurônio de McCulloch & Pitts
é de fato um modelo, e não uma cópia de um neurônio biológico
real.
Frank Rosemblatt denominou este modelo de neurônio de
“perceptron”, em 1962. Em seu livro “Principles of
Neurodynamics”, ele descreve os perceptrons como redes
simplificadas nas quais certas propriedades do sistema nervoso
real (biológico) são exageradas, enquanto outras são ignoradas.
Cita ainda que os perceptrons não são cópias detalhadas de
qualquer sistema nervoso real.
Aprendizado dos Perceptrons
Conectar perceptrons permite produzir “redes” que podem
reconhecer/aprender coisas. Precisamos contudo treinar a “rede”
para que ela possa reconhecer alguma coisa.
Devemos procurar aplicar a mais simples regra possível de
aprendizagem de modo a manter o controle da “rede de
perceptrons” no sentido de entender seu esquema de
reconhecimento de padrões.
Com relação ao processo de aprendizagem, em geral, “bom
comportamento” é incentivado, enquanto que “mau
comportamento” é desestimulado
18
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Aprendizado dos Perceptrons
A estratégia de aprendizado de um perccptron ocorre pelo seu
“auto-aprendizado” a partir de seus próprios erros:
Se o perceptron produz uma saída (output) incorreto,
desejamos reduzir as chances desta situação ocorrer novamente.
Se o perceptron produz uma saída correta, nada é necessário
fazer.
Exemplo de Aprendizado
Suponha que desejemos ter um perceptron capaz de distinguir
entre duas classes de objetos: classe A e classe B. A e B poderiam
ser, por exemplo, objetos pesados X leves, altos X baixos, de cor
clara X de cor escura, etc...
Para exemplificar, vamos supor que os objetos da classe A sejam
letras “A” escritas à mão livre num espaço de 32 X 32 pixels (de
cor ou preta ou branca), e os objetos da classe B sejam letras “B”
escritas à mão livre num espaço de 32 X 32 pixels (de cor ou preta
ou branca).
19
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Aprendizado dos Perceptrons
Exemplo de Aprendizado
No exemplo, o perceptron terá 32 x 32 = 1024 “inputs”, um para
cada um dos pixels que compõe as imagens de letras A e B.
Vamos definir previamente que o perceptron deve dar como
resposta o valor 1 se o padrão de entrada for um “A” e deve dar
como resposta o valor 0 se o padrão de entrada for um “B”.
Inicialmente, os 1024 pesos (“sinapses”) de cada uma das 1024
“inputs” são gerados aleatoreamente, assim como o “threshold” do
perceptron. Neste momento, o perceptron não sabe distinguir
objetos entre classe A e classe B.
Apresenta-se um padrão ao perceptron: se for apresentado um
“A”, o perceptron fará a soma ponderada Σ X.W que será
comparada ao valor “threshold” θ. Se a soma exceder θ, o
perceptron apresenta “output” 1, que é o valor de fato esperado
para um padrão de “A”. Porém, se o “output” é 0, isto é um erro, e
o perceptron deve então se “auto-ajustar” para produzir um
“output” 1. Como fazer isto ? Neste exemplo, deve-se tentar
aumentar os pesos a fim de forçar a soma ponderada ultrapassar o
valor “threshold” θ.
20
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Aprendizado dos Perceptrons
Exemplo de Aprendizado
Temos então a diretriz geral da regra para treinar o perceptron
fazendo com que o mesmo aprenda:
Ao apresentar um padrão de “A” para o perceptron e o mesmo
responder 0 (indicando “B”) devemos aumentar os pesos para
forçar o perceptron a responder 1.
Ao apresentar um padrão de “B” para o perceptron e o mesmo
responder 1 (indicando “A”) devemos diminuir os pesos para
forçar o perceptron a responder 0.
Esta “regra de aprendizagem” (ou “regra de treinamento”) é uma
variante da regra proposta em 1949 por Donald Hebb e, por isso, é
conhecida como Aprendizagem Hebbiana
Uma vez que o aprendizado é “guiado” para aquilo que queremos
que o perceptron responda, dizemos então que temos um processo
de aprendizado supervisionado (supervised learning)
21
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
O Algoritmo Básico de Aprendizado dos Perceptrons
1.
Inicializar os pesos (“sinapses”) e o valor “threshold”:
• Seja wk(t), (0 ≤ k ≤ n) os pesos do padrão k no tempo t, e θ
o valor “threshold” do neurônio.
• Faça w0 = -θ e x0 = 1 sempre !!
• Inicialize wk(0) para pequenos valores randômicos,
inicializando assim todos os pesos e valor “threshold”
2.
Apresente um padrão de entrada e a saída desejada d(t):
• Apresente “input” x0 , x1 , x2 , x3 , .... , xn e “output” d(t),
que terá valor 0 ou 1
3.
Calcular “output” produzido pelo perceptron y(t) :
y(t) = 1 se S > 0
y(t) = 0 se S < 0
4.
Adaptar os pesos do perceptron:
Se y(t) = d(t), está correto então: wk(t+1) = wk(t) senão:
Se y(t) = 0 e d(t) = 1, então: wk(t+1) = wk(t) + xk(t)
Se y(t) = 1 e d(t) = 0, então: wk(t+1) = wk(t) - xk(t)
22
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Algoritmo: Aprendizado dos Perceptrons - Modificações
Proposta de alteração 1: introduzir um fator multiplicativo η tal
que 0 < η ≤ 1 a fim de desacelerar o processo de adaptação de
pesos:
4.
Adaptar os pesos do perceptron – com fator η
Se y(t) = d(t), está correto então: wk(t+1) = wk(t) senão:
Se y(t) = 0 e d(t) = 1, então: wk(t+1) = wk(t) + ηxk(t)
Se y(t) = 1 e d(t) = 0, então: wk(t+1) = wk(t) - ηxk(t)
23
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Algoritmo: Aprendizado dos Perceptrons - Modificações
Proposta de alteração 2 (Widrow & Hoff):
Efetuar um mudança “intensa” nos pesos quando a soma
ponderada Σ X.W está “muito longe” do valor “output”
desejado
Efetuar um mudança “suave” nos pesos quando a soma
ponderada Σ X.W está “muito perto” do valor “output”
desejado
Regra-Delta Widrow-Hoff
A diferença entre o valor desejado e o valor obtido é chamada de
erro
O ajuste de pesos ocorre de forma proporcional ao “tamanho” do
erro
∆ = d(t) - y(t)
∆ = 0 se d(t) = y(t)
∆ = +1 se d(t) = 1 e y(t) = 0
∆ = -1 se d(t) = 0 e y(t) = 1
24
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Algoritmo: Aprendizado dos Perceptrons - Modificações
Proposta de alteração 2 (Widrow & Hoff):
Regra-Delta Widrow-Hoff
4.
Adaptar os pesos do perceptron – Regra Delta Widrow-Hoff
∆ = d(t) - y(t)
wk(t+1) = wk(t) + η ∆ xk(t)
onde 0 < η ≤ 1
Quando o algoritmo de treinamento de perceptron utilizar a
Regra-Delta Widrow-Hoff, o perceptron é chamado ADALINE
(adaptative linear neurons)
Quando os muitos perceptrons ADALINE são interconectados
chamamos a “rede de perceptrons” de MADALINE (multiple
adaptative linear neurons)
25
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptrons – uma perspectiva vetorial
Se representarmos as n entradas (“inputs”) do padrão e a “input” 0
(que sempre vale 1) do “threshold” num vetor X, podemos encarar
o algoritmo de aprendizagem dos perceptrons de uma forma
vetorial: X = (x0, x1, x2, ..., xn)
Ao encarar o algoritmo de aprendizagem dos perceptrons forma
vetorial, os pesos (“sinapses”) serão também representados de
forma vetorial (obs: o peso w0 sempre será igual a -θ, o valor
“threshold” do neurônio): W = (w0, w1, w2, ..., wn)
A saída (“output”) do perceptron será sempre ou 0 ou 1 de modo a
classificar duas classes distintas de padrões, digamos classe A e
classe B.
Sob o ponto de vista vetorial, isto significa que o perceptron irá
tentar “descobrir”, através do algoritmo de aprendizagem, uma
“linha divisória” que separa os padrões da classe A dos padrões
da classe B.
Se a dimensão dos padrões de entrada é n = 1 ou n = 2, então
a “linha divisória” será uma reta.
Se a dimensão dos padrões de entrada é n = 3, então a “linha
divisória” será um plano.
Se a dimensão dos padrões de entrada é n > 3, então a “linha
divisória” será um hiperplano.
26
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptrons – uma perspectiva vetorial
Exemplo 1 - Suponha a classificação de pessoas como aptas
ou não aptas para jogar basquete. Suponha que a classificação
se baseia apenas no peso e na altura das pessoas. Temos
então:
Entradas (“input”): (1) peso (2) altura ⇒ dimensão do padrão: n = 2
Classificação:
“Classe A” : pessoa apta
“Classe B” : pessoa não apta
Saída (“output”):
1 para pessoa apta e 0 para pessoa não apta
Neste caso de n = 2, o perceptron tentará “construir” a reta que é a
“linha divisória” dos padrões Classe A e Classe B.
27
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptrons – uma perspectiva vetorial
Exemplo 2 - Suponha um jogo de dados onde o jogador
lança três distintos dados, A, B e C, e ganha o jogo se e
somente se os três dados lançados apresentarem número
menor que 4. Caso contrário o jogador perde o jogo. Então:
Entradas (“input”): (1) Número do Dado A (2) Número do Dado B
(3) Número do Dado C ⇒ dimensão do padrão:
n=3
Classificação:
“Classe A” : Jogador Ganha o Jogo
“Classe B” : Jogador Perde o Jogo
Saída (“output”):
1 para Ganha o Jogo e
0 para Perde o Jogo
Neste caso de n = 3, o perceptron tentará “construir” o plano que é a
“linha divisória” dos padrões Classe A e Classe B.
28
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptrons – uma perspectiva vetorial
Exemplo 3 - Vamos supor que os padrões a serem
reconhecidos pelo perceptron sejam letras “A” escritas à mão
livre num espaço de 32 X 32 pixels (de cor ou preta ou
branca), e letras “B” escritas à mão livre num espaço de 32 X
32 pixels (de cor ou preta ou branca). Temos então:
Entradas (“input”): (1) Cor do pixel 1 da matriz de 32 X 32 pixels
(2) Cor do pixel 2 da matriz de 32 X 32 pixels
(3) Cor do pixel 3 da matriz de 32 X 32 pixels
... ....
(1024) Cor do pixel 1024 da matriz de 32 X 32
pixels
⇒ dimensão do padrão: n = 1024
Classificação:
“Classe A” : letras A
“Classe B” : letras B
Saída (“output”):
1 para letras A e
0 para letras B
Neste caso de n = 1024, onde n > 3, o perceptron tentará “construir”
um hiperplano que é a “linha divisória” dos padrões Classe A e
Classe B.
Obs.: Obviamente, é impossível “desenhar” o espaço das “inputs”
com dimensão n > 3 !!
29
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptrons – uma perspectiva vetorial
Sintetizando:
O perceptron tenta, através do ajuste dos valores do vetor de pesos
W via algoritmo de aprendizagem, gerar a “linha divisória” que
classifica padrões em duas classes distintas (denominadas aqui
genéricamente de Classe A e Classe B)
No exemplo acima, o perceptron parte de uma “linha divisória”
inicial gerada aleatoriamente (linha 0) e, progressivamente ao ser
“treinado” tem seu vetor de pesos ajustado até conseguir gerar a
verdadeira “linha divisória” que separa os padrões do tipo Classe A
e do tipo Classe B. No exemplo, a “linha divisória” 30 já classifica
os padrões, porém a continuação do algoritmo de treinamento
permite a obtenção da “linha divisória” 35.
30
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptrons – Limitação
É possível provar matematicamente que o perceptron é capaz de
“descobrir” via algoritmo de aprendizagem (Regra Delta –
Widrow-Hoff) a “linha divisória” entre dois padrões distintos
caso essa “linha divisória” exista !
Existem porém situações em que as classes de padrões não são
“linearmente separáveis”. Neste caso o perceptron falha ao
tentar distinguir os padrões das (genéricas) Classe A e Classe B.
Em 1969 Minsky & Pappert em seu livro Perceptrons
apresentaram um exemplo de incapacidade de reconhecimento dos
perceptrons: O problema do OU-Exclusivo (XOR problem)
Problema do OU-Exclusivo (XOR problem)
Existe “linha divisória” para o problema do OU-Exclusivo ?
31
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptrons – Limitação
Problema do OU-Exclusivo (XOR problem)
Vamos exemplificar o problema do OU-exclusivo (XOR problem)
através da seguinte situação:
Suponha um jogo de moedas onde o jogador lança duas
moedas distintas, moeda A e moeda B e ganha o jogo se e
somente se uma única moeda (ou a moeda A ou a moeda B)
apresentar cara. Caso contrário o jogador perde o jogo. Então:
Entradas (“input”)
Classificação
Moeda A: Cara (1) ou Coroa(0) “Classe A” : Ganha o Jogo
Moeda B: Cara (1) ou Coroa(0) “Classe B” : Perde o Jogo
Não existe “linha divisória” para o Jogo. O perceptron é incapaz
de reconhecer o padrão de ganhador e o padrão de perdedor deste
jogo !
32
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptron Multicamada (Multilayer perceptron)
Minsky & Papert (1969) em seu livro Perceptrons apresentaram a
limitação do perceptron com o problema do OU-exclusivo (XOR
problem)
A “área” de redes neurais sofreu um grande impacto então e
somente em 1986 com a publicação do livro Parallel Distributed
Processing dos autores McClelland & Rumelhart o tema das redes
neurais voltou a despertar interesse.
McClelland & Rumelhart (1986) apresentaram o modelo de
perceptrons multicamadas (multilayer perceptrons) visando
superar a limitação do perceptron (com relação ao XOR problem)
Werbos (1974) e Parker (1982) mostraram ter apresentado
trabalhos semelhantes ao de McClelland & Rumelhart (1986),
porém é atribuído a estes últimos o mérito do “renascimento” das
redes neurais.
33
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Alterando o modelo de perceptron – Tentativa 1
Para o problema do OU-exclusivo (XOR problem) pode-se tentar
utilizar mais de um perceptron, cada um com o objetivo específico
de identificar pequenos “pedaços” “linearmente separáveis” dos
padrões e combinar as saídas destes perceptrons:
À primeira vista parece que a proposta funciona, porém, ao se
analisar mais detalhadamente ver-se-á que não funciona:
O problema deve-se ao fato de cada neurônio receber “inputs”
ou 0 ou 1 e assim, o neurônio receptor não “conhece” os valores
processados pelos neurônios anteriores que o “alimentaram”.
Aprendizagem consiste em “calcular” os pesos (“intensidades”)
das conexões sinápticas dos neurônios e a intensidade 0 ou 1
recebida pelo neurônio impossibilita sua adaptação sináptica.
34
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
O problema do “output” ou 0 ou 1 dos neurônios
O “output” do neurônio é função da soma ponderada de
seus “inputs”: Quando esta soma é maior que o “threshold”
do neurônio, o “output” é 1. Caso contrário, o “output” é 0.
Para que o “output” represente melhor a “intensidade” da soma
ponderada em relação ao “threshold” pode-se utilizar não a
“função degrau”, mas alguma função com alguma “declividade
suave”
35
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptron Multicamada (Multilayer perceptron)
O modelo perceptron multicamada apresenta no mínimo 2
camadas: camada de entrada (input layer) e camada de saída
(output layer). Se a topologia da rede utilizar mais camadas, cada
uma delas é denominada camada escondida (hidden layer)
Além disso, o “output” de cada neurônio, não é mais
necessariamente o valor 0 ou o valor 1, mas sim um valor neste
intervalo [0,1] calculado por uma função “sigmoidal” (com
“declividade suave”)
E pelo fato de se ter mudado a “função de threshold” de cálculo
do “output” do neurônio, é necessário alterar a regra de
aprendizagem do perceptron multicamada.
36
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Aprendizado do Perceptron Multicamada
A regra de aprendizagem para o perceptron multicamada é a
chamada regra delta generalizada (generalized delta rule) ou
regra da retropropagação (backpropagation rule) proposta em
1986 por Rumelhart, McClelland e Willians
Lembre-se que aprendizagem é ajuste de pesos (“sinapses”) da
rede neural através do seu treinamento via apresentação dos
padrões de interesse.
Estratégia de aprendizagem
1) Definir uma função erro que represente a diferença entre o
“output” efetivamente calculado pelo neurônio e o “output” que é
esperado que o neurônio forneça. Ao longo do treinamento, a
meta é diminuir continuamente o valor desta função erro.
2) Ao se apresentar algum padrão para a rede, os neurônios da
output layer fornecem seus “outputs” que são ajustados pela
função erro.
3) Como o erro nos neurônios na output layer foi causado
“diretamente” pelos neurônios da hidden layer, a “taxa de ajuste”
efetuada na output layer é retropropagada para a hidden layer.
4) E finalmente, como o erro nos neurônios na hidden layer foi
causado “diretamente” pelos neurônios da input layer, a “taxa de
ajuste” efetuada na hidden layer é retropropagada para a input
layer.
37
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Matemática do Aprendizado do Perceptron Multicamada
Definições de símbolos:
Função erro para o padrão p
“output” desejada (alvo – target) para o padrão p no nodo
(neurônio) j
“output” efetivamente fornecido para o padrão p pelo
nodo (neurônio) j
Peso “sináptico” entre o nodo (neurônio) i e o nodo
(neurônio) j
Vamos definir a seguinte função erro:
(1)
O “output” de cada nodo (neurônio) j para o padrão p pode ser
assim representado:
(2)
38
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Matemática do Aprendizado do Perceptron Multicamada
O “output” para cada nodo (neurônio) j é calculado por uma
“função sigmoidal” fj que tem como variável independente a
soma ponderada netj. Assim temos:
(3)
Vamos escrever:
(4)
O segundo termo de (4) vale:
(5)
39
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Matemática do Aprendizado do Perceptron Multicamada
Podemos caracterizar a taxa de variação do erro em função da taxa
de mudança dos pesos do nodo (neurônio) j da seguinte forma:
(6)
Assim a igualdade (4) fica:
(7)
Minimizar o valor do erro Ep significa “ conduzir” a mudança de
pesos proporcional a δpj opi ou seja:
(8)
Precisamos agora saber o valor de δpj para cada um dos nodos
(neurônios) da rede. Sabendo este valor, podemos então
minimizar o erro Ep.
40
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Matemática do Aprendizado do Perceptron Multicamada
Tomando-se a equação (6) obtemos:
(9)
Considerando o segundo termo de (9) e a partir de (3) temos:
(10)
Considerando o primeiro termo de (9). A partir de (1) podemos
diferenciar Ep em relação a Opj e obtemos:
(11)
Assim, para nodos j (neurônios) da output layer temos:
(12)
O valor acima vale para nodos da output layer, porquê nesta
camada é conhecido o valor “alvo” desejado tpj.
41
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Matemática do Aprendizado do Perceptron Multicamada
Para nodos (neurônios) da hidden layer, cujo valor “alvo” não é
conhecido podemos escrever o primeiro termo de (9) assim:
(13)
(14)
Assim, para nodos j (neurônios) da hidden layer temos:
(15)
42
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Matemática do Aprendizado do Perceptron Multicamada
As equações (12) e (15) representam a taxa de variação da função
erro em relação aos pesos na rede, fornecendo um método de
redução do erro Ep.
(12)
(15)
A função erro Ep é proporcional aos erros nos nodos (neurônios)
subsequentes de modo que o erro tem que ser calculado
inicialmente para os nodos(neurônios) da output layer (usando
(12)) e então ser retropropagado (backpropagation) este “ajuste”
para os nodos da camada anterior.
É a retropropagação do “ajuste” do erro de onde deriva o nome da
rede perceptron multicamada como rede backpropagation.
43
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Matemática do Aprendizado do Perceptron Multicamada
Resta apenas definir a função f usada nas equações (12) e
(15). Esta deve ser uma função sigmoidal continuamente
derivável. Uma função sigmoidal comumente escolhida é a
seguinte:
onde 0 < f(net) < 1 e k é uma constante positiva
que controla a “expansão” da função.
A principal razão de uso desta função deve-se ao fato de sua
derivada ser simples sob o ponto de vista matemático. Dado que
Temos então:
44
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Algoritmo – Aprendizado perceptron multicamada
1.
Inicializar os pesos (“sinapses”) e o valor “threshold”:
• Seja wk(t), (0 ≤ k ≤ n) os pesos do padrão k no tempo t, e θ
o valor “threshold” do neurônio.
• Faça w0 = -θ e x0 = 1 sempre !!
• Inicialize wk(0) para pequenos valores randômicos,
inicializando assim todos os pesos e valor “threshold”
2.
Apresente um padrão de entrada e a saída desejada :
• Apresente “input” Xp = x0 , x1 , x2 , x3 , .... , xn : n é o
número de nodos (neurônios) da input layer.
• Apresente “output” desejado (valor dos neurônios da output
layer): Tp = t1 , t2 , t3 , .... , tm : m é o número de nodos da
output layer.
• Para propósitos de classificação todo elemento de Tp vale 0,
exceto um único elemento tk que valerá 1, indicando a classe
a que pertence o padrão de entrada Xp.
3.
Calcular valor atual de “output”: cada camada calcula
e passa este valor para a próxima camada. A camada final
(output layer) calcula opj
45
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Algoritmo – Aprendizado perceptron multicamada
4.
Adaptar os pesos: Partindo da output layer e efetuando
backpropagation
onde wij representa o peso do nodo (neurônio) i para o nodo
(neurônio) j, η é um termo de ganho e δpj o termo do erro para o
padrão p sobre o nodo (neurônio) j.
Para os nodos (neurônios) da output layer:
Para os nodos (neurônios) da hidden layer:
onde o somatório envolve os K nodos (neurônios) da camada
anterior ao nodo (neurônio) j.
46
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptron multicamada e o problema do OU-exclusivo
Desde que o problema do OU-exclusivo (XOR problem) foi
mostrado como sendo um “barreira” aos perceptrons, tornou-se o
paradigma de referência de julgamento de performance de
diversos sistemas neurais.
Relembrando o problema do OU-exclusivo (XOR problem):
47
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptron multicamada e o problema do OU-exclusivo
Uma solução para o problema do OU-exclusivo (XOR problem)
Como o padrão de entrada neste caso envolve apenas as “inputs”
00, 01, 10 ou 11, é possível utilizar a função degrau f ao invés de
uma função sigmoidal.
Deve-se observar que esta topologia de rede utiliza apenas duas
camadas (input layer e output layer)
48
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptron multicamada e o problema do OU-exclusivo
Outra solução para o problema do OU-exclusivo (XOR problem)
Como o padrão de entrada neste caso envolve apenas as “inputs”
00, 01, 10 ou 11, é possível utilizar a função degrau f ao invés de
uma função sigmoidal.
Deve-se observar que esta topologia de rede utiliza apenas duas
camadas (input layer e output layer)
49
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Comportamento de aprendizado do perceptron multicamda
Conforme apresentado anteriormente, o aprendizado da rede
perceptron multicamada baseia-se na minimização da função erro
Ep (ou função energia) da rede. Basicamente, Ep representa o
quanto a resposta de saída da rede se difere da resposta desejada
de saída da rede.
Observa-se que a função erro é função dos pesos e “inputs” da
rede
À medida em que a rede for sendo treinada, é possível traçar o
gráfico mostrando a variação da função erro Ep.
50
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Comportamento de aprendizado do perceptron multicamda
Suponha inicialmente um padrão de entrada de dimensão
n = 1 (por exemplo, a nota final do aluno em química):
Desta forma a função erro Ep está em função de apenas um peso (e
um “input”) advindo do nodo (neurônio) de entrada
Assim, ao longo do treinamento da rede multicamada Ep irá variar
em função do único peso w1 que ela ajusta via algoritmo
backpropagation (à medida em que se apresentam padrões para o
treinamento). Podemos visualizar esta variação num gráfico
bidimensional:
51
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Comportamento de aprendizado do perceptron multicamda
Suponha agora um padrão de entrada de dimensão n = 2
(por exemplo, os “inputs” binários do OU-exclusivo):
Desta forma a função erro Ep está em função de dois pesos (e dois
“inputs”) advindo dos nodos (neurônios) de entrada
Assim, ao longo do treinamento da rede multicamada Ep irá variar
em função de dois pesos w1 e w2 que ela ajusta via algoritmo
backpropagation (à medida em que se apresentam padrões para o
treinamento). Podemos visualizar esta variação num gráfico
tridimensional:
52
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Comportamento de aprendizado do perceptron multicamda
Não podemos visualizar gráficos da função erro para padrões para
padrões de dimensão n ≥ 2 pois precisaríamos de no mínimo 4 ou
mais eixos de apresentação
Devemos então tentar visualizar o comportamento da
minimização da função erro Ep em gráficos 3-D, imaginando que
todos os n ≥ 2 pesos que influenciam Ep estão devidamente
representados no gráfico 3-D
53
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Comportamento de aprendizado do perceptron multicamda
Outra forma de visualizar a superfície da função erro Ep é
imaginá-la uma cama elástica larga inicialmente em repouso num
primeiro momento, e em seguida soltar diversas bolas pesadas (de
chumbo por exemplo) em diversos pontos da cama elástica.
Queremos descobrir o ponto “mais fundo” da cama elástica após
soltar todas as bolas sobre a mesma.
Devemos considerar um espaço vetorial de dimensão n ≥ 1 onde
cada um dos n eixos representa um determinado peso w. O
problema é descobrir o vetor de pesos W que melhor classifique
os padrões desejados.
54
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptron multicamada no papel de Classificador
Conforme apresentado anteriormente, o perceptron
“simples” pode não conseguir encontrar a “linha divisória”
que separa dois padrões distintos (Classe A e Classe B),
conforme visto no exemplo do problema do OU-exclusivo.
Com o perceptron multicamada (multilayer perceptron) foi
mostrado que é possível resolver o problema do OU-exclusivo, ou
seja encontrar uma “linha divisória” para os padrões Classe A
(00, 11) e Classe B (01, 10) em questão. Para isso, foi preciso
(A) Organizar os nodos (neurônios) da rede em camadas
(B) Utilizar uma função “threshold” que não a função degrau
(“output” ou 0 ou 1)
(C) Propor novo algoritmo de treinamento para a rede.
55
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptron multicamada no papel de Classificador
Considere um nodo I1 (neurônio) que se encontre na input layer de
uma rede neural, “alimentado” pelos n “inputs” do padrão
(camada “retina”).
O nodo I1 “alimentado” pelos n “inputs” é capaz de gerar uma
“linha divisória” classificando, digamos, Classe A e Classe B.
Suponha, por exemplo, um padrão de dimensão n = 2. Assim a
“linha divisória” será uma reta.
56
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptron multicamada no papel de Classificador
Considere agora que a Input layer possui um segundo nodo
I2, capaz de gerar uma “linha divisória” classificando,
digamos, Classe C e Classe D. Supondo ainda um padrão
de dimensão n = 2 temos:
57
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptron multicamada no papel de Classificador
Combinando as saídas dos nodos (neurônios) I1 e I2 obtemos a
combinação de duas “linhas divisórias” que geram regiões
convexas ou “envelopes convexos” (convex hulls) abertos ou
fechados.
Observação: Uma região é convexa se for possível traçar uma
linha reta entre dois pontos quaisquer pertencentes à região sem
“sair” da mesma.
58
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptron multicamada no papel de Classificador
Se aumentarmos a dimensão n do padrão de entrada, ou seja, se
inserirmos mais nodos (neurônios) na input layer obteremos mais
e mais cantos de uma figura (região de classificação !!) sempre
convexa.
• 2 neurônios → 2 “linhas divisórias” → 4 regiões convexas
• 3 neurônios → 3 “linhas divisórias” → 7 regiões convexas
• 4 neurônios → 4 “linhas divisórias” → 11 regiões convexas
Resumindo: Quando a topologia da rede neural tem a camada da
“retina”, a input layer e a output layer, consegue-se apenas
classificar padrões que se enquadrem em regiões convexas.
Na maioria dos casos, porém, as regiões de classificação são não
convexas. Como a rede neural irá então efetuar a a classificação ?
59
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptron multicamada no papel de Classificador
Na maioria dos casos as regiões de classificação são não
convexas. Como a rede neural irá então efetuar a a classificação ?
Ao acrescentarmos mais uma camada de neurônios (hidden layer)
à rede neural, esta passa a ter as seguintes camadas:
“retina” → input layer → hidden layer → output layer
Aí sim, a rede neural será capaz de classificar padrões que se
situam em regiões não convexas.
Isto porquê cada neurônio da hidden layer é capaz de identificar,
como “linha divisória”, uma região convexa, e a combinação de
diversas regiões convexas (provenientes dos diversos neurônios da
hidden layer) produz regiões não convexas.
60
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptron multicamada no papel de Classificador
Três camadas de unidades de perceptrons (input layer, hidden
layer e output layer) permitem formar regiões não convexas das
mais variadas e diversas formas, permitindo então a tarefa de
classificação de padrões.
A complexidade dos “formatos” das regiões não convexas é
limitada apenas pela quantidade de neurônios presentes na
topologia da rede e sua distribuição pelas camadas.
E como é possível construir qualquer “formato” de região não
convexa com 3 camadas na topologia da rede, podemos dizer que
qualquer problema de classificação (reconhecimento de padrão)
pode ser realizado usando-se rede neural com 3 camadas. Este fato
é matematicamente provado e conhecido como Teorema de
Kolmogorov.
61
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptron multicamada no papel de Classificador
A literatura sobre redes neurais apresenta alguma inconsistência
quando tenta descrever a topologia das redes neurais com respeito
ao número de camadas da rede e seu potencial de reconhecimento.
Para a situação anteriormente apresentada, alguns autores
considerariam uma rede neural com 4 camadas e não uma rede
neural de 3 camadas.
Vamos então aqui definir um critério de contagem do número de
camadas da rede neural.
• Critério: Considere como camada de uma rede neural, aquela
que é “alimentada” por conexões que apresentam pesos.
Temos então 3 camadas:
1) da camada “retina” para input layer
2) da camada input layer para hidden layer
3) da camada hidden layer para output layer.
E assim é possível implementar um classficador, qualquer que
seja a complexidade dos padrões a serem classificados.
62
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptron multicamada no papel de Classificador
Topologia geral para uma rede neural
63
INTELIGÊNCIA ARTIFICIAL
Redes Neurais - Algumas ideias
Perceptron multicamada no papel de Classificador
Topologia geral para uma rede neural
64