Inteligência Artificial: Uma Abordagemde Aprendizado de

Máquina

Métodos Baseados emOtimizaçã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

3André Ponce de Leon de Carvalho

Cérebro humano é responsável pelo proces- samento 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

Redes

Neurais

Artificiais

4André Ponce de Leon de Carvalho

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”)

Histórico

1940 1950 1960 1970 1980...

1943 Primeiro modelo de neurônio artificialW. McCulloch e W. Pitts (neurônio MCP)

McCulloch: psicólogo e neurofisiologistaPitts: matemático

Histórico

1940 1950 1960 1970 1980...

1949 Primeiro trabalho demonstrando aprendizadoem redes neurais artificiais (D. Hebb) Conseguido através de alterações nos pesos de entrada dos neurôniosRegra 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. RosenblattSinapses ajustáveis com neurônios MCP poderiam ser treinadas para classificaçãoPropôs algoritmo de treinamento

Histórico

1940 1950 1960 1970 1980...

1969 Artigo de Minsky e PapertPerceptron de Rosenblatt não é alguns problemas simples

capaz de resolver

(Perceptron simples é limitado à resolução de pro-blemas linearmente separáveis)

Histórico

1940 1950 1960 1970 1980...

Década de 70 abordagem conexionista adormecidaAlguns poucos trabalhos importantes:

•••

Redes sem pesoSistemas auto-adaptativosMemórias associativas e modelos auto-organizáveis

Histórico

1940 1950 1960 1970 1980...

Década de 80: ressurgimento

1982 J. Hopfield: propriedadesRNAs – relação com sistemas

associativasfísicos

das

1986 D. E. Rumelhart e J. L. McClellandAlgoritmo de treinamento back-propagation paraRNAs multi-camadas resolução de problemasmais complexos

Histórico

1940 1950 1960 1970 1980...

Interesses mais recentes em RNAs:••••

Implementação em hardwareModelos mais próximos ao biológicoSistemas neurais híbridosBusca 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:

DendritosAxônio

Corpo Sinal

Sinapse

Neurônio

nios, especializados na re- recebidas dos dendritos

Dendritos são prolongamen- O somma coleta, combina e

tos numerosos dos neurô- processa as informações

cepção de estímulos nervosos

Manda informações já proces-

Estes estímulos podem ser do sadas para o axônio

meio ambiente, como deoutros neurônios

Cada dendrito carrega o sinal elétrico para o corpo (somma) da célula principal

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

Cada sinapse tem um peso,local mais distante

Axônios são prolongamentos Sinapse é o nome dado à co- dos neurônios, responsá- nexão entre neurônios

veis pela condução dos impulsos elétricos até outro

que caracteriza a força da conexão entre dois

São responsáveis pela neurônios transmissão de estímulos

Os sinais são transportados

Alguns axiônios de um através de sinapses porhumano adulto podem substâncias

químicas cha-chegar a mais de um metro madas neurotransmissores

de comprimento

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 massiva- mente paralela Neurônios estão organizados em cerca de 1000 nódu- los 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

faw2

w1

w d

1

...

Unidade de processamento fundamental de uma RNAEntradas Pesos

x Saídax2 y

xd

Sinal

Objeto x com d atributos fornece entradaPesos 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

1

dyu x j w j

j j2 a

Entrada total do neurônio:

x1 w

x2 w

wd

xd

Conexões podem ser excitatórias (peso > 0) ou inibitórias (peso < 0)

Neurônio

artificial

Funções

deativação

a

a 0, se u (ou -1)

a

a

Funções de ativação mais comuns:

Linear: f (u) = u

Threshold ou limiar: f (u) = 1 , se u≥Φ

Sigmoide Logística: f (u) = 1/(1 + e- u)

Tangente hiperbólica: f (u) = (1 - e-

u)

(1 +e- u)

Função linear

f(u)

u

f(u) = u

Função

limiar

f(u) =

f(u)

u

1, se 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

- u(1 - e )f(u) =

f(u)

+1

(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

entrada saída

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

conexõescamadas intermediárias

Topologia

Rede multicamadas: Pode ter diferentes padrões de conexões entre neurônios:

Completamente co- Parcialmente co- Localmente co- nectada: neurônios nectada: neurônios nectada: neurônios estão todos conecta- estão conectados a conectados encon- dos aos da camada apenas alguns neu- tram-se em uma re- anterior/seguinte rônios da camada gião específica

anterior/seguinte

0 1 0

Topologia

Rede multicamadas: Pode ter diferentes arranjos de conexões:

Redes feedforward: Redes recorrentes: Grades: matriz de processamento da ca- apresentam cone- nodosmada de entrada à de xões de retroalimen-

saída tação (uso em siste- Tipo mais comum mas dinâmicos)

0 1 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

competição entre neurôniosajustar pesos para reduzir

sos ajustados, geralmente(supervisionado)

Hebbiano: baseados na regra (não supervisionado)

Termodinâmico (Boltzmann):vos, a conexão entre eles

seados em princípios ob-(não supervisionado)

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

valorw(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 fx = (1, x1, ..., xn)

-

1

x x

3

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 w1

2

2 w3

+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 yd e

0 0 00 1 11 0 -11 1 0

Aprendizado

y yd e

0 1 1

( w . x < 0, já que y = 0 w(t)

||w|| ||x|| cos( α ) < 0 α = ângulo entre vetores w e x . α

cos(α ) < 0 x

α > 90º

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

Aprendizado rápido Taxas grandes Captação de mudanças no

processo

Taxas variáveis Instabilidade

Maiores no começo

Aprendizado

y yd e

1 0 -1

w . x > 0, já que y = 1 ( ||w|| ||x|| cos( α ) > 0 w(t)

cos(α ) > 0 . α

α < 90º x

Aprendizado

( Assim, w(t) = - x(t)

Mudança plausível para w é subtraí-lo de um vetor na direção de x Para modificar ângulo Vetor η x

(w(t+1) = w(t) - η x(t)η x Como e = -1, podemos escrever:

w(t) w(t+1) = w(t) + η ex(t). w(t+1)

x

Aprendizado

Ajuste de pesos deve ser proporcional ao produto doerro pelo valor de entrada da sinapse

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

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

deerro

Erro

mínimo global

Parâmetros livres

Superfície

deerro

Erro

X

mínimos locaismínimo global

Parâmetros livres

Algoritmo

detreinamento

Perceptron

21/11/11 48Redes Neurais - André Ponce de Leon F. de

Teorema de convergência: Se é possível classificar um conjunto de entradas linearmente, uma rede Perceptron fará a

classificação Em um número finito de passos Mas tempo pode ser proibitivo!

Algoritmo de treinamento

Algoritmo de treinamento de RNA PerceptronEntrada: Conjunto de treinamento D = {(x ,y ), i

= 1,...n}i i

Saída: Rede Perceptron com pesos ajustados Iniciar pesos da rede com valores baixos repita

para cada x façai

Calcular valor da saída produzida pela rede f(x )i

erro e = y - f(x )i i

se e > 0 entãoAjustar pesos do neurônio w(t+1) = w(t) + ηex(t)

até que erro = 0 (ou erro < ε)

21/11/11 49Redes Neurais - André Ponce de Leon F. de

Algoritmo

detreinamento

Vetor peso ideal

6

5

3 4

2

1

21/11/11 50Redes Neurais - André Ponce de Leon F. de

Algoritmo

detreinamento

32

1

54

8 6 7

21/11/11 51Redes Neurais - André Ponce de Leon F. de

Algoritmo de teste

Uso da RNA treinada

Algoritmo de teste de RNA PerceptronEntrada: Exemplo de teste x e RNA Perceptron tados

com pesos ajus-

Saída: previsão para classificação de xApresentar x à entrada da RNACalcular a saída f(x)Retorne f(x)

21/11/11 52Redes Neurais - André Ponce de Leon F. de

Exemplo Dada uma rede Perceptron com:

Três terminais de entrada, utilizando pesos iniciais w1 = 0.4, w2 = -0.6 e w3 = 0.6, e limiar = 0.5:

E 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

Situaçãodesejada

Limiar

+1

-1

001

110

y

x1

x2

x3

Exemplo

a) Treinar a redea.1) Para o dado 001 (yd = -1)

Passo 1: definir a saída da redeu = 0(0.4) + 0(-0.6) + 1(0.6) -1(0.5)

= 0.1

0

)y = +1 (uma vez 0.1≥ 0)

Passo 2: atualizar pesos (y ≠ y )d

0.4w1 = 0.4 + 0.4(0)(-1 - (+1)) =

w2 =

w3 =

w0 =

-0.6 + 0.4(0)(-1 - (+1)) = -0.6

0.6 + 0.4(1)(-1 - (+1)) = -0.2

0.5 + 0.4(-1)(-1 - (+1)) = 1.3 (bias)

+1

-1

001

=110

Exemplo

d

a) Treinar a redea.2) Para o dado 110 (y = +1)

Passo 1: definir a saída da redeu = 1(0.4) + 1(-0.6) + 0(-0.2) -1(1.3) = -1.5

y y = -1 (uma vez -1.5 < 0)

) Passo 2: atualizar pesos (y ≠ yd)

-1

001

w1 = 0.4 + 0.4(1)(1 - (-1)) = 1.2

w2 = -0.6 + 0.4(1)(1 - (-1)) = 0.2

w3 = -0.2 + 0.4(0)(1 - (-1)) = -0.2

w0 = 1.3 + 0.4(-1)(1 - (-1)) = 0.5 (bias)110

+1

Exemplo

d

d

110

a) Treinar a redea.3) Para o dado 001 (y = -1)

Passo 1: definir a saída da rede

u = 0(1.2) + 0(0.2) + 1(-0.2) -1(0.5) = -0.7

y y = -1 (uma vez -0.7 < 0): Passo 2: atualizar pesos

-1

001

Como y = y , os pesos não precisam ser

modificados

+1

Exemplo

d

Como y = y , os pesos não precisam ser

110

a) Treinar a redea.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 y = +1 (uma vez 0.9 > 0): Passo 2: atualizar pesos

-1

001

d

modificados

+1

Exemplob) Testar a rede

b.1) Para o dado 111u = 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 000u = 0(1.2) + 0(0.2) + 0(-0.2) -1(0.5) = -0.5

y = -1 (porque -0.5 < 0)

Exemplob) Testar a rede

b.3) Para o dado 100u = 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 011u = 0(1.2) + 1(0.2) + 1(-0.2) -1(0.5) = -0.5

y = -1 (porque -0.5 < 0)