Learning Conditional Preference Networks: An Approach Based on the Minimum Description Length Principle

1 Introduction

Online shopping services, like video-on-demand streaming services and product configurators for computers, cars, or kitchens, rely on recommendation and customization of the user experience to boost sales [Zhang, 2014]. Recommendations are essential in large, combinatorial product spaces, where the number of alternatives can lead to over-choice confusion [Huffman and Kahn, 1998]. In such a case, a user is overwhelmed by the possibilities and cannot choose. A common tool in configurators is optimal completion, where the configurator automatically completes a partially configured product by maximizing the product's utility for the user. Recommendation, and optimal completion, in particular, are typically based on a modeling of user preferences. However, except when the number of attributes is very small, it is intractable to represent a linear order over the space of all possible alternatives in extension. Several compact, graphical representations of preferences have been studied in the literature. Combinatorial preferences can be modeled with numerical models, such as GAI-nets [Gonzales and Perny, 2004] and ensemble ranking function [Freund et al., 2003], or by ordinal graphical models, such as lexicographic preferences trees (LP-trees) [Fraser, 1993] and conditional preferences networks (CP-nets) [Boutilier et al., 2004].

CP-nets, in particular, are well-suited for interactive configuration: they can represent (albeit partially) any preference relation, and the optimal completion query can be answered in polynomial time with acyclic CP-nets with the Forward Sweep algorithm [Boutilier et al., 2004].

Learning CP-nets has often been studied in settings where the input data has the form of pairwise comparisons between alternatives [Dimopoulos et al., 2009; Lang and Mengin, 2009; Chevaleyre et al., 2011; Allen et al., 2017; Alanazi et al., 2016; Labernia et al., 2017; Liu and Liu, 2019; Alanazi et al., 2020]. However, this type of preference data is not commonly stored. It can be elicited [Koriche and Zanuttini, 2010] but this puts an additional burden on the decision maker. In this article, we investigate a newmethod for learning CP-nets from sales history, a kind of data readily available in many e-commerce applications. The approach is based on the minimum description length (MDL) principle, which has been successfully applied in the unsupervised learning of many classes of models, such as Bayesian networks [Suzuki, 1993; Lam and Bacchus, 1994], causal networks [Mian et al., 2021] and formal grammars [Garofalakis et al., 2003].

More precisely, the contributions of this article are:

• the sample complexity of unsupervised CP-nets learning;
• the NP-completeness of unsupervised CP-nets learning;
• an unsupervised CP-nets learning algorithm;
• an experimental evaluation on a real-world recommendation task.

2 RelatedWork

We review some works on learning preferences from a list of observed optimal alternatives, not pairwise comparisons.

Bayesian networks [Pearl, 1985; Pearl, 2009] are graphical probabilistic models that can represent any probability distribution. Because it associates a numerical value to every alternative (its probability), they can be used to order these alternatives. Syntactically, a Bayesian network is a directed acyclic graph where each node is associated to a conditional probability table, making them syntactically similar to CPnets. Learning the probability tables when the structure is known amounts to some simple frequencies computation, but learning the optimal, graphical structure of a Bayesian network is an NP-hard problem. Numerous methods for learning Bayesian networks have been proposed (see, e.g., a recent survey by [Kitson et al., 2023]). Learning methods typically use local conditional independence tests to decide the presence or absence of some arrows in the graph, and/or some global scoring function to explore the space of possible structures. In particular, the Bayesian Information Criterion (BIC) is at the core of approaches based on the MDL principle. Note that the computation of the optimal, most probable completion of a partial instantiation is an NP-complete task for Bayesian networks [Kwisthout, 2011]. Our experiments in a configuration settings, described in Section 7, show that the recommendation time is significantly lower when using a CPnet than with a Bayesian network.

[Bigot et al., 2014] and [Khoshkangini et al., 2018] propose methods to transform a learnt Bayesian network into a CP-net: local probability tables are converted to local preference orders, with most probable value being preferred. However, the probabilistic dependencies in a Bayesian network are not directed, whereas preferential dependencies in a CPnet are directed: [Bigot et al., 2014] propose to identify the correct direction of the dependencies in a CP-net in an active learning settings, using pairwise comparison queries, and [Khoshkangini et al., 2018] assume that the structure is partially known at the start.

[Fargier et al., 2018] propose a greedy algorithm to learn preferences represented by lexicographic preference trees from sales history. The aim is to find a model that attributes low ranks to alternatives that appear often in the history. The preference tree is computed in a top-down fashion, based on statistics calculated from the sales history on the attributes and their values. They prove that the algorithm computes the optimal structure when restricted to linear structures (lexicographic preference lists). In [Fargier et al., 2022], the authors prove that the sample complexity for this preference learning method is logarithmic in the number of attributes. However, experiments described by [Fargier et al., 2020] indicate that lexicographic preference models may be too restrictive to represent well preferences from a group of agents (even if they are known to be a good model to represent preferences of one agent). Besides, their approach is based on the rank of an alternative and, therefore, cannot be applied to learn languages that represent partial orders, such as CP-nets.

3 Background

Combinatorial Domain. We consider a combinatorial domain over a finite set X of discrete attributes that characterise the possible alternatives. Each attribute X P X has a finite set of possible values X. X denotes the Cartesian product of the domains of the attributes in X, its elements are called alternatives. We often use the symbols o, o1 , o1, o2, . . . to denote alternatives. In the following, n is the number of attributes in X, and d is a bound on the size of the domains of the attributes: for every X P X , 2 ď |X| ď d.

For a subset U of X, we will denote by U the Cartesian product of the domains of the attributes in U, every u P U is an instantiation of U, or partial instantiation (of X). If v is an instantiation of some V Ď X, vrUs denotes the restriction of v to the attributes in V XU.

Preference Relations. In this paper, we consider that a preference relations is a linear order over X, i.e., a total, transitive, irreflexive binary relation over X, often denoted with curly symbol ą. For alternatives o, o1 P X, o ą o1 indicates that o is strictly preferred to o1 . Given a partial instantiation u, consider the set of alternatives that extend u: this set is finite and the projection of linear order ą over this set is a linear order too, so it has a unique "most preferred" element. We denote this element by optpu, ąq.

CP-nets. Given the exponential size of X, it is not tractable to represent preference relations in extension. So, we use preferences models that rely on the assumption that the preference relations of interest exhibit some structure. We focus on one family of graphical models: Conditional Preference Networks (CP-nets). CP-nets have been introduced in [Boutilier et al., 2004] as a tool to make explicit a particular kind of structure, called preferential (in)dependence.

Figure 1a depicts a CP-net ϕ0. More generally, a CP-net is a triple ϕ " pX , P a, CP T q, where:

• Pa associates to every attribute X P X , a subset PapXq of XztXu. Thus Pa defines a directed graph over X, where there is an edge pX, Y q if and only if X P PapY q. PapY q is the set of parents of Y . In this article, we only consider acyclic CP-nets.
• CPT is a set of conditional preference tables. One table CPTpXq for every attribute X: CPTpXq contains, for every instantiation u of PapXq, a rule u :ą, where ą is a linear order over X.

Let us call swap any pair of alternatives that have identical values for every attribute except one. A CP-net ϕ orders every swap to, o1 u as follows: let X be the only attribute such that orXs ‰ o1 rXs, let u " orPapXqs " o1 rPapXqs, let u :ą be the corresponding rule in CPTpXq, then po, o1 q is a worsening swap (w.r.t. ϕ) if and only if orXs ą o1 rXs. The transitive closure of all the worsening swaps sanctioned by ϕ is, by definition, transitive, and we denote it by ąϕ. It is not necessarily irreflexive, and not complete in general. Acyclic CP-nets are guaranteed to be consistent, i.e., there always exists a total order that extends the order defined by a CP-net.

Example 1. Figure 1a depicts a CP-net ϕ0 over a combinatorial domain with three boolean attributes A, B and C, with respective domains ta, ¯au, tb, ¯bu and tc, ¯ cu: PapAq " tu and CPTpAq " ta ą ¯au, PapBq " tA,Cu and CPTpBq " ta _ ¯ c : b ą ¯b, ¯ac : ¯b ą bu, where a _ ¯ c : b ą ¯b indicates that for the three instantiations ac, a¯ c, ¯a¯ c, value b is preferred to ¯b. Figure 1b depicts ąϕ0 : edges o o1 represent the worsening swaps sanctioned by ϕ0. Some of them are redundant since implied, by transitivity of ąϕ0 : for instance the fact that abc ąϕ0 ¯abc is implied by the worsening swaps pabc, ab¯ cq, pab¯ c, ¯ab¯ cq, p¯ab¯ c, ¯abcq.

[Boutilier et al., 2004] proved that, when a CP-net ϕ is acyclic, given a partial instantiation u, optpu,ąϕq exists and is unique, and it can be computed in time linear in the number of attributes with the so-called Forward Sweep procedure.

Although CP-nets cannot in general represent a total preference relation, they capture enough information to answer the opt query: more precisely, any total preference relation ą induces a CP-net ϕą such that optpu,ąq " optpu,ąϕą q when ϕą is acyclic [Gimenez and Mengin, 2023].

Minimal Description Length. In Machine Learning, the Minimal Description Length (MDL) principle is akin to Occam's razor principle, which states that the simplest hypothesis should be privileged. MDL enforces this idea through compression: given some data D and a class of possible models that may explain D, one should choose the model ϕ that enables the lossless compression of D with minimum size [Gr¨unwald, 2000]. Formally, if LpD|ϕq denotes the length of the representation of D knowing ϕ, one can define the minimum description length for D given a class of models C as minϕPC `Lpϕq ` LpD|ϕq˘.

4 Applying the MDL Principle to CP-Nets Learning

We now recall the learning problem that is the focus of this paper, and the MDL-based approach that is proposed.

Following [Fargier et al., 2018], the input of the learning process is a sales history, i.e. a multiset D Ď X. Its elements are alternatives corresponding to products that may have been, for instance, configured by users of some configurator and bought. Each user has a preference relation ˘ą among products, and is free to configure the products according to her preference. However, for some reasons like the influence of advertisements, special offers or unavailability, she may end up with a product which is not her most preferred one. Yet, the higher an outcome is ranked in the user's preference, the greater the probability that she ends up with it. Given this input, we want to compute a CP-net that represents a preference relations that explains this dataset D, and can be used to guide future users throughout the interaction with the configurator, towards an alternative that best suits their needs.

[Gimenez and Mengin, 2023] propose, given an acyclic CP-net ϕ, a lossless compression of such a dataset D as follows: for alternative o, codepo, ϕq is the smallest partial instantiation u such that optpu,ąϕq " o. They prove u to be uniquely defined, and it can be computed in polynomial time. For instance, for the CP-net ϕ0 of example 1, codepa¯b¯ c, ϕ0q " ¯b: Figure 1b shows that a¯b¯ c is the optimal alternative when B " ¯b. Codes of preferred alternatives are generally shorter than codes of less preferred alternatives.

Using this function code to compress D given ϕ, we have:

ÿ

where, for each outcome o P D, the terms encode, in order: the length of the minimal code of o, the set of variables that are assigned in this code, and the value for each attribute, and where LN is the length of the Rissanen universal integer encoding [Rissanen, 1983]. This encoding therefore favors models that associate common alternatives with short codes, so such alternatives are among the most preferred.

Moreover, the size of the representation of a given CP-net ϕ " pX, Pa,CPTq is :

where, slightly abusing notation, |N| denotes the domain size of the attribute labellingN. These terms encode, in order: the total number of nodes, and for each node, the number of its parents, its set of parents and the optimal value for each value of its parents.

Therefore, the learning problem that we study in the remainder of the paper is the following one: given a set of attributes X , and a sales history D, find the CP-net ϕ that minimizes Lpϕq `LpD|ϕq as defined above. In the next section, we prove two complexity results about this problem. Section 6 proposes a simple local search algorithm to explore the set of CP-nets guided by this MDL-inspired cost function, and section 7 describe some experiments to compare this new approach to previous approaches to learning preferences in this settings.

5 Theoretical Results

In this section, we propose a formalization of the MDL score that is more suited for theoretical analysis, and we present two new results on the CP-nets unsupervised learning: an upper bound on its sample complexity and the NP-completeness.

5.1 NormalizedMean Code Length

Cost equations Eq. (2) and (1) are complex because, according to the MDL principle, the compressed data must contain all the information required for a lossless decompression, making these equations unsuited for theoretical analysis. We propose to study instead a surrogate loss function that defines the cost of an alternative as its code length.

While Eq. (2) and (1) are not linear in the code length, we argue that it is, in practice, a reasonable approximation. Lpϕq is a regularization parameter to avoid learning too complex models. In fact, the terms that most contribute to the MDL cost are řXPcodepo,ϕq log2p|X| ´ 1q and log2 ` n | codepo,ϕq|˘. When all variables have the same cardinality, the first term is proportional to codepo, ϕq. Besides, most alternatives have a short code (because this is what the model is optimized for), so log2 ` n | codepo,ϕq|˘ « log2 n| codepo,ϕq| | codepo,ϕq|! « | codepo, ϕq|plog2 n ´ log2 | codepo, ϕq|q, which is slightly sublinear in codepo, ϕq.

By denoting p the probability distribution of the alternatives, we therefore propose to use the normalized mean code length (NMCL for short) as the loss of ą:

This metric is between 0 and 1. Algorithm 4 proposed in [Gimenez and Mengin, 2023] shows that, for acyclic CP-nets:

where Pref pN, orPapNqsq is the preferred value in the rule associated to orPapNqs in the CPT of N. Remark that we can further simplify the expression of NMCLp by introducing perrpN, vq, the probability that a randomly drawn alternative is instantiated to v for the parents of N and does not include the most preferred value of N: perrpN, vq " ppv ^␣Pref pN, vqq. Then:

5.2 Upper Bound on the Sample Complexity

Our analysis of the sample complexity is done within the PAC learning theory proposed by Valiant [Valiant, 1984], where we are interested in the number Npδ, ϵq such that, if Npδ, ϵq examples are available at training, then there is a high probability (bigger than 1´δ) that the distance between the CP-net that minimizes the empirical normalized mean code length and the target unknown CP-net is small (lower than ϵ). In our case, this distance is the difference of their normalized mean code length. In this section, we show that the sample complexity is polynomial for fixed bounds on the size of the domains of the attributes and the number of parents.

Proposition 1. For the family of CP-nets with n nodes and whose nodes have at most k parents, Npδ, ϵq " O` d2k ϵ2 pln 1δ ` kpln d ` lnpn ` 1qqq˘

Proof. Denote CP-netk the set of CP-nets whose nodes have at most k parents. Denote ˘ ϕ a CP-net in CP-netk that represents the preference relation ˘ą. p is a probability distribution that is non-increasing w.r.t. ˘ą, i.e. o ˘ą o1 ñ ppoq ě ppo1 q. Let us denote ϕ˚ the CP-net in CP-netk that minimizes the empirical normalized mean code length with respect to some sample S. Then:

because EpS r| codep¨, ϕ˚ q|s ´ EpS r| codep¨, ˘ ϕq|s ď 0 by definition of ϕ˚ . Now, for any ϕ P CP-netk :

where d is a bound on the domain size of the attributes, and M is an upper bound on |perrpN, vq´pS,errpN, vq| for every N P nodespϕq, every v P ParpNq.

Thus, if 1n |Epr| codep¨, ϕq|s ´EpS r| codep¨, ϕq|s| ě ϵ, there must be some V Ď X and v P V such that |perrpN, vq ´ pS,errpN, vq| ě ϵ{p2dk q, which implies that:

For every V Ď X and every v P V , pSpvq is an estimate, from sample S, of the ground probability ppvq of drawing an alternative o such that orV s " v. Hoeffding's inequality states that for every α ą 0:

For every i P t1, . . . , ku, there are `ni ˘ ways of choosing a subset V of X of cardinality i, then |V | ď di . Therefore:

Therefore, in order to have Prplosspϕ˚ , ˘ ϕq ď ϵq ě 1 ´ δ, it is sufficient to have 1´2dk p1`nqk expp´|S|ϵ2 {p4d2k qq ě 1´δ, which is equivalent to |S| ě 2d2k ϵ2 pln 1δ `kplnd`lnpn` 1qq ´ ln 2q.

This low sample complexity shows that CP-nets, like other ordinal models, require a low number of examples to be learnt accurately. This is a very positive result, since CP-nets are still very expressive in the preferences they can express.

5.3 CP-net Unsupervised Learning is NP-complete

While CP-nets require few examples to be learned accurately, they rely on a graph, a data structure for which many problems are NP-complete. In fact, the following proposition shows that learning a CP-net that minimizes the empirical normalized mean code length is indeed NP-complete.

Proposition 2. Let D be a dataset. The problem of finding the minimal acyclic CP-net that minimizes the empirical normalized mean code length over D is NP-complete.

Proof sketch. The full proof is available online in our repository.

We reduce the minimum feedback arc set (FAS) problem [Karp, 2010], to this problem. Let G " pV,Eq be an instance of FAS, whose n nodes are denoted V1, V2, . . . , Vn. The problem is to find a minimal set of edges E1 such that G " pV, EzE1 q is acyclic. To that end, we construct a dataset such that the CP-net that minimizes the empirical normalized mean code length allows us to solve FAS easily. The combinatorial space of the dataset is X " V Y tVi,j | i Ñ j P Eu. Each attribute is binary and its domain is tJ, Ku. We initialize the dataset D with 3|E|`1 alternatives that all have value K for every attribute. Then, for each edge Vi Ñ Vj in E, we add three alternatives to D: o1 with o1rVis " o1rVi,js " o1rVj s " J, and o1rXs " K for every other attribute, o2 with o2rVis " o2rVjs " J, and o2rXs " K for every other attribute, and o3, with o3rVi,js " o3rVjs " J, and o3rXs " K for every other attribute X. So, for every alternative o P D, orVjs " orVis _ orVi,js. In the following, we will refer to tpVi, Vi,j , Vjq | Vi Ñ Vj P Eu as "triplets".

The optimal and minimal CP-net ϕ minimizes the empirical score NMCLpD pąq " 1n řN řvPPapNq pD,errpN, vq.

Because ϕ minimizes the empirical normalized mean code length, we show that the subgraph for each triplet can only be of two sorts: structure A or B, as depicted below:

By construction, Vi,j cannot appear in multiple triplets. Therefore, structure B cannot introduce any cycle in the CPnet, while it can be the case for structure A. Besides, structure A has a lower cost than structure B. Therefore the optimal acyclic CP-net has a maximum number of occurrences of structure A, and will use structure B in all other cases.

Given an optimal CP-net, we can provide a solution to the initial FAS problem as follows: for every triplet pVi, Vi,j , Vjq, if Vi is not the parent of Vj, then Vi Ñ Vj is added to the feedback arc set.

Algorithm 1: Hill climbing search for CP-net learning

Data: a dataset D, an initial CP-net ϕ1 Result: a CP-net ϕ

• 1 score ÐLpϕ1 q `LpD|ϕ1 q; previous scoreÐ`8
• 2 while score ă previous score do
• 3 ϕÐϕ1
• 4 neighbors Ð transformationspϕq
• 5 remove non-acyclic graphs from neighbors
• 6 fit CPTs of neighbors fromD
• 7 ϕ1 Ð argminϕ2 Pneighbors Lpϕ2 q `LpD|ϕ2 q
• 8 previous score Ð score
• 9 score Ð Lpϕ1 q ` LpD|ϕ1 q

• 10 return ϕ

6 CP-net Learning Algorithm

The learning algorithm we propose has two parts: the structure learning and the conditional preference tables fitting.

6.1 Structure Learning with Hill Climbing

Since CP-nets learning is NP-complete, we propose an approximate learning algorithm, using a hill-climbing approach based on a series of greedy improvements of the score by local modifications of the model. The approach is described with Algorithm 1. This algorithm takes as parameter an initial CP-net ϕ1 . It can be, for example, a separable CP-net, i.e., a CP-net whose underlying directed acyclic graph has no edge. At each iteration of the "while" loop, a family of neighbors of the current best model ϕ1 is generated at line 4. Specifically, we use the classical transformations used for learning Bayesian networks: 1) edge addition, 2) edge deletion, and 3) edge inversion. Non-acyclic neighbors are discarded at line 5. For every neighbor, conditional preference tables are computed at line 6 to best fit the data (cf. section 6.2). The MDL scores of these new models are computed at line 7, and one that minimizes this score is saved in ϕ1 . In our implementation, we also added a tabu list.

6.2 Conditional Preference Tables Fitting

At line 6 of Algorithm 1, for every acyclic neighbor ϕ2 of ϕ, the conditional preference tables associated to nodes N such that PaϕpNq ‰ Paϕ2pNq must be updated. Since our local search aims at minimizing the MDL cost of D, we look for conditional preference tables that minimize LpD | ϕ2 q. Since codepo, ϕ2 q tends to be longer for alternatives that are less preferred in ąϕ2, CPTpNq should favor most common alternatives in D so their codes are short. In our implementation, for a fixed u P PapNq, we order values in X in increasing order of their number of occurrences associated to u: x ąX,u x1 if pDpxuq ě pDpx1uq (ties are broken arbitrarily). This heuristic matches the one used by [Fargier et al., 2018] to learn the conditional preference tables of LP-trees.

7 Experiments

We assess CP-net learning with a practical application to recommendation systems by applying an experimental protocol similar to that of [Fargier et al., 2016], described in section 7.1. The datasets used in our experiments are three genuine car sales histories provided by the car manufacturer Renault: "small" (48 attributes, 27,088 vectors), "medium" (44 attributes, 14,786 vectors) and "big" (87 attributes, 17,715 vectors). Each dataset is a list of cars of a particular model, sold by Renault during a past 12 months period. There is no information about the buyers.

We report below on the recommendation accuracy and time obtained in various experimental settings. These experiments seek to answer the following questions:

• Is recommendation accuracy improved with clustering? And with which model selection heurisitcs?
• How does our method compare with the k-LP-tree approach proposed by [Fargier et al., 2018]? And with Bayesian networks?
• What recommendation methods are compatible with online applications?
• Is converting a Bayesian network to a CP-net an effective learning tool?

Source code, models and datasets are available online 1 .

7.1 Experimental Protocol

Each dataset is split into a training set (80%) and a test set (20%). To assess the learnt models, we simulate an online configuration just as [Fargier et al., 2018]: for each vector o in the test set, we draw uniformly an order over the attributes. One attribute V at a time, the model provides a recommended value r for V given the current partial instantiation u. The value r is then compared to orV s and u is updated with orV s. The recommendation is deemed accurate if r " orV s. We draw 100 orders per vector to reduce the variance.

7.2 Clustering

Because an individual does not usually often buy a new car, we cannot learn the preferences of a single individual with these datasets, but we can learn about general preferences of a set of buyers. However, buyers can have wildly differing preferences, which can hardly be captured with a single preference model. [Fargier et al., 2018] show that an effective strategy is to split each dataset in a fixed number of clusters: each cluster contains similar cars, and it can be expected the buyers of such cars have similar preferences, so that it is reasonable to learn a unique CP-net for each cluster. Besides, acyclic CP-nets have a limited expressivity: there exist orders that can only be represented by cyclic CP-nets, and clustering can alleviate this reduced expressiveness. Thus, in the experiments, we started by clustering the dataset with the k-means algorithm using the Hamming distance and then applied the learning algorithms on each cluster. We use k " 3, as suggested by [Fargier et al., 2018] for these datasets.

At test time, to compute the recommended value optpuq, [Fargier et al., 2018] use the model corresponding to the cluster whose centroid is closest (according to the Hamming distance) to u. Since this approach was very effective in their experimental settings, we use it in our experiments too. We also compare it to a new heuristic, called "Shortest code", for selecting the model for preferential optimization: instead of checking the Hamming distance between u and the clusters centroids, the new heuristic selects the model ϕ that minimises | codepoptpu, ϕqq|. In case of a tie, the heuristic selects the model associated to the largest cluster.

1 https://github.com/PFGimenez/cp-nets-learning-ijcai24

Table 1 shows the accuracy of recommendations by CPnets with clustering with three model selection heuristics. In this experiment, the clusters and the models are fixed, so only the model selection heuristics impact the results. Choosing a random model yields poor results, motivating the need for a more sophisticated method. The "Shortest code" heuristic yields generally the best accuracy, although the difference with "Closest centroid" is low. Since "Shortest code" has better recommendation accuracy and has interesting properties, we only use this heuristic in the experiments described below.

7.3 Recommendation Accuracy and Time

To assess the recommendation accuracy and time, we compare the following models:

• the "Oracle" (proposed in [Fargier et al., 2016]), which gives an upper bound on the recommendation accuracy;
• Bayesian networks, used with the exact inference algorithm "variable elimination";
• our implementation of k-LP-tree learning (with k " 3 and τ " 20), as well as a version with 3 clusters;
• CP-nets learnt with our MDL approach (Algo. 1), as well as a version with 3 clusters.

Recommendation accuracy is presented in Fig. 2a, 2b and 2c. As expected, the "oracle" (in black) always has the highest accuracy since it is an upper bound. The Bayesian network (in cyan) always has the second highest accuracy and is close to this upper bound on the "small" and "medium" datasets. However, on the "big" dataset, recommendations with this model did not finish within our 72-hour timeout. The two models using clusters (in red and green) always outperform their base models. Among these models, the clustered CP-nets have the highest accuracy. Finally, CP-nets outperform LP-trees. This can be most notably explained by the strong assumption, with LP-trees, that the target order is lexicographic. This hypothesis is not necessary for CP-net learning. Note that for higher numbers of assigned attributes, even non-clustered CP-nets generally have higher accuracy than clustered LP-trees.

Recommendation time are presented in Fig. 3a, 3b and 3c. Bayesian networks are the slowest model by up to two orders of magnitude. Indeed, the MAP query used for recommendation is NP-hard, while it is polytime for LP-trees and CP-nets. In fact, this complexity can explain why it did not finish on the "big" dataset. We suppose this is mostly due to the Python library we used, which only proposes the "variable elimination" algorithm, even though more effective inference algorithms exist [Pourret et al., 2008]. The recommendation times for CP-nets and LP-trees are similar, even though CPnets are generally faster. The use of clusters makes the recommendation longer. However, even for the biggest dataset, the recommendation time is always within 3 ms, making it usable on terminals with limited computational power, like smartphones or embedded systems. Besides, we expect implementations in a compiled language (like C or Rust) to be one or two orders of magnitude faster.

7.4 Learning CP-nets FromBayesian Network

[Khoshkangini et al., 2018] propose to learn CP-nets by learning a Bayesian network and converting it into a CP-net. We now compare this approach with our method. Besides, we propose a hybrid approach, where a Bayesian network is used to initialize a CP-net that is then optimized with our MDL-score guided hill climbing learning method. We use the Python implementation pgmpy to learn the Bayesian network. The BN learning algorithm is hill climbing, with the BIC score and a K2 prior. Table 2 contains the recommendation accuracy of CP-nets learned using these three strategies. Remark the small difference in accuracy, indicating that the method of [Khoshkangini et al., 2018] is indeed effective, even though there is no apparent connection between NMCL (cf. Eq. (4)) and log-likelihood-based scores. Converting a Bayesian network into a CP-net and then optimizing it with our hill climbing method seems the most effective method.

8 Conclusion and Perspectives

This paper gives the first theoretical analysis of unsupervised learning of CP-nets. It introduces the NMCL metric and shows that the sample complexity is polynomial and that learning the optimal CP-nets is NP-complete. Finally, we demonstrated the usefulness of this approach by comparing it with various state-of-the-art methods on a real-world recommendation task. More generally, the NMCL can be used to learn any model with an efficient preferential optimization algorithm, so this approach is not limited to CP-nets.

In future works, we plan to study the connection between Bayesian networks and CP-nets to support theoretically the method of transforming Bayesian networks into CP-nets. We conjecture that the difference of recommendation accuracy between Bayesian networks and CP-nets is due to the limited expressivity of acyclic CP-nets, and so we plan to study the learning of (subclasses of) cyclic CP-nets.

Acknowledgments

Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https: //www.grid5000.fr). This work was also supported by the AI Interdisciplinary Institute ANITI, funded by the French "Investing for the Future - PIA3" program under grant agreement ANR-19-PI3A-0004.