Inteligência Artificial Prof. Dr. Sérgio Silva Profª. Josiane M. Pinheiro 1 Motivação Planejamento de Processos Controle de despacho p/ centros de produção Obtenção de recursos - estoque, fornecedores - prazo de entrega... Alocação de recursos Logística – recursos X tempo Otimização de aproveitamento de recursos Satisfação dos clientes (tempo, qualidade, custo) Grandes quantidades de dados (data mining) Maior capacidade de processamento e a melhoria dos algoritmos permitem a resolução de problemas que eram computacionalmente inviáveis 2 Motivação Companhia Vale do Rio Doce UNICAMP – Sistema especialista baseada em lógica difusa Lógica difusa - frio/quente, cheio/vazio, alto/baixo Despacho de trens com minério de ferro das Minas de Carajás para o Porto de São Luiz 892 km de trilhos por onde trafegam 124 mil m3 de aço/dia Sistema analisa o movi// dos trens e auxilia o planeja// do melhor despacho de aço entre os mesmos Aumento da quantidade de aço transportada em 15% Redução do consumo de óleo diesel em 1,6l a cada mil m3 de aço transportadas 3 O que é Inteligência Artificial (IA) ? A automação das atividades que associamos ao pensamento humano, tais como: tomadas de decisão, solução de problemas, aprendizado. [BELLMAN, 1978]. O estudo das faculdades mentais usando modelos computacionais. [CHARNIAK & McDERMOTT, 1985] O estudo de como os computadores fazem coisas que, no momento, as pessoas são melhores. [RICH + KNIGHT, 1991] O ramo da ciência da computação que está relacionado com a automação do comportamento inteligente. [LUGGER & STUBBLEFIELD, 1993]. 4 O que é Inteligência Artificial (IA)? Definição: O ramo da ciência da computação que trata da automação do comportamento inteligente. Tarefa: Compreender o comportamento inteligente para construir entidades inteligentes. Problema: O que é inteligência? 5 O que é INTELIGÊNCIA ? Exatamente o que ocorre quando aprendemos? O que é criatividade? O que é intuição? Ela pode ser inferida de um comportamento observável ou requer algum mecanismo interno particular? Como o conhecimento é representado nos tecidos de um ser vivo? Que lições isto traz para o design de máquinas inteligentes? O que pode ser aproveitado dos seres vivos? 6 O que é INTELIGÊNCIA ? Que papel a cultura exerce sobre a inteligência? É necessário basear um computador inteligente sobre o que se conhece sobre a inteligência humana ou uma abordagem de engenharia é suficiente? É possível atingir a inteligência em um computador ou inteligência requer a capacidade de sentir e experienciar que só existe em seres vivos? O que é auto-conhecimento? Que papel ele exerce sobre a inteligência? 7 Qual é o núcleo do problema? Conhecimento Aquisição Representação Uso 8 Sub-áreas de IA Conhecimento Aquisição Representação Uso Aprendizagem Simbólica Conexionista Social e emergente Percepção Visão … Lógica Redes Simbólica Conexionista Bayseana Raciocínio Planejamento PLN Robótica … 9 Quatro pontos de vista sobre AI Pensando “A automação de atividades que nós associamos com o pensamento humano” “O estudo das faculdades mentais através do uso de modelos computacionais” Como humanos “A arte de criar máquinas que realizam funções que requerem inteligência quando realizadas por pessoas” Racionalmente “O ramo da Ciência da Computação que estuda a automação de comportamento inteligente” Agindo 10 Agindo como humanos: O teste de Turing Turing (1950): “Computing Machinery and Intelligence” [http://www.abelard.org/turpap/turpap.htm] As máquinas podem pensar? As máquinas podem se comportar inteligentemente? Teste operacional para comportamento inteligente: O JOGO DA IMITAÇÃO Previu que, em 2000, as máquinas teriam 30% de chance de enganar uma pessoa leiga por 5 minutos. Antecipou os principais argumentos contrários à IA dos próximos 50 anos; 11 Agindo como humanos: O teste de Turing O Interrogador 12 Agindo como humanos: O teste de Turing Para passar no Teste de Turing é necessário: Processamento de Linguagem Natural Representação de Conhecimento Raciocínio Automático Aprendizagem de máquina Teste de Turing Total Visão Computacional Robótica 13 Agindo como humanos: O teste de Turing Softwares Existentes: Eliza: http://shoel.cscmicro.com/eliza.html Este programa simula um psicoterapeuta rogeriano. Não use tempo passado ou pontuação. Eliza não entende sentença fragmentadas como "all the time". Ela entende apenas algumas simples sentenças completas como: i am lonely my dad hits me i love my freedom Júlia: http://fuzine.mt.cs.cmu.edu/mlm/julia.html É um programa que tenta passar pelo Teste de Turing. Ele é descendente do Eliza. Para acessar o programa dê o login como "julia" sem senha. ... 14 Pensando como humanos: Modelagem Cognitiva Programas pensam como humanos => como os humanos pensam? Como a mente humana trabalha por dentro? Através de introspecção Através de experimentos psicológicos Uma teoria precisa do funcionamento da mente => possibilidade de expressar a teoria no computador 15 Pensando como humanos: Modelagem Cognitiva Newell e Simon (1961) – General Problem Solver (GPS) Ciência Cognitiva –modelos computacionais da IA + técnicas experimentais da psicologia Estavam preocupados em comparar as formas de seu raciocínio às formas do raciocínio humano para resolver os mesmos problemas Tentar construir teorias precisas e testáveis a respeito dos processos de funcionamento da mente humana IA e ciência cognitiva ajudam uma a outra, especialmente em áreas de visão computacional, linguagem natural e aprendizagem 16 Pensando racionalmente: as leis do pensamento Aristóteles => pensamento correto => silogismos Silogismos = conclusões corretas para premissas corretas As leis do pensamento deveriam governar as operações da mente => início da lógica Desenvolvimento da lógica formal (séculos 19 e 20) => fornece uma notação precisa para declarar sobre todos os tipos de coisas do mundo e as relações entre elas 17 Pensando racionalmente: as leis do pensamento (1965) programas existentes Entrada: descrição do problema em notação lógica + tempo e memória Saída: a solução do problema, se ela existir Obstáculos da abordagem: Dificuldade de passar conhecimento informal para termos formais (notação lógica) – principalmente quando o conhecimento é impreciso Existe uma grande diferença entre ser capaz de resolver um problema e fazer isto na prática (recursos computacionais) 18 Agindo racionalmente: o agente racional Comportamento Racional FAZER A COISA CERTA A coisa certa é aquilo que maximiza o objetivo, dada a informação disponível Uma agente é uma entidade que percebe e age Leis do pensamento => inferências corretas Fazer inferências corretas é parte de uma agente racional Agir racionalmente é raciocinar logicamente sobre o objetivo que uma dada ação irá alcançar, e então agir 19 Agindo racionalmente: o agente racional Inferência correta nem sempre envolve racionalidade Algo deve ser feito, mas não existe algo correto a fazer Agir racionalmente às vezes não envolve inferência. Ex: tirar a mão de algo quente Vantagens sobre as outras abordagens Mais geral do que as leis do pensamento => inferência correta é apenas um mecanismo utilizado para alcançar racionalidade É mais adequada ao desenvolvimento científico do que as abordagens baseadas no comportamento e no pensamento humano => o padrão de racionalidade é claramente definido e completamente geral Obs.: Limitações computacionais tornam a racionalidade perfeita inalcançável. 20 Fundamentos da inteligência artificial IA Filosofia Matemática Psicologia Computação Lingüística 21 Filosofia (428 B.C. - presente) Tornaram a IA concebível Considerando a idéia de que a mente é, em alguns aspectos, semelhante a uma máquina Ela opera sobre o conhecimento codificado em alguma linguagem interna E o pensamento pode escolher as ações que deverão ser executadas Aristóteles (384-322 a.C.) – silogismos, noção de intuição René Descartes (1596-1650) – Dualismo – mente isenta das leis da física (matéria) Wilhelm Leibniz (1646-1716) imaginava construir equipamentos mecânicos que realizava operações mentais (materialismo) materialismo, onde todas as coisas do mundo (inclusive o cérebro e a mente) opera segundo leis físicas 22 Filosofia (428 B.C. - presente) Quanto à fonte do conhecimento Francis Bacon's (1561-1626) - empirismo, conhecimento está baseado na observação e na experiência Hume (1978) - princípio da indução - regras gerais são adquiridas pela exposição e repetidas associações entre seus elementos Bertrand Russel (1872-1970) - positivismo lógico - observações que correspondem ao sensores de entrada Atualmente existem várias teorias sobre como o conhecimento é adquirido e representado O elemento final do modelo filosófico da mente é a conexão entre o conhecimento e a ação 23 Matemática (800-presente) Forneceram as ferramentas para manipular declarações de certeza lógica declarações incertas e probabilísticas Definiram a base para a compreensão da computação (algoritmo forma) e do raciocínio inteligente George Boole (1847) - linguagem formal para fazer inferências lógicas (lógica booleana) Gottlob Frege (1879) - formou a lógica 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 lógica a objetos do mundo real Kurt Gödel (1931) - teorema da incompletude, o qual mostra que para alguns problemas não podem ser estabelecidos um algoritmo 24 Matemática (800-presente) Alan Turing (1936) - modelo da máquina de Turing determinar se um problema é ou não decidível um problema é decidível se existe um algoritmo para ele Cobham (1964) e Edmonds (1965) – intratabilidade - o tempo de execução dos problemas chamados intratáveis crescem exponencialmente em relação ao tamanho de suas instâncias Gerolamo Cardano (1501-1576) - teoria da probabilidade Tomas Bayes (1702-1761) – análise Bayesiana - regras para quantificar probabilidades subjetivas (tratamento de incerteza) John Von Neumann e Oskar Morgenstern (1944) - teoria da decisão – teoria da probabilidade + teoria da utilidade 25 Psicologia (1879-presente) Idéia de que os seres humanos e os animais podem se considerados máquinas de processamento de informações John Watson (1878-1958) e Edward Lee Thorndike (18741949) - Behaviorism (comportamentalismo) Rejeita a idéia de que a introspecção fornece evidências confiáveis sobre o comportamento humano Estuda somente medidas objetivas sobre a percepção (stimulus) e as ações resultantes (response) Teve sucesso na compreensão dos animais, mas teve pouco sucesso na compreensão de humanos. A psicologia cognitiva vê o cérebro como um dispositivo de processamento de informações. Percepção envolvia uma forma de inferência lógica inconsciente. 26 Psicologia (1879-presente) Passos entre a percepção e as ações (Kenneth Craik, 1943). Craik especificou três passos chaves de um agente baseado em conhecimento: (1) O estímulo é transformado em uma representação interna; (2) A representação é manipulada por um processo cognitivo que deriva novas representações internas; e (3) Esta representação é traduzida em uma ação. Forte interação entre IA e a ciência cognitiva (processos de transformação do conhecimento bem definidos). 27 Computação (1940-presente) A inteligência artificial necessita de duas coisas: inteligência e um artefato. Atualmente o computador é o artefato mais adequado. Máquina eletromecânica de Health Robison (1940) time de Alan Turing - decifrar mensagens Alemãs Colussus (1943) – máquina de uso geral – utilizava válvulas Z-3 (Konrad Zuse, 1941, Alemanha), primeiro comp. programável Primeiro computador eletrônico (USA) ABC (John Atanasoff e Clifford Berry, 1942) ENIAC (2º guerra - primeiro computador digital de propósito geral) – mais famoso pq seus conceitos ainda são utilizados IBM 701 (1952 - primeiro com fins comerciais). 28 Computação (1940-presente) Evolução do software: sistemas operacionais, linguagens de programação e ferramentas necessárias para escrever programas sofisticados. Varias contribuições de IA para ciência da computação: compartilhamento de tempo, conceitos de orientação a objetos e desenvolvimento de programas com interfaces gráficas 29 Lingüística (1957-presente) B. F. Skinner (1957) - Verbal Behavior - Abordagem comportamentalista para o aprendizado da linguagem Chomsky - exibiu como a teoria comportamentalista não está direcionada a noção de criatividade na linguagem Ela não explicava como uma criança podia compreender e formar frases que nunca tinha ouvido antes. IA + Lingüística = Lingüística computacional ou PLN Compreensão da linguagem exige compreensão do assunto e do contexto (e não somente sintaxe) Representação do Conhecimento – como colocar o conhecimento em uma forma que o computador possa utilizar – vinculado à linguagem 30 História da inteligência artificial A gestação da inteligência artificial (1943-1956) Warren McCulloch e Walter Pitts (1943) – modelo de neurônios artificiais Cada neurônio poderia estar “ligado” ou “desligado” 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 construiram o primeiro computador de redes neurais em 1951, possuía 40 neurônios Primeiras conferências atribuir o nome do campo a Inteligência Artificial 31 História da inteligência artificial Entusiasmo inicial (1952-1969) Newell e Simon - General Problem Solver (GPS) Programa projetado para resolver problemas como os humanos Sebmetas e ações - semelhantes à ordem de resolução dos humanos Herbert Gelernter (1959) – Geometry Theorem Prover Demonstrava teoremas bastante complicados Arthur Samuel (1952) – série de programas para jogar damas que podiam aprender 32 História da inteligência artificial McCarthy (1958) - Lisp - Um ano mais nova que FORTRAN Advice Taker – 1º sistema de IA completo – princípios centrais de RC e raciocínio Escassez e custo dos recursos computacionais => time sharing Minsky - Micromundos - Problemas em um contexto limitado que requer inteligência para resolver Ex: Mundo de blocos 33 História da inteligência artificial Uma dose de realidade (1966-1974) Herbert Simon – “futuro visível” – computadores lidarão com uma variedade de problemas correspondente à mente humana Dificuldade de tratar problemas complexos (exemplos testados eram muito simples) Principais problemas nas abordagens adotadas: Os programas possuíam pouco, ou nenhum conhecimento sobre o problema objeto Problema de tradução Russo <-> inglês 34 História da inteligência artificial Intratabilidade de alguns problemas que AI estava tentando resolver (antes da teoria da NP-completude) Ilusão do poder computacional ilimitado, computadores 1.000.000 x mais rápidos não resolvem o problema – explosão combinatória Problemas NP-completos existem e novas abordagens devem ser adotadas Machine evolution (algoritmos genéticos de hoje) Limitação de estruturas "básicas" para gerar um comportamento inteligente Ex: Estrutura até então utilizada para representar redes neurais Minsky (1969) – Os perceptrons podem aprender qualquer coisa que eles são capazes de representar, mas eles podem representar muito pouco. Cai o mito que em pouco tempo teríamos máquinas “super inteligentes” 35 História da inteligência artificial Sistemas baseados em conhecimento (1969-1979) Weak methods (pouco informação sobre o domínio) – necessidade maior de computação Surgimento dos Sistemas Especialistas Conhecimento, heurísticas e regras sobre um determinada especialidade Separação clara entre conhecimento (regras) e componente de raciocínio DENDRAL – conhecimento de química reduz a quantidade de computação Feignbaum e outros – MYCIN – diagnostico de doenças infecciosas (450 regras) Problemas do mundo real – representação de conhecimento teve que melhorar Frames (Minsky), abordagem mais estruturada baseada em classes e hierarquia de objetos, analogia com taxonomia da biologia 36 História da inteligência artificial A IA se torna uma indústria (1980 – hoje) Digital Equipment Corporation – R1 (pedidos de novos computadores Economia de 40 milhões de dólares 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 milhões de dólares 37 História da inteligência artificial O retorno das redes neurais (1986-presente) Desenvolvimento continuou em outras áreas Uso/desenvolvimento de algoritmos “back-propagation” IA Tradicional x Redes Neurais Eventos recentes (1987-1995-2000) 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. 38 O estado-da-arte O que pode ser feito (usando IA) atualmente? Planejamento autônomo e escalonamento (NASA) Jogos: Programa da IBM derrota campeão mundial de xadrez Controle autônomo: Sistema de visão computacional ALVINN treinado para dirigir um automóvel Diagnóstico: Programas de diagnóstico médico com explicação Planejamento logístico e programação de execução de transporte Robótica: Ao ponto de ajudarem em microcirurgias Reconhecimento de linguagem e resolução de problemas 39 Atualmente... Duas vertentes principais Simbólica Conexionista Símbolos (objetos, frames) Regras Redes neurais Reconhecimento de padrões Tentativa de unir os dois paradigmas => sistemas hibrídos Lógica difusa (ou fuzzy) Algoritmos Genéticos 40 Atualmente... Ramos da IA Sistemas especialistas Processamento de linguagem natural Robótica Aprendizado de Máquina Reconhecimento de Padrões ... 41 Sistema Inteligente Definição segundo Turing (1950): “Um sistema é inteligente se e somente se ele produz a mesma saída simbólica que um ser humano produziria, dada a mesma entrada simbólica” Características Heurísticas ao invés de algoritmos pré-determinados Problemas diferentes, soluções diferentes A solução tem que ser construída 42 Heurística X Algoritmo Metodologia empregada para resolver problemas de IA Algoritmo Mais heurística do que sistemática, algorítmica Regra Premissas conhecida => resultados esperados Solução lógica, verdade, regra matemática (resolver eq. de 2º) Verificável Heurística Não é verificável – matematicamente provável Solução obtida através de tentativas e erros Regras práticas desenvolvidas através da experiência 43