Artificial Intelligence in the 21st Century

Cover
Half-Title
Title
Copyright
Dedication
Contents
Preface
Acknowledgments (Three Editions)
Credits for the 3rd Edition
Part I: Introduction
Chapter 1: Overview of Artificial Intelligence
1.0 Introduction
1.0.1 What is Artificial Intelligence?
1.0.2 What is Thinking? What is Intelligence?
1.1 The Turing Test
1.1.1 Definition of the Turing Test
1.1.2 Controversies and Criticisms of the Turing Test
1.2 Strong AI versus Weak AI
1.3 Heuristics
1.3.1 The Diagonal of a Rectangular Solid: Solving a Simpler, but Related Problem
1.3.2 The Water Jug Problem: Working Backward
1.4 Identifying Problems Suitable for AI
1.5 Applications and Methods
1.5.1 Search Algorithms and Puzzles
1.5.2 Two-Person Games
1.5.3 Automated Reasoning
1.5.4 Production Rules and Expert Systems
1.5.5 Cellular Automata
1.5.6 Neural Computation
1.5.7 Genetic Algorithms
1.5.8 Knowledge Representation
1.5.9 Uncertainty Reasoning
1.6 Early History of AI
1.6.1 Logicians and Logic Machines
1.7 Recent History of AI to the Present
1.7.1 Games
1.7.2 Expert Systems
1.7.3 Neural Computing
1.7.4 Evolutionary Computation
1.7.5 Natural Language Processing
1.7.6 Bioinformatics
1.8 AI in the New Millennium
1.9 Chapter Summary
Part II: Fundamentals
Chapter 2: Uninformed Search
2.0 Introduction: Search in Intelligent Systems
2.1 State-Space Graphs
2.1.1 The False Coin Problem
2.2 Generate-and-Test Paradigm
2.2.1 Backtracking
2.2.2 The Greedy Algorithm
2.2.3 The Traveling Salesperson Problem
2.3 Blind Search Algorithms
2.3.1 Depth First Search
2.3.2 Breadth First Search
2.4 Implementing and Comparing Blind Search Algorithms
2.4.1 Implementing a Depth First Search Solution
2.4.2 Implementing a Breadth First Search Solution
2.4.3 Measuring Problem-Solving Performance
2.4.4 Comparing dfs and bfs
2.5 Chapter Summary
Chapter 3: Informed Search
3.0 Introduction
3.1 Heuristics
3.2 Informed Search Algorithms (Part I) – Finding Any Solution
3.2.1 Hill Climbing
3.2.2 Steepest-Ascent Hill Climbing
3.3 The Best-First Search
3.4 The Beam Search
3.5 Additional Metrics for Search Algorithms
3.6 Informed Search (Part 2) – Finding An Optimal Solution
3.6.1 Branch and Bound
3.6.2 Branch and Bound with Underestimates
3.6.3 Branch and Bound with Dynamic Programming
3.6.4 The A* Search
3.7 Informed Search (Part 3) – Advanced Search Algorithms
3.7.1 Constraint Satisfaction Search
3.7.2 AND/OR Trees
3.7.3 The Bidirectional Search
3.8 Chapter Summary
Chapter 4: Search Using Games
4.0 Introduction
4.1 Game Trees and Minimax Evaluation
4.1.1 Heuristic Evaluation
4.1.2 Minimax Evaluation of Game Trees
4.2 Minimax with Alpha-Beta Pruning
4.3 Variations and Improvements to Minimax
4.3.1 Negamax Algorithm
4.3.2 Progressive Deepening
4.3.3 Heuristic Continuation and the Horizon Effect
4.4 Games of Chance and the Expectiminimax Algorithm
4.5 Game Theory
4.5.1 The Iterated Prisoner’s Dilemma
4.6 Chapter Summary
Chapter 5: Logic in Artificial Intelligence
5.0 Introduction
5.1 Logic and Representation
5.2 Propositional Logic
5.2.1 Propositional Logic – Basics
5.2.2 Arguments in the Propositional Logic
5.2.3 Proving Arguments in the Propositional Logic Valid – A Second Approach
5.3 Predicate Logic – Introduction
5.3.1 Unification in the Predicate Logic
5.3.2 Resolution in the Predicate Logic
5.3.3 Converting a Predicate Expression to Clause Form
5.4 Several Other Logics
5.4.1 Second Order Logic
5.4.2 Non-Monotonic Logic
5.4.3 Fuzzy Logic
5.4.4 Modal Logic
5.5 Chapter Summary
Chapter 6: Knowledge Representation
6.0 Introduction
6.1 Graphical Sketches and The Human Window
6.2 Graphs and The Bridges of Königsberg Problem
6.3 Representational Choices
6.4 Production Systems
6.5 Object Orientation
6.6 Frames
6.7 Scripts and the Conceptual Dependency System
6.8 Semantic Networks
6.9 Associations
6.10 More Recent Approaches
6.10.1 Concept Maps
6.10.2 Conceptual Graphs
6.10.3 Baecker’s Work
6.11 Agents: Intelligent or Otherwise
6.11.1 A Little Agent History
6.11.2 Contemporary Agents
6.11.3 The Semantic Web
6.11.4 The Future – According to IBM
6.11.5 Author’s Perspective
6.12 Chapter Summary
Chapter 7: Production Systems
7.0 Introduction
7.1 Background
7.2 Basic Examples
7.3 The CarBuyer System
7.3.1 Advantages of Production Systems
7.4 Production Systems and Inference Methods
7.4.1 Conflict Resolution
7.4.2 Forward Chaining
7.4.3 Backward Chaining
7.5 Production Systems and Cellular Automata
7.6 Stochastic Processes and Markov Chains
7.7 Chapter Summary
Part III: Knowledge-Based Systems
Chapter 8: Uncertainty in AI
8.0 Introduction
8.1 Fuzzy Sets
8.2 Fuzzy Logic
8.3 Fuzzy Inferences
8.4 Probability Theory and Uncertainty
8.5 Chapter Summary
Chapter 9: Expert Systems
9.0 Introduction
9.1 Background
9.1.1 Human and Machine Experts
9.2 Characteristics of Expert Systems
9.3 Knowledge Engineering
9.4 Knowledge Acquisition
9.5 Classic Expert Systems
9.5.1 Dendral
9.5.2 Mycin
9.5.3 Emycin
9.5.4 Prospector
9.5.5 Fuzzy Knowledge and Bayes’ Rule
9.6 Methods for Efficiency
9.6.1 Demon Rules
9.6.2 The Rete Algorithm
9.7 Case-Based Reasoning
9.8 Other Expert Systems
9.8.1 Systems for Improving Employment Matching
9.8.2 An Expert System for Vibration Fault Diagnosis
9.8.3 Automatic Dental Identification
9.8.4 More Expert Systems Employing Case-Based Reasoning
9.9 Chapter Summary
Chapter 10: Machine Learning : Part I Neural Networks
10.0 Introduction
10.1 Machine Learning: A Brief Overview
10.2 The Role of Feedback in Machine Learning Systems
10.3 Inductive Learning
10.4 Learning with Decision Trees
10.5 Problems Suitable for Decision Trees
10.6 Entropy
10.7 Constructing a Decision Tree With ID3
10.8 Issues Remaining
10.9 Rudiments of Artificial Neural Networks
10.10 McCulloch-Pitts Network
10.11 The Perceptron Learning Rule
10.12 The Delta Rule
10.13 Backpropagation
10.14 Implementation Concerns
10.14.1 Pattern Analysis
10.14.2 Training Methodology
10.15 Discrete Hopfield Networks
10.16 Application Areas
10.17 Chapter Summary
Chapter 11: Machine Learning : Part II Deep Learning
11.0 Introduction
11.1 Deep Learning Applications: A Brief Overview
11.2 Deep Learning Network Layers
11.3 Deep Learning Types
11.3.1 Multilayer Neural Network
11.3.2 Convolutional Neural Network (CNN)
11.3.3 Recurrent Neural Network (RNN)
11.3.4 Long Short-Term Memory Network (LSTM)
11.3.5 Recursive Neural Network (RvNN)
11.3.6 Stacked Autoencoders
11.3.7 Extreme Learning Machine (ELM)
11.4 Chapter Summary
Chapter 12: Search Inspired by Mother Nature
12.0 Introduction
12.1 Simulated Annealing
12.2 Genetic Algorithms
12.3 Genetic Programming
12.4 Tabu Search
12.5 Ant Colony Optimization
12.6 Chapter Summary
Part IV: Advanced Topics
Chapter 13: Natural Language Understanding
13.0 Introduction
13.1 Overview: The Problems and Possibilities of Language
13.1.1 Ambiguity
13.2 History of Natural Language Processing (NLP)
13.2.1 Foundations (1940s and 1950s)
13.2.2 Symbolic vs. Stochastic Approaches (1957–1970)
13.2.3 The Four Paradigms: 1970–1983
13.2.4 Empiricism and Finite-State Models
13.2.5 The Field Comes Together: 1994–1999
13.2.6 The Rise of Machine Learning
13.3 Syntax and Formal Grammars
13.3.1 Types of Grammars
13.3.2 Syntactic Parsing: The CYK Algorithm
13.4 Semantic Analysis and Extended Grammars
13.4.1 Transformational Grammar
13.4.2 Systemic Grammar
13.4.3 Case Grammars
13.4.4 Semantic Grammars
13.4.5 Schank’s Systems
13.5 Statistical Methods in NLP
13.5.1 Statistical Parsing
13.5.2 Machine Translation (Revisited) and IBM’s Candide System
13.5.3 Word Sense Disambiguation
13.6 Probabilistic Models for Statistical NLP
13.6.1 Hidden Markov Models
13.6.2 The Viterbi Algorithm
13.7 Linguistic Data Collections for Statistical NLP
13.7.1 The Penn Treebank Project
13.7.2 WordNet
13.7.3 Models of Metaphor in NLP
13.8 Applications: Information Extraction and Question Answering Systems
13.8.1 Question Answering Systems
13.8.2 Information Extraction
13.9 Present and Future Research (According to Charniak)
13.10 Speech Understanding
13.10.1 Speech Understanding Techniques
13.11 Applications of Speech Understanding
13.11.1 Dragon’s NaturallySpeaking System and Windows’ Speech Recognition System
13.11.2 CISCO’s Voice System
13.12 Chapter Summary
Chapter 14: Automated Planning
14.0 Introduction
14.1 The Problem of Planning
14.1.1 Planning Terminology
14.1.2 Examples of Planning Applications
14.2 A Brief History and a Famous Problem
14.2.1 The Frame Problem
14.3 Planning Methods
14.3.1 Planning as Search
14.3.2 Partially Ordered Planning
14.3.3 Hierarchical Planning
14.3.4 Case-Based Planning
14.3.5 A Potpourri of Planning Methods
14.4 Early Planning Systems
14.4.1 Strips
14.4.2 Noah
14.4.3 Nonlin
14.5 More Modern Planning Systems
14.5.1 O-Plan
14.5.2 Graphplan
14.5.3 A Potpourri of Planning Systems
14.5.4 A Planning Approach to Learning Systems
14.5.5 The SCI Box Automated Planner
14.6 Chapter Summary
Part V: The Present and Future
Chapter 15: Robotics
15.0 Introduction
15.1 History: Serving, Emulating, Enhancing, and Replacing Man
15.1.1 Robot Lore
15.1.2 Early Mechanical Robots
15.1.3 Robots in Film and Literature
15.1.4 Twentieth-Century Robots
15.2 Technical Issues
15.2.1 Robot Components
15.2.2 Locomotion
15.2.3 Path Planning for a Point Robot
15.2.4 Mobile Robot Kinematics
15.3 Applications: Robotics in the Twenty-First Century
15.4 Chapter Summary
Chapter 16: Advanced Computer Games
16.0 Introduction
16.1 Checkers: From Samuel to Schaeffer
16.1.1 Heuristic Methods for Learning in the Game of Checkers
16.1.2 Rote Learning and Generalization
16.1.3 Signature Table Evaluations and Book Learning
16.1.4 World Championship Checkers with Schaeffer’s Chinook
16.1.5 Checkers is Solved
16.2 Chess: The Drosophila of AI
16.2.1 Historical Background of Computer Chess
16.2.2 Programming Methods
16.2.3 Beyond the Horizon
16.2.4 Deep Thought and Deep Blue against Grandmaster Competition: 1988–1995
16.3 Contributions of Computer Chess to Artificial Intelligence
16.3.1 Search in Machines
16.3.2 Search in Man vs. Machine
16.3.3 Heuristics, Knowledge, and Problem-Solving
16.3.4 Brute Force: Knowledge vs. Search; Performance vs. Competence
16.3.5 Endgame Databases and Parallelism
16.3.6 Author Contributions
16.4 Other Games
16.4.1 Othello
16.4.2 Backgammon
16.4.3 Bridge
16.4.4 Poker
16.5 Go: The New Drosophila of AI?
16.5.1 The Stars of Advanced Computer Games
16.6 Chapter Summary
Chapter 17: Reprise
17.0 Introduction
17.1 Recapitulation—PART I
17.2 Prometheus Redux
17.3 Recapitulation—PART II: Present AI Accomplishments
17.4 IBM Watson-Jeopardy Challenge
17.5 AI in the 21st Century
17.6 Chapter Summary
Part VI: Security and Programming (Optional)
Chapter 18: Artificial Intelligence in Security (Optional)
18.0 Introduction
18.1 Internet Protocol Security (IPSec)
18.2 Security Association (SA)
18.3 Security Policies
18.3.1 Security Policy Database (SPD)
18.3.2 Security Association Selectors (SA Selectors)
18.3.3 Combining of Security Associations
18.3.4 IPSec Protocol Modes
18.3.5 Anti-Replay Window
18.4 Secure Electronic Transactions
18.4.1 Business Requirements of SET
18.5 Intruders
18.6 Intrusion Detection
18.6.1 Intrusion Detection Techniques
18.7 Malicious Programs
18.7.1 Different Phases in the Lifetime of a Virus
18.8 Anti-Virus Scanners
18.8.1 Different Generations of Anti-Virus Scanners
18.9 Worms
18.10 Firewalls
18.10.1 Firewall Characteristics
18.10.2 Firewall Techniques to Control Access
18.10.3 Types of Firewalls
18.11 Trusted Systems
18.12 Chapter Summary
Chapter 19: Artificial Intelligence Programming Tools (Optional)
19.1 Programming in Logic (Prolog)
19.1.1 Differences between C/C++ and Prolog
19.1.2 How Does Prolog Work?
19.1.3 Milestones in Prolog Language Development
19.1.4 Clauses
19.1.5 Robinson’s Resolution Rule
19.1.6 Parts of a Prolog Program
19.1.7 Queries to a Database
19.1.8 How Does Prolog Solve a Query?
19.1.9 Compound Queries
19.1.10 The _ Variable
19.1.11 Recursion in Prolog
19.1.12 Data Structures in Prolog
19.1.13 Head and Tail of a List
19.1.14 Print all the Members of the List
19.1.15 Print the List in Reverse Order
19.1.16 Appending a List
19.1.17 Find Whether the Given Item is a Member of the List
19.1.18 Finding the Length of the List
19.1.19 Controlling Execution in Prolog
19.1.20 Cut Predicate
19.1.21 About Turbo Prolog
19.2 Python
19.2.1 Running Python
19.2.2 Pitfalls
19.2.3 Features of Python
19.2.4 Functions as Rst-Class Objects
19.2.5 Useful Libraries
19.2.6 Utilities
19.2.7 Testing Code
19.3 MATLAB
19.3.1 Getting Started and Windows of MATLAB
19.3.2 Using MATLAB in Calculations
19.3.3 Plotting
19.3.4 Symbolic Computation
19.3.5 MATLAB for Python Users
Appendices
Appendix A. Example with CLIPS: The Expert System Shell
Appendix B. Implementation of the Viterbi Algorithm for Hidden Markov Chains
Appendix C. The Amazing Walter Shawn Browne
Appendix D. Applications and Data
Appendix E. Solutions to Selected Odd Exercises
Index