«Agentes – Aprendizagem»
Trabalho Teórico
AISC – Agentes Inteligentes e Sistemas Cooperativos
5º Ano – 1º Semestre – 2006/2007
1000313 António Santos
1020113 Helder Ferreira
Departamento de Engenharia Informática
Resumo
O trabalho teórico apresentado neste relatório surge no decorrer da
disciplina de Agentes Intelegentes e Sistemas Cooperativos, ministrada no
primeiro semestre do quinto ano do Curso de Engenharia Informática, no
Instituto Superior de Engenharia do Porto no ano lectivo de 2006 / 2007.
O tema do trabalho é Agentes – Aprendizagens. Para a inteligência artificial a
aprendizagem é uma característica fundamental de um agente tal como o
raciocínio e as capacidades sociais.
A aprendizagem é a capacidade do agente mudar o seu comportamento com
base na experiência passada, existem outras definições umas mais
específicas das áreas em questão outras muito genéricas, no entanto, na
essência todas parecem concordar de alguma forma que aprendizagem está
relacionada com:
•
Aquisição de conhecimento (diferente de aquisição de informação)
•
Definição de Inteligência (alguma coisa que não aprende é
inteligente?)
•
Adaptabilidade ao meio (possível objectivo da aprendizagem)
De qualquer forma a definição de aprendizagem não é consensual. Temos
alguns conhecimentos de como é que os seres vivos conseguem aprender,
no entanto não conseguimos criar programas que simulem completamente o
ser vivo em todos os seus aspectos. Sendo alguns desses aspectos a
inteligência e a capacidade de aprender. De qualquer forma esta área têm
sido alvo de imensa investigação e discussão.
Actualmente a criação de programas inteligentes tem tido por base
essencialmente 3 paradigmas centrais:
•
Paradigma da Aprendizagem Simbólica
ii
•
Paradigma Conexionista
•
Paradigma Biológico
O primeiro refere-se à utilização de lógica e algoritmos e capacidade de
processamento de computadores actuais com o objectivo de recriar a
aprendizagem. O segundo baseia-se no funcionamento interno do cérebro
(redes
neuronais)
um
“equipamento”
bem
sucedido
na
tarefa
de
aprendizagem. Finalmente o terceiro tenta aplicar os conceitos de evolução
biológica e sobrevivência dos mais bem adaptados às questões relacionadas
com aprendizagem.
iii
Índice
1 INTRODUÇÃO.................................................................................................................................. 11
1.1 TRABALHO PRETENDIDO..................................................................................................................... 11
1.2 ORGANIZAÇÃO DO RELATÓRIO ............................................................................................................11
2 ARQUITECTURA DE UM AGENTE (APRENDIZ).................................................................... 13
3 PARADIGMA DE APRENDIZAGEM SIMBÓLICA................................................................... 16
3.1 BASEADA EM EXEMPLOS.....................................................................................................................16
3.1.1 Algoritmo de Eliminação de Candidatos............................................................................. 17
3.1.2 Algoritmo ID3...................................................................................................................... 18
3.1.3 Algoritmo de cobertura (AQ)............................................................................................... 19
3.2 OBSERVAÇÃO E DESCOBERTA............................................................................................................. 20
3.2.1 Agrupamento Conceptual.....................................................................................................20
3.2.2 Descoberta Empírica........................................................................................................... 22
3.3 ANALÍTICA.......................................................................................................................................23
3.4 BASEADA EM CASOS.......................................................................................................................... 24
3.5 APRENDIZAGEM INDUTIVA..................................................................................................................24
3.5.1 Indução por arvores de decisão...........................................................................................26
3.6 APRENDIZAGEM BAYESIANA................................................................................................................33
3.6.1 Fórmulas Básicas para Probabilidade................................................................................ 36
3.6.2 Classificador Bayesiano ingênuo.........................................................................................36
3.7 APRENDIZAGEM POR REFORÇO............................................................................................................37
4 PARADIGMA DE APRENDIZAGEM CONEXIONISTA........................................................... 40
4.1 REDES NEURONAIS........................................................................................................................... 40
4.1.1 Neurónios Artificiais............................................................................................................ 42
4.1.2 Topologias de Redes Neuronais...........................................................................................44
4.1.3 Aprendizagem da rede neuronal.......................................................................................... 47
5 PARADIGMA DE APRENDIZAGEM BIOLÓGICA................................................................... 49
5.1 ALGORITMOS GENÉTICOS................................................................................................................... 49
5.1.1 Selecção e Recombinação de indivíduos..............................................................................51
5.1.2 Problemas dos Algoritmos genéticos................................................................................... 54
5.1.3 Outros tipos de Algoritmos genéricos..................................................................................55
5.2 SISTEMAS CLASSIFICADORES...............................................................................................................56
6 CONCLUSÕES.................................................................................................................................. 60
6.1 TRABALHO REALIZADO.......................................................................................................................60
6.2 TRABALHO FUTURO .......................................................................................................................... 60
iv
6.3 APRECIAÇÃO FINAL........................................................................................................................... 60
BIBLIOGRAFIA....................................................................................................................................... 61
ÍNDICE REMISSO.................................................................................................................................... 62
v
Índice de Figuras
FIGURA 1 – ARQUITECTURA INTERNA DE UM AGENTE APRENDIZ.................................14
FIGURA 2 – MÓDULO DE APRENDIZAGEM................................................................................15
FIGURA 3 – B) E C) SÃO FUNÇÕES POSSÍVEIS PARA REPRESENTAR A)...........................25
FIGURA 4 – UMA ÁRVORE DE DECISÃO PARA DEFINIR SE VAMOS OU NÃO ESPERAR
POR UMA MESA.................................................................................................................................. 27
FIGURA 5 – EXEMPLOS PARA O DOMÍNIO DO RESTAURANTE.......................................... 28
FIGURA 6 – ESCOLHA DO ATRIBUTO TIPO............................................................................... 29
FIGURA 7 – ESCOLHA DO ATRIBUTO CLIENTE....................................................................... 29
FIGURA 8 – A ÁRVORE DE DECISÃO INDUZIDA A PARTIR DO CONJUNTO DE TREINO
DE 12 EXEMPLOS................................................................................................................................31
FIGURA 9 – TEOREMA DE BAYES................................................................................................. 33
FIGURA 10 – A INTERACÇÃO AGENTE-AMBIENTE EM APRENDIZAGEM POR
REFORÇO..............................................................................................................................................37
FIGURA 11 – ARVORE QUE MOSTRA QUE APENAS CHEGADO AO FIM DO JOGO O
REFORÇO É OBTIDO (VITÓRIA, DERROTA OU EMPATE).....................................................39
FIGURA 12 – PROBABILIDADE ASSOCIADA À SITUAÇÃO DO TABULEIRO.....................40
FIGURA 13 – NEURÓNIO BIOLÓGICO.......................................................................................... 41
FIGURA 14 – POSSÍVEL REPRESENTAÇÃO GENÉRICA DE NEURÓNIOS ARTIFICIAS. 42
FIGURA 15 – FUNÇÃO ACTIVAÇÃO.............................................................................................. 43
FIGURA 16 – GRÁFICO DA FUNÇÃO SIGMOIDE....................................................................... 44
FIGURA 17 – REDE MONOCAMADA À ESQUERDA. REDE HOPFIELD À DIREITA..........45
FIGURA 18 - CAMADA DE ENTRADA, CAMADA ESCONDIDA E CAMADA DE SAÍDA....46
FIGURA 19 – “CROSSOVER” DE UM PONTO...............................................................................52
FIGURA 20 – “CROSSOVER” EM DOIS PONTOS........................................................................ 53
vi
FIGURA 21 – CUT AND SPLICE....................................................................................................... 53
FIGURA 22 - ARQUITECTURA GENÉRICA DE UM SISTEMA CLASSIFICADOR...............57
vii
Índice de Algoritmos
ALGORITMO 1 – ELIMINAÇÃO DE CANDIDATOS....................................................................18
ALGORITMO 2 – ALGORITMO ID3................................................................................................19
ALGORITMO 3 – ALGORITMO DE COBERTURA (AQ)............................................................ 19
ALGORITMO 4 - CLUSTER/2............................................................................................................21
ALGORITMO 5 – PARA TORNAR OS CONJUNTOS DISJUNTOS............................................ 22
ALGORITMO 6 – ALGORITMO PARA REFINAR........................................................................24
ALGORITMO 7 – ALGORITMO PARA UMA APRENDIZAGEM BASEADA EM CASOS.... 24
ALGORITMO 8 – APRENDIZAGEM DE ÁRVORE DE DECISÃO.............................................31
ALGORITMO 9 – ALGORITMO GENÉTICO GENÉRICO..........................................................51
viii
Notação e Glossário
Aprendizagem
A aprendizagem é a capacidade do agente mudar o seu
comportamento com base na experiência passada.
Heurísticas
São regras de senso comum que são obtidas após um
olhar atento sobre um dado problema ou tipo de
problemas. Geralmente levam à obtenção de boas
soluções, embora não garantam nem que se obtenha a
melhor solução, nem que se obtenha uma boa solução
nem sequer que se encontre uma solução. Ajudam a
reduzir a necessidade de pesquisa e são particularmente
úteis na resolução de problemas sujeitos à explosão.
Inteligência
Artificial
(1) A Inteligência Artificial é o ramo da ciência dos
computadores que tem a ver com a automação de
comportamentos inteligentes [Luger-93].
(2) A Inteligência Artificial é o estudo da computação que
torna possível sentir, raciocinar e agir [Winston-92].
(1), (2) duas definições de entre as várias existentes.
Lógica
Parte da filosofia que ensina as leis do raciocínio.
ix
Formatos
Corpo do texto
Arial, 12 pt.
Estrangeirismo
Times New Roman, 12 pt, Itálico.
Algoritmos
Courier New, 10 pt.
Legendas
Times New Roman, 12 pt, Itálico.
(figuras, exemplos, tabelas)
Palavras ou frases a São escritas com ênfase como por exemplo em
destacar
MAIÚSCULAS, Negrito, Sublinhado, Itálico.
x
Agentes – Aprendizagem
1 Introdução
Pretende-se com este capítulo introdutório dar a conhecer o conteúdo do
trabalho.
1.1 Trabalho pretendido
De modo muito resumido, pode-se descrever que era pretendido abordar
métodos que podem ser aplicados aos agentes para que este tenham ou
imitem a capacidade humana de aprender.
1.2 Organização do relatório
Capítulo 1 – Introdução: neste capítulo é dado ao leitor a informação básica
necessária de forma a facilitar o enquadramento dos objectivos e dos
resultados.
Capítulo 2 – Arquitectura de um Agente (Aprendiz): neste capítulo primeiramente
é dada a definição de agente para enseguida mostrar a arquitectura interna
de um agente aprendiz.
Capítulo 3 – Paradigma de Aprendizagem Simbólica: neste capítulo é
apresentado o Paradigna de Aprendizagem Simbólica: baseada em exemplos, por
observação e descoberta e por descoberta empírica. Para uma abordagem
baseada em exemplos são dados a conhecer os algoritmos Eliminação de
Candidatos, ID3 e o algoritmo de cobertura (AQ).
Capítulo 4 – Paradigma de Aprendizagem Conexionista: neste capítulo são
apresentadadas as redes neuronais e conceitos associados.
AISC – 5º Ano – 1º Semestre – 2006/2007
11 / 63
Agentes – Aprendizagem
Capítulo 5 – Paradigma de Aprendizagem Biológica: neste capítulo são
apresentadadas os algoritmos genéticos e os sistemas classificadores.
Capítulo 6 – Conclusões: neste capítulo é apresentado de forma resumida o
trabalho feito, possíveis trabalhos futuros e tiradas as conclusões finais.
AISC – 5º Ano – 1º Semestre – 2006/2007
12 / 63
Agentes – Aprendizagem
2 Arquitectura de um Agente (aprendiz)
Antes de se considerar o que é um agente aprendiz convém definir o que é
um Agente?
Mais uma vez, existem diversas definições, usaremos a fornecida na sebenta
da disciplina de Agentes Inteligentes e Sistemas Cooperativos, ou seja um
agente é um programa que apresenta as seguintes características:
•
Capacidade sensorial: Dispõe de sensores para captar informação
do meio ambiente onde se encontra.
•
Reactividade: Sente, age e responde às mudanças do meio ambiente.
•
Autonomia: Decide e controla as suas próprias acções.
•
Pró Actividade: Orienta-se por objectivos e não age apenas por
reacção ao ambiente.
•
Persistência: Existe ao longo do tempo.
•
Capacidade
social:
Comunica,
coopera,
concorre,
compete,
argumenta e negoceia com outros agentes (ou pessoas).
•
Aprendizagem: Muda o seu comportamento com base na experiência
anterior.
•
Mobilidade: Capacidade de movimentar-se de uma maquina para a
outra.
•
Carácter: Personalidade credível e comportamento emocional.
•
Inteligência: Capacidade de raciocínio autónomo, planeio o que faz,
corrige erros e reage a situações inesperadas, adapta-se e aprende,
argumenta, negoceia e gere conflitos.
AISC – 5º Ano – 1º Semestre – 2006/2007
13 / 63
Agentes – Aprendizagem
O seguinte diagrama de módulos mostra a arquitectura interna de um agente
aprendiz.
Ambiente
Agente
Aprendizagem
Acção
Percepção
Decisão
Figura 1 – arquitectura interna de um agente aprendiz
O que distingue este agente dos restantes é o módulo de aprendizagem. Este
módulo é constituído por:
AISC – 5º Ano – 1º Semestre – 2006/2007
14 / 63
Agentes – Aprendizagem
Modulo de aprendizagem
Decisor
Decisor
Crítico
Modificador
Comparador
Figura 2 – módulo de aprendizagem
De forma resumida, a cada percepção proveniente do meio ambiente o
agente processa-a no módulo Decisor. Por sua vez este vai comparar as
percepções com experiências passadas no módulo Critico e passa a
informação ao módulo Modificador. Se esta comparação resultar em que o
agente deve modificar o seu comportamento de forma a atingir algum
objectivo é tomada uma decisão de modificação do comportamento e
passada novamente ao módulo Decisor.
Finalmente o algoritmo do módulo de aprendizagem do agente pode ser
classificado segundo 5 aspectos distintos:
•
Entrada: Características dos dados de entrada do algoritmo, por
exemplo: pares atributo/valor, expressões relacionais.
AISC – 5º Ano – 1º Semestre – 2006/2007
15 / 63
Agentes – Aprendizagem
•
Saída: Os dados de saída do algoritmo (resultado da aprendizagem)
pode ser do tipo: arvores de decisão, expressões lógicas, vectores de
números, regras do tipo Se (condição) Então (acção).
•
Tipo de aprendizagem: usam técnicas indutivas, técnicas dedutivas,
técnicas híbridas (baseadas em casos).
•
Ambiente de aprendizagem: Supervisionada (os exemplos de treino
são classificados) ou não e se é incremental (os exemplos aparecem
sequencialmente ao longo do tempo) ou não.
•
Tarefas: Classificação (procura-se aprender classificando instancias
concretas do problema) ou Resolução de problemas (procura resolver
um problema em vários passos de uma forma eficiente).
3 Paradigma de Aprendizagem Simbólica
3.1 Baseada em exemplos
O raciocínio baseado em exemplos procura promover a aprendizagem
através do fornecimento de exemplos de treino. Trata-se portanto de uma
técnica de treino supervisionada.
Através do fornecimento de exemplos específicos, procura-se chegar a
conceitos mais genéricos ou globais.
Os
dois
algoritmos
mais
importantes,
associados
a
este
tipo
de
aprendizagem é o de Eliminação de Candidatos e o ID3. Segue-se um resumo
de cada um destes e finaliza-se o capítulo com um algoritmo de cobertura (AQ)
que usa essencialmente os dois algoritmos anteriores.
AISC – 5º Ano – 1º Semestre – 2006/2007
16 / 63
Agentes – Aprendizagem
3.1.1 Algoritmo de Eliminação de Candidatos
Este algoritmo pressupõe a definição de um Espaço de Versões que é
essencialmente uma definição comum a todas as hipóteses definidoras de
um conceito que se pretende aprender.
É considerada a existência de dois tipos de hipóteses:
•
G (Gerais): Conjunto de hipóteses mais gerais consistentes com os
exemplos. Inicialmente é representado com “?” ou seja pode tomar
qualquer valor
•
E (Especificas): Conjunto de hipóteses mais específicas consistentes
com os exemplos. Inicialmente é representado com “-“ ou seja não
toma nenhum valor
As hipóteses definidoras de um conceito (positivas) são aplicadas ao
conjunto de hipóteses mais gerais de forma a torna-las mais específicas. Por
outro lado usam-se as hipóteses não definidoras do conceito (negativas) para
tornar o conjunto de hipóteses específicas mais geral. De seguida é
apresentado o algoritmo.
1.0 E = { < - , - , ... , -, - >}
2.0 G = { < ? , ? , ... , ?, ? >}
3.0 Para cada exemplo positivo x+
3.1 Retirar de G os membros inconsistentes com x+
3.2 Generalizar os membros de E até ficarem consistentes com
4.0
5.0
x+ mas guarda-los apenas se forem mais específicos
que G
3.3 Retirar de E os membros que não sejam os maximamente
específicos
Para cada exemplo negativo de x4.1 Retirar de E os membros inconsistentes com x4.2 Especializar os membros de G até ficarem consistentes
com x-, mas guarda-los apenas se forem mais gerais que E
4.3 Retirar de G os membros que não sejam minimamente
específicos
Se há mais exemplos voltar a 3.0, senão termina.
AISC – 5º Ano – 1º Semestre – 2006/2007
17 / 63
Agentes – Aprendizagem
Algoritmo 1 – eliminação de candidatos
Uma das grandes desvantagens do algoritmo de eliminação de candidatos é
que não consegue aprender conceitos se estes forem apresentados na forma
disjuntiva.
3.1.2 Algoritmo ID3
O algoritmo ID3 tem por base uma árvore de decisão. A vantagem deste
algoritmo relativamente aos demais é que incorpora um método que lhe
permite construir uma árvore de decisão “mínima”, através de uma escolha do
atributo mais discriminante para cada ramificação da arvore.
A forma como é feita a escolha do atributo mais discriminante baseia-se na
Regra da Escolha: Deve-se escolher como atributo de divisão aquele que
produz maior ganho informativo, ou seja considerando o nó com etiqueta A o
melhor atributo é aquele que minimiza E(A).
v
E(A)=
∑
i =1
pi + pn
I ( pi, ni )
p+n
Sendo:
E – Ganho em informação
P, N – Subconjuntos de todos os nós possíveis da arvore
A explicação detalhada deste algoritmo vai para além do âmbito deste
trabalho. Para mais informações consultar a bibliografia usada.
De seguida apresenta-se o algoritmo do ID3.
Dado:
o Conjunto S de exemplos de treino (E+, E-)
o Família de conjuntos de atributos e respectivos valores A
o Conceito alvo T
AISC – 5º Ano – 1º Semestre – 2006/2007
18 / 63
Agentes – Aprendizagem
Determinar:
o Uma arvore de decisão AD cujas folhas são formadas por
elementos da mesma classe. O conceito alvo T é dado pela
disjunção da caracterização da classe positiva (E+)
Algoritmo:
1.0 Se todos os elementos são da mesma classe então terminar
com AD formada por um nó etiquetado pela classe dos
elementos de S
2.0 Senão:
2.1 Escolher um atributo A={A1,...,Av}
2.2 Dividir S em {S1, ..., Sv} subconjuntos disjuntos de
acordo com os diferentes valores de A
2.3 Chamar recursivamente o algoritmo para cada um dos
subconjuntos S
2.4 Construir uma AD tendo por raiz o atributo A e os ramos
etiquetados pelos valores Aj ligados as sub arvores
associadas a Sj
Algoritmo 2 – algoritmo ID3
3.1.3 Algoritmo de cobertura (AQ)
Este algoritmo permite atacar os problemas de aprendizagem mais
complexos. Os algoritmos anteriores baseiam-se em dividir os exemplos
fornecidos em duas classes, uma positiva (definidora do conceito) e outra
negativa (definidora do que o conceito não é), no entanto podemos necessitar
de uma maior subdivisão do que apenas duas classes... Este algoritmo
permite-nos isto, a sua descrição é a seguinte:
1.0
2.0
Dividir os exemplos pelas classes
Para cada classe
2.1 Considerar os seus exemplos como positivos e todos os
restantes como negativos
2.2 Aplicar o algoritmo de Eliminação de Candidatos às duas
classes assim criadas
Algoritmo 3 – Algoritmo de cobertura (AQ)
AISC – 5º Ano – 1º Semestre – 2006/2007
19 / 63
Agentes – Aprendizagem
3.2 Observação e Descoberta
Até aqui analisamos técnicas de aprendizagem que usam exemplos
supervisionados e classificados por alguém. No entanto existem técnicas que
permitem ao agente descobrir por si os exemplos através de algoritmos de
observação e descoberta. Vamos descrever sucintamente dois dos
encontrados na bibliografia, Agrupamento Conceptual e a Descoberta Empírica
3.2.1 Agrupamento Conceptual
Existem dois métodos dentro do agrupamento conceptual o método das
partições e o hierárquico
•
Método Partições
Efectua-se uma partição inicial e altera-se a partição de acordo com os
critérios de optimização. Procede-se à repetição desta alteração até
ser atingido o critério de paragem.
•
Método Hierárquico
Existem dois métodos dentro deste que podem ser usados por si ou em
simultâneo (misto).
o Método hierárquico aglomerativo que consiste em apenas ir
fundindo os elementos em grupos que contenham o máximo de
semelhanças, até restar apenas um elemento (de facto grupo).
o Método hierárquico divisivo que consiste em começar com um
grupo que contém todos os exemplos e ir dividindo em subgrupos de
acordo com um critério discriminante. O critério de paragem é os
grupos ficarem coerentes.
AISC – 5º Ano – 1º Semestre – 2006/2007
20 / 63
Agentes – Aprendizagem
Além de um método de agrupamento necessitamos de um meio para avaliar
os grupos resultantes dos algoritmos. Isto é conseguido recorrendo a
definições matemáticas de métricas. Apenas para mencionar algumas:
•
Simetria – d(x,y) = d(y,x)
•
Positividade – d(x,y) ≥ 0
•
Descriminação – d(x,y) ≠ 0 se x ≠ y
•
Vizinho mais próximo – dkl = min i , min j d(Xi,Xj)
•
Centroides – dkl= || Xk – Xl ||2
•
Etc...
Tendo isto por base, existem algoritmos que podem ser aplicados, é o caso
do Cluster/2
Sendo CI o conjunto de instancias e K o numero de agrupamentos a formar
1.0 Escolher K instâncias (sementes)
2.0 Para cada semente:
2.1 Generalizar ao máximo (estrelas)
2.2
2.3
2.4
2.5
apenas limitado
outras sementes
Tornar os grupos disjuntos
Se satisfeito com a divisão então:
2.3.1 Devolve partição
Senão escolhe novas sementes para cada grupo formado
Volta a 2.0
Algoritmo 4 -
pelas
Cluster/2
Para tornar os conjuntos disjuntos aplica-se este algoritmo:
Sendo A e B dois grupos e C1,...,Ck os elementos comuns.
AISC – 5º Ano – 1º Semestre – 2006/2007
21 / 63
Agentes – Aprendizagem
1.0 Retirar os ci de A e B e coloca-los numa lista de excepções
2.0
(le)
Repetir:
2.1 Retirar elemento de le
2.2 Coloca-lo alternadamente em A e em B
2.3 Obter para cada caso as caracterizações maximamente
expecíficas.
2.4 Optar por uma delas
2.5 Voltar a 2.1 até le ser vazio.
Algoritmo 5 – para tornar os conjuntos disjuntos
Para uma descrição mais detalhada destes métodos consultar a bibliografia.
3.2.2 Descoberta Empírica
A ideia subjacente a este tipo de método de aprendizagem é, temos os dados e
pretendemos chegar às leis (ou teorias ou regras). Podemos considerar a
existência de dois tipos de leis, qualitativas e as quantitativas.
Um algoritmo de descoberta de leis quantitativas encontrado na bibliografia
foi o Bacon 6.0. De forma resumida este sistema funciona em 2 fases:
•
Numa primeira fase é feita a colecta de dados onde se procura todas
as variáveis independentes e dependentes. De seguida calcula-se
todos os valores das variáveis dependentes para as diversas
combinações de variáveis independentes.
•
Numa segunda fase o algoritmo tenta correlacionar os dados obtidos
de uma forma heurística, com o objectivo de encontrar leis que
justifiquem os resultados obtidos. Por exemplo chegar a uma
expressão matemática que defina a forma como as variáveis
independentes se relacionam com as dependentes.
AISC – 5º Ano – 1º Semestre – 2006/2007
22 / 63
Agentes – Aprendizagem
3.3 Analítica
A aprendizagem analítica fundamenta-se na técnica de Generalização Baseada
em Explicações. Essencialmente consiste em usar regras conhecidas para
explicar os conceitos e a geração de novas regras baseadas nas regras
existentes para explicar os conceitos que não conhece.
Existem 3 fases nesta técnica:
•
Explicar: Trata-se de através da análise das regras conhecidas
explicar que um determinado objecto (instancia) é parte de um
conceito alvo.
•
Analise: Pretende-se generalizar o objecto em causa, ou seja tendo
em conta as regras e a instancia, verificar se algum valor da instância
em causa pode ser variável (genérico).
•
Refinar: Construir uma nova regra que contemple o objecto, caso este
apresente alguma particularidade não coberta pelas regras já
existentes.É usado o seguinte algoritmo.
Dados:
Instancia positiva, conceito alvo.
Teoria sobre o domínio.
Determinar:
Hipótese compatível com o conceito a partir dos exemplos
1.0 Hipóteses = {}
2.0 Para cada exemplo de treino não coberto pelas hipóteses:
2.1 Explicar (provar) como o exemplo de treino satisfaz o
2.2
2.3
conceito alvo usando a teoria sobre o domínio
Analisar a explicação generalizando o máximo de forma
compatível com a explicação
Refinar as hipóteses acrescentando uma nova regra cujos
antecedentes são as condições determinadas e cujo
consequente afirma o conceito alvo
AISC – 5º Ano – 1º Semestre – 2006/2007
23 / 63
Agentes – Aprendizagem
Algoritmo 6 – algoritmo para refinar
3.4 Baseada em casos
A aprendizagem baseada em casos consiste numa forma de resolver problemas
recorrendo a casos conhecidos. A arquitectura deste sistema tem 4 fases:
•
Recolha
•
Reutilização
•
Revisão
•
Retenção
Estas fases são detalhadas no seguinte algoritmo:
Dados:
Conjunto de casos conhecidos C
Conhecimento geral K (opcional), e um problema não resolvido P
Determinar:
Uma solução S, para P usando K e elementos adaptados de C, Ci
Transforma S+P num novo caso de C
1.0 Recolher casos relevantes para P
2.0 Repetir até estar satisfeito um critério de paragem
2.1 Reutilizar casos recolhidos Ci produzindo S’
2.2 Rever S’ originando S
3.0 Reter S+P como novo caso de C
Algoritmo 7 – algoritmo para uma aprendizagem baseada em casos
3.5 Aprendizagem Indutiva
Na aprendizagem indutiva são dadas entradas específicas e o resultado
correcto da função desconhecida e deve-se tentar encontrar a tal função ou
uma aproximação. De forma mais formal, diz-se que um exemplo é um par (x,
AISC – 5º Ano – 1º Semestre – 2006/2007
24 / 63
Agentes – Aprendizagem
f(x)), onde x é a entrada e f(x) é a saída da função aplicada a x. A tarefa da
inferência indutiva pura (ou indução) é:
Dada uma colecção de exemplos de f, retornar uma função h que se
aproxime de f.
A função h é chamada hipótese. A razão pela qual a aprendizagem é difícil
de um ponto de vista conceptual, é que não é fácil saber se uma hipótese h
específica é uma boa aproximação de f. Uma boa hipótese irá generalizar
bem – isto é, irá prever correctamente exemplos ainda não vistos. Este é o
problema fundamental da indução.
Exemplo:
A figura a) representa os exemplos, a função f é desconhecida. As figuras b)
e c) representam possíveis funções h. Não há razão que nos faça preferir b
ou c.
Figura 3 – b) e c) são funções possíveis para representar a)
AISC – 5º Ano – 1º Semestre – 2006/2007
25 / 63
Agentes – Aprendizagem
3.5.1 Indução por arvores de decisão
A indução por árvores de decisão é uma das formas mais simples e também
uma com maior sucesso. Uma árvore de decisão recebe como entrada um
objecto ou situação descritos por atributos e devolve uma decisão.
Exemplo:
O objectivo é inferir uma “regra” que permita dizer se devemos ou não
esperar por uma mesa num restaurante, o objectivo é aprender uma definição
para o predicado de objectivo VaiEsperar,
Começa-se por definir os atributos que descreverem os exemplos:
1. Alternativa: existe um restaurante alternativo próximo?
2. Bar: existe uma área de bar confortável para esperar?
3. Sexta/Sábado: hoje é Sexta ou Sábado?
4. Fome: temos fome?
5. Clientes: número de pessoas no restaurante (Nenhum, Algum, Cheio)
6. Preço: gama de preços (€, €€, €€€)
7. Chuva: está a chover lá fora?
8. Reserva: fizemos uma reserva?
9. Tipo de restaurante: Francês, Italiano, Tailandês, Burger, …
10. Estimativa do tempo de espera: 0-10, 10-30, 30-60, >60
AISC – 5º Ano – 1º Semestre – 2006/2007
26 / 63
Agentes – Aprendizagem
Figura 4 – Uma árvore de decisão para definir se vamos ou não esperar por uma
mesa
3.5.1.1 Como induzir as árvores de decisão a partir de exemplos
Atributos
Conclusão
Exemplo
X1
X2
X3
X4
X5
X6
X7
X8
X9
X10
X11
Alt
Sim
Sim
Não
Sim
Sim
Não
Não
Não
Não
Sim
Não
Bar
Não
Não
Sim
Não
Não
Sim
Sim
Não
Sim
Sim
Não
Se/Sa
Não
Não
Não
Sim
Sim
Não
Não
Não
Sim
Sim
Não
Fo
Sim
Sim
Não
Sim
Não
Sim
Não
Sim
Não
Sim
Não
Cli
Alguns
Cheio
Alguns
Cheio
Cheio
Alguns
Nenhum
Alguns
Cheio
Cheio
Nenhum
AISC – 5º Ano – 1º Semestre – 2006/2007
Pre
€€€
€
€
€
€€€
€€
€
€€
€
€€€
€
Chu
Não
Não
Não
Sim
Não
Sim
Sim
Sim
Sim
Não
Não
Res
Sim
Não
Não
Não
Sim
Sim
Não
Sim
Não
Sim
Não
Tipo
Francês
Tailandês
Hamburger
Tailandês
Francês
Italiano
Hamburger
Tailandês
Hamburger
Italiano
Tailandês
Tes
0-10
30-60
0-10
10-30
>60
0-10
0-10
0-10
>60
10-30
0-10
27 / 63
VaiEsperar
Sim
Não
Sim
Sim
Não
Sim
Não
Sim
Não
Não
Não
Agentes – Aprendizagem
X12
Sim
Sim
Sim
Sim
Cheio
€
Não
Não
Hamburger
30-60
Figura 5 – Exemplos para o domínio do restaurante
Uma solução simples é construir uma árvore que a cada exemplo faça
corresponder um caminho que leve à folha, onde o caminho testa cada
atributo. Quando for dado o mesmo exemplo a árvore chega à classificação
certa. Mas, e para os outros casos?
Como a árvore apenas memoriza as observações, não extrai qualquer
padrão, não se pode esperar que ela seja capaz de extrapolar para exemplos
não vistos antes.
A solução é tentar encontrar-se a menor árvore de decisão que descreva um
grande número de exemplos de um modo conciso. Como encontrar a menor
árvore de decisão é um problema intratável, aplicam-se heurísticas simples
que ajudam a encontrar uma árvore pequena. A ideia por detrás do algoritmo
a aplicar consiste em “testar o atributo mais importante primeiro”, em que “mais
importante” significa aquele que fizer maior diferença para a classificação de
um exemplo.
Exemplo:
Com um conjunto de 12 exemplos de treino, classificados como positivos e
negativos, em que positivos são aqueles cujo valor do Objectivo VaiEsperar é
Sim e negativos aqueles cujo valor é Não escolhemos um atributo.
Se por exemplo se escolher o atributo Tipo ficamos com 4 resultados
possíveis, cada um deles com o mesmo número de exemplos positivos e
negativos o que leva a concluir que o atributo é fraco. Por outro lado a
escolha do atributo cliente faz com que fiquemos com 3 resultados possíveis,
em que se o resultado é Nenhum ou Alguns ficamos só com exemplos
positivos ou só exemplos negativos, o que permite responder definitivamente
não e sim respectivamente, cliente é portanto um atributo importante. Se o
valor é cheio, ficamos com um conjunto de exemplos positivos e negativos e
AISC – 5º Ano – 1º Semestre – 2006/2007
28 / 63
Sim
Agentes – Aprendizagem
voltamos a ter o problema inicial agora com menos exemplos e menos um
atributo.
1
2
Francês
1
5
3
5
4 6
7 9
Tipo
Italiano
6
10
8
10
12
11
Tailandês
4
8
2 11
Hambúrger
3 12
7
9
Figura 6 – Escolha do atributo tipo
1
2
Nenhum
7
3
4 6
5
7 9
Clientes
Alguns
1
3
6
8
10
12
11
Cheio
4 12
2 5 9 10
Faminto
8
11
Não
5
9
4
2
Sim
12
10
Figura 7 – Escolha do atributo cliente
Genericamente falando a ideia do algoritmo é: escolher o atributo “mais
importante” como raiz da árvore ou sub-árvore tendo em consideração 4
situações:
•
Se existem exemplos positivos e negativos, escolher o melhor atributo
para os dividir. A Figura 3 (b) mostra o atributo fome a ser usado para
dividir os exemplos restantes.
•
Se todos os exemplos são positivos ou todos são negativos podemos
parar. Na figura (b) Nenhum e Alguns são exemplos disso.
AISC – 5º Ano – 1º Semestre – 2006/2007
29 / 63
Agentes – Aprendizagem
•
Se não restam exemplos, então tal situação nunca foi observada e
devolvemos um valor de defeito.
•
Se não restam atributos e ainda temos exemplos positivos e negativos
então temos um problema. Isto significa que os exemplos têm
exactamente a mesma descrição, mas classificações diferentes. Esta
situação acontece quando alguns dados estão incorrectos ou quando
os atributos não fornecem informação suficiente para descrever a
situação completamente ou quando o domínio é verdadeiramente não
determinístico; dizemos que existe ruído nos dados (tipicamente
devolve-se valor em maioria).
AISC – 5º Ano – 1º Semestre – 2006/2007
30 / 63
Agentes – Aprendizagem
Função DLT (exemplos,atributos,defeito) devolve árvore de decisão
se exemplos vazio então devolve defeito
senão se todos os exemplos têm a mesma classificação
então devolve classificação
senão se atributos está vazio
então devolve Maioria(exemplos)
senão
melhor = EscolheAtributo(atributos, exemplos)
árvore = nova árvore com melhor na raiz
m = Maioria(exemplos)
paracada valor vi de melhor
exemplos = {elementos de exemplos com melhor=vi}
sub-árvore = DTL(exemplos,atributos-melhor,m)
adiciona um ramo à árvore com etiqueta vi e sub-árvore
devolve verdadeiro
Algoritmo 8 – aprendizagem de árvore de decisão
Clientes?
Nenhum
Não
Cheio
Alguns
Sim
Faminto?
Não
Não
Francês
Sim
Sim
Tipo?
Italiano
Não
Tailandês
Sex/Sáb?
Não
Não
Hambúrger
Sim
Sim
Sim
Figura 8 – A árvore de decisão induzida a partir do conjunto de treino de 12
exemplos
AISC – 5º Ano – 1º Semestre – 2006/2007
31 / 63
Agentes – Aprendizagem
Após a aplicação do algoritmo a árvore resultante é claramente mais
compacta.
A
árvore
resultante
funciona
com
todos
os
12
exemplos
e
é
consideravelmente mais simples que a original. Os atributos chuva e Reserva
não foram incluídos pelo algoritmo aplicado, porque ele pode classificar os 12
exemplos sem esses atributos.
Se fossem adicionados novos exemplos a árvore resultante poderia ser mais
semelhante à original. A árvore resultante da aplicação do algoritmo irá
cometer um erro, pois ela nunca viu um exemplo onde a EsperaEstimada é 010 min. e o restaurante esta Cheio. Isto levanta a questão “se o algoritmo
induz uma árvore consistente, embora incorrecta, a partir dos exemplos, até que
ponto a árvore está incorrecta?”. A resposta a esta questão poderia levantar
novas questões e como tal ultrapassa o ambito deste trabalho. Sugere-se a
consulta por exemplo da obra Inteligência Artificial de Stuart e Peter Norvig ou
outra obra.
3.5.1.2 Escolha de testes de atributos
A escolha de um atributo tem como objectivo minimizar a profundidade da
árvore final. Um atributo perfeito divide os exemplos em conjuntos que são
todos positivos ou todos negativos. O atributo cliente não é perfeito mas é
bastante bom. O atributo tipo é realmente inútil porque divide o conjunto de
exemplos com aproximadamente a mesma proporção de exemplos positivos
e negativos.
Torna-se portanto definir uma medida formal de “bastante bom” e “realmente
inútil”, a medida precisa de o valor máximo quando os atributos são perfeito e
o valor mínimo quando o atributo for absolutamente inútil. Uma medida
apropriada é a quantidade esperada de informações fornecidas pelo atributo,
que é calculada através de uma expressão matemática.
Para se entender a noção de informações, pode-se pensar como a resposta
a uma pergunta, a quantidade de informações contidas na resposta depende
do conhecimento anterior do indivíduo. Quanto menos se sabe, mais
AISC – 5º Ano – 1º Semestre – 2006/2007
32 / 63
Agentes – Aprendizagem
informações são fornecidas. A teoria da informação mede o conteúdo de
informação em bits.
Um bit de informação é suficiente para responder a uma pergunta do tipo
sim/não sobra a qual não se tem nenhuma ideia. Por exemplo se lançarmos
uma moeda imparcial qual a quantidade de informação necessária?
Em geral, se cada resposta possível vi têm probabilidade P(vi), então o
conteúdo de informação I da resposta real é dado por:
n
I ( P(V1 ),..., P (v n )) =∑ − P (vi ) log 2 P (vi )
i =1
No caso do lançamento da moeda, temos:
1 1
1
1 1
1
I ( , ) = − log 2 − log 2 = 1bit
2 2
2
2 2
2
3.6 Aprendizagem bayesiana
É um método de aprendizagem que se baseia na criação de um modelo
estatístico.Os modelos estatísticos variam desde o cálculo simples de médias
até a construção de modelos complexos, como redes bayesianas e redes
neuronais. O teorema de Bayes mostra como alterar a probabilidade a priori
tendo em conta novas evidências de forma a obter a probabilidade a posteriori.
Figura 9 – Teorema de Bayes
AISC – 5º Ano – 1º Semestre – 2006/2007
33 / 63
Agentes – Aprendizagem
P(Ai) são as probabilidades a priori (probabilidade inicial).
P(B | Ai) probabilidade de B sabendo que ocorreu Ai.
P(Ai | B) são as probabilidades a posteriori.
Com
Exemplo:
Supor que um médico pretende fazer um diagnóstico em que as alternativas
se excluem e são as seguintes:
•
O doente tem um tipo especial de cancro
•
O doente não tem cancro
O resultado dos testes de laboratório pode ser:
•
– (negativo)
•
+ (positivo)
Conhecimento prévio (a priori):
•
0,8% da população tem este tipo de cancro
•
O resultado dos testes acerta em 98% dos casos positivos e 97% dos
negativos
Resumindo os dados tem-se:
P(cancro) = 0.008
P(~cancro) = 0.992
P(+ | cancro) = 0.98
P(+ | ~cancro) = 0.03
P(- | cancro) = 0.02
P(- | ~cancro) = 0.97
Para um novo doente o teste é positivo. Qual deverá ser o diagnóstico?
AISC – 5º Ano – 1º Semestre – 2006/2007
34 / 63
Agentes – Aprendizagem
O teorema de Bayes responde a esta pergunta ou por outras palavras
permite determinar o diagnóstico mais provável.
O teorema de Bayes mostra como alterar as probabilidades a priori tendo em
conta novas evidências de forma a obter a probabilidade a posteriori.
P(cancro | +) =
0,98 ∗ 0.008
(0,98 ∗ 0,008) + (0,03 ∗ 0,992)
P(cancro | +) =
0,00784
= 0,20851
0,0376
P(cancro | +) = 20, 85%
Importante notar que pelo método de Bayes, nenhuma hipótese é aceite ou
rejeitada completamente; apenas se torna mais ou menos provável à medida
que novos dados são conhecidos.
As dificuldades do método de Bayes na aprendizagem de agentes torna-se
difícil porque:
•
É necessário conhecer inicialmente muitas probabilidades
• Se elas não forem conhecidas, são estimadas
•
No caso geral, determinar a hipótese óptima é linear no
número de hipóteses. Em certas situações, esse custo pode
ser reduzido.
AISC – 5º Ano – 1º Semestre – 2006/2007
35 / 63
Agentes – Aprendizagem
3.6.1 Fórmulas Básicas para Probabilidade
Regra do produto: probabilidade de conjunção de dois eventos A e B
Regra da soma: Probabilidade de disjunção de dois eventos A e B
Teorema da probabilidade total: se eventos A1, ..., Ai são mutuamente
exclusivos com
, então
3.6.2 Classificador Bayesiano ingênuo
Provavelmente, o modelo de rede Bayesiana mais comum utilizado na
aprendizagem de máquina é o modelo de Bayes ingénuo. Neste tipo de
aprendizagem cada instancia X é descrita por uma conjunção de atributos. O
modelo é “ingénuo” porque supõe que os atributos são condicionalmente
independentes uns dos outros, dada a classe.
Funcionamento:
- é necessário fornecer um conjunto de treino da função alvo e apresentar
uma nova instancia descrita pela sequência de atributos X = (<a1, a2, …,
na>), o classificador deve então calcular o valor alvo, ou classificar esta nova
instancia X.
AISC – 5º Ano – 1º Semestre – 2006/2007
36 / 63
Agentes – Aprendizagem
3.7 Aprendizagem por Reforço
Grande parte do conhecimento que todos os seres vivos adquirem ao longo
das suas vidas provém da aprendizagem por reforço. Então o que é a
aprendizagem por reforço? É aprender interagindo com o ambiente.
No modelo da aprendizagem por reforço, o agente interage com o ambiente.
A interacção consiste na percepção do ambiente e na escolha de uma acção
para executar nesse ambiente. A acção altera o ambiente de alguma forma e
esta alteração é comunicada ao agente através de um sinal de reforço (ou
recompensa). Esta recompensa pode ser positiva ou negativa, e reflecte a
qualidade da acção para um estado. A recompensa pode ser imediata ou em
situações mais desafiadoras pode ser futura (caso dos jogos em que apenas
no final sabemos se é vitória, derrota ou empate).
Exemplo de recompensa positiva e negativa:
Ensinar um robot a desviar-se dos obstáculos, sempre que ele toca
num obstáculo recebe uma recompensa negativa, caso se desloque em
espaço aberto recebe uma recompensa positiva.
Figura 10 – A interacção agente-ambiente em aprendizagem por reforço
Um estado caracteriza a situação do ambiente e é especificado por um
conjunto de variáveis que o descrevem. Os sistemas de aprendizagem por
reforço aprendem a mapear situações em acções através de interacções com
AISC – 5º Ano – 1º Semestre – 2006/2007
37 / 63
Agentes – Aprendizagem
um ambiente dinâmico. A execução de uma acção num determinado estado
dá origem a um reforço recebido pelo agente, na forma de um valor
numérico. O agente aprende a executar acções que maximizam a soma dos
reforços recebidos, desde o estado inicial até ao estado final. A escolha de
uma função de reforço (ou recompensa) que transpareça, de uma forma
apropriada, os objectivos do agente é fundamental.
O problema central da aprendizagem por reforço é, portanto, a escolha de
acções. A política define o comportamento do agente, determinando que
acção deve ser executada em cada estado. Quase todos os algoritmos que
implementam este tipo de aprendizagem se baseiam em estimar funções de
valor – funções que determinam quão bom é um estado – função estado-valor
(ou utilidade) V(s) - ou quão bom é executar uma determinada acção num
estado - função acção-valor Q(s,a).
A aprendizagem por reforço é aplicada por exemplo a jogos, o sistema TDGamon de Gerry Tesauro (1992) é um bom exemplo e mostra o potencial das
técnicas de aprendizagem por reforço. O sistema aprendeu a jogar melhor
que qualquer outro até à altura sendo o melhor jogador IA de Gamão e está
entre os 5 melhores jogadores humanos a nível mundial. No TD-Gamon a
recompensa apenas era dada no final da partida. A função de avaliação era
representada por uma rede neuronal completamente ligada com uma única
camada oculta contendo 40 nós.
A aprendizagem por reforço é também aplicada na robótica, por exemplo na
navegação autónoma de veículos. A navegação autónoma é a habilidade de
um veículo mover-se sem intervenção humana até alcançar o seu objectivo,
num ambiente para o qual não está disponível qualquer informação inicial. De
forma geral, para realizar esta tarefa existe uma função de mapeamento que
recebe como entrada os dados dos sensores e são produzidos comandos
que serão enviados aos actuadores do veículo.
Exemplo de aplicação da aprendizagem por reforço no jogo do galo:
AISC – 5º Ano – 1º Semestre – 2006/2007
38 / 63
Agentes – Aprendizagem
X
X
O X
O X
x
X
X
X
O X
O X
O X
O
O
O
O
x
...
...
...
X O X
O X
...
x o
X O X
...
x
...
o
x
...
...
} x joga
} 0 joga
o x
...
} x joga
} 0 joga
x o
x
xo
} x joga
Figura 11 – Arvore que mostra que apenas chegado ao fim do jogo o reforço é obtido
(vitória, derrota ou empate)
AISC – 5º Ano – 1º Semestre – 2006/2007
39 / 63
X
Agentes – Aprendizagem
Estado
.5
?
1
vitória
0
derrota
0
empate
.
o x o
o x x
x o o
?
.
x o
o
o
.
.
.
x
.
.
.
x x x
o
o
.5
.
.
.
.
x
V(s) – Probabilidade estimada de ganhar
Figura 12 – Probabilidade associada à situação do tabuleiro
4 Paradigma
de
Aprendizagem
Conexionista
4.1 Redes Neuronais
As redes neuronais tentam basear-se no conhecimento que temos sobre como
funcionam os neurónios existentes no cérebro humano.
AISC – 5º Ano – 1º Semestre – 2006/2007
40 / 63
Agentes – Aprendizagem
Figura 13 – neurónio biológico
Replicando o funcionamento de um neurónio biológico talvez se consiga
replicar a aprendizagem que os seres biológicos são capazes.
As redes neuronais artificiais são usadas em diversas áreas da investigação de
inteligência artificial, e são bem sucedidas em reconhecimento de padrões,
controlo de processos e controlo de robôs.
AISC – 5º Ano – 1º Semestre – 2006/2007
41 / 63
Agentes – Aprendizagem
4.1.1 Neurónios Artificiais
As redes neuronais baseiam-se na utilização de neurónios artificiais. Estes
neurónios artificiais são software que de uma forma genérica poderiam ser
representados da seguinte forma:
Figura 14 – Possível representação genérica de neurónios artificias
As linhas de input representam linhas de entrada de dados, normalmente de
sensores ou outros neurónios artificiais. Associado a cada linha existe uma
variável que quantifica a “importância” dessa linha, ou seja, um peso.
O quadrado com o Σ no interior representa uma função de soma de inputs.
Nesta função, o somatório de todos os inputs individuais associados aos seus
pesos será comparado com um valor limiar a partir do qual o neurónio
activará o output.
AISC – 5º Ano – 1º Semestre – 2006/2007
42 / 63
Agentes – Aprendizagem
Em função do tipo de output que pretendemos, temos que escolher uma
função de activação adequada. Se pretendemos apenas um output do tipo
binário poderemos usar uma função de activação tipo degrau.
Output
Função activação
Figura 15 – Função activação
Por outro lado, se necessitarmos de uma gama de valores de output a função
de activação terá que ser outra. Uma função de activação muito usada é a
função sigmoide, que apresenta a seguinte expressão matemática:
O gráfico da função sigmoide é apresentado de seguida. Notar que esta função
comporta uma gama de valores de output em função do valor que lhe é
passado pelos inputs.
AISC – 5º Ano – 1º Semestre – 2006/2007
43 / 63
Agentes – Aprendizagem
Figura 16 – gráfico da função sigmoide
Este output pode ser dirigido para outros neurónios ou para a saída da rede
neuronal.
O neurónio artificial é o elemento base de uma rede neuronal. Uma rede
neuronal contém uma quantidade de neurónios conectados de determinadas
formas – Topologia da Rede Neuronal e usa um algoritmo de aprendizagem
para aprender.
4.1.2 Topologias de Redes Neuronais
De seguida apresenta-se duas topologias simples de redes neuronais:
AISC – 5º Ano – 1º Semestre – 2006/2007
44 / 63
Agentes – Aprendizagem
Figura 17 – Rede Monocamada à esquerda. Rede Hopfield à direita.
No caso da rede neuronal em mono camada, existe apenas uma camada de
neurónios entre a entrada e a saída da rede. Neste caso a rede é do tipo
feedforward ou seja o output de um neurónio é o input do próximo neurónio.
No entanto o output do próximo nunca será input do anterior.
Por outro lado na Rede de Hopfield isto não acontece uma vez que o output de
um neurónio é o input do próximo que têm ligado ao seu output o anterior.
Neste caso diz-se que a rede é recorrente (em oposição à situação de
feedforward).
Há topologias em que a camada de entrada na rede não coincide com a
camada de saída. Estes casos denominam-se de redes multicamada. Nestas
topologias existe uma camada de entrada, uma camada de saída e camadas
escondidas (“Hidden layer”).
AISC – 5º Ano – 1º Semestre – 2006/2007
45 / 63
Agentes – Aprendizagem
Figura 18 - camada de entrada, camada escondida e camada de saída
Relativamente à forma como os neurónios se ligam, considera-se que duas
camadas estão completamente ligadas quando todos os neurónios se ligam
uns aos outros. Podemos ter no entanto situações em que os neurónios não
se encontram completamente ligados entre duas camadas.
Relativamente ao numero de neurónios nas camadas de saída e de entradas.
Os neurónios na camada de entrada representam as variáveis às quais a
rede será sensível, ou seja, considerando a ultima rede multicamada
apresentada, supondo que o exemplo anterior era aplicado a uma situação
de reconhecimento de cores. Os 3 neurónios na camada de entrada
poderiam ser sensíveis aos valores das componentes de azul, verde e
vermelho.
Supondo que se aplicava uma função de activação do tipo degrau, podíamos
treinar a rede neuronal para se activar apenas quando se detecta um
determinado tom, por exemplo, azul-escuro ou lilás.
Se pretendemos que a nossa rede neuronal controle por exemplo, um veiculo
actuando apenas num volante e um acelerador (esquecendo questões
relacionadas com segurança rodoviária é claro) provavelmente o mais
AISC – 5º Ano – 1º Semestre – 2006/2007
46 / 63
Agentes – Aprendizagem
adequado seria usarmos a função sigmoide como função de activação e 2
neurónios na camada de saída da rede, um para controlar a velocidade e
outro para o grau de viragem do volante.
4.1.3 Aprendizagem da rede neuronal
Até ao momento vimos de forma sucinta o funcionamento de uma rede
neuronal. No entanto a questão fulcral é: Como é que a rede neuronal
aprende?
A aprendizagem da rede é conseguida por intermédio do ajuste dos valores
dos pesos associados a cada input do neurónio (o valor do w na figura de
explicação do neurónio artificial).
A “decisão” do neurónio é função daquilo que ele recebe em todos os seus
inputs (dos neurónios vizinhos) e comparado com uma função de activação
(que define a forma de activação do neurónio).
No entanto cada input tem um peso (w) associado que de forma simplista,
representa a importância desse input para o neurónio.
Se depois de calcular a soma ponderada de todos os inputs, o neurónio
decidir que vai activar-se, ele vai modificar (incrementar) o peso de todos os
inputs que eram “a favor” da activação. Este incremento é função de um ritmo
de aprendizagem (η). Isto vai fazer com que em decisões futuras os inputs
que “acertam mais vezes” tenham maior peso na decisão de cada neurónio
individual.
Em caso de estarmos numa situação de treino da rede neuronal, o valor real e
correcto é conhecido e pode ser incorporado na forma como a rede aprende.
As seguintes expressões denotam o que foi explicado atrás.
Peso de um input:
I=W * Xi
Valor ponderado de todos os inputs:
AISC – 5º Ano – 1º Semestre – 2006/2007
47 / 63
Agentes – Aprendizagem
n
Σ
(Wk * Xk)
k=0
Aprendizagem (Modificação dos pesos dos inputs):
∆Wk = η * Xi * X
Aprendizagem com exemplos de treino (aprendizagem supervisionada):
∆Wk = η * (Ri - Xi) * X
Sendo:
I - Valor resultante do input
W – Peso do input
Xi- Valor do input associado ao neurónio i
X- Valor do input calculado
Ri – Valor real
AISC – 5º Ano – 1º Semestre – 2006/2007
48 / 63
Agentes – Aprendizagem
5 Paradigma de Aprendizagem Biológica
5.1 Algoritmos Genéticos
Os algoritmos genéticos procuram aplicar os conceitos de evolução das
espécies ao problema da adaptabilidade e aprendizagem de, no nosso caso,
agentes inteligentes.
Na natureza os seres vivos são obrigados a uma adaptação constante às
condições do meio ambiente. Se o indivíduo não for bem sucedido nesta
adaptação eventualmente morre sem deixar descendência. Por outro lado se
esta adaptação for bem sucedida, ele continuara a sobreviver e terá
(provavelmente)
possibilidade
de
se
reproduzir
deixando
na
sua
descendência parte dos seus genes. Genes estes que tornaram possível uma
adaptação com sucesso. Em poucas palavras é a sobrevivência do mais
apto.
De que forma podemos usar este conhecimento para programar agentes
inteligentes com capacidade de aprender?
A ideia fundamental aqui é considerar que uma possível solução
(independentemente se é uma boa ou má solução, eficiente ou ineficiente)
para um determinado problema é o equivalente a um indivíduo. É claro que
esta solução (individuo) terá que ser codificada de tal forma que possa ser
representada por uma cadeia de bits, que representam de alguma forma as
características do indivíduo.
Tal como na natureza existem uma grande diversidade de indivíduos, para
um determinado problema podem existir uma diversidade de soluções.
Existem soluções boas, outras não tão boas e outras simplesmente más.
Necessitamos de conseguir avaliar o valor (mérito) de uma solução.
Tendo isto em mente, consideremos um problema complexo, com diversas
soluções (população), nenhuma delas ideais, mas cada uma com um
determinado mérito. De seguida procede-se a classificar todas as soluções,
de forma decrescente, segundo o seu mérito.
AISC – 5º Ano – 1º Semestre – 2006/2007
49 / 63
Agentes – Aprendizagem
A título de exemplo vamos assumir que apenas 50% da população, as
melhores soluções terão possibilidade de “reprodução”, os restantes 50%
serão eliminados e substituídos pelos descendentes das melhores soluções.
A nossa população (conjunto de indivíduos ou melhor conjunto de soluções)
deu um passo no sentido de ficar mais bem adaptada ao “ambiente”. No
nosso caso específico, o nível médio de mérito na nossa população subiu (à
partida).
Este processo de classificação, reprodução dos melhores e eliminação das
soluções mais fracas, repetido de forma sistemática até ser atingido um
determinado nível médio (ou solução específica) é semelhante à evolução
que acontece nos seres vivos ao longo de milhares de anos. Foi o que
permitiu simples organismos unicelulares evoluírem para os seres vivos
complexos que existem hoje.
De forma mais formal, em pseudo-código o seguinte algoritmo descreve o
funcionamento de um algoritmo genético genérico:
Dados:
o
o
o
o
Função de adaptabilidade ou mérito (fa)
Probabilidade de recombinação (pr)
Probabilidade de mutação (pr)
Critério de paragem (cp)
Determinar:
Individuo que maximiza fa
Algoritmo Genético:
1.0 Definir aleatoriamente e avaliar a população inicial (p0)
2.0 Se existir um individuo em p(i) que satisfaça cp então
2.1 Devolve o indivíduo e pára.
3.0 Senão
3.1 Selecciona indivíduos de p(i) de acordo com fa
3.2 Recombina os indivíduos de acordo com pr
3.3 Muta individuo de acordo com pm
3.4 Define e avalia nova população p(i+1)
3.5 Volta a 2
AISC – 5º Ano – 1º Semestre – 2006/2007
50 / 63
Agentes – Aprendizagem
Algoritmo 9 – algoritmo genético genérico
5.1.1 Selecção e Recombinação de indivíduos
A forma como os indivíduos são seleccionados pode ser variada. Os métodos
mais vulgares são a selecção por roleta, selecção por torneio, selecção por
truncagem.
•
A selecção por truncagem é a mais simples e menos sofisticada.
Neste tipo de selecção, os indivíduos são ordenados pelo seu mérito.
Aqueles que têm um mérito inferior a um limiar são removidos da
população e substituídos por soluções descendentes dos de maior
mérito. Isto é uma solução simplista e potencialmente problemática,
uma vez que algumas soluções de menor mérito poderão conter
solução para futuras mudanças no ambiente.
•
Na selecção por roleta é considerada uma “roleta virtual” com um
número de ranhuras fixo. Os indivíduos de maior mérito recebem uma
maior quantidade de ranhuras, os de menor mérito recebem menos
ranhuras. São escolhidas aleatoriamente 2 ranhuras da roleta e os
indivíduos dessas ranhuras são reproduzidos. Apesar de os indivíduos
de maior valor terem maior probabilidade de reprodução, nunca é uma
certeza de que terão descendentes na próxima geração de indivíduos.
Desta forma as soluções mais fracas continuam a ter uma
possibilidade de sobrevivência, fornecendo ao sistema diversidade
necessária para enfrentar as mudanças.
•
No caso da selecção por torneio, a ideia é diferente. De toda a
população é seleccionado aleatoriamente um número K de indivíduos
(K = tamanho do torneio). Deste grupo K de indivíduos são formados
aleatoriamente N pares de indivíduos. De cada par de indivíduos é
AISC – 5º Ano – 1º Semestre – 2006/2007
51 / 63
Agentes – Aprendizagem
escolhido o melhor (maior mérito). Do grupo resultante repete-se o
processo de formar pares até só existir um par a formar. Quando isto
acontecer recombinam-se os genes dos indivíduos vencedores.
Segundo a bibliografia consultada esta solução apresenta mais
vantagens do que as anteriores, concretamente permite resolução de
problemas não só de maximização como minimização, converge mais
lentamente que anteriores entre outras vantagens.
Uma vez escolhidos os indivíduos a recombinar, a forma como é feita a
recombinação dos genes pode ser a mais variada. De seguida são
apresentadas algumas formas de recombinação (Crossover).
•
“Crossover” de um ponto:
No crossover de um ponto é escolhido um ponto nos genes dos pais.
Os filhos (serão 2) terão os mesmos genes que os pais até esse
ponto, depois desse ponto trocam entre si os genes dos progenitores.
Figura 19 – “Crossover” de um ponto
•
“Crossover” em dois pontos:
No caso do crossover em dois pontos, o princípio é o mesmo que o
crossover num ponto. No entanto o segundo ponto define o final da
troca de informação genética.
AISC – 5º Ano – 1º Semestre – 2006/2007
52 / 63
Agentes – Aprendizagem
Figura 20 – “Crossover” em dois pontos
•
“Cut and Splice”:
Esta situação de crossover é exactamente igual ao crossover num
ponto com uma distinção fundamental: O ponto de corte nos genes
dos pais não é no mesmo ponto. Isto tem como consequência imediata
que os filhos não vão ter o mesmo comprimento na sua cadeia de
informação genética.
Figura 21 – Cut and Splice
•
“Crossover” Uniforme:
Neste tipo de recombinação a situação é semelhante aos anteriores no
facto de termos dois pais e dois filhos. No entanto para cada filho os
seus genes são o resultado da troca entre os bits dos seus pais com
probabilidade de (normalmente 50%).
•
“Crossover” Meio Uniforme:
AISC – 5º Ano – 1º Semestre – 2006/2007
53 / 63
Agentes – Aprendizagem
Este tipo de recombinação é igual à anterior com a seguinte diferença,
numa fase inicial são detectadas as diferenças entre os cromossomas
dos pais. De seguida é aplicada a técnica de crossover uniforme
exactamente em metade dos bits diferentes entre os pais.
•
“Crossover” de Cromossomas Ordenados:
Num crossover de cromossomas ordenados os filhos recebem os
cromossomas dos pais após estes terem trocado sem repetições os
seus cromossomas depois de um determinado ponto de corte. Se o
tamanho final do gene do filho não tiver o mesmo comprimento do dos
seus pais, preenche-se o resto dos genes com os dos pais antes do
ponto de corte.
Existe também, tal como na natureza, a possibilidade de acontecer uma
mutação nos genes dos novos indivíduos. Normalmente a probabilidade de
acontecerem mutações deve ser baixa de forma a termos alguma
estabilidade nos indivíduos da população.
5.1.2 Problemas dos Algoritmos genéticos
A utilização dos algoritmos genéticos apresenta alguns problemas:
•
Restrições computacionais, qual melhor relação: população / numero
de gerações?
•
Melhor relação entre Probabilidade de recombinação/ mutação?
•
Podem não fornecer a melhor solução (máximo local)
•
Operadores usados podem não ser os mais adequados, qual a melhor
definição?
AISC – 5º Ano – 1º Semestre – 2006/2007
54 / 63
Agentes – Aprendizagem
5.1.3 Outros tipos de Algoritmos genéricos
É possível considerar outros tipos de algoritmos genéticos. Um exemplo é o
caso de um algoritmo usado por um vírus. Neste caso, todo o processo é
semelhante ao descrito, diferindo apenas na questão da eliminação de
indivíduos... Nesta tipo de algoritmo genético os mais fracos são infectados
com o código genético dos mais fortes. Desta forma as soluções mais fracas
nunca são completamente eliminadas.
A área de algoritmos genéticos é uma área em constante investigação e
evolução.
AISC – 5º Ano – 1º Semestre – 2006/2007
55 / 63
Agentes – Aprendizagem
5.2 Sistemas Classificadores
Um sistema classificador é essencialmente um misto de um sistema pericial
com algoritmos genéticos.
O sistema pericial usa regras para controlar as suas respostas perante as
percepções do meio ambiente. Os algoritmos genéticos são usados para
escolher as regras que melhor se adaptam ao ambiente.
Existem duas variantes de Sistemas Classificadores mas as suas diferenças
residem apenas na definição do indivíduo usado no algoritmo genético. Numa
variante um indivíduo representa um conjunto de regras, ao passo que na
outra variante um indivíduo representa apenas uma regra.
A seguinte figura representa a arquitectura genérica de um sistema
classificador.
AISC – 5º Ano – 1º Semestre – 2006/2007
56 / 63
Agentes – Aprendizagem
Ambiente
Reacção
Sistema
Classificador
Lista
Percepção
Descoberta de
Classificadores
(Alg. Genético)
Acção
Mensagens
População
de
Classificadores
Conj. Acções
(Regras)
Leilão
Recompensa
Punição
/
Figura 22 - arquitectura genérica de um sistema classificador
O funcionamento de um sistema classificador pode ser bastante complexo.
Uma explicação muito detalhada está fora do âmbito deste trabalho. No
entanto para que a forma de funcionamento de um sistema classificador seja
compreendida, há alguns pormenores a serem esclarecidos antes de se
proceder a uma explicação sucinta.
AISC – 5º Ano – 1º Semestre – 2006/2007
57 / 63
Agentes – Aprendizagem
O ambiente é percepcionado pelo agente e a informação captada é
codificado numa mensagem, que é colocada numa fila de mensagens. Estas
mensagens traduzem o ambiente num determinado instante.
Cada uma destas mensagens é comparada com as regras conhecidas pelo
sistema. Estas regras (Classificadores) são relativamente genéricas. Portanto
numa determinada situação pode acontecer ser possível aplicar um
subconjunto de todas as regras conhecidas.
Qual é o classificador que o sistema escolhe? Para explicar este pormenor é
necessário especificar melhor o que é um classificador.
Os classificadores num sistema classificador, têm a estrutura de:
Condição: Acção (Força)
Ou seja, quando uma determinada Condição acontece, uma determinada
Acção pode ser despoletada, assumindo que tem a Força necessária. Todos
os classificadores têm estes três parâmetros.
A decisão de qual o classificador que é escolhido é feita através de um
processo de leilão.
O facto de um determinado classificador estar a participar num leilão, implica
que este pague uma taxa de participação, assim como uma taxa de licitação.
Isto vai ter como consequência uma diminuição no valor da força de uma
condição.
Se o classificador escolhido for bem sucedido, o que resulta numa Reacção
positiva por parte do Ambiente, o valor da força do classificador é
incrementada caso contrário o valor é decrementado.
Todos os classificadores que não são escolhidos para irem a leilão são
decrementados os valores das suas forças. Desta forma os classificadores
menos requisitados vêm a sua força diminuir.
AISC – 5º Ano – 1º Semestre – 2006/2007
58 / 63
Agentes – Aprendizagem
Os melhores classificadores são usados pelo módulo de algoritmos
genéticos, para descobrir ainda melhores classificadores que substituem os
classificadores já existentes de menor força.
AISC – 5º Ano – 1º Semestre – 2006/2007
59 / 63
Agentes – Aprendizagem
6 Conclusões
Neste capítulo avalia-se o trabalho desenvolvido e mencionam-se os
objectivos que foram concretizados, referem-se alguns aspectos que
poderiam estar na base de um trabalho futuro.
6.1 Trabalho realizado
No trabalho pesquyisamos várias fontes sobre aprendizagem de agentes e
que deu origem a este relatório.
6.2 Trabalho futuro
Poderiasse escolher um tema abordado neste trabalho, por exemplo as redes
neuronais ou outro e aprofunda-lo de modo a ter-se as bases teóricas de tal
modo fortes que permitissem implementar.
Poderiasse também implementar agentes com diferentes módulos de
aprendizagem e comparar o seu comportamento “aprendiz” em alguns tipos
de problemas.
6.3 Apreciação final
O trabalho deu a conhecer aos elementos do grupo a existensia de inúmeros
métodos que podem ser aplicados em agentes de modo a dota-lo de
aprendizagem. Alguns dos temas poderiam ser aprofundados de tal modo
que possivelmente dariam para um semestre. Alguns dos métodos tratados
neste relatório despertaram o interesse pelo assunto como é o caso dos
algorimos genéticos, redes neuronais e métodos de aprendizagem não
supervisionada.
Por fim concluímos que os objectivos do trabalho foram alcançados.
AISC – 5º Ano – 1º Semestre – 2006/2007
60 / 63
Agentes – Aprendizagem
Bibliografia
António Silva, Carlos Ramos (2006/2007); “Apontamentos das Aulas Teóricas
de Agentes Inteligentes e Sistemas Cooperativos”; ISEP
“Sebenta da Cadeira de Agentes Inteligentes e Sistemas Cooperativos”; ISEP
Ernesto Costa, Anabela Simões; “Inteligência Artificial – Fundamentos e
Aplicações”; FCA
Stuart Russell, Peter Norvig; “Inteligência Artificial”; Editora Campos
Bradd L. Miller, David E. Goldberg; “Genetic Algoriths, Tournement Selection
and the Effects of Noise”; IlliGAL report 95006 – July 1995
Sobre redes Neuronais:
http://www.faqs.org/faqs/ai-faq/neural-nets/part1/
http://www.codeproject.com/useritems/NeuralNetwork_1.asp
http://www.codeproject.com/useritems/Backprop_ANN.asp
http://www.codeproject.com/useritems/GA_ANN_XOR.asp
Sobre algoritmos genéticos:
http://www.codeproject.com/cs/algorithms/Genetic_Algorithm.asp
http://en.wikipedia.org/wiki/Mutation_%28genetic_algorithm%29
http://en.wikipedia.org/wiki/Crossover_%28genetic_algorithm%29
http://webservicesfree.com/Articles/Artificial-Intelligence-Articles/GeneticAlgorithms-Selection-Methods.htm
http://geneticalgorithms.ai-depot.com/Tutorial/Overview.html
http://geneticalgorithms.ai-depot.com/
http://www.ai-junkie.com/ai-junkie.html
AISC – 5º Ano – 1º Semestre – 2006/2007
61 / 63
Índice Remisso
agente aprendiz......................11, 13, 14
Inteligência Artificial............. ix, 32, 61
Agrupamento Conceptual..................20
método das partições......................... 20
algoritmo de cobertura (AQ)....... 11, 16
Método Hierárquico.......................... 20
algoritmo ID3.............................. 18, 19
Método hierárquico aglomerativo..... 20
algoritmos genéticos.12, 49, 54, 55, 56,
Método hierárquico divisivo............. 20
59, 61
módulo Critico...................................15
Aprendizagem... 1, ii, ix, 11, 12, 13, 16,
24, 33, 37, 40, 47, 48, 49
módulo de aprendizagem............ 14, 15
módulo Decisor................................. 15
aprendizagem analítica......................23
aprendizagem baseada em casos....... 24
aprendizagem por reforço............37, 38
Bacon 6.0...........................................22
Bayes ingénuo................................... 36
Descoberta Empírica................... 20, 22
Espaço de Versões.............................17
formas de recombinação....................52
função de activação............... 43, 46, 47
função de activação tipo degrau........ 43
função de soma de inputs.................. 42
módulo Modificador..........................15
neurónio biológico.............................41
neurónios artificiais........................... 42
predicado de objectivo...................... 26
probabilidade a posteriori............33, 35
probabilidade a priori........................ 33
Rede Hopfield................................... 45
Rede Monocamada............................45
redes multicamada.............................45
redes neuronais....iii, 11, 33, 40, 41, 42,
44, 60
função sigmoide.................... 43, 44, 47
selecção por roleta.............................51
Generalização
selecção por torneio...........................51
Baseada
em
Explicações....................................23
heurísticas..........................................28
Hidden layer...................................... 45
inferência indutiva pura.....................25
selecção por truncagem..................... 51
sistema classificador..............56, 57, 58
técnica de treino supervisionada....... 16
teoria da informação..........................33
Agentes – Aprendizagem
tipos de hipóteses.............................. 17
árvore de decisão.......18, 26, 27, 28, 31
AISC – 5º Ano – 1º Semestre – 2006/2007
63