A New Look at the Semantics and Optimization Methods of CP-Networks

1 Introduction

Ceteris Paribus (CP) preference statements are among the most natural and most intuitive preference statements that people make. Thus, it is not surprising that they have drawn the attention of many researchers in philosophy and AI (e.g., [Doyle and Wellman, 1994; Hanson, 1996]). CP statements indicate a preference for one value over another in the con­ text of a fixed background. For example, the statement "I prefer an apple pie to a chocolate cake as a dessert, ceteris paribus" expresses the fact that given two identical contexts -i.e. , meals- that differ only in their dessert, the one contain­ ing an apple pie is preferred to the one containing a chocolate cake. Finer distinctions can be made using conditional CP statements. For example: "I prefer red wine over white wine if the main course is beef." In this case, the preference for red wine to white wine is restricted to comparisons between identical meals in which the main course is beef.

CP-nets [Boutilier et al., 1999] are a graphical tool for rep­ resenting and for structuring a set of CP statements. A CP­ network consists of a graph describing the preferential depen­ dency relationship between different domain variables. Each node is annotated by a conditional preference table (CPT) that describes how the user's preference over the different values

Yannis Dimopoulos

Dept. of Computer Science University of Cyprus Nicosia 1678, Cyprus

yannis®cs.ucy.ac.cy

of the variable associated with this node depends on the vari­ ables associated with the parents of this node.

Cyclic CP-nets emerge naturally when there is a set of in­ terdependent variables, none of which is more important than the other. For example, [Domshlak et al., 2001] note that such dependency can emerge naturally among web-page compo­ nents in their web-personalization tool. Cyclic CP-network raise some conceptual and computational problems to which we still do not have satisfactory answers. Even worse, accord­ ing to the standard semantics of CP-nets, most cyclic CP-nets are inconsistent. For example, in [Domshlak and Brafman, 2002], it was shown that the preference ordering induced by any simple cycle (i.e, a cycle that does not contain smaller cy­ cles) with more than two nodes is inconsistent. That is, there will be at least two outcomes, o1 and o2 , such that one can show that o1 is strictly preferred to o2 and o2 is strictly pre­ ferred to o1 . In addition, whereas for acyclic networks one can determine the most preferred outcome in linear time even in the face of evidential constraints (i.e., constraints that fix the value of certain variables), no corresponding algorithm is known for networks that contain cycles.

The fact that many cyclic networks are inconsistent raises a serious practical concern. When a user specifies an incon­ sistent cyclic network, we must ask him to revise his network. To do so, we need to provide information that will help him obtain a consistent network. In this paper we make two prac­ tical contributions aimed at improving this process. First, we show that various optimization queries can be answered nat­ urally even when the network is "inconsistent" according to the standard semantics. In such cases, no additional burden is placed on the user. Second, when revision is required, we show how the notion of a partial model, studied in the area of logic programming, can be used to identify those aspects of a model that require revision.

While pursuing our more practical goals we make a num­ ber of technical and semantic contributions. First, we pro­ vide a more flexible semantics for CP-nets that is identical with the current semantics on those networks the latter con­ siders consistent. This semantics justifies our approach for generating optimal outcomes given networks that are incon­ sistent under the standard semantics. Second, we show how to answer optimization queries using various approaches that include reduction to SAT, and reduction to logic programs. This extends current methods which are restricted to acyclic nets, and helps us define the notion of a partial outcome.

The paper is structured as follows: In Section 2 we pro­ vide the necessary background on ceteris paribus preference statements and CP-nets. In Sections 3 and 4 we take a closer look at the notion of consistency in CP-nets and the problem that cyclic networks introduce, we suggest a natural defini­ tion of a preferred model as one that cannot be improved, and explain how the problem of the existence of such models can be reduced into a CSP problem. In Section 5 we discuss an alternative translation into nonmonotonic logic programs and some of its implications, and in Section 6 we conclude. The full version of this paper is available from the authors' web site. It contains proofs, an optimization method based on cut­ set conditioning, a discussion of constrained optimization and other inference tasks, and a comparison with logic programs with ordered disjunction [Brewka et al., 2002].1

2 CP-Nets

We start with a review of ceteris paribus preference state­ ments and preferential independence, followed by the defini­ tion of CP-nets.

2.1 Ceteris Paribus Preference Statements

A preference relation is a total pre-order (a ranking) over a set of outcomes. Given two outcomes o, o', we write o ~ o' if o is at least as preferred as o' and we write o >- o' if o is strictly more preferred than o'.

The types of outcomes we are concerned with consist of possible assignments to some set of variables. More formally, we assume some given set V = {X1 , ... , Xn} of variables with corresponding domains D(X1), ... , D(Xn). The set of possible outcomes is then 1J(X1 ) x · · · x D(Xn)· For exam­ ple, in the context of the problem of configuring a personal computer (PC), the variables may be processor type, screen size, operating system etc., where screen size has the domain { 17in, 19in, 21 in}, operating system has the domain { LJNUX, Windows98, WindowsXP}, etc. Each assignment to the set of variables specifies an outcome - a particular PC configura­ tion. Thus, a preference ordering over these outcomes speci­ fies a ranking over possible PC configurations.

The number of possible outcomes is exponential in n, while the set of possible total orders on them is doubly ex­ ponential in n. Therefore, explicit specification and represen­ tation of a ranking are not realistic. We must find implicit means of describing this preference relation. The notion of conditional preferential independence plays a key role in such representations. Intuitively, X and Y are conditionally pref­ erentially independent given Z (where X, Y, Z are disjoint subsets of V) if for every fixed assignment to Z, the ranking of X values is independent of the value of Y. Formally, let X, Y and Z be a partition ofV and let z E D(Z). X andY are conditionally preferentially independent given z iff, for all x1, x2, Yl, Y2 we have that

X and Y are conditionally preferentially independent given Z if they are conditionally preferentially independent given any assignment z E D(Z). In our PC example, the user may assess operating system to be independent of other features given processor type. That is, it always prefers LINUX given an AMD processor and Windows98 given an Intel processor (e.g., because he believes Windows98 is optimized for the Intel processor, whereas LINUX is otherwise better). Condi­ tional preferential independence is a standard notion in multi­ attribute utility theory [Keeney and Raiffa, 1976].

1 A note on notation. Due to the difficulty of using the logical negation operator, ·, in drawing packages, we use two alternative notations: a instead of ·a, and al, a2 instead of a, ·a.

2.2 CP-nets

CP-nets were introduced in [Boutilier eta!., 1999] as a tool for compactly and intuitively representing qualitative pref­ erence relations. This graphical model exploits conditional preferential independence in structuring a decision maker's preferences under ceteris paribus (all else being equal) se­ mantics. CP-net is the first model based on the notions of purely qualitative preferential independence, and bears a sur­ face similarity to Bayesian nets [Pearl, 1988]. However, the nature of the relationship between nodes within a CP-net is generally quite weak compared with the probabilistic rela­ tions in Bayes nets.

During preference elicitation, for each variable X in the variable set V, the decision maker is asked to specify a set of parent variables Pa(X) that can affect her preferences over the values of X. That is, given a particular value assignment to Pa(X), the decision maker should be able to determine a preference order over the domain of X (denoted as D(X)), all other things being equal.

The above information is used to create the graph of the CP-net in which each node X has Pa(X) as its immediate predecessors. Given this structural information, the decision maker is asked to explicitly specify her preferences over the values of X for each instantiation of Pa(X). This conditional preference over the values of X is captured by a conditional preference table (CPT) which is annotated with the node X in the CP-net. That is, for each assignment to Pa(X), CPT(X) specifies a total order (denoted >-) over D(X), such that for any two values Xi, Xj E D(X), either Xi >- Xj, or Xj >-Xi.

Formally, a CP-net N over variables V = {X 1 , ... , X n} is a directed graph G over X 1 , ... , Xn and a set of condi­ tional preference tables CPT(Xi) for each Xi E V. Each conditional preference table CPT(Xi) associates a total or­ der>- j ( Uj) OVer the domain of Xi with each instantiation Uj of Xi's parents Pa(Xi) = U.

The semantics of CP-nets is defined as follows. A model for a CP-net is a total-order over the set of possible outcomes that satisfies every CPT within the CP-net. A total order sat­ isfies CPT(X) if for every pair of X -values Xi, x j and every assignment c to Pa(X) such that Xi >- Xj given c according to CPT( X), the following holds: Let o, o' be two outcomes that differ only in their assignment to X and satisfy c, and suppose that o assigns xi to X and o' assigns x j to X, then, o >- o' holds in the model. We say that o >- o' is valid ac­ cording to the CP-network if o >- o' holds in all models of the CP-net. A CP-net is said to be consistent if it has a model.

As an example, consider the network in Figure l(a), in which all variables are boolean. This network has three vari­ ables, A, B, and C. The preferences over A and Bare un­ conditional, whereas the preferences for C's values depend on the values of A and B. In Figure l(b), we see the pref­ erence order induced by this CP-network. For every pair of outcomes o, o', we have that o >- o' is valid iff there is a path from o' to o in this graph.

3 The Weak Preference Semantics

According to the standard semantics, the preferences ex­ pressed in the CPT of a CP-net are strict preferences. We suggest viewing them as weak preferences using pre-orders instead of strict orders. As we show, this leads to a semantics that is only slightly weaker than the standard semantics. In fact, it leads to identical orderings on CP-nets that are con­ sistent according to the standard semantics. More formally, a model for a CP-network is a total pre-order over the set of outcomes that satisfies every CPT within the CP-net. A to­ tal pre-order satisfies CPT(X) if for every pair of X -values Xi , Xj and every assignment c to Pa(X) such that Xi ?:: x1 given c according to CPT(X) 2 the following holds: Let o, o' be two outcomes that satisfy c and differ only in their assign­ ment to X, such that o assigns Xi to X and o' assigns x 1 to X . Then, o ?:: o' holds in the ordering. We say that o ?:: o' is valid according to the CP-network if o ?:: o' holds in all models of the CP-net. Finally, we say that o >- o' is valid according to the CP-network if o ?:: o' is valid but o' ?:: o is not valid. Thus, if o >- o' holds in all models and there is a model in which o >- ~~ holds, we say that o >- o' is valid. Had we required o >- o' to hold in all models foro >- o' to be valid, no strict preference would be valid. This is because the preference relation in which all outcomes are equally desir­ able is a model for every CP-network according to the above semantics. Thus, all CP-nets are "consistent" according to our semantics.

The above semantics can be related to a more syntactic no­ tion of a proof of preference, or a flipping sequence [Boutilier et al., 1999]. Let o be an outcome, and suppose that o as­ signs to X some value Xj that the user ranks lower than Xi in parental context c satisfied in o. Then, we can improve o by flipping the value of X from x1 to x;. An improvingflipping sequence o1 , o2, ... , ok is a sequence of outcomes such that Oi is obtained from Oi-l via a single improving flip. Natu­ rally, these definitions are with respect to some CP-network, which we take to be fixed by the appropriate context.

2 In the standard semantics we have x; >- Xj instead of x; t Xj.

Theorem 1 o ?:: o' is valid iff there is an improving flipping sequence from o' to o.

An immediate consequence is the following:

Consequence 1 o >- o' is valid iff there is an improving flip­ ping sequence from o' too but no improving flipping sequence from o too'.

Another interesting theorem relates the standard, stronger se­ mantics, and our semantics.

Theorem 2 Let G be a CP-network that is consistent accord­ ing to the standard semantics. Then, G satisfies o >- o' ac­ cording to our semantics iff G satisfies o >- o' according to the standard semantics.

This theorem shows that our semantics is a direct extension of the standard semantics. To understand it better, we will soon take a look at networks that are inconsistent according to the standard semantics.

Finally, we define the notion of optimality in the context of a CP-network. There are two possible definitions: An out­ come o is said to be strongly optimal iff there is no other outcome o' such that o' ?:: o holds. An outcome o is said to be weakly optimal iff there is no other outcome o' such that o' >- o holds. Thus, in the first case, o is either strictly bet­ ter than any other outcome or incomparable. In the second case, there may be other outcomes that are as preferred as o, but no outcome that is strictly preferred over o. In networks that are consistent according to the standard semantics, there is a unique best outcome that is strictly better than any other outcome. However, when we move beyond this class of net­ works, we can have more than one optimal outcome, and it can be either strongly or weakly optimal. The latter class is computationally more challenging to identify, and so we con­ centrate on strongly optimal outcomes.

4 Optimality in Cyclic Networks

The semantics of CP-nets allows for cycles. But only the consistency of acyclic CP-nets is guaranteed according to the standard semantics [Boutilier et al., 1999]. Moreover, such networks have a unique optimal outcome. This remains true even if we introduce evidential constraints, i.e., constraints that fix the value of some variables.

Cyclic networks often induce an inconsistent (i.e., cyclic) preference order according to the standard semantics. For ex­ ample, consider the network in Figure 2 which contains a cy­ cle of size 4, called a simple cycle in [Domshlak and Braf­ man, 2002]. The web-personalization applications described in [Domshlak et al., 2001] naturally gives rise to such cyclic structures. There, variables correspond to articles, ads, and other content element in an online newspaper. The value of each variable indicates whether it is currently displayed or not. The CP-net captures the preferences of the editor regard­ ing the presentation of different elements on the user's cur­ rent screen. These preferences together with user-generated content constraints lead to a personalized view that takes into account the user's interests and the editor's expertise on pre­ ferred combinations of news items. For example, in the CP­ net in Figure 2, A could be a review of a new Toyota 4x4 vehicle, B a test-drive of a new BMW series 7 car, C a story about a recent Man. United match, and D a story about Man. City's recent success. Suppose that Man. United is sponsored by Toyota, and Man. City by BMW, and the editor would pre­ fer not to display stories about competing teams and/or com­ panies in the same screen. This is expressed in the CP-net in Figure 2 by stipulating that if A is present then B should not, if A is not present then B should be present, etc.

In [Domshlak and Brafman, 2002] it is shown that such a network is not consistent, i.e., there is no total order of the set of outcomes that satisfies all the preferences embodied in this network. It is easy to see why this is so when we examine Figure 3 which describes the relationships among different possible outcomes. The nodes in that figure correspond to outcomes and the edges correspond to legal improving (sin­ gle) flips. For example, consider the outcome a2b2cld2 in the lower left-hand side of Figure 3. Given that A is assigned a2, we can see from the B's CPT that bl is a more preferred value for B. Thus, there is an edge from a2b2cld2 to a2blcld2.

We can see that Figure 3 contains cycles, making it impos­ sible to totally order its elements consistently. However, it is also apparent that it contains two elements, alb2cld2 and a2blc2dl that, in some sense, can be viewed as optimal ele­ ments, as well as two elements, alblcldl and a2b2c2d2, that in some sense can be viewed as the worst elements.

Indeed, according to our semantics, this network induces three classes of outcomes described in Figure 4. The out­ comes within each class are either equally preferred or in­ comparable, and there is a strict preference between outcomes belonging to different classes. An important consequence of this is that there are clear candidates for the set of optimal outcomes: the two outcomes in the top class.

We can see that our semantics is more lenient, allowing for specifications that, in some sense, are cyclic. If the cycle con­ tains all outcomes, then all outcomes are equally preferred. This specification is not informative, and the user needs to be informed of this fact. However, the example above shows that the cycle may contain some, but not all of the outcomes. Whereas the standard semantics will dismiss this CP-network as inconsistent, our semantics is more tolerant, and can use this CP-net to determine an optimal outcome.

We now turn to the computation of an optimal outcome via a simple reduction to a CSP problem (or a SAT problem when the variables are binary). The variables in our reduction consist of the variables in the CP-network. For every entry in the CP Table of every variable v, we add the constraint ¢ -+ VI, where ¢ denotes the context (i.e., the assignment to the parents of v) and VI is the preferred value of v.

As an example, for the CP-network in Figure 1 we obtain the following propositional formula.

Lemma 1 o is a strongly optimal outcome for a CP-net iff it satisfies the above CSP.

The above algorithm does not work when we have weakly optimal outcomes, i.e., when we have a set of outcomes that are equally preferred, but cannot be strictly improved. Fig­ ures 5 and 6 show an example of a network giving rise to such a case and the relation over the outcome space it induces. From now on, our treatment centers on strongly optimal out­ comes only, to which we simply refer as optimal outcomes.

Lemma 1 implies that the problem of finding a single op­ timal outcome is in NP. When the CP-network is acyclic, an optimal outcome can be found in linear time [Boutilier et al., ! 999]. Our result indicates a linear time solution for simple­ cycle nets, too, if the variables are binary, because the result­ ing CSP is an instance of 2-SAT [Aspvall et al., 1979].

5 Logic Programs and Partial Consistency

We start with some background on the semantics of logic programs, followed by a reduction of CP-net optimization to logic programs. Then, using the notion of a partial stable model of a logic program, we can define a corresponding no­ tion for a CP-net that captures those variables for which we have some reasonable candidate for an optimal value.

5.1 The Semantics of Logic Programs

A propositional normal logic program P is a set of normal rules. A normal rule is a rule of the form h +- ai,a2, ... ,an,not bi, not b2, ... , not bm where h, a I, a2, ... ,an, bi, b2, ... , bm are propositional atoms. The set of atoms of Pis denoted by Atoms(P). LetS be a truth or value assignment on the atoms of Atoms(P). We denote by s+ the set of atoms of s that are assigned the value true, and s- the set of atoms that are assigned the value false. The reduct pS of a logic program P w.r.t. an assignment S is the logic program obtained from P after deleting (i) every rule of P that has a negated atom not b;, with b; E s+ (ii) every negated atom from the body of the remaining rules.

The resulting program does not contain negated atoms, and is called a definite logic program. Let cl(P) denote the de­ ductive closure of a definite logic program P, which coin­ cides with its minimal model. A stable model [Gelfond and Lifschitz, 1988] of a logic program P is an assignment S, such that s+ = cl(P 5 ). A normal logic program may have none, one or several stable models. The problem of decid­ ing whether a normal logic program has a stable model is NP-complete, but many problems can be solved efficiently in practice by state-of-the art systems such as smodels [Surja­ nen and Niemela, 2001] and DLV [Dell' Armi et al., 2001].

An alternative semantics for normal logic programs is the partial stable model semantics [Sacca and Zaniolo, 1990]. This is a three-valued semantics, where each atom may as­ sume the values: true, false or undefined. Given a three­ valued assignmentS of Atoms(P), we say that Sis a partial model of P if for each ·A E s-, every rule with head A contains at least one literal Bin its body, such that -.B E S. The reduct P 5 of P w.r.t. a partial modelS is defined as the program that is obtained from P after deleting (i) every rule of P that has a negated atom not b;, with b; E s+ (ii) every rule where an undefined atom occurs (iii) every negated atom from the body of the remaining rules. A partial model S such that s+ = cl(P 5 ) is called afounded model of P . A maxi­ mal founded model is called partial stable model of P. It is not hard to see that every program has a partial stable model.

Example 1 Consider the program

a+-n~d b+-n~a c+-n~b d+-n~c This program has two stable models, namely MI = {a, c} and M2 = {b, d}. Consider now the program

a +- not c b +- not a c +- not b

d +- not e e +- not d

This program has two partial stable stable models, namely MI = { d} and M2 = { e}, but no stable model.

The intuition behind a founded model is similar to that be­ hind a stable model, except that we are willing to ignore cer­ tain variables and the rules that they participate in. A partial stable model is one where we try to ignore as few variables (w.r.t. set inclusion) as we can.

5.2 Translating CP-nets into Logic Programs

In this section we translate CP-nets into nonmonotonic logic programs, showing a one-to-one correspondence between the net's optimal outcomes and the stable models of the corre­ sponding logic program.

A preference PI V P2 V ... V Pk : QI > Q2 > · · · > Qn, where each p; is a conjunction of atoms, translates into a set of rules of the following form QI +- Pi for 1 :S j :S k. Additionally, for every variable X of the network with dom(X)={ VI, v2, ... , Vn} a set of rules of the form v; +- not v; 1 , not v; 2 , ··· , not v;n_ 1 , for ij # i, is added to the pro­ gram. We call this set choice rules set. Finally for each variable X, with dom(X)={ VI, v2, ... , Vn} we add the set of uniqueness constraints+- v;, Vj, for every pair of values such that i # j .

Theorem 3 o is a strongly optimal outcome for a CP-net iff it is a stable model of its corresponding logic program.

Note that only the most preferred values of each prefer­ ence statement participate in the translation of a CP-network into a logic program. Furthermore, the not operator appears only in the choice rules set, a feature that seems to indicate a rather weak link between CP-networks and nonmonotonic logic programs. However, in the long version of the paper we show that in the case of CP-networks with constraints, the not operator plays a more central role in the translation and the relation between CP-networks and logic programs is stronger than it may appear here.

Example 2 Consider the network:

a1 : b1 > b2 a2 : b2 > b1 b1 : a1 > a2 b2 : a2 > a1 The corresponding logic program is b1 +- a1 b2 +- a2 a1 +- b1 a2 +- b2 a1 +-not a2 a2 +-not a1 b1 +-not b2 b2 +- not b1 +- a1 , a2 +- b1 , b2.

The above program has exactly two stable models, namely M1 = {a1 , bd and M2 = {a2 , b2}.

5.3 Partial Stable Models and Partial Outcomes

We showed a direct correspondence between the optimal out­ comes of a CP-network and the stable models of its associated logic program. However, some logic programs have no sta­ ble model, much like some CP-nets have no strongly optimal outcome. We can interpret the non-existence of an optimal outcome as an indication that some of the preferences are not well-defined. There are two ways to handle such situations: we can isolate the ill-defined preferences and reason with the rest of the network, or we can try to revise the ill-defined pref­ erences. In both case, we require the ability to identify the problematic parts of the network. Here we show how partial stable models can provide valuable assistance in this task.

Example 3 Consider the network defined as follows.

together with the corresponding choice rules set and unique­ ness constraints. This program has no stable model, but it has two partial stable models, M1 = { c1, d1} and M2 = { c2 , d2}. These partial stable models do not assign a value to variables a 1 , a2 , b1 , b2 because the corresponding subnet­ work does not possess an optimal outcome.

We call the outcomes of a CP-network that correspond to the partial stable models of its associated logic program, par­ tial optimal outcomes. Intuitively, a partial stable model cor­ responds to an optimal assignment to a coherent sub-net of the original CP-net that contains the same preferences as the CP-net. Thus, we attempt to remove certain nodes, until we get a coherent specification. Those nodes that were removed are the ones we should point to the user as problematic.

Existing knowledge · on partial stable models (e.g., [Di­ mopoulos et al., 2002]) implies that a total partial optimal outcome (i.e., one that assigns a value to every variable) is an optimal outcome, and that deciding whether a logic program has a partial stable model other than the empty set is NP­ complete. Discovering whether a variable appears in some partial optimal outcome is NP-complete, whereas deciding whether a variable appears in all partial optimal outcomes is II~ -complete.

6 Conclusion

We showed that the current semantics of CP-network is too conservative in its interpretation of user specification. This is contrary to the aim of research on preference elicitation tech­ niques, i.e., reducing the burden on users. Consequently, we suggested a different semantics under which optimization can be meaningfully applied to CP-nets that are currently consid­ ered inconsistent. We showed how such an optimization pro­ cess can be practically implemented, extending current op­ timization techniques to cyclic network. Moreover, we de­ scribed a computational method for identifying sub-networks that are meaningful, providing the first tool that can point out to a user what part of her specification requires revision.