Belief Change, from AGM to realistic models

20-24 August 2001 (second week)

Type: Introductory Course

Lecturers: Andreas Herzig and Renata Wassermann

Prerequisites: Propositional logic

Abstract:

Belief revision has been extensively studied during the last twenty years. Given an agent with a set of beliefs, how should he change his beliefs when confronted with new information? An agent may be a human being, a computer program or any kind of system to which one can ascribe beliefs and from which one would expect rational reactions.

The aim of the course is to provide the students a basic background in the existing theories of belief revision and update as well as to give an overview of current research in the area. We will start from the by now standard paradigm for belief revision, due to Alchourrón, Gärdenfors and Makinson (AGM). AGM theory provides good formal results, but it deals with very idealized agents. We will proceed presenting alternatives and refinements that have been proposed in order to model more realistic agents. We will present models that represent the agent's belief state by finite sets of formulas (belief bases) and that deal with limitations of available resources (time, memory, logical ability).

These theories deal with the case where the world has not changed, only the agent got to know more about it. But an agent may also receive new information concerning changes that have occurred in the world. The operation of accommodating such information is called update. Katsuno and Mendelzon have provided a formal analysis of updates. Their approach generalizes several update operations that have been proposed in the field of database theory.

Course Description:

Lecture 1: Standard AGM theory.: In this first lecture, we motivate the course by means of examples and introduce the standard theory for belief revision. We present the AGM postulates for revision and contraction and some of the construction that were proposed in the literature. We then discuss the shortcomings of the AGM paradigm as a model for realistic agents.
Lecture 2: Base revision.: In the second lecture, we deal with models of belief revision in which the belief state of an agent is represented by a finite set of formulas - a belief base. This has advantages in terms of expressivity and computability. We present several operations for changing belief bases.
Lecture 3: New trends in belief revision.: In this lecture, we discuss recent works that address some of the problems found when trying to apply belief revision theory to real problems. One such problem is the limitation in the availability of resources such as memory, time, and logical ability. We present some proposals to solve this problem which involve inconsistency tolerance, approaches based on relevance, and approximate reasoning.
Lecture 4: The theory of update.: We discuss the difference between revision and update, and establish the link with conditional logics. We introduce the KM postulates for update, and the construction based on partial preorders. We finally discuss some shortcomings.
Lecture 5: Computational models of update.: The last lecture addresses more practical issues of update, including complexity results, decision procedures, and algorithms.

Course material: