Knowledge Representation & Reasoning: 2011-2012
Lecturer | |
Degrees | Schedule B2 — 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.
Feedback
Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.
Taking our courses
This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses
Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.