Inteligência Artificial: Uma Abordagem
de Aprendizado de Máquina
Métodos Baseados em
Otimização
Métodos Baseados em Otimização

Algumas técnicas de AM buscam hipótese
recorrendo à otimização de uma função:



Ex. erro médio quadrático
Em problemas supervisionados, rótulo dos objetos é
considerado na formulação
Estudaremos duas técnicas:


Redes Neurais Artificiais (RNAs)
Máquinas de Vetores de Suporte (SVMs)

Support Vector Machines
Redes Neurais Artificiais

Cérebro humano é responsável pelo processamento e controle de diversas informações

Realizamos ações que requerem atenção a diversos
eventos ao mesmo tempo e processamentos variados


Ex. pegar objeto, caminhar, envolvem ação de diversos
componentes, como memória, coordenação, aprendizado
Motivação na construção de máquinas inteligentes
André Ponce de Leon de Carvalho
3
Redes Neurais Artificiais

Sistemas distribuídos inspirados na estrutura
e funcionamento do sistema nervoso

Objetivo: simular capacidade de aprendizado do
cérebro na aquisição de conhecimento
Compostas por várias unidades de processamento (“neurônios”)
Interligadas por um grande número de conexões (“sinapses”)
André Ponce de Leon de Carvalho
4
Histórico
1940
1950
1960
1970
1943 Primeiro modelo de neurônio artificial
W. McCulloch e W. Pitts (neurônio MCP)
McCulloch: psicólogo e neurofisiologista
Pitts: matemático
1980...
Histórico
1940
1950
1960
1970
1980...
1949 Primeiro trabalho demonstrando aprendizado
em redes neurais artificiais (D. Hebb)
Conseguido através de alterações nos pesos de
entrada dos neurônios
Regra de Hebb: baseada no reforço das ligações
entre neurônios excitados
Histórico
1940
1950
1960
1970
1980...
1958 Modelo de RNA Perceptron de F. Rosenblatt
Sinapses ajustáveis com neurônios MCP poderiam
ser treinadas para classificação
Propôs algoritmo de treinamento
Histórico
1940
1950
1960
1970
1980...
1969 Artigo de Minsky e Papert
Perceptron de Rosenblatt não é capaz de resolver
alguns problemas simples
(Perceptron simples é limitado à resolução de problemas linearmente separáveis)
Histórico
1940
1950
1960
1970
1980...
Década de 70 abordagem conexionista adormecida
Alguns poucos trabalhos importantes:
• Redes sem peso
• Sistemas auto-adaptativos
• Memórias associativas e modelos auto-organizáveis
Histórico
1940
1950
1960
1970
1980...
Década de 80: ressurgimento
1982 J. Hopfield: propriedades associativas das
RNAs – relação com sistemas físicos
1986 D. E. Rumelhart e J. L. McClelland
Algoritmo de treinamento back-propagation para
RNAs multi-camadas  resolução de problemas
mais complexos
Histórico
1940
1950
1960
1970
1980...
Interesses mais recentes em RNAs:
• Implementação em hardware
• Modelos mais próximos ao biológico
• Sistemas neurais híbridos
• Busca de algoritmos de treinamento eficientes
Redes Biológicas

Cérebro humano: 1011 neurônios


Cada neurônio processa e se comunica com
milhares de outros continuamente e em paralelo
Cérebro: responsável por funções cognitivas e
execução de funções sensoriomotoras e
autônomas

Tem capacidade de reconhecer padrões e relacioná-los,
usar e armazenar conhecimento por experiência e
interpretar observações
Neurônio Natural

Um neurônio simplificado:
Dendritos
Axônio
Corpo
Sinal
Sinapse
Neurônio
Dendritos são prolongamentos numerosos dos neurônios, especializados na recepção de estímulos
nervosos
Estes estímulos podem ser do
meio ambiente, como de
outros neurônios
Cada dendrito carrega o sinal
elétrico para o corpo
(somma) da célula principal
O somma coleta, combina e
processa as informações
recebidas dos dendritos
Manda informações já processadas para o axônio
Neurônio

Concentrações de potássio (negativo) e sódio (positivo) criam diferenças de potencial
V
+ 40 mV
Tempo
- 50 mV
- 70 mV
Disparo
Repouso
Neurônio
Axônios são prolongamentos
dos neurônios, responsáveis pela condução dos
impulsos elétricos até outro
local mais distante
São responsáveis pela
transmissão de estímulos
Alguns axiônios de um
humano adulto podem
chegar a mais de um metro
de comprimento
Sinapse é o nome dado à conexão entre neurônios
Cada sinapse tem um peso,
que caracteriza a força da
conexão entre dois
neurônios
Os sinais são transportados
através de sinapses por
substâncias químicas chamadas neurotransmissores
Redes Biológicas

Neurônios são bem mais lentos que os circuitos
elétricos, mas o cérebro é capaz de realizar muitas
tarefas mais rápido que qualquer computador



Redes neurais biológicas trabalham de forma massivamente paralela
Neurônios estão organizados em cerca de 1000 nódulos principais, cada um com 500 redes neurais
E cada neurônio pode estar ligado a centenas ou até
milhares de outros neurônios
Rede Neural Artificial

Uma Rede Neural Artificial (RNA) é um sistema
computacional que apresenta um modelo inspirado na
estrutura neural do cérebro humano

Componentes básicos:
Neurônio: unidade computacional básica da rede
Arquitetura: estrutura topológica de como os neurônios são
conectados
Aprendizagem: processo que adapta a rede de modo a
computar uma função desejada, ou realizar uma tarefa
Neurônio artificial

Unidade de processamento fundamental de uma RNA
Entradas
Pesos
x1
x2
...
w2
∑
fa
Saída
y
xd
Sinal
Objeto x com d atributos fornece entrada
Pesos para as entradas são dados pelo vetor w
É realizada uma soma ponderada da entrada, à qual é aplicada uma
função de ativação, que fornece a saída final (previsão)
Neurônio artificial

Entrada total do neurônio:
d
u
x jwj
x1
w
x2
w2
1
a
j
j
y
wd
xd
Conexões podem ser excitatórias (peso > 0) ou inibitórias (peso < 0)
Neurônio artificial
Funções de ativação

Funções de ativação mais comuns:

Linear: fa(u) = u

Threshold ou limiar: fa(u) =
1 , se u≥Φ
0, se u
(ou -1)

Sigmoide Logística: fa(u) = 1/(1 + e- u)

Tangente hiperbólica: f a(u) = (1 - e- u)
(1 +e- u)
Função linear
f(u)
u
f(u) = u
Função limiar
f(u)
u
1, se u
f(u) =
0, se u
Função sigmoide logística
f(u)
1
f(u) =1/(1 + e- u)
Função de limiar diferenciável
Função tangente hiperbólica
f(u)
+1
- u
(1
e
)
f(u) =
(1 +e- u)
-1
Topologia

Definida por:




Número de camadas da RNA
Número de neurônios em cada camada
Grau de conectividade dos neurônios
Presença ou não de conexões de retropropagação
Topologia

Neurônios podem estar dispostos em camadas


Neurônio pode receber como entrada a saída de neurônios
da camada anterior
E enviar sua saída para entrada de neurônios em camada
seguinte
camada de
camada de
entrada
saída
conexões
camadas intermediárias
Topologia

Rede multicamadas:

Pode ter diferentes padrões de conexões entre neurônios:
Completamente conectada: neurônios
estão todos conectados aos da camada
anterior/seguinte
Parcialmente conectada: neurônios
estão conectados a
apenas alguns neurônios da camada
anterior/seguinte
Localmente conectada: neurônios
conectados encontram-se em uma região específica
Topologia

Rede multicamadas:

Pode ter diferentes arranjos de conexões:
Redes feedforward:
processamento da camada de entrada à de
saída
Tipo mais comum
Redes recorrentes:
apresentam conexões de retroalimentação (uso em sistemas dinâmicos)
Grades: matriz de
nodos
0
0
1
1
0
0
Topologia

Escolhas dependem de vários fatores:





Complexidade do problema
Dimensionalidade da entrada
Características dinâmicas ou estáticas
Conhecimento a priori
Representatividade dos dados
Aprendizado

Ajuste dos pesos das conexões
w(t+1) = w(t) + Δ w(t)
(

Algoritmos de aprendizado
Conjunto de regras bem definidas para ensinar a
rede a resolver um dado problema

Divergem na maneira como os pesos são ajustados


Em como Δ w é calculado
Aprendizado
ajustar pesos para reduzir
competição entre neurônios
(supervisionado)
sos ajustados, geralmente
Hebbiano: baseados na regra
vos, a conexão entre eles
(não supervisionado)
(não supervisionado)
Termodinâmico (Boltzmann):
seados em princípios ob-
Perceptron

Desenvolvida por Rosemblat em 1958

Utiliza modelo de McCulloch-Pitts como
neurônio

Rede mais simples para classificação de
dados linearmente separáveis

Dados que podem ser separados por um
hiperplano
Perceptron

Na realidade, é RNA com uma única camada



Estado de ativação
1 = ativo
0 = inativo


Pode ser usado +1 e -1 também
Aprendizado por correção de erro

Obter valor de incremento Δ w(t) para que
valor
w(t+1) = w(t) + Δ w(t) esteja mais próximo
da ( solução desejada que w(t)
Aprendizado Perceptron

Considere um neurônio arbitrário

Com entradas x’e pesos w’

Ativação =
i
w’i x’i = w’ . x’
Produto interno

Condição de disparo: w’ . x’ = θ

Ou w’ . x’ - θ = 0
Limiar de ativação
Aprendizado Perceptron

w’ . x’ - θ = 0 é equivalente a adicionar um
peso w0 com valor - θ às entradas do
neurônio e conectá-lo a uma entrada com
valor fixo x0 = 1
) w = (-θ , w1, ..., wn)


x = (1, x1, ..., xn)
x
1
2
x
x3
w1
2
w
w3
f
-
+1
Aprendizado

Considere o par de treinamento {x, yd} e a
saída atual da rede y

Erro devido à saída atual: e = yd – y
y
0
0
1
1
yd
0
1
0
1
e
0
1
-1
0
Aprendizado
y
0
( w


. x < 0, já que y = 0
e
1
w(t)
||w|| ||x|| cos( α ) < 0


yd
1
α = ângulo entre vetores w e x
cos(α ) < 0
α > 90º
. α
x
Aprendizado

Mudança plausível para w é somá-lo a um
vetor na direção de x


(
Para modificar ângulo
Aprendizado

η = taxa de aprendizado

0< η <1

Taxas pequenas
Estimativas estáveis de peso
Aprendizado lento

Taxas grandes
Aprendizado rápido
Captação de mudanças no
processo

Taxas variáveis
Instabilidade

Maiores no começo
Aprendizado
y
1
yd
0
w . x > 0, já que y = 1
 (
||w|| ||x|| cos( α ) > 0

cos(α ) > 0
α
< 90º
e
-1

w(t)
.α
x
Aprendizado

Mudança plausível para w é subtraí-lo de um
vetor na direção de x


(
Para modificar ângulo
Vetor η x
ηx
w(t)
. w(t+1)
x
Assim, w(t) = - x(t)
(w(t+1) = w(t) - η x(t)
Como e = -1, podemos escrever:
w(t+1) = w(t) + η ex(t)
Aprendizado

Para duas situações de erro possíveis,
chegou-se à mesma regra de atualização:
(

w(t+1) = w(t) + η ex(t)
Logo,
Δw(t) = η ex(t), se y ≠ yd
0, se y = yd
Ajuste de pesos deve ser proporcional ao produto do
erro pelo valor de entrada da sinapse
Aprendizado por correção de erro

Superfície de erro


Superfície multi-dimensional representando gráfico
da função de custos X peso
Objetivo do aprendizado:

A partir de um ponto qualquer da superfície, mover em
direção a um mínimo global
Superfície de erro
Erro
mínimo global
Parâmetros livres
Superfície de erro
Erro
X
mínimos locais
mínimo global
Parâmetros livres
Algoritmo de treinamento Perceptron

Teorema de convergência:

Se é possível classificar um conjunto de entradas
linearmente, uma rede Perceptron fará a
classificação


21/11/11
Em um número finito de passos
Mas tempo pode ser proibitivo!
Redes Neurais - André Ponce de Leon F. de
48
Algoritmo de treinamento
Algoritmo de treinamento de RNA Perceptron
Entrada: Conjunto de treinamento D = {(xi ,yi), i = 1,...n}
Saída: Rede Perceptron com pesos ajustados
Iniciar pesos da rede com valores baixos
repita
para cada xi faça
Calcular valor da saída produzida pela rede f(xi)
erro e = yi - f(xi)
se e > 0 então
Ajustar pesos do neurônio w(t+1) = w(t) + ηex(t)
até que erro = 0 (ou erro < ε)
21/11/11
Redes Neurais - André Ponce de Leon F. de
49
Algoritmo de treinamento
Vetor peso ideal
6
5
3
4
2
1
21/11/11
Redes Neurais - André Ponce de Leon F. de
50
Algoritmo de treinamento
3
2
1
5
4
8
21/11/11
6
Redes Neurais - André Ponce de Leon F. de
7
51
Algoritmo de teste

Uso da RNA treinada
Algoritmo de teste de RNA Perceptron
Entrada: Exemplo de teste x e RNA Perceptron com pesos ajustados
Saída: previsão para classificação de x
Apresentar x à entrada da RNA
Calcular a saída f(x)
Retorne f(x)
21/11/11
Redes Neurais - André Ponce de Leon F. de
52
Exemplo

Dada uma rede Perceptron com:

E
Três terminais de entrada, utilizando pesos iniciais
w1 = 0.4, w2 = -0.6 e w3 = 0.6, e limiar = 0.5:

Ensinar a rede com os dados (001, -1) e (110, +1)


Utilizar taxa de aprendizado η = 0.4
Definir a classe dos dados: 111, 000, 100 e 011
Exemplo
x1
Situação
desejada
y
x2
-1
001
x3
Limiar
110
+1
Exemplo
a) Treinar a rede
a.1) Para o dado 001
(yd = -1)
Passo 1: definir a saída da rede
u = 0(0.4) + 0(-0.6) + 1(0.6) -1(0.5) = 0.1
y = +1 (uma vez 0.1≥ 0)
0
Passo 2: atualizar pesos (y ≠ yd)
)
w1 = 0.4 + 0.4(0)(-1 - (+1)) = 0.4
-1
001
=
110
w2 = -0.6 + 0.4(0)(-1 - (+1)) = -0.6
w3 = 0.6 + 0.4(1)(-1 - (+1)) = -0.2
w0 = 0.5 + 0.4(-1)(-1 - (+1)) = 1.3 (bias)
+1
Exemplo
a) Treinar a rede
a.2) Para o dado 110
(y d = +1)
Passo 1: definir a saída da rede
u = 1(0.4) + 1(-0.6) + 0(-0.2) -1(1.3) = -1.5
y = -1 (uma vez -1.5 < 0)
y
)
Passo 2: atualizar pesos (y ≠ yd)
-1
w1 = 0.4 + 0.4(1)(1 - (-1)) = 1.2
001
w2 = -0.6 + 0.4(1)(1 - (-1)) = 0.2
w3 = -0.2 + 0.4(0)(1 - (-1)) = -0.2
110
w0 = 1.3 + 0.4(-1)(1 - (-1)) = 0.5 (bias)
+1
Exemplo
a) Treinar a rede
a.3) Para o dado 001
Passo 1: definir a saída da rede
u = 0(1.2) + 0(0.2) + 1(-0.2) -1(0.5) = -0.7
y = -1 (uma vez -0.7 < 0)
Passo 2: atualizar pesos
Como y = yd, os pesos não precisam ser
y
:
-1
001
110
(yd = -1)
+1
modificados
Exemplo
a) Treinar a rede
a.4) Para o dado 110
y
:
-1
Passo 1: definir a saída da rede
u = 1(1.2) + 1(0.2) + 0(-0.2) -1(0.5) = +0.9
y = +1 (uma vez 0.9 > 0)
Passo 2: atualizar pesos
Como y = yd, os pesos não precisam ser
001
110
(y d = +1)
+1
modificados
Exemplo
b) Testar a rede
b.1) Para o dado 111
u = 1(1.2) + 1(0.2) + 1(-0.2) -1(0.5) = 0.7
y = +1 (porque 0.7 0)
b.2) Para o dado 000
u = 0(1.2) + 0(0.2) + 0(-0.2) -1(0.5) = -0.5
y = -1 (porque -0.5 < 0)
Exemplo
b) Testar a rede
b.3) Para o dado 100
u = 1(1.2) + 0(0.2) + 0(-0.2) -1(0.5) = 0.7
y = +1 (porque 0.7 0)
b.4) Para o dado 011
u = 0(1.2) + 1(0.2) + 1(-0.2) -1(0.5) = -0.5
y = -1 (porque -0.5 < 0)