1

Inteligncia Artificial

Prof. Dr. Srgio SilvaProf. Josiane M. Pinheiro

Baseado no Cap. 2 do livro de Stuart Russel e Peter Norving - Inteligncia Artificial, 2a ed.

2

O que Inteligncia Artificial? Durante milhares de ano procuramos entender como

pensamos Como um mero punhado de matria pode perceber,

compreender, prever e manipular um mundo muito maior?

A IA tenta alm de entender, tambm construir entidades inteligentes

Subcampos rea de uso geral: aprendizado e percepo

Tarefas especficas: jogos de xadrez, demonstrao de teoremas matemticos, criao de poesia e diagnstico de doenas

Um campo universal: sistematiza e automatiza tarefas intelectuais

3

Quatro pontos de vista sobre AIPensando

Agindo

Como humanos Racionalmente

A automao de atividades que ns associamos com o pensamento humano, atividades como a tomada de deciso, a resoluo de problemas, o aprendizado... [Bellman, 1978]

A arte de criar mquinas que realizam funes que requerem inteligncia quando realizadas por pessoas [Kurzwell, 1990]

O estudo das computaes que tornam possvel perceber, raciocinar e agir [Winston, 1992]

O estudo e o projeto de agentes inteligentes [Poole et al.,1998]

4

Agindo como humanos Alan Turing (1950) prope o Teste de Turing

Computing Machinery and Intelligence [http://www.abelard.org/turpap/turpap.htm]

As mquinas podem se comportar inteligentemente?

Teste operacional para comportamento inteligente: O JOGO DA IMITAO

Previu que, em 2000, as mquinas teriam 30% de chance de enganar uma pessoa leiga por 5 minutos

5

O Interrogador

Agindo como humanos

6

Agindo como humanos Para passar no Teste de Turing necessrio:

Processamento de Linguagem Natural Representao de Conhecimento Raciocnio Automtico Aprendizagem de mquina

Teste de Turing Total

Viso Computacional Robtica

7

Agindo como humanos Eliza e Jlia so softwares que tentaram passar no teste

Atualmente pesquisadores em IA tem dedicado pouco esforo para passar no teste de Turing

Acreditam que mais importante estudar os princpios bsicos da inteligncia do que reproduzir um ser inteligente

O desafio do vo artificial Teve sucesso quando os pesquisadores pararam de imitar os

pssaros e estudaram a aerodinmica

8

Pensando como humanos Programas pensam como humanos => como os humanos

pensam?

Como a mente humana trabalha por dentro? Atravs de introspeco Atravs de experimentos psicolgicos

Uma teoria precisa do funcionamento da mente => possibilidade de expressar a teoria no computador

9

Pensando como humanos Newell e Simon (1961) General Problem Solver (GPS)

Estavam preocupados em comparar as formas de seu raciocnio s formas do raciocnio humano para resolver os mesmos problemas

Cincia Cognitiva modelos computacionais da IA + tcnicas experimentais da psicologia Tentar construir teorias precisas e testveis a respeito dos processos de

funcionamento da mente humana

IA e cincia cognitiva ajudam uma a outra, especialmente em reas de viso computacional, linguagem natural e aprendizagem

10

Pensando racionalmente Aristteles => tentou codificar o pensamento correto

(processos de raciocnio irrefutveis, incontestveis) Silogismos = concluses corretas para premissas corretas

Scrates um homem e Todo homem mortal, ento Scrates mortal

As leis do pensamento deveriam governar as operaes da mente => incio da lgica

Desenvolvimento da lgica formal (sculos 19 e 20) => fornece uma notao precisa para declarar sobre todos os tipos de coisas do mundo e as relaes entre elas

Em 1965 existiam programas que podiam resolver qualquer problema solucionvel descrito em notao lgica Se no houver uma soluo o programa pode nunca mais parar

11

Pensando racionalmente A tradio logicista da IA tenta desenvolver tais programas

para criar sistemas inteligentes

Obstculos da abordagem:

Dificuldade de passar conhecimento informal para termos formais (notao lgica) principalmente quando o conhecimento impreciso

Existe uma grande diferena entre ser capaz de resolver um problema e fazer isto na prtica

Problemas pequenos podem esgotar os recursos computacionais se no tiverem alguma orientao de quais etapas de raciocnio ele deve tentar primeiro

12

Agindo racionalmente: o agente racional Agente computacional X programas

Operar sob controle autnomo, perceber seu ambiente, adaptar-se s mudanas ser capaz de assumir metas

Agente racional => age para alcanar o melhor resultado (esperado)

Comportamento Racional FAZER A COISA CERTA aquilo que maximiza o objetivo, dada a informao disponvel

Fazer inferncias corretas parte de uma agente racional Agir racionalmente raciocinar logicamente sobre o objetivo que

uma dada ao ir alcanar, e ento agir

13

Agindo racionalmente Inferncia correta no representa toda a racionalidade

Algo deve ser feito, mas no existe algo comprovadamente correto

Agir racionalmente s vezes no envolve inferncia. Ex: tirar a mo de algo quente

Obs.:Limitaes computacionais tornam a racionalidade perfeita inalcanvel.

14

Qual o ncleo do problema?

Conhecimento

Aquisio Representao Uso

15

Sub-reas de IA

Conhecimento

AquisioAprendizagem Simblica Conexionista Social e emergentePercepo Viso

RepresentaoLgicasRedes Simblica Conexionista BayseanaFrames

UsoRaciocnioPlanejamentoPLNRobtica

16

Fundamentos da inteligncia artificial

IA

Filosofia Matemtica

PsicologiaComputao

Lingstica

Economia

Neurocincia

Teoria de Controle e Ciberntica

17

Filosofia (428 B.C. - presente) Lgica e mtodos de raciocnio

Aristteles (384-322 a.C.) silogismos, noo de intuio

Ramon Lull (1315) artefato mecnico para raciocnio til

Thomas Hobbes (1588-1679) raciocnio semelhante computao numrica

Leonardo da Vinci (1500) projeto de uma calculadora mecnica

Wilhelm Leibniz (1623) primeira mquina de calcular conhecida

A mente como um sistema fsico

Ren Descartes (1596-1650) Dualismo mente isenta das leis da fsica (matria)

materialismo, onde todas as coisas do mundo (inclusive o crebro e a mente) opera segundo leis fsicas

18

Filosofia (428 B.C. - presente) A origem do conhecimento

Francis Bacon's (1561-1626) - empirismo, conhecimento est baseado na observao e na experincia

Hume (1739) - princpio da induo - regras gerais so adquiridas pela exposio e repetidas associaes entre seus elementos

Ludwig Wittgestein (1889-1951) e Bertrand Russel (1872-1970) - positivismo lgico - observaes que correspondem ao sensores de entrada

Carnap e Carl Hempel (1905 - 1997) teoria da confirmao tentava compreender como o conhecimento pode ser adquirido a partir da experincia

Racionalidade

19

Matemtica (800-presente) Representao formal e lgica clssica

George Boole (1847) - linguagem formal para fazer inferncias lgicas - lgica booleana

Gottlob Frege (1879) - formou a lgica de predicados de primeira ordem, que utilizada em boa parte dos sistemas atuais (RC)

Alfred Tarski (1902-1983) - teoria que mostra como relacionar objetos em uma lgica a objetos do mundo real

Algoritmos de prova

Kurt Gdel (1931) - teorema da incompletude, existem afirmaes verdadeiras que so indecidveis sua verdade no pode ser estabelecida por qualquer algoritmo

20

Matemtica (800-presente) Indecidibilidade

Alan Turing (1936) - modelo da mquina de Turing - determinar se um problema ou no decidvel (um problema decidvel se existe um algoritmo para ele)

Intratabilidade

Cobham (1964) e Edmonds (1965) intratabilidade - o tempo de execuo dos problemas chamados intratveis crescem exponencialmente em relao ao tamanho de suas instncias

Teoria da NP-Completude

Steven Cook (1971) e Richard Karp (1972) mtodo para reconhecer um problema intratvel

21

Matemtica (800-presente) Teoria da Probabilidade

Gerolamo Cardano (1501-1576) - teoria da probabilidade

Tomas Bayes (1702-1761) anlise Bayesiana - regras para quantificar probabilidades subjetivas (tratamento de incerteza)

22

Economia (1776-presente) Economia:estuda como as pessoas fazem escolhas que levam

a resultados preferenciais (utilidade)

Utilidade Lon Walras (1834-1910)

Frank Ramsey (1931)

Teoria dos jogos e o comportamento econmico John Von Neumann e Oskar Morgenstern (1944)

Teoria da deciso = teoria da probabilidade + teoria da utilidade Wellman (1965)

Pesquisa operacional Richard Bellman (1957) processos de deciso de Markov

23

Neurocincia (1861-presente) Como o crebro processa informaes?

Paul Broca (1861) estudos em deficincia da fala em pacientes com crebros danificados

Camillo Golgi (1873) tcnica de colorao para observar neurnios no crebro

Santiago Ramon Cajal (1852-1934) estudos pioneiros das estruturas de neurnios no crebro

Hans Berger (1929) eletroencefalgrafo medio da atividade do crebro intcto

24

Psicologia (1879-presente) Fenmenos de percepo e controle

H. S. Jennings (1906) Introspeco

John Watson (1878-1958)- behaviorism (comportamentalismo) medidas obejetivas de percepo estmulo e resposta

O crebro como um dispositivo de processamento de informaes

Willian James (1842-1910) Psicologia Cognitiva

Passos entre a percepo e as aes

Kenneth Craik (1943) - especificou trs passos chaves de um agente baseado em conhecimento: (1) O estmulo transformado em uma representao interna;

(2) A representao manipulada por um processo cognitivo que deriva novas representaes internas; e

(3) Esta representao traduzida em uma ao.

25

Computao (1940-presente) A inteligncia artificial necessita de duas coisas: inteligncia e um

artefato. Atualmente o computador o artefato mais adequado.

Alan Turing e sua equipe Mquina eletromecnica de Health Robison (1940) - decifrar mensagens

Alems Colussus (1943) mquina de uso geral utilizava vlvulas

Konrad Zuse (1941) - Z-3 primeiro computador programvel, pontos flutuantes e a 1 linguagem de programao de alto nvel: Plankalkl

John Atanasoff e Clifford Berry (1942) ABC Primeiro computador eletrnico

John Mauchly e John Eckert - ENIAC (2 guerra - primeiro computador digital de propsito geral) mais famoso pq seus conceitos ainda so utilizados

Evoluo do software: sistemas operacionais, linguagens de programao e ferramentas necessrias para escrever programas sofisticados

26

Teoria de controle e ciberntica Projetos de sistemas que maximizem o objetivo

Ctesbio de Alexandria (+ ou - 250 a. C.) primeira mquina autocontrolada um relgio de gua com um regulador que mantinha o fluxo de guam constante

James Watt (1736 1819) regulador de mquinas a vapor

Cornelis Debbell (1572 1633) Termostato e o submarino

Norbert Wiener (1894 - 1964) Teoria de controle possibilidade de mquinas dotadas de inteligncia

27

Lingstica (1957-presente) Representao de conhecimento e gramtica

B. F. Skinner (1957) - Verbal Behavior - Abordagem comportamentalista para o aprendizado da linguagem

Chomsky - exibiu como a teoria comportamentalista no est direcionada a noo de criatividade na linguagem Ela no explicava como uma criana podia compreender e formar frases que

nunca tinha ouvido antes.

IA + Lingstica = Lingstica computacional ou PLN

Compreenso da linguagem exige compreenso do assunto e do contexto (e no somente sintaxe)

Representao do Conhecimento como colocar o conhecimento em uma forma que o computador possa utilizar vinculado linguagem

28

Histria da inteligncia artificial A gestao da inteligncia artificial (1943-1956)

Warren McCulloch e Walter Pitts (1943) modelo de neurnios artificiais

Cada neurnio poderia estar ligado ou desligado

Troca para ligado ocorria como resposta aos estmulos para um nmero suficiente de neurnios vizinhos

Idia de que as redes seriam capazes de aprender

Donald Hebb (1949) regra de atualizao dos pesos da rede

Marvin Minsky e Dean Edmonds (1951) SNARC o primeiro computador de redes neurais, possua 40 neurnios

Alan Turing (1950) artigo Computing Machinery and Intelligence

29

Histria da inteligncia artificial O nascimento da Inteligncia Artificial (1956)

John McCarthy, Minsky, Claude Shannon e Nathaniel Rochester (1956) seminrio de dois meses, com 10 participantes

Allen Newell e Herbert Simon Logic Therorist programa de raciocnio

McCarthy sugere o nome Inteligncia Artificial

30

Entusiasmo inicial, grandes espectativas (1952-1969)

A classe intelectual preferia acreditar que uma mquina nunca poder realizar X Os pesquisadores em IA respondiam naturalmente demostrando um

X aps o outro

Newell e Simon - General Problem Solver (GPS) - Programa projetado para resolver problemas como os humanos

Nathaniel Rochester e Herbert Gelernter (1959) Geometry Problem Solver podiam demonstrar teoremas complicados para alunos de matemtica

Arthur Samuel (1952) srie de programas para jogar damas que podiam aprender

Histria da inteligncia artificial

31

Histria da inteligncia artificial McCarthy (1958) - Lisp - Um ano mais nova que FORTRAN

Advice Taker 1 sistema de IA completo princpios centrais de RC e raciocnio

Escassez e custo dos recursos computacionais => time sharing

J. A. Robinson mtodo de resoluo algoritmo completo para demostrao de teoremas em lgica de primeira ordem

Minsky - Micromundos - Problemas em um contexto limitado que requer inteligncia para resolver

Ex: Mundo de blocos

Frank Rosemblatt (1962) Perceptrons e o teorema de convergncia

32

Histria da inteligncia artificial Uma dose de realidade (1966-1974)

Herbert Simon futuro visvel computadores lidaro com uma variedade de problemas correspondente mente humana

previso: dentro de dez anos um computador seria campeo de xadrez e provaria um teorema matemtico significativo

Dificuldade de tratar problemas complexos (exemplos testados eram muito simples)

Principais problemas nas abordagens adotadas:

Os programas possuam pouco, ou nenhum conhecimento sobre o problema objeto

Problema de traduo Russo ingls Traduo exige conhecimento do assunto

33

Histria da inteligncia artificial Intratabilidade de alguns problemas que AI estava tentando

resolver (antes da teoria da NP-completude)

Iluso do poder computacional ilimitado, computadores 1.000.000 x mais rpidos no resolvem o problema exploso combinatria

Problemas NP-completos existem e novas abordagens devem ser adotadas

Machine evolution (algoritmos genticos de hoje)

Limitaes fundamentais nas estruturas "bsicas" que estavam sendo utilizadas para gerar um comportamento inteligente

Ex: Estrutura at ento utilizada para representar redes neurais

Minsky (1969) Os perceptrons podem aprender qualquer coisa que eles so capazes de representar, mas eles podem representar muito pouco.

Cai o mito que em pouco tempo teramos mquinas super inteligentes

34

Histria da inteligncia artificial Sistemas baseados em conhecimento (1969-1979)

Weak methods (pouco informao sobre o domnio) necessidade maior de computao

Surgimento dos Sistemas Especialistas Conhecimento e regras sobre um determinada especialidade

Separao entre conhecimento mecanismo de raciocnio

Buchanan e outros DENDRAL (1969) conhecimento de qumica reduz a quantidade de computao

Feigenbaum e outros MYCIN diagnstico de doenas infecciosas (450 regras)

Problemas do mundo real representao de conhecimento teve que melhorar Surgimento de novas LRCs Frames (Minsky), abordagem mais estruturada baseada em

classes e hierarquia de objetos

35

Histria da inteligncia artificial A IA se torna uma indstria (1980 hoje)

Digital Equipment Corporation R1 (ajuda a configurar pedidos de novos sistemas de computadores) Economia de 40 milhes de dlares (1986)

1988 O grupo de IA da DEC tinha 40 sist. especialistas entregues Du Pont - 100 SEs em uso e 500 em desenvolvimento

Economia de 10 milhes de dlares

Projetos ambiciosos no Japo e EUA (1981) nunca atenderam suas metas

Industria da IA: 1980 alguns milhes 1988 bilhes de dlares

36

Histria da inteligncia artificial O retorno das redes neurais (1986-presente)

Desenvolvimento continuou em outras reas (fsica, psicologia)

Recriao do algoritmo back-propagation (4 grupos diferentes)

IA Tradicional x Redes Neurais

Eventos recentes (1987-1995-2000)

Avanos e utilizao de tecnologia para reconhecimento de imagem e fala/som.

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

Desenvolvimento de mecanismos lgicos para tratar incerteza. Ex: lgica fuzzy, lgica modal, etc.

37

O estado-da-arte O que pode ser feito (usando IA) atualmente?

Planejamento autnomo e escalonamento (NASA)

Jogos: Deep Blue da IBM derrota Garry Kasparob campeo mundial de xadrez

Controle autnomo: Sistema de viso computacional ALVINN treinado para dirigir um automvel

Diagnstico: Programas de diagnstico mdico com explicao

Planejamento logstico e programao de execuo de transporte

Robtica: Ao ponto de ajudarem em microcirurgias

Reconhecimento de linguagem e resoluo de problemas