GS/CSE 6390A Knowledge Representation
Fall 2012
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:
Nov 30: Assignment 4 is out.
It is due December 19 at 4pm.
If you want to attempt the second Bonus Exercise,
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.
- Nov 23: Test 2 will be on Nov 29. It will cover
everything we have seen in class until Nov. 22 inclusive. The focus
will be on the material in Chapters 9 to 13 inclusive of the textbook,
as well as on the other readings posted on the course website or
emailed to students on Description Logics and Answer Set Programming.
You may want to work on exercises 3 and 4 of Chapter 13 of the
textbook to get a better understanding of the material on explanation
and diagnosis.
- Nov. 12: Assignment 3 is out; it due on
Nov. 29.
- Nov 8: The deadline for assignment 2 has been extended; it is now due on Nov 13 at 5pm.
- Oct 31: The office hours on Nov 1 and Nov 2 are cancelled. Send email to
the instructor if you have questions.
- Oct. 22: Assignment 2 is out; it due on
Nov. 13 (deadline extended).
- Oct. 21: Slides and readings on Description Logics:
De Giacomo's slides on Description Logics and their use for reasoning about UML class diagrams - read at least pp. 1-26 and p. 32,
Horrocks and Sattler's slides on tableaux for ALC concept satisfiability - read these,
Horrocks and Sattler's slides on tableaux for ALC knowledge bases - read at least p. 2 & 3,
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) - read at least pp. 4-6, 13, 29, 30, 36-38, 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 4: Test 1 will be on Oct 25. It will cover everything we have seen in class until Oct 18 inclusive. With respect to description logics, only the material in Brachman and Levesque Chapter 9 and
De Giacomo's slides on Description Logics and their use for reasoning about UML class diagrams slides 1-11 are covered.
- Sept 28: The office hour on Sept 28 is cancelled.
- Sept 27: Assignment 1 is out; it due on
Oct. 18 at the beginning of class.
- Sept 19: The lectures will now be held from 17:30 to 20:30 on Thursdays; the room is still VH1152. The office hours on Thursdays have been changed too; see below.
- The first lecture is on Sept 6.
Instructor
Prof. Yves Lespérance
Office: LAS 3052A
Tel: 416-736-2100 ext. 70146
Email: lesperan "at" cse.yorku.ca
Lectures
Thursday from 17:30 to 20:30 in VH 1152 (VH is Vari Hall).
Instructor Office Hours
Tuesday 17:00 - 18:00, Thursday 13:00 - 14:00, and Friday 14:00 - 15: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 6) Chapter 1 Introduction.
Chapter 2 The Language of First-Order Logic.
- Week 2 (Sept 13) Chapter 3 Expressing Knowledge.
- Week 3 (Sept 20) Chapter 4 Resolution.
- Week 4 (Sept 27) Chapter 5 Reasoning with Horn Clauses.
- Week 5 (Oct 4) Chapter 6 Procedural Control of Reasoning, Prolog.
Chapter 7 Rules in Production Systems.
- Week 6 (Oct 11) Chapter 8 Object-Oriented Representation.
- Week 7 (Oct 18) Chapter 9 Structured Descriptions, Description Logic, and Ontologies.
- Week 8 (Oct 25) Test 1. Description Logics.
- (Nov 1) Reading week; no class.
- Week 9 (Nov 8) Chapter 10 Inheritance.
Chapter 11 Defaults. Answer Set Programming.
- Week 10 (Nov 15) Chapter 12 Vagueness, Uncertainty, and Degrees of Belief.
- Week 11 (Nov 22) Chapter 13 Explanations and Diagnosis.
- Week 12 (Nov 29) Test 2.
Chapter 14 Actions. Chapter 15 Planning.
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