Preferential Reasoning for Ontologies

Michael Harrison and Reid Swan

Motivation

The aim of the project is to implement an ontology editing environment for a form of non-classical reasoning known as preferential reasoning. Preferential reasoning is a logical system, based on classical reasoning, that is able to deal with inconsistent ontologies in a systematic and well defined manner. The system needs to allow the user to assign rankings to statements (based on exceptionality) and take these rankings into account when querying the knowledge base. This system would provide a basis for intelligent systems that are capable of dealing with preference.

Theory

The core of the theory section is a set of theorems detailing various characteristics of user-defined rankings. A more detailed overview can be found on the Theory page. Rational closure is an algorithm designed by Lehmann and Magidor1 to satisfy a set of postulates known as the KLM postulates and rational monotonicity, defined by Kraus, Lehmann and Magidor2 and motivated to be rules that any rational non-monotonic reasoning system should satisfy. Rational closure automatically computes a ranking of statements for use in reasoning. A theorem presented in the paper, however, shows that the KLM postulates and rational monotonicity hold when reasoning with an arbitrary ranking of statements:

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

In the paper, dense rankings are defined, which are essentially user-defined rankings with the property that no two adjacent ranks are equivalent. It is shown that every user-defined ranking has an equivalent dense ranking, and an algorithm is given for finding this. A result is then presented about when two dense rankings entail the same set of statements: only when they have the same number of ranks, and corresponding ranks are equivalent.

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

Following this, the redundancy of statements in a ranking is discussed; in other words, identifying when statements can be removed from a ranking without effecting the set of statements it entails. 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. It is shown that for dense rankings, these can be related, because a statement is locally redundant at the highest rank at which it is present if and only if it is totally redundant.

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

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.

Implementation

Our implementation of preferential reasoning was carried out in the form of an independant ontology editor and reasoner. The aim of this was to create a tool specifically suited to creating, ranking, and querying defeasible knowledge bases.

Ontology editor
The software tool allows users to create new OWL ontologies using Manchester Syntax. An OWL ontology is equivalent to a Description Logics knowledge base. Manchester Syntax is similar to natural language, allowing a user to edit and query the ontology without knowledge of Description Logics.

Denoting defeasibility
Users are able to denote whether a statement, or axiom, is strict or defeasible. A defeasible statement is weaker than a strict statement. The defeasible equivalent of Birds always fly is Birds typically fly. This allows for exceptions to be handled, whilst still maintaining a general rule.

Assigning rankings
The interface allows users to rank defeasible statements in the ontology. This ability allows users to have a finer grained control on the ontology by being able to define levels of exceptionality amongst statements.

Querying the ontology
The key function of the software tool is the ability to perform Preferential Reasoning. A user is able to enter a query in Manchester Syntax. The tool then checks if the query is in the Rational Closure of the ontology/knowledge base. If the query is in a Rational Closure of the knowledge base, then it is preferentially entailed by the knowledge base.

1Daniel Lehmann and Menachem Magidor. 1992. What does a conditional knowledge base entail? Artificial intelligence 55, 1 (1992), 1–60.
2Sarit Kraus, Daniel Lehmann, and Menachem Magidor. 1990. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial intelligence 44, 1-2 (1990), 167–207.