Fabien Labernia

Florian Yger

Brice Mayag

Jamal Atif

Query-based learning of acyclic conditional preference networks from noisy data

Conditional preference networks (CP-nets) provide a powerful, compact, and intuitive graphical tool to represent the preferences of a user. However learning such a structure is known to be a difficult problem due to its combinatorial nature. We propose in this paper a new, efficient, and robust query-based learning algorithm for acyclic CP-nets. In particular, our algorithm takes into account the incoherences in the user's preferences or in noisy data by searching in a principled way the variables that condition the other ones. We provide complexity results of the algorithm, and demonstrate its efficiency through an empirical evaluation on synthetic and on real datasets.

Introduction

Representing, learning and reasoning over users preferences is a central question in many Artificial Intelligence related fields, and beyond. A large body of research has focused on preference representation and reasoning (e.g. [START_REF] Ronald J Brachman | Knowledge representation[END_REF][START_REF] Peter C Fishburn | Decision and value theory, number 10[END_REF][START_REF] Ralph | Decisions with multiple objectives: preferences and value trade-offs[END_REF][START_REF] Sandholm | Expressive commerce and its application to sourcing: How we conducted $35 billion of generalized combinatorial auctions[END_REF][START_REF] Tsoukiàs | From decision theory to decision aiding methodology[END_REF][START_REF] Walsh | Representing and reasoning with preferences[END_REF]), but few works have concerned their learning (e.g. [START_REF] Chevaleyre | Learning ordinal preferences on multiattribute domains: The case of cp-nets[END_REF][START_REF] Dimopoulos | Ceteris paribus preference elicitation with predictive guarantees[END_REF][START_REF] Eckhardt | How to learn fuzzy user preferences with variable objectives[END_REF][START_REF] Fürnkranz | Preference learning[END_REF][START_REF] Koriche | Learning conditional preference networks[END_REF][START_REF] Lang | Learning preference relations over combinatorial domains[END_REF][START_REF] Liu | Learning conditional preference networks from inconsistent examples[END_REF]). This work focuses on learning combinatorial preferences, in the framework of conditional preference networks (CP-nets) as introduced in [START_REF] Boutilier | Cp-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF].

CP-nets are a formal framework for preference representation based on the notion of ceteris paribus (i.e "all other things being equal"). This notion of ceteris paribus captures an intuitive idea: it is difficult to express one preference between two totally different objects 2 . Nevertheless, it is easier to express one preference between two almost identical ones. In this work, we consider that ceteris paribus means that two objects differ only by one attribute value. For instance, if two hotels differ by their price ceteris paribus, it is probably easier to chose one of them. CP-nets implement this notion by factorizing the preferences, leading to a compact graphical representation.

Learning CP-nets is known to be NP-Complete [START_REF] Alanazi | The complexity of learning acyclic cp-nets[END_REF][START_REF] Boutilier | Cp-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF][START_REF] Chevaleyre | Learning ordinal preferences on multiattribute domains: The case of cp-nets[END_REF], even for acyclic ones. Despite this 'negative' result, some works have tackled this problem, e.g. regression-based learning [START_REF] Eckhardt | How to learn fuzzy user preferences with variable objectives[END_REF][START_REF] Eckhardt | Learning user preferences for 2cpregression for a recommender system[END_REF][START_REF] Liu | Representing conditional preference by boosted regression trees for recommendation[END_REF], learning by reduction to 2-SAT [START_REF] Dimopoulos | Ceteris paribus preference elicitation with predictive guarantees[END_REF], and learning by user queries [START_REF] Chevaleyre | Learning ordinal preferences on multiattribute domains: The case of cp-nets[END_REF][START_REF] Joshua T Guerin | Learning cpnet preferences online from user queries[END_REF][START_REF] Koriche | Learning conditional preference networks[END_REF].

In all these approaches, the preferences of the users are considered to be coherent ones. Some other works take into account of noisy preferences [START_REF] Liu | Learning conditional preference networks from inconsistent examples[END_REF][START_REF] Liu | Learning conditional preference network from noisy samples using hypothesis testing[END_REF]. A noise, also called incoherence or inconsistency, is a preference that does not correspond to the true one, i.e. "I prefer a than b" whereas the true preference is "I prefer b than a". This noise can appear at random, as explained in [START_REF] Angluin | Randomly fallible teachers: Learning monotone dnf with an incomplete membership oracle[END_REF], instead of an adversarial noise [START_REF] Dana Angluin | Malicious omissions and errors in answers to membership queries[END_REF] which is not studied here. In this work, we propose a new, efficient, and robust learning algorithm for CP-nets. Our aim is to come up with a learning procedure with the aim of recommendation systems as illustrated in Figure 1. Classically, a CP-net is constructed for each user. However, in this work, we use a CP-net as a way to aggregate preferences of many users. Our learning procedure can be seen as a way to learn an average CP-net of the common preferences between different users. To do this, we exploit the notion of exact learning, initially proposed by [START_REF] Angluin | Queries and concept learning[END_REF] in the context of query learning.

We focus on the query learning paradigm for CP-nets as introduced in [START_REF] Koriche | Learning conditional preference networks[END_REF]. More precisely, we proceed by querying (a set of users or a database) the preference between two objects that differ by just one attribute value), and in case of incoherence detection, we minimize its influence by choosing the optimal attributes that maximize the coherence of the overall learnt CP-net.

Our learning algorithm is composed of two phases: a general learning phase aiming at adding the preference in the graphical structure of the CP-net, and a parent search phase aiming at updating this graphical structure. This two-phases decomposition is classical in CP-nets learning. However, the originality of our approach lies in these both phases. In the general learning phase, our method add the less possible number of preferences in the structure which significantly decreases the computation time, and in the search parent phase, we propose a principle updating strategy that minimizes the incoherence of the overall structure by choosing the parent variable which splits the large number of rules stemming from the data.

Let us first introduce some notations and concepts related to CPnets [START_REF] Boutilier | Cp-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF].

Conditional preference networks (CP-nets)

Let V = {X1, . . . , Xn} be a set of n binary variables (variables are denoted by capital letters X and sets of variables are denoted by bold letters X). Each variable X ∈ V is associated with a domain Dom({X}) = {x, x } (to simplify the notation, we will omit the brackets and write Dom(X)) of values it can take. The value x ∈ Dom(X) of a variable X ∈ V is called an assignment. We denote by Dom(V) = Dom(X1) × . . . × Dom(Xn) the domain of the values of V. We call a state vector x ∈ Dom(X) which is an assignment of all Xi ∈ X, with X ⊆ V (if X = V, such a vector is called outcome).

We consider in this study a strict preference relation as a partial ordering on Dom(V), i.e. x y meaning that an object x is strictly preferred to an object y.

Let x ∈ Dom(X) and y ∈ Dom(Y) be two states, with X, Y ⊆ V, X ∩ Y = ∅. The notation xy ∈ Dom(X ∪ Y) is the concatenation of the state x and the state y.

Let o, o ∈ Dom(V) be two outcomes. We call a swap, denoted by (o, o )V (which induces o o ), a pair of two outcomes such that the assignment of only one variable V changes between both. This variable is called the swap variable of (o, o )V . Furthermore, o[X] represents the vector of assignments of all variables in the set X ⊆ V (when

X = V, o[X] = o).
A variable X is called a parent variable of another variable V if the assignment of X changes the preference over the assignments of V . More generally, P a(V ) denotes the set of all parent variables of V . This defines a rule r, called CP-rule, of the form r = (u : v v ) with V ∈ V, Dom(V ) = {v, v }, U = P a(V ) ⊆ V \ {V }, and u ∈ Dom(U). If P a(V ) = ∅, we just write r = (v v ). We say that a CP-rule r = (u : v v ) is linked by V . These rules are stored in a structure called CP-table (for conditional preference table), which is unique for each variable Y ∈ V and is denoted by CP T (Y ). A CP-table contains the preferences over the assignment of Y for some states x ∈ Dom(P a(Y )). When all the possible states of P a(Y ) are present, it is said to be complete. We note by CP T (V) the union of all CP-tables in V. More formally

CP T (V) = V ∈V CP T (V ). Definition 1. A conditional preference network (CP-net) N = (V, A, CP T (V)
) is a directed graph with V the set of vertices (representing the variables), A the set of directed arcs such that (X, Y ) ∈ A iff X ∈ P a(Y ), and CP T (V) = V ∈V

CP T (V ).

A CP-net is said complete if its associated CP-tables are complete. We call separable CP-net a CP-net N such that A = ∅, i.e. P a(V ) = ∅, ∀V ∈ V.

A graphic representation of a CP-net and the partial ordering of all possible outcomes is given in Figure 2. One can note that it is a complete and a non-separable CP-net which contains an independent variable (swimming pool) and a variable conditioned by another one (kitchen is conditioned by occupancy).

We say that a CP-net N is cyclic iff there exists a cycle in its associated graph. Otherwise, the CP-net is said acyclic. We restrict our work to acyclic CP-nets.

Query learning algorithms for CP-nets

We discuss in this section the main query learning algorithms for CP-nets. We denote by n the number of variables of a CP-net, i.e. |V| = n, by NT the target CP-net, i.e. the structure that we want to fit, and by NL our learned CP-net.

The first reported query learning algorithm for CP-nets in the literature [START_REF] Koriche | Learning conditional preference networks[END_REF] proceeds by asking different questions to a user in order to learn her preferences. The working assumption is that the user preferences are representable by a CP-net structure. Two types of questions can be distinguished:

• equivalence queries EQ(NL,NT ) which return TRUE if NL is equivalent to NT 3 , otherwise they return FALSE plus a counterex- ample in a form of a swap (o, o )V s.t. o o representing a violated rule r.
• membership queries MQ(NT , r), which return TRUE if the rule r is satisfied in NT (denoted by NT r), otherwise they return FALSE.

When NL = NT , the equivalence query returns a swap counterexample (o, o )V . This swap induces a rule r which (1) if it does not exist in NL, then we just have to add r in NL, or (2) if it is violated in NL, then we have to find a new parent variable for V . In [START_REF] Koriche | Learning conditional preference networks[END_REF], it has been shown that a linear number of equivalence queries (O(|V|)) and a logarithmic number of membership queries (O(log 2 |V|)) are required to learn such a CP-net. For an in-depth explanation of the method, the interested reader can refer to [START_REF] Koriche | Learning conditional preference networks[END_REF].

The second algorithm [START_REF] Joshua T Guerin | Learning cpnet preferences online from user queries[END_REF] is neither based on ceteris paribus comparison nor equivalence and membership queries. It is an online algorithm that learns an acyclic CP-net and is decomposed into two phases:

• finding a separable CP-net by asking for each variable V the preference between v and v , • updating the CP-table of each variable by finding the best set of parent variables using a set of confident4 variables.

In this algorithm, all the parent variables are selected at the same time by phase 2. It seeks a subset of parent variables P from the set of all confident variables C, i.e. P ⊆ C ⊆ V. Moreover, for all P ⊆ C, the entire CP-table of the current variable V is created and tested until a good one is found (i.e. a CP-table that satisfies all the preferences). In the worst case, this algorithm needs 2 2 n operations to determine, for each variable, its parents and its corresponding CP-table .  Due to the exponential nature of this phase, it is necessary to limit the computation by bounding the size p of parent variables, the number e of edges in the target CP-net NT , and the number q of necessary swaps to conclude that a variable becomes confident. Finally, the algorithm can learn a CP-net in O(n p ), with p the maximum number of parent variables. For more details, we refer the reader to [START_REF] Joshua T Guerin | Learning cpnet preferences online from user queries[END_REF].

3 Proposed algorithm for learning a CP-net

Let r = (u : v v ) be a rule with V ∈ V, Dom(V ) = {v, v }, P a(V ) = U ⊆ V \ {V } and u ∈ Dom(U).
For the sake of clarity, we introduce in this section the notations r = (u : v v) as the inverse rule of V , and r p = (up : v v ) as the augmentation of rule r with an assignment p ∈ Dom(P ) of a new parent variable

P ∈ V \ (U ∪ {V }).
As in the algorithm in [START_REF] Koriche | Learning conditional preference networks[END_REF], we query an oracle through EQ(NL, NT ) if our learned CP-net NL is equivalent to its induced (the target) CP-net NT . This oracle can be either a user or a dataset that returns TRUE or FALSE. We suppose here that the oracle is able to answer, in a polynomial time, the following three queries:

1. the equivalence between two CP-nets (and returns a counterexample if not), 2. its preference between two outcomes in a swap, 3. another swap (o , o )V which respects some conditions (see Eq. ( 1) in Subsection 3.2).

We denote by Σ the oracle, and by NT its proper CP-net. The target CP-net NT , cannot generally be explicitly known due to e.g. cognitive overloads for a user or the size of the database. However, we suppose that the oracle is able to differentiate its proper CP-net from the learned one.

Our algorithm, contrary to the state of the art approaches, tries to take into account incoherent (contradictory) preferences. Indeed, it may happen, for a user, to have incoherent preferences (she makes some mistakes or her preferences cannot be modeled by a CP-net). In case of databases, the data can be affected by noise, i.e. contradictory preferences. Hence, the learning procedure should be robust as much as possible to such a noise. In our approach, we introduce a list of violated rules L which cannot be represented in our CP-net either because we cannot add a parent to a variable to represent the rule, or even if such a parent exists, this rule cannot hold in NL. Then, we say that two CP-nets NL and NT are equivalent if the oracle compares these two CP-nets without using the rules contained in L, i.e. EQ(NL, Σ, L).

Following previous learning algorithms, we decompose our procedure into a general learning phase, and a parent search phase. Still, our two phases are different from the ones in the state of the art.

General learning phase

In exact learning theory, we look for a perfect equivalence between the target and the learned structure. Following this perspective, we need to completely fit NL and improve as much as possible the learning accuracy. Algorithm 1 corresponds to the general learning phase, starting with an empty CP-net NL.

NL is updated by the rule r induced by the swap counterexample provided by the oracle. As in [START_REF] Boutilier | Cp-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF], two cases can occur: the inverse rule r is not present in NL, then we just have to add r to our CP-net. But if r is already present, then we must find a new parent to the variable V associated with the rule r. Since our Algorithm 1 does not always pick the real good parent (because of the presence of incoherences in the data), the parent search procedure can fail. If this happens (Line 11), we add r in the list of violated rules (i.e. a list that cannot be represented in NL). Otherwise (Line 7), we remove all the CP T (V ) and create a new one that contains r p and rp . The algorithms in [START_REF] Joshua T Guerin | Learning cpnet preferences online from user queries[END_REF][START_REF] Koriche | Learning conditional preference networks[END_REF] try to compute the complete CP-table of V and restart for each new parent variable, which leads to heavy computations. Nevertheless, we guess that in real world applications, CP-tables are not generally complete. Moreover, in case when the oracle refines its judgment, the preference in a swap can be different from a moment to the other, and an incoherence becomes coherent. Unfortunately, the opposite is also possible. However, we expect that its preferences becomes truthful as the time passes. Then it is not mandatory to compute the complete one in a greedy manner. This allows us to reduce the computational time. Besides, the missing entries are detected in our algorithm thanks to the equivalence queries.

Parent search phase

The parent search phase is the most important one in the learning procedure. This is due to the fact that several parent variables can be chosen, which may lead to bad decisions.

The procedure searchParent needs as an input the swap counterexample given by EQ and the oracle Σ. Its first step is to query the parent variable P of the swap (o, o )V (with o o ) associated with variable V . The variable P must satisfy the following conditions:

1. It should preserve the assignment p between two comparable5 outcomes. This is trivial in our case because we have a swap. 2. There should exist at least one other swap (o , o )V associated with the same variable V such that the preference on V is reversed and it contains the inverse assignment of P .

We can summarize these conditions in the following equation: let

(o, o )V and (o , o )V two swaps, with V, P ∈ V, which respect o[V ] = o [V ] = o [V ] = o [V ], and
o[P ] = o [P ] = o [P ] = o [P ]. (1)
These constraints are modeled in Line 1. Since we restrict ourselves to acyclic CP-nets, a function cycle is used to test the acyclicity of NL with the new parent variable.

We need to choose the good parent variable among all the available ones in P. Instead of choosing a random P ∈ P, we pick the variable P that minimizes the number of swaps that violate the rule induced by the current swap counterexample, i.e. let (o, o )V and (o , o )V be two swaps, with V ∈ V and P ∈ P a(V ), then:

(o[P ] = o [P ] and o[V ] = o [V ]) or (o[P ] = o [P ] and o[V ] = o [V ]). (2)
In case of equality, we randomly choose one.

Our parent search procedure is given in Algorithm 2. It is important to note that this algorithm can be parallelized using one process for each parent candidate, thanks to the independence of this search. However, this implementation is left for future work. Result: A parent variable P if there exists one, an error otherwise.

1 P ← {P ∈ V \ ({V } ∪ P a(V )) | ¬cycle(N = (V, A ∪ {(P, V )}, CP T (V))) and ∃(o , o )V ∈ Σ s.t.
Eq. ( 1) returns TRUE}; 2) returns TRUE}; 4 else return "parent not found"; Example 1. Let us now try to learn a simple complete CP-net from Figure 2 (without the swimming pool variable). We begin by asking a couple if the empty learned CP-net is equivalent to their induced one. This is obviously not the case. Consider that they then give us the following swap counterexample ((2, big), (3, big))occupancy. The algorithm finds the rule r = (2 3) which is added to NL. The next step is the equivalence query. Consider now that they answer the query by returning ((2, small), (2, big)) kitchen . Then, the rule r = (small big) is deduced, and is added to NL. The process is repeated once again. Consider once more that the couple at this stage returns the following swap counterexample ((3, big), (3, small)) kitchen which induces the rule r = (big small). Since the inverse rule r = (small big) already exists, the searchParent returns only the occupancy variable. Theses two new rules r 3 = (3 : big small) and r2 = (2 : small big) are then added in the CP-net.

2 if (P = ∅) then 3 return argmin P ∈P {#(o , o )V ∈ Σ | Eq. (
We end this subsection by giving some complexity results about these two algorithms. Proposition 1. Let Σ be an oracle. We define by s the number of swaps contained in Σ, i.e. holding in a database, or known by a user, and by n the number of variables in a CP-net. Algorithm 2 has a complexity of O(n 3 + ns).

Proof : Line 1 has to detect a cycle in O(n+n 2 ) ≈ O(n 2 ). The first n is the number of variables in the CP-net and the second n 2 corresponds to the maximum number of directed arcs in a directed graph. Finding a swap that respects the parent condition can be computed in O(s). These steps have to be repeated for each parent candidate. Thus, Line 1 has a total complexity of O(n(s + n 2 ) = O(n 3 + ns).

Line 3 has to count the number of swaps in Σ that respect a given condition, it is in O(ns). Hence, Algorithm 2 has a total complexity of O(n 3 + ns).

Proposition 2. Algorithm 1 has a complexity of O(2 p (n 4 + n 2 s + ne)) to compute NL, where p = max V ∈V {|P a(V )|}, e is the time taken by EQ to return TRUE or FALSE, and NL is an acyclic CP-net.

Proof : We know from Prop. 1 that searchParent (Line 6) has a complexity of O(n 3 +ns). We now consider the while condition at Line 3. Suppose that NT is a complete CP-net. Then, we must have complete CP-tables which imply, for p the max number of parents in NT , 2 p equivalence queries (one for each rule). Moreover, we have to remove all the rules in the CP-table when a new parent is found. In the worst case, we need p i=1 2 i = 2(2 p -1) equivalence queries to learn one CP-table, so 2n(2 p -1) equivalence queries in total. We finally have a complexity of 2n(2 p -1)(n

3 + ns + e) ∈ O(2 p (n 4 + n 2 s + ne)).
Note that s and e, which are respectively defined in Propositions 1 and 2, correspond to the same process if the oracle is a dataset. For n the number of variables, the maximum number of objects in a dataset is 2 n in the binary case. The maximum number of rules is then k ≤ 2 n . Furthermore, each of these rules is represented by at least one swap (exactly one if k = 2 n ). Hence, in the worst case, s ≤ 2 n and e ≤ 2 n . However, in real world applications, s < m 2 n (with m the number of objects in a dataset) and the worst case does not hold in most of situations.

Experimental results

In this section, we consider that the oracle Σ is a database that contains a list of swaps. To evaluate the efficiency of our algorithm, we demonstrate its usefulness on real and on simulated datasets.

Defining an accuracy measure of a learning algorithm on such a structure is not a trivial task. A CP-net can be seen as a set of rules. A workaround to define an accuracy measure is to use the number of rules induced by the preferences of Σ which are correctly represented in NL versus the total number of rules. However, even if this can be relevant in some cases, where there is just one violated rule, this measure becomes meaningless. Indeed, a violated rule cannot be represented in NL and then induces a huge number of unsatisfiable swaps. In a context of learning a relevant CP-net, we rather prefer to use the number of swaps that are in agreement with NL versus the total number of swaps in the whole dataset.

We use two different runs of our algorithm in order to smooth our results: the first one consists of the random generation phase of the target CP-nets or the datasets, and the second one consists of the learning phase of NL. We note these two runs by k × l with k the random generation phase and l the learning phase. In all the graphics in the rest of the paper, each point corresponds to a simple averaged value according to the number of runs. The standard deviation is reported as an error bar on these graphics.

We use two distinct datasets to conduct our experiments:

1. the TripAdvisor dataset [START_REF] Wang | Latent aspect rating analysis on review text data: a rating regression approach[END_REF][START_REF] Wang | Latent aspect rating analysis without aspect keyword supervision[END_REF] rescaled to obtain binary attributes (considered here as variables), 2. randomly generated dataset in order to test the scalability of our algorithm, and its robustness to incoherences.

The TripAdisor 6 dataset contains about 240, 000 hotel reviews. A hotel is represented by seven rates (between 1 and 5) plus one general rate. We use this general rate as our preference relation between the reviews. To be able to learn a binary CP-net, the rates are rescaled: 1 if the rate is strictly greater than two, and 0 otherwise. We have, after this procedure, 126 different hotel reviews that induce a target CP-net NT which potentially contains incoherences.

We also generate a random artificial dataset as follows: two random boolean vectors such that they form a swap (only one bit changes between both vectors) are generated along with a random score for each of these vectors. This score corresponds to our preference relation. In order to test Algorithm 1, we generate three sizes of random datasets with 50 objects (7 attributes), 500 objects (10 attributes), and 10000 objects (15 attributes). We set the size of vectors of each dataset by applying n = log 2 m + 1, with m the number of objects in the dataset. We suppose that such a generated synthetic dataset reflects reality in the sense that a real dataset cannot contain all the possible combinations of the attribute values and some objects may not exist, i.e. m ≤ 2 n-1 < 2 n . A preprocessing procedure transforms a set of objects into a set of swaps. We firstly test the importance of having coherent preferences for the learning phase. Except for the 50 objects dataset (probably due to the few number of objects), a gap is observed between the real hotel dataset and the 500 objects dataset in Figure 3. Of course, the agreement grows with regards to the maximum number of parents. The last test consists in relaxing the acyclic condition in order to observe the its influence. In this case, we are able to exactly fit NT , but at the price of heavy computations.

Figure 3 depicts the results of Table 1. The accuracy increases linearly w.r.t the number of parents. Once again, one can observe a gap between the accuracy of separable (p = 0) and tree-shaped CP-nets (p = 1) for all datasets, and a decreasing accuracy between p = 1 and p = 2. The accuracy continues growing when p > 2. Furthermore, one can note that the learning procedure is not stable 6 http://times.cs.uiuc.edu/ ˜wang296/Data/. for small numbers of objects (n < 500) because of the number of variables which does not allow the algorithm to correct its mistakes. Figure 4 shows the influence of the number of objects m on the accuracy for a fixed number of variables n. When m 2 n , we can easily fit the structure with an accuracy greater than 80% (for the 500 and 1000 datasets). When the dataset contains a number of objects m close to the limited size 2 n , the accuracy increases until about 60%. We can observe the same phenomenon as in Figure 3, with a negative gap between p = 1 and p = 2. It occurs for all random datasets.

At last, we focus on the time taken by Algorithm 1 to learn one CPnet from a dataset. We can see in Figure 5 that this learning task is immediate for m ≤ 1000. However, whereas we need about 20 seconds to learn a CP-net from m = 5000 and p = 14, we need more than 150 seconds to learn a CP-net from m = 10000 and p = 14. Thus, for two times more objects, we need ten times longer to com- pute it. However, the computation time increases linearly according to the number of parents: as we need to browse the whole database, the number of objects m (thus the number of swaps s that induce the rules) is a critical factor.

Conclusion

We presented in this paper a new algorithm for learning acyclic CPnets, and designed a bunch of experiments to evaluate its performances on synthetic and on real datasets. They showed that despite its exponential complexity depending on the number of objects and parents (Proposition 2), our algorithm can learn in a few seconds a CP-net on random CP-nets, random datasets, or real dataset.

The main ingredient of our approach is incoherence handling in the preferences. The robustness of our algorithm to these incoherences has been evidenced by the designed experiments. For instance, on a task for hotel rating using a TripAdvisor dataset affected by noise, our algorithm achieves good accuracy results. Future work will concern the improvement of our algorithm from different standpoints, in particular to reduce its time complexity.

A first effort will concern the implementation of a parallel version of our searchParent subroutine in order to decrease the learning time according to Proposition 1. This will allow to gain at least a n factor. This is especially important as recommender systems are applied in environments with massive datasets such as social networks.

A second effort will concern the improvement of several critical parts of our algorithm. The first one concerns the exhaustive nature of equivalence queries. Since we want a perfect fitting between NT and NL (when working with datasets) we must look over all the input data for an answer, which is very time consuming. This issue can be overcome by designing an approximate strategy, potentially with accuracy guarantees. The second critical part concerns the random nature of the counterexample returned by the equivalence queries. It may occur when the counterexample does not correspond to the real true preference rule. This leads to erroneous rules generation.

Figure 2 .

 2 Figure 2. CP-net with three variables.

Algorithm 1 : 6 P 8 A 10 L

 16810 learningCPNet(Σ, NT ) Data: An oracle Σ which induces a target CP-net NT . Result: A learned CP-net NL. 1 L = ∅; 2 NL = (V, A = ∅, CP T (V) = ∅); 3 while (¬EQ(NL, NT , L)) do 4 Let (o, o )V ∈ Σ be a swap counterexample returned by EQ and r = (u : v v ) its induced rule with U = P a(V ); 5 if (r ∈ CP T (V )) then ← searchParent((o, o )V , Σ); 7 if (P exists, with Dom(P ) = {p, p }) then ← A ∪ {(P, V )}; 9 CP T (V ) ← {r p , rp } where p = o[P ]; ← L \ {r }, ∀r ∈ L s.t. r is linked by V ; 11 else L ← L ∪ {r}; 12 else CP T (V ) ← CP T (V ) ∪ {r}; 13 return NL;

Algorithm 2 :

 2 searchParent((o, o )V , Σ) Data: A swap (o, o )V and the oracle Σ.

Figure 3 .

 3 Figure 3. Learning accuracy according to the number of parent p per variable. Datasets are randomly generated except for the real 126 hotels file. Results are averaged on 5 × 10 runs and error bars correspond to the standard deviation of the observed values.

Figure 4 .

 4 Figure 4. Learning accuracy when the number of variables is fixed (n = 15). We increase the number of objects in the random datasets. Results are averaged on 2 × 5 runs and error bars correspond to the standard deviation of the observed values.

Figure 5 .

 5 Figure 5. Learning time when the number of variables is fixed (n = 15). We increase the number of objects in the datasets. Results correspond to one learning execution averaged on 2 × 5 runs and error bars correspond to the standard deviation of the observed values.

  {fabien.labernia,brice.mayag,florian.yger,jamal.atif}@lamsade.dauphine.fr 2 An object can be a hotel having as a set of attributes: the number of rooms, the price, etc.

								preferences User's	Induce	Ideal preference structure
								Feedback
								Data	Approximates
								Query	CP-net
								Constructs
								Recommender system
	1	Université	Paris-Dauphine,	PSL	Research	University,
		CNRS,	UMR	7243,	LAMSADE,	75016	PARIS,	email:

Extract

Figure

1

. General scheme of a learning procedure for CP-nets.

Table 1 .

 1 Accuracy of Algorithm 1. Results are averaged on 10 × 10 runs.

	Accuracy(%)	Agreement Disagreement
		p = 1
	real hotels (126)	0.73	0.27
	random hotels (50)	0.72	0.28
	random hotels (500)	0.57	0.43
	random hotels (10000)	0.52	0.48
		p = 5
	real hotels (126)	0.82	0.18
	random hotels (50)	0.82	0.18
	random hotels (500)	0.59	0.41
	random hotels (10000)	0.51	0.49
		p = ∞
	real hotels (126)	0.83	0.17
	random hotels (50)	0.79	0.21
	random hotels (500)	0.69	0.31
	random hotels (10000)	0.66	0.34
		relaxing acyclic condition
	real hotels (126)	1.00	0.00
	random hotels (50)	1.00	0.00
	random hotels (500)	1.00	0.00
	random hotels (10000)	too long to compute

We say that two CP-nets N and N are equivalent, denoted by N ≡ N iff they induce exactly the same preferences.

We consider a variable V as confident if enough swap that induced rules of V are found.

Two outcomes o and o are comparable if either o o or o o.