Introducing Ontological CP-Nets

Abstract

Preference representation and reasoning is a key issue in many real-world scenarios. Currently, there are many approaches allowing preferences to be assessed in a qualitative or quantitative way. The most prominent qualitative approach for representing preferences are CP-nets. Their clear graphical structure unifies an easy representation of user desires with nice computational properties when computing the best outcome. Here, we introduce ontological CP-nets, which allow the representation of preferences using a CP-net over an ontological domain, i.e., variable values are logical formulas constrained relative to a background domain ontology.

Motivation

In this section, we introduce some necessary preliminary notions and formalisms. Given a set of variables V , an outcome is an assignment to all the variables in V . A preference relation is a total pre-order over the set of outcomes. We write o1 o1 iff o1 is strictly preferred to o2, and o1 o2 iff o1 is strictly or equally preferred to o2; we then also say that o2 is dominated by o1. If there is no outcome o such that o o1, we say that o1 is undominated.

Conditional preference networks (CP-nets) [ 2 ] are a formalism to represent and reason with qualitative preferences. This compact but powerful language allows the specification of preferences based on the notion of conditional preferential independence. Fundamental for CP-nets is the notion of conditionally preferentially independent (CPI). Let P; Q 2 V be two variables and R V be a set of variables such that P , Q, and R partition V, and Dom(P ), Dom(Q), and Dom(R) represent all possible assignments for P , Q, and all the variables in R, respectively. We say that P is conditionally preferentially independent (CPI) of Q given an assignment r 2 R iff, for all p1; p2 2 P and q1; q2 2 Q, we have that p1q1r p2q1r iff p1q2r p2q2r. Here, represents the preference order among assignments for sets of variables. CP-nets are a graphical language to model CPI statements. Formally, a CP-net N consists of a directed graph G representing preference relations among variables Pi and a set of conditional preference tables CP T (Pi) (one for each variable). Given the set of variables V = fPi j i 2 f1; : : : ; ngg [ fPn+1g representing the nodes of G, such that Pi is a parent of Pn+1 in G, the corresponding CP T (Pn+1) contains a preference for each pair of values of Pn+1 conditioned to all possible assignments of variables Pi. The representation of a CP-net assumes that the user explicitly specifies her preferences over the values of Pn+1 for each complete assignment of Pi, with i 2 f1; : : : ; ng. Given a CP-net N , we denote by CPT i the set of all conditional preferences represented in CP T (Pi), and CPT N = fCPT i j i 2 f1; : : : ; ngg.

Given a CP-net, the two main queries one may ask are: – Dominance query: Given two outcomes o1 and o2, decide whether o1 o2. – Outcome optimization: What is the optimal outcome given the preferences represented in the CP-net? That is, we look for one of the undominated outcomes.

Given an acyclic CP-net, one can compute the best outcome in linear time. The algorithm just follows the order among variables represented by the graph and assigns values to the variables Pi from top to bottom satisfying the preference order in the corresponding CP T (Pi). Finding the optimal outcome in cyclic CP-nets is NP-hard.

In constrained CP-nets [ 5, 3 ], constraints among variables are added to the basic formalism of CP-nets. Adding constraints among variables may reduce the set of possible outcomes. The approach to finding the optimal outcome proposed in [ 5 ] relies on a reduction of the preferences represented in the CP-net to a set of hard constraints (which can be represented in clause form for binary variables) taking into account the variables occurring in the preferences. Given a CP-net N and a set of constraints C, an outcome o is feasible if it satisfies all the constraints in C. A feasible outcome is Pareto optimal [ 3 ] iff it is undominated. In [ 5 ], the authors present an algorithm to find the optimal outcome solving a constraint satisfaction problem. For binary variables, given a conditional preference (pn+1 :pn+1 j Vi=1:::n p~i), where p~i 2 fpi; :pig, the corresponding constraint is the clause Vi=1:::n p~i ! pn+1 (analogously, for (:pn+1 pn+1 j Vi=1:::n p~i), we have Vi=1:::n p~i ! :pn+1).

Given a CP-Net N and a set of constraints C, a feasible Pareto optimal outcome is an assignment satisfying the corresponding set of clauses and all the constraints in C (and vice versa). 3

Ontological CP-Nets

We now introduce a framework for preference representation harnessing the technologies described in the previous section. The idea is to combine CP-nets and ontologies represented in description logics (DLs) [ 1 ]. In this combination, variable values are satisfiable DL concepts. For ease of presentation, we describe our approach using variables whose domain contains only two values, i.e., two concepts; the extension to more than two concepts is straightforward.

Two conditional preferences ( j ) and ( 0 0 j 0) are equivalent relative to an ontology T iff T j= 0, T j= 0, and T j= 0.

Definition 1. An ontological CP-net (T ; N ) consists of an ontology T and a CP-net N such that: (1) for each variable P in N , Dom(P ) = f ; g, where and are DL concepts that are satisfiable relative to T , and such that T 6j= >, T 6j= >, and T 6j= ; (2) any two conditional preferences in CPT N are pairwise not equivalent.

Note that each variable P 2 V with Dom(P ) = f ; g may have one of the four values , : , , and : . That is, the variables are not strictly binary.

Example 1 (Hotel). Consider a simple ontology, describing the services offered by a hotel:

Scooter v Motorcycle

Motorcycle v :Bike 9rent.Scooter v 9facilities.(Parking u 9payment u 8payment.Free) :

A simple ontological CP-net is depicted in the following together with possible CP T s related to the nodes P1 and P2. The domains of P1, P2 and P3 are: Dom(P1) = f 1 = 9location.OnTheSea; 1 = 9location.NearTheAirportg Dom(P2) = f 2 = 9rent.Bike; 2 = 9facilities.(Parkingu9paymentu8payment.Free)g Dom(P3) = f 3 = 9rent u 8rent.Scooter; 3 = 9facilities.Shuttleg 8 ( 1 >>>> ( 1 <> ( 1 >>>> (( 11 >: (: 1 : 1)

1) : 1) : 1) : 1) : 1) CP T (P1) =

CP T (P2) = 8 ( 2 >< ( 2

( 2 >: ( 2 2 j 1) 2 j : 1) 2 j 1) 2 j : 1) :

Although we know how to reason with expressive DLs and with CP-nets, their combination leads to diverse issues both from the modeling and the reasoning perspective. We now sketch the main ideas behind our approach, using illustrative examples whenever possible. Implicitly constrained variables. Even if we do not have any explicit hard constraint expressed among the variables of the CP-net, due to the background ontology, we have a set of implicit constraints among and values of the variables V in the CP-net.

Example 2 (Hotel cont’d). Consider the ontology T of Example 1 and the two variables P2 and P3. Because of T , we have the implicit constraint T j= 3 v 2.

One way to infer all possible constraints among variable values is to adopt the ontology compilation technique presented in [ 7 ]. There, the authors propose an algorithm to elicit all possible hidden constraints (represented in clausal form) occurring among a set of DL concepts. Preference satisfiability. Following [ 5 ], for each preference = ( ~ ~ j ) 2 CPT N , we may write the clause: ! ~ (i.e., : t ~). In ontological CP-nets, this is not sufficient. Indeed, since and belong to the domain of the same variable, we have to explicitly state that they are disjoint with each other relative to T . Hence, for each preference we have to add one more clause of the form ~ ! : ~. This may also lead to unsatisfiable clauses. Example 3 (Hotel cont’d). Consider the preference (not allowed by the CP-net represented in Example 1) = ( 3 2 j : 1). If we imposed 3 ! : 2 then we had T j= (: 1 ! 3) u ( 3 ! : 2) v ?. In fact, we know that T j= 3 v 2. That is, we are saying that is never satisfied.

Hence, the preference is satisfiable iff T j= ( ! ~) u ( ~ ! : ~) 6v ?. The notion of satisfiability can be extended also to the whole CP-net.

Definition of outcome. In a constrained CP-net, if we had propositional true/false variables, an outcome would be a model, i.e., a true/false assignment that satisfies all the constraints and some of the clauses built starting from the preferences represented in CPT N . In ontological CP-nets, we deal with DL concepts, so a model satisfying the constraints cannot be explicitly represented. Actually, we have more than one equivalent outcome, i.e., all the models that satisfy the same preferences. A solution to this issue is to compute a formula whose models satisfy the same preferences. Also, in this case, such formula can be computed by adapting the techniques proposed in [ 7 ], where the preference satisfaction problem for DL concepts is solved via Integer Linear Programming encoding.

Dominance test and eligibility of CP-statements. A set of conditional preferences (CPstatements) is eligible iff it has an undominated outcome. In case of a set of eligible CPstatements, once we introduce an ontology to describe the background knowledge we can make the undominated outcome unsatisfiable. Then we have to be very careful when evaluating the dominance test among a set of possible outcomes of the CP-net. In fact, in case we have cycles in the dependency graph [ 2 ] associated to the CP-net, due to the presence of an ontology, we could be unable to find an undominated outcome.

Complexity of reasoning. As also argued in [ 5 ], having background knowledge may introduce implicit cycles in the graph representing the CP-net. This affects the computational complexity related to the computation of an outcome. 4

Conclusion

The availability of semantic information over the Web and the social revolution, pave the way to a new wave of personalized applications where ontological knowledge plays a fundamental role. User’s preferences may act as a filter to the information accessed by the user in order to provide a personalized experience while interacting with the Semantic Web. Among the various formalisms proposed in the literature to represent preferences, a very promising one is that of CP-nets. They have a strong theoretical background and many results are already available in the literature both related to their computational properties and to modeling aspects. Nevertheless, to the best of our knowledge, almost nothing has been done to combine CP-nets with ontological modeling and reasoning. In this paper we introduce the notion of Ontological CP-nets and highlight some issues related to the ontological nature of the information we deal with when combined with conditional preferences arranged in a CP-net.

Acknowledgments. This work was supported by the EPSRC grant EP/J008346/1 (“PrOQAW”), the ERC under the EU’s 7th Framework Programme (FP7/2007-2013/ERC) grant 246858 (“DIADEM”), a Google Research Award, and a Yahoo! Research Fellowship. Tommaso Di Noia also acknowledges support by HP IRP 2011, grant CW267313.

References

1. F. Baader , D. Calvanese , D. L. McGuinness , D. Nardi , and P. F. Patel-Schneider . The Description Logic Handbook: Theory, Implementation, and Applications . Cambridge University Press, 2003 .

2. C. Boutilier , R. I. Brafman , C. Domshlak , H. H. Hoos , and D. Poole . CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements . JAIR , 21 : 135 - 191 , 2004 .

3. C. Boutilier , R. I. Brafman , C. Domshlak , H. H. Hoos , and D. Poole . Preference-based constrained optimization with CP-nets . Comput. Intell. , 20 ( 2 ): 137 - 157 , 2004 .

4. C. Domshlak , E. Hu¨llermeier, S. Kaci, and H. Prade . Preferences in AI: An overview . Artif. Intell., 175 ( 7 /8): 1037 - 1052 , 2011 .

5. C. Domshlak , S. Prestwich , F. Rossi , K. B. Venable , and T. Walsh . Hard and soft constraints for reasoning about qualitative conditional preferences . J. Heuristics , 12 ( 4 /5): 263 - 285 , 2006 .

6. T. Lukasiewicz and J. Schellhase . Variable-strength conditional preferences for ranking objects in ontologies . J. Web Sem ., 5 ( 3 ): 180 - 194 , 2007 .

7. A. Ragone , T. D. Noia , F. M. Donini , E. D. Sciascio , and M. P. Wellman . Weighted description logics preference formulas for multiattribute negotiation . In Proc. SUM-2009 , pp. 193 - 205 , 2009 .