Inteligência Artificial
Fabrício Enembreck
1
Estrutura da Apresentação






Introdução
Problemas e Busca
Representação de Conhecimento
Aprendizado de Máquina
Sistemas Especialistas
Conclusões
2
Introdução




IA: Computador Inteligente?
Sistemático não é inteligente
Computador X Humano
Comportamentos Humanos naturais são os
mais difíceis de imitar: pensar, aprender,
reconhecer, falar, etc...
 “Conjunto de técnicas que visam atribuir
comportamentos inteligentes a sistemas
e/ou computadores”
3
Histórico
 Décadas de 50 e 60:




Grande expectativa em relação a IA
Encantamento de pesquisadores no
desenvolvimento de Resolvedores Gerais de
Problema: os computadores inteligentes
Barreira da limitação do poder computacional
Alternativa: separar o conhecimento do
mecanismo de raciocínio resultaram nos
Sistemas Especialistas
4
Histórico
 Décadas de 60 e 70:



Grande frustação dos pesquisadores
Poder computacional limitado
Toda técnica é um modelo extremamente
simplificado do comportamento humano
 Meados dos anos 80/90

Pesquisa em IA volta a despertar interesse com
novas técnicas, maior poder computacional e,
principalmente, ciente de suas limitações
5
Problemas e Busca
6
Definição do Problema
 Considerações:
•
•
•
•
•
Representação Computacional do problema
Objetivo (o que se pretende alcançar)
Onde Iniciar
Como modificar os estados
Como identificar modificações úteis na solução do
problema
7
Problemas Difíceis
 Definições:
•
•
•
•
•
Entendimento de Linguagem Natural.
Jogar Xadrez.
Resolver Integrais Indefinidas.
Prever o clima.
Prever mudanças no estoque de uma loja
8
Definição do Problema como um
Espaço de Estados (Cont.)
 Uma possível estratégia para solução de
problemas é listar todos os estados
possíveis.
 A solução do problema consiste em
percorrer o espaço de estados a partir do
estado inicial até o estado meta.
 É necessário desenvolver um conjunto de
operadores que modifique um estado para
um outro estado.
9
Exemplo: Problema dos Jarros de
Água
4 lt
3 lt
Sem limite
de Água
Objetivo: 2 litros no jarro 4 lt
Restrições:
•Cada jarro não pode conter mais água do que a sua capacidade;
•Os jarros não possuem marcas, logo quando a água é retirada de
uma fonte o jarro fica cheio
10
•Quando água é jogada de um jarro ele precisa ficar vazio
Estados do
Jarros de Água
(0,0)
(4,0)
(3,0)
(2,0)
(1,0)
(4,1)
(3,1)
(2,1)
(1,1)
(4,2)
(3,2)
Espaço de
Busca
(0,1)
(1,2)
(0,2)
(1,3)
(X,Y)
(2,2)
Jarro 4 lt.
(4,3)
(3,3)
(2,3)
(0,3)
Estados Solução
Jarro 3 lt.
11
Operações com Jarros de Água





Colocar 3 lt. no jarro 3
Colocar 4 lt. no jarro 4
Esvaziar jarro 3
Esvaziar jarro 4
Coloca o conteúdo do
jarro 3 no jarro 4
 Outros ???
(x,y) -> (x,3)
(x,y) -> (4,y)
(x,y) -> (x,0)
(x,y) -> (0,y)
(0,y) -> (y,0)
12
Restrições
 Regras de Produção podem ser utilizadas
para modificar um estado
 As Regras implementam as restrições do
problema
(x,y), x<4 -> (x,0)
(x,y), y<3 -> (0,y)
(x,y), x>0,y=0 -> (y,0)
13
Regras de Produção
 Reduzem o Espaço de Estados
 Geram a Árvore de Busca
(0,0)
(4,0)
(4,3)
(0,0)
(1,3)
(4,3)
Encher jarra 3
(0,3)
Despejar
conteúdo de
3 em4
(0,0)
(3,0)
Encher jarra 3
Despejar
(2,0) conteúdo de (0,2)
3 em4
Esvaziar
jarra 4
(4,2)
Encher jarra
(3,3)
4 com o
conteúdo de 3
14
Estratégias de Busca
a
a
b
d
h
b
c
e
i
f
j
d
g
k
Busca em Largura
c
h
e
i
f
j
g
k
Busca em Profundidade
15
Outro Problema
 Problema do Caixeiro Viajante
•
•
•
•
Lista de cidades para visitar
Lista de distâncias entre cada cidade
Visite cada cidade apenas uma vez
Encontre o menor trajeto
16
Busca Heurística
 Muitos problemas possuem espaços de
busca que são muito grandes para serem
examinados completamente.
 É possível construir estratégias que não
prometem a melhor solução, mas que
encontram uma “boa” resposta rapidamente.
17
Técnicas de Busca Heurística
Gerar-e-testar
Subida da Encosta
Busca Best-First
18
Gerar e Testar
 Gerar e testar:
• Repita até que a solução seja encontrada
•
Gere um próximo estado
19
Subida da Encosta
 Usa heurística para mudar para estados que
são melhores que o estado corrente
 Sempre muda para o melhor estado quando
possível
 O processo termina quando todos os
operadores tiverem sido aplicados e nenhum
dos estados resultantes são melhores que o
20
estado corrente
Subida da Encosta
Função de Otimização
y = f(x)
y
x
21
Recozimento Simulado (Cont.)
 A busca inicialmente faz grandes saltos,
explorando muitas regiões do espaço
 Os saltos são gradualmente reduzidos e a
busca torna-se uma subida de encosta
simples (busca por um ótimo local)
22
Simulated Anneling
23
Busca Best-First
 Combina as vantagens das buscas em
Largura e Profundidade
•
•
Profundidade: segue um caminho único, não
precisa gerar todos os possíveis caminhos
Largura: não tem problemas com loops ou
caminhos sem solução
 Busca Best First : explora o caminho mais
promissor visto
24
Busca Best-First
s
f(n) = g(n) + h (n)
g(n)
n
h(n)
t
• f(n) é uma função que estima o valor heurístico do nó n.
• s é o nó inicial, t é uma solução
25
Representação de Conhecimento
Herança
Lógica Matemática
Redes Semânticas
Frames
26
Representação de Conhecimento
 Algumas tarefas exigem conhecimento do
domínio
 Existem diversas técnicas mas nenhuma
delas consegue representar exatamente a
realidade
 Escolher uma boa representação faz grande
diferença
27
Conhecimento e Mapeamentos
 Conhecimento é uma coleção de fatos sobre
o domínio
 É necessário uma representação de fatos
que possa ser manipulada por um programa
 Envolve linguagem de representação e
consulta
28
Representação de Propriedades
 Adequabilidade Representacional
 Adequabilidade Inferential
 Eficiência na Inferência
 Eficiência na Aquisição
29
Herança
 É, geralmente, utilizada para fornecer uma
estrutura de representação que suporta
diretamente mecanismos de inferência.
 Herança de Propriedades é um mecanismo
de herança comum.
 Objetos pertencem a classes.
 Classes possuem propriedades que são
herdadas por objetos que pertencem à
30
classe.
Hierarquia de Classes
 Classes são organizadas em uma hierarquia,
dessa forma algumas classes são membros de
classes mais gerais.
 Há variedade em estratégia de representação
usadas em IA que são baseadas em herança:
•
•
•
regras de produção
redes semânticas
sistema de frames
31
Lógica
 Usa dedução matemática para derivar novo
conhecimento.
 Lógica de Predicados é um poderoso
esquema de representação para programas
de IA.
 Lógica de Predicados é muito utilizada para
como ferramenta de representação e
inferência.
32
Representação de Fatos
 Representação lógica é comum em
programas de IA:
•
•
•
Malhado é um cachorro
• cachorro(Malhado)
Todos os cachorros têm rabo
• x:cachorro(x)->tem_rabo(x)
Malhado tem rabo
• tem_rabo(Malhado)
33
Relações isa e ako
 O exemplo usa herança sem explicitamente
ter predicados isa ou ako.
 É possível reescrever os fatos usando fatos
isa e ako explicitamente:
 isa(Marcos,homem)
 isa(Marcos,Pompeu)
 ako(Pompeu,Romano)
34
Redes Semânticas
 Nós representam entidades e arcos
representam relações entre nós.
 Rede de Herança é um bom exemplo.
 É possível transformar cada arco em um
predicado binário que relaciona 2 nós.
 É possível, também, criar uma rede
semântica para representar uma coleção de
predicados.
35
Rede Semântica
Pessoa
Chuta-com
Direita
ako
Adulto
Mascul.
Altura
1,75
ako
1,82
Jogador
Futebol
ako
.034
Média de
gols
Lateral
isa
Palestra
Time
Carlos
0.56
ako
Atacante
Média de
gols
0.67
isa
Pelé
Time
Santos
36
Predicados
Homem(Marcos)
Casado(Marcos,Madonna)
Transmite(Madonna,Marcos,Sarampo)
Homem
isa
casado
Marcos
Receptor
Sarampo
algo-transmitido
G17
Madonna
Transmissor
isa
Vírus
37
Múltipla Herança
 Redes Semânticas podem suportar múltipla
herança, portanto, é possível revisar o
algoritmo básico de herança.
Pessoa
ako
Não
auto-estima
auto-estima
SIM
ako
Estudante
Pai
isa
isa
Dave
Dave tem auto-estima?
38
Frames (Cont.)
 Objetos pertencem a Classes
 Um objeto pode pertencer a mais de uma
classe
 Objetos podem estar dispostos em uma
taxonomia que permite herança de
propriedades
 Objetos podem possuir uma representação
complexa
39
Proposta de Frames
 Criada em 1974 por Marvin Minsky
 Objetivo de representar grandes quantidades
de dados de forma estruturada
 Frames podem estar relacionados e
compartilhar similaridades
 A disposição dos frames forma uma rede
semântica
40
Estrutura dos Frames (Cont.)
• Estrutura genérica de um frame
41
Estrutura dos Frames (Cont.)
Madeira
material
Móvel
pernas
um tipo de
Branca
cor
Cadeira
é um
Cadeira do João
4
Móvel
ako
valor : RAIZ
material
default: madeira
pernas
tipo: inteiro
default: 4
Cadeira
ako
valor : Móvel
cor
default: branca
Cadeira de João
isa
valor : Cadeira
Rede de Semântica
42
Representação de Frames em
Prolog
Móvel
ako
valor : RAIZ
material
default: madeira
pernas
tipo: inteiro
default: 4
Cadeira
ako
valor : Móvel
cor
default: branca
Cadeira de João
isa
valor : Cadeira
movel(ako,valor,’RAIZ’).
movel(material,default,madeira).
movel(pernas,tipo,inteiro).
movel(pernas,default,4).
cadeira(ako,valor,movel).
cadeira(cor,default,branca).
cadeira_de_joao(isa,valor,cadeira).
Conjunto de fatos
43
Raciocinadores de Herança
 Raciocinadores do Menor Caminho

solução mais próxima na hierarquia
 Raciocinadores Crédulos

escolhe arbitrariamente uma solução
 Raciocinadores Céticos

Pacifista
nenhuma solução é escolhida ako
ako
Quacker
Republicano
isa
isa
Nixon
44
Aprendizado de Máquina
(Data Mining ou KDD)
45
Banco
de Dados
Estatística
AM
Inteligência
Artificial
46
O que se pode fazer com
Aprendizado
$
Volume
Conhecim.
Valor
Informação
Dados
47
Etapas do Processo de KDD
INTERPRETAÇÃO/
AVALIAÇÃO
DATA
MINING
CONHECIMENTO
?
PADRÕES
TRANSFORMAÇÃO
PRÉ-PROCESSAMENTO
DADO
TRANSFORMADO
DADO
PROCESSADO
SELEÇÃO
FAYYAD 1996
DADO
ANALISADO
DADOS
48
Aprendizado por Exemplos:
Indução
 Na estratégia de aprendizado por indução, o
sistema adquire os conceitos através de
inferências indutivas realizadas sobre fatos
fornecidos ou observados.
49
Indução & Dedução
 Exemplo Dedução:
•
•
todos os homens são fortes
Se Pedro é homem Então Pedro é forte
 Exemplo de Indução:
•
•
A maioria dos homens é forte
Se Pedro é homem Então Pedro é forte
50
Identificar a Tarefa
 Classificação
 Associação
 Clustering
51
Aprendizado por Indução:
Classificação
 O objetivo é associar a cada exemplo, ou
observação, uma classe à qual ele pertence
 Os conceitos construídos estão representados
na forma de um classificador
Exemplos
Algoritmo
de
Aprendizado
Classificador
52
Aprendizado por Indução:
Classificação (cont.)
 O exemplo a ser classificado é submetido
aos conceitos adquiridos, e uma decisão
sobre a sua classe é devolvida pelo
classificador
Exemplo a
ser
classificado
Sistema
Classificador
Decisão
53
Problemas com Classificação
A1
A1
A2
A2
A1
54
A2
•Aprendizado - Árvores de
Decisão (Cont.)
Exterior
ensolarado
nublado
chuvoso
umidade
alta
normal
Não Pratica
Pratica
 Algoritmo de Construção
•
•
Entrada: Conjunto de Exemplos E
Saída: Árvore de Decisão T
55
Outros métodos de Aprendizado
por Exemplos
 Redes Neurais
também conhecidas como o modelos
coneccionistas
• são redes interconectadas formadas por elementos
computacionais muito simples
camadas
intermediárias
camada
• baseadas no modelo de
de
funcionamento do cérebro entrada
•
conexões
camada
de
saída
56
Algoritmos Genéticos
110110
32
110110
111101
111101
111101
001101
24
001101
000110
000110
010110
010111
24
010111
010100
010100
010100
101100
20
101100
101111
101111
101110
População
Função de
Inicial Adequabilidade
Seleção
Cruzamento Mutação
Nova
População
57
Clustering
 Exemplo: Agrupar clientes com
comportamentos semelhantes
A1
A2
58
Regras de Associação
 Descobrir associações entre venda de
produtos
 Exemplos:



Se Café e Pão então Manteiga
Se Cerveja então Café
Se CD e Jornal então Revista e Chocolate
59
Sistemas Especialistas
60
Sistemas Especialistas
 Sistema substitui o Especialista Humano?
 Ferramenta de Apoio à tomada de decisão
 Aplicações:




Diagnóstico Médico
Sistemas de Controle de Qualidade
Detecção de zonas petrolíferas
etc.
61
Modelo dos Sistemas Especialistas
Pergunta ou Explicação
Módulo de Interface
Módulo Explicativo
Usuário
Resposta
ou “Por quê?”
Shell
Mecanismo de Inferência
Base de Conhecimento
Sistema Especialista
62
Como criar uma base de
conhecimento?
 Especialista
s
Engenheiro(s) de
Conhecimento
BC
ou
Exemplos
Sistema
de
AM
BC
63
Ainda tem mais?






Gerenciamento de Incerteza
IA Distribuída
Case Base Reasoning
Planning
Processamento em Linguagem Natural
etc...
64
Conclusões
 Puts, é muita coisa!
 Identificar o problema e decidir por onde
começar
 Poder computacional X Técnicas de IA X
Comportamento Humano
 Matrix é uma Viagem Total!
65
Dúvidas, Críticas, Sugestões?
66