Knowledge Representation & Reasoning: 2011-2012
Information
|
Lecturer |
|
|
Degrees |
Schedule B2 — Honour School of Computer Science Schedule B2 — Honour School of Mathematics and Computer Science |
|
Term |
Hilary Term 2012 (16 lectures) |
Overview
Students attending this course are expected to acquire a good understanding of the logical foundations of Knowledge Representation and Reasoning as well as to become familiar with current research trends in the field. The course requires some familiarity with propositional and first order logic.Special emphasis is placed on decidable fragments of first order logic, which are suited for Knowledge Representation. These include, for example, the logics underlying ontology-based technologies and the Semantic Web.
The course will also discuss logics that depart from first order logic, such as non-monotonic logics.
Learning outcomes
- Students satisfying the prerequisites are expected to understand the fundamental principles of logic-based Knowledge Representation;
- be able to model simple domains in a logic-based language;
- understand the notion of a reasoning service;
- master the fundamentals of the reasoning algorithms underlying current systems;
- understand the fundamental tradeoff between representation power and computational properties of a logic-based representation language;
- be conversant with several widely used knowledge representation languages; and
- understand how the theoretical material covered in the course is currently being applied in practice.
Prerequisites
Students taking this course should have completed the first year Logic and Proof course (or an equivalent course in a different institution). Students would benefit from taking the third year Computational Complexity course as well as the second year Databases course; however, this is not a requirement.
Synopsis
[if gte mso 9]>
1.- Introduction
The need for formal languages for representing (machine-understandable) knowledge. Reasoning services and logic-based reasoning. High level architecture of KR&R systems.
2. - Propositional Logic
Syntax and semantics of propositional logic. Notions of satisfiability, validity, and entailment. Reasoning based on model enumeration. Normal forms.
3. - Reasoning in Propositional Logic
Propositional resolution. The DPLL algorithm.
4.– Representing Knowledge in First Order Predicate Logic
Limitations of propositional logic for knowledge representation. Syntax and semantics of first order logic. Knowledge engineering using first order logic.
5 and 6. – Reasoning in First Order Predicate Logic
Reasoning in first order logic. Normal forms, Herbrand interpretations and Herbrand's theorem. Undecidability of the satisfiability and validity problems. Resolution in first order logic.
PART 2: FRAGMENTS OF FIRST ORDER LOGIC
7.- Description Logics
Description logics as fragments of first order logic. Syntax and semantics.
8, 9 and 10.- Reasoning in Description Logics
Terminological and data-oriented reasoning in description logics. Tableau-based algorithms. Optimisation techniques and practical reasoning.
11.- Lightweight description logics.
The description logics EL and DL-Lite.
12.- Horn Fragments of First Order Logic.
Propositional and first order Horn fragments. Horn fragments without function symbols. Resolution with free selection. Forward and backward chaining reasoning.
13.- Other Decidable Fragments of First Order Logic
The Bernays-Schoenfinkel prefix class. The Guarded fragment. The 2 Variable Fragment.
PART 3: NON-MONOTONIC LOGICS
14.- Non-monotonicity
Classical vs non-monotonic logic. Ways to achieve non-monotonicity.
15.- Stable Model Semantics
Non monotonic semantics via stable models.
APPLICATIONS
16. Ontology Languages and the Semantic Web
Introduction to Semantic Web languages such as RDF and OWL.
Syllabus
Representing knowledge using logic. Reasoning techniques in propositional and first order logic. Fundamental tradeoff between representation power and computational properties. Fragments of first order logic suited for Knowledge Representation. Ontology languages for the Semantic Web. Non-monotonic logics.
Reading list
Relevant for Part 1:
- Knowledge Representation and Reasoning. Ronald Brachman and Hector Levesque. The Morgan Kaufmann Series in Artificial Intelligence, 2004.
- First Order Logic and Automated Theorem Proving. Melvin Fitting. Texts in Computer Science. 1995.
- Handbook of Knowledge Representation. Frank van Harmelen, Vladimir Lifschitz and Bruce Porter (Eds). Foundations of Artificial Intelligence, 2008.
Relevant for Part 2:
- The Description Logic Handbook: Theory, Implementation and Applications, 2nd Edition. Franz Baader, Diego Calvanese, Deborah L. MacGuinness, and Daniele Nardi. Cambridge University Press. 2007.
- Foundations of Semantic Web Technologies. Chapman & Hall/ CRC Textbooks in Computing. Pascal Hitzler, Markus Kroetsch, and Sebastian Rudolph, 2009.
Relevant for Part 3:
- Nonmonotonic Reasoning. Grigoris Antoniou. The MIT Press, 1997.
- Bridges Between Classical and Nonmonotonic Logic. David Makinson. Texts in Computing. 2005.