Introdução à Inteligência Artificial - cee.uma.ptcee.uma.pt/edu/iia/acetatos/iia-Introdu%E7%E3o%20... · Introdução à Inteligência Artificial Universidade da Madeira 1 Introdução

Introdução à Inteligência Artificial Universidade da Madeira

1

Introdução à

Inteligência Artificial

Introdução

Agenda

PARTE 1IntroduçãoO que é a Inteligência Artificial?Paradigmas de IAFundamentos

PARTE 2HistoriaÁreas de IAAlgumas Aplicações


2

Um Problema

Resolver o quebra-cabeças

Um Problema

2 x 2 = 24 combinações possíveis


3

Um Problema3 x 3 = 362,880 combinações possíveis

Um Problema8 x 8 ≅ 1.2688 x 1089 combinações possíveis


4

Um Problema8 x 8 ≅ 1.2688 x 1089 combinações possíveis

63 sub casos

62 sub casos

Um Problema

8 x 8 ≅ 1.2688 x 1089 combinações possíveis.

A 1,000,000,000 de combinações por segundo demoraríamos 4 x 1069 milénios em testar todas as combinações.


5

Um Problema

Então porquê que nós humanos, podemos resolve-lo num curto prazo?

A resposta é simples: Porque utilizamos conhecimento do problema em forma inteligente.

Um Problema

Podemos programar um computador para utilizar conhecimento de um problema em forma inteligente?

A resposta esta na IA.


6

Agenda



O que é Inteligência Artificial

Não existe uma definição única.

Podemos classificar as definições de Inteligência Artificial de acordo com as seguintes quatro abordagens da IA:


7

O que é Inteligência ArtificialDimensões/abordagens da IA

Pensando

Agindo

Como humanos Racionalmente

Sistemas que pensam como um ser humano

Sistemas que actuam como um ser humano

Sistemas que pensam racionalmente

Sistemas que actuam racionalmente


“a arte de criar máquinas que realizem actividades que requerem inteligência quando realizadas por pessoas” (Kurzweil, 1990)

“como fazer os computadores fazerem coisas nas quais os seres humanos hoje em dia são mais eficientes.” (Rich and Knight, 1991)


8


Pensando

Agindo







“O excitante esforço para fazer computadores pensarem, máquinas com mentes, no sentido completo e literal” (Haugeland, 1985)

“A automação de actividades que associamos com o pensamento humano, tais como tomada de decisões, solução de problemas e aprendizagem” (Bellman, 1978)


9


Pensando

Agindo







“O estudo das faculdades mentais através do uso de modelos computacionais” (Charniak and McDermott, 1985).

“O estudo das computações que fazem possível perceber, raciocinar e agir”(Winston, 1992).


10


Pensando

Agindo







“Um campo de estudo que procura explicar e emular o comportamento inteligente em termos de processos computacionais” (Schalkoff, 1990).

“O ramo da ciência de computação que está preocupada com a automação do comportamento inteligente” (Luger andStubblefield, 1993).


11

(John McCarthy , Basic Questions)

What is artificial intelligence?It is the science and engineering of making intelligent machines, especially intelligent computer programs. It is related to the similar task of using computers to understand human intelligence, but AI does not have to confine itself to methods that are biologically observable.

Yes, but what is intelligence? Intelligence is the computational part of the ability to achievegoals in the world. Varying kinds and degrees of intelligence occur in people, many animals and some machines.

(John McCarthy , Basic Questions)

Isn't there a solid definition of intelligence that doesn't depend on relating it to human intelligence?

Not yet. The problem is that we cannot yet characterize in general what kinds of computational procedures we want to call intelligent. We understand some of the mechanisms of intelligence and not others.

http://www-formal.stanford.edu/jmc/whatisai/node1.html


12

Sistemas que actuam como um ser humano: O Teste de Turing

Proposto por Alan Turing em 1950.

O computador seria interrogado por um humano através de algum tipo de rede (na época, Turing sugeriu o teletipo).

O computador passa no teste se o interrogador não consegue dizer se existe um computador ou um ser humano do outro lado.



13


Ideia: obter uma forma satisfatória de definir a inteligência operacionalmente.

Definição de inteligência de Turing: “a habilidade de obter uma performance de nível humano em todas as tarefas cognitivas de forma a enganar um interrogador humano”.


Os humanos são observados “por dentro”.Como é que os humanos pensam?

IntrospecçãoCiências CognitivasNeurociênciasPsicologia experimental


14


Os humanos não são sempre racionais.Racional – definido em termos de lógica?

Dedutiva ou outras lógicas?Aristóteles foi o primeiro a tentar definir um processo de raciocínio irrefutável.

Ele desenvolveu os silogismosOs silogismos fornecem estruturas de argumentação que sempre fornecem conclusões correctas, dadas premissas correctas.

“Sócrates é um homem”“Todos os homens são mortais”Então Sócrates é mortal


Se eu parti de factos verdadeiros, como posso ter chegado a conclusões absurdas?

Tudo pode ser desvirtuado:Deus é amorO amor é cegoStevie Wonder é cego

ConclusãoDeus é cego Stevie Wonder é Deus!


15


Isto iniciou o campo da lógica.O campo foi muito expandido no século XIX por Boole, Pascal, Bayes, etc.Existem dois problemas com esta abordagem:

Dificuldade de definir conhecimento informal de forma a colocá-lo na notação lógica (especialmente quando o conhecimento não é 100% preciso).Existe uma grande diferença entre resolver um problema na teoria e na prática.


Comportamento racional: Cumprir os objectivos a partir das informações disponíveis.

Um agente é algo/alguém que percebe e age.

A abordagem racional dá ênfase às inferências correctas.

Para agir racionalmente, é necessário um processo de inferência racional.


16


A dificuldade vem quando não há uma provável acção correcta, mas uma decisão tem que ser tomada de alguma forma.

Existem formas de agir racionalmente que não envolvem inferência.

Tirar a mão de uma panela quente.Piscar quando alguém passa a mão na frente dos nossos olhos.

Agenda




17

Paradigmas de IASimbólico: metáfora linguística

Ex.: Sistemas periciais, agentes,...

Conexionista: metáfora cerebralEx.: Redes neurais.

Evolucionista: metáfora da natureza Ex.: Algoritmos genéticos, vida artificial.

Estatístico/Probabilístico/Posibilístico:Ex.: Redes Bayesianas, sistemas difusos.

Paradigma SimbólicoWest é 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. O Capitão West vendeu os mísseis a um traficante de armas espanhol, que vendeu a Cuba”

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 utilizando uma linguagem formal de representaçãoImplementar um mecanismo de inferência para utilizar esse conhecimento


18

Paradigma ConexionistaDefiniçã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 simplesraciocínio -> aprender directamente a função entrada-saída

Paradigma EvolucionistaEvoluçã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.


19

Paradigma Evolucionista

Definição: Método probabilista de busca para resolução de problemas (optimizaçã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.

Paradigma Estatístico/Probabilístico/Posibilístico

Probabilidades: Raciocínio com Incerteza

Possibilidades: Raciocínio com Imprecisão


20

Agenda



FundamentosMatemática

Sociologia

Psicologia

Filosofia

Linguística

Computação

IA

Neuro-fisiologiaGenética


21

FilosofiaSócrates, Platão, Aristóteles mente racional (400 AC)

Criaram as bases do pensamento e cultura ocidentais.

Aristóteles desenvolveu um sistema de silogismos para raciocínio organizado que, a princípio, permitiria mecanizar o processo de geração de conclusões a partir de premissas verdadeiras.

Usando este mecanismo temos um conjunto de regras para estabelecer o processo de pensamento, mas nada para definir os conceitos de livre arbítrio, criatividade, etc.

FilosofiaDescartes (1600) dualismo (natureza física x mente, livre arbítrio).

Descartes dizia que havia uma parte da mente que não poderia ser explicada pelas leis da física.

De acordo com Descartes, os animais não possuíam esta qualidade do dualismo.


22

FilosofiaMaterialismo (séc. XVII) o mundo (cérebro e mente) funciona de acordo com leis físicas.

Aponta a matéria como primeira e última substância de qualquer ser, coisa ou fenómeno do universo.

Para os materialistas, a única realidade é a matéria em movimento, que, por sua riqueza e complexidade, pode compor tanto a pedra quanto os extremamente variados reinos animal e vegetal, e produzir efeitos surpreendentes como a luz, o som, a emoção e a consciência.

FilosofiaEmpiricismo - fonte do conhecimento (observação dos factos e generalização de regras).

“nothing is in the understanding which was not first in thesense”

Alguns filósofos empiristas: Francis Bacon, Locke, Hume.


23

FilosofiaPositivismo lógico, o conhecimento pode ser expresso em teorias lógicas.

Todo significado de uma afirmação pode ser verificado ou falseado por meio de experimentação.

Principais Filósofos: Circulo de Viena, Bertrand Russell.

Matemática (Lógica e Computabilidade)

AristótelesBooleFregeTarskiHilbert

GodelTuring ChurchBayesCookVon Neumann


24

MatemáticaAristóteles – explica o raciocínio dedutivoBayes - 1760 – probabilidadeBoole – 1840 formalização de operações lógicasFrege – 1880 lógica de primeira ordem, termo e predicado, quantificaçãoTarski – 1940 relação dos objectos da lógica com objectos do mundo (modelo)Hilbert – 1900 formalização da matemática

MatemáticaGodel – 1930 incompletude da aritmética

mostrou que existe um procedimento efectivo para provar uma proposição verdadeira em lógica de primeira ordem, mas que esta lógica não poderia capturar o princípio de indução matemática necessária para caracterizar os números naturais

Turing e Church – 1940 computabilidadeComputabilidade x tratabilidade (complexidade) Cook (1971) Problemas NP-Completos

Von Neumann – Teoria de Jogos/ Teoria da Decisão.


25

Psicologia1850 – primeiro laboratório de psicologia experimental para o estudo da visão humana.

Pesquisa baseada na introspecção dos sujeitos (subjectivismo).

Behaviorismo (1900)Observação da ação (reação) dos sujeitos.

Psicologia1900 Psicologia cognitiva: metáfora computacional do cérebro.

Crenças, objectivos, raciocínio: elementos para uma teoria do comportamento humano.

Características de um agente baseado em conhecimento.O estímulo deve ser traduzido para uma representação interna;A representação é manipulada por processos cognitivos para derivar novas representações internas;

Estas representações são re-traduzidas em ação.


26

Engenharia computacional

HardwareAumento da velocidade de processamento e capacidade de memória.

SoftwareLinguagens, metodologias, interfaces.

LinguísticaChomsky – 1957 estruturas sintáticas

Linguagem: estrutura das sentenças + conhecimento do mundo

Filosofia da linguagem – representação do conhecimento

Campo híbrido: processamento de linguagem natural ou linguística computacional


27

Agenda



Historia – Tentativas

A historia original, publicada pela MaryShelley em 1818, descreve a tentativa do Dr. Victor Frankenstein, de criar vida.


28

Historia – Tentativas

1834

Historia – TentativasJoseph Faber's (1830-40's). Máquina falante Euphonia

“It is "... a speech synthesizer variously known as the Euphoniaand the Amazing Talking Machine. By pumping air with the bellows ... and manipulating a series of plates, chambers, and other apparatus (including an artificial tongue ... ), the operator could make it speak any European language. A German immigrant named Joseph Faber spent seventeen years perfecting the Euphonia, only to find when he was finished that few people cared."

David Lindsay called "Talking Head", Invention & Technology, Summer 1997, 57-63.

http://www.haskins.yale.edu/haskins/HEADS/SIMULACRA/euphonia.html


29

A gestação da inteligência Artificial (1943-1955)

Warren McCulloch e Walter Pitts (1943) – modelo de neurónios artificiais

Cada neurónio poderia estar “ligado” ou “desligado”.A troca para ligado, ocorria como resposta aos estímulos para um número suficiente de neurónios vizinhos.Conhecimento básico sobre fisiologia e as funções dos neurónios no cérebro, lógica proposicional, teoria da computação.

Marvin Minsky (tese) e Dean Edmonds construíram o primeiro computador de redes neurais em 1951, possuía 40 neurónios.

O nascimento da IA Dartmouth Conference (1956)

Organizada pelo John McCarthy para estabelecer uma nova área para estudar computação e inteligência.

John McCarthy baptiza a área introduzindo o termino “artificial intelligence” durante a conferencia.

Os seguintes 20 anos testemunharam o crescimento da área, sendo este crescimento conduzido pelos pioneiros que participaram na conferência de Dartmouth.


30

Entusiasmo inicial (1952-1969)

Alan Newell e Herbert Simon desenvolveram o “General ProblemSolver” (GPS)

Projectado para imitar protocolos humanos de resolução de problemasGPS foi o primeiro programa a incorporar a abordagem “Pensar como humanos”A combinação de IA e Ciência Cognitiva continua até hoje

Arthur Samuel (1952) escreveu uma série de programas para jogar damas e provou o contrário do que era senso comum na época:

“a ideia de que computadores podiam fazer somente o que lhes era dito”Seus programas aprendiam rapidamente a jogar melhor que seu criador

Herbert Gelernter (1959) – Geometry Theorem ProverDemonstrava teoremas bastante complicados

Entusiasmo inicial (1952-1969)

McCarthy (1958) desenvolveu o LISP, que se tornou a linguagem dominante de IA.Robinson (1963) descobriu o método da resolução:

Algoritmo completo de provas de teoremas para a Lógica de 1a Ordem.PROLOG estava a caminho.

Minsky supervisionou uma série de estudantes que escolheram problemas limitados, que pareciam requerer inteligência para serem resolvidos:

Micromundos .O mais famoso micromundo foi o mundo dos blocos.


31

Uma Dose de Realidade (1966-1974)

A barreira que muitos projectos de IA encontraram foi que:

Métodos que eram suficientes para demonstrações de um ou dois exemplos simples, quase sempre fracassavam quando testados com um elenco maior de problemas ou com problemas mais difíceis.

O primeiro tipo de dificuldadeOs primeiros programas continham pouco ou nenhum conhecimento do assunto que tratavam.Tinham sucesso através de manipulações sintácticas muito simples - ELIZA (65).

Uma Dose de Realidade (1966-1974)

O segundo tipo de dificuldadeA não resolução de muitos problemas que a IA estava tentando solucionar.Os primeiros programas funcionavam somente porque os micromundos continham poucos objectos.Antes que a teoria de problemas NP-completos fosse desenvolvida, acreditava-se que o problema de se "escalar" para problemas maiores era simplesmente um problema de se ter hardware mais rápido.

Uma terceira dificuldade veio das limitações sobre as estruturas básicas usadas para gerar comportamento inteligente.


32

SBC: A Chave para o Poder? (1969-1979)

O método de resolução de problemas usado na primeira década da IA foi o mecanismo de busca de propósito geral.

Eles são chamados métodos fracos porque usam pouca informação sobre o domínio.Para domínios complexos o desempenho é pobre.

Surgem os sistemas periciaisConhecimento, heurísticas e regras sobre um determinada especialidade. Separação clara entre conhecimento (regras) e componente de raciocínio.DENDRAL (1969) – conhecimento de química reduz a quantidade de computação.

Foi o primeiro sistema a trabalhar com conhecimento intensivo.Sua perícia era derivada de um grande número de regras específicas.Inferia a estrutura molecular de informações fornecidas por um espectrómetro de massa.

Feignbaum e outros – MYCIN – diagnostico de doenças infecciosas (450 regras)

SBC: A Chave para o Poder? (1969-1979)

A importância do conhecimento do domínio foi também aparente na área de processamento de linguagem natural.

O crescimento das aplicações no mundo real aumentou a demanda por esquemas de representação de conhecimento alternativos:

Lógica e Frames


33

Problemas da Linguagem Natural

Olive oil

Problemas da Linguagem Natural

Baby oil


34

Renascimento(1969 – 1979)

1971: T. Winograd’s Ph.D. thesis (MIT) cria um sistema capaz de compreender inglês num domínio reduzido (mundo de blocos).

1972: nasce PROLOG e torna-se uma alternativa a LISP e o paradigma funcional.

Renascimento(1969 – 1979)

1978: O Version Space algorithm foi desenvolvido pelo Tom Mitchell em Stanford.

Primeiro algoritmo de aprendizagem.E considerado o “Father of Machine Learning”.

1979: Lógicas não-monótonas.Formalizadas pelo John McCarthy e seus colegas.


35

A IA Torna-se Comercial (1980-hoje)

O primeiro sistema especialista de sucesso comercial, R1, começou a operar na DEC.

Ajudava a configurar ordens para novos computadores.

Em 1981, os japoneses anunciaram a "Quinta Geração“.

Um projecto de 10 anos, para construção de computadores inteligentes que utilizavam Prolog.

O retorno das redes neurais (1986- hoje)

Desenvolvimento continuou em outras áreas.

Uso/desenvolvimento de algoritmos “back-propagation”.

IA Tradicional x Redes Neurais.


36

Eventos recentes (1987-1995-2000-hoje)

Avanços e utilização de tecnologia para reconhecimento de imagem e fala/som.

Belief networks, "probabilidade" que permite formalismo para tratar incertezas.

Desenvolvimento de mecanismos lógicos para tratar incerteza.

Ex.: lógica fuzzy, lógica modal, etc.

Tendências ActuaisPassagem de sistemas experimentais para aplicações reais de larga escala

Representação de conhecimento (CYC).Reconhecimento da fala. Robótica.Visão.Internet (softbots).


37

Agenda



Redes Neurais

LógicaFuzzy

ComputaçãoEvolucionária

AgentesInteligentes

LinguagemNatural

RobóticaRaciocínio Baseadoem Casos

RaciocínioBaseado

em Regras

Outros


38

Agenda



FIFA SoccerThe Sims

Produção de jogos e histórias interactivas

Como modelar o ambiente físico e o comportamento/personalidade dos personagens?Como permitir uma boa interação com o utilizador?


39

Deep Blue

Deep Blue vs Kasparov

Em 1997 Deep Blue venceu Kasparov


40

Deep Blue vs Kasparov

PoucoMuito Cálculo

MuitoPoucoConhecimento em xadrez

Até 3 p/segundo

Até 200 milhões p/segundo

Capacidade avaliativa de jogadas

KasparovDeep BlueCaracterísticas

Controle de tráfego aéreo(OASIS - sofisticado sistema de controle de tráfego aéreo baseado no paradigma multiagente, utilizado no aeroporto de Sydney, Austrália, no qual os agentes assumem o lugar dos aviões em operação);


41

Massive softwareMultiple agent simulation system in virtual environment

Cada combatente representa um agente que escolhe as suas próprias acções em função:

Das suas percepções do ambienteDo seu conhecimentoDa sua especialização

Não há lugar á decisão centralizada,cada agente é autónomo.Cada um deles toma cerca de 24 decisões por segundo.Dezenas de milhares de combatentes

Massive softwareMultiple agent simulation system in virtual environment

Os agentes têm:Uma representação do seu ambienteSentidos: visão, audição, tacto, até mesmo olfactoUm carácter (agressividade, medo, força)Características pessoais (raça, tamanho, morfologia)

Cada agente pode:Andar, correr, saltar, lutarEncontrar, identificar e iniciar o combate com o inimigoGanhar e viver ou então perder e morrer

Com isto tudo consegue-se:O comportamento de um combatente não é previsível:

Durante um combate, um humano vai responder a um ataque pegando na sua espada

Depois de quando tempo ? Em que preciso momento ?Ele vai avançar ? Recuar ? Ou ainda ir para o lado ?

Quando os soldados da terra média atacam, emitem gritos e um ruído que tem uma incidência directa sobre a moral dos seus adversários.


42

HAZBOT: ambientes com atmosfera inflamável

Controle de robôs

Como obter navegação segura e eficiente, estabilidade, manipulação fina e versátil? E no caso de ambientes dinâmicos e imprevisíveis?

Robots - Dante

1994 Dante II (CMU) explora o vulcão Mt. Spurr (Aleutian Range, Alaska). Ambiente inóspito para humanos


43

Busca de informação na Web

Como localizar a informação relevante?

Recomendação de produtos

Como fazer recomendações personalizadas de produtos? Como modelar o perfil dos compradores?


44

Previsão

Como prever o valor do dólar (ou o clima) amanhã?Que dados são relevantes? Há comportamentos recorrentes?

Detecção de Intrusão e Filtragem de Spam

Como saber se uma mensagem é lixo ou de fato interessa?Como saber se um dado comportamento do utilizador é suspeito e com lidar com isso?


45

Como travar o carro sem as rodas deslizarem em função da velocidade, atrito, etc.?Como focar a câmera em função de luminosidade, distância, etc.?Como ajustar a temperatura em relação á quantidade de roupa, fluxo de água, etc.?

Sistemas de Controle

InterfaceComo fornecer ao utilizador a ajuda de que ele precisa exactamente?Como interagir (e quem sabe navegar na web) com um telemóvel sem ter de digitar os números (hands-free)?


46

O que estes problemas têm em comum?

Grande complexidade (número, variedade e natureza das tarefas).

Não há “solução algorítmica”, mas existe conhecimento.

Modelagem do comportamento de um ser inteligente (conhecimento, aprendizagem, iniciativa, etc.).

Leituras SugeridasLIVROS

Russel, Norvig, Artificial Intelligence: A ModernApproach, Cap. 1.Costa, Simões, Inteligência Artificial. Fundamentos e Aplicações. Cap 1.1 a 1.4.

ARTIGOSJohn McCarthy. What is artificial intelligence?.

http://www-formal.stanford.edu/jmc/whatisai.html

Alan Turing "Computing Machinery and Intelligence"http://www.abelard.org/turpap/turpap.htm


47

FIM

Documents

Introdução à Inteligência Artificial - cee.uma.ptcee.uma.pt/edu/iia/acetatos/iia-Introdu%E7%E3o%20... · Introdução à Inteligência Artificial Universidade da Madeira 1 Introdução