COMP521

Knowledge Representation

Aims

This module aims:

  • To introduce Knowledge Representation as a research area.
  • To give a complete and critical understanding of the notion of representation languages and logics.
  • To study modal logics and their use;
  • To study description logic and its use;
  • To study epistemic logic and its use
  • To study methods for reasoning under uncertainty

Syllabus

  1. Introduction to knowledge representation (KR), formalisms for KR and in particular propositional logic (1week).
  2. Introduction to modal and description logics (5 weeks):Modal logics: Syntax, semantics (Kripke models), model checking, theorem proving. Description logics: Syntax, semantics, satisfiability checking, expressive description logics
  3. Applications of modal logic: epistemic logic (3 weeks): One agent case: S5 models, specific properties; Multi-agent case: Modelling epistemic puzzles, reasoning about other's knowledge and ignorance, alternating bit protocols; Group notions of knowledge: Distributed knowledge, common knowledge,examples; Computational models: Interpreted systems
  4. Handling uncertain information through probability and decision theory 2 weeks): Sample spaces; independence; conditional probability; prior and posterior probabilities; random variables; decision theory for agent systems; Bayesian networks.

Recommended Texts

Epistemic Logic for AI and Computer Science, J.-J.Ch. Meyer and W. van der Hoek, Cambridge Tracts in Theoretical Computer Science 41, 1995.

S. Russell and P. Norvig: Artificial Intelligence: A Modern Approach. Prentice Hall (2003).

Learning Outcomes

At the end of the module, the student will:

  • be able to explain and discuss the need for formal approaches to knowledge representation in artificial intelligence, and in particular the value of logic as such an approach;
  • be able to demonstrate knowledge of the basics of propositional logic
  • be able to determine the truth/satisfiability of modal formula;
  • be able to perform modal logic model checking on simple examples
  • be able to perform inference tasks in description logic
  • be able to model problems concenring agents' knowledge using epistemic logic;
  • be able to indicate how updates and other epistemic actions determine changes on epistemic models;
  • have sufficient knowledge to build "interpreted systems" from a specification, and to verify the "knowledge" properties of such systems;
  • be familiar with the axioms of a logic for knowledge of multiple agents;
  • be able to demonstrate knowledge of the basics of probability and decision theory, and their use in addressing problems in knowledge representation;
  • be able to model simple problems involving uncertainty, using probability and decision theory;
  • be able to perform simple Hilbert-style deductions in modal and epistemic logic;
  • be able to use tableau based methods to do inference in description logic.

The module addresses learning outcomes 2, 3, 4, 5 and 6 for the MSc in Computer Science programme, and learning outcomes 2, 3, 4, 5 and 6 for the MEng in Computer Science programme.

Learning Strategy

Formal Lectures: Students will be expected to attend three hours of formal lectures in a typical week plus one hour supervised tutorial.

Private study: In a typical week students will be expected to devote six hours of unsupervised time to private study. The time allowed per week for private study will typically include three hours of time for reflection and consideration of lecture material and background reading, and three hours for completion of practical exercises.