Contents

I Representations and Methods

1 The Intelligent Computer

• The Field and the Book
  • This Book Has Three Parts
  • The Long-Term Applications Stagger the Imagination
  • The Near-Term Applications Involve New Opportunities
  • Artificial Intelligence Sheds New Light on Traditional Questions
  • Artificial Intelligence Helps Us to Become More Intelligent
• What Artificial Intelligence Can Do
  • Intelligent Systems Can Help Experts to Solve Difficult Analysis Problems
  • Intelligent Systems Can Help Experts to Design New Devices
  • Intelligent Systems Can Learn from Examples
  • Intelligent Systems Can Provide Answers to English Questions Using both Structured Data and Free Text
  • Artificial Intelligence Is Becoming Less Conspicuous, yet More Essential
• Criteria for Success
• Summary
• Background

2 Semantic Nets and Description Matching

• Semantic Nets
  • Good Representations Are the Key to Good Problem Solving
  • Good Representations Support Explicit, Constraint-Exposing Description
  • A Representation Has Four Fundamental Parts
  • Semantic Nets Convey Meaning
  • There Are Many Schools of Thought About the Meaning of Semantics
  • Theoretical Equivalence Is Different from Practical Equivalence
• The Describe-and-Match Method
  • Feature-Based Object Identification Illustrates Describe and Match
• The Describe-and-Match Method and Analogy Problems
  • Geometric Analogy Rules Describe Object Relations and Object Transformations
  • Scoring Mechanisms Rank Answers
  • Ambiguity Complicates Matching
  • Good Representation Supports Good Performance
• The Describe-and-Match Method and Recognition of Abstractions
  • Story Plots Can Be Viewed as Combinations of Mental States and Events
  • Abstraction-Unit Nets Enable Summary
  • Abstraction Units Enable Question Answering
  • Abstraction Units Make Patterns Explicit
• Problem Solving and Understanding Knowledge
• Summary
• Background

3 Generate and Test, Means-Ends Analysis, and Problem Reduction

• The Generate-and-Test Method
  • Generate-and-Test Systems Often Do Identification
  • Good Generators Are Complete, Nonredundant, and Informed
• The Means-Ends Analysis Method
  • The Key Idea in Means-Ends Analysis Is to Reduce Differences
  • Dendral Analyzes Mass Spectrograms
  • Difference-Procedure Tables Often Determine the Means
• The Problem-Reduction Method
  • Moving Blocks Illustrates Problem Reduction
  • The Key Idea in Problem Reduction Is to Explore a Goal Tree
  • Goal Trees Can Make Procedure Interaction Transparent
  • Goal Trees Enable Introspective Question Answering
  • Problem Reduction Is Ubiquitous in Programming
  • Problem-Solving Methods Often Work Together
  • Mathematics Toolkits Use Problem Reduction to Solve Calculus Problems
• Summary
• Background

4 Nets and Basic Search

• Blind Methods
  • Net Search Is Really Tree Search
  • Search Trees Explode Exponentially
  • Depth-First Search Dives into the Search Tree
  • Breadth-First Search Pushes Uniformly into the Search Tree
  • The Right Search Depends on the Tree
  • Nondeterministic Search Moves Randomly into the Search Tree
• Heuristically Informed Methods
  • Quality Measurements Turn Depth-First Search into Hill Climbing
  • Foothills, Plateaus, and Ridges Make Hills Hard to Climb
  • Beam Search Expands Several Partial Paths and Purges the Rest
  • Best-First Search Expands the Best Partial Path
  • Search May Lead to Discovery
  • Search Alternatives Form a Procedure Family
• Summary
• Background

5 Nets and Optimal Search

• The Best Path
  • The British Museum Procedure Looks Everywhere
  • Branch-and-Bound Search Expands the Least-Cost Partial Path
  • Adding Underestimates Improves Efficiency
• Redundant Paths
  • Redundant Partial Paths Should Be Discarded
  • Underestimates and Dynamic Programming Improve Branch-and-Bound Search
  • Several Search Procedures Find the Optimal Path
  • Robot Path Planning Illustrates Search
• Summary
• Background

6 Trees and Adversarial Search

• Algorithmic Methods
  • Nodes Represent Board Positions
  • Exhaustive Search Is Impossible
  • The Minimax Procedure Is a Lookahead Procedure
  • The Alpha-Beta Procedure Prunes Game Trees
  • Alpha-Beta May Not Prune Many Branches from the Tree
• Heuristic Methods
  • Progressive Deepening Keeps Computing Within Time Bounds
  • Heuristic Continuation Fights the Horizon Effect
  • Heuristic Pruning Also Limits Search
  • DEEP THOUGHT Plays Grandmaster Chess
• Summary
• Background

7 Rules and Rule Chaining

• Rule-Based Deduction Systems
  • Many Rule-Based Systems Are Deduction Systems
  • A Toy Deduction System Identifies Animals
  • Rule-Based Systems Use a Working Memory and a Rule Base
  • Deduction Systems May Run Either Forward or Backward
  • The Problem Determines Whether Chaining Should Be Forward or Backward
• Rule-Based Reaction Systems
  • Mycin Diagnoses Bacterial Infections of the Blood
  • A Toy Reaction System Bags Groceries
  • Reaction Systems Require Conflict Resolution Strategies
• Procedures for Forward and Backward Chaining
  • Depth-First Search Can Supply Compatible Bindings for Forward Chaining
  • XCON Configures Computer Systems
  • Depth-First Search Can Supply Compatible Bindings for Backward Chaining
  • Relational Operations Support Forward Chaining
  • The Rete Approach Deploys Relational Operations Incrementally
• Summary
• Background

8 Rules, Substrates, and Cognitive Modeling

• Rule-based Systems Viewed as Substrate
  • Explanation Modules Explain Reasoning
  • Reasoning Systems Can Exhibit Variable Reasoning Styles
  • Probability Modules Help You to Determine Answer Reliability
  • Two Key Heuristics Enable Knowledge Engineers to Acquire Knowledge
  • Acquisition Modules Assist Knowledge Transfer
  • Rule Interactions Can Be Troublesome
  • Rule-Based Systems Can Behave Like Idiot Savants
• Rule-Based Systems Viewed as Models for Human Problem Solving
  • Rule-Based Systems Can Model Some Human Problem Solving
  • Protocol Analysis Produces Production-System Conjectures
  • SOAR Models Human Problem Solving, Maybe
  • SOAR Searches Problem Spaces
  • SOAR Uses an Automatic Preference Analyzer
• Summary
• Background

9 Frames and Inheritance

• Frames, Individuals, and Inheritance
  • Frames Contain Slots and Slot Values
  • Frames may Describe Instances or Classes
  • Frames Have Access Procedures
  • Inheritance Enables When-Constructed Procedures to Move Default Slot Values from Classes to Instances
  • A Class Should Appear Before All Its Superclasses
  • A Class's Direct Superclasses Should Appear in Order
  • The Topological-Sorting Procedure Keeps Classes in Proper Order
• Demon Procedures
  • When-Requested Procedures Override Slot Values
  • When-Read and When-Written Procedures Can Maintain Constraints
  • With-Respect-to Procedures Deal with Perspectives and Contexts
  • Inheritance and Demons Introduce Procedural Semantics
  • Object-Oriented Programming Focuses on Shared Knowledge
• Frames, Events, and Inheritance
  • Digesting News Seems to Involve Frame Retrieving and Slot Filling
  • Event-Describing Frames Make Stereotyped Information Explicit
• Summary
• Background

10 Frames and Commonsense

• Thematic-role Frames
  • An Object's Thematic Role Specifies the Object's Relation to an Action
  • Filled Thematic Roles Help You to Answer Questions
  • Various Constraints Establish Thematic Roles
  • A Variety of Constraints Help Establish Verb Meanings
  • Constraints Enable Sentence Analysis
  • Examples Using Take Illustrate How Constraints Interact
• Expansion into Primitive Actions
  • Primitive Actions Describe Many Higher-Level Actions
  • Actions Often Imply Implicit State Changes and Cause-Effect Relations
  • Actions Often Imply Subactions
  • Primitive-Action Frames and State-Change Frames Facilitate Question Answering and Paraphrase Recognition
  • Thematic-Role Frames and Primitive-Action Frames Have Complementary Foci
  • CYC Captures Commonsense Knowledge
• Summary
• Background

11 Numeric Constraints and Propagation

• Propagation of Numbers Through Numeric Constraint Nets
  • Numeric Constraint Boxes Propagate Numbers through Equations
• Propagation of Probability Bounds Through Opinion Nets
  • Probability Bounds Express Uncertainty
  • Spreadsheets Propagate Numeric Constraints Through Numeric-Constraint Nets
  • Venn Diagrams Explain Bound Constraints
  • Propagation Moves Probability Bounds Closer Together
• Propagation of Surface Altitudes Through Arrays
  • Local Constraints Arbitrate between Smoothness Expectations and Actual Data
  • Constraint Propagation Achieves Global Consistency through Local Computation
  • GENINFER Helps Counselors to Provide Precise Genetic Advice
• Summary
• Background

12 Symbolic Constraints and Propagation

• Propagation of Line Labels through Drawing Junctions
  • There Are Only Four Ways to Label a Line in the Three-Faced-Vertex World
  • There Are Only 18 Ways to Label a Three-Faced Junction
  • Finding Correct Labels Is Part of Line-Drawing Analysis
  • Waltz's Procedure Propagates Label Constraints through Junctions
  • Many Line and Junction Labels Are Needed to Handle Shadows and Cracks
  • Illumination Increases Label Count and Tightens Constraint
  • The Flow of Labels Can Be Dramatic
  • The Computation Required Is Proportional to Drawing Size
• Propagation of Time-Interval Relations
  • There Are 13 Ways to Label a Link between Interval Nodes Yielding 169 Constraints
  • Time Constraints Can Propagate across Long Distances
  • A Complete Time Analysis Is Computationally Expensive
  • Reference Nodes Can Save Time
• Five Points of Methodology
• Summary
• Background

13 Logic and Resolution Proof

• Rules of Inference
  • Logic Has a Traditional Notation
  • Quantifiers Determine When Expressions Are True
  • Logic Has a Rich Vocabulary
  • Interpretations Tie Logic Symbols to Worlds
  • Proofs Tie Axioms to Consequences
  • Resolution Is a Sound Rule of Inference
• Resolution Proofs
  • Resolution Proves Theorems by Refutation
  • Using Resolution Requires Axioms to Be in Clause Form
  • Proof Is Exponential
  • Resolution Requires Unification
  • Traditional Logic Is Monotonic
  • Theorem Proving Is Suitable for Certain Problems, but Not for All Problems
• Summary
• Background

14 Backtracking and Truth Maintenance

• Chronological and Dependency-Directed Backtracking
  • Limit Boxes Identify Inconsistencies
  • Chronological Backtracking Wastes Time
  • Nonchronological Backtracking Exploits Dependencies
• Proof by Constraint Propagation
  • Truth Can Be Propagated
  • Truth Propagation Can Establish Justifications
  • Justification Links Enable Programs to Change Their Minds
  • Proof by Truth Propagation Has Limits
• Summary
• Background

15 Planning

• Planning Using If-Add-Delete Operators
  • Operators Specify Add Lists and Delete Lists
  • You Can Plan by Searching for a Satisfactory Sequence of Operators
  • Backward Chaining Can Reduce Effort
  • Impossible Plans Can Be Detected
  • Partial Instantiation Can Help Reduce Effort Too
• Planning Using Situation Variables
  • Finding Operator Sequences Requires Situation Variables
  • Frame Axioms Address the Frame Problem
• Summary
• Background

II Learning and Regularity Recognition

16 Learning by Analyzing Differences

• Induction Heuristics
  • Responding to Near Misses Improves Models
  • Responding to Examples Improves Models
  • Near-Miss Heuristics Specialize; Example Heuristics Generalize
  • Learning Procedures Should Avoid Guesses
  • Learning Usually Must Be Done in Small Steps
• Identification
  • Must Links and Must-Not Links Dominate Matching
  • Models May Be Arranged in Lists or in Nets
  • ARIEL Learns about Proteins
• Summary
• Background

17 Learning by Explaining Experience

• Learning about Why People Act the Way they Do
  • Reification and the Vocabulary of Thematic-Role Frames Capture Sentence-Level Meaning
  • Explanation Transfer Solves Problems Using Analogy
  • Commonsense Problem Solving Can Generate Rulelike Principles
  • The Macbeth Procedure Illustrates the Explanation Principle
  • The Macbeth Procedure Can Use Causal Chains to Establish Common Context
• Learning about Form and Function
  • Examples and Precedents Help Each Other
  • Explanation-Based Learning Offers More than Speedup
• Matching
  • Stupid Matchers Are Slow and Easy to Fool
  • Matching Inexact Situations Reduces to Backward Chaining
  • Matching Sheds Light on Analogical Problem Solving
• Summary
• Background

18 Learning by Correcting Mistakes

• Isolating Suspicious Relations
  • Cups and Pails Illustrate the Problem
  • Near-Miss Groups Isolate Suspicious Relations
  • Suspicious Relation Types Determine Overall Repair Strategy
• Intelligent Knowledge Repair
  • The Solution May Be to Explain the True-Success Suspicious Relations
  • Incorporating True-Success Suspicious Relations May Require Search
  • The Solution May Be to Explain the False-Success Suspicious Relations, Creating a Censor
  • Failure Can Stimulate a Search for More Detailed Descriptions
• Summary
• Background

19 Learning by Recording Cases

• Recording and Retrieving Raw Experience
  • The Consistency Heuristic Enables Remembered Cases to Supply Properties
  • The Consistency Heuristic Solves a Difficult Dynamics Problem
• Finding Nearest Neighbors
• A Fast Serial Procedure Finds the Nearest Neighbor in Logarithmic Time
• Parallel Hardware Finds Nearest Neighbors Even Faster
• Summary
• Background

20 Learning by Managing Multiple Models

• The Version-Space Method
  • Version Space Consists of Overly General and Overly Specific Models
  • Generalization and Specialization Leads to Version-Space Convergence
• Version-Space Characteristics
  • The Version-Space Procedure Handles Positive and Negative Examples Symmetrically
  • The Version-Space Procedure Enables Early Recognition
• Summary
• Background

21 Learning by Building Identification Trees

• From Data to Identification Trees
  • The World Is Supposed to Be Simple
  • Tests Should Minimize Disorder
  • Information Theory Supplies a Disorder Formula
• From Trees to Rules
  • Unnecessary Rule Antecedents Should Be Eliminated
  • Optimizing a Nuclear Fuel Plant
  • Unnecessary Rules Should Be Eliminated
  • Fisher's Exact Test Brings Rule Correction in Line with Statistical Theory
• Summary
• Background

22 Learning by Training Neural Nets

• Simulated Neural Nets
  • Real Neurons Consist of Synapses, Dendrites, Axons, and Cell Bodies
  • Simulated Neurons Consist of Multipliers, Adders, and Thresholds
  • Feed-Forward Nets Can Be Viewed as Arithmetic Constraint Nets
  • Feed-Forward Nets Can Recognize Regularity in Data
• Hill Climbing and Back Propagation
  • The Back-Propagation Procedure Does Hill Climbing by Gradient Ascent
  • Nonzero Thresholds Can Be Eliminated
  • Gradient Ascent Requires a Smooth Threshold Function
  • Back Propagation Can Be Understood Heuristically
  • Back-Propagation Follows from Gradient Descent and the Chain Rule
  • The Back-Propagation Procedure Is Straightforward
• Back-Propagation Characteristics
  • Training May Require Thousands of Back Propagations
  • ALVINN Learns to Drive
  • Back Propagation Can Get Stuck or Become Unstable
  • Back Propagation Can Be Done in Stages
  • Back Propagation Can Train a Net to Learn to Recognize Multiple Concepts Simultaneously
  • Trained Neural Nets Can Make Predictions
  • Excess Weights Lead to Overfitting
  • Neural-Net Training Is an Art
• Summary
• Background

23 Learning by Training Perceptrons

• Perceptrons and Perceptron Learning
  • Perceptrons Have Logic Boxes and Stair-Step Thresholds
  • The Perceptron Convergence Procedure Guarantees Success Whenever Success Is Possible
  • Ordinary Algebra Is Adequate to Demonstrate Convergence When There Are Two Weights
  • Vector Algebra Helps You to Demonstrate Convergence When There Are Many Weights
• What Perceptrons Can and Cannot Do
  • A Straight-Through Perceptron Can Learn to Identify Digits
  • The Perceptron Convergence Procedure Is Amazing
  • There Are Simple Tasks That Perceptrons Cannot Do
• Summary
• Background

24 Learning by Training Approximation Nets

• Interpolation and Approximation Nets
  • Gaussian Functions Centered on Samples Enable Good Interpolations
  • Given Sufficient Nodes, Nets Can Interpolate Perfectly
  • Given Relatively Few Nodes, Approximation Nets Can Yield Approximate Results for All Sample Inputs
  • Too Many Samples Leads to Weight Training
  • Overlooked Dimensions May Explain Strange Data Better than Elaborate Approximation
  • The Interpolation-Approximation Point of View Helps You to Answer Difficult Design Questions
• Biological Implementation
  • Numbers Can Be Represented by Position
  • Neurons Can Compute Gaussian Functions
  • Gaussian Functions Can Be Computed as Products of Gaussian Functions
• Summary
• Background

25 Learning by Simulating Evolution

• Survival of the Fittest
  • Chromosomes Determine Hereditary Traits
  • The Fittest Survive
• Genetic Algorithms
  • Genetic Algorithms Involve Myriad Analogs
  • The Standard Method Equates Fitness with Relative Quality
  • Genetic Algorithms Generally Involve Many Choices
  • It Is Easy to Climb Bump Mountain Without Crossover
  • Crossover Enables Genetic Algorithms to Search High-Dimensional Spaces Efficiently
  • Crossover Enables Genetic Algorithms to Traverse Obstructing Moats
  • The Rank Method Links Fitness to Quality Rank
• Survival of the Most Diverse
  • The Rank-Space Method Links Fitness to Both Quality Rank and Diversity Rank
  • The Rank-Space Method Does Well on Moat Mountain
  • Local Maxima Are Easier to Handle when Diversity Is Maintained
• Summary
• Background

III Vision and Language

26 Recognizing Objects

• Linear Image Combinations
  • Conventional Wisdom Has Focused on Multilevel Description
  • Images Contain Implicit Shape Information
  • One Approach Is Matching Against Templates
  • For One Special Case, Two Images Are Sufficient to Generate a Third
  • Identification Is a Matter of Finding Consistent Coefficients
  • The Template Approach Handles Arbitrary Rotation and Translation
  • The Template Approach Handles Objects with Parts
  • The Template Approach Handles Complicated Curved Objects
• Establishing Point Correspondence
  • Tracking Enables Model Points to Be Kept in Correspondence
  • Only Sets of Points Need to Be Matched
  • Heuristics Help You to Match Unknown Points to Model Points
• Summary
• Background

27 Describing Images

• Computing Edge Distance
  • Averaged and Differenced Images Highlight Edges
  • Multiple-Scale Stereo Enables Distance Determination
• Computing Surface Direction
  • Stereo Analysis Determines Elevations from Satellite Images
  • Reflectance Maps Embody Illumination Constraints
  • Making Synthetic Images Requires a Reflectance Map
  • Surface Shading Determines Surface Direction
• Summary
• Background

28 Expressing Language Constraints

• The Search for an Economical Theory
  • You Cannot Say That
  • Phrases Crystallize on Words
  • Replacement Examples Support Binary Representation
  • Many Phrase Types Have the Same Structure
  • The X-Bar Hypothesis Says that All Phrases Have the Same Structure
• The Search for a Universal Theory
  • A Theory of Language Ought to Be a Theory of All Languages
  • A Theory of Language Ought to Account for Rapid Language Acquisition
  • A Noun Phrase's Case Is Determined by Its Governor
  • Subjacency Limits Wh- Movement
• Competence versus Performance
  • Most Linguists Focus on Competence, Not on Performance
  • Analysis by Reversing Generation Can Be Silly
  • Construction of a Language Understanding Program Remains a Tough Row to Hoe
  • Engineers Must Take Shortcuts
• Summary
• Background

29 Responding to Questions and Commands

• Syntactic Transition Nets
  • Syntactic Transition Nets Are Like Roadmaps
  • A Powerful Computer Counted the Long Screwdrivers on the Big Table
• Semantic Transition Trees
  • A Relational Database Makes a Good Target
  • Pattern Instantiation Is the Key to Relational-Database Retrieval in English
  • Moving from Syntactic Nets to Semantic Trees Simplifies Grammar Construction
  • Count the Long Screwdrivers
  • Recursion Replaces Loops
  • Q&A Translates Questions into Database-Retrieval Commands
• Summary
• Background

Appendix: Relational Databases

• Relational Databases Consist of Tables Containing Records
• Relations Are Easy to Modify
• Records and Fields Are Easy to Extract
• Relations Are Easy to Combine
• Summary

Exercises

Bibliography

Index

Colophon