1
Inteligência Artificial: Uma
Panorâmica
Claudio Cesar de Sá
[email protected]
UDESC/CCT/DCC
COCA – Grupo de Computação Cognitiva Aplicada
2
Inteligência Artificial
Roteiro
 Definições e evolução histórica
 Aplicações
 Abordagens e problemas principais
 Comparação com a computação convencional
 As três (03) IAs
 Nossos Projetos
 Bibliografia (Links)
Ciências do Artificial
 Ciências naturais
• objetivo: analisar e descrever a natureza (observação)
– “ mostrar que a complexidade é apenas uma máscara da simplicidade”
• ex.: Química, Física, Botânica, etc.
 Ciências do artificial
• objetivo: prescrever e sintetizar “artefatos” (transformação)
– criar artefatos que satisfaçam as necessidades humanas, de acordo
com as leis naturais
– ex. cadeira de madeira, cura da AIDS, um programa de computador, etc
• metodologia: essencialmente empírica
– compreensão por construção/simulação e avaliação do resultado
3
O que é inteligência?
Teste de Turing
Podemos ficar pensando se um dia um computador poderá fazer o
mesmo. Como poderíamos saber se um computador estará
pensando num belo dia?
Does the Turing Test still have relevance?
4
Modern Turing Test
 “On the web, no one knows you’re and….”
 Problem: ‘bots’
• Automated agents swamp services
 Challenge: Prove you’re human
• Test: Something human can do, ‘bot can’t
 Imagens:
• Distorted images: trivial for human; hard for ‘bot
 Key: Perception, not reasoning
5
Inteligência Artificial (IA)
 Objetivo: desenvolver sistemas para realizar tarefas que, no
momento
• são melhor realizadas por seres humanos que por máquinas, ou
• não possuem solução algorítmica viável pela computação
convencional
problemas que não possuem
uma solução algorítmica
IA
problemas solúveis
por seres humanos
Se o ser humano pode, por que não a máquina?
(tese de Church-Turing)
6
Definindo a IA:
Fato 1: “Joãozinho trabalha como cortador de cana durante o período da manhã,
e tem uma produtividade de 20Kg em 04 (quatro horas)´´
Fato 2: “Mariazinha trabalha como cortadora de cana durante o período da tarde,
e tem uma produtividade de 15Kg em 04 (quatro horas) ´´
Fato 3: “Joãozinho e Mariazinha começam a namorar´´
Fato 4: “Mariazinha é transferida para o turno da manhã´´
Pergunta: “Qual a produtividade em Kg de cana por período destes dois
personagens, após esta transferência de turno?´´
1.
2.
3.
4.
20+15 = 35
20+15 > 35
20+15 < 35
20+15 ~ 35 (típica da IA)
7
Onde está a IA em nossos dias ...
1. Programa que reconhece carácteres a partir do texto
varrido por um scanner
2. O programa que faz a digitação automática do texto que
voce fala
3. O aspirador de pó autônomo (literalmente um robô)
4. O aparelho de ar-condicionado que busca manter a
temperatura ambiente constante, e buscando reduzir o
custo de energia
5. O buscador na WEB que faz uma análise sintática e
semântica do texto em repositórios
6. O câmbio, a suspensão, o ar-condicionado de alguns
carros
7. O traçador de rotas (ruas) em uma cidade entre dois
pontos quaisquer
8
O que acontece então ....
O que
faremos
com isto?
teorias
9
Domínio Público
tecnologias
P&D
Uso em larga
escala
Produtos e mais
produtos
Esquecimento das origens !
“Once it works, it’s not AI anymore. It’s engineering.” (J. Moore,
Wired)
PROBLEMAS ABORDADOS PELA I.A.
Características dos problemas adequados à I.A.:
 São muito variados e têm pouco em comum entre si;
 São difíceis: complexidade (3 tipos) algoritmica (quanto ao
pgm em software), computacional (quanto ao esforço em
máquina (hardware)) e da solução (“tentativa-e-erro”: nãodeterminismo);
 Exigem armazenamento de volumes imensos de
conhecimento;
 Conhecimento:
 Difícil de caracterizar.
 Impreciso.
 Muda constantemente.
10
Mais Aplicações
 Matemática: demonstração de teoremas, resolução simbólica de
equações, geometria, etc.
 Pesquisa operacional: otimização e busca heurística em geral
 Jogos: xadrez, damas, go, etc.
 Processamento de linguagem natural: tradução automática,
verificadores ortográficos e sintáticos, interfaces para BDs, etc.
 Sistemas tutores: modelagem do aluno, escolha de estratégias
pedagógicas, etc.
 Percepção: visão, tato, audição, olfato, paladar...
 Robótica (software e hardware): manipulação, navegação,
monitoramento, etc.
11
Aplicações
 Sistemas especialistas: Atividades que exigem conhecimento
especializado e não formalizado
• Tarefas: diagnóstico, previsão, monitoramento, análise,
planejamento, projeto, etc.
• Áreas: medicina, finanças, engenharia, química, indústria,
arquitetura, arte, computação,...
 Computação:
•
•
•
•
•
•
engenharia de software (sobretudo na Web)
bancos de dados dedutivos
interfaces adaptativas
mineração de dados (data mining)
sistemas distribuídos
programação automática, etc.
12
Trajetórias de Robôs
X  Xc
2
 Y  Yc  Rrobot2
2
13
Coloração do Mapa
 color a map with three colors so that adjacent countries have
different colors
A
C
G
B
D
E
F
14
Continuação
15
 most-constrained-variable heuristic
A
C
G
B
D
E
F
8-Rainhas
1
3
3
3
5
1
2
2
4
2
2
1
2
1
16
Popular Tasks of Today
 Data mining
 Intelligent agents and internet applications
• Softbots (Ex: http://ai.bpa.arizona.edu/resume/dmitri/query.html)
• believable agents
• intelligent information access
 Scheduling applications
 Configuration applications
 Airport gate scheduling:
• Satisfy constraints on gate size, passenger transfers, traffic flow
• Uses AI techniques of constraint propagation, rule-based reasoning,
and spatial planning
18
Interação com outras ciências
Matemática
Filosofia
Lingüística
Sociologia
IA
Psicologia
Computação
Neuro-fisiologia
Genética
19
20
Máquinas inteligentes?
21
evolução em direção ao paradigma dos agentes
Pensando
“A automação de atividades que nós
associamos com o pensamento humano
(e.g., tomada de decisão, solução de
problemas, aprendizagem, etc.)” (50-60)
“O estudo das faculdades mentais
através do uso de
modelos computacionais” (60-70)
Idealmente
(racionalmente)
Humanamente
“A arte de criar máquinas que realizam
funções que requerem inteligência
quando realizadas por pessoas” (50-70)
“O ramo da Ciência da Computação
que estuda a automação de
comportamento inteligente”
Agindo
Inteligência Natural e Inteligência Artificial
1.
Comparação entre inteligência natural e artificial
Atributo e grau de dificuldade
Inteligência Natural
Inteligência Artificial
Obter um grande volume de informações
externas
Alto
Baixo
Usar sensores (olhos, ouvidos, tato, olfato)
Alto
Baixo
Ser criativo e imaginativo
Alto
Baixo
Aprender com a experiência
Alto
Baixo
Ser esquecido
Alto
Baixo
Realizar cálculos complexos
Baixo
Alto
Ser flexível
Alto
Baixo
Usar diversas fontes de informações
Alto
Baixo
Transferir informações
Baixo
Alto
Custo da obtenção de inteligência
Alto
Baixo
22
MODELO DE HIERARQUIA DE INFORMAÇÕES
BOM-SENSO
Desafio da pesquisa
CONHECIMENTO
Inteligência Artificial
INFORMAÇÕES
Sistemas tradicionais
DADOS
EXEMPLO
HIERARQUIA DE INFORMAÇÕES
BOM-SENSO
Deve ser pela mudança de clima
CONHECIMENTO
Recomendação: Aspirina e cama
INFORMAÇÕES
Está com febre
DADOS
Temperatura = 39oC
Em resumo:
A IA não é um fenômeno isolado, mas uma família de
atividades por vezes relacionadas, em que cada uma busca
capturar algum aspecto da inteligência dos seres humanos
e de seu modo de ser. Os cientistas da computação,
engenheiros eletrônicos, psicólogos, lingüistas, fisiologistas
e biólogos estão envolvidos nessa busca, que os leva a
pesquisar a linguagem natural, a robótica, os sistemas
perceptivos, os sistemas especialistas, as redes neurais e o
software inteligente.
25
DIVISÕES DA I.A.
I.A. Simbólica
Conhecimento explícito
• Ciência Cognitiva
• Ex: Estados, Lógica, Regras, Casos.
•
I.A. Conexionista
Conhecimento implícito
• Neuro-Ciências
• Ex: Redes Neuronais.
•
I.A. Evolutiva
Representação de soluções candidatas
• Ciência Biológica (em particular, Teoria da Evolução)
• Ex: Algoritmos Genéticos.
•
Paradigmas de Raciocínio (e da IA)
 Simbólico: metáfora lingüística
• ex. sistemas de produção, agentes, lógica, ...
 Conexionista: metáfora cerebral
• ex. redes neurais
 Evolucionista: metáfora da natureza
• ex. algoritmos genéticos, vida artificial,
27
Evolução da IA
28
 Surgiu na década de 50
 Agindo humanamente (anos 50-70): Teste de Turing
• Problema: “mito do cérebro eletrônico“
 Pensando humanamente (anos 50-60): simulação cognitiva (Simon
& Newell)
• Boas inspirações (GPS, Sistemas Especialistas,...) mas
fraca justificativa para os resultados obtidos
 Pensando idealmente (anos 60-70): A escola logicista
(McCarthy)
• Desenvolvimento de formalismos de representação de
conhecimento
• Problemas: escasez de recursos computacionais, limitação
dos tipos de inferências
 Agindo idealmente (anos 80-90): Agente inteligente (Newell,
Minsky, Russel & Norvig)
• Abrangente (atividades), unificador (domínios da IA),
excelente framework para projeto e análise de programas.
Issues with Classical AI
 Oversold! (Excesso de Expectativa)
 Narrow: Navigate an office but not a sidewalk
 Brittle: Sensitive to input errors
• Large complex rule bases: hard to modify,
maintain
• Manually coded
 Cumbersome: Slow think, plan, act cycle
29
Modern AI
 Situated intelligence (Inteligência “bem-posicionada”)
• Sensors, perceive/interact with environment
• “Intelligence at the interface” – speech, vision
 Machine learning
• Automatically identify regularities in data
 Incomplete knowledge; imperfect input
 Comportamento Emergente
 Probabilistic, chaos, etc.
30
PRINCIPAIS TÉCNICAS
 Estados e Busca Heurística
 Regras
 Lógica
 Casos
 Frames e Scripts
 Redes Semânticas
 ..........
 Computação Evolutiva (evolutiva)
 Redes Neurais (conexionista)
Paradigma Simbólico
ou IA Simbólica
 West é criminoso ou não?
• “A lei americana diz que é proibido vender armas a uma nação
hostil. Cuba possui alguns mísseis, e todos eles foram vendidos
pelo Capitão West, que é americano” (coisas de seres humanos ...)
 Como resolver automaticamente este problema de
classificação?
 Segundo a IA (simbólica), é preciso:
• Identificar o conhecimento do domínio (modelo do problema)
• Representá-lo utlizando uma linguagem formal de representação
• Implementar um mecanismo de inferência para utilizar esse
conhecimento
32
Conhecimento: organizando...
 Programa em IA = Agente racional
• entidade de software que age em um ambiente segundo um
princípio de racionalidade
 Precisa ter conhecimento sobre:
•
•
•
•
•
•
quais são suas propriedades relevantes do mundo
como o mundo evolui
como identificar os estados desejáveis do mundo
quais as conseqüências de suas ações no mundo
como medir o sucesso de suas ações
como avaliar seus próprios conhecimentos
33
Conhecimento: Representação e Uso
 Raciocínio:
• processo de construção de novas sentenças a partir de outras
sentenças.
 Deve-se assegurar que o raciocínio é plausível (sound)
fatos
segue-se
fatos
Mundo
Representação
sentenças
implica
sentenças
34
LÓGICA
•Provar um teorema a partir de um conjunto de premissas.
• Exemplo:
Provar o teorema herbívoro(zebra), a partir das premissas:
animal(zebra).
vegetal(grama).
come(zebra,grama).
"x"y[animal(x) E come(x,y) E vegetal(y)=> herbívoro(x)].
Símbolos X Representações X Problemas
• Todos estudantes são mortais.
• Paulo é um estudante.
"x estudantes(x)  mortais(x).
estudante(paulo).
mortal( X ) :- estudante( X ).
estudante( paulo ).
Um conhecimento, coisas de
Humanos. Fácil !
Uma representação
intermediária,
Coisas de engenheiros.
Em código Prolog. Pronto para
executar.
36
Uma ferramenta
claudio@Goedel:~/pesquisa/livro/prolog/pgms$ prolog
% /home/professores/claudio/.plrc compiled 0.00 sec, 2,152 bytes
Welcome to SWI-Prolog (Multi-threaded, Version 5.2.13)
Copyright (c) 1990-2003 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.
For help, use ?- help(Topic). or ?- apropos(Word).
?- consult('mortal.pl').
% mortal.pl compiled 0.00 sec, 696 bytes
Yes
??- estudante(X).
X = paulo ;
No
?- mortal(Y).
Y = paulo ;
No
?-
/* mais soluções ? */
/* mais soluções ? */
37
ESTADOS e BUSCA HEURÍSTICA
Problema do Carteiro Viajante
CAMP
130
180
110
ITU
SJC
90
80
SP
150
230
100
160
UBA
SANT
ITU
130
X
180
160
Solução:
ITU - SP - SJC - UBA
Custo: 320 Km
80
SP
CAMP
SANT
100
110
90
SJC
SANT
X
230
SANT
X
CAMP
150
100
230
X
UBA
Custo: 320
Qual é o melhor
percurso
ITU > UBA ?
180
SJC
UBA
X
Custo: 340
SP
X
REGRAS
SISTEMAS
BASEADOS
EM
REGRAS
Conhecimento representado em regras do tipo:
SE
<Condição 1>
<Condição 2>
ENTÃO
<Conclusão 1>
<Conclusão 2>
EX: Análise de restritivos (em inst. bancária)
SE
tipo - restritivo = Ação de Busca
E pessoa analisada = Jurídica
E quantidade de ocorrências < 2
ENTÃO
Análise Restritivo = Não Relevante
CASOS
 Simulação de Raciocínio:
SISTEMAS
BASEADOS
EM CASOS
Problemas atuais são
resolvidos através da analogia
com casos do passado, onde
problemas semelhantes foram
solucionados.
Ex. Diagnose Médica.
SISTEMAS BASEADOS EM CASOS
Principais Elementos:
BASE DE CASOS
ACESSO POR ANALOGIA
NOVO
CASO
ACESSO POR
ANALOGIA
CASOS
ANÁLOGOS
BASE DE
CASOS
Paradigma Conexionista
Redes Neurais
 Definição “Romântica”:
Técnica inspirada no funcionamento do cérebro, onde neurônios
artificiais, conectados em rede, são capazes de aprender e de
generalizar.
 Definição “Matemática”:
Técnica de aproximação de funções por regressão não-linear.
 É uma outra abordagem:
• linguagem -> redes de elementos simples
• raciocínio -> aprender diretamente a função entrada-saída
43
Redes Neurais
Utiliza um modelo do processamento paralelo
do cérebro humano.
Cada neurônio tem ligações múltiplas com
vários outros.
Cada ligação tem um peso.
É treinada para “aprender” vários exemplos
(configuração de pesos).
REDES NEURAIS
E
N
T
R
A
D
A
S
A
Í
D
A
Redes Neurais
s1
w1i
sj
wji
sn
e(i)  w ji  sj
e(i)



s(i)
s(i)  f (e(i))
wni
camada
de entrada
camada
escondida
camada
de saída
Paradigma Evolutivo
 EVOLUÇÃO
• Diversidade é gerada por cruzamento e mutações
• Os seres mais adaptados ao seus ambientes sobrevivem (seleção
natural)
• As características genéticas de tais seres são herdadas pelas
próximas gerações
47
Paradigma Evolutivo
 Definição:
• Método probabilista de busca para resolução de problemas
(otimização) “inspirado” na teoria da evolução
 Idéia:
• indivíduo = solução
• faz evoluir um conjunto de indivíduos mais adaptados por
cruzamento através de sucessivas gerações
• fitness function f(i): R ->[0,1]
48
COMPUTAÇÃO EVOLUTIVA
PID
Ajuste do PID:
Kp,Ti e Td
Processo
0,00 > K,Ti,Td < 200,00
3
Espaço: (20.000) = 8 x 10
Kp
PID (Indivíduo):
Ti
Td
População Inicial (100 indiv.):
Crossover:
Kp
Ti
Td
Kp
Ti
Kp
Ti
Td
Kp
Ti
Mutação:
Kp
Ti
Td
Kp
Ti
Td
Kp
Ti
Td
Kp
Ti
Td
12
Kp
Ti
Td
Kp
Ti
Td
...
Td
Kp
Ti
Td
Td
Kp
Ti
Td
Seleção Adaptativa:
os melhores individuos
sobrevivem
COMPUTAÇÃO EVOLUTIVA
Start
Population
Scoring of each individual
by means of a Fitness function
Selection of the
best ones
Selected
sub-population
Is there a
satisfactory
candidate
solution?
No
Aplication of Genetic Operators
(Reproduction, Crossover, Mutation...)
Y es
End
Após os 03 paradigmas ....
Algumas direções as pesquisas indicam onde está o
ganho:
1. IA Distribuída: sociedade de agentes e solução
distribuída do problema
2. Arquiteturas Híbridas: combinações de técnicas
3. Robótica
4. “Nanotecnologia”: computadores vestíveis, sistemas
embarcados,
5. Arquiteturas ....
6. Inspirações Biológicas
51
Sistemas Simbólicos: arquitetura
52
Sistemas sub-simbólicos: arquiteturas
53
Tensões Centrais da IA
54
conhecimento em intenção (regras)
Sistemas de PLN
Sistemas
Nebulosos
(fuzzy)
Robôs
numérico
Algoritmos
genéticos
Sistemas baseados em
Redes Neurais
Sistemas
Especialistas
Redes
Bayesianas
Sistemas
baseado
em casos
simbólico
Sistemas de
Aprendizagem
simbólica indutiva
conhecimento em extensão (exemplos)
Problemas genéricos da IA
 Representação de conhecimento (RC)
 Aquisição de conhecimento e Aprendizagem (ACA)
 Busca heurística e resolução de problemas (BH)
 Planejamento (PL)
 Tratamento de incerteza (TI)
 Reconhecimento de padrões (RP)
 Ambientes/linguagens de desenvolvimento
 Avaliação de sistemas
55
Computação convencional x IA:
classes de problemas
 Solução matemática (NÃO), conhecimento (SIM)
=> IA simbólica
 Modelo do problema (NÃO), exemplos de solução (SIM)
• => IA (aprendizagem)
 Autonomia, adaptabilidade, interoperabilidade, ...
• => IA simbólica
 Repositório de conhecimento especialista (expertise)
• => IA simbólica
56
Computação Convencional x IA:
metas
 Tarefas para as quais os seres humanos são
• ineficientes x eficientes
 Completeza da entrada
 Fornecimento de explicações inteligíveis
 Adaptabilidade para novas instâncias do problema
 Privilégio das soluções heurísticas
57
Computação convencional x IA:
métodos
 Algoritmo passo a passo x
Mecanismo geral de inferência + conhecimento
... ou então aprendizado
 Dados e controle embutidos em código procedimental x
Separação entre conhecimento declarativo e controle
 SPIV (specify prove implement verify) x RUDE (run understand
debug edit)
 Linguagens de programação: imperativas x “alto-nível” (funcional,
lógica, orientada a objeto, baseada em restrições)
 IA: Usa metáforas de sistemas naturais (neurônio, evolução,
memória, sociedade, língua,...)
58
59
State of the Art
 Deep Blue beats Kasparov
 NASA’s Remote Agent program controls a
spacecraft autonomously
 High accuracy continuous speech recognition with
fairly large vocabularies (2000 words, 2% error)
 Usable natural language interface to air travel
system
 No Hands Across America: Automated vehicle
drives cross-country on freeways
State of the Art
 Medical diagnosis in specialized fields is sometimes assisted
by AI programs
 AI logistics programs were critically important in the Gulf
War.
 PROVERB can solve crossword puzzles faster than most
humans.
60
Visões da IA (para pensar)
 Weak vs. strong
 Scruffy vs. neat
 Engineering vs. cognitive
61
IA no Brasil
 Fracamente representada nas graduações em computação
• no máximo, 1 disciplina obrigatória
• Sem pré-requisitos. Estudantes chegam sem a fundamentação
necessária.
• No melhor dos casos, depois do sexto período
• Ementa restrita e desatualizada
 Economicamente ainda incipiente
• por falta de demanda ou de profissionais bem formados?
 Visão “destorcida e incompleta” do que é IA
 No exterior é o contrário
• MIT, Stanford, Carnegie Mellon, Berkeley, Imperial College,
Cambridge
• Mercado fatura alto
62
Grupo de Computação Cognitiva Aplicada - COCA
 http://www.joinville.udesc.br/dcc/coca/
 Projetos já finalizados:
1. Sistema de controle fuzzy para aquários. Escrito em Assembly
de um microcontrolador. Méritos: abordagem multidisciplinar, com
IA, aquarismo e controle fuzzy. Desenvolvimento de uma placa
coletora de dados. Finalmente um patente no INPI foi requerida;
2. Sistema Neuro-Fuzzy Modificado por Kohonen. Um sistema
híbrido destinado a identificação de sistemas. Mérito: muita
implementação computacional, e vários artigos publicados.
63
Grupo de Computação Cognitiva Aplicada - COCA
 Projetos em andamento:
1. Sistema de Controle Fuzzy de Chocadeiras em granjas industriais;
2. Um livro sobre IA Simbólica com enfoque há uma abordagem
metodológica de problemas;
3. Um livro sobre a Linguagem Haskell. Uma Linguagem de
Programação para Engenheiros, curiosos em programação, etc.
Ver protótipo em:
http://geocities.yahoo.com.br/lpg3udesc/
4. Solução de um problema da CSN (ou Belgo Mineira) com uma
abordagem de Alg. Genéticos;
64
Links interessantes (em português)
 http://www.ec.ucdb.br/~marco/courses02b/ai1/calendar.html
 http://www.das.ufsc.br/gia/iaft/ (Inteligência ArtificialFerramentas e Teorias, Guilherme Bittencourt )
65
Outros
 http://www-2.cs.cmu.edu/~tom/mlbook.html (aprendizagem
de máquinas, quase todo livro disponível, escrito em LaTeX)
 http://www.gy.com/Science/Math/Recreations/ (link sobre
jogos ... Uma motivação sobre o que pensar do que é
inteligência)
 http://www.particle.kth.se/~lindsey/nnwLinks.html (completo
sobre Redes Neurais)
 http://www.cs.berkeley.edu/~russell/ai.html (um dos
melhores, é o ponto de partida para tudo que há de
importante na WEB)
66