Variable−Strength Conditional Preferences for Ranking Objects in Ontologies

Abstract

We introduce conditional preference bases as a means for ranking objects in ontologies. Conditional preference bases consist of a description logic knowledge base and a finite set of conditional preferences, which are statements of the form "generally, in the context φ, property α is preferred over property ¬α with strength s". They are inspired by variable-strength defaults in conditional knowledge bases. We define the notion of consistency for conditional preference bases, and we show how consistent conditional preference bases can be used for ranking objects in ontologies, where every object represents essentially a set of individuals that are sharing the same ranking-relevant properties. More concretely, we define two object rankings, denoted κ^sum and κ^lex, which evaluate the strengths of conditional preferences in an additive and a lexicographic way, respectively. Furthermore, we provide algorithms for the main computational tasks for ranking objects under conditional preference bases, we analyze the complexity of these tasks, and we delineate a tractable special case. To give evidence of the usefulness of this approach in practice, we describe two applications in the areas of product and literature search, where it allows especially for a flexible user-defined ranking of the query results reflecting personal preferences.