Artificial Intelligence: Structures and Strategies for Complex Problem Solving (6th Edition)

Artificial Intelligence: Structures and Strategies for Complex Problem Solving is ideal for a one- or two-semester undergraduate course on AI.In this accessible, comprehensive text, George Luger captures the essence of artificial intelligence–solving the complex problems that arise wherever computer technology is applied. Ideal for an undergraduate course in AI, the Sixth Edition presents the fundamental concepts of the discipline first then goes into detail with the practical information necessary to implement the algorithms and strategies discussed. Readers learn how to use a number of different software tools and techniques to address the many challenges faced by today’s computer scientists. Cover 1 Title Page 4 Copyright 5 Preface 8 Publisher’s Acknowledgements 17 Contents 20 PART I: ARTIFICIAL INTELLIGENCE: ITS ROOTS AND SCOPE 26 1 AI: HISTORY AND APPLICATIONS 28 1.1 From Eden to ENIAC: Attitudes toward Intelligence, Knowledge, and Human Artifice 28 1.2 Overview of AI Application Areas 45 1.3 Artificial Intelligence—A Summary 55 1.4 Epilogue and References 56 1.5 Exercises 58 PART II: ARTIFICIAL INTELLIGENCE AS REPRESENTATION AND SEARCH 60 2 THE PREDICATE CALCULUS 70 2.0 Introduction 70 2.1 The Propositional Calculus 70 2.2 The Predicate Calculus 75 2.3 Using Inference Rules to Produce Predicate Calculus Expressions 87 2.4 Application: A Logic-Based Financial Advisor 98 2.5 Epilogue and References 102 2.6 Exercises 102 3 STRUCTURES AND STRATEGIES FOR STATE SPACE SEARCH 104 3.0 Introduction 104 3.1 Graph Theory 107 3.2 Strategies for State Space Search 118 3.3 Using the State Space to Represent Reasoning with the Predicate Calculus 132 3.4 Epilogue and References 146 3.5 Exercises 146 4 HEURISTIC SEARCH 148 4.0 Introduction 148 4.1 Hill Climbing and Dynamic Programming 152 4.2 The Best-First Search Algorithm 158 4.3 Admissibility, Monotonicity, and Informedness 170 4.4 Using Heuristics in Games 175 4.5 Complexity Issues 182 4.6 Epilogue and References 186 4.7 Exercises 187 5 STOCHASTIC METHODS 190 5.0 Introduction 190 5.1 The Elements of Counting 192 5.2 Elements of Probability Theory 195 5.3 Applications of the Stochastic Methodology 207 5.4 Bayes’ Theorem 211 5.5 Epilogue and References 215 5.6 Exercises 216 6 CONTROL AND IMPLEMENTATION OF STATE SPACE SEARCH 218 6.0 Introduction 218 6.1 Recursion-Based Search 219 6.2 Production Systems 225 6.3 The Blackboard Architecture for Problem Solving 242 6.4 Epilogue and References 244 6.5 Exercises 245 PART III: CAPTURING INTELLIGENCE: THE AI CHALLENGE 248 7 KNOWLEDGE REPRESENTATION 252 7.0 Issues in Knowledge Representation 252 7.1 A Brief History of AI Representational Systems 253 7.2 Conceptual Graphs: A Network Language 273 7.3 Alternative Representations and Ontologies 283 7.4 Agent Based and Distributed Problem Solving 290 7.5 Epilogue and References 295 7.6 Exercises 298 8 STRONG METHOD PROBLEM SOLVING 302 8.0 Introduction 302 8.1 Overview of Expert System Technology 304 8.2 Rule-Based Expert Systems 311 8.3 Model-Based, Case Based, and Hybrid Systems 323 8.4 Planning 339 8.5 Epilogue and References 354 8.6 Exercises 356 9 REASONING IN UNCERTAIN SITUATIONS 358 9.0 Introduction 358 9.1 Logic-Based Abductive Inference 360 9.2 Abduction: Alternatives to Logic 375 9.3 The Stochastic Approach to Uncertainty 388 9.4 Epilogue and References 404 9.5 Exercises 406 PART IV: MACHINE LEARNING 410 10 MACHINE LEARNING: SYMBOL-BASED 412 10.0 Introduction 412 10.1 A Framework for Symbol-based Learning 415 10.2 Version Space Search 421 10.3 The ID3 Decision Tree Induction Algorithm 433 10.4 Inductive Bias and Learnability 442 10.5 Knowledge and Learning 447 10.6 Unsupervised Learning 458 10.7 Reinforcement Learning 467 10.8 Epilogue and References 474 10.9 Exercises 475 11 MACHINE LEARNING: CONNECTIONIST 478 11.0 Introduction 478 11.1 Foundations for Connectionist Networks 480 11.2 Perceptron Learning 483 11.3 Backpropagation Learning 492 11.4 Competitive Learning 499 11.5 Hebbian Coincidence Learning 509 11.6 Attractor Networks or “Memories” 520 11.7 Epilogue and References 530 11.8 Exercises 531 12 MACHINE LEARNING: GENETIC AND EMERGENT 532 12.0 Genetic and Emergent Models of Learning 532 12.1 The Genetic Algorithm 534 12.2 Classifier Systems and Genetic Programming 544 12.3 Artificial Life and Society-Based Learning 555 12.4 Epilogue and References 566 12.5 Exercises 567 13 MACHINE LEARNING: PROBABILISTIC 568 13.0 Stochastic and Dynamic Models of Learning 568 13.1 Hidden Markov Models (HMMs) 569 13.2 Dynamic Bayesian Networks and Learning 579 13.3 Stochastic Extensions to Reinforcement Learning 589 13.4 Epilogue and References 593 13.5 Exercises 595 PART V: ADVANCED TOPICS FOR AI PROBLEM SOLVING 598 14 AUTOMATED REASONING 600 14.0 Introduction to Weak Methods in Theorem Proving 600 14.1 The General Problem Solver and Difference Tables 601 14.2 Resolution Theorem Proving 607 14.3 PROLOG and Automated Reasoning 628 14.4 Further Issues in Automated Reasoning 634 14.5 Epilogue and References 642 14.6 Exercises 642 15 UNDERSTANDING NATURAL LANGUAGE 644 15.0 The Natural Language Understanding Problem 644 15.1 Deconstructing Language: An Analysis 647 15.2 Syntax 650 15.3 Transition Network Parsers and Semantics 658 15.4 Stochastic Tools for Language Understanding 674 15.5 Natural Language Applications 683 15.6 Epilogue and References 691 15.7 Exercises 692 PART VI: EPILOGUE 696 16 ARTIFICIAL INTELLIGENCE AS EMPIRICAL ENQUIRY 698 16.0 Introduction 698 16.1 Artificial Intelligence: A Revised Definition 700 16.2 The Science of Intelligent Systems 713 16.3 AI: Current Challanges and Future Directions 723 16.4 Epilogue and References 728 Bibliography 730 Author Index 760 A 760 B 760 C 761 D 761 E 761 F 761 G 762 H 762 I 762 J 763 K 763 L 763 M 763 N 764 O 764 P 764 Q 765 R 765 S 765 T 766 U 766 V 766 W 766 X 766 Y 766 Z 766 Subject Index 768 A 768 B 769 C 769 D 770 E 771 F 771 G 771 H 772 I 773 J 773 K 773 L 773 M 773 N 775 O 775 P 776 Q 777 R 777 S 777 T 778 U 778 V 778 W 778 X 779

Artificial Intelligence

Structures and Strategies for Complex Problem Solving, Sixth Edition

by George F Luger

This accessible, comprehensive book captures the essence of artificial intelligence -- solving the complex problems that arise wherever computer technology is applied. With his signature enthusiasm, George Luger demonstrates numerous techniques and strategies for addressing the many challenges facing computer scientists today. Diverse topics on this exciting and ever-evolving field range from perception and adaptation using neural networks and genetic algorithms, intelligent agents with ontologies, automated reasoning, natural language analysis, and stochastic approaches to machine learning.

This book is ideal for a one - or two-semester university course on AI.

New to this edition:

• A new chapter on stochastic approaches to machine learning, including first-prder Bayesian networks, variants of hidden Markov models, inference with Markov random fields and loopy belief propagation.
• Presentation of parameter fitting with expectation maximization learning and structure learning using Markov chain Monte Carlo sampling. Use of Markov decision processes in reinforcement learning.
• Presentation of agent technology and the use of ontologies.
• Natural language processing with dynamic programming (the Earley parser) and other probabilistic parsing techniques including Viterbi.
• A new supplemental programming book is available: AI Algorithms in Prolog, Lisp, and JavaTM. Available online and in print, this book demonstrates these languages as tools for building many of the algorithms presented throughout Luger's AI book.

"There are many ideas in this area that students often find difficult; the clarity and precision of Luger's exposition is informed by sharp, incisive examples with straightforward graphical components."

-- Joseph Lewis, San Diego State University

"The book is a perfect complement to an AI course. It gives readers both an historical point of view and a practical guide to all the techniques. It is THE book I would recommend as an introduction to this field."

-- Pascal Rebreyend, Dalarna University

"The style of writing and comprehensive treatment of the subject matter makes this a valuable addition to the AI literature."

-- Malachy Eaton, University of Limerick

George Luger is currently a Professor of Computer Science, Linguistics, and Psychology at the University of New Mexico. He received his Ph.D. from the University of Pennsylvania and spent five years researching and teaching at the Department of Artificial Intelligence at the University of Edinburgh.

In this accessible, comprehensive text, George Luger captures the essence of artificial intelligence-solving the complex problems that arise wherever computer technology is applied. Key representation techniques including logic, semantic and connectionist networks, graphical models, and many more are introduced. Presentation of agent technology and the use of ontologies are added. A new machine-learning chapter is based on stochastic methods, including first-order Bayesian networks, variants of hidden Markov models, inference with Markov random fields and loopy belief propagation. A new presentation of parameter fitting with expectation maximization learning and structure learning using Markov chain Monte Carlo sampling. Use of Markov decision processes in reinforcement learning. Natural language processing with dynamic programming (the Earley parser) and other probabilistic parsing techniques including Viterbi, are added. A new supplemental programming book is available online and in print: "AI Algorithms in Prolog, Lisp and Java (TM). "References and citations are updated throughout the Sixth Edition. For all readers interested in artificial intelligence "Artificial Intelligence: Structures and Strategies for Complex Problem Solving is ideal for a one or two semester university course on AI, as well as an invaluable reference for researchers in the field or practitioners wishing to employ the power of current AI techniques in their work."--BOOK JACKET.