Knowledge Representation & Reasoning: 2010-2011
Lecturers | |
Degrees | Schedule B2 — Computer Science |
Term | Hilary Term 2011 (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
PART 1: KR&R WITH PROPOSITIONAL AND FIRST ORDER LOGIC
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 FOL. Representation of a domain using FOL with special emphasis on the knowledge engineering aspects.
5 and 6 – Reasoning in First Order Predicate Logic
Resolution and tableaux for FOL. Undecidability of the satisfiability and validity problems. Fundamental tradeoff between representation power and computational properties.
PART 2: FRAGMENTS OF FIRST ORDER LOGIC
7 and 8. Horn Predicate Logic (Datalog)
Datalog as a KR language. SLD resolution and backwards chaining. Bottom-up reasoning, semi-naive evaluation. Computational properties. Connection with Prolog. Horn fragment of propositional logic and its computational properties.
9. Description Logics and the Ontology Languages for the Semantic Web
Motivation via semantic networks and frame systems. The basic description logic ALC. Relevant reasoning problems. Extensions of ALC. The vision of the Semantic Web and the ontology languages OWL and OWL 2.
10 and 11 Reasoning in Description Logics
Tableaux-based and resolution algorithms. Tree model property. Decidability and computational properties. Relationship with first-order tableaux and resolution.
12. Sub-boolean DLs
Motivation. Sub-boolean DLs and the OWL 2 Profiles. Reasoning in Sub-boolean DLs.
13 Recapitulation
Relationships and differences between fragments of FOL discussed thus far. Relationships between various reasoning problems in different logics. Relationship with Databases.
PART 3: NON-MONOTONIC LOGICS
14 Non-monotonicity
Classical vs non-monotonic logic. Ways to achieve non-monotonicity.
Defaults, autoepistemic logic and circumscription.
15 Default reasoning
Operational semantics and default extensions. Normal default theories.
16 Non-monotonic extensions to Datalog
Non-monotonic reasoning and logic programming. Adding negation to Datalog. Stable and well-founded semantics.
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.
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.