All intelligent activity presupposes knowledge. Knowledge is represented in a knowledge base, which consists of knowledge structures (typically symbolic) and programs. Brian C. Smith's Knowledge Representation Hypothesis forms the basis of this perspective (see References and Resources below):
Any mechanically embodied intelligent process will be comprised of
structural ingredients that
Not necessarily exclusive from the above, this is the lowest expectation out of a knowledge representation module in any AI system. Any KR system should provide at least two operations:
This is the
connectionist view.
This approach takes the view that
there are several (perhaps millions!) identical interconnected
units that are collectively responsible for representing various
concepts. A concept is represented in a distributed sense (as
opposed to local) and is indicated by an evolving pattern of activity
over a collection of units.
function Person(X) return boolean is
function Mortal(X) return boolean is
person(Socrates).
Rich & Knight eight out of the 20 chapters devoted to KR. Most of
the treatment takes the tell-ask perspective. There are separate chapters
(1 each) devoted to predicate logic, rule-based systems, reasoning with
uncertainty, statistical reasoning, semantic networks, and frames and
scripts. Connectionist models and common sense ontologies also have separate
chapters devoted to them.
The chapter on Knowledge representation in Tanimoto surveys
production rules, concept hierarchies, predicate logic, frames, networks,
constraints, ralational databases, and CYC in approximately 50 pages.
There are, however, separate chapters on logical reasoning (mainly
resolution principle and PROLOG), probabilistic reasoning, neural networks,
and rule-based systems.
Russell & Norvig's book devotes 5 out of the 26 chapters on KR.
The tell-ask perspective is used. Most of the discussion is centered around
logical reasoning. Not much on networks and frames. There are however, separate
chapters on uncertainty (4), and neural networks (1).
Ginsberg devotes 8 out of 18 chapters to KR of which 6 deal with
logical reasoning, 1 on probabilistic reasoning, and one on frames and
semantic networks. The main focus of the book is to equate KRR with logical
reasoning.
Dean, Allen & Aloinonos have two (out of 9) chapters devoted to
KR. Only logic-based approached are presented. There are sections on temporal
and spatial reasoning. Decision trees are presented in the chapter on
learning. Distributed representations are also presented in the same
context. There is a separate chapter on uncertainty which also has some
more on decision trees.
Below is a table showing a survey of six AI texts and their coverage
of various of knowledge representation and reasoning paradigms.
Pairs of numbers indicate the approximate number of pages of text, and
an estimate of the number of lectures that will typically be required
to cover all the material in the text. Each lecture is assumed
to be 75 minutes long.
A typical semester has about 13 weeks of lectures, each week having
two 75 minute lectures, giving
a total of 26 lectures.
Please write back to the author for any corrections/additions
Dean, Allen, & Aloimonos : Artificial Intelligence -Theory and
Practice, Benjamin Cummings Publishing Company, 1995.
Genesereth & Nilsson : Logical Foundations of Artificial
Intelligence , Morgan Kaufmann Publishers, Los Altos, CA, 1987.
Ginsberg : Essentials of Artificial Intelligence, Morgan
Kaufmann Publishers, 1993.
Artificial Intelligence: Structures and
Strategies for Complex problem Solving, Second Edition, Benjamin
Cummings Publishing Company, 1993.
McClelland & Rumelhart : Parallel Distributed Processing,
MIT Press, 1986.
Reichgelt : Knowledge Representation: An AI Perspective,
Ablex Publishing, 1991. (A small, but comprehensive text on classic
KR techniques. The text summarizes most of the important discussions
from papers in the Brachman & Levesque collection.)
Rich & Knight : Artificial Intelligence, Second Edition,
McGraw Hill, 1991.
Russell &
Norvig :
Artificial Intelligence: A Modern Approach,
Prentice Hall, 1995.
Shapiro : The Encyclopedia of Artificial Intelligence, Second
Edition, John Wiley & Sons, Inc., 1992.
Brian C. Smith : Prologue to "Reflection and Semantics in a
Procedural Language", in Readings in Knowledge Representation,
edited by R. J. Brachman & H. J. Levesque, Morgan Kaufmann, 1985.
Tanimoto : The Elements of Artificial Intelligence Using
Common Lisp, Second Edition, Computer Science press, 1995.
Winston : Artificial Intelligence, Third Edition,
Addison Wesley, 1992.
KR Paradigms
There are several paradigms that have emerged from these perspectives.
The paradigms may be simply surveyed and/or if time permits, one or more may be
introduced in some detail. Here are the key paradigms:
if (X = ``Socrates'') or (X = ``Hillary'') then return true
else return false;
return person(X);
person(Hillary).
forall X [person(X) ---> mortal(X)]Advanced Topics
The following topics represent areas at the cutting edge of KR research---
nonmonoticity and defaults, inconsistency, incompleteness, expressiveness
vs tractability, knowledge sharing, ontologies, ..., etc.
KR in AI Texts
Luger & Stubblefield treat KR as the center piece of AI study.
Topics such as search, natural language understanding, machine learning,
and expert systems are motivated through the KRR approach. All of the paradigms
listed above are presented scattered through the various chapters of the text.
The book devotes equal time to implementation issues in LISP as well as
PROLOG.
------------------------------------------------------------------------------
Dean,
Allen &, Russell & Rich & Luger &
Aloimonos Ginsberg Norvig Tanimoto Knight Stubblefield
------------------------------------------------------------------------------
Overall Text 500/40 400/24 850/52 760/42 580/40 700/40
------------------------------------------------------------------------------
Nets/Frames 1/0 18/1 7/0.5 45/2 50/2 40/2
------------------------------------------------------------------------------
Logic 100/12 122/7 180/9 60/5 70/5 60/3
------------------------------------------------------------------------------
Dec. Trees 10/1 12/1 14/1 1/0 10/1
------------------------------------------------------------------------------
Stat. Reas. 53/3 19/1 120/6 45/3 20/2 25/2
------------------------------------------------------------------------------
Rules 40/2 20/1 20/1
------------------------------------------------------------------------------
PDP 38/3 3/0 60/4 25/2 35/3 15/2
------------------------------------------------------------------------------
Totals 202/19 162/9 379/21 229/15 196/13 170/11
------------------------------------------------------------------------------
% of Text 47% 37% 40% 36% 32% 27%
------------------------------------------------------------------------------
% of Course 73% 35% 81% 58% 50% 42%
------------------------------------------------------------------------------
Sample Curriculum
Typically, I expect to spend about 6 weeks (out of a total of 13) on KR.
I concentrate mainly on procedural knowledge, semantic networks, frames,
logic, rule-based reasoning, and distributed representations. Other paradigms
listed above are covered under separate topics. Shown below is a 6-week
lecture plan:
An introduction to KR, procedural knowledge, and
frames. Sometimes I use the code from Winston blocksworld
as a demo/home work. Semantic nets are also introduced. (Note: Scripts
are presented in the context of NLU).
Use SNePS as an example of an implemented semantic network
processing system (see References &
Resources below). Students get a lab assignment based on SNePS.
Logic as a KR formalism is introduced
(See lecture notes on
Logic).
At this point I show how to do logical reasoning using semantic
network representations (an example of a hybrid system) in SNePS.
This week is spent on an introduction to distributed representations.
Most of the material comes out of the first two/three chapters of
McClelland & Rumelhart's Volume 1. At this point, one can
go right into learning, by introducing learning in connectionist
networks, or wait until the topic is formally covered.
Alternative Curriculum
Here is another 6-week schedule:
An introduction to KR, procedural knowledge, nets and frames.
Logic. Propositional Logic, Predicate Calculus, Inference Rules
(choice of resolution, natural deduction, etc.),
Unification, Non-monotonic Reasoning.
(See lecture notes on
Logic).
Rule-based systems. Forward and backward chaining.
Distributed Representations.
References & Resources
Clicking below on names will take you to the individual's home page. Generally
a good starting point for locating current information. Clicking below on
titles of the publications will take you to homepages of the documents where
other resources like code, instructional materials, and related software
may be available.
Brachman & Levesque (editors):
Readings in Knowledge Representation,
Morgan Kaufmann, 1985. (A good resource for classic papers on KR.
One can also use Reichgelt, as an alternative.)
Software
ANALOG:
A system for building, using, and retrieving from propositional semantic
networks. It is designed to facilitate knowledge representation for natural language processing. It is a
descendant of SNePS (see below).
SNePS : A Lisp-based Semantic Network Processing System. This link points to various on-line resources available (distribution, manuals, bibliography, and a tutorial). SNePS is also available in the GNU distribution, as well as in the CMU AI Repository.
CMU AI Repository on KR : Includes several KR systems: COLAB, several frame systems (FRAMEWRK, FRL, FROBS, KR, PARMENID), KNOWBEL, ONTIC, RHET, SNePS, URANUS, and several KL-ONE-based systems (BACK, CEC, DP, MOTEL).
LOOM : Another nice KR system (KL_ONE family).