人工智能简介（Springer 2011）Artificial Intelligence, Introduction (Springer 2011).doc

Wolfgang ErtelIntroduction to Artificial IntelligenceTranslated by Nathanael Black With illustrations by Florian MastProf. Dr. Wolfgang ErtelFB Elektrotechnik und InformatikHochschule Ravensburg-WeingartenUniversity of Applied SciencesWeingartenGermanyertelhs-weingarten.deSeries editorIan MackieAdvisory boardSamson Abramsky, University of Oxford, Oxford, UKKarin Breitman, Pontifical Catholic University of Rio de Janeiro, Rio de Janeiro, Brazil Chris Hankin, Imperial College London, London, UK Dexter Kozen, Cornell University, Ithaca, USAAndrew Pitts, University of Cambridge, Cambridge, UKHanne Riis Nielson, Technical University of Denmark, Kongens Lyngby, Denmark Steven Skiena, Stony Brook University, Stony Brook, USA Iain Stewart, University of Durham, Durham, UKISSN 1863-7310ISBN 978-0-85729-298-8 e-ISBN 978-0-85729-299-5 DOI 10.1007/978-0-85729-299-5Springer London Dordrecht Heidelberg New YorkBritish Library Cataloguing in Publication DataA catalogue record for this book is available from the British LibraryLibrary of Congress Control Number: 2011923216Originally published in the German language by Vieweg+Teubner, 65189 Wiesbaden, Germany, as “Ertel, Wolfgang: Grundkurs Künstliche Intelligenz. 2. rev. edition”. © Vieweg+Teubner | GWV Fachverlage GmbH, Wiesbaden 2009© Springer-Verlag London Limited 2011Apart from any fair dealing for the purposes of research or private study, or criticism or review, as per-mitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publish-ers, or in the case of reprographic reproduction in accordance with the terms of licenses issued by the Copyright Licensing Agency. Enquiries concerning reproduction outside those terms should be sent to the publishers.The use of registered names, trademarks, etc., in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant laws and regulations and therefore free for general use.The publisher makes no representation, express or implied, with regard to the accuracy of the information contained in this book and cannot accept any legal responsibility or liability for any errors or omissions that may be made.Printed on acid-free paperSpringer is part of Springer Science+Business Media ()PrefaceArtificial Intelligence (AI) has the definite goal of understanding intelligence and building intelligent systems. However, the methods and formalisms used on the way to this goal are not firmly set, which has resulted in AI consisting of a multitude of subdisciplines today. The difficulty in an introductory AI course lies in conveying as many branches as possible without losing too much depth and precision.Russell and Norvigs book RN10 is more or less the standard introduction into AI. However, since this book has 1,152 pages, and since it is too extensive and costly for most students, the requirements for writing this book were clear: it should be an accessible introduction to modern AI for self-study or as the foundation of a four-hour lecture, with at most 300 pages. The result is in front of you.In the space of 300 pages, a field as extensive as AI cannot be fully covered. To avoid turning the book into a table of contents, I have attempted to go into some depth and to introduce concrete algorithms and applications in each of the following branches: agents, logic, search, reasoning with uncertainty, machine learning, and neural networks.The fields of image processing, fuzzy logic, and natural language processing are not covered in detail. The field of image processing, which is important for all of computer science, is a stand-alone discipline with very good textbooks, such as GW08. Natural language processing has a similar status. In recognizing and gen-erating text and spoken language, methods from logic, probabilistic reasoning, and neural networks are applied. In this sense this field is part of AI. On the other hand, computer linguistics is its own extensive branch of computer science and has much in common with formal languages. In this book we will point to such appropriate systems in several places, but not give a systematic introduction. For a first introduc-tion in this field, we refer to Chaps. 22 and 23 in RN10. Fuzzy logic, or fuzzy set theory, has developed into a branch of control theory due to its primary application in automation technology and is covered in the corresponding books and lectures. Therefore we will forego an introduction here.The dependencies between chapters of the book are coarsely sketched in the graph shown below. To keep it simple, Chap. 1, with the fundamental introduc-tion for all further chapters, is left out. As an example, the thicker arrow from 2 to 3 means that propositional logic is a prerequisite for understanding predicate logic. The thin arrow from 9 to 10 means that neural networks are helpful for un-derstanding reinforcement learning, but not absolutely necessary. Thin backwardvviPrefacearrows should make clear that later chapters can give more depth of understanding to topics which have already been learned.This book is applicable to students of computer science and other technical natural sciences and, for the most part, requires high school level knowledge of mathemat-ics. In several places, knowledge from linear algebra and multidimensional analysis is needed. For a deeper understanding of the contents, actively working on the ex-ercises is indispensable. This means that the solutions should only be consulted after intensive work with each problem, and only to check ones solutions, true to Leonardo da Vincis motto “Study without devotion damages the brain”. Somewhat more difficult problems are marked with , and especially difficult ones with . Problems which require programming or special computer science knowledge are labeled with .On the books web site at www.hs-weingarten.de/ertel/aibook digital materi-als for the exercises such as training data for learning algorithms, a page with refer-ences to AI programs mentioned in the book, a list of links to the covered topics, a clickable list of the bibliography, an errata list, and presentation slides for lecturers can be found. I ask the reader to please send suggestions, criticisms, and tips about errors directly to ertelhs-weingarten.de.This book is an updated translation of my German book “Grundkurs Künstliche Intelligenz” published by Vieweg Verlag. My special thanks go to the translator Nathan Black who in an excellent trans-Atlantic cooperation between Germany and California via SVN, Skype and Email produced this text. I am grateful to Franz Kur-feß, who introduced me to Nathan; to Matthew Wight for proofreading the translated book and to Simon Rees from Springer Verlag for his patience.I would like to thank my wife Evelyn for her support and patience during this time consuming project. Special thanks go to Wolfgang Bibel and Chris Loben-schuss, who carefully corrected the German manuscript. Their suggestions and dis-cussions lead to many improvements and additions. For reading the corrections and other valuable services, I would like to thank Richard Cubek, Celal Döven, Joachim Feßler, Nico Hochgeschwender, Paul Kirner, Wilfried Meister, Norbert Perk, Pe-ter Radtke, Markus Schneider, Manfred Schramm, Uli Stärk, Michel Tokic, Arne Usadel and all interested students. My thanks also go out to Florian Mast for the priceless cartoons and very effective collaboration.I hope that during your studies this book will help you share my fascination with Artificial Intelligence.RavensburgFebruary 2011Wolfgang ErtelContents1Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.1What Is Artificial Intelligence? . . . . . . . . . . . . . . . . . .11.1.1Brain Science and Problem Solving . . . . . . . . . . . .31.1.2The Turing Test and Chatterbots . . . . . . . . . . . . . .41.2The History of AI . . . . . . . . . . . . . . . . . . . . . . . . .51.2.1The First Beginnings . . . . . . . . . . . . . . . . . . . .51.2.2Logic Solves (Almost) All Problems . . . . . . . . . . .61.2.3The New Connectionism . . . . . . . . . . . . . . . . . .71.2.4Reasoning Under Uncertainty . . . . . . . . . . . . . . .71.2.5Distributed, Autonomous and Learning Agents . . . . . .81.2.6AI Grows up . . . . . . . . . . . . . . . . . . . . . . . .91.3Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .91.4Knowledge-Based Systems . . . . . . . . . . . . . . . . . . . .121.5Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .142Propositional Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . .152.1Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .152.2Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .162.3Proof Systems . . . . . . . . . . . . . . . . . . . . . . . . . . .182.4Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . .222.5Horn Clauses . . . . . . . . . . . . . . . . . . . . . . . . . . . .252.6Computability and Complexity . . . . . . . . . . . . . . . . . .282.7Applications and Limitations . . . . . . . . . . . . . . . . . . .292.8Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .293First-order Predicate Logic . . . . . . . . . . . . . . . . . . . . . . .313.1Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .323.2Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .333.2.1Equality . . . . . . . . . . . . . . . . . . . . . . . . . .363.3Quantifiers and Normal Forms . . . . . . . . . . . . . . . . . . .373.4Proof Calculi . . . . . . . . . . . . . . . . . . . . . . . . . . . .403.5Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . .423.5.1Resolution Strategies . . . . . . . . . . . . . . . . . . . .463.5.2Equality . . . . . . . . . . . . . . . . . . . . . . . . . .463.6Automated Theorem Provers . . . . . . . . . . . . . . . . . . . .47viiviiiContents3.7Mathematical Examples . . . . . . . . . . . . . . . . . . .483.8Applications . . . . . . . . . . . . . . . . . . . . . . . . .513.9Summary . . . . . . . . . . . . . . . . . . . . . . . . . . .543.10Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . .544Limitations of Logic . . . . . . . . . . . . . . . . . . . . . . . .574.1The Search Space Problem . . . . . . . . . . . . . . . . . . .574.2Decidability and Incompleteness . . . . . . . . . . . . . . . .594.3The Flying Penguin . . . . . . . . . . . . . . . . . . . . .604.4Modeling Uncertainty . . . . . . . . . . . . . . . . . . . .634.5Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . .655Logic Programming with PROLOG. . . . . . . . . . . . . . . .675.1PROLOG Systems and Implementations . . . . . . . . . . .685.2Simple Examples . . . . . . . . . . . . . . . . . . . . . . .685.3Execution Control and Procedural Elements . . . . . . . . . .715.4Lists. . . . . . . . . . . . . . . . . . . . . . . . . . . . .735.5Self-modifying Programs . . . . . . . . . . . . . . . . . .755.6A Planning Example . . . . . . . . . . . . . . . . . . . . .765.7Constraint Logic Programming. . . . . . . . . . . . . . . .775.8Summary . . . . . . . . . . . . . . . . . . . . . . . . . . .795.9Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . .806Search, Games and Problem Solving . . . . . . . . . . . . . . . .836.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . .836.2Uninformed Search . . . . . . . . . . . . . . . . . . . . . .896.2.1Breadth-First Search . . . . . . . . . . . . . . . . .896.2.2Depth-First Search . . . . . . . . . . . . . . . . . .916.2.3Iterative Deepening . . . . . . . . . . . . . . . . .926.2.4Comparison . . . . . . . . . . . . . . . . . . . . .946.3Heuristic Search . . . . . . . . . . . . . . . . . . . . . . .946.3.1Greedy Search . . . . . . . . . . . . . . . . . . . .966.3.2A -Search . . . . . . . . . . . . . . . . . . . . . .986.3.3IDA -Search . . . . . . . . . . . . . . . . . . . . .1006.3.4Empirical Comparison of the Search Algorithms. . . . . 1006.3.5Summary . . . . . . . . . . . . . . . . . . . . . . .1026.4Games with Opponents . . . . . . . . . . . . . . . . . . . .1026.4.1Minimax Search . . . . . . . . . . . . . . . . . . .1036.4.2Alpha-Beta-Pruning . . . . . . . . . . . . . . . . .1036.4.3Non-deterministic Games . . . . . . . . . . . . . . .1066.5Heuristic Evaluation Functions. . . . . . . . . . . . . . . .1066.5.1Learning of Heuristics. . . . . . . . . . . . . . . . .1076.6State of the Art . . . . . . . . . . . . . . . . . . . . . . . .1086.7Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . .1107Reasoning with Uncertainty . . . . . . . . . . . . . . . . . . . .1137.1Computing with Probabilities. . . . . . . . . . . . . . . . .115Contentsix7.1.1Conditional Probability . . . . . . . . . . . . . . . . . .1187.2The Principle of Maximum Entropy . . . . . . . . . . . . . . . .1227.2.1An Inference Rule for Probabilities . . . . . . . . . . . .1237.2.2Maximum Entropy Without Explicit Constraints . . . . .1277.2.3Conditional Probability Versus Material Implication . . .1287.2.4MaxEnt-Systems . . . . . . . . . . . . . . . . . . . . . .1297.2.5The Tweety Example . . . . . . . . . . . . . . . . . . . .1307.3LEXMED, an Expert System for Diagnosing Appendicitis . . . .1317.3.1Appendicitis Diagnosis with Formal Methods . . . . . . .1317.3.2Hybrid Probabilistic Knowledge Base . . . . . . . . . . .1327.3.3Application of LEXMED