Preferential Reasoning for Ontologies

Michael Harrison and Reid Swan

Theory

What follows is a high-level overview of the theory section of the project. The paper linked in the sidebar presents a rigorous discussion of everything presented on this page, as well as containing an appendix with proofs of all claims presented here. It should be the first reference for clearer or more in-depth discussions on the content of this page.

Background

Description logics are a family of logic languages used to represent knowledge in terms of concepts, roles and individuals. A set of description logic statements form a knowledge base. Using a precise semantics, it is possible for an automated system to use the information represented in the knowledge base to derive conclusions.
However, classical entailment is hampered by the monotonicity property, which states that once a conclusion has been drawn or a statement is entailed, no extension of the knowledge base will cause that conclusion to be retracted. To illustrate this, we consider the example of Whales. A Whale is a Mammal. Mammals are LandDwellers. Whales are SeaDwellers, and SeaDwellers are not LandDwellers. While it is easy to revise our mental models to attain a consistent model of this situation (Whales are an exceptional type of Mammal), a reasoner, constrained by monotonicity, will always see Whales as inconsistent.
The solution to this is to use a non-monotonic reasoning system. One such system is preferential reasoning, proposed by Kraus, Lehmann and Magidor1. Instead of defining an entailment procedure, they proposed how any rational non-monotonic reasoner should behave in a set of inference rules known as the KLM postulates and rational monotonicity. Rational closure was defined in a follow up paper by Lehmann and Magidor2 to be the minimum set of statements entailed by any non-monotonic reasoning system. The algorithm to compute rational closure constructs a ranking of a given set of defeasible axioms based on their exceptionality, and uses this construction to determine if statements are entailed.
It is possible, however, to supply a user-defined ranking to this entailment procedure. The goal of the theoretical part of this project was to characterize what happens when a user-defined ranking is supplied to this procedure.

User-defined rankings are rational

A ranking is defined as a partition of the set of defeasible axioms in a conditional knowledge base into a set of ranks, with each of these ranks being given an index from 0. One of the initial major results of the paper is presented in theorems 4.5 and 4.6:

Theorems 4.5 & 4.6:
Any user-defined ranking satisfies the KLM postulates and rational monotonicity.

This means that it is possible for a user to define their own ranking of statements and reason with it without any changes, without losing out on the desirable properties of the KLM postulates and rational monotonicity. This ranking allows the user to indicate a preference on statements - in other words, to define which statements they view as the most important - and the reasoner will respect this preference while adhering to the KLM postulates and rational monotonicity. This results in more intuitive modelling, and allows the user to communicate some knowledge of the situation being modelled which is not easily communicated using only rational closure.

Equivalence of user-defined rankings

Two rankings are defined to be equivalent if and only if they entail the same sets of statements. In order to present a strong result about when two rankings are equivalent, the concept of a dense ranking is introduced. A dense ranking is one in which no two adjacent ranks are equivalent to each other. It is also shown that every ranking has an equivalent dense ranking, and an algorithm is presented for finding this dense ranking. The major result in this section is theorem 5.11

Theorem 5.11
Two dense rankings are equivalent if and only if they have the same number of ranks, and corresponding ranks are equivalent

This results shows that beyond finding a dense ranking, not much can be done to reduce the size of a given ranking without changing the set of entailed statements in some way. Since the running time and complexity of the entailment algorithm is (exponentially) proportional to the size of the ranking, we would wish to reduce these sizes as much as possible. However, this result shows that beyond finding the dense ranking, there is little that can be done in this regard while also preserving the set of entailed statements.

Redundancy of statements

The discussion then moves to redundant statements; in other words, those statements which can be removed from a ranking without effecting the set of statements it entails. By identifying those statements which can be safely removed from a ranking, we can reduce the size of the ranks themselves. The complexity of classical entailment checking is ExpTime-complete as per Lutz3, and our non-monotonic entailment checking reduces to a set of classical entailment checks with the given ranks, so reducing the size of these ranks will effect the algoriths running time.
A statement is locally redundant for a given rank if that rank is the same with or without the statement. A statement is totally redundant if it can be removed from the entire ranking without effecting the set of entailed statements.

Theorem 6.4
A statement is totally redundant if and only if it is locally redundant at the highest rank at which it is present

Due to this result, we can determine if a statement can be safely removed by performing a single check for local redundancy at the highest level at which a statement is present in a dense ranking.

Rankings are as powerful as rational closure

The last core result of the paper is a result showing that Lehmann and Magidor's rational closure is essentially equivalent to reasoning with user-defined rankings, because given the right inputs, rankings can simulate rational closure, and rational closure can simulate any rankings.

Theorem 7.1
For every user-defined ranking, there exists a conditional knowledge base from which rational closure will construct an equivalent ranking.

This result demonstrates that we do not gain any explicit reasoning advantage by working with rankings as opposed to using rational closure directly, and it might be argued that these rankings are therefore a redundant construction. However, rankings still retain some advantages.
  • Modelling with rankings is intuitive and allows the user to specify their preferences on axioms intuitively; by comparison, the construction by which a ranking can be simulated in rational closure is complicated and messy.
  • By taking the ranking specified by a user, we reduce the total required computation time by not having the ranking be generated

1Sarit Kraus, Daniel Lehmann, and Menachem Magidor. 1990. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial intelligence 44, 1-2 (1990), 167–207.
2Daniel Lehmann and Menachem Magidor. 1992. What does a conditional knowledge base entail? Artificial intelligence 55, 1 (1992), 1–60.
3Carsten Lutz. 2008. The complexity of conjunctive query answering in expressive description logics. Automated Reasoning (2008), 179–193.