Introducing Ontological CP-Nets

Tommaso Di Noia, Thomas LukasiewiczURSW 2012 · OpenReview

Abstract

As the Semantic Web evolves, the need for sophisticated user preference modeling becomes critical. This paper introduces Ontological CP-nets, a novel framework that integrates qualitative preference modeling (CP-nets) with formal background knowledge (Ontologies). By defining preference variables as logical concepts within Description Logics, the authors enable preference structures that are logically consistent with domain-specific constraints.

Introduction

The transition toward "Web 3.0"—a synthesis of the Social and Semantic Webs—necessitates systems capable of filtering vast amounts of data based on nuanced user preferences. Traditionally, researchers have used CP-nets (Conditional Preference Networks) to model qualitative preferences, such as "I prefer a hotel near the beach over one near the airport, provided it has a pool."

However, standard CP-nets operate in a vacuum. They lack awareness of semantic relationships—for instance, that a "Scooter" is a type of "Motorcycle" or that certain choices are logically incompatible. To bridge this gap, the authors propose embedding CP-nets within an Ontology (expressed in Description Logics), ensuring that user preferences respect the underlying logical rules and constraints of the real-world domain.

Methodology

An Ontological CP-net is formally defined as a pair $(T, N)$, where $T$ represents a background ontology and $N$ is a CP-net. This integration requires several key technical shifts:

  1. Variable Domains as Concepts: Instead of simple binary values, variable values are satisfiable concepts within the ontology (e.g., ∃location.OnTheSea).
  2. Logical Equivalence and Disjointness: Preferences are evaluated based on logical identity proven by the ontology. For a preference to be valid, the chosen values must be logically distinct and satisfiable under the ontology's rules.
  3. Constraint Mapping: The authors adapt techniques from constrained CP-nets to translate preferences into logical clauses. Crucially, they add a requirement that the preference structure must account for "hidden" relationships defined in the ontology.
Formal structure of an Ontological CP-net, showing the dependency graph and associated Conditional Preference Tables (CPTs) using logical concepts.

Theoretical Framework and Key Insights

The integration of ontologies introduces several unique challenges and insights compared to standard preference modeling:

  • Implicit Constraints: The ontology may impose constraints not explicitly stated by the user. If a user prefers Option A over B, but the ontology dictates that A logically implies B, the preference structure must be adjusted to remain consistent.
  • Satisfiability: In standard CP-nets, preferences are generally always expressible. In an ontological context, a preference may be "unsatisfiable" if it contradicts background knowledge (e.g., preferring a "Cheap Luxury Suite" when the ontology defines "Luxury" as inherently "Expensive").
  • Outcome Ambiguity: Rather than a single assignment of values, an "outcome" in this framework is a set of logical models. The authors propose computing formulas that represent the set of all equivalent optimal outcomes.

Results and Complexity

The paper provides the first formal bridge between CP-nets and Description Logics. A significant finding is the impact on computational complexity. While finding the best outcome in an acyclic CP-net is typically linear, background knowledge can introduce implicit cycles in the dependency graph. These cycles can push the problem into NP-hard territory, requiring more sophisticated reasoning techniques such as Integer Linear Programming (ILP) encodings.

Furthermore, the authors establish "eligibility" criteria for CP-statements, noting that an ontology can render previously "undominated" outcomes unsatisfiable, necessitating more rigorous dominance testing.

Limitations and Future Work

While theoretically sound, Ontological CP-nets face challenges regarding computational overhead. Integrating Description Logic reasoning significantly increases the cost of finding optimal outcomes and testing dominance. Future research is needed to develop specialized algorithms capable of handling implicit cycles efficiently and to provide empirical evidence of scalability as ontologies grow in size and complexity.

Summary updated

BibTeX
@inproceedings{noia2012introducing,
  author = {Tommaso Di Noia and Thomas Lukasiewicz},
  title = {{Introducing Ontological CP-Nets}},
  booktitle = {URSW},
  year = {2012},
  url = {https://openreview.net/forum?id=OAvdvhydkV},
}
Figure