bobgian@psuvax.UUCP (01/01/84)
CMPSC 481: INTRODUCTION TO ARTIFICIAL INTELLIGENCE
TOPIC OUTLINE:
INTRODUCTION: What is "Intelligence"?
Computer modeling of "intelligent" human performance. Turing Test.
Brief history of AI. Examples of "intelligent" programs: Evan's Geometric
Analogies, the Logic Theorist, General Problem Solver, Winograd's English
language conversing blocks world program (SHRDLU), MACSYMA, MYCIN, DENDRAL.
PRELUDE AND FUGUE ON THE "SECRET OF INTELLIGENCE":
"What is a Brain that it may possess Intelligence, and Intelligence that
it may inhabit a Brain?" Introduction to Formal Systems, Physical Symbol
Systems, and Multilevel Interpreters.
REPRESENTATION OF PROBLEMS, GOALS, ACTIONS, AND KNOWLEDGE:
State Space problem formulations. Predicate Calculus. Semantic Networks.
Production Systems. Frames and Scripts.
SEARCH:
Representation of problem-solving as graph search.
"Blind" graph search:
Depth-first, Breadth-first.
Heuristic graph search:
Best-first, Branch and Bound, Hill-Climbing.
Representation of game-playing as tree search:
Static Evaluation, Minimax, Alpha-Beta.
Heuristic Search as a General Paradigm:
Search WITH Heuristics, Search FOR Heuristics
THE GENERAL PROBLEM SOLVER (GPS) AS A MODEL OF INTELLIGENCE:
Goals and Subgoals -- problem decomposition
Difference-Operator Tables -- the solution to subproblems
Does the model fit? Does GPS work?
EXPERT SYSTEMS AND KNOWLEDGE ENGINEERING:
Representation of Knowledge: The "Production System" Movement
The components:
Knowledge Base
Inference Engine
Examples of famous systems:
MYCIN, TEIRESIAS, DENDRAL, MACSYMA, PROSPECTOR
INTRODUCTION TO LISP PROGRAMMING:
Symbolic expressions and symbol manipulation:
Basic data types
Symbols
The special symbols T and NIL
Numbers
Functions
Assignment of Values to Symbols (SETQ)
Objects constructed from basic types
Constructor functions: CONS, LIST, and APPEND
Accessor functions: CAR, CDR
Evaluation and Quotation
Predicates
Definition of Functions (DEFUN)
Flow of Control (COND, PROG, DO)
Input and Output (READ, PRINT, TYI, TYO, and friends)
REPRESENTATION OF DECLARATIVE KNOWLEDGE IN LISP:
Built-in representation mechanisms
Property lists
Arrays
User-definable data structures
Data-structure generating macros (DEFSTRUCT)
Manipulation of List Structure
"Pure" operations (CONS, LIST, APPEND, REVERSE)
"Impure" operations (RPLACA and RPLACD, NCONC, NREVERSE)
Storage Mapping, the Free List, and Garbage Collection
REPRESENTATION OF PROCEDURAL KNOWLEDGE IN LISP:
Types of Functions
Expr: Call by Value
Fexpr: Call by Name
Macros and macro-expansion
Functions as Values
APPLY, FUNCALL, LAMBDA expressions
Mapping operators (MAPCAR and friends)
Functional Arguments (FUNARGS)
Functional Returned Values (FUNVALS)
THE MEANING OF "VALUE":
Assignment of values to symbols
Binding of values to symbols
"Local" vs "Global" variables
"Dynamic" vs "Lexical" binding
"Shallow" vs "Deep" binding
The concept of the "Environment"
"VALUES" AND THE OBJECT-CENTERED VIEW OF PROGRAMMING:
Data-Driven programming
Message-passing
Information Hiding
Safety through Modularity
The MIT Lisp Machine "Flavor" system
LISP'S TALENTS IN REPRESENTATION AND SEARCH:
Representation of symbolic structures in LISP
Predicate Calculus
Rule-Based Expert Systems (the Knowledge Base examined)
Frames
Search Strategies in LISP
Breadth-first, Depth-first, Best-first search
Tree search and the simplicity of recursion
Interpretation of symbolic structures in LISP
Rule-Based Expert Systems (the Inference Engine examined)
Symbolic Mathematical Manipulation
Differentiation and Integration
Symbolic Pattern Matching
The DOCTOR program (ELIZA)
LISP AS THE "SYSTEMS SUBSTRATE" FOR HIGHER LEVEL ABSTRACTIONS
Frames and other Knowledge Representation Languages
Discrimination Nets
Augmented Transition Networks (ATNs) as a specification of English syntax
Interpretation of ATNs
Compilation of ATNs
Alternative Control Structures
Pattern-Directed Inference Systems (production system interpreters)
Agendas (best-first search)
Chronological Backtracking (depth-first search)
Dependency-Directed Backtracking
Data Dependencies, Non-Monotonic Logic, and Truth-Maintenance Systems
"Higher" High-Level Languages: PLANNER, CONNIVER
PROBLEM SOLVING AND PLANNING:
Hierarchical models of planning
GPS, STRIPS, ABSTRIPS
Non-Hierarchical models of planning
NOAH, MOLGEN
THE UNDERSTANDING OF NATURAL LANGUAGE:
The History of "Machine Translation" -- a seemingly simple task
The Failure of "Machine Translation" -- the need for deeper understanding
The Syntactic Approach
Grammars and Machines -- the Chomsky Hierarchy
RTNs, ATNs, and the work of Terry Winograd
The Semantic Approach
Conceptual Dependency and the work of Roger Schank
Spoken Language Understanding
HEARSAY
HARPY
ROBOTICS:
Machine Vision
Early visual processing (a signal processing approach)
Scene Analysis and Image Understanding (a symbolic processing approach)
Manipulator and Locomotion Control
Statics, Dynamics, and Control issues
Symbolic planning of movements
MACHINE LEARNING:
Rote Learning and Learning by Adaptation
Samuel's Checker player
Learning from Examples
Winston's ARCH system
Mitchell's Version Space approach
Learning by Planning and Experimentation
Samuel's program revisited
Sussman's HACKER
Mitchell's LEX
Learning by Heuristically Guided Discovery
Lenat's AM (Automated Mathematician)
Extending the Heuristics: EURISKO
Model Induction via Generate-and-Test
The META-DENDRAL project
Automatic Formation of Scientific Theories
Langley's BACON project
A Model for Intellectual Evolution (my own work)
RECAP ON THE PRELUDE AND FUGUE:
Formal Systems, Physical Symbol Systems, and Multilevel Interpreters
revisited -- are they NECESSARY? are they SUFFICIENT? Is there more
(or less) to Intelligence, Consciousness, the Soul?
SUMMARY, CONCLUSIONS, AND FORECASTS:
The representation of knowledge in Artificial Intelligence
The problem-solving paradigms of Artificial Intelligence
The key ideas and viewpoints in the modeling and creation of intelligence
The results to date of the noble effort
Prospectus for the future
--
Spoken: Bob Giansiracusa
Bell: 814-865-9507
Bitnet: bobgian@PSUVAX1.BITNET
Arpa: bobgian%psuvax1.bitnet@Berkeley
CSnet: bobgian@penn-state.csnet
UUCP: allegra!psuvax!bobgian
USnail: Dept of Comp Sci, Penn State Univ, University Park, PA 16802