Ceteris Paribus Preference Elicitation with Predictive Guarantees

1 Introduction

Preferences have been studied for a long time in different scientific fields such as economics, operations research, decision theory, and computer science. One of the central problems there is that of automated learning and adaptation of preferences. The significance of this problem has been recognized quite early, and there is now a considerable body of research related to the problem of preference elicitation. Within Artificial Intelligence, some aspects of the problem of preference elicitation have more recently received some attention in Machine Learning. Among the different problems that have been investigated, that of label ranking (see, e.g., [Brinker et al., 2006; Cohen et al., 1999]) has some similarities with the problem we study in this work. We direct the interested reader to the relevant literature for more details.

CP-networks (CP-nets for short) have been proposed as a simple and intuitive graphical tool for representing and reasoning with qualitative conditional preferences. CP-nets are directed graphs whose vertices correspond to variables, each annotated with preferences over the variable's values. These preferences may depend on the values of other variables, hence the term conditional. Although CP-nets, being a compact, intuitive language for representing preferences, alleviate the problem of preference elicitation, they do not completely eliminate it. Indeed, deriving a CP-net in complex domains can be a tedious and time-consuming task. Moreover, in some domains, such as auctions and automated negotiation, users may not be willing to reveal their preferences. Thus, there is a need for deriving methods for learning CP-nets.

Despite the evident significance of the problem, there are only a couple of studies that address the question of learning CP-networks, namely [Athienitou and Dimopoulos, 2007] and [Lang and Mengin, 2008]. In this work we extend and complement these previous studies in several ways. Specifically, we study the problem of deriving a CP-net from a given set P of pairwise comparisons oi ≻ oj between outcomes, meaning "outcome oi is strictly preferred over outcome oj". Such pairwise comparisons may be gathered, for instance, by passively observing the choices of a user on a web page. In the simplest case, we seek to derive a CP-net N such that P is a subset of the relation induced by N. We show that the problem is intractable even in the case where the input comparisons are on outcomes that differ on at most two variables, and the in-degree of the nodes of the simplest CP-net that implies the comparisons (if one exists) is upper-bounded by 2.

Although CP-net learning is hard in the general case, we present an algorithm that solves this problem in polynomial time, provided that some restrictions on the input pairwise comparison and the CP-net to be learned are satisfied. Moreover, we show the the proposed algorithm is a PAC-learner, i.e., the CP-networks it induces accurately predict the user's preferences on future and possibly previously unseen variable assignments. A reduction suggests the hardness of improving our algorithm's running time, and establishes the fixedparameter intractability of the learning problem.

2 CP-networks

We start by briefly reviewing the basics of CP-nets, following [Boutilier et al., 2003]. Let V = {X1, · · · ,Xn} be a set of variables over which a user has preferences. Each variable Xi is associated with a domain of values Dom(Xi) = {xi1 , · · · , xini }. An assignment x of values to a set X ⊆ V of variables maps each variable of X to an element of its domain; if X = V, x is an outcome. Denote Asst(X) the set of all assignments to X ⊆ V. For X, Y ⊆ V such that X ∩ Y = ∅, xy ∈ Asst(X ∪ Y) denotes the combination of assignments x ∈ Asst(X ) and y ∈ Asst(Y).

A preference ranking is a total preorder ⪰ over the set of outcomes. The notation o1 ⪰ o2 means that outcome o1 is equally or more preferred than o2, while o1 ≻ o2 means that outcome o1 is strictly more preferred by the decision maker than o2 (i.e., o1 ⪰ o2 and o2 ̸⪰ o1). Finally, o1 ∼ o2 denotes that outcomes o1 and o2 are indifferent.

A CP-net N is constructed as follows. For each variable Xi, the user specifies a set of parent variables PaN(Xi) that affect her preference over the values of Xi. Then, she specifies her preferences over the values of Xi for all instantiations of the variable set PaN(Xi). More specifically, for each assignment u ∈ Asst(PaN(Xi)), the user provides in a conditional preference table or CPT, a total preorder ⪰iu over Dom(Xi) by specifying for any two values x and x′ , either x ≻iu x′ , x′ ≻iu x, or x ∼iu x′ . For simplicity of presentation, we ignore indifference for the rest of this paper.

Definition 1. A CP-net N over the set V = {X1, · · · ,Xn} of variables is a directed graph G over the vertex set V, with each Xi ∈ V annotated with a conditional preference table CPT(Xi). Each conditional preference table CPT(Xi) associates a total order ≻iu with each u ∈ Asst(PaN(Xi)).

The following notions define the semantics of a CP-net.

Definition 2 ([Boutilier et al., 2003]). Consider a CP-net N over the set V of variables, a variable Xi ∈ V, and Y = V \ (PaN(Xi) ∪ {Xi}). For every u ∈ Asst(PaN(Xi)), let ≻iu be the ordering over Dom(Xi) dictated by CPT(Xi). A preference ranking ≻ over Asst(V) satisfies (i) the total preorder ≻iu iff uxy ≻ ux′ y holds for every y ∈ Asst(Y), and every x, x′ ∈ Dom(Xi) s.t. x ≻iu x′ ; (ii) the conditional preference table CPT(Xi) iff it satisfies ≻iu for every u ∈ Asst(PaN(Xi)); (iii) the CP-net N iff it satisfies CPT(Xi) for every Xi ∈ V. A CP-net N is satisfiable iff there exists a preference ranking ≻ that satisfies N.

Definition 3. Let N be a CP-net over a set V of variables, and let o, o′ ∈ Asst(V) be any two outcomes. N entails o ≻ o′ , denoted N |= o ≻ o′ , iff o ≻ o′ holds in every preference ranking that satisfies N.

For the remainder of this paper, we restrict our attention to the class of acyclic CP-nets. We denote by Nk the subclass of acyclic CP-nets with a maximum in-degree at most k.

3 Learning by Fitting the Data

One of the simplest definitions of CP-net learnability, and the one considered here, is that of identifying a CP-net consistent with a given set of pairwise comparisons between outcomes that are entailed by some unknown target CP-net.

Definition 4 (CP-Net Consistent-Learnability). A class N of CP-nets over a set V of variables is consistent-learnable (by a class H of hypotheses) if there exists an algorithm L such that for every CP-net N ∈ N, and every set P of pairwise comparisons between outcomes over V entailed by N, algorithm L has the following property: given access to V and P, algorithm L runs in time polynomial in |V|, |P|, and size(N), and returns a hypothesis h (in H) that entails every comparison in P.

The constraint of Definition 4 that only polynomial time is allowed, makes learnability impossible in the general case.

Theorem 1. Fix a constant integer k ≥ 2. Deciding whether there exists a CP-net in Nk that entails all pairwise comparisons in a set P is NP-hard, even if for every o1 ≻ o2 ∈ P, o1, o2 differ on at most two variables, and even if when some CP-net entails all comparisons in P, then there also exists a CP-net N ∈ N2 that entails all comparisons in P.

Proof (sketch). By reduction from read-3 3-SAT. Given a formula ϕ = ∧mj=1 ℓj,1 ∨ ℓj,2 ∨ℓj,3 over variables {v1, . . . , vn}, define the set V to contain one variable for each variable vi and clause cj of ϕ, and their negations vi, cj. Without loss of generality, assume that every variable of ϕ that appears in some clause appears negated in some other clause (thus each literal appears at most twice), and not in the same clause.

Let the domain of x ∈ V be {x0 , x1}, and a 0 in outcomes mean that all unspecified variables are false. For each cj, P[ϕ] includes c1j cj 0 0 ≻ c0j cj 1 0; roughly, this preference corresponds to asking that the clause cj of ϕ should be satisfied.

We associate a set PP(x) of possible parents with each x ∈ V. For each clause cj, PP(cj) = {ℓj,1, ℓj,2, ℓj,3}, PP(cj) = {}. For each literal ℓ, PP(ℓ) = {ℓ} ∪ {cr | cr contains ℓ}. We constrain CP-nets N ∈ Nk so that PaN(x) ∩PP(x) ̸= ∅. We do so by excluding the possibility that any set S ⊆ V of k variables such that S ∩ PP(x) = ∅ is the parent set PaN(x) of x. This is achieved if P[ϕ] includes x0 s0 ≻ x1 s0 for every assignment s ∈ {0, 1}k of values to S. The construction can be done in time polynomial in the size of ϕ since k is constant.

It can be shown that the preferences in P[ϕ] are entailed by some CP-net N in Nk if and only if for each j, there exists t such that ℓj,t is a parent of cj and a child of ℓj,t in N. For the "only if" direction, the CPT of x ∈ V includes x0 ≻ x1 when all its parents are false, and x1 ≻ x0 otherwise. Thus, the parent relations in N induce satisfying assignments for ϕ, and vice versa, which suffices to establish the reduction. ✷

The following result is an immediate conclusion:

Corollary 1. Fix a constant integer k ≥ 2. The class N2 of CP-nets is not consistent-learnable by Nk, unless P = NP.

Thus, consistent-learnability is intractable given the standard complexity assumption P ̸= NP, even if the target CPnet is in N2, with binary variables, even if more expressive CP-nets may be returned (i.e., in Nk), and even if outcomes in pairwise comparisons differ on at most two variables.

We present next an algorithm that tackles the problem of learning, as in Definition 4, from restricted sets P. (The algorithm assumes binary variables, but the same basic idea, applies for non-binary variables.) The algorithm takes as input a set V of variables, and a set P of pairwise comparisons between outcomes over V. It generates an acyclic CP-net that satisfies the given input, by creating the CPT of each variable.

The main procedure learn(V,P) is shown in pseudocode in Algorithm 1. The algorithm maintains a CP-net h that is initially empty, and attempts to extend it with the addition of the CPT of one of the remaining variables X, by calling the procedure extendNetwork(X, V \ X,P, k, h). If a CPT for each variable in V can be added, the constructed CP-net h is returned. Otherwise, the value of k is increased and the process loops, until either a CP-net is constructed, or failure is detected. For each invocation of the procedure extendNetwork(X, V \ X,P, k, h), all variables in X are tested until one is identified whose CPT can be constructed (if possible). For each candidate variable X ∈ X , the procedure getNextSubset(V ′ , k, U) is invoked to return the possible subsets U of V ′ of size at most k. Each such subset U ⊆ V ′ is provisionally assumed to be the parent set of X. The procedure createCPT(X, U, P, h) is then invoked, which checks the set of pairwise comparisons P to determine if Pah(X) can be set to U in the CP-net h being constructed. If so, the constructed CPT(X) is added in h, and the procedure returns the variable X. Otherwise, the next provisional parent set is considered. If Pah(X) cannot be set to any of the provisional parent sets U, the next candidate variable is considered. If the CPT of no variable X can be added to the CP-net h, the empty set is returned.

1: h := the empty CP-net /∗ Constructed CP-net ∗/ 2: k := 0 /∗ Number of allowed parents ∗/ 3: X := V /∗ Remaining variables not in h ∗/ 4: repeat 5: repeat 6: added := extendNetwork(X , V \ X , P, k, h) 7: X := X \ added 8: until added = ∅ 9: if X = ∅ then 10: return h 11: end if 12: k := k +1 13: until k = |V| 14: return failure

1: while X ̸= ∅ do 2: choose X fromX 3: U := ∅ /∗ Provisional parent set for X ∗/ 4: repeat 5: CPTcreated := createCPT(X, U,P, h) 6: subsetExists := getNextSubset(V ′ , k, U) 7: until CPTcreated or not(subsetExists) 8: if CPTcreated then 9: return {X} 10: end if 11: X := X \ {X} 12: end while 13: return ∅

Observe that since V ′ = V \ X, then V ′ contains exactly those variables that are already in the CP-net h at the time that the CPT of some variable X ∈ X is added. This guarantees that the constructed CP-net h is acyclic. Note further that we may assume that the subsets U ⊆ V ′ returned by the procedure getNextSubset(V ′ , k, U), are considered in order of increasing size. Although this is not required for our formal results to go through, it might provide a heuristic for further reducing the size of the constructed CP-nets.

To decide whether U can be the parent set of X in h, the procedure createCPT (X, U, P, h) examines each uixiyi ≻ ujxjyj ∈ P, where ui, uj ∈ Asst(U), xi, xj ∈ Dom(X), yi, yj ∈ Asst(V \ (U ∪ {X})), and considers the inclusion of either ui : xi ≻ xj or uj : xi ≻ xj in CPT(X). Given the set

of all choices that procedure createCPT(X, U, P, h) has to make, the procedure attempts to generate CPT(X) by selecting one of the disjuncts in each element of S such that the selected entries are jointly consistent (i.e., for every choice of u, exactly one of u : x1 ≻ x2 and u : x2 ≻ x1 is chosen).

The above problem of selecting disjuncts from the set S can be naturally casted as a propositional satisfiability problem: to each element u ∈ Asst(U) that appears in S associate a boolean variable v(u), whereas to each entry u : x1 ≻ x2 associate the positive literal v(u), and to each entry u : x2 ≻ x1 the negative literal v(u). Then, the elements of S translate to binary clauses, and the resulting satisfiability problem is a 2-SAT one. The following example illustrates the translation.

Example 1. Consider the variables A,B,C, with domains {a1, a2}, {b1, b2}, {c1, c2}, respectively. Consider also the set P of comparisons:

During the invocation of createCPT(C, {A,B} ,P, h), the set S of choices is populated as follows:

Assume that we associate the elements of Asst({A,B}) with boolean variables as follows: a1b1 → v1, a1b2 → v2, a2b1 → v3, a2b2 → v4. Then, the candidate entries are associated with literals as follows: a1b1 : c1 ≻ c2 → v1, a1b1 : c2 ≻ c1 → v1, a1b2 : c1 ≻ c2 → v2, a1b2 : c2 ≻ c1 → v2, a2b1 : c1 ≻ c2 → v3, a2b1 : c2 ≻ c1 → v3, a2b2 : c1 ≻ c2 → v4, a2b2 : c2 ≻ c1 → v4. The resulting 2-SAT instance is (v1 ∨ v2) ∧ (v1 ∨ v3) ∧ v3 ∧ (v4 ∨ v2).

A satisfying assignment for the above 2-SAT instance assigns false to v1, and true to v2, v3 (and either truth-value to v4). This translates to the CPT entries a1b1 : c2 ≻ c1, a1b2 : c1 ≻ c2, and a2b1 : c1 ≻ c2 (and the remaining entry can be either a2b2 : c1 ≻ c2 or a2b2 : c2 ≻ c1).

Thus, constructing a CPT for a variable X given a provisional parent set U reduces to computing a satisfying assignment of a 2-SAT instance, which can be done in polynomial time [Aspvall et al., 1979]. If the 2-SAT instance is unsatisfiable, U cannot be the parent set of X in the CP-net h.

We now illustrate the working of the entire algorithm.

Example 2. Consider the set V = {A, B, C, D} of variables, with Dom(A) = {a1, a2}, Dom(B) = {b1, b2}, Dom(C) =

{c1, c2}, Dom(D) = {d1, d2}. Consider also the following set P of comparisons:

1. a1b1c2d1 ≻ a1b2c2d2
2. a1b2c1d2 ≻ a1b1c1d1
3. a2b2c2d2 ≻ a2b1c2d1
4. a1b1c1d1 ≻ a1b2c1d1
5. a1b2c1d1 ≻ a2b1c2d1

During the algorithm's first iteration with k = 0, the algorithm successfully constructs CPTs for the variables A and C through two consecutive invocations of the procedure extendNetwork. The CP-net h is, thus, updated to include : a1 ≻ a2 as CPT(A), and : c1 ≻ c2 as CPT(C). During the third invocation of the procedure extendNetwork, the empty set is returned, since the CPT of none of the remaining variables B and D can be constructed with an empty parent set - in comparisons (1) and (2) the preference over b1 and b2 is reversed; so is the case for d1 and d2.

The value of k is increased to 1, and the algorithm attempts again to create CPTs for B and D, only to discover that this is still not possible. The provisional parent set {A} does not become an actual parent set of B, since in comparisons (1) and (2) conditioning on a1 does not resolve the fact that the preference over b1 and b2 is reversed. Similarly, the provisional parent set {C} fails due to the comparisons (1) and (3), where conditioning on c2 does not resolve the reversed preference over b1 and b2. An analogous situation applies when the algorithm attempts to build the CPT of D.

In the subsequent iteration the value of k is increased to 2. Assume that the algorithm first chooses the variable B. All attempts to create CPT(B) with a parent set other than {A,C} fail as before. The attempt also fails when {A,C} is considered, since in comparisons (2) and (4) conditioning on a1c1 does not resolve the reversed preference over b1 and b2. Next, variable D is chosen. When the procedure createCPT(D, {A,C} ,P, h) is invoked, it succeeds and adds the following CPT as CPT(D) in the CP-net h:

Since CP T created becomes true, {D} is returned by procedure extendNetwork, the set X is updated, and the procedure extendNetwork is invoked anew. The variable B is (necessarily) chosen. All attempts to create CPT(B) with an empty or singleton parent set fail. When the procedure createCPT(B, {A,D} ,P, h) is invoked, it succeeds and adds the following CPT as CPT(B) in the CP-net h:

The procedure extendNetwork returns {B}, and in its subsequent call it returns ∅. Since X is now empty, the algorithm returns the CP-net h, and terminates.

4 Properties of the Learning Algorithm

We now prove the soundness and completeness of the presented algorithm. For every outcome o over the set V of variables, and every subset S ⊆ V, o[S] denotes the projection of o on S; to avoid clattering, for every X ∈ V, we write o[X] instead of o[{X}]. In the outcome o[S1] o[S2] . . . o[Sn]o, with Si ⊆ V and 1 ≤ i ≤ n, it holds that o ∈ Asst(V \ (S1 ∪ S2 ∪ . . . ∪ Sn)). Finally, for every CP-net N over V, and every X ∈ V, ℓN(X) denotes the level of X in N.

Theorem 2 (Soundness of Algorithm learn). If the call learn(V,P) returns a CP-net h, then h entails every pairwise comparison between outcomes in P.

Proof (sketch). Let Vn = {X | X ∈ V and ℓh(X) ≤ n}. We show that for every oi ≻ oj ∈ P, and every positive integer n, if oi[Vn] ̸= oj[Vn] then h |= oi[Vn]o ≻ oj[Vn]o for every appropriate choice of o. The result follows when n = |V|. Let V ′n = {X | X ∈ Vn \ Vn-1 and oi[X] ̸= oj[X]}.

We proceed by induction on n. The base case n = 1 follows easily, and we omit the proof. Assume that the claim holds for all values up to some n ≥ 1, and consider the case of n + 1. Assume oi[Vn+1] ̸= oj[Vn+1]. We only consider the case V ′n+1 ̸= ∅. Let X ∈ V ′n+1 and x1 = oi[X], x2 = oj[X]. Then the CPT of X contains either (i) the entry oi[Pah(X)] : x1 ≻ x2, or (ii) the entry oj[Pah(X)] : x1 ≻ x2. In case (i), N |= oi[Vn] oi[X]o ≻ oi[Vn] oj[X]o. By the inductive hypothesis, N |= oi[Vn] oj[X]o ≻ oj[Vn] oj[X]o (or oi[Vn] = oj[Vn]), and by transitivity, N |= oi[Vn] oi[X]o ≻ oj[Vn] oj[X]o. In case (ii), N |= oj[Vn] oi[X]o ≻ oj[Vn] oj[X]o. By the inductive hypothesis, N |= oi[Vn] oi[X]o ≻ oj[Vn] oi[X]o (or oi[Vn] = oj[Vn]), and by transitivity, N |= oi[Vn] oi[X]o ≻ oj[Vn] oj[X]o. In either case it follows that for every X ∈ V ′n+1 , N |= oi[Vn] oi[X]o ≻ oj[Vn] oj[X]o.

Now let V in+1 = {Xi1 , . . . ,Xi b } = {X | X ∈ V ′n+1 and CPT(X) contains oi[Pah(X)] : x1 ≻ x2}, and define V jn+1 analogously. Let V i,- n+1 = {Xi1 , . . . ,Xi b-1}. It follows that N |= omo ≻ om+1o, for 1 ≤ m < b, where o1 = oi[Vn] oi[V i,- n+1 ] , ob-1 = oi[Vn] oj[V i,- n+1 ] , and om differs from om+1 in the value of exactly one variable X ∈ V i,- n+1 , with om[X] = oi[X] and om+1[X] = oj[X]. By transitivity, N |= oi[Vn] oi[V i,- n+1 ]o ≻ oi[Vn] oj[V i,- n+1 ]o.

We have already shown that N |= oi[Vn] oi[Xi b ] oj[V i,- n+1 ]o ≻ oj[Vn] oj[Xi b ] oj[V i,- n+1 ]o. Thus, N |= oi[Vn] oi[Xi b ] oi[V i,- n+1 ]o ≻ oj[Vn] oj[Xi b ] oj[V i,- n+1 ]o; equivalently N |= oi[Vn] oi[V in+1 ]o ≻ oj[Vn] oj[V in+1 ]o. Using similar arguments it holds that N |= oj[Vn] oj[V in+1 ] oi[V jn+1 ]o ≻ oj[Vn] oj[V in+1 ] oj[V jn+1 ]o. Hence, N |= oi[Vn] oi[V in+1 ] oi[V jn+1 ]o ≻ oj[Vn] oj[V in+1 ] oj[V jn+1 ]o, or equivalently N |= oi[Vn+1]o ≻ oj[Vn+1]o, as needed. ✷

Note that the soundness of the algorithm is unconditional. Given Theorem 1, however, we cannot hope for an unconditional completeness result also. We establish completeness for a special case, that of learning CP-nets that not only entail the comparisons in a set P, but do so in a transparent manner.

Definition 5 (Transparent Entailment). Consider a CP-net N over a set V of variables that entails every comparison in a set P of pairwise comparisons between outcomes over V.

N transparently entails P if for every oioi[PaN(X)] oi[X] ≻ ojoj[PaN(X)] oj[X] ∈ P with oi[X] ̸= oj[X], N entails either ooi[PaN (X)] oi[X] ≻ ooi[PaN(X)] oj[X] or ooj[PaN(X)] oi[X] ≻ ooj[PaN(X)] oj[X] for some o ∈ Asst(V \ (PaN(X)∪{X})).

Note that transparency does not restrict the complexity of a CP-net, but indicates how detailed information P offers about the CP-net. It is easy to show that if P contains comparisons only between outcomes that differ on exactly one variable (in some sense, the best one can hope for, given Theorem 1), then entailment and transparent entailment coincide. Transparent entailment is, however, a broader notion. Indeed, if P contains only the preference a1b1c1 ≻ a2b2c2, then the CP-net N over the variables A, B, C, and with their CPTs containing : a1 ≻ a2, : b1 ≻ b2, and a1b1 : c1 ≻ c2 irrespectively of the other entries, transparently entails P. Yet, the preference in P is between outcomes that differ on three variables. If P is extended with a1b1c2 ≻ a1b1c1 and a2b2c2 ≻ a2b2c1, then no CP-net transparently entails P. Moreover, the algorithm returns failure, although there is a CP-net that entails P.

Theorem 3 (Completeness of Algorithm learn). Consider a set P of pairwise comparisons between outcomes over a set V of variables. If some CP-net N ∈ Nk over V transparently entails P, then the call learn(V, P) returns a CP-net h ∈Nk.

Proof (sketch). Consider the Steps (4)-(13) of learn(V,P) during the k-th iteration, and assume by way of contradiction that X ̸= ∅ at Step (9). Then, the last invocation of extendNetwork(X , V ′ , P, k, h) at Step (4) returned ∅; note that V ′ = V \ X. Choose X ∈ X such that no variable in X is a parent variable for X in the CP-net N; since N is acyclic, this can always be done. It follows that all parent variables PaN(X) of X in N are in V \ X. Since extendNetwork(X, V ′ ,P, k, h) returned ∅, it follows that the invocation of createCPT(X, U, P, h) failed when U = PaN(X); a contradiction by the transparency assumption. ✷

Roughly, transparency implies that the preferences in P offer information for the dependency of a variable on its parents to be "easily" determined. Thus, backtracking is avoided.

By Theorems 2 and 3, and by observing that learn(V,P) runs in time poly(|P|, |V|k ), we obtain:

Corollary 2 (Consistent-Learning CP-Nets). The class Nk of CP-nets over a set V of variables is consistent-learnable in time poly(|P|, |V|k ) given a set P of pairwise comparisons between outcomes over V that is transparently entailed by some N ∈ Nk. In particular, the result holds if all comparisons between outcomes differ on exactly one variable.

5 Learning with Predictive Guarantees

Beyond simply fitting the available data, the ultimate goal in many real-world domains is to confidently predict a user's preferences on future, and possibly previously unseen, occasions. We examine next a learning setting that builds on the Probably Approximately Correct semantics [Valiant, 1984].

A learner observes the user's preferences, modelled as being entailed by some unknown CP-net N ∈ N. To account for the learner's lack of control on what such preferences are obtained, the preferences are assumed to be randomly drawn from some unknown probability distribution D.

Definition 6 (Random Instance Oracle). Given a set V of variables, a probability distribution D over unordered outcome pairs over V, and a CP-net N over V, the (transparent) random instance oracle R(D; N) is a procedure that runs in unit time, and on each call o1 ≻ o2 ← R(D;N) returns a comparison o1 ≻ o2, where {o1, o2} is drawn randomly and independently from D, and N (transparently) entails o1 ≻ o2.

Definition 7 (CP-Net PAC-Learnability). A class N of CPnets over a set V of variables is PAC-learnable (by a class H of hypotheses) if there exists an algorithm L such that for every probability distribution D over unordered outcome pairs over V, every CP-net N ∈ N , and every pair of real numbers δ, ε ∈ (0, 1], algorithm L has the following property: given access to V, R(D;N), δ, and ε, algorithm L runs in time polynomial in |V|, 1/δ, 1/ε, and size(N), and with probability 1 - δ returns a hypothesis h (in H) such that

Except with an arbitrarily small probability of failure δ, a learner is expected to return a hypothesis h ∈ H that correctly predicts the user's preference o1 ≻ o2 in an arbitrarily high fraction 1 - ε of occasions. An appropriate increase in the allowed resources compensates for this requirement. Although the learner need not return a CP-net as its hypothesis, restricting the learner to do so is possible by fixing H = N .

We show that learnability under these strong requirements is possible, by observing that the algorithm presented earlier produces concise CP-nets h ∈ N with maximum in-degree that does not exceed that of the hidden target CP-net N ∈ N.

Theorem 4 (The Effect of Conciseness). Consider a class Nk of CP-nets over a set V of variables. If Nk is consistentlearnable by Nk, then Nk is PAC-learnable by Nk.

Proof (sketch). The consistent-learnability of Nk implies an (α, β)-Occam algorithm for Nk using Nk, for some constant α and β = 0. The claim follows by standard results [Kearns and Vazirani, 1994, pp. 33-34, Theorem 2.1]. ✷

An immediate consequence of Theorem 4 is that all hardness results for PAC-learnability that we establish in the remainder of this work also apply to consistent-learnability. On the positive side, Theorem 4 implies:

Corollary 3 (PAC-Learning CP-Nets). The class Nk of CPnets over a set V of variables is PAC-learnable by Nk, if a transparent random instance oracles is employed, and time poly(|V|k ) is allowed in addition to the time prescribed by Definition 7. (Observe that since size(N) ≥ 2k for every N ∈ Nk, then poly(|V|k ) ≤ poly(size(N)log |V | ).)

We emphasize that modulo the restriction imposed on the random instance oracle (corresponding to a restriction on the probability distributions from which comparisons are drawn), and the quasi-polynomial in |V| running time, Corollary 3 establishes that the presented algorithm is a PAC-learner as per Definition 7. Furthermore, if CP-nets with a constant indegree are considered, the algorithm runs in polynomial time.

While more efficient algorithms could conceivably exist, we show that this is unlikely, since such algorithms could be used to PAC-learn the class of k-juntas - the class of all boolean functions over n variables that depend on at most k of them, albeit in any arbitrary manner. No PAC-learner for the class of k-juntas is known that runs in time poly(n) for non-constant values of k; the most efficient known one requires time poly(nk ). Improving upon this time would resolve a major long-standing open problem in Computational Learning Theory [Blum, 2003], one, in fact, that was shown to be in the heart of numerous other open problems.

Theorem 5 (Reduction of k-Junta to CP-Net Learning). Let Jk be the class of k-juntas over n variables. Consider the class Nk of all CP-nets over some set V of n + 1 variables (and can even assume that all but one variables have zero parents). If Nk is PAC-learnable (by Nk) in time t, then Jk is PAC-learnable (by Jk) in time poly(t, n).

Proof (sketch). Introduce a variable Vi ∈ V for each of the n variables xi over which k-juntas are defined, and an additional variable Q ∈ V that corresponds to the output of k-juntas. For each v ∈ {0, 1}, let v be s.t. {v, v} = {0, 1}.

For each k-junta ϕ ∈ Jk that depends on the variables {xi1 , . . . , xik } let the CP-net net(ϕ) ∈ Nk over V be s.t.: net(ϕ) includes links from the variables in {Vi1 , . . . , Vik } to the variable Q, and CPT(Q) contains for each input in of ϕ the entry in : ϕ(in) ≻ ϕ(in). Observe, then, that ϕ(in) = out if and only if net(ϕ) |= inout ≻ inout.

The bijection between inputs/outputs of ϕ to comparisons entailed by net(ϕ) is computable in time polynomial in n; thus, a PAC-learner for Nk implies a PAC-learner for Jk.

Finally, if Nk is PAC-learned by Nk, then CPT(Q) contains at most 2k entries, which determine a k-junta in Jk. ✷

Note, in particular, that the reduction preserves a properness property: the PAC-learner returns a hypothesis in the same class as the target concept, as opposed to some other hypothesis class H. Recent results imply that properly PAClearning k-juntas is W[2]-hard [Arvind et al., 2007, Lemma 4], which amounts to an intractability result for obtaining a PAC-learner for k-juntas that runs in time g(k)poly(n), for any computable function g. By Theorem 5, we have that:

Corollary 4 (Fixed-Parameter PAC-Learning Hardness).

PAC-learning the CP-net class Nk by Nk is W[2]-hard.

6 Conclusions

The importance of preference learning has been recognized in different scientific areas. This paper presents some of the first results, both positive and negative, concerning the problem of learning CP-nets. On the positive side it introduces a polynomial-time learning algorithm for a restricted class of input examples and CP-nets. Moreover, it establishes that CPnets that can be learned by this procedure are PAC-learnable. On the negative side it proves that learning is intractable even for rather simple cases. It also shows that properly PAClearning CP-nets of bounded in-degree is W[2]-hard.

There are many possibilities for future research. In one direction we plan to investigate the integration of our approach with the global consistency of [Lang and Mengin, 2008]. An input comparison a ≻ b understood under global consistency, requires that the learned CP-net does not entail b ≻ a. Thus, it is possible to learn with both kinds of comparisons, where those under entailment can be seen as positive examples, and those under global consistency as negative ones. We also intent to study the learnability of other CP-net classes, including the case of CP-nets over non-binary variables, as well the case of the more expressive TCP-nets [Brafman et al., 2006]. In the former case, the algorithm presented herein can be generalized to use a SAT/CSP solver for solving general constraint satisfaction problems. State of the art solvers have been proven very effective in solving real-world problems, and this efficiency can be exploited for learning CP-nets.

Investigating different learning paradigms is another possible line of research. For instance, it would be of practical importance to devise techniques for learning when only partial assignments are available, or when the data does not perfectly fit any hidden CP-net. Finally, online learning is another direction, where the learner is given (possibly adversarially chosen) preferences one by one, and each time makes a prediction on the next preference before obtaining it.