Log In
Or create an account ->
Imperial Library
Home
About
News
Upload
Forum
Help
Login/SignUp
Index
Halftitle
Artifical Intelligence
Copyright
Dedication
Contents
Preface
Acknowledgments
Credits
Part I: Introduction
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
Block’s Criticism of the Turing Test
Searle’s Criticism: The Chinese Room
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
2. Uninformed Search Intelligence
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
Algorithm: Breadth First Search
2.4.2 Implementing a Breadth First Search Solution
2.4.3 Measuring Problem-Solving Performance
Completeness
Optimality
Time Complexity
Space Complexity
2.4.4 Comparing dfs and bfs
2.5 Chapter Summary
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
The Foothills Problem
The Plateau Problem
The Ridge Problem
3.3 The Best-first Search
Abbreviations:
Abbreviations:
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 Boundwith 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
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
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
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 Search Trees
6.3.1 Decision Tree
6.4 Representational Choices
6.5 Production Systems
6.6 Object Orientation
6.7 Frames
6.8 Scripts and the Conceptual Dependency System
6.9 Semantic Networks
6.10 Associations
6.11 More Recent Approaches
6.11.1 Concept Maps
6.11.2 Conceptual Graphs
6.11.3 Baecker’s Work
6.12 Agents: Intelligent or Otherwise
6.12.1 A Little Agent History
6.12.2 Contemporary Agents
KaZaA
Monitoring Agent: Spector Pro
Zero Intelligence Plus (Zip)
HAL: The Next Generation Intelligent Room
6.12.3 The Semantic Web
6.12.4 The Future – According to IBM
6.12.5 Authors’ Perspective
6.13 Chapter Summary
7. Production Systems
7.0 Introduction
7.1 Background
7.1.1 Strong Methods vs. Weak Methods
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
Conflict Resolution Strategies
7.4.2 Forward Chaining
Examples of Forward Chaining
7.4.3 Backward Chaining
Examples of 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
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
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 More Recent 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
10. Neural Networks
10.0 Introduction
10.1 Rudiments of Artificial Neural Networks
10.2 McCulloch–Pitts Network
10.3 The Perceptron Learning Rule
10.4 The Delta Rule
10.5 Backpropagation
10.6 Implementation Concerns
10.6.1 Pattern Analysis
10.6.2 Training Methodology
10.7 Discrete Hopfield Networks
10.8 Application Areas
10.9 Chapter Summary
11. Search Inspired by Mother Nature
11.0 Introduction
11.1 Simulated Annealing
11.2 Genetic Algorithms
11.3 Genetic Programming
11.4 Tabu Search
11.5 Ant Colony Optimization
11.6 Chapter Summary
Part IV: Advanced Topics
12. Natural Language Understanding
12.0 INTRODUCTION
12.1 Overview: The Problems and Possibilities of Language
12.1.1 Ambiguity
12.2 History of Natural Language Processing (NLP)
12.2.1 Foundations (1940s and 1950s)
12.2.2 Symbolic vs. Stochastic Approaches (1957–1970)
12.2.3 The Four Paradigms: 1970–1983
12.2.4 Empiricism and Finite-State Models
12.2.5 The Field Comes Together: 1994–1999
12.2.6 The Rise of Machine Learning
12.3 Syntax and Formal Grammars
12.3.1 Types of Grammars
Type 0: Recursively Enumerable Languages
Type 1: Context Sensitive Languages
Type 2: Context-Free Languages
Type 3: Regular Languages
12.3.2 Syntactic Parsing: The CYK Algorithm
12.4 Semantic Knowledge and Extended Grammars
12.4.1 Transformational Grammar
12.4.2 Systemic Grammar
12.4.3 Case Grammars
12.4.4 Semantic Grammars
12.4.5 Schank’s Systems
MARGIE
Inference Mode
Paraphrase Mode
SAM
PAM
12.5 Statistical Methods in NLP
12.5.1 Statistical Parsing
12.5.2 Machine Translation (Revisited) and IBM’s Candide System
12.5.3 Word Sense Disambiguation
12.6 Probabilistic Models for Statistical NLP
12.6.1 Hidden Markov Models
12.6.2 The Viterbi Algorithm
12.7 Linguistic Data Collections for Statistical NLP
12.7.1 The Penn Treebank Project
12.7.2 Wordnet
12.8 Applications: Information Extraction and Question Answering Systems
12.8.1 Question Answering Systems
12.8.2 Information Extraction
12.9 Present and Future Research (according to Charniak)
12.10 Chapter Summary
13. Automated Planning
13.0 Introduction
13.1 The Problem of Planning
13.1.1 Planning Terminology
13.1.2 Examples of Planning Applications
13.2 A Brief History and a Famous Problem
13.2.1 The Frame Problem
13.3 Planning Methods
13.3.1 Planning as Search
13.3.1.1 State-Space Search
13.3.1.2 Means Ends Analysis
13.3.1.3 A Variety of Heuristic Search Methods for Planning
13.3.2 Partially Ordered Planning
13.3.2.1 The Sussman Anomaly
13.3.3 Hierarchical Planning
13.3.4 Case-Based Planning
13.3.5 A Potpourri of Planning Methods
13.4 Early Planning Systems
13.4.1 STRIPS
13.4.2 NOAH
13.4.3 NONLIN
13.5 More Modern Planning Systems
13.5.1 O-Plan
13.5.2 Graphplan
13.5.3 A Potpourri of Planning Systems
Planning Research Areas, Systems, and Techniques
13.5.4 A Planning Approach to Learning Systems
A Plan-Oriented Learning Environment for Novice Object Design
13.6 Chapter Summary
14. Advanced Computer Games
14.0 INTRODUCTION
14.1 CHECKERS: FROM SAMUEL TO SCHAEFFER
14.1.1 Heuristic Methods for Learning in the Game of Checkers
14.1.2 Rote Learning and Generalization
14.1.3 Signature Table Evaluations and Book Learning
14.1.4 World Championship Checkers with Schaeffer’s Chinook
14.1.5 Checkers is Solved
14.2 CHESS: THE DROSOPHILA OF AI
14.2.1 Historical Background of Computer Chess
14.2.2 Programming Methods
14.2.2.1 Shannon Approaches
14.2.2.2 Board and Legal Move Representation
14.2.2.3 Openings and Position Evaluation
14.2.2.4 Mobility and Connectivity
14.2.3 Beyond the Horizon
14.2.4 Deep Thought and Deep Blue against Grandmaster Competition: 1988–1995
Gary Kasparov vs. Deeper Blue
14.3 CONTRIBUTIONS OF COMPUTER CHESS TO ARTIFICIAL INTELLIGENCE
14.3.1 Search in Machines
14.3.2 Search in Man vs. Machine
14.3.3 Heuristics, Knowledge, and Problem-Solving
14.3.4 Brute Force: Knowledge vs. Search; Performance vs. Competence
14.3.5 Endgame Databases and Parallelism
14.3.6 Author Contributions
14.4 OTHER GAMES
14.4.1 Othello
14.4.2 Backgammon
14.4.3 Bridge
14.4.4 Poker
14.5 GO: THE NEW DROSOPHILA OF AI?
14.5.1 The Stars of Advanced Computer Games
14.6 Chapter Summary
Part V: The Present and Future
15.0 INTRODUCTION
15.1 RECAPITULATION—PART I
15.2 PROMETHEUS REDUX
15.3 RECAPITULATION—PART II: PRESENT AI ACCOMPLISHMENTS
15.4 IBM WATSON—JEOPARDY CHALLENGE
15.5 AI IN THE 21st CENTURY
15.6 Chapter Summary
A. Example with CLIPS:The Expert System Shell
B. Implementation of the Viterbi Algorithm for Hidden Markov Chains
C. Contributions to Computer Chess: The Amazing Walter Shawn Browne
D. Applications and Data
D.1 Examples of Applications
1. Expert Systems
2. Neural Networks
3. Robotics
4. Fuzzy Logic
D.2 Data For Neural Training Exercises
D.3 An Overview of Advanced Computer Games
1. The Rules and Objectives of Bridge
2. The Rules and Objectives of Chess
3. The History of Advanced Computer Games
E. Solutions to Selected Exercises
Index
← Prev
Back
Next →
← Prev
Back
Next →