Introduction to Artificial Intelligence

Description

内容简介 · · · · · · This concise and accessible textbook supports a foundation or module course on A.I., covering a broad selection of the subdisciplines within this field. The book presents concrete algorithms and applications in the areas of agents, logic, search, reasoning under uncertainty, machine learning, neural networks and reinforcement learning. Topics and features: presents an application-focused and hands-on approach to learning the subject; provides study exercises of varying degrees of difficulty at the end of each chapter, with solutions given at the end of the book; supports the text with highlighted examples, definitions, and theorems; includes chapters on predicate logic, PROLOG, heuristic search, probabilistic reasoning, machine learning and data mining, neural networks and reinforcement learning; contains an extensive bibliography for deeper reading on further topics; supplies additional teaching resources, including lecture slides and training data for learning algorithms, at an associated website. Cover Undergraduate Topics in Computer Science Introduction to Artificial Intelligence ISBN 9780857292988 Preface Contents Chapter 1: Introduction 1.1 What Is Artificial Intelligence? 1.1.1 Brain Science and Problem Solving 1.1.2 The Turing Test and Chatterbots 1.2 The History of AI 1.2.1 The First Beginnings 1.2.2 Logic Solves (Almost) All Problems 1.2.3 The New Connectionism 1.2.4 Reasoning Under Uncertainty 1.2.5 Distributed, Autonomous and Learning Agents 1.2.6 AI Grows up 1.3 Agents 1.4 Knowledge-Based Systems 1.5 Exercises Chapter 2: Propositional Logic 2.1 Syntax 2.2 Semantics 2.3 Proof Systems 2.4 Resolution 2.5 Horn Clauses 2.6 Computability and Complexity 2.7 Applications and Limitations 2.8 Exercises Chapter 3: First-order Predicate Logic 3.1 Syntax 3.2 Semantics 3.2.1 Equality 3.3 Quantifiers and Normal Forms 3.4 Proof Calculi 3.5 Resolution 3.5.1 Resolution Strategies 3.5.2 Equality 3.6 Automated Theorem Provers 3.7 Mathematical Examples 3.8 Applications 3.9 Summary 3.10 Exercises Chapter 4: Limitations of Logic 4.1 The Search Space Problem 4.2 Decidability and Incompleteness 4.3 The Flying Penguin 4.4 Modeling Uncertainty 4.5 Exercises Chapter 5: Logic Programming with PROLOG 5.1 PROLOG Systems and Implementations 5.2 Simple Examples 5.3 Execution Control and Procedural Elements 5.4 Lists 5.5 Self-modifying Programs 5.6 A Planning Example 5.7 Constraint Logic Programming 5.8 Summary 5.9 Exercises Chapter 6: Search, Games and Problem Solving 6.1 Introduction 6.2 Uninformed Search 6.2.1 Breadth-First Search Analysis 6.2.2 Depth-First Search Analysis 6.2.3 Iterative Deepening Analysis 6.2.4 Comparison 6.3 Heuristic Search 6.3.1 Greedy Search 6.3.2 A-Search 6.3.3 IDA-Search 6.3.4 Empirical Comparison of the Search Algorithms 6.3.5 Summary 6.4 Games with Opponents 6.4.1 Minimax Search 6.4.2 Alpha-Beta-Pruning Complexity 6.4.3 Non-deterministic Games 6.5 Heuristic Evaluation Functions 6.5.1 Learning of Heuristics 6.6 State of the Art 6.7 Exercises Chapter 7: Reasoning with Uncertainty 7.1 Computing with Probabilities 7.1.1 Conditional Probability Chain Rule Marginalization Bayes' Theorem 7.2 The Principle of Maximum Entropy 7.2.1 An Inference Rule for Probabilities 7.2.2 Maximum Entropy Without Explicit Constraints 7.2.3 Conditional Probability Versus Material Implication 7.2.4 MaxEnt-Systems 7.2.5 The Tweety Example 7.3 Lexmed, an Expert System for Diagnosing Appendicitis 7.3.1 Appendicitis Diagnosis with Formal Methods 7.3.2 Hybrid Probabilistic Knowledge Base 7.3.3 Application of Lexmed 7.3.4 Function of Lexmed Learning of Rules by Statistical Induction Determining the Dependency Graph Estimating the Rule Probabilities Expert Rules Diagnosis Queries 7.3.5 Risk Management Using the Cost Matrix Cost Matrix in the Binary Case 7.3.6 Performance 7.3.7 Application Areas and Experiences 7.4 Reasoning with Bayesian Networks 7.4.1 Independent Variables 7.4.2 Graphical Representation of Knowledge as a Bayesian Network 7.4.3 Conditional Independence 7.4.4 Practical Application 7.4.5 Software for Bayesian Networks 7.4.6 Development of Bayesian Networks Lexmed as a Bayesian Network Causality and Network Structure 7.4.7 Semantics of Bayesian Networks 7.5 Summary 7.6 Exercises Chapter 8: Machine Learning and Data Mining What Is Learning? The Learning Agent What Is Data Mining? 8.1 Data Analysis 8.2 The Perceptron, a Linear Classifier 8.2.1 The Learning Rule 8.2.2 Optimization and Outlook 8.3 The Nearest Neighbor Method 8.3.1 Two Classes, Many Classes, Approximation 8.3.2 Distance Is Relevant 8.3.3 Computation Times 8.3.4 Summary and Outlook 8.3.5 Case-Based Reasoning 8.4 Decision Tree Learning 8.4.1 A Simple Example 8.4.2 Entropy as a Metric for Information Content 8.4.3 Information Gain 8.4.4 Application of C4.5 8.4.5 Learning of Appendicitis Diagnosis 8.4.6 Continuous Attributes 8.4.7 Pruning-Cutting the Tree 8.4.8 Missing Values 8.4.9 Summary 8.5 Learning of Bayesian Networks 8.5.1 Learning the Network Structure 8.6 The Naive Bayes Classifier Estimation of Probabilities 8.6.1 Text Classification with Naive Bayes 8.7 Clustering 8.7.1 Distance Metrics 8.7.2 k-Means and the EM Algorithm 8.7.3 Hierarchical Clustering 8.8 Data Mining in Practice 8.8.1 The Data Mining Tool KNIME 8.9 Summary 8.10 Exercises 8.10.1 Introduction 8.10.2 The Perceptron 8.10.3 Nearest Neighbor Method 8.10.4 Decision Trees 8.10.5 Learning of Bayesian Networks 8.10.6 Clustering 8.10.7 Data Mining Chapter 9: Neural Networks 9.1 From Biology to Simulation 9.1.1 The Mathematical Model 9.2 Hopfield Networks 9.2.1 Application to a Pattern Recognition Example 9.2.2 Analysis 9.2.3 Summary and Outlook 9.3 Neural Associative Memory 9.3.1 Correlation Matrix Memory 9.3.2 The Pseudoinverse 9.3.3 The Binary Hebb Rule 9.3.4 A Spelling Correction Program 9.4 Linear Networks with Minimal Errors 9.4.1 Least Squares Method 9.4.2 Application to the Appendicitis Data 9.4.3 The Delta Rule 9.4.4 Comparison to the Perceptron 9.5 The Backpropagation Algorithm 9.5.1 NETtalk: A Network Learns to Speak 9.5.2 Learning of Heuristics for Theorem Provers 9.5.3 Problems and Improvements 9.6 Support Vector Machines 9.7 Applications 9.8 Summary and Outlook 9.9 Exercises 9.9.1 From Biology to Simulation 9.9.2 Hopfield Networks 9.9.3 Linear Networks with Minimal Errors 9.9.4 Backpropagation 9.9.5 Support Vector Machines Chapter 10: Reinforcement Learning 10.1 Introduction 10.2 The Task 10.3 Uninformed Combinatorial Search 10.4 Value Iteration and Dynamic Programming 10.5 A Learning Walking Robot and Its Simulation 10.6 Q-Learning 10.6.1 Q-Learning in a Nondeterministic Environment 10.7 Exploration and Exploitation 10.8 Approximation, Generalization and Convergence 10.9 Applications 10.10 Curse of Dimensionality 10.11 Summary and Outlook 10.12 Exercises Chapter 11: Solutions for the Exercises 11.1 Introduction 11.2 Propositional Logic 11.3 First-Order Predicate Logic 11.4 Limitations of Logic 11.5 PROLOG 11.6 Search, Games and Problem Solving 11.7 Reasoning with Uncertainty 11.8 Machine Learning and Data Mining 11.9 Neural Networks 11.10 Reinforcement Learning References Index