SISTEMAS DE APRENDIZAGEM
(OU APRENDIZAGEM DE MÁQUINAS)
31/03/2005
Trabalho realizado por:
Filipe Pereira nº14677
Luís Aguilar nº14676
Vitor Rodrigues nº11542
1
Questões Importantes
►O
que é a aprendizagem ?
► Porquê
►A
aprender ?
aprendizagem é mesmo possível ?
 Pode um algoritmo prever o futuro?
►A
aprendizagem é uma questão de estatísticas?
2
O Que é a Aprendizagem ?
► A psicologia costuma definir a aprendizagem como uma
mudança relativamente permanente no conhecimento ou
no comportamento produzido pela experiência. A
aprendizagem considera então a aquisição de informação e
conhecimentos, de habilidades, de hábitos, de atitudes e
de crenças (as mudanças físicas do amadurecimento não é
considerado aprendizagem)
Gonzalez-Perez, J.; Criado M.J.
Psicologia de la Educacion para una Enseñansa Prática (2003)
3
O Que é a Aprendizagem ?
► Memorizar
► Aprender
qualquer coisa
factos através da observação e
exploração
► Melhorar
capacidades cognitivas e/ou motoras
através da prática
► Organizar
novo conhecimento em representações
gerais.
4
Uma definição mais computacional
►
Herb Simon, uma figura histórica importante na
Inteligência Artificial e Economia, deu-nos a seguinte
definição de Aprendizagem:
 Aprendizagem denota mudanças no sistema que são
adaptativas no sentido em que permitem ao sistema
fazer a tarefa ou as tarefas tiradas da mesma população
mais eficientemente e mais eficazmente da próxima vez.
5
X
Então como aprender?
►A
Indução
O bocado de pão 1 estava saboroso quando eu o comi.
O bocado de pão 2 estava saboroso quando eu o comi.
…
O bocado de pão 100 estava saboroso quando eu o comi.
Então, todos os bocados de pão estarão saborosos quando eu
os comer.
(David Hume resumiu assim o raciocínio por Indução)
6
Indução
►
Qualquer matemático abomina o raciocínio anterior.
►
Então porque é que a indução é aceitável ?
 Um Exemplo
► Quando
perguntado se o Sol vai nascer amanhã, a nossa
resposta natural é: Sim, porque o Sol sempre nasceu todos os
dias.
 Para um cientista, a resposta não é satisfatória, mas para o comum
dos mortais, é suficiente saber que o Sol sempre nasceu todos os
dias para “aprender” que ele vai nascer amanhã.
7
Tipos de Aprendizagem
►
Existem imensos tipos de problemas relacionados com a
aprendizagem de Máquinas.
 Aprendizagem Supervisionada
 Clustering (agrupamento)
 Reforço (Reinforcement)
8
Aprendizagem Supervisionada
►
Dado um conjunto de pares de input/output, encontrar uma
regra que nos permita prever o output associado a cada novo
input.
►
Por exemplo: Imaginemos que nos é dado os pesos e
comprimentos de um grupo de trutas, e os pesos e
comprimentos de um grupo de carpas. O trabalho do sistema
de aprendizagem supervisionada seria encontrar uma regra que
permitisse prever, dado o comprimento e o peso de um peixe,
se este era uma truta ou uma carpa.
9
Clustering
►
Outro tipo de problema comum de aprendizagem é o
agrupamento.
►
Dado um conjunto de exemplos, mas sem uma
classificação predefinida destes, o objectivo é agrupar os
exemplos dados em “conjuntos naturais”.
10
Um exemplo de Clustering
►
Neste caso, é-nos dada as descrições de um grupo de
animais diferentes em termos das suas características
(comprimento, peso, se tem cabelos ou não, etc.). A tarefa
agora é dividi-los em grupos, possivelmente numa
hierarquia de grupos que “faça sentido”.
►
O que torna o clustering diferente da aprendizagem
supervisionada é que não lhe é dito á partida, que grupos
de animais devemos ter. Apenas que o sistema deve
encontrar um agrupamento natural.
11
Aprendizagem por Reforço
►
Um agente interagindo com o mundo faz observações, age,
e é recompensado ou castigado. Deverá ser capaz de
escolher acções de maneira a maximizar o número de
recompensas.
►
Este problema de aprendizagem é mais familiar à maioria
de nós porque envolve a aprendizagem de capacidades
motoras, como aprender a andar ou a andar de bicicleta.
12
Aprendizagem por Reforço
►
É diferente da aprendizagem supervisionada porque
ninguém nos diz explicitamente qual é a coisa certa a fazer.
Temos apenas de ir tentando e verificar aquilo que nos faz
cair ou aquilo que nos faz ficar direitos.
13
Aprendizagem
►
Como já vimos, uma maneira de encarar a aprendizagem, é
encontrar uma função que a partir de um conjunto de dados de
input e output, expresse da melhor maneira possível a relação.
►
Aprender a pronunciar palavras pode ser visto como uma função de
letras para sons.
►
Aprender a reconhecer a escrita pode ser vista como uma função de
conjuntos de pixeis para letras
►
Aprender a diagnosticar doenças pode ser visto como uma função de
resultados de exames laboratoriais para categorias de doenças.
14
Alguns problemas…
►
O problema de inferir uma função a partir de exemplos é
complicado. Podemos pensar em pelo menos três
problemas diferentes que podem surgir:
►
Memória
►
Calcular médias
►
Generalização
15
Problema Exemplo:
►
Imaginemos que estou a tentar prever se a minha vizinha vai de
carro ou não para o trabalho
►
( o objectivo é saber se vale a pena pedir-lhe boleia. )
►
Se a minha vizinha vai de carro ou não para o trabalho parece
depender das seguintes características do dia:





temperatura ambiente,
precipitação,
o dia da semana,
se vai ou não ás compras pelo caminho e
o tipo de vestuário que ela traz.
16
exemplo…
Digamos que observamos estas características durante 3 dias. A
tabela seguinte mostra-nos os resultados destas mesmas
observações e se a vizinha vai de carro ou vai a pé para o trabalho:
17
Memória
Agora pretende-se prever qual irá ser a atitude que a
nossa vizinha ira tomar mediante as seguintes
condições (ultima linha):
Ela vai de carro ou a pé?
18
Memória
A resposta parece ser óbvia, pois as condições são
semelhantes a uma das anteriores.
Este tipo de aprendizagem é bastante rudimentar pois
basta memorizar o que se viu anteriormente para se poder
dar a resposta.
19
Calculo da média
►E
quando há ruído nos dados
(As coisas não sempre tão
simples como no caso anterior.)
►
A nossa vizinha não é totalmente coerente.
20
Calculo da média
Para input semelhante temos outputs diferentes. Se nos surgir
novamente o mesmo input qual vai ser a nossa previsão?
21
Calculo da média
Podemos afirmar que ela irá a pé com uma probabilidade de 5/7
22
X
Generalização
►
Imaginemos agora o caso em que temos de tratar com casos nunca vistos.
Neste caso, pode não haver uma resposta óbvia. Podemos abdicar de fazer
uma previsão, ou então assumir que existe uma certa propriedade de
estabilidade: situações similares tendem a ter categorias similares. Podiamos
argumentar que:
• Ela vai a pé, porque
a única vez que
choveu ela foi a pé.
• Ela vai de carro,
porque às segundas
foi sempre de carro.
23
Generalização
►
A questão de qual deles escolher é uma questão difícil e um dos
problemas mais profundos subjacentes à Aprendizagem de
Máquinas.
►
Convém realçar que o objectivo é sempre que a máquina possa
fazer as previsões acerca de dados novos sem a ajuda da
intuição humana (apresentamos estes exemplos (e o seguinte)
para sublinhar a complexidade dos problemas, que mesmo para
os humanos são questionáveis).
24
Exemplo:
• Imaginemos que se
pretende dividir estes dois
conjuntos de pontos por
forma a que, dado este
input, consigamos prever
qual a cor que irá ter um
novo ponto.
• Qual será a melhor
escolha?
(pode-se fazer o paralelo com o exemplo anterior, em que os pontos
existentes são as linhas da tabela e o ponto novo que há-de surgir
corresponde à linha nova)
25
Qual será a resposta mais correcta?
• Neste caso parece óbvio, que
seja uma linha a separar os
dois conjuntos de pontos.
• Assim um ponto que surja no lado direito, prevemos que seja
vermelho e preto se surgir no lado esquerdo
26
E agora?
• Agora que temos uma
configuração diferente de
pontos.
• Qual será a melhor escolha?
27
Também não parece ser difícil…
28
E agora?!
• Já não parece ser tão trivial
encontrar a solução neste caso
• Há pelo menos dois tipos de
resposta possível
29
Primeira opção
• Neste caso, é possível
separar completamente os
dois conjuntos de pontos
• Mas será esta a melhor
escolha?
30
Segunda opção
• Neste caso, os pontos não
estão totalmente divididos
por cor
• Esta opção despreza
alguns elementos dispersos
por forma a simplificar a
separação
31
Algoritmos de aprendizagem
►
Existem vários tipos de algoritmos de aprendizagem:
► Nearest
Neighbor (Vizinho mais próximo)
►Arvores
de decisão
► K-means
►Á
(algoritmo de agrupamento)
priori
►…
32
Nearest Neighbor
• Este algoritmo é o mais simples de todos. O novo ponto
será da cor daquele que é o seu vizinho mais próximo.
• Qual será neste
caso a cor do ponto
que falta?
• Vermelho é a cor
do ponto que está
mais próximo. Então
fica vermelho.
33
Nearest Neighbor
►
O algoritmo neste caso apenas faz o seguinte:
 Lembrar-se de todos os dados
 Quando alguém nos faz uma pergunta:
► Encontrar
► Devolver
o ponto mais próximo
a resposta associada a este.
34
Árvores de Decisão
• Outro bom exemplo de algoritmos de aprendizagem é
construir hipóteses na forma de árvores de decisão. Nas
árvores de decisão, cada nodo representa uma questão, e os
ramos representam as possíveis respostas. Podemos utilizar
esta árvore de decisão para encontrar a previsão que devemos
fazer no exemplo “vai de carro”/ ”vai a pé”.
35
Árvores de Decisão
Neste exemplo, a árvore ficaria com a seguinte
estrutura.
►
36
Árvores de Decisão
Começamos por perguntar qual é o actual estado de
precipitação. Se estiver a nevar paramos o questionário,
pois já sabemos que vai de carro. Se estiver a chover,
teremos de ir a pé (não nos vai dar boleia).
37
Árvores de Decisão
Se não estiver a chover, então temos de perguntar qual
o tipo de roupas que a vizinha trás vestido. Se for com
uma roupa formal vai de carro. Se não teremos de fazer
outra pergunta.
38
Árvores de Decisão
Podemos continuar a fazer perguntas e a dar respostas
até chegarmos a um único nodo das árvores onde iremos
obter a nossa previsão.
39
À priori
►
Este algoritmo permite inferir informação de uma base de dados que
não esteja explícita. É um dos algoritmos mais conhecidos da área do
Data Mining.
►
Data Mining é o processo de descoberta de novas e significantes
correlações, padrões e tendências, filtrando grandes quantidades de
dados guardados em repositórios, utilizando tecnologias de
reconhecimento de padrões bem como técnicas matemáticas e
estatísticas.
►
Algoritmos deste género permitem analisar grandes quantidades de
dados, extraindo de lá informações que muito dificilmente um ser
humano conseguiria “à mão”.
40
À priori
►
Este algoritmo consiste na descoberta de regras de associação.
►
O exemplo paradigmático é o do Cesto do Supermercado.
►
O objectivo é descobrir que produtos costumam ser comprados
juntos (ex. cada vez que compro pasta de dentes compro
também escova de dentes). Deste modo, o supermercado pode
“facilitar” o trabalho ao cliente e colocar os produtos que
costumam ser comprados juntos perto uns dos outros.
41
Redes Neuronais
►
Redes Neuronais Artificiais são técnicas computacionais
que apresentam um modelo matemático inspirado na
estrutura neuronal de organismos inteligentes e que
adquirem conhecimento através da experiência. Uma
grande rede neuronal artificial pode ter centenas ou
milhares de unidades de processamento; já o cérebro de
um mamífero pode ter muitos biliões de neurónios.
42
Redes Neuronais
►
O sistema nervoso é formado por um conjunto extremamente
complexo de células, os neurónios. Eles têm um papel essencial
na determinação do funcionamento e comportamento do corpo
humano e do raciocínio. Os neurónios são formados pelos
dendritos, que são um conjunto de terminais de entrada, pelo
corpo central, e pelos axônios que são longos terminais de
saída.
43
Redes Neuronais
►
Breve História das Redes Neuronais
 Os estudos de McCulloch e Pitts (1943), Hebb (1949), e
Rosemblatt (1958) introduziram o primeiro modelo de redes
neuronais simulando “máquinas”, o modelo básico de rede de
auto-organização, e o modelo Perceptron de aprendizagem
supervisionada, respectivamente.
 nos anos 60 e 70, importantes trabalhos sobre modelos de
redes neuronais em visão, memória, controle e autoorganização como: Amari, Anderson, Cooper, Cowan,
Fukushima, Grossberg, Kohonen, von der Malsburg, Werbos
e Widrow.
44
Redes Neuronais
► Breve
História das Redes Neuronais
 Alguns históricos sobre a área costumam “saltar” os
anos 60 e 70 e apontar uma reintrodução das redes
neuronais com a publicação dos trabalhos de Hopfield
(1982) relatando a utilização de redes simétricas para
optimização e de Rumelhart, Hinton e Williams que
introduziram o poderoso método Backpropagation.
45
Redes Neuronais
► Características
Gerais
 Uma rede neuronal artificial é composta por várias unidades
de processamento, cujo funcionamento é bastante simples.
Essas unidades, geralmente são conectadas por canais de
comunicação que estão associados a determinado peso. As
unidades fazem operações apenas sobre os seus dados
locais, que são entradas recebidas pelas suas conexões. O
comportamento inteligente de uma Rede Neuronal Artificial
vem das interacções entre as unidades de processamento da
rede.
46
Redes Neuronais
►
Características Gerais
 São modelos adaptativos treináveis
 Podem representar domínios complexos (não lineares)
 São capazes de generalização diante de informação incompleta
 Robustos
 São capazes de fazer armazenamento associativo de
informações
 Processam informações Espaço/temporais
 Possuem grande paralelismo, o que lhes conferem rapidez de
processamento
47
Redes Neuronais
►O
que é uma Rede Neuronal?
 A grande premissa do conexionismo para aplicações em
processamento de informações e/ou inteligência artificial é o
facto de que se pode analisar um problema de acordo com o
funcionamento do cérebro humano
 O cérebro processa informações através da activação de uma
série de neurónios biológicos. Os neurónios por sua vez,
interagem numa rede biológica através da intercomunicação.
48
Redes Neuronais
►
O Neurónio Artificial
 McCullock e Pitts 1943;
 sinais são apresentados à entrada;
 cada sinal é multiplicado por um
número, ou peso, que indica a sua
influência na saída da unidade;
 é feita a soma ponderada dos sinais
que produz um nível de actividade;
 se este nível de actividade exceder
um certo limite (threshold) a unidade
produz uma determinada resposta de
saída.
49
Redes Neuronais
► Exemplo




sinais de entrada X1, X2, ..., Xp (0 ou 1)
pesos w1, w2, ..., wp, valores reais.
limitador t;
Neste modelo, o nível de actividade a é dado por:
►a
= w1X1 + w2X2 + ... + wpXp
 A saída y é dada por:
•
•
y = 1, se a >= t ou
y = 0, se a < t.
50
Redes Neuronais
• Organização em camadas
51
Redes Neuronais
► Organização
em camadas
 Usualmente as camadas são classificadas em três grupos:
►
Camada de Entrada: onde os padrões são
apresentados à rede;
►
Camadas Intermediárias ou Escondidas: onde é
feita a maior parte do processamento, através das
conexões ponderadas; podem ser consideradas como
extractoras de características;
►
Camada de Saída: onde o resultado final é concluído e
apresentado.
52
Redes Neuronais
► Processos
de Aprendizagem
 A propriedade mais importante das redes neuronais é a
habilidade de aprender a partir do seu ambiente e com
isso melhorar o seu desempenho.
 Isso é feito através de um processo iterativo de ajustes
aplicado aos seus pesos, o treino.
 A aprendizagem ocorre quando a rede neuronal atinge
uma solução generalizada para uma classe de
problemas.
53
Redes Neuronais
► Algoritmos
de Aprendizagem
 algoritmo de aprendizagem é um conjunto de regras bem definidas
para a solução de um problema de aprendizagem.
 Existem muitos tipos de algoritmos de aprendizagem específicos
para determinados modelos de redes neuronais;
 estes algoritmos diferem entre si principalmente pelo modo como
os pesos são modificados.
54
Algoritmos Genéticos
►
O paradigma genético dos sistemas de aprendizagem é o que
tem estado mais em voga na área dos sistemas de
aprendizagem.
►
Consiste num sistema de classificação inspirado na analogia com
as operações ocorridas na reprodução biológica e na selecção
natural da forma como foi descrita por Darwin, onde impera a lei
do mais forte.
►
Encontram-se especialmente talhados para problemas de
reconhecimento discreto de padrões e para a aquisição de
regras para sistemas periciais.
55
Algoritmos Genéticos
►
Programas Evolutivos
 Consiste em sistemas de resolução de problemas baseados
nos princípios biológicos da evolução e da hereditariedade.
 Cada indivíduo representa uma potencial solução do
problema.
 Cada solução é avaliada para se ter uma medida do seu
desempenho.
 Uma nova população é gerada a partir da anterior por
selecção dos melhores indivíduos e aplicação dos operadores
genéticos.
56
Algoritmos Genéticos
► Operadores
genéticos
 Selecção: utilizado para seleccionar os indivíduos que
tiveram melhor desempenho.
 Mutação: consiste numa alteração aleatória em alguns
dos indivíduos seleccionados.
 Cruzamento: consiste em recombinar dois indivíduos
por forma a obter dois filhos potencialmente mais
capazes
57
Algoritmos Genéticos
►
Resumindo, é um método adaptativo de procura num
espaço de soluções por aplicação de operadores derivados
da teoria da evolução. Mantém uma população de soluções
propostas para um dado problema.
►
As soluções relativamente “boas” produzem descendentes,
enquanto que as “piores” já não surgem na nova geração.
►
A estimativa da qualidade de uma solução é baseada numa
função de avaliação, que representa um dado ambiente.
58
Resumindo...
►
A Aprendizagem de Máquinas (Machine Learning) é uma área da
Inteligência Artificial muito vasta. Neste trabalho tentamos apresentar
de uma maneira geral os seus principais tópicos. Abordamos os
principais algoritmos de aprendizagem por mineração de dados (Data
Mining): árvores de decisão, à priori e algoritmos de clustering.
►
Tentamos também introduzir o conceito de aprendizagem e a forma
como esta pode ocorrer num sistema (tipos de aprendizagem).
►
Abordamos também o paradigma conexionista, nomeadamente o seu
expoente máximo, as redes neuronais.
►
Por fim abordamos os algoritmos genéticos, que têm vindo a adquirir
uma importância crescente muito nos últimos anos.
59
Bibliografia
►
Artificial Intelligence by T. Lozano-Perez and L. Kaelbling. Copyright ©
2003, Massachusetts Institute of Technology (MIT).
http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-ComputerScience/6-034Artificial-IntelligenceSpring2003/3559854D-86CD-4D8BBBF0-17456980E4AC/0/9mlintrohandout.pdf
►
Data Mining: Concepts, Models, Methods, and Algorithms by Mehmed
Kantardzic, ISBN:0471228524 John Wiley & Sons © 2003
►
Data Minning: Análise Determinística, Nelson Guedes Paulo Júnior e Ricardo
Hideo Sahara, www.linux.ime.usp.br/~npaulo/mac439
►
http://piano.dsi.uminho.pt/disciplinas/LIGIA/20012002/ai2.PDF
60