Knowledge Representation



Perspectives

There are at least three broad perspectives one can lend to the field of knowledge representation and reasoning (KRR). It is likely that all three perspectives will be presented, regardless of the over all thematic organization of the course.

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:

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.

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.


------------------------------------------------------------------------------
              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:

Alternative Curriculum

Here is another 6-week schedule:

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.

Please write back to the author for any corrections/additions


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.)

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.

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).


Last updated: June 5, 1995.
Deepak Kumar
Bryn Mawr College
dkumar@cc.brynmawr.edu