Inteligencia artificial 3a ed russell stuart norvig peterpdf PDF

Preview

Summary

Do original: Artificial Intelligence Tradução autorizada do idioma inglês da edição publicada por Prentice Hall Copyright © 2010, 2003,1995 by Pearson Education, Inc. © 2013, Elsevier Editora Ltda. Todos os direitos reservados e protegidos pela Lei no 9.610, de 19/02/1998. Nenhuma parte deste livro...

Description

Do original: Artificial Intelligence Tradução autorizada do idioma inglês da edição publicada por Prentice Hall Copyright © 2010, 2003,1995 by Pearson Education, Inc. © 2013, Elsevier Editora Ltda. Todos os direitos reservados e protegidos pela Lei no 9.610, de 19/02/1998. Nenhuma parte deste livro, sem autorização prévia por escrito da editora, poderá ser reproduzida ou transmitida sejam quais forem os meios empregados: eletrônicos, mecânicos, fotográficos, gravação ou quaisquer outros. Coordenação de produção: Silvia Lima Copidesque: Ivone Teixeira Editoração eletrônica: DTPhoenix Editorial Revisão gráfica: Marília Pinto de Oliveira Conversão para eBook: Freitas Bastos Elsevier Editora Ltda. Conhecimento sem Fronteiras Rua Sete de Setembro, 111 – 16o andar 20050-006 – Centro – Rio de Janeiro – RJ – Brasil Rua Quintana, 753 – 8o andar 04569-011 – Brooklin – São Paulo – SP – Brasil Serviço de Atendimento ao Cliente 0800-0265340 [email protected] ISBN da edição original: 978-0136042594 ISBN: 978-85-352-3701-6 Nota: Muito zelo e técnica foram empregados na edição desta obra. No entanto, podem ocorrer erros de digitação, impressão ou dúvida conceitual. Em qualquer das hipóteses, solicitamos a comunicação ao nosso Serviço de Atendimento ao Cliente, para que possamos esclarecer ou encaminhar a questão. Nem a editora nem o autor assumem qualquer responsabilidade por eventuais danos ou perdas a pessoas ou bens, originados do uso desta publicação.

CIP-Brasil. Catalogação-na-fonte. Sindicato Nacional dos Editores de Livros, RJ

Russell, Stuart J. (Stuart Jonathan), 1962Inteligência artificial / Stuart Russell, Peter Norvig; tradução Regina Célia Simille. – Rio de Janeiro: Elsevier, 2013. R925i

Tradução de: Artificial intelligence, 3rd ed. Inclui bibliografia e índice ISBN 978-85-352-3701-6 1. Inteligência artificial. I. Norvig, Peter, 1956- II. Título.

115978

CDD: 006.3 CDU: 004.81

Para Loy, Gordon, Lucy e Isaac — S.J.R. Para Kris, Isabella e Juliet — P.N.

Prefácio inteligência artificial (IA) é um grande campo, e este é um grande livro. Tentamos explorar toda a extensão do assunto, que abrange lógica, probabilidade e matemática do contínuo, além de percepção, raciocínio, aprendizado, ação e, ainda, tudo o que se refere à eletrônica, desde dispositivos microeletrônicos até robôs para exploração planetária. O livro também é grande porque nos aprofundamos na apresentação de resultados. O subtítulo deste livro é “Uma Abordagem Moderna”. O significado pretendido dessa frase um tanto vazia é que tentamos sintetizar o que hoje é conhecido numa estrutura comum, em vez de tentarmos explicar cada subcampo da IA em seu próprio contexto histórico. Pedimos desculpas àqueles que trabalham em subcampos, que, como resultado, receberam menos reconhecimento do que deveriam.

A

Novidades desta edição Esta edição capturou as mudanças em IA que tiveram lugar desde a última edição em 2003. Houve aplicações importantes de tecnologia de IA, tais como a implantação generalizada da prática de reconhecimento de fala, tradução automática, veículos autônomos e robótica de uso doméstico. Houve marcos em algoritmos, como a solução do jogo de damas, e um significativo progresso teórico, particularmente em áreas como a do raciocínio probabilístico, aprendizado de máquina e visão computacional. Mais importante, do nosso ponto de vista, é a evolução contínua na maneira como pensamos sobre essa área e, dessa forma, como organizamos este livro. As principais mudanças foram as seguintes: •

•

• • •

Colocamos mais ênfase em ambientes parcialmente observáveis e não determinísticos, especialmente nas configurações não probabilísticas de pesquisa e planejamento. Os conceitos de estado de crença (um conjunto de mundos possíveis) e estimação de estado (manutenção do estado de crença) foram introduzidos nesta versão; mais adiante, adicionamos probabilidades. Além de discutir os tipos de ambientes e tipos de agentes, agora cobrimos com mais profundidade os tipos de representações que um agente pode utilizar. Distinguimos entre representações atômicas (em que cada estado do mundo é tratado como uma caixa-preta), representações fatoradas (em que um estado é um conjunto de atributos/pares de valor) e representações estruturadas (em que o mundo consiste em objetos e relações entre eles). Nossa cobertura do planejamento aprofundou-se sobre o planejamento contingente em ambientes parcialmente observáveis, incluindo​​ uma nova abordagem para o planejamento hierárquico. Adicionamos um novo material de modelos probabilísticos de primeira ordem, incluindo modelos de universo aberto para casos de incerteza quanto à existência de objetos. Reescrevemos totalmente o capítulo introdutório de aprendizado de máquina, salientando uma variedade ampla de aprendizagem mais moderna de algoritmos, colocando-os em um patamar

teórico mais consistente. • Expandimos a cobertura de pesquisa na Web e de extração de informações e de técnicas de aprendizado a partir de conjuntos de dados muito grandes. • 20% das citações desta edição são de trabalhos publicados depois de 2003. • Estimamos que 20% do material é novo. Os 80% restantes refletem trabalhos mais antigos, mas foram amplamente reescritos para apresentar uma imagem mais unificada da área.

Visão geral do livro O principal tema unificador é a ideia de agente inteligente. Definimos a IA como o estudo de agentes que recebem percepções do ambiente e executam ações. Cada agente implementa uma função que mapeia sequências de percepções em ações, e abordaremos diferentes maneiras de representar essas funções, tais como sistemas de produção, agentes reativos, planejadores condicionais em tempo real, redes neurais e sistemas de teoria de decisão. Explicaremos o papel da aprendizagem como uma extensão do alcance do projetista em ambientes desconhecidos e mostraremos que esse papel restringe o projeto de agentes, favorecendo a representação explícita do conhecimento e do raciocínio. Trataremos da robótica e da visão, não como problemas definidos independentemente, mas como ocorrendo a serviço da realização de objetivos. Enfatizamos a importância do ambiente da tarefa na determinação do projeto apropriado de agentes. Nosso principal objetivo é transmitir as ideias que emergiram nos últimos cinquenta anos de pesquisa sobre a IA e nos dois últimos milênios de trabalhos relacionados a esse tema. Procuramos evitar uma formalidade excessiva na apresentação dessas ideias, ao mesmo tempo em que tentamos preservar a exatidão. Quando consideramos apropriado, incluímos algoritmos em pseudocódigo para tornar as ideias concretas; nosso pseudocódigo é descrito de forma sucinta no Apêndice B. Este livro se destina principalmente ao uso em cursos de graduação ou de extensão. Também pode ser usado em curso de pós-graduação (talvez com a inclusão de algumas das principais fontes de consulta sugeridas nas notas bibliográficas). O único pré-requisito é a familiaridade com os conceitos básicos de ciência da computação (algoritmos, estruturas de dados, complexidade) em nível básico; os fundamentos matemáticos necessários encontram-se no Apêndice A.

Os exercícios que exigem programação significativa estão marcados com um ícone de teclado. Esses exercícios podem ser mais bem resolvidos aproveitando-se o repositório de código e m aima.cs.berkeley.edu. Alguns deles são grandes o suficiente para serem considerados projetos semestrais. Vários exercícios exigem alguma investigação da literatura de referência; esses exercícios estão marcados com o ícone de livro. Ao longo do livro, os pontos importantes estão indicados por um pequeno ícone de mão apontando. Incluímos um índice extenso, com cerca de 6.000 termos, a fim de facilitar a localização de itens no livro. Onde quer que um novo termo seja definido pela primeira vez, ele também estará indicado na margem.

Sobre o site* aima.cs.berkeley.edu, o site do livro, contém: • implementações dos algoritmos do livro em várias linguagens de programação • uma lista de mais de 1.000 escolas que utilizaram o livro, muitas com links para materiais de cursos on-line e ementas • uma lista comentada com mais de 800 links para diversos sites com conteúdo útil de IA • uma lista, capítulo por capítulo, de materiais de consulta e links suplementares • instruções sobre como participar de um grupo de discussão referente ao livro • instruções sobre como entrar em contato com os autores para fazer perguntas ou comentários

Sobre a capa A capa mostra a posição final do jogo decisivo da partida 6 de 1997 entre o campeão de xadrez Garry Kasparov e o programa DEEP BLUE. Kasparov, com a cor preta, foi forçado a desistir, tornando essa a primeira vez que um computador derrotou um campeão do mundo em uma partida de xadrez. No topo está a imagem de Kasparov. À sua esquerda está o robô humanoide Asimo e, à sua direita, Thomas Bayes (1702-1761), cujas ideias sobre probabilidade, como medida de crença, formam a base de muito da tecnologia moderna de IA. Abaixo vemos o MarsExploration Rover, um robô que aterrissou em Marte em 2004 e tem explorado o planeta desde então. À direita está Alan Turing (1912-1954), cujo trabalho fundamental definiu os campos da ciência da computação em geral e da inteligência artificial em particular. No fundo está Shakey (1966-1972), o primeiro robô a combinar percepção, modelagem do mundo, planejamento e aprendizado. Junto com Shakey está o líder de projeto Charles Rosen (1917-2002). Embaixo à direita está Aristóteles (384-322 a.C.), pioneiro no estudo da lógica, seu trabalho foi o estado da arte até o século XIX (cópia de um busto por Lisipo). Na parte inferior à esquerda, levemente escondido atrás dos nomes dos autores, está um algoritmo de planejamento por Aristóteles de De Motu Animalium no original em grego. Atrás do título está uma porção da rede bayesiana CPSC para diagnóstico médico (Pradhan et al., 1994). Atrás do tabuleiro de xadrez encontra-se parte do modelo lógico bayesiano para detectar explosões nucleares a partir de sinais sísmicos. Créditos: Stan Honda/Getty (Kasparov), Biblioteca do Congresso (Bayes), Nasa (Mars rover), National Museum of Rome (Aristóteles), Peter Norvig (livro), Ian Parker (silhueta de Berkeley), Shutterstock (Asimo, peças de xadrez), Time Life/Getty (Shakey, Turing).

Agradecimentos Este livro não teria sido possível sem os muitos colaboradores cujos nomes não consegui colocar na capa. Jitendra Malik e David Forsyth escreveram o Capítulo 24 (visão computacional) e Sebastian Thrun escreveu o Capítulo 25 (robótica). Vibhu Mittal escreveu parte do Capítulo 22 (linguagem natural). Nick Hay, Mehran Sahami e Ernest Davis escreveram alguns dos exercícios. Zoran Duric

(George Mason), Thomas C. Henderson (Utah), Leon Reznik (RIT), Michael Gourley (Central Oklahoma) e Ernest Davis (NYU) revisaram o manuscrito e fizeram sugestões úteis. Agradecemos a Ernie Davis, em especial por sua capacidade incansável para ler múltiplos rascunhos e ajudar a melhorar o livro. Nick Hay formatou a bibliografia e no prazo final permaneceu até às 05h30 codificando para melhorar o livro. Jon Barron formatou e melhorou os diagramas nesta edição, enquanto Tim Huang, Mark Paskin e Cynthia Bruyns ajudaram com diagramas e algoritmos em edições anteriores. Ravi Mohan e Ciaran O’Reilly escreveram e mantiveram os exemplos de código Java no site. John Canny escreveu o capítulo de robótica para a primeira edição e Douglas Edwards pesquisou as notas históricas. Tracy Dunkelberger, Allison Michael, Scott Disanno e Jane Bonnell da Pearson fizeram o melhor possível para nos manter dentro do cronograma e deram muitas sugestões úteis. Mais útil de todas foi Julie Sussman, P.P.A., que leu todos os capítulos, proporcionando melhorias extensivas. Nas edições anteriores tivemos revisores que nos avisavam se deixávamos uma vírgula de fora, corrigiam para qual quando colocávamos que, Julie avisava-nos quando nos esquecíamos de um sinal de menos e corrigia para xi quando colocávamos xj. Para cada erro de digitação ou explicação confusa que permaneceu no livro, tenha certeza de que Julie corrigiu pelo menos cinco. Ela perseverou mesmo quando uma falha de energia a obrigou a trabalhar com luz da lanterna, em vez da incandescência do LCD. Stuart gostaria de agradecer a seus pais pelo apoio e incentivo constante, e à sua esposa, Loy Sheflott, por sua paciência infinita e sabedoria ilimitada. Ele espera que Gordon, Lucy, George e Isaac logo estejam lendo este livro, após perdoá-lo por ter trabalhado tanto. O RUGS (Russell’s Unusual Group of Students — Grupo Incomum de Alunos de Russell) foi de uma utilidade sem igual, como sempre. Peter gostaria de agradecer a seus pais (Torsten e Gerda), os responsáveis pelo início de sua carreira, e também à sua esposa (Kris), a seus filhos (Bella e Juliet), colegas e amigos pelo incentivo e pela tolerância durante as longas horas de escrita e durante as horas ainda mais longas em que foi preciso reescrever algumas páginas. Nós dois agradecemos aos bibliotecários em Berkeley, Stanford, e à Nasa e aos desenvolvedores do CiteSeer, Wikipédia e Google, que revolucionaram a maneira de pesquisar. Não podemos agradecer a todas as pessoas que utilizaram o livro e fizeram sugestões, mas gostaríamos de observar os comentários especialmente úteis de Gagan Aggarwal, Eyal Amir, Ion Androutsopoulos, Krzysztof Apt, Warren Haley Armstrong, Ellery Aziel, Jeff Van Baalen, Darius Bacon, Brian Baker, Shumeet Baluja, Don Barker, Tony Barrett, James Newton Bass, Don Beal, Howard Beck, Wolfgang Bibel, John Binder, Larry Bookman, David R. Boxall, Ronen Brafman, John Bresina, Gerhard Brewka, Selmer Bringsjord, Carla Brodley, Chris Brown, Emma Brunskill, Wilhelm Burger, Lauren Burka, Carlos Bustamante, João Cachopo, Murray Campbell, Norman Carver, Emmanuel Castro, Anil Chakravarthy, Dan Chisarick, Berthe Choueiry, Roberto Cipolla, David Cohen, James Coleman, Julie Ann Comparini, Corinna Cortes, Gary Cottrell, Ernest Davis, Tom Dean, Rina Dechter, Tom Dietterich, Peter Drake, Chuck Dyer, Doug Edwards, Robert Egginton, Asma’a El-Budrawy, Barbara Engelhardt, Kutluhan Erol, Oren Etzioni, Hana Filip, Douglas Fisher, Jeffrey Forbes, Ken Ford, Eric Fosler-Lussier, John Fosler, Jeremy Frank, Alex Franz, Bob Futrelle, Marek Galecki, Stefan Gerberding, Stuart Gill, Sabine Glesner, Seth Golub, Gosta Grahne, Russ Greiner, Eric Grimson, Barbara Grosz, Larry Hall, Steve Hanks, Othar Hansson, Ernst Heinz, Jim Hendler, Christoph

Herrmann, Paul Hilfinger, Robert Holte, Vasant Honavar, Tim Huang, Seth Hutchinson, Joost Jacob, Mark Jelasity, Magnus Johansson, Istvan Jonyer, Dan Jurafsky, Leslie Kaelbling, Keiji Kanazawa, Surekha Kasibhatla, Simon Kasif, Henry Kautz, Gernot Kerschbaumer, Max Khesin, Richard Kirby, Dan Klein, Kevin Knight, Roland Koenig, Sven Koenig, Daphne Koller, Rich Korf, Benjamin Kuipers, James Kurien, John Lafferty, John Laird, Gus Larsson, John Lazzaro, Jon LeBlanc, Jason Leatherman, Frank Lee, Jon Lehto, Edward Lim, Phil Long, Pierre Louveaux, Don Loveland, Sridhar Mahadevan, Tony Mancill, Jim Martin, Andy Mayer, John McCarthy, David McGrane, Jay Mendelsohn, Risto Miikkulanien, Brian Milch, Steve Minton, Vibhu Mittal, Mehryar Mohri, Leora Morgenstern, Stephen Muggleton, Kevin Murphy, Ron Musick, Sung Myaeng, Eric Nadeau, Lee Naish, Pandu Nayak, Bernhard Nebel, Stuart Nelson, XuanLong Nguyen, Nils Nilsson, Illah Nourbakhsh, Ali Nouri, Arthur Nunes-Harwitt, Steve Omohundro, David Page, David Palmer, David Parkes, Ron Parr, Mark Paskin, Tony Passera, Amit Patel, Michael Pazzani, Fernando Pereira, Joseph Perla, Wim Pijls, Ira Pohl, Martha Pollack, David Poole, Bruce Porter, Malcolm Pradhan, Bill Pringle, Lorraine Prior, Greg Provan, William Rapaport, Deepak Ravichandran, Ioannis Refanidis, Philip Resnik, Francesca Rossi, Sam Roweis, Richard Russell, Jonathan Schaeffer, Richard Scherl, Heinrich Schuetze, Lars Schuster, Bart Selman, Soheil Shams, Stuart Shapiro, Jude Shavlik, Yoram Singer, Satinder Singh, Daniel Sleator, David Smith, Bryan So, Robert Sproull, Lynn Stein, Larry Stephens, Andreas Stolcke, Paul Stradling, Devika Subramanian, Marek Suchenek, Rich Sutton, Jonathan Tash, Austin Tate, Bas Terwijn, Olivier Teytaud, Michael Thielscher, William Thompson, Sebastian Thrun, Eric Tiedemann, Mark Torrance, Randall Upham, Paul Utgoff, Peter van Beek, Hal Varian, Paulina Varshavskaya, Sunil Vemuri, Vandi Verma, Ubbo Visser, Jim Waldo, Toby Walsh, Bonnie Webber, Dan Weld, Michael Wellman, Kamin Whitehouse, Michael Dean White, Brian Williams, David Wolfe, Jason Wolfe, Bill Woods, Alden Wright, Jay Yagnik, Mark Yasuda, Richard Yen, Eliezer Yudkowsky, Weixiong Zhang, Ming Zhao, Shlomo Zilberstein e nossos estimados colegas os Revisores Anônimos. * Conteúdo em inglês.

Sobre os Autores Stuart Russell nasceu em 1962 em Portsmouth, Inglaterra. Bacharelou-se com louvor em Física pela Universidade de Oxford em 1982, e doutorou-se em Ciência da Computação por Stanford em 1986. Entrou para o corpo docente da Universidade da Califórnia, em Berkeley, onde leciona Ciência da Computação, dirige o Centro para Sistemas Inteligentes e ocupa a cátedra Smith-Zadeh de Engenharia. Em1990, recebeu o Prêmio Presidencial ao Jovem Cientista (Presidential Young InvestigatorAward), concedido pela National Science Foundation, e, em 1995, foi covencedor do Prêmio de Computação e Pensamento (Computers and Thought Award). Foi professor da cadeira Miller em 1996 na Universidade de Califórnia, e indicado para a bolsa docente Chancellor. Em 1998, foi o palestrante da Conferência Forsythe Memorial, na Universidade de Stanford. É membro efetivo da Associação Americana de Inteligência Artificial e ex-integrante do Conselho Executivo da entidade. Já publicou mais de cem artigos sobre uma ampla gama de tópicos ligados à inteligência artificial. Entre seus outros livros, incluem-se: The Use of Knowledge in Analogy and Induction e (com Eric Wefald) Do the Right Thing: Studies in Limited Rationality. Peter Norvig atualmente é diretor de Pesquisa na Google, Inc. e foi o diretor responsável pelos algoritmos de busca do núcleo da Web de 2002 até 2005. É membro efetivo da Associação Americana de Inteligência Artificial e da Associação para Máquinas de Computação. Anteriormente, foi chefe da Divisão de Ciências Computacionais no Ames Research Center, da NASA, onde supervisionou a pesquisa e o desenvolvimento da robótica e da inteligência artificial para a agência espacial americana. Antes disso, foi cientista-chefe da Junglee, onde ajudou a desenvolver um dos primeiros serviços de acesso a informações pela Internet. Bacharelou-se em matemática aplicada pela Brown University e doutorou-se em Ciência da Computação pela Universidade de Califórnia, em Berkeley. Ele recebeu os prêmios Distinguished Alumni e Engineering Innovation de Berkeley e a Exceptional Achievement Medal da NASA. Tem atuado como professor da Universidade do Sul da Califórnia e pesquisador em Berkeley. Seus outros livros são: Paradigms of AI Programming: Case Studies in Common Lisp, Verbmobil: A Translation System for Face-to-Face Dialog, e Intelligent Help Systems for UNIX.

Nota dos revisores técnicos da edição brasileira articipar do projeto editorial de um livro importante como Inteligência artificial, de Russel e Norvig, é para nós motivo de orgulho e satisfação, considerando o impacto e a importância dessa obra no ensino de inteligência artificial. A revisão técnica da tradução é atividade complexa e de grande responsabilidade, pois exige a escolha de termos para a tradução de conceitos técnicos, de forma a facilitar seu entendimento e, ao mesmo tempo, preservar sua vinculação com a forma original, simplificando com isso o acesso do leitor às fontes de conhecimento que permitam prosseguimento de seus estudos. Para garantir a qualidade da revisão técnica, cada um dos revisores se concentrou nos capítulos relacionados às suas atividades de pesquisa. Assim, a professora Liliane Nunes de Barros revisou os capítulos 2 a 6, 10, 11, 17 e 21; a Professora Renata Wassermann revisou os capítulos 7 a 9, 12, 26 e 27; e o Professor Flávio Soares Corrêa da Silva revisou os capítulos 13 a 16, 18 a 20, 22 a 25 e os Apêndices. ...