Knowledge Representation and Reasoning

      -- Logic meets Probability Theory --


      Latest News
      • Start: 10th September, 2012 (Learning aims)
      • Resit exam: Monday 8th April, 2013, 10:45-12:45, Huygens 00.303 (note that this exam covers all the topics of the lectures)
      • Final mark is determined by: 60% exam (30% exam1 + 30% exam2) + 40% practical assignments (20% assignment I and 20% assignment II)
      • Deadline asssignment II: 21st January, 2013
      • Lecture notes and solutions to exercises are now available! (see below)
      • Preliminary marks for resit 8th April, 2013
      • Submission of assignments: through blackboard
      • Mock exam


      Knowledge representation and Reasoning is an AI course where we systematically study representation and reasoning methods with logic and probability theory as the canonical forms. In the end we show that 'never the twain shall meet' is no longer true in recent AI.

      Content of Lectures in 2012:

      The lectures constitute the backbone of the course. You need to understand (and not simply be able to reproduce) the content of the slides to pass the exam.
      • Lecture 1: Introduction (10th September, 2012) [Slides 1/page: PDF1; PDF2]
        Read Chapter 1 of lecture notes.
        Content of course, learning aims. Knowledge representation and reasoning is one of the core topics of artificial intelligence. Issue that are central are: (1) by means of what sort of languages can knowledge be represented; (2) what is the complexity of reasoning with representations in these languages? Complexity concerns whether reasoning can be done efficiently in general or not. For predicate logic reasoning is even undecidable (so we do not know whether the reasoning algorithm ever terminates with an answer). However, if we know beforehand that the knowledge in predicate logic is unsatisfiable (inconsistent) then reasoning is decidable: we know that in principle we may get a result, although it may take a long while. We also discussed applications and challenges.

      • Lecture 2: Revision of logic in AI (17th September, 2012) [Slides 1/page: PDF]
        See Appendix A, lecture notes
        Required background knowledge of logic needed in the course. Start reading these notes in the week of 10th September, 2012. You need to have read this until page 102! This lecture was meant to refresh your knowledge about propositional and predicate logic. Completely new was the resolution rule: a rule used in AI for reasoning with logic in order to draw conclusions.

      • Lecture 3 and 4: Logic Programming, Prolog (24th September and 1st October, 2012) [Slides 1/page: PDF]
        Logic programming offer a simple, basic view on AI. Any problem needs to be represented in terms of facts and rules. Solving a problem is done by querying a logic program. Prolog is the practical realisation of that idea.

        History and principles of Prolog and logic programming (complements slides of 24th September and 1st October, 2012) Read Chapter 2 of lecture notes. AILog (1st October, 2012) [Slides 1/page PDF: Overview AILog]

        Small AILog knowledge base on cardiology (Note mime type is ail)
        There is a close connection between knowledge representation, logic programming and Prolog. Logic programming is also the foundation for much recent work on relational learning. Covered are the basics of logic programming, Prologs and the AILog system. AILog is a knowledge representation and reasoning system based on Horn clause logic and probability theory. It will be used in two subsequent assigments for which you get a mark.

      • Lecture 5: Description logics and Frames (7th October, 2012) [Slides 1/page: PDF]
        Read Chapter 3, Section 3.1 and 3.2 of lecture notes.
        In recent years, partly due to the world-wide web, has seen an increasing interest in representing and reasoning with things that exist in the real world using special purpose logics.

      • Lecture 6: Model-based reasoning (22nd October, 2012) [Slides 1/page: PDF]
        Read Chapter 4, Section 4.1 and 4.2 of lecture notes.
        Model-based reasoning is a separate research area in AI with a focus on trouble shooting and diagnosis. This lecture focuses on the use of models of normal behaviour for diagnosis

      • Lecture 7: Model-based reasoning (continued) (29th October, 2012) [Slides 1/page: PDF]
        Read the paper by Reiter
        Model-based diagnosis is a typical example of a field where one has to think about optimisation of algorithms. It is also a form of non-monotonic reasoning, which one can prove by linking it to default logic. Finally it is shown that one can do a sort of reasoning where new observations or measurements are suggested to refine the previous solutions (hypotheses).

      • Lecture 8: Model-based reasoning (abduction) (5th November, 2012) [Slides 1/page: PDF]
        Read Chapter 4, Section 4.3 and 4.4 of lecture notes.
        This lecture looks at using knowledge of abnormal behaviour, expressed as causal knowledge, for diagnosis using a reasoning method, called abduction (= reasoning to the best explanation)

      • REVISION LECTURE AND ANSWERING QUESTIONS (12th November, 2012; LIN 5)
        As preparation for the first exam on 15th November, 2012, we give the opportunity to ask questions, and when needed we go through part of the lectures 1-6)

      • Lecture 9: Uncertainty reasoning I (19th November, 2012) [Slides 1/page: PDF]
        Read Chapter 5, Section 5.1-5.3 of lecture notes.
        We will make the journey from ideas underlying early rule-based approaches to reasoning with uncertainty to Bayesian networks.

      • Lecture 10: Uncertainty reasoning II (26th November, 2012) [Slides 1/page: PDF]
        Read Chapter 5, Section 5.3-5.4 of lecture notes.
        In this lecture we study modern probabilistic logic. Thus we are back to combining rules and uncertainty as in the early days, but now we do it properly!

      • Lecture 11: Situations and actions (3rd December, 2012) [Slides 1/page: PDF]
        Reference material [Brachman] and [situation calculus]

      • Lecture 12: Recap & vision (10th December, 2012) [Slides 1/page: PDF]
        Paper of David Poole (for example 5.3)

      Lectures Notes:

      • Lecture notes used in the course in 2012-2013 . These complement the slides and tutorial exercises. (You may bring the lecture notes together with the slides and your own lecture notes to the exam. Note that you are not allowed to bring the tutorial exercises to the exam.)

      Content of Practicals:

      Aim of the practical is to get you quickly familiar with the basics of logic programming, Prolog and AILog. You will need this understanding for the two assignments.
      • Prolog and AILog Practical manual [PDF]
        This manual contains the Prolog and AILog exercises you need to work through during the practical (Note that you have only 4 hours to work through them!)

      • SWI Prolog

      • Prolog and AILog exercises

      • AILog manual

      • AIlog system

      Assignments:

      There are two assignments

      • Practical assignment I: deadline 7th December, 2012
        You should start with assignment I, Task I and II, after the lecture on 22nd October. The warm-up exercises should be done before that (e.g. on Thursday, 11th October or later).
        • Prolog program (tp.pl) for consistency-based diagnosis to be used in the assignment
        • Example diagnosistic problem (diagnosis.pl)

      • Assignment II: deadline 21st January, 2013
        • AIlog system
        • Planner and situation calculus:
          • Planner (planner.pl)
          • Samples planning problem (sample-blocks.pl and sample-blocks-domain.pl)
          • Describing the domain: domain-template.pl and instance-template.pl

      Tutorials:

      The tutorials complement the lectures and are meant for you to check your understanding ot the material covered by the lectures.
      • Tutorial on 27th September, 2012 [Exercises PDF]

      • Tutorial on 25th October, 2012 on Description logics and frames [Exercises PDF]

      • No tutorial on 1st November, 2012

      • Tutorial on 8th November, 2012 on Model-based reasoning [Exercises PDF]

      • Exam on 15th November, 2012

      • Tutorial on reasoning with uncertainty, 29th November 2012 [Exercises PDF]

      • Solutions to some of the exercises



      Peter Lucas | Computing Science
      Radboud University Nijmegen

      Last updated: 25th September, 2012
      peterl AT cs.ru.nl