The Complexity of Learning Separable ceteris paribus Preferences

1 Introduction

In many applications, especially electronic commerce, it is important to learn the preferences of a user on a set of alternatives that has a combinatorial (or multiattribute) structure: each alternative is a tuple of values for each of a given number of variables (or attributes). For instance, suppose we observe a user making choices about airplane tickets: (a) she prefers a KLM night flight landing at Heathrow to an Aeroflot day flight landing at Gatwick, (b) she prefers an Aeroflot night flight landing at Heathrow to a KLM day flight landing at Heathrow and (c) she prefers a KLM day flight landing at Heathrow to a KLM night flight landing at Heathrow. An intuitively correct explanation (among others) is that she prefers Aeroflot to KLM (unconditionally), day flights to night flights (unconditionally), and Heathrow to Gatwick, again unconditionally. This explanation enjoys the key property that the user's preference relation is separable: the preference over the values of each attribute is independent from the values of other attributes. Such an explanation allows for predicting that she will prefer an Aeroflot day flight landing at Heathrow to anything else, and an Aeroflot day flight landing at Heathrow to an Aeroflot day flight landing at Gatwick (but is not able to predict whether she will prefer an Aeroflot day flight landing at Gatwick or an Aeroflot night flight landing at Heathrow).

Now, if we observe later that she prefers an Aeroflot night flight landing at Gatwick to an Aeroflot day flight landing at Gatwick, the previous explanation fails, and more generally,

J´er ˆome Mengin

IRIT

Universit´e de Toulouse 31062 Toulouse Cedex, France

Jerome.Mengin@irit.fr

so does any explanation where separability holds. A possible explanation (among others) could be that she prefers Aeroflot to KLM, Heathrow to Gatwick, day flights to night flights when flying on KLM and vice versa when flying on Aeroflot.

This raises several interesting questions: how can we decide whether it is possible that the user's preference relation is separable? If so, what are her local preference relations on every variable? If not, can we find the separable preference relation "maximally compatible" with the set of examples? How expensive are these computations? This paper aims at answering these questions (but it does not intend to find nonseparable preference relations fitting a set of examples).

In this paper we focus on passive learning: the system has as input a set of preferences between alternatives, that the user has already stated (not necessarily without her being asked to), and one wants to reason about her preferences so as to predict choices she will make on new alternatives. This clearly differs from preference elicitation (see for instance [Chen and Pu, 2004; Braziunas and Boutilier, 2006] for surveys) where the system interacts with the user by asking her specific requests, or suggesting new alternatives to lead her to express a preference on the value of some attribute [Viappiani et al., 2006], until she has found her target object or left the system.

Preferences over combinatorial domains have been investigated in detail in multiattribute decision theory (starting with Keeney and Raiffa 1976) and in Artificial Intelligence. Multiattribute decision theory has focused on modelling preferences, while AI has focused on designing languages for representing preferences as succinctly as possible and algorithms for finding optimal alternatives that are as fast as possible.

Classes of models and languages can be partitioned first according to whether they represent ordinal preferences (consisting in ranking the alternatives), and numerical preferences (e.g., utility functions). Here we focus on ordinal preferences. They have the advantage of often being easier to obtain from users.

Whereas there has been quite a lot of recent work on learning ranking functions and pairwise preferences over noncombinatorial sets of alternatives (see for instance Cohen et al. 1999, H¨ullermeier et al. 1999), and whereas learning or eliciting utility functions over multiattribute domains has been considered in some places (Ha and Haddawy 1997 or Gonzales and Perny 2004, among others) there have been fewer attempts at learning preferences from ordinal comparisons, notably: (a) learning lexicographic preferences [Schmitt and Martignon, 2006; Dombi et al., 2007; Yaman et al., 2008]; (b) a few works on learning CP-nets [Athienitou and Dimopoulos, 2007; Koriche and Zanuttini, 2009], (c) more general ceteris paribus preferences [Sachdev, 2007] or (d) utility functions learned from ordinal comparisons between logical formulas [Domshlak and Joachims, 2007]. These approaches are discussed in Section 6.

In both (a) and (b), the preference relation on the multiattribute domain is built from "local" preference relations on the attribute domains; these local orderings are then combined either in a lexicographic manner for (a), or, for (b), assuming that the local comparisons are lifted to comparisons of vectors of values when all other attributes have the same value (ceteris paribus). CP-nets allow dependencies between variables, and then providing local preferences on the values of one attribute depending on the values of other attributes.

In order to learn general CP-nets, given a set of examples, one would have to identify the dependency structure and the conditional preference tables. One could then search for the simplest CP-net compatible with the examples, or for the best trade-off between simplicity and compatibility with the examples. However, in this paper we focus on a simpler problem, namely, learning the simplest class of CP-nets: separable CP-nets (whose associated dependency graph is empty). There are several reasons for that. First, separable preferences are a very important class of preference relations on multi-attribute domains, as e.g. in economics or social choice (see for instance [Bradley et al., 2005]), so that learning separable preferences deserves a study on its own. Second, as we will see, learning separable preferences is computationally hard - more than one would think at first sight, since reasoning with separable CP-nets can be done in linear time. Third, designing methods for learning non-separable preferences, as we said, is a challenging and important issue to be investigated, but it is also a very involved question that surely cannot be answered in a single paper. Focusing first on separable preferences is a nontrivial and necessary step towards learning more complex preferences. Lastly, it is well-known that a simpler structure can have better generalization properties than a more complex one that may fit the examples better.

In Section 2, we give some background on preferences on combinatorial domains and (separable) CP-nets. We then focus successively on three forms of compatibility between a CP-net and a set of examples: weak compatibility in Section 3, strong compatibility in Section 4 and implicative compatibility at the end of Section 3. We show that while it can be checked in polynomial time whether there exists a SCP-net implying a set of examples, determining whether there exists a SCP-net weakly (resp. strongly) compatible with a set of examples is NP-complete. Related work is discussed in Section 6 and a concluding discussion is given in Section 7.

2 The problem

We want to learn an ordering on objects, or alternatives, defined by their values for attributes of a set V = {X1, . . . , Xn}. Each attribute Xi has a finite domain Di. We denote by D = D1 × . . . ×Dn the set of all possible alternatives. If ⃗x ∈ D, then (⃗x)i denotes the value of ⃗x for the i-th attribute Xi. An attribute Xi is binary if Di has two elements, which by convention we note xi and xi. A (strict) preference relation ≻ is a strict order on D, i.e., an irreflexive and transitive (theferore asymmetric) binary relation. If moreover ≻ is connected then ≻ is a linear preference relation (or linear order for short). Note that if we see a transitive relation ≻ as a graph over D (where there is an edge from ⃗x to ⃗y if x ≻ y), then ≻ is irreflexive if and only if the graph is acyclic.

Suppose now that we have a finite set of examples E, where each example is a pair of distinct alternatives (⃗x, ⃗y) (also denoted, equivalently, by ⃗x ≻ ⃗y) such that ⃗x is preferred to ⃗y. In a recommender system for instance, these examples may have been recorded in the course of a user interaction with the system. Ideally, we would like to learn how to order every unordered pair of distinct alternatives {⃗x, ⃗y}. Therefore, ideally, our target is a linear preference relation 1 .

In this paper, we focus on learning separable ceteris paribus preference structures (SCP structures for short). SCP-structures are particular cases of conditional preference networks, or CP-nets [Boutilier et al., 2004], obtained when the dependency graph between attributes is empty, therefore when every attribute is preferentially independent of all other attributes (CP-nets allow more generally the preference of an attribute to depend on the values of other attributes). A SCP structure on V is a collection N of linear orders ≻i, one on each Di. A swap is a pair of alternatives {⃗x, ⃗y} that differ in the value of one attribute only. From a SCP structure N we induce a preference relation ≻N as follows. First, a linear order on D is said to satisfy N if for every attribute Xi and every ⃗z, ⃗ z′ such that ⃗z and ⃗ z′ coincide on all attributes except Xi, ⃗z ≻ ⃗ z′ if and only if (⃗z)i ≻i (⃗ z′ )i. Then, ≻N is the intersection of all preference relations satisfying N . Note that ≻N is a partial order on D. Any linear order ≻ that satisfies a SCP structure is separable. Separability means that attributes are mutually preferentially independent. Note that if N is a SCP structure, then ≻N is irreflexive, and thus can be extended to a linear order on D [Boutilier et al. 2004, Th. 1].

In most of the paper, for the ease of presentation we assume all attributed are binary, although our results apply to non binary attributes as well (as shown at the end of section 3). In this case, for any pair (⃗x, ⃗y) of alternatives, let Diff (⃗x, ⃗y) = {xi | (⃗x)i = xi and (⃗y)i = xi}∪ {xi | (⃗x)i = xi and (⃗y)i = xi}; we can then use the following characterisation of ≻N (a corollary of a Theorems 7 and 8 by Boutilier et al., 2004):

Lemma 1 Let N be a SCP structure over binary variables, and ⃗y ̸= ⃗x. Then ⃗x ≻N ⃗y if and only if N contains xi ≻ xi for every xi ∈ Diff (⃗x, ⃗y) and xi ≻ xi for every xi ∈ Diff (⃗x, ⃗y).

Example 1 Consider three binary attributes A, B and C, with respective domains {a, a}, {b, b} and {c, c}, and let N = {a ≻ a, b ≻ b, c ≻ c}. We have abc ≻N abc, while abc and abc are incomparable w.r.t. ≻N .

1 Our methodology and results would easily carry over to the problem of learning nonstrict preference relations (where indifference is allowed). We stick here to strict preference relation because the presentation is simpler.

We said earlier that the target of our learning process should ideally be a linear order over D, but we have just seen that a SCP structure N does not in general correspond to such an order, since the preference relation ≻N induced fromN is generally not complete. Actually, ≻N can be seen as the set of all its completions, that is, a SCP structure expresses a set of linear preference relations.

If an example (⃗x, ⃗y) is a swap, then either ⃗x ≻N ⃗y or ⃗y ≻N ⃗x, and clearly we would like N to be in agreement with the example, that is, for instance, such that ⃗x ≻N ⃗y. But if (⃗x, ⃗y) is not a swap, there may be completions ≻ and ≻′ of ≻N such that ⃗x ≻ ⃗y and ⃗y ≻′ ⃗x. So we should start by discussing the possible ways of measuring to which extent a given SCP structure generalizes from a given set of examples.

Athienitou and Dimopoulos (2007) propose algorithms to learn CP-nets whose associated partial order contains all the examples - we say that it implies the examples. We argue here that this requirement may be too strong. To see this, consider the following example:

Example 2 We have two binary attributes X1 and X2 (with domains {x1, x1} and {x2, x2}), and the set of examples E = {x1x2 ≻ x1x2, x1x2 ≻ x1x2, x1x2 ≻ x1x2}.

What do we expect to learn from the above set of examples E? The transitive closure of E is the complete preference relation x1x2 ≻ x1x2 ≻ x1x2 ≻ x1x2. This preference relation is separable (the agent unconditionally prefers x1 to x1 and x2 to x2). The fact that x1x2 is preferred to x1x2 simply means that when asked to choose between X1 and X2, the agent prefers to give up X2 (think of X1 meaning "getting rich" and X2 meaning "beautiful weather tomorrow"). Intuitively, since E is separable, we expect to output a structure N that contains x1 ≻ x1 and x2 ≻ x2. However, no SCP structure implies E (in fact, no CP-net implies E, whatever the dependencies). The structure N induces a partial preference relation in which x1x2 and x1x2 are incomparable. More generally, no ceteris paribus structures can "explain" that x1 ≻ x1 is "more important" than x2 ≻ x2 (i.e., with no intermediate alternative). Therefore, if we look for a structure implying all the examples, we will simply output "failure". On the other hand, if we look for a SCP structure that is simply consistent with the examples, i.e. that does not imply the contrary of the examples, we will output N.

The explanation is that when an agent expresses a CP-net, the preference relation induced by this CP-net is not meant to be the whole agent's preference relation, but a subset (or a lower approximation) of it. In other terms, when an agent expresses the CP-net N, she simply expresses that she prefers x1 to x1 ceteris paribus (i.e., for a fixed value of X2) and similarly for the preference x2 ≻ x2; the fact that x1x2 and x1x2 are incomparable in N surely does not mean that the user really sees them incomparable, but, more technically, that CPnets are not expressive enough for representing the missing preference x1x2 ≻ x1x2 2 .

2 If we want to do this, we have to resort to a more expressive language such as TCP-nets [Brafman et al., 2006] or conditional preference theories [Wilson, 2004].

Therefore, rather than looking for a CP-net that implies the examples, we should rather look for a CP-net whose preference relation is consistent with the examples. A first way of understanding consistency is to require that the learned CPnet N is such that the examples are consistent with at least one preference relation extending N. In some contexts it may even be too strong to require that one of the completions of ≻N contains all the examples, in particular if they come from multiple users (given that we want to learn the generic preferences of a group of users), or a single user in different contexts:

Example 3 Suppose that we learn that all users in a group unconditionally prefer x1 to x1 and x2 to x2, whereas their preferences between x1x2 and x1x2 may differ (think as x1 and x2 as, respectively, "being invited to a fine dinner" and "receiving a $50 award"): then E ⊇ {x1x2 ≻ x1x2, x1x2 ≻ x1x2}. E is clearly inconsistent, so there cannot be any preference structure whose ordering can be completed into a linear preference relation that contains E. However, if N = {x1 ≻ x1, x2 ≻ x2}, then each example in E is (individually) contained in at least one completion of ≻N .

We now define three notions of compatibility of a SCP structure with a set of examples. (Note that these definitions also work for general CP-nets.)

Definition 1 Let N be a SCP structure over V. An example (⃗x, ⃗y) is implied by N if ⃗x ≻ ⃗y for every completion ≻ of ≻N; it is consistent with N if there is a completion ≻ of ≻N such that ⃗x ≻ ⃗y. Furthermore, we will say that a set of examples E is:

• implied by N if every example of E is implied by N;
• globally (or strongly) compatible with N if there is a completion ≻ of ≻N such that for all (⃗x, ⃗y) ∈ E, ⃗x ≻ ⃗y;
• weakly compatible with N if every example (⃗x, ⃗y) ∈ E is individually consistent with N.

Lastly, we will say that E is implicatively / strongly / weakly separable if it is implied by / strongly compatible / weakly compatible with at least one SCP structure.

Clearly, strong compatibility implies weak compatibility, and if E is implied by N, it is strongly compatible with N.

3 Weak compatibility

We start by showing how searching for a SCP structure weakly compatible with a set of examples can be rewritten as a propositional satisfiability problem. In the case of binary attributes, consider the following translation from sets of examples to sets of clauses, the models of which correspond to SCP structures that are weakly consistent with the examples.

With each example ⃗x ≻ ⃗y we associate the clause C⃗x≻⃗y that contains xi iff xi∈Diff (⃗x, ⃗y) and ¬xi iff xi∈Diff (⃗x, ⃗y). For instance, if ⃗x = x1x2x3x4 and ⃗y = x1x2x3x4 then Diff (⃗x, ⃗y) = {x1, x2, x4} and C⃗x≻⃗y = x1 ∨ ¬x2 ∨ x4. This clause expresses that x1 is preferred to x1, or x2 is preferred to x2, or x4 is preferred to x4. (The explanation for this is that if a SCP structure N contains {x1 ≻ x1, x2 ≻ x2, x4 ≻ x4}, then by Lemma 1 we have ⃗y ≻N ⃗x, therefore N is not consistent with ⃗x ≻ ⃗y.)

If E is a set of examples then ΦE = {Ce | e ∈ E}. We now define the following one-to-one correspondence between truth assignments over {x1, . . . , xn} and SCP structures over V. If M is such a truth assignment, let NM contain the preference xi ≻ xi for every i such that M |= xi and the preference xi ≻ xi for every i such that M |= ¬xi. For instance, if M(x1) = ⊤, M(x2) = ⊥, M(x3) = ⊥ and M(x4) = ⊤ then NM contains the preference tables {x1 ≻ x1, x2 ≻ x2, x3 ≻ x3, x4 ≻ x4}.

Proposition 1 Let M be an interpretation. A set of examples E is weakly consistent with NM if and only if M |= ΦE .

Proof : We show that NM ̸|= ⃗y ≻ ⃗x if and only if M |= C⃗x≻⃗y. Without loss of generality, let ⃗x = x1 . . . xn and ⃗y = x1 . . . xixi+1 . . . xn. Then M ̸|= C⃗x≻⃗y if and only if NM contains x1 ≻ x1, . . . , xi ≻ xi, which from Lemma 1 is equivalent to NM |= ⃗y ≻ ⃗x. ■

Corollary 1 E is weakly separable if and only if ΦE is satisfiable.

As a consequence, weak separability comes down to a satisfiability test.

Example 4 Consider three binary attributes A,B,C, and the set of examples

ΦE has a unique model, corresponding to the SCP structure N = {a ≻ a, b ≻ b, c ≻ c}. Therefore, N is the unique SCP structure weakly compatible with N, which implies that E is weakly separable.

Proposition 2 Deciding whether a set of examples over binary attributes is weakly separable is NP-complete.

Proof : Membership follows directly from Corollary 1. For hardness, we use a reduction from 3SAT: let Φ be a set of non tautological, 3-clauses. For every C = l1 ∨ l2 ∨ l3 in Φ we create an example eC = (⃗x ≻ ⃗y) with ⃗x = ε1.x1ε2.x2 . . . εn.xn and ⃗y = ε′1 .x1ε′2 .x2 . . . ε′n .xn, where, for every i, εi.xi = ε′i .xi = xi, except that if lj = ¬xi for some j, then εi.xi = ¬xi; and if lj = xi for some j, then ε′i .xi = ¬xi. Now, let EΦ = {eC | C ∈ Φ}. For example, if Φ = {x1 ∨ ¬x2 ∨ x3, ¬x1 ∨ x2 ∨ x4, x2 ∨ x3 ∨ x4} then EΦ = {x1x2x3x4 ≻ x1x2x3x4, x1x2x3x4 ≻ x1x2x3x4, x1x2x3x4 ≻ x1x2x3x4}. We easily check that ΦEΦ = Φ, and therefore that Φ is satisfiable if and only if EΦ is weakly separable. ■

The generalization to non-binary domains is not difficult. Instead of having one propositional symbol per attribute, we have one propositional symbol for every pair of values of every attribute. For instance, if we have an attribute X whose domain is {d1, d2, d3} then we have the three propositional symbols d1≻d2, d1≻d3 and d2≻d3 (d2≻d1 being equivalent to ¬(d1≻d2), etc.). For instance, if Y is a binary attribute, the clause corresponding to the example d1y ≻ d2y is (d1 ≻ d2)∨¬y. The main difference with the binary case is the transitivity requirement. Let Trans = ∧Xi∈V TransXi be the propositional formula expressing transitivity - for instance, for D1 = {d1, d2, d3} we have T ransX1 = (d1≻d2∧

d2≻d3 → d1≻d3) ∧ .... Note that Trans is polynomially long. The one-to-one correspondence between interpretations and SCP structures now works only for interpretations satisfying T rans: M |= ΦE ∧T rans if and only if NM is weakly consistent with NM. As a consequence, E is weakly separable if and only if ΦE ∧ Trans is satisfiable.

This translation shows that weak consistency for nonbinary attributes is in NP, hence it is NP-complete.

Now, as soon as E becomes large with respect to the number of attributes n, the chances that E is weakly consistent become low. In this case, we may want to determine a SCP structure that is weakly compatible with as many examples of E as possible. Applying Corollary 1 to subsets of E, we get that this problem amounts to solving a MAXSAT problem. The SCP structure that best fits a set of examples (in the sense of weak compatibility) corresponds to the interpretation maximizing the number of clauses fromΦE satisfied. This extends to nonbinary variables, with the difference that the clauses in Trans are protected.

As a consequence of Propositions 1, we can reuse algorithms for MAXSAT for computing an SCP structure that best fits a set of examples, as well as polynomial approximation schemes. Using the same kind of translation, we can easily prove that if all variables are binary and all examples in E differ at most on two variables, then deciding whether E is consistent can be done in polynomial time (however, the corresponding optimization problem remains NP-hard).

4 Strong compatibility

Characterizing strong compatibility is less easy. The difference between weak and strong compatibility is that while in weak compatibility we look for a SCP structure which is consistent with each individual example in E, in strong compatibility we look for a SCP structure which is consistent with the whole set of examples E.

Example 4, continued E is not strongly compatible with N, because E ∪≻N has the following cycle:

Since E is not strongly compatible with any other SCP structure than N (because N is the unique SCP structure weakly compatible with N), E is not strongly separable 3 .

Note that all alternatives of the cycle on the example above appear in E. More generally, if we denote by D(E) the set of alternatives of D that appear in E, we have the following characterisation of strong compatibility:

Proposition 3 E is strongly compatible with N if and only if the restriction of ≻N ∪ E to D(E) is acyclic.

Proof : By definition, if E is strongly compatible with N then ≻N can be completed into a linear order containing E, therefore ≻N ∪ E is acyclic, and so is its restriction to D(E). For the converse, assume that E is not strongly compatible with N: ≻N ∪ E cannot be extended to a linear order, this means that it is not irreflexive, so it contains a cycle Γ. Since SCP structures are consistent, Γ must contain at least one edge of E. We can transform Γ into a cycle Γ′ whose vertices are all in D(E): simply replace, as long as it is possible, any sequence of vertices in Γ of the form x ≻N y ≻N z by the vertex x ≻N z (which holds because ≻N is transitive). Now, every edge in Γ′ is either in E or adjacent to two edges in E (recall it cannot be reduced to a single reflexive edge of ≻N because ≻N is irreflexive), so its extremities are in D(E). So Γ′ is a cycle of the restriction of ≻N ∪ E to D(E). ■

3 Note that E is both weakly consistent and does not contain any cycles as it was the case for Example 3, yet is not strongly consistent.

Since the restriction of ≻N ∪ E to D(E) has at most 2.|E| vertices, checking if it possesses a cycle can be done in polynomial time, so checking whether E is strongly compatible with N is in P. Thus, since the size of a SCP-structure is linear in the number of variables, checking whether E is strongly separable is in NP.

Proposition 4 Checking whether E is strongly separable is NP-complete.

Proof : Hardness comes from the following reduction from WEAK SEPARABILITY. Let E = {⃗x1 ≻ ⃗y1, . . . , ⃗xm ≻ ⃗ym} be a set of examples, built on a set of propositional symbols X. We map E to the following set of examples E ′ , built on the set of attributes X ∪ {P1, . . . , Pm}. For every ei = ⃗xi ≻ ⃗yi in E we create the example

e′i : ⃗xip1 . . . pi-1pipi+1 . . . pm ≻ ⃗yip1 . . . pi-1pipi+1 . . . pm. We claim that E ′ = {e′i | ei ∈ E} is strongly separable if and only if E is weakly separable. Assume E is weakly separable: there exists a SCP structure N consistent with each ei in E. Let N ′ = N ∪ {p1 ≻ p1, . . . , pn ≻ pn}. For every i, because N is consistent with ⃗xi ≻ ⃗yi, there exists a linear order ≻i extending ≻N and containing ⃗xi ≻ ⃗yi. Let ≻ be the preference relation defined by ⃗x⃗ p ≻ ⃗y⃗ p′ if and only if one of the following conditions hold:

• (a) ⃗ p is lexicographically larger than ⃗ p′ (denoted by ⃗ p >lex ⃗ p′ ), that is, there exists an i ≤ m such that ⃗ p contains pi, ⃗ p′ contains pi, and for all j < i, ⃗ p contains pj if and only if ⃗ p′ contains pj.
• (b) ⃗ p= ⃗ p′ =p1 . . . pi-1pipi+1 . . . pm for some i, and ⃗x ≻i ⃗y;
• (c) ⃗ p = ⃗ p′ , ⃗ p is not of the form p1 . . . pi-1pipi+1 . . . pm for some i, and ⃗x ≻∗ ⃗y, where ≻∗ is any preference relation extending ≻N .

It can be checked that ≻ is a complete preference relation ≻ extending ≻N ′ , and containing E ′ , which implies that E ′ is strongly consistent with N ′ , and that E ′ is strongly separable.

Conversely, assume E ′ is strongly separable. Let N ′ be strongly consistent with E ′ , and ≻ extending ≻N ′ and containing E ′ . For every i ≤ m, define ≻i as follows: ⃗x ≻i ⃗y iff ⃗xp1 . . . pi-1pipi+1 . . . pm ≻ ⃗yp1 . . . pi-1pipi+1 . . . pm. Then, for every i: ≻i is a complete strict order on 2X ; ≻i extends ≻N; and ≻i contains ⃗xi ≻ ⃗yi, because ≻ contains ⃗xip1 . . . pi-1pipi+1 . . . pm ≻ ⃗yip1 . . . pi-1pipi+1 . . . pm. Therefore, for every i we have found an extension ≻i of ≻N containing ⃗xi ≻ ⃗yi, which implies that E is weakly compatible with N, and that E is weakly separable. ■

Note that although weak and strong separability have the same complexity, weak consistency enjoys the nice property that there is a simple solution-preserving translation into SAT (the models of ΦE correspond bijectively to the CP-nets that are weakly consistent with E), which allows weak consistency to be computed in practice using algorithms for SAT. In order to compute a SCP structure strongly consistent with E, we can generate structures N weakly consistent with E, and test for acyclicity of ≻N ∪ E using graph algorithms.

5 Implicative compatibility

It is easy to characterize whether there exists a SCP structure that implies E. In the case of binary variables, with each example ⃗x ≻ ⃗y we associate the conjunction of literals Γ⃗x≻⃗y = ¬C⃗y≻⃗x. Let ΓE = ∧{Γe | e ∈ E}. Using Lemma 1, we can prove that M |= ΓE if and only if NM implies E. Searching for a model of a conjunction of literals can be done in polynomial time, thus the problem of checking if a set of examples is implicatively separable is in P.

Although implicative separability is easier than strong or weak separability, as argued before, we believe that implicative separability is much too strong.

6 Related work

There is an active stream of research on preference learning, which focuses on many facets of preference learning, such as label ranking [H¨ullermeier et al., 2008] or learning to rank objects [Cohen et al., 1999], but so far the focus is laid on preferences on simple, noncombinatorial domains 4 .

Learning numerical utility functions on combinatorial domains has been addressed in e.g. [Ha and Haddawy, 1997; Gonzales and Perny, 2004]. Recently, Domshlak and Joachims [2007] proposed a method to learn a utility function from general preference statements between logical formulas. As for learning ordinal preferences on multiattribute domains, an approach that follows a methodology close to ours (but for a very different class of preference structures) is the work on learning lexicographic preferences on multiattribute domains [Schmitt and Martignon, 2006; Dombi et al., 2007; Yaman et al., 2008]. A significant difference is that they learn the full preference relation, while we learn only the local preference relations. Of course, learning the full preference relation gives a richer information, but this comes with a price, namely, the hypothesis they make (lexicographic preferences) is highly restrictive. Lexicographic preferences are a very specific, special form of preferences that is not often met in practice. Note that every lexicographic preference is separable, but the set of separable preferences is much larger. Interestingly, the complexity results are similar.

Koriche and Zanuttini [2009] show that it is possible to efficiently elicitate acyclic CP-nets using simple queries of the form ⃗x ≻? ⃗y where ⃗x and ⃗y differ in the value of one variable only. Passive learning of CP-nets has been considered by Athienitou and Dimopoulos [2007]. As argued above, their focus on implicative compatibility limits the applicability of the approach. Sachdev [2007] proposes to learn a preference theory, in the sense of Doyle et al. [1991], consistent with a set of examples. He assumes that one is given (or has access to) the complete set of examples corresponding to an existing preference theory that one is trying to induce, which practically limits its applicability.

4 Note that multiattribute domains are sometimes considered, but with a very different role: for instance, in label ranking one learns a preference relation on a simple domain, given some information under the form of a vector or attribute values (for instance, predict a user's ranking on a set of candidates at an election given his/her sex, age and profession).

7 Conclusion and further work

Our contribution is twofold: we have seen that finding a separable ceteris paribus preference relation (or equivalently, finding a separable CP-net) compatible with a set of examples is not straighforward to define, due to the fact that, unlike lexicographicity, separability does not permit to lift the local preference relation into a complete preference relation on the multiattribute domain. We have proposed and discussed three different forms of compatibility between a separable CP-net and a set of examples. For each of these, we have identified its complexity and given characterizations that can be used for computing a separable CP-net that fits best a set of examples. Although implicative separability is easier than strong or weak separability, as argued before, implicative separability is far less interesting than the other two notions.

Now, our definitions of implicative, strong and weak compatibility would work for any CP-net. So far our characterizations and complexity results for each of these three forms of consistency concern only the case of separable preferences, where the dependency graph has no edge. A long-term challenge would consist in investigating methods for learning CP-nets with any structure, focusing first on simple structures (e.g., hypertrees). A first step would consist in learning CP-nets with a fixed graph: given a set of examples E and a dependency graph G, output the CP-net maximizing G-compatibility (w.r.t. any of the three forms) with E. Unfortunately, this is not simple. Our translation of examples into propositional clauses can be extended, using, for each binary attribute, one propositional variable for every combination of values of its parents. For instance, if A has no parent and is the only parent of B, we use three propositional variables: a, (a:b) and (a:b), where, for instance, (a:b) assigned to true corresponds to the entry a: b≻b in the preference table for B. Weak compatibility can then be encoded using, for each example ⃗x≻⃗y, one clause for each sequence of swaps from ⃗y to ⃗x, expressing that at least one step of this sequence is blocked. This ensures that ⃗y≻N⃗x does not hold. But there can be exponentially many such clauses, even in the case where the number of parents in the dependency graph is bounded, which considerable limits the applicability of this translation.

Acknowledgements

Many thanks to Richard Booth, Yann Chevaleyre, Kevin Garcia, Peter Haddawy, Fr´ed´eric Koriche, Mathieu Serrurier, Chattrakul Sombatheera and Bruno Zanuttini for helpful discussions. Anonymous referees also gave helpful comments. This research has been partially supported by the project ANR-05-BLAN-0384 "Preference Handling and Aggregation in Combinatorial Domains".