Learning Conditional Preference Networks with Queries

1 Introduction

The spectrum of AI applications that resort on the ability to reason about preferences is extremely wide, ranging from configuration softwares and recommender systems to autonomous agents and group decision-making. As many, if not most, of these applications are defined over large, multiattribute domains, a key challenge in preference research is to develop representation languages and elicitation techniques that cope with the exponential size of the outcome space.

Conditional preference networks (CP-nets), have emerged as an expressive language capable of representing ordinal preferences relations in a compact and structured manner [Boutilier et al., 2004]. Briefly, a CP-net is a graph where each node is labelled with a table describing the user's preference over alternative values of this node given different values of the parent nodes. For example, the entry Jb ∧Pb : Sr ≻ Sb might state that, all other things being equal, I prefer a red shirt than a black one if the color for both the jacket and the pants is black. The semantics of a CP-net is defined by a dominance ordering on the outcome space, derived from such reading of entries in the tables. Based on this relation, a key reasoning task is dominance testing: given a CP-net N and a pair of outcomes (o, o′ ), determine whether o dominates o′ , according to the dominance ordering induced by N.

Bruno Zanuttini

GREYC, CNRS UMR 6072 Université de Caen Basse-Normandie, France bruno.zanuttini@info.unicaen.fr

Ideally, in preference elicitation with CP-nets, the decision-maker should simply "fill the tables" by asking the user how her preference over the values of one node depends on the values of its parents. Yet, in practice, eliciting preferences is far from easy because the dependency graph is generally not known in advance: the decision-maker must therefore seek the interdependencies between attributes and identify a minimal set of parents for each target node. The problem is exacerbated still further by the fact that real-world applications typically involve many irrelevant attributes. For instance, it is not uncommon in recommender systems to describe products using thousands of variables, with the expectation that only a small fraction of these are crucial for describing preferences [Basilico and Hofmann, 2004; Ziegler et al., 2008]. The decision-maker is thus required to select, within a large collection of attributes, a relatively small subset over which the network will be specified.

Such considerations bring into sharp focus the need for query learning algorithms that aim at extracting CP-nets by guiding the user through an appropriate sequence of queries. A widely adopted framework for studying this issue is the model of exact learning with equivalence and membership queries [Angluin, 1988]. In essence, equivalence queries simulate a form of passive learning in which the decision-maker observes the user's behavior until she finds a counterexample to her hypothesis. By contrast, membership queries capture a form of active learning by allowing the decision-maker to ask about examples of her own choice. The utility of this model lies in the fact that rich concept classes, including Horn theories, decision trees, and some description logics, have been shown to be learnable with both equivalence queries and membership queries, while in weaker versions one can prove superpolynomial lower bounds [Angluin et al., 1992; Bshouty, 1995; Frazier and Pitt, 1996].

In the learning model suggested by this study, the target concept is a dominance ordering on the outcome space. Each example is a preference situation involving some pair of outcomes. For a membership query, the learner supplies an example (o, o′ ) and is told whether o dominates o′ , or not. For an equivalence query, the learner presents a CP-net N, and either is told that N correctly identifies the target concept, or it is given a counterexample (o, o′ ). The goal is to identify the target concept using as few resources as possible, where resources refer both to the run time and the number of queries.

From a practical perspective, one must take into account the fact that outcomes are typically not comparable with an equivalent cost. As observed in [Green and Srinivasan, 1978], users can meaningfully compare outcomes if they differ only on very few attributes. Similarly, for the learner, this task can be arduous because dominance testing is generally NP-hard, even for acyclic CP-nets. Thus, our learnability results are defined in terms of a concept class in which the target concept is chosen, and an instance class that circumscribes the set of examples used by equivalence and membership queries.

The key message to be gleaned from this paper is that active learning is required to correctly and efficiently extract preference networks in binary-valued domains. On the one hand, acyclic CP-nets are not learnable with equivalence queries alone, while on the other, they are learnable with equivalence and membership queries, provided that the instance class is restricted to simple outcome pairs for which dominance testing takes linear time. Interestingly, a similar property holds for tree-structured CP-nets by extending the instance class to arbitrary examples. When membership queries are available, we provide attribute-efficient learning algorithms for which the query complexity is linear in the size of the minimal CP-net that identifies the target concept, and logarithmic in the total number of attributes. Such encouraging results pave the way for fast elicitation techniques capable of extracting "small" CP-nets in "large" domains.

2 Conditional Preference Networks

The learning problems under consideration in this study are defined over a set of Boolean variables X = {x1, · · · , xn}. As usual, we refer to xi and xi as literals. Given a literal p, we denote by p the opposite of p; for example, if pi is xi, then pi is xi. A term t is a conjunction of literals. By var(t) we denote the set of variables occurring in t. A term t is maximal for a subset of variables Y ⊆ X if var(t) = Y .

A conditional preference rule (CP-rule) on a variable x is an expression of the form t : p ≻ p, where p is a literal of x and t is a term such that x ̸∈ var(t). Such a rule captures the statement "given that t holds, the value p is preferred to the value p for the variable x, all other things being equal".

A conditional preference table (CP-table) on a variable x with respect to a set Y ⊆ X \ {x} is a set of CP-rules on x that associates at most one rule t : p ≻ p to each maximal term t for Y . The CP-table is complete if exactly one rule t : p ≻ p is associated to each maximal term t for Y .

A conditional preference net (CP-net) is a labelled digraph N over a subset var(N ) of X, where each node x ∈ var (N ) is annotated with a CP-table cpt(x) on x with respect to the set Pa(x) of parents of x in the graph. The CP-net is complete if any node x ∈ var(N ) is annotated with a complete CPtable. A CP-net is acyclic if its digraph is acyclic, and treestructured if its digraph forms a forest, that is, a set of trees.

These notions are illustrated in the left part of Figure 1, where an acyclic complete CP-net is specified for the popular evening dress scenario. I unconditionally prefer black (j, p) to white (j, p) as the color of both the jacket and the pants, while my preference for a red shirt (s) versus a white one (s) depends on the combination of jacket and pants.

An outcome is a maximal term o for X. Given a term t, we write o[t] for the outcome obtained by making o agree with t, i.e. o[t] = {p : p ∈ t or p ∈ o - t}. For example, if o = x1x2x3 and t = x1x2, then o[t] = x1x2x3. An outcome o satisfies a term t if o = o[t]. We write 0 (resp. 1) for the outcome that assigns 0 (resp. 1) to every variable in X.

The ceteris paribus semantics of a CP-rule t : p ≻ p on a variable x can be described as follows: if an outcome o satisfies the condition t and assigns the value p to x, then it is preferred to an outcome o′ which differ from o only in that is assigns the value p to x. In formal terms, we say that o is preferred to o′ for t : p ≻ p if o = o[t ∧ p] and o′ = o[p]. In this case, (o, o′ ) is called a model of the rule t : p ≻ p.

Given a CP-net N and two outcomes o and o′ , we say that o dominates o′ for N if there is a sequence (o1, · · · , om) such that o1 = o′ , om = o and for each i : 1 ≤ i < m, (oi+1, oi) is a model of some CP-rule of N. In this case, (o, o′ ) is called a model of N, and (o1, · · · , om) an improving sequence from o′ to o. The dominance ordering of N, denoted ≻N, is the set of all models of N. For example, the dominance ordering of the CP-net for evening dress is the transitive closure of the digraph displayed in the right part of Figure 1.

A CP-net N is consistent if there is no outcome o which dominates itself, i.e. o ≻N o. If N is consistent, then ≻N is a strict partial order over the outcome space. As reported in [Boutilier et al., 2004], any acyclic CP-net is consistent.

Given two CP-nets N and N ′ , we say that N subsumes N ′ if for any CP-rule t′ : p ≻ p in N ′ , there is a CP-rule t : p ≻ p in N such that t′ ⊆ t. A CP-net N is minimal if there is no distinct net N ′ subsumed by N and for which ≻N=≻N ′ . For example, the CP-net in Figure 1 is minimal.

Finally, the size |r| of a CP-rule r will be the number of occurrences of literals in its definition. Specifically, if r is of the form t : p ≻ p, then |r| = |t|+2. The size |N| of a CP-net N will be the sum of |r| over all rules r in N. For example, the size of the CP-net in Figure 1 is 2+2+4 × (2+2) = 20.

3 Exact Learning with Queries

The learning criterion expected in this study is that of exact identification, which is achieved if the learner can infer a CPnet that correctly represents the target concept. A concept is a strict partial ordering ≻ on the outcome space. A representation class is a set N of CP-nets. A concept ≻ is representable by N if there is a CP-net N ∈ N such that ≻N=≻. The concept class CN over N is the set of all concepts that are representable by N. The description size of a concept ≻ in CN will be the minimum of |N| over all representations N of ≻ in N. Finally, an instance or example is a pair (o, o′ ) of outcomes, and an instance class is a set O of examples.

Let ≻ be a target concept of some concept class CN, and O be an instance class. The learner may extract information about ≻ using two types of queries. A membership query MQ over O takes an example (o, o′ ) ∈ O and returns Yes if o ≻ o′ , and No otherwise. An equivalence query EQ over O takes a CP-net N ∈ N, and returns Yes if N is a representation of ≻, or returns a counterexample (o, o′ ) ∈ O otherwise. The counterexample (o, o′ ) is positive if o ≻ o′ and o ⊁N o′ , and negative if o ⊁ o′ and o ≻N o′ .

Definition 1. An algorithm A is a query learning algorithm for a concept class CN with respect to an instance class O if there are two polynomials p and q such that, for any target concept ≻ in CN , after p(n) membership and equivalence queries over O, and total running time in q(n), A outputs a representation N ∈ N of ≻. It is attribute-efficient if the number of queries p(n) is polynomial in the description size of ≻, but only polylogarithmic in the number of variables n.

Given an instance class O, we say that a concept class CN is attribute-efficiently learnable if there is an attributeefficient query learning algorithm for CN with respect to O.

Clearly, the strength of query-directed learning lies in membership queries, which model not only the interaction with a user, but also the careful crafting of experiments by a decision-maker in order to observe the response of the user. In order to demonstrate that a class of CP-nets is not learnable with equivalence queries alone, we shall use the technique of approximate fingerprints introduced in [Angluin, 1990].

Intuitively, a concept class CN has approximate fingerprints if it includes a set C ∗N such that for each hypothesis N in CN supplied by the learner, the user can choose a counterexample for N that eliminates only a superpolynomially small fraction of candidate concepts in C ∗N . By repeating this process, the learner cannot be certain of the target concept in C ∗N after only polynomially many equivalence queries.

A pair (o, o′ ) of outcomes is called an α-fingerprint of a concept class C ∗N according to some concept ≻1 if

Formally, a concept class CN has approximate fingerprints with respect to an instance class O if for any polynomial p(n), CN includes a subclass C ∗N such that for any sufficiently large n, C ∗N contains at least two concepts, and for all concepts ≻ in CN of description size bounded by p(n), there is an example in O which is a 1 p(n) -fingerprint of C ∗N according to ≻.

4 Learning Acyclic CP-nets with Queries

Acyclic CP-nets take a central part in preference research by providing the right level of expressivity for many real-world applications, while remaining tractable for certain reasoning tasks such as outcome optimization [Domshlak et al., 2001; Boutilier et al., 2004]. We begin with some useful properties.

Two outcomes form a swap if they differ in the value of only one variable. Such examples correspond to simple situations of the form "for this car I prefer it red than white", where the color is one of the multiple attributes of the car. The next property states that, in acyclic CP-nets, swaps can be retrieved in linear time by simple rule matching.

Lemma 1. Let N be an acyclic CP-net and (o, o′ ) be a swap. Then o ≻N o′ if and only if there is a CP-rule r in N such that (o, o′ ) is a model of r.

Proof. The if direction is immediate. Conversely, if o ≻N o′ , then there is an improving sequence from o′ to o in N. Assume w.l.o.g. that o satisfies x1 and o′ = o[x1]. Using the suffix fixing rule [Boutilier et al., 2004, Section 5.1], we can also assume that the sequence affects only x1 and its ascendants in N. By acyclicity, one of those ascendants xk is modified but has none of its parents modified in the sequence. Thus, xk cannot be modified back to its value in o′ , which entails xk = x1. So only x1 is modified, which concludes.

A CP-net N is a minimal representation of a concept ≻ if N represents ≻ and |N| is minimal.

Lemma 2. For the class CACY of acyclic CP-nets, the minimal representation of any concept is unique.

Proof. Let ≻ be a concept in CACY and N a representation of ≻ satisfying the following: for any variables x and y, and any rule r ∈ N on x, if y is a parent of x in N, then there is a model (o, o′ ) of r such that exactly one of (o[y], o′ [y]) and (o[y], o′ [y]) is not a model of r. This amounts to say that y is a relevant parent of x. Clearly, such a representation exists: take any representation and remove all irrelevant parents. Now let N ′ be any representation of ≻; we show that N ′ subsumes N. Let r ∈ N be a rule of the form t : p ≻ p. Any swap (o, o′ ) for which o = o[t ∧ p] and o′ = o[p] is a model of r. Since ≻N=≻N ′ , by Lemma 1, (o, o′ ) must be a model of some rule r′ in N ′ of the form t′ : p ≻ p. If t ⊈ t′ , then there is a variable y ∈ var(t) \ var(t′ ) such that (o[y], o′ [y]) and (o[y], o′ [y]) are both models of r′ , but exactly one of these pairs is not a model of r, contradicting the fact that ≻N=≻N ′ . So t ⊆ t′ , and hence, N ′ subsumes N.

We now show that acyclic and complete CP-nets have approximate fingerprints, even if examples are restricted to swaps. Thus, by applying Theorem 1 in [Angluin, 1990], they are not learnable with equivalence queries alone.

Theorem 1. The class CACC of acyclic complete CP-nets has approximate fingerprints with respect to swap examples.

Proof. Let C ∗ ACC be the class of all concepts represented by a CP-net N ∗ with logn root nodes xj pointing to the same fixed child node x1. Each table cpt(xj) has the rule xj ≻ xj . The table cpt(x1) includes one rule s : x1 ≻ x1, where s is the conjunction of all positive literals in Pa(x1), and n - 1 rules s′ : x1 ≻ x1, where s′ is any maximal term of Pa(x1) with at least one negative literal. Clearly N ∗ is acyclic and complete. Furthermore, |C ∗ ACC | = ( n-1 log n). Now, let p(n) = nk for some constant k, and let N ∈ CACC with |N| ≤ p(n).

The fingerprint (o, o′ ) is defined as follows. If N does not include any rule of the form t : x1 ≻ x1, then we let o = 1 and o′ = o[x1]. Then o ⊁N o′ but o ≻ o′ for any concept ≻ in C ∗ ACC . So (o, o′ ) is an α-fingerprint of C ∗ ACC for any α > 0.

Now, if N includes a rule of the form t :x1 ≻x1, then o is any outcome satisfying t ∧ x1 and containing k log n positive literals excluding x1, which can be constructed as follows. Because N is complete, the size of its table on x1 is more than 2|t| . Since |N| ≤ nk we get |t| ≤ k logn. Thus, o can be constructed by satisfying t first and filling the rest as necessary. Again, o′ = o[x1]. So o ≻N o′ and o has k logn positive literals (excluding x1). Hence, the number of concepts ≻ in C ∗ ACC for which o ≻ o′ is (k logn logn ). Using a-i b-i ≤ ab ,

Taking logarithms, this proportion is less than 1 nk if and only if n-1 log n > k2k , which is true for sufficiently large n.

When membership queries are available, we can provide an attribute-efficient algorithm for learning acyclic, and possibly incomplete, CP-nets, provided that the supplied examples are restricted to swaps. As specified in Algorithm 1, the learner iteratively updates her hypothesis N by asking equivalence queries. On seeing a counterexample (o, o′ ), the learner checks whether N includes a rule that covers either (o′ , o) or (o, o′ ). If this is indeed the case, she asks membership queries in order to refine the condition of that rule. Otherwise, she expands her net with a new rule. Here, each rule r of the form t : pi ≻ pi is associated with an outcome or, called the support of r, and such that (or[pi], or[pi]) is a model of r.

The key routine SEARCHPARENT finds a new parent of some misclassifying rule r, using only a logarithmic number of membership queries. Using the support or of r and the last counterexample (o, o′ ), it operates a binary search on the sequence (o1, · · · , on) where oj is formed by the first j literals occurring in or and the last n - j literals occurring in o. As shown in the lemma below, SEARCHPARENT is guaranteed to find a new parent in the rule r, by maintaining the invariant that for each explored subsequence (oa, · · · , ob), we have both oa[pi]⊁oa[pi] and ob[pi]≻ob[pi] in the target concept.

Lemma 3. Let ≻ be a concept of CACY, oa, ob be two outcomes, and pi, pi be a pair of opposite literals for some variable xi. If we have oa[pi] ⊁ oa[pi] and ob[pi] ≻ ob[pi], then there is a parent xj of xi in the minimal representation N ∗ of ≻ whose value is different in oa and ob.

Proof. Consider the outcome sequence (o0, · · · , on) where oj = oa[tj] with tj the conjunction of the first j literals in ob. Since o0 = oa and on = ob, there is some j > 0 such that oj-1[pi] ⊁ oj-1[pi] and oj[pi] ≻ oj[pi]. So there is a rule t : pi ≻ pi in N ∗ such that oj satisfies t but oj-1 does not. Since they differ only on xj , we get xj ∈ var(t).

Lemma 4. Let ≻ be a target concept in the class CACY. Then Algorithm 1 maintains an acyclic CP-net N which is always subsumed by the minimal representation N ∗ of ≻.

Algorithm 1: Learning Acyclic CP-nets

let xi be the variable s.t. pi ∈ o and pi ∈ o′ if (o′ , o) is a model of some rule 〈r, or〉 in N then (o, o′ ) ← (o′ , o) if (o, o′ ) is a model of some rule 〈r, or〉 in N then /∗ The counterexample is negative ∗/ xj ← SEARCHPARENT(xi, pi, o, or, 0, n) foreach rule 〈r′ , or′ 〉 in the table of xi expand the condition of r′ with the literal of xj in or′ else/∗ The counterexample is positive ∗/ add the rule 〈t : pi ≻ pi, o〉 to N where t is the projection of o onto the set Pa(xi) in N

return N

Procedure SEARCHPARENT(xi, pi, o, o′ , a, b) if a = b + 1 then return xb j ← ⌊(a + b)/2⌋ oj ← o[tj] where tj are the first j literals occurring in o′ if MQ(oj [pi], oj [pi]) = Yes then return SEARCHPARENT(xi, pi, o, o′ , a, j) else return SEARCHPARENT(xi, pi, o, o′ , j, b)

Proof. Initially, N = ∅, so the property holds. Now, consider an iteration of the main loop and suppose by induction hypothesis (I.H.) that N is subsumed by N ∗ before calling EQ. If EQ returns a positive counterexample (o, o′ ), then by Lemma 1 N ∗ includes a rule t∗ : pi ≻ pi for which o = o[t∗ ∧ pi] and o′ = o[pi]. Then N is expanded with t : pi ≻ pi where t is the projection of o onto the parent set Pa(xi) of xi in N. Since (by I.H.) N is subsumed by N ∗ , we have Pa(xi) ⊆ Pa ∗ (xi), where Pa ∗ is the parent set in N ∗ . Therefore t ⊆ t∗ , and hence, the invariant is preserved.

Dually, if EQ returns a negative counterexample (o, o′ ), then by Lemma 1 N includes a rule r of the form t : pi ≻ pi for which o = o[t∧pi] and o′ = o[pi]. By construction, for the support or of r we also have or = or[t ∧pi], and or ≻ or[pi]. So by Lemma 3, SEARCHPARENT returns a parent xj of xi in N ∗ . Now, let r′ be any rule of the form t′ : p′i ≻ p′i . Since the support or′ of r′ satisfies or′ [p′i ] ≻ or′ [p′i ], by I.H., there is a rule t∗ : p′i ≻ p′i in N ∗ such that t′ ⊆ t∗ and or′ satisfies t∗ . This together with the fact that xj is a parent of xi in N ∗ ensures t′ ∪ {pj} ⊆ t∗ , so the invariant is preserved.

Now let us examine the complexity of Algorithm 1. For equivalence queries, each counterexample allows us to find a new rule t : pi ≻ pi or a new literal pj of some rule in the minimal representation N ∗ of the target concept. Because the hypothesis N is always subsumed by N ∗ , this can happen at most |N ∗ | times. For membership queries, at most logn of these are used in each call of SEARCHPARENT, which always uncovers a new parent of some variable. So the number of these queries is at most e log n, where e = ∑i Pa(xi).

Theorem 2. The class CACY is attribute-efficiently learnable from equivalence and membership queries over swaps: any concept ≻ in CACY can be identified in polynomial time, using at most |N ∗ | + 1 equivalence queries and e⌈log n⌉ membership queries, where N ∗ is the minimal representation of ≻, and e is the number of edges in N ∗ .

5 Learning Tree CP-nets with Queries

Binary-valued tree-structured CP-nets constitute a restricted, yet important, class of preference networks for which dominance testing on arbitrary pairs of outcomes is solvable in quadratic time using a backtrack-free search technique [Boutilier et al., 2004]. It is therefore legitimate to study the learnability issues of this class in the general setting where the examples supplied to the learner are arbitrary preference situations. In this context, we first show that tree-structured CP-nets are not learnable with equivalence queries alone.

Theorem 3. The class CTREE of tree CP-nets has approximate fingerprints with respect to arbitrary outcome pairs.

Proof. We assume w.l.o.g. that n is even to avoid floors and ceilings. To each permutation π of (x1, · · · , xn) we associate the smallest set of rules Nπ such that xπ(1) ≻ xπ(1) is in Nπ, and for each i > 1, Nπ includes xπ(i-1) : xπ(i) ≻ xπ(i). Let C ∗ TREE be the class of all concepts represented by some Nπ specified as above. Clearly, |C ∗ TREE | = n!. Now, let p(n) = nk for some constant k and let N ∈ CTREE with |N| ≤ p(n). 1

The fingerprint (o, o′ ) is defined as follows. Assume first that there is an outcome o1 containing at least n/2 ones and such that (o1, 0) is a model of N. Then there is an improving sequence from 0 to o1 in N, and since variables are flipped one by one, it must contain an outcome o with exactly n/2 ones. Moreover, by construction o ≻N 0 holds. Let o′ = 0. We claim that (o, o′ ) is an 1 nk -fingerprint of C ∗ TREE w.r.t. ≻N. Indeed, a concept Nπ in C ∗ TREE has (o, o′ ) as a model if and only if the first n/2 variables according to π are exactly those assigned 1 by o. Otherwise, any improving sequence in Nπ should flip at least one variable assigned 0 by both o and o′ , with no way back, a contradiction. It follows that there are (n/2)!(n/2)! concepts in C ∗ TREE with (o, o′ ) as a model, hence

which is clearly less than 1 nk for sufficiently large n. Now, assume that there is no o1 as above. Let o = 1 and o′ = 0. So o ⊁N o′ , but o ≻ o′ holds for every concept ≻ in C ∗ TREE . Hence, (o, o′ ) is an α-fingerprint of C ∗ TREE for any α > 0.

As further evidence for the utility of membership queries, we now give an attribute-efficient algorithm for eliciting tree CP-nets in presence of arbitrary examples. Let △(o, o′ ) be the set of all variables whose value differ in two outcomes o and o′ . Algorithm 2 uses the fact that considering only variables in Δ(o, o′ ) and their ascendants is enough for searching

1 For a tree CP-net N, |N| ≤ 6|var(N)| (two rules of size 3 per variable), so if p(n) ≥ 6n, N can be any tree CP-net.

Algorithm 2: Learning tree CP-nets N ←∅ while (o, o′ ) ← [EQ(N ) ̸= Yes] do /∗ The counterexample is necessarily positive ∗/ for each x ∈ △(o, o′ ) do PROPAGATE(x) return N Procedure PROPAGATE(x) if x ∈ var(N ) then return var (N ) ← var (N ) ∪ {x} for o, p ∈ {0, 1} × {x, x} do prefo,p ← MQ(o[p], o[p]) if pref0,p = pref1,p = Yes for some p ∈ {x, x} then parents ← ∅ else if pref0,p = Yes for some p ∈ {x, x} then parents ← {SEARCHPARENT(x, p, 1, 0, 0, n)} else if pref1,p = Yes for some p ∈ {x, x} then parents ← {SEARCHPARENT(x, p, 0, 1, 0, n)} else parents ← ∅ add to N a table for x with parents parents and the rules satisfied by the prefo,p's if parents = {y} then PROPAGATE(y)

an improving sequence from o′ to o. Thus, on seeing a counterexample (o, o′ ), the learner computes the tables for each such variable. Because any variable has at most one parent, its table can be found using few membership queries.

From a practical perspective, note that the examples used in MQ's are restricted to swaps in order to minimize the cognitive effort spent by the user in comparing outcomes. 2

Lemma 5. Let N ∗ be a minimal representation of the target concept in CTREE. Then PROPAGATE is called only on variables x in var(N ∗ ), and always extracts the table of x in N ∗ .

Proof. By construction, when PROPAGATE(xi) is called by Algorithm 2, we must have x ∈ △(o, o′ ) and o ≻ o′ . So x ∈ var(N ∗ ), because otherwise it would have no table in N ∗ and hence, its value could not change along any improving sequence from o′ to o. Now given x ∈ var (N ∗ ), we show that PROPAGATE computes the right set of parents for x.

First, let MQ(0[p], 0[p]) =MQ(1[p], 1[p]) = Yes. Then by Lemma 1 there is a rule t : p ≻ p in N ∗ such that both 0 and 1 satisfy t. Hence t is empty. Now to the second case. Here MQ(0[p], 0[p]) = Yes and MQ(1[p], 1[p]) = No, so by Lemma 3 there is a parent y of x in N ∗ , which is found by SEARCHPARENT. The third case is symmetric. In the last case, all queries answer No, so there is no rule on x in N ∗ , and hence, x has no parent in N ∗ .

Consequently, in all cases PROPAGATE computes the right set of (at most one) parents. Because each possible rule is validated by one of the queries MQ(o[p], o[p]), the table computed for x is the correct one. Furthermore, since each recursive call of PROPAGATE is on a variable y which is the parent of some variable in var(N ∗ ), we have y ∈ var(N ∗ ).

2 In addition, the outcomes 1 and 0 used in PROPAGATE can be replaced by any suitable pair (o, o) for which o = {p : p ∈ o}.

By Lemma 5, it follows that all counterexamples supplied to the learner are positive. Moreover, from the structure of the algorithm it is easily seen that after treating (o, o′ ), the hypothesis N contains the correct tables for all ascendants of all variables in △(o, o′ ). This together with the suffix fixing principle [Boutilier et al., 2004, Section 5.1] ensures that N now agrees with o ≻ o′ , and so that the algorithm converges.

Concerning the complexity of our learning algorithm, the number of equivalence queries is at most |var(N ∗ )| + 1, because each counterexample allows the learner to treat at least one new variable in N ∗ . Likewise, the routine PROPAGATE treats each variable in var(N ∗ ) exactly once, using at most logn + 4 membership queries for computing the pref o,p's plus searching for a parent. Finally, the hypothesis maintained by the learner is always a subtree of N ∗ , and hence, dominance testing can be evaluated in quadratic time.

Theorem 4. The class CTREE is attribute-efficiently learnable from equivalence and membership queries over arbitrary outcome pairs: any concept ≻ in this class can be identified in polynomial time using at most k + 1 equivalence queries and k⌈log n⌉ + 4k membership queries, where k is the number of nodes in the minimal representation of ≻.

6 Discussion

Along the lines of making query-directed learning applicable to preference elicitation, we have provided a model for learning preference networks from equivalence and membership queries, together with significant learnability results. Taking into account the cognitive effort required by human users to answer queries, our model is distinguished by the close way in which it integrates learning and dominance testing, and the insistence on having convergence bounds that are polynomial in the minimal description size of the target concept, but only polylogarithmic in the total number of attributes. In essence, our results reveal that membership queries are essential for extracting both acyclic CP-nets from restricted outcome pairs, and tree CP-nets from arbitrary outcome pairs. Importantly, the examples used by these queries can be limited to "swaps" in order to facilitate their comparison.

To the best of our knowledge, this work provides the first connection between active learning and graphical preference languages. Some authors, though, have recently focused on passive learning, where the goal is to extract a CP-net from a set of examples [Athienitou and Dimopoulos, 2007]. Yet, in this "offline" passive learning model, the problem of finding an acyclic CP-net consistent with a set of arbitrary outcome pairs is NP-hard, even if the dependence graph is known in advance [Lang and Mengin, 2009]. Note that in the "online" passive learning model, acyclic CP-nets are not predictable with a polynomial mistake bound, even if examples are restricted to swaps; this is a direct corollary of Theorem 1, that follows from a standard conversion between online learning and exact learning with EQ's alone [Littlestone, 1988].

Perhaps the closest framework to ours is due to Sachdev [2007], who investigates some preference logics in different learning models. Although encouraging, his results do not take into account the cost of dominance testing, and the query complexity grows exponentially with the size of rules.

A direction of research that naturally emerges from our study is to extend the learnability results to larger classes of preference networks. Algorithm 1 can provide a starting point for attacking multi-valued acyclic CP-nets. Similarly, Algorithm 2 might be extended to directed-path singly-connected CP-nets. Less obvious, however, is to efficiently learn cyclic CP-nets even with swap examples. Finally, the problem of revising CP-nets with queries looks challenging.

Acknowledgments: Thanks to the referees for helpful comments. This work was supported by the ANR project ANR-06-BLAN-083-02.