GS/CSE 6390A Knowledge Representation
Fall 2010
Department of Computer Science and Engineering,
York University
An In-Depth Survey of Knowledge Representation and Reasoning
The course examines some of the techniques used to represent
knowledge in artificial intelligence, and the associated methods of
automated reasoning. The emphasis will be on the compromises involved
in providing a useful but tractable representation and reasoning
service to a knowledge-based system.
What's new:
-
Dec. 2: Assignment 4 is out.
It is due December 20 at 4pm.
If you want to attempt the Bonus Problem,
use this Golog interpreter.
See also this elevator controller
example Golog program.
Note that you should change the extensions from .swipl to .pl
before you load the files into SWI Prolog.
- Dec 2: Test 2 will be on December 9. It will cover
Chapters 9 to 15 inclusively, inlcuding the material discussed in
class that is not in the textbook. The test will last 80 min.
- Nov. 18: Reading: Sheila McIlraith's slides on Answer Set Programming.
Optional reading on Answer Set Programming:
Gelfond, M. Answer Sets. In F. van Harmelen, V. Lifschitz, and B. Porter, editors, Handbook of Knowledge Representation, 285-316, Elsevier, 2008.
Reference: a paper that discusses the connection between default logic and autoepistemic logic:
G. Lakemeyer and H.J. Levesque: Only-Knowing: Taking It Beyond Autoepistemic Reasoning. Proc. of AAAI 2005: 633-638.
-
Nov. 18: Assignment 3 is out. It is due December 2.
- Nov. 4: Assignment 2 is out; it due on
Nov. 18 at the beginning of class.
- Oct. 29: Slides and readings on Description Logics:
De Giacomo's slides on Description Logics and their use for reasoning about UML class diagrams - read p. 1-26 and p. 32,
Horrocks and Sattler's slides on tableaux for ALC concept satisfiability,
Horrocks and Sattler's slides on tableaux for ALC knowledge bases,
Baader and Sattler's paper Overview of Tableau Algorighms for Description Logics,
De Giacomo's slides on DL-Lite (Oct 5, 2010 talk at U of T), as well as
Calvanese et al's paper Conceptual Modeling for Data Integration which discussses much the same material. A more detailed reference is
Calvanese et al's Ontologies and Databases: The DL-Lite Approach.
Another useful reference on Description Logic is
Lutz's slides on
Reasoning in Description Logics: Expressive Power vs. Computational Complexity,
from his tutorial at KR 2010.
- Oct. 22: Test 1 will be on Oct. 28 at the beginning of
class. It covers Chapters 1 to 8 inclusively of the textbook.
-
Oct. 12: Some lecture notes on
Prolog have been posted; the zebra puzzle example
is also available. More information on Prolog can be found on the
CSE 3401 web
page for Fall 2005; see the lecture notes for section B starting
from October 25
(click on Notes in the menu on the left).
- Oct. 7: The office hour on Oct. 8 is cancelled. During reading
week, office hours will be held at the regular times.
- Sept. 30: Assignment 1 is out; it due on
Oct. 21 at the beginning of class.
- The first lecture is on Sept 16.
Instructor
Prof. Yves Lespérance
Office: CSE 3052A
Tel: 416-736-2100 ext. 70146
Email: lesperan "at" cse.yorku.ca
Lectures
Thursday from 19:00 to 22:00 in BC 225 (BC is Bethune College).
Instructor Office Hours
Tuesday and Thursday 17:00 - 18:00 and Friday 15:00 - 16:00,
or by appointment.
Textbook
Ronald J. Brachman and Hector J. Levesque,
Knowledge Representation and Reasoning,
Elsevier/Morgan Kaufmann 2004, ISBN 1-55860-932-6
Recommended but not required; lecture notes (slides) will be
distributed, which are often sufficient; textbook is on reserve at
Steacie Library.
Prerequisites
Knowledge of first-order logic. Some knowledge of Prolog.
Evaluation
| Assignements (4 @ 12.5% each) | 50% |
| Test 1 | 30% |
| Test 2 | 20% |
| Total | 100% |
Tentative Schedule
- Week 1 (Sept 16) Chapter 1 Introduction.
Chapter 2 The Language of First-Order Logic.
- Week 2 (Sept 23) Chapter 3 Expressing Knowledge.
Begin Chapter 4 Resolution.
- Week 3 (Sept 30) Finish Chapter 4. Chapter 5 Reasoning with Horn Clauses.
- Week 4 (Oct 7) Chapter 6 Procedural Control of Reasoning, Prolog.
Chapter 7 Rules in Production Systems.
- (Oct 14) Reading week; no class.
- Week 5 (Oct 21) Chapter 8 Object-Oriented Representation.
Begin Chapter 9 Structured Descriptions.
- Week 6 (Oct 28) Test 1.
Continue Chapter 9. Description Logic and Ontologies.
- Week 7 (Nov 4) Finish Chapter 9. Chapter 10 Inheritance.
- Week 8 (Nov 11) Chapter 11 Defaults. Answer Set Programming.
- Week 9 (Nov 18) Chapter 12 Vagueness, Uncertainty, and Degrees of Belief.
- Week 10 (Nov 25) Chapter 13 Explanations and Diagnosis.
- Week 11 (Dec 2) Chapter 14 Actions. Chapter 15 Planning.
- Week 12 (Dec 9) Test 2.
Chapter 16 The Tradeoff between Expressiveness and Tractability.
Additional References
A good Prolog text:
Clocksin, W.F. and Mellish, C.S.,
Programming in Prolog, (5th edition), Springer Verlag, New York, 2004.
On knowledge representation:
Baral, C.
Knowledge representation, reasoning, and declarative problem solving.
Cambridge University Press, Cambridge/New York, 2003.
Genesereth, M.R. and Nilsson, N.J.
Logical foundations of artificial intelligence.
Morgan Kaufmann, Los Altos, CA, 1987.
Van Harmelen, F., Lifschiltz, V., and Porter, B.
Handbook of Knowledge Representation.
Elsevier, Amsterdam, 2008.
On description logic:
Baader, F., Calvanese, D., McGuiness, D., Nardi, D., Patel-Schneider, P.
The Description Logic Handbook, 2nd Edition.
Cambridge Univ. Press, Cambridge UK, 2007.
Lutz, C.
Reasoning in Descriprion Logics: Expressive Power vs. Computational Complexity,
slides from Tutorial at KR 2010.
On reasoning about action:
Reiter, R.,
Knowledge in Action: Logical Foundations for Specifying and Implementing
Dynamical Systems,
MIT Press, 2001.
York Library eCopy,
Book home page.
On AI:
Russell, S.J. and Norvig, P.,
Artificial Intelligence: A Modern Approach, 3rd edition
Prentice Hall, 2010.
Poole, D. and Mackworth, A.,
Artificial Intelligence: Foundations of Computational Agents,
Cambridge University Press, 2010.
|
Running SWI-Prolog on the York CSE Research System or Prism
|
-
To run Prolog execute the command pl. To exit enter
<CTRL>-D
at the prompt.
-
Documentation is available
on the web.
Getting Prolog
About Prolog