Knowledge Representation

CS 4725
Wednesdays, 7:10-9:40 P.M.
535 Mudd
Columbia University
Professor Leora Morgenstern

Last modified: May 7, 1999

General Information

How to get in touch

In general I can be reached at:
IBM T.J. Watson Research Center
30 Saw Mill River Road, Mail Stop H1B54
Hawthorne, NY 10532
leora@watson.ibm.com
or leora@cs.columbia.edu
914-784-7151

My office hours are on Wednesdays from 5:00 -- 6:30 P.M.
Office: 722 CEPSR (Schapiro Engineering and Research Building --- right near Mudd).
This is Professor McKeown's office: expect to see her name on the office door.
Phone: 212-939-7118.

Course Requirements:

There will be 3 (down from 5) homework assignments and 1 term project. Homework assignments will not require programming. There will probably be an option to program the term project, but this has not been finalized.
Lateness: Homework assignments should be submtted by the beginning of class on the due date. Late homeworks will be accepted up to 1 week after the due date, but with a penalty: 10% of the grade will be deducted. Homeworks more than 1 week late will not be accepted.
Grading: The homework assignments count for 65%; the term project counts for 35% of the grade. Class participation can positively affect one's grade; unexplained lack of attendance will negatively affect one's grade.

Syllabus

The syllabus can be found here. But this syllabus is at this point hopelessly outdated. Here is the syllabus for end of March/ April classes:

March 24, 1999: Decription Logics, Inheritance Networks, Formula-Augmented Networks. Readings: See below, under Readings section. There are 3 sets of foils that are useful: one is an overview of description logics and inheritance with exceptions; the second and third are versions of an invited talk that I gave at IJCAI-97 on formula-augmented networks and their applicability to industry. The third set of foils may be more useful than the second; there is less extraneous matter and a bit more on applications of formula-augmented networks. I also have links to my papers on FANs.

March 29, 1999: NOTE DATE CHANGE!!! Nonmonotonic Logics. Readings: Davis, Chapter 3; my MITECS article (see below for the link).

April 5, 1999: NOTE DATE CHANGE!!! Nonmonotonic Logics, continued. Readings: same as above, plus my paper, "The Problems with Solutions to the Frame Problem." See below for link. Also see below for foils

April 14, 1999: Nonmon, continued. Same as above. Plus, Reiter: "A Theory of Diagnosis from First Principles," AIJ (will put on reserve). Also see foils below.

April 21, 1999: Bayesian Reasoning. "Bayesian Nets without Tears" (E. Charniak, AI Magazine) Will bring copies to class. Also see below, links to tutorials and papers of interest.

April 28, 1999: Diagnosis, using Bayesian reasoning. Same readings as above.

Textbook and Supplementary Readings

This section includes links to useful papers and presentations.

Required Text:

Ernest Davis, Representations in Commonsense Knowledge, Morgan Kaufmann, 1990. Available from Papyrus Bookstores, amazon.com, or Morgan Kaufmann publishers.

Propositional and first-order logic

These are listed in decreasing order of depth:

Benson Mates, Elementary Logic, Oxford University Press, especially Chapter 5 (translating natural language into first-order logic) and Chapter 7 (rules of inference for first-order logic). Chapter 7 is on reserve.
Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, Chapter 7.
Judith Gersting, Mathematical Structures for Computer Science, Prentice Hall, Chapter 1, sections 1.1 - 1.3. These sections, along with solutions to selected problems, are on reserve.

Ontology and General Knowledge Representation Issues:

John McCarthy and Patrick Hayes: "Some Philosophical Problems from the Standpoint of Artificial Intelligence," 1969. In many collections of papers, including Ginsberg, ed: Readings in Nonmonotonic Reasoning. Seminal paper on knowledge representation, the use of logic in AI, the situation calculus, and the connection between many areas of philosophy and AI.

Ernest Davis: "Guide to Axiomatizing Domains in First-Order Logic". A short guide, useful for novices and experienced axiomatizers alike.

Patrick Hayes: "The Second Naive Physics Manifesto," in Jerry Hobbs and Robert Moore (Eds): Formal Theories of the Commonsense World, Ablex, 1985. This is the classic work on knowledge representation, and I highly recommend reading it. On reserve in the library.

Patrick Hayes: "Naive Physics I: Ontology for Liquids," in Hobbs and Moore, above. A detailed example of the representation of a portion of commonsense knowledge. Highly recommended. On reserve in the library.

Ernest Davis: "The Naive Physics Perplex," AI Magazine, Winter, 1999. A discussion of various approaches toward represening commonsense knowledge.

Temporal Logics, Logics of Action:

A variety of interesting articles can be found at Reasoning about Actions Research Area of the Electronic Transactions on Artificial Intelligence. Click on the "Received Articles" link to find recent papers. Of particular interest is:

Hector Levesque, Fiora Pirri, and Ray Reiter: "Foundations of the Situation Calculus"

Modal Logics, Logics of Knowledge:

Ernest Davis and Leora Morgenstern: "Epistemic Logics and their Applications (foils)" A powerpoint presentation of a tutorial on logics of knowledge given at IJCAI-93, the International Joint Conference of Artificial Intelligence.

Ernest Davis and Leora Morgenstern: "Epistemic Logics and their Applications (write-up) of epistemic logics, written to accompany the IJCAI-93 tutorial, above.

Ernest Davis and Leora Morgenstern: "Epistemic Logics: Annotated Bibliography. An annotated bibliography of epistemic and modal logics, written to accompany the IJCAI-93 tutorial, above.

Leora Morgenstern: Foundations of a Logic of Knowledge, Action, and Communication, Ph.D. thesis. On reserve in the library. Chapters 3 and 4 especially deal with syntactic epistemic logics: the Knower Paradox and its resolution, quasi-quotation, etc.

Inheritance and Description Logics

Han Reichgelt: Knowledge Representation: An AI Perspective, Chapter 5 (Semantic Networks) and Chapter 6(Frames). On reserve in the library.

Hector Levesque and Ron Brachman: "Expressiveness and Tractability in Knowledge Representation and Reasoning," Computational Intelligence, 1987. On reserve in the library.

Enrico Franconi's tutorial on descripton logics. There's a lot of material here; it's probably best to concentrate on the slides in Parts 2 (Structural Description Logics) and 3 (Propositional Description Logics) of Part A.

Web page for descripton logics. Links to pages describing many of the classic inheritance systems.

Foils for A short introductory overview which I wrote up on semantic networks, description logics, inheritance with exceptions. (Updated on March 29, with example of drug formulary).

Foils for "Inheritance Comes of Age", , invited talk at IJCAI-97. The link above will get you foils with a dark background; click for the environmentally correct version, with a light background. (Somewhat harder to read, especially the description of previous systems.)

Same as above, but this version contains less extraneous material and a bit more on potential applications of FANs.

Leora Morgenstern: "Inheritance Comes of Age: Applying Nonmonotonic Techniques to Problems in Industry". This is the long journal paper (Artificial Intelligence, 1998). You may wish to look at the shorter conference paper (IJCAI, 1997), and at an earlier paper, Inheriting Well-formed Formulae in a Formula-Augmented Semantic Network (KR, 1996).

Nonmonotonic Logics

Leora Morgenstern: "Nonmonotonic Logics," an article written for the MIT Encyclopedia of Cognitive Science, MITECS, 1999. You can access a variety of articles in knowledge representation and logic through the MITECS site.

Slides for the class (April 5/April 9) on nonmonotonic logic. An overview. Lots of typos; will be corrected soon.

Leora Morgenstern: "The Problem with Solutions to the Frame Problem," . Discusses temporal reasoning, especially the frame problem and its solutions in nonmonotonic logic.

Slides for April 14 class on solutions to Yale shooting problem.

Slides for April 14 class on diagnosis and nonmonotonic reasoning.

Bayesian (Probabilistic) Reasoning

Eugene Charniak: "Bayesian Networks without Tears" (AI Magazine, Winter 1991 ). Copies distributed in class.

Daphne Koller's home page. Of special interest here is the AAAI 1997 tutorial on Bayesian networks, available for browsing or in postscript (2 slides a page) or (6 slides a page).

Judea Pearl's home page. Of special interest here are Pearl's 1996 Faculty Research Lecture on The Art and Science of Causality and the related papers on Pearl's home page.

Lectures notes for Computational Intelligence by David Poole, Mackworth, and Goebbel, especially lectures for Chapter 10 on probability very good introduction to probability.

Some foils that I've written up to go with Charniak's paper. Still has errors.

Homeworks

Homework 1 (due February 10, 1999)

Solutions to Homework 1

Homework 2 (due March 12, 1999)

The following may be helpful for homework 2:

Examples of some axioms needed in the axiomatization for hw2 .
Ernest Davis: A write-up of Reiter-style situation calculus (the newest dialect of the language) for the blocks world.
Hector Levesque, Fiora Pirri, and Ray Reiter: "Foundations of the Situation Calculus"Relatively concise, terse, write-up of the situation calculus. Assumes knowledge of nonmonotonic reasoning, but may nontheless be useful, if the write-ups above aren't enough.
Frequently Asked Questions on Homework 2
Ernest Davis: "Guide to axiomatizing domains in first-order logic.

Homework 3 (due May 6, 1999). Note date change. Homework has been revised, and includes a link to a sample proof for Kripke structures. (May 3)

Term Project (due May 17, 1999): 2 choices:

Formalizing the first half of the Wolves and Rabbits problem on the commonsense problem page . More details can be found here.
Implementing Formula-Augmented Networks. See my AIJ paper (link is above, under readings) for the algorithm for FANs; you will also need to look at Lynn Stein's algorithm for computing inheritance. This project does not require translating English sentences into logic. More details, sample input files, and answers to frequently asked questions can be found here.

General Resources

The following are some useful general resources for finding out about AI and Knowledge Representation:

AI Subject Index, Institute for Information Technology and especially the subindex on knowledge representation
MIT Encyclopedia of Cognitive Science. This encyclopedia, available (for the next few months) online, has good introductory articles on a variety of topics in knowledge representation, including logic, nonmonotonic reasoning, and temporal reasoning.

Other Information:
The initial course announcement (written up for the CVN program), including a general description of the course and the initial syllabus, can be found here; however, the information at this location is rapidly becoming out of date.