Copy Link
Add to Bookmark
Report
AIList Digest Volume 2 Issue 003
AIList Digest Thursday, 5 Jan 1984 Volume 2 : Issue 3
Today's Topics:
Course - Penn State's First Undergrad AI Course
----------------------------------------------------------------------
Date: 31 Dec 83 15:18:20-PST (Sat)
From: harpo!floyd!clyde!akgua!psuvax!bobgian @ Ucb-Vax
Subject: Penn State's First Undergrad AI Course
Article-I.D.: psuvax.380
Last fall I taught Penn State's first ever undergrad AI course. It
attracted 150 students, including about 20 faculty auditors. I've gotten
requests from several people initiating AI courses elsewhere, and I'm
posting this and the next 6 items in hopes they may help others.
1. General Information
2. Syllabus (slightly more detailed topic outline)
3. First exam
4. Second exam
5. Third exam
6. Overview of how it went.
I'll be giving this course again, and I hate to do anything exactly the
same twice. I welcome comments and suggestions from all net buddies!
-- Bob
[Due to the length of Bob's submission, I will send the three
exams as a separate digest. Bob's proposal for a network AI course
associated with his spring semester curriculum was published in
the previous AIList issue; that was entirely separate from the
following material. -- Ken Laws]
--
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
------------------------------
Date: 31 Dec 83 15:19:52-PST (Sat)
From: harpo!floyd!clyde!akgua!psuvax!bobgian @ Ucb-Vax
Subject: PSU's first AI course, Part 1/6
Article-I.D.: psuvax.381
CMPSC 481: INTRODUCTION TO ARTIFICIAL INTELLIGENCE
An introduction to the theory, research paradigms, implementation techniques,
and philosopies of Artificial Intelligence considered both as a science of
natural intelligence and as the engineering of mechanical intelligence.
OBJECTIVES -- To provide:
1. An understanding of the principles of Artificial Intelligence;
2. An appreciation for the power and complexity of Natural Intelligence;
3. A viewpoint on programming different from and complementary to the
viewpoints engendered by other languages in common use;
4. The motivation and tools for developing good programming style;
5. An appreciation for the power of abstraction at all levels of program
design, especially via embedded compilers and interpreters;
6. A sense of the excitement at the forefront of AI research; and
7. An appreciation for the tremendous impact the field has had and will
continue to have on our perception of our place in the Universe.
TOPIC SUMMARY:
INTRODUCTION: What is "Intelligence"?
Computer modeling of "intelligent" human performance. The Turing Test.
Brief history of AI. Relation of AI to psychology, computer science,
management, engineering, mathematics.
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. Necessity and Sufficiency of
Physical Symbol Systems as the basis for intelligence.
REPRESENTATION OF PROBLEMS, GOALS, ACTIONS, AND KNOWLEDGE:
State Space, Predicate Calculus, Production Systems, Procedural
Representations, Semantic Networks, Frames and Scripts.
THE "PROBLEM-SOLVING" PARADIGM AND TECHNIQUES:
Generate and Test, Heuristic Search (Search WITH Heuristics,
Search FOR Heuristics), Game Trees, Minimax, Problem Decomposition,
Means-Ends Analysis, The General Problem Solver (GPS).
LISP PROGRAMMING:
Symbolic Expressions and Symbol Manipulation, Data Structures,
Evaluation and Quotation, Predicates, Input/Output, Recursion.
Declarative and Procedural knowledge representation in LISP.
LISP DETAILS:
Storage Mapping, the Free List, and Garbage Collection,
Binding strategies and the concept of the "Environment", Data-Driven
Programming, Message-Passing, The MIT Lisp Machine "Flavor" system.
LISP AS THE "SYSTEMS SUBSTRATE" FOR HIGHER LEVEL ABSTRACTIONS:
Frames and other Knowledge Representation Languages, Discrimination
Nets, "Higher" High-Level Languages: PLANNER, CONNIVER, PROLOG.
LOGIC, RULE-BASED SYSTEMS, AND INFERENCE:
Logic: Axioms, Rules of Inference, Theorems, Truth, Provability.
Production Systems: Rule Interpreters, Forward/Backward Chaining.
Expert Systems: Applied Knowledge Representation and Inference.
Data Dependencies, Non-Monotonic Logic, and Truth-Maintenance Systems,
Theorem Proving, Question Answering, and Planning systems.
THE UNDERSTANDING OF NATURAL LANGUAGE:
Formal Linguistics: Grammars and Machines, the Chomsky Hierarchy.
Syntactic Representation: Augmented Transition Networks (ATNs).
Semantic Representation: Conceptual Dependency, Story Understanding.
Spoken Language Understanding.
ROBOTICS: Machine Vision, Manipulator and Locomotion Control.
MACHINE LEARNING:
The Spectrum of Learning: Learning by Adaptation, Learning by Being
Told, Learning from Examples, Learning by Analogy, Learning by
Experimentation, Learning by Observation and Discovery.
Model Induction via Generate-and-Test, Automatic Theory Formation.
A Model for Intellectual Evolution.
RECAPITULATION AND CODA:
The knowledge representation and problem-solving paradigms of AI.
The key ideas and viewpoints in the modeling and creation of intelligence.
Is there more (or less) to Intelligence, Consciousness, the Soul?
Prospectus for the future.
Handouts for the course include:
1. Computer Science as Empirical Inquiry: Symbols and Search. 1975 Turing
Award Lecture by Allen Newell and Herb Simon; Communications of the ACM,
Vol. 19, No. 3, March 1976.
2. Steps Toward Artificial Intelligence. Marvin Minsky; Proceedings of the
IRE, Jan. 1961.
3. Computing Machinery and Intelligence. Alan Turing; Mind (Turing's
original proposal for the "Turing Test").
4. Exploring the Labyrinth of the Mind. James Gleick; New York Times
Magazine, August 21, 1983 (article about Doug Hofstadter's recent work).
TEXTBOOKS:
1. ARTIFICIAL INTELLIGENCE, Patrick H. Winston; Addison Wesley, 1983.
Will be available from publisher in early 1984. I will distribute a
copy printed from Patrick's computer-typeset manuscript.
2. LISP, Patrick Winston and Berthold K. P. Horn; Addison Wesley, 1981.
Excellent introductory programming text, illustrating many AI implementation
techniques at a level accessible to novice programmers.
4. GODEL, ESCHER, BACH: AN ETERNAL GOLDEN BRAID, Douglas R. Hofstadter;
Basic Books, 1979. One of the most entertaining books on the subject of AI,
formal systems, and symbolic modeling of intelligence.
5. THE HANDBOOK OF ARTIFICIAL INTELLIGENCE, Avron Barr, Paul Cohen, and
Edward Feigenbaum; William Kaufman Press, 1981 and 1982. Comes as a three
volume set. Excellent (the best available), but the full set costs over $100.
6. ANATOMY OF LISP, John Allen; McGraw-Hill, 1978. Excellent text on the
definition and implementation of LISP, sufficient to enable one to write a
complete LISP interpreter.
------------------------------
Date: 31 Dec 83 15:21:46-PST (Sat)
From: harpo!floyd!clyde!akgua!psuvax!bobgian @ Ucb-Vax
Subject: PSU's first AI course -- part 2/6 (Topic Outline)
Article-I.D.: psuvax.382
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
------------------------------
Date: 31 Dec 83 15:28:32-PST (Sat)
From: harpo!floyd!clyde!akgua!psuvax!bobgian @ Ucb-Vax
Subject: PSU's first AI course -- part 6/6 (Overview)
Article-I.D.: psuvax.386
A couple of notes about how the course went. Interest was high, but the
main problem I found is that Penn State students are VERY strongly
conditioned to work for grades and little else. Most teachers bore them,
expect them to memorize lectures and regurgitate on exams, and students
then get drunk (over 50 frats here) and promptly forget all. Initially
I tried to teach, but I soon realized that PEOPLE CAN LEARN (if they
really want to) BUT NOBODY CAN TEACH (students who don't want to learn).
As the course evolved my role became less "information courier" and more
"imagination provoker". I designed exams NOT to measure learning but to
provoke thinking (and thereby learning). The first exam (on semantic
nets) was given just BEFORE covering that topic in lecture -- students
had a hell of a hard time on the exam, but they sure sat up and paid
attention to the next week's lectures!
For the second exam I announced that TWO exams were being given: an easy
one (if they sat on one side of the room) and a hard one (on other side).
Actually the exams were identical. (This explains the first question.)
The winning question submitted from the audience related to the chapter
in GODEL, ESCHER, BACH on the MU system: I gave a few axioms and inference
rules and then asked whether a given wff was a theorem.
The third exam was intended ENTIRELY to provoke discussion and NOT AT ALL
to measure anything. It started with deadly seriousness, then (about 20
minutes into the exam) a few "audience plants" started acting out a
prearranged script which included discussing some of the questions and
writing some answers on the blackboard. The attempt was to puncture the
"exam mentality" and generate some hot-blooded debate (you'll see what I
mean when you see the questions). Even the Teaching Assistants were kept
in the dark about this "script"! Overall, the attempt failed, but many
people did at least tell me that taking the exams was the most fun part
of the course!
With this lead-in, you probably have a clearer picture of some of the
motivations behind the spring term course. To put it bluntly: I CANNOT
TEACH AI. I CAN ONLY HOPE TO INSPIRE INTERESTED STUDENTS TO WANT TO LEARN
AI. I'LL DO ANYTHING I CAN THINK OF WHICH INCREASES THAT INSPIRATION.
The motivational factors also explain my somewhat unusual grading system.
I graded on creativity, imagination, inspiration, desire, energy, enthusiasm,
and gusto. These were partly measured by the exams, partly by the energy
expended on several optional projects (and term paper topics), and partly
by my seat-of-the-pants estimate of how determined a student was to DO real
AI. This school prefers strict objective measures of student performance.
Tough.
This may all be of absolutely no relevance to others teaching AI. Maybe
I'm just weird. I try to cultivate that image, for it seems to attract
the best and brightest students!
-- Bob Giansiracusa
------------------------------
End of AIList Digest
********************
