Nahla Ben Amor
email: nahla.benamor@gmx.fr

Zeineb El Khalfi
email: zeineb.khalfi@gmail.com

Helene Fargier
email: fargier@irit.fr

Regis Sabbadin
email: rsabbadin@toulouse.inra.fr

Lexicographic Refinements in Possibilistic Decision Trees

Possibilistic decision theory has been proposed twenty years ago and has had several extensions since then. Because of the lack of decision power of possibilistic decision theory, several refinements have then been proposed. Unfortunately, these refinements do not allow to circumvent the difficulty when the decision problem is sequential. In this article, we propose to extend lexicographic refinements to possibilistic decision trees. We show, in particular, that they still benefit from an Expected Utility (EU) grounding. We also provide qualitative dynamic programming algorithms to compute lexicographic optimal strategies. The paper is completed with an experimental study that shows the feasibility and the interest of the approach.

Introduction

For many years, there has been an interest in the Artificial Intelligence community towards the foundations and computational methods of decision making under uncertainty (see e.g. [START_REF] Bauters | Anytime algorithms for solving possibilistic MDPs and hybrid MDPs[END_REF][START_REF] Weng | Axiomatic foundations for a class of generalized expected utility: Algebraic expected utility[END_REF][START_REF] Chu | Great expectations. part I: on the customizability of generalized expected utility[END_REF][START_REF] Bonet | Arguing for decisions: A qualitative model of decision making[END_REF][START_REF] Daniel | Generalized qualitative probability: Savage revisited[END_REF]). The usual paradigm of decision under uncertainty is based on the Expected Utility (EU) model [START_REF] Von | Theory of games and economic behavior[END_REF][START_REF] Savage | The Foundations of Statistics[END_REF]. Its extensions to sequential decision making are Decision Trees (DT) [START_REF] Raiffa | Decision Analysis: Introductory Lectures on Choices under Uncertainty[END_REF] and Markov Decision Processes (MDP) [START_REF] Cassandra | Acting optimally in partially observable stochastic domains[END_REF][START_REF] Puterman | Markov Decision Processes[END_REF], where the uncertain effects of actions are represented by probability distributions.

When information about uncertainty cannot be quantified in a probabilistic way, possibilistic decision theory is a natural field to consider [START_REF] Giang | Two axiomatic approaches to decision making using possibility theory[END_REF][START_REF] Weng | Qualitative decision making under possibilistic uncertainty: Toward more discriminating criteria[END_REF][START_REF] Dubois | Decision-theoretic foundations of qualitative possibility theory[END_REF][START_REF] Godo | On the possibilistic-based decision model: Characterization of preference relations under partial inconsistency[END_REF][START_REF] Dubois | Making decision in a qualitative setting: from decision under uncertainty to case-based decision[END_REF][START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF][START_REF] Godo | On the possibilistic-based decision model: Characterization of preference relations under partial inconsistency[END_REF]. Qualitative decision theory is relevant, among other fields, for applications to planning under uncertainty, where a suitable strategy (i.e. a set of conditional or unconditional decisions) is to be found, starting from a qualitative description of the initial world, of the available decisions, of their (perhaps uncertain) effects and of the goal to reach (see [START_REF] Bauters | Anytime algorithms for solving possibilistic MDPs and hybrid MDPs[END_REF][START_REF] Ben Amor | Possibilistic sequential decision making[END_REF][START_REF] Drougard | Structured possibilistic planning using decision diagrams[END_REF][START_REF] Drougard | Qualitative possibilistic mixed-observable MDPs[END_REF][START_REF] Régis | Possibilistic Markov decision processes[END_REF][START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF]).

Even though appealing for its ability to handle qualitative problems, possibilisitic decision theory suffers from an important drawback. Acts (and strategies in sequential problems) are compared through min and max operators, which leads to a drowning effect: plausible enough bad or good consequences may blur the comparison between acts that would otherwise be clearly differentiable.

In order to overcome the drowning effect, refinements of possibilistic decision criteria have been proposed in the non-sequential case [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF][START_REF] Weng | Qualitative decision making under possibilistic uncertainty: Toward more discriminating criteria[END_REF]. Some refinements have the very interesting property to remain qualitative while satisfying the properties of EU. But these refinements do not extend to sequential decision under uncertainty (in the context of the present work, to decision trees) where the drowning effect is also due to the reduction of compound possibilistic strategies into simple ones [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF].

The present paper proposes lexicographic refinements that compare full strategies (and not simply their reductions) and provides a dynamic programming algorithm to compute a lexicographic optimal strategy. It is a technical challenge to establish results of equivalence between lexicographic refinements of utilities of strategies in possibilistic decision trees and EU-based criteria. We prove such results, which opens the way to define dynamic programming solutions or even reinforcement learning algorithms for possibilistic MDPs [START_REF] Sutton | Reinforcement Learning:An Introduction[END_REF][START_REF] Sutton | Learning to predict by the methods of temporal differences[END_REF], which would not suffer from the drowning effect.

The paper is structured as follows ; the next Section recalls some results about the comparison of strategies in possibilistic decision trees. In Section 3, we define lexicographic orderings that refine the possibilistic criteria. Section 4 then proposes a dynamic programming algorithm for the computation of lexi-optimal strategies. Section 5 shows that the lexicographic criteria can be represented by infinitesimal expected utilities. The last Section reports experiments highlighting the feasibility and interest of the approach5 .

Possibilistic decision trees

Decision trees provide an explicit modeling of sequential decision problems by representing, simply, all possible scenarios. The graphical component of a decision tree is a labelled graph DT = (N , E). N = ND ∪ NC ∪ NU contains three kinds of nodes (see Figure 1):

• ND is the set of decision nodes (represented by squares); • NC is the set of chance nodes (represented by circles); • NU is the set of leaves, also called utility nodes.

For any node N , Out(N ) denotes its outgoing edges, Succ(N ) the set of its children nodes and Succ(N, e) the child of N that is reached by edge e ∈ Out(N ). This tree represents a sequential decision problem as follows:

• Leaf nodes correspond to states of the world in which a utility is obtained (for the sake of simplicity we assume that utilities are attached to leaves only); the utility of a leaf node Li ∈ NU is denoted u(Li). • Decision nodes correspond to states of the world in which a decision is to be made: Di ∈ ND represents a decision variable Yi the domain of which corresponds to the labels a of the edges starting from Di. These edges lead to chance nodes, i.e. Succ(Di) ⊆ NC . • A state variable Xj is assigned to each chance node Cj ∈ NC , the domain of which corresponds to the labels x of the edges starting from that node. Each edge starting from a chance node Cj represents an event Xj = x. For any Cj ∈ NC , Succ(Cj) ⊆ NU ∪ND i.e. after the execution of a decision, either a leaf node or a decision node is reached.

Start(DT ) denotes the first decision nodes of the tree (it is a singleton containing the root of the tree if it is a decision node, or its successors if the root is a chance node). For the sake of simplicity, we suppose that all the paths from the root to a leaf in the tree have the same length: h, the horizon of the decision tree, is the number of decision nodes along these paths. Given a node N of DT , we shall also consider the subproblem DT N defined by the tree rooted in N .

The joint knowledge on the state variables is not given in extenso, but through the labeling of the edges issued from chance nodes. In a possibilistic context the uncertainty pertaining to the possible outcomes of each Xj is represented by a possibility distribution: each edge starting from Cj, representing an event Xj = x, is endowed with a number πj(x), the possibility π(Xj = x|past(Cj)) 6 . A possibilistic ordered scale, L = {α0 = 0L < α1 < . . . < α l = 1L}, is used to evaluate the utilities and possibilities.

Solving a decision tree amounts to building a strategy, i.e. a function δ : ND → A, where A is the set of possible actions, including a special "undefined" action ⊥, chosen for action nodes which are left unexplored by a given strategy. Admissible strategies assign a chance node to each reachable decision node, i.e. must be:

• sound: ∀Di ∈ ND, δ(Di) ∈ Out(Di) ∪ {⊥} ⊆ A, and • complete: (i) ∀Di ∈ Start(DT ), δ(Di) = ⊥ and (ii) ∀Di s.t. δ(Di) = ⊥, ∀N ∈ Succ(Succ(Di, δ(Di))) either δ(N ) = ⊥ or N ∈ NU .
We denote by ∆N (or simply ∆, when there is no ambiguity) the set of admissible strategies built from a tree rooted in N . Each strategy δ defines a connected subtree of DT , the branches of which represent possible scenarios, or trajectories. Formally, a trajectory τ = (aj 0 , xi 1 , aj 1 , . . . , aj h-1 , xi h ) is a sequence of value assignments to decision and chance variables along a path from a starting decision node (a node in Start(DT )) to a leaf: Y0 = aj 0 is the first decision in the trajectory, xi 1 the value taken by its first chance variable, Xj 0 in this scenario, Yi 1 = aj 1 is the second decision, etc.

We identify a strategy δ, the corresponding subtree and the list of its trajectories represented by a matrix. We also consider subtrees, and thus sub-strategies: let Cj be a chance node, Di 1 , . . . , Di k its successors and, for l = 1, k, the strategies δi l ∈ ∆D i l which solve the subproblem rooted in Di l . δi 1 + • • • + δi k is the strategy of ∆C j resulting from the composition of the δi l :

(δi 1 + • • • + δi k )(N ) = δi l (N ) iff N belongs to the subtree rooted in Di l .
Example 1 Let us suppose that a "Rich and Unknown" person runs a startup company. In every state she must choose between Investing (Inv) or Advertising (Adv) and she may be then Rich (R) or Poor (P) and Famous (F) or Unknown (U). Figure 1 shows the possibilistic decision tree (with horizon h = 2) that represents this decision problem. This tree has 8 strategies, 16 trajectories: τ1 = (Adv, R&U, Inv, P &U ), τ2 = (Adv, R&U, Inv, R&U ), τ3 = (Adv, R&U, Adv, R&U ), τ4 = (Adv, R&U, Adv, R&F ), τ5 = (Adv, R&F, Adv, R&U ), τ6 = (Adv, R&F, Adv, R&F ), etc.

The evaluation of a possibilistic strategy, as proposed by [START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF], relies on the qualitative optimistic and pessimistic decision criteria axiomatized by [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF]. The utility of the strategy is computed on the basis of the transition possibilities and the utilities of its trajectories. For each trajectory τ = (aj 0 , xi 1 , aj 1 , . . . , xi h ): 6 As in classical probabilistic decision trees, it is assumed that π(X j = x|past(C j )) only depends on the variables in past(C j ) and actually only on the decision made in the preceding node and on the state of the preceding chance node. • Its utility denoted u(τ ), is the utility u(xi h ) of its leaf.

• The possibility of τ given that a strategy δ is applied from initial node D0 is defined by:

π(τ |δ, D0) = min k=1..h πj k-1 (xi k ) if τ is a trajectory of δ, 0 otherwise.
where πj k-1 is the possibility distribution at Cj k-1 .

It is now possible to compute, for any δ ∈ ∆ its optimistic and pessimistic utility degrees (the higher, the better):

uopt(δ) = max τ ∈δ min(π(τ |δ, D0), u(τ )) upes(δ) = min τ ∈δ max (1 -π(τ |δ, D0), u(τ ))
This approach is purely ordinal (only min and max operations are used to aggregate the evaluations of the possibility of events and the ones of the utility of states). We can check that the preference orderings O between strategies, derived either from uopt (O = uopt) or from upes (O = upes), satisfy the principle of weak monotonicity:

∀Cj ∈ NC j , ∀Di ∈ Succ(Cj), δ, δ ′ ∈ ∆D i , δ" ∈ ∆ Succ(C j )\D i : δ O δ ′ =⇒ δ + δ" O δ ′ + δ ′′
This property guarantees that dynamic programming [START_REF] Bellman | Dynamic Programming[END_REF] applies, and provides an optimal strategy in time polynomial with the size of the tree: [START_REF] Régis | Possibilistic Markov decision processes[END_REF][START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF] have proposed qualitative counterparts of stochastic dynamic programming algorithms: in the finite horizon case backwards induction, or in the infinite horizon case value and policy iteration.

The basic pessimistic and optimistic utilities nevertheless present a severe drawback, known as the "drowning effect", due to the use of idempotent operations. In particular, when two strategies give an identical and extreme (either good, for uopt or bad, for upes), utility in some plausible trajectory, they may be undistinguished although they may give significantly different consequences in other possible trajectories, as illustrated in Example 2.

Example 2 Let δ and δ ′ be the two strategies of Example 1 defined by δ(D0) = δ ′ (D0) = Adv; δ(D1) = Inv; δ ′ (D1) = Adv; δ(D2) = δ ′ (D2) = Adv. δ gathers 4 trajectories, τ1, τ2, τ5, τ6 with π(τ1|D0, δ) = 0.2 and u(τ1) = 0.3; π(τ2|D0, δ) = 0.5 and u(τ2) = 0.5 ; π(τ5|D0, δ) = 0.5 and u(τ5) = 0.5; π(τ6|D0, δ) = 1 and u(τ5) = 0.5. Hence uopt(δ) = upes(δ) = 0.5.

δ ′ is also composed of 4 trajectories (τ3, τ4, τ5, τ6). Hence uopt(δ ′ ) = upes(δ ′ ) = 0.5.

Thus uopt(δ) = uopt(δ ′ ) and upes(δ) = upes(δ ′ ): δ ′ , which provides at least utility 0.5 in all trajectories, is not preferred to δ that provides a bad utility (0.3) in some non impossible trajectory (τ1). τ2, which is good and totally possible "drowns" the bad consequence of δ in τ1 in the optimistic comparison; in the pessimistic one, the bad utility of τ1 is drowned by its low possibility, hence a global degree upes that is equal to the one of δ ′ (that, once again, guarantees a 0.5 utility degree at least).

The two possibilistic criteria thus may fail to satisfy the principle of Pareto efficiency, that may be written as follows, for any optimization criterion O (here upes or uopt):

∀δ, δ ′ ∈ ∆, if (i) ∀D ∈ Common(δ, δ ′ ), δD O δ ′ D and (ii) ∃D ∈ Common(δD, δ ′ D ), δD ≻O δ ′ D , then δ ≻O δ ′
where Common(δ, δ ′ ) is the set of nodes for which both δ and δ ′ provide an action and δD (resp. δ ′ D ) is the restriction of δ (resp. δ ′ ) to the subtree rooted in D.

Moreover, neither uopt or upes do fully satisfy the classical, strict, monotonicity principle, that can be written as follows:

∀Cj ∈ NC , Di ∈ Succ(Cj), δ, δ ′ ∈ ∆D i , δ" ∈ ∆ Succ(C j )\D i , δ O δ ′ ⇐⇒ δ + δ" O δ ′ + δ ′′ It may indeed happen that upes(δ) > upes(δ ′ ) while upes(δ + δ") = upes(δ ′ + δ") (or that uopt(δ) > uopt(δ ′ ) while uopt(δ + δ") = uopt(δ ′ + δ")).
The purpose of the present work is to build efficient preference relations that agree with the qualitative utilities when the latter can make a decision, and break ties when not -to build refinements 7 that satisfy the principle of Pareto efficiency.

Escaping the drowning effect by leximin and leximax comparisons

The possibilistic drowning effect is due to the use of min and max operations. In ordinal aggregations, this drawback is well known and it has been overcome by means of leximin and leximax comparisons [START_REF] Moulin | Axioms of Cooperative Decision Making[END_REF]. More formally, for any two vectors t and t ′ : 7 Formally, a preference relation ′ refines a preference relation if and

• t lmin t ′ iff ∀i, t σ(i) = t ′ σ(i) or ∃i * , ∀i < i * , t σ(i) = t ′ σ(i) and t σ(i * ) > t ′ σ(i * ) • t lmax t ′ iff ∀i, t µ(i) = t ′ µ(i) or ∃i * , ∀i < i * , t µ(i) = t ′ µ(i) and t µ(i * ) > t ′ µ(i * )
only if whatever δ, δ ′ , if δ ≻ δ ′ then δ ≻ ′ δ ′ .
where, for any vector v (here

, v = t or v = t ′ ), v µ(i) (resp. v σ(i) )
is the i th best (resp. worst) element of v.

The refinements of uopt and upes by lexicographic principles have been considered by [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF] for non sequential problems; in this context, a decision is a possibility distribution π over the utility degrees, i.e. a vector of pairs (π(u), u). Then it is possible to write:

• π lmax(lmin) π ′ iff ∀i, (π(u), u) µ(i) ∼ lmin (π ′ (u), u) µ(i) or ∃i * , ∀i < i * , (π(u), u) µ(i) ∼ lmin (π ′ (u), u) µ(i) and (π(u), u) µ(i * ) ≻ lmin (π ′ (u), u) µ(i * ) . • π lmin(lmax) π ′ iff ∀i, (1 -π(u), u) σ(i) ∼ lmax (1 - π ′ (u), u) σ(i) or ∃i * , ∀i < i * , (1 -π(u), u) σ(i) ∼ lmax (1 - π ′ (u), u) σ(i) and (1 -π(u), u) σ(i * ) ≻ lmax (1 -π ′ (u), u) µ(i * ) .
where (π(u), u) µ(i) is the i th best pair of (π(u), u) according to lmin and (1π(u), u) σ(i) is the i th worst pair of (1π(u), u) according to lmax.

A straightforward way of applying this to sequential decision is to reduce the compound possibility distribution corresponding to the strategy, as usually done in possibilistic (and probabilistic) decision trees. The reduction of δ yields the distribution π δ on the utility degrees, defined by: π δ (u) = max τ,u(τ )=u π(τ |δ, D0). Then we can write:

δ lmax(lmin) δ ′ iff π δ lmax(lmin) π δ ′ , δ lmin(lmax) δ ′ iff π δ lmin(lmax) π δ ′ .
lmax(lmin) (resp. lmin(lmax) ) refines uopt (resp. upes ), but neither lmax(lmin) nor lmin(lmax) do satisfy Pareto efficiency, as shown by the following counterexample. 2). δ and δ ′ are the two strategies defined by: δ

Example 3 Consider a modified version of the problem of Example 1 (Figure

(D0) = δ ′ (D0) = Adv, δ(D1) = Inv, δ ′ = (D1) = Adv, δ(D2) = δ ′ D 2 = Adv. Common(δ, δ ′ ) = {D0, D1, D2}, δD 0 = δ ′ D 0 , δD 2 = δ ′ D 2
and δD 1 dominates δ ′ D 1 w.r.t. lmax(lmin), since ((1, 0.1), (1, 0.9)) ⊲ lmax(lmin) ((1, 0.1)(0.5, 0.9)). δ should then be strictly preferred to δ ′ . By reduction, we get π δ (0.9) = π δ (0.1) = min(0.4, 1) = 0.4 and π δ (0.8) = min(1, 1) = 1 and for δ ′ we have π δ ′ (0.9) = min(0.4, 0.5) = 0.4, π δ ′ (0.1) = min(0.4, 1) = 0.4 and π δ ′ (0. The drowning effect at work here is due to the reduction of strategies, namely to the fact that the possibility of a trajectory is drowned by the one of the least possible of its edges. That is why we propose to give up the principle of reduction and to build lexicographic comparisons on strategies considered in extenso. Recall that: uopt(δ) = max

τ ∈δ min min k=1..h πj k-1 (xi k ); u(xi h ) .
Then, for any τ = (aj 0 , xi 1 , . . . , aj h-1 , xi h ) and τ ′ = (a j ′ 0 , x i ′ 1 , . . . , a j ′ h-1 , x i ′ h ), we define lmin and lmax by:

• τ lmin τ ′ iff (πj 0 (xi 1 ), . . . , πj h-1 (xi h ), u(xi h )) lmin (π j ′ 0 (x i ′ 1 ), . . . , π j ′ h-1 (x i ′ h ), u(x i ′ h )) • τ lmax τ ′ iff (1 -πj 0 (xi 1 ), . . . , 1 -πj h-1 (xi h ), u(xi h )) lmax (1 -π j ′ 0 (x i ′ 1 ), . . . , 1 -π j ′ h-1 (x i ′ h ), u(x i ′ h ))
Hence the proposition of the following preference relations8 :

• δ lmax(lmin) δ ′ iff ∀i, τ µ(i) ∼ lmin τ ′ µ(i) or ∃i * , ∀i ≤ i * , τ µ(i) ∼ lmin τ ′ µ(i) and τ µ(i * ) ≻ lmin τ ′ µ(i * ) , • δ lmin(lmax) δ ′ iff ∀i, τ σ(i) ∼ lmax τ ′ σ(i) or ∀i, τ σ(i) ∼ lmax τ ′ σ(i) or ∃i * , ∀i ≤ i * , τ σ(i) ∼ lmax τ ′ σ(i) and τ σ(i * ) ≻ lmax τ ′ σ(i * ) ,
where τ µ(i) (resp. τ ′ µ(i) ) is the i th best trajectory of δ (resp δ ′ ) according to lmin and τ σ(i) (resp. τ ′ σ(i) ) is the i th worst trajectory of δ (resp δ ′ ) according to lmax .

These relations are relevant refinements and escape the drowning effect -they are those we are looking for: Proposition 1 lmax(lmin) is complete, transitive and refines uopt ; lmin(lmax) is complete, transitive and refines upes .

Proposition 2 lmax(lmin) and lmin(lmax) both satisfy the principle of Pareto efficiency as well as strict monotonicity.

Propositions 1 and 2 have important consequences; from a prescriptive point of view, they outline the rationality of lmax(lmin) and lmin(lmax) and suggest a probabilistic interpretation, which we develop in Section 5. From a practical point of view, they allow us to define a dynamic programming algorithm to get lexi optimal solutions -this is the topic of the next Section.

Dynamic Programming for lexi qualitative criteria

The algorithm we propose (Algorithm 1 for the lmax(lmin) variant; the lmin(lmax) variant is similar) proceeds in the classical way, by backwards induction: when a chance node is reached, an optimal substrategy is recursively built for each of its children; these substrategies are combined but the resulting strategy is NOT reduced, contrarily to what is classically done; when a decision node is reached, the program is called for each child and the best of them is selected. The comparison of strategies is done on the basis of the matrices of their trajectories (denoted ρ ; each line gathers the possibility and utility degrees of a trajectory τ = (aj 0 , xi 1 , aj 1 , . . . , aj h , xi h )):

ρ lt =    πj t-1 xi t if t ≤ h, O = lmax lmin 1 -πj t-1 xi t if t ≤ h, O = lmin lmax u xi h if t = h + 1.
So as to allow fast comparisons, the matrices are built incrementally and ordered on the fly by the function ConcatAndOrder: when a The lexicographic comparison of two strategies δ and δ ′ is performed by scanning the elements ρ l,t and ρ ′ l,t of ρ and ρ ′ in parallel, line by line from the first one. The first pair of different (ρ l,t , ρ ′ l,t ) determines the best matrix/strategy. If the matrices have different numbers of lines, neutral lines are added at the bottom of the shortest one (filled with 0 for the optimistic case, with 1 for the pessimistic one).

Even if working with matrices rather than numerical values, the algorithm is polynomial w.r.t. the size of the original tree. This is because (i) the algorithm crosses each edge of the tree only once (as in the classical version), (ii) the matrices are never bigger than the strategies and (iii) the comparison of strategies is done in time linear with their size -thus linear with the size of the original tree.

Lexi comparisons and Expected Utility

If the problem is not sequential, it is easy to see that the comparison of possibilistic utility distributions by lmax(lmin) and lmin(lmax) do satisfy the axioms of EU. [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF] have indeed shown that these decision criteria can be captured by an EU -namely, relying on infinitesimal probabilities and utilities. In this Section, we claim that such a result can be extended to sequential problems -for decision trees.

The proof relies on a transformation of the possibilistic tree into a probabilistic one. The graphical components are identical and so are the sets of admissible strategies. In the optimistic case the probability and utility distributions are chosen in such a way that the lmax(lmin) and EU criteria do provide the same preference on ∆. To this extent, we build a transformation φ :

L ⊆ [0, 1] → [0, 1]
that maps each possibility distribution to an additive distribution and each utility level into an additive one; this transformation is required to satisfy the following condition:

(R) : ∀α, α ′ ∈ L such that α > α ′ : φ(α) h+1 > b h φ(α ′ ),
where b is the branching factor of the tree. Condition (R) guarantees that if uopt(δ) = α > uopt(δ ′ ) = α ′ , then a comparison based on a sum-product approach on the new tree will also decide in favor of δ.

For any chance node Cj, a local transformation φj is then derived from φ, such that φj satisfies both condition (R) and the normalization condition of probability theory. EUopt denotes the preference relation provided by the EU-criterion on the probabilistic tree obtained by replacing each πj by φj • πj and the utility function u by φ • u. We show that:

Proposition 3 If (R) holds, then EUopt refines uopt . Proposition 4 δ lmax(lmin) δ ′ iff δ EUopt δ ′ , ∀(δ, δ ′ ) ∈ ∆.
Example 4 φ(1) = 1, φ(0.9) = 0.2, φ(0.8) = 0.001, φ(0.5) = 10 -10 , φ(0.4) = 10 -30 , φ(0.1) = 10 -91 .

It holds that φ(α) 3 > φ(α ′ ) * 2 2 , for all α > α ′ . We obtain the transformed conditional distributions by normalizing on each node. For instance for node C1, φ1(10 -30 ) = 10 -30 1+10 -30 and φ1(1) = The construction is a little more complex if we consider the lmin(lmax) comparison, where the utility degrees are not directly compared to possibility degrees π but to degrees 1π. Hopefully, it is possible to rely on the results obtained for the optimistic case, since the optimistic and pessimistic utilities are dual of each other.

Proposition 5 Let DT inv the tree obtained from DT by using utility function u ′ = 1u on leaves. It holds that:

upes,DT (δ) ≥ upes,DT (δ ′ ) iff u opt,DT inv (δ ′ ) ≥ u opt,DT inv (δ)
As a consequence, we build an EU-based equivalent of lmin(lmax) , denoted EUpes , by replacing each possibility distribution πi in DT by the probability distribution φi • πi, as for the optimistic case and each utility degree u byφ(1)φ(u). It is then possible to show that:

Proposition 6 δ lmin(lmax) δ ′ iff δ EUpes δ ′ , ∀(δ, δ ′ ) ∈ ∆.
Propositions 4 and 6 show that lexi-comparisons have a probabilistic interpretation -actually, using infinitesimal probabilities and utilities. This result comforts the idea, first proposed by [START_REF] Benferhat | Possibilistic and standard probabilistic semantics of conditional knowledge bases[END_REF] and then by [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF], of a bridge between qualitative approaches and probabilities, through the notion of big stepped probabilities [START_REF] Benferhat | Possibilistic and standard probabilistic semantics of conditional knowledge bases[END_REF][START_REF] Snow | Diverse confidence levels in a probabilistic semantics for conditional logics[END_REF]. We make here a step further, by the identification of transformations that support sequential decision making.

Beyond this theoretical argument, this result suggests an alternative algorithm for the optimization of lmax(lmin) (resp. lmin(lmax)): simply transform the possibilistic decision tree into a probabilistic one and use a classical, EU-based algorithm of dynamic programming. In a perfect world, both approaches solve the problem in the same way and provide the same optimal strategiesthe difference being that the first one is based on the comparison of matrices, the second one on expected utilities in R + . The point is that the latter handles infinitesimals; then either the program is based on an explicit handling of infinitesimals, and proceeds just like the matrix-based comparison, or it lets the programming language handle these numbers in its own way -and, given the precision of the computation, provides approximations.

Experiments

We thus get three criteria for each of the pessimistic and optimistic approaches: the basic possibilistic ones, the lexicographic refinements described in Section 3, and the EU approximations of the latter. We compare the 3 variants within each series with two measures: the CPU time and a pairwise success rate: Success A B is the percentage of solutions provided by an algorithm optimizing criterion A that are optimal with respect to criterion B; for instance, the lower Success u opt lmax(lmin)

, the more important the drowning effect.

The backward induction algorithms corresponding to the six criteria have been implemented in Java. As to the EU-based approaches, the transformation function depends on the horizon h and the branching factor b (here b = 2). We used φ

(1L) = 1, φ(αi) = φ(α i+1 ) h+1 b h * 1.1
, each φj being obtained by normalization of φ on Cj. The experiments have been performed on an Intel Core i5 processor computer (1.70 GHz) with 8GB DDR3L of RAM..

The tests were performed on complete binary decision trees, for h = 2 to h = 7, that are randomly generated. The first node is a decision node: at each decision level from the root (i = 1) to the last level (i = 7) the tree contains 2 i-1 decision nodes.This means that with h = 2 (resp. 3, 4, 5, 6, 7), the number of decision nodes is equal to 5 (resp. 21, 85, 341, 1365, 5461) The utility values are uniformly randomly fired in the set L = {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1}. Conditional possibilities relative to chance nodes are normalized, one edge having possibility one and the possibility degree of the other is uniformly fired in L. For each value of h, 100 decision trees are generated.

Figure 4 presents the average execution CPU time for the six criteria. We observe that, whatever the optimized criterion, the CPU time increases linearly w.r.t. the number of decision nodes, which is in line with what we could expect. Furthermore, it remains affordable with big trees: the maximal CPU time is lower than 1s for a decision tree with 5461 decision nodes. It appears that u opt is always faster than EUopt, which is 1.5 or 2 times faster than lmax(lmin) The same conclusion is drawn when comparing lmin(lmax) to upes and EUpes. These results are easy to explain: (i) the manipulation of matrices is obviously more expensive than the one of numbers and (ii) the handling of numbers by min and max operations is faster than sum-product manipulations of infinitesimal. As to the success rate, the results are described in Figure 5. The percentage of solutions optimal for uopt (resp. for upes) that are also optimal for lmax(lmin) (resp. lmin(lmax)) is never more than 82%, and decreases when the horizon increases: the drowning effect is not negligible and increases with the length of the trajectories. Moreover EUopt (resp. EUpes) does not perform well as an approximation of lmax(lmin) (resp. lmin(lmax)): the percentage of solutions optimal for the former which are also optimal for the latter is lower than 80% in all cases, and decreases when h increases. This is easily explained by the fact that the probabilities are infinitesimals and converge to 0 when the length of the branches (and thus the number of factors in the products) increase, as suggested in Section 5.

These experiments conclude in favor of the lexi refinements in their full definition -their approximation by expected utilities are comparable in terms of CPU efficiency but not precise enough. The EU criteria nevertheless offer a better approximation than uopt and upes when space is limited (or when h increases).

Concluding remarks

This work has both theoretical and practical implications. It extends and generalizes to sequential problems the theoretical links established in [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF] between possibilistic utilities and expected utilities. It performs better that the refinement of binary possibilistic utilities (BPU) proposed in [START_REF] Weng | Qualitative decision making under possibilistic uncertainty: Toward more discriminating criteria[END_REF] for Binary Possibilistic Utilities and as a particular case, to classical, optimitic and pessimistic, possibilitistic utilities. In [START_REF] Weng | Qualitative decision making under possibilistic uncertainty: Toward more discriminating criteria[END_REF]'s treatment indeed, two similar trajectories of the same strategy are merged. The resulting criterion thus suffers from a drowning effect and does no satisfy strict monotonicity: as such, it cannot be represented by an EU-based criterion which "counts" trajectories (weighted by their probabilities). We actually do refine [START_REF] Weng | Qualitative decision making under possibilistic uncertainty: Toward more discriminating criteria[END_REF]'s criterion. Incorporating our lexicographic refinements in BPU would lead to a more powerful refinement and suggests a probabilistic interpretation of efficient BPU. It also leads to new planning algorithms that are more "decisive" than their original counterparts.

The perspectives of our work are twofold. First, our approach could be naturally extended to solve possibilistic Markov Decision Processes.This extension seems theoretically straightforward, since a finite-horizon MDP can be translated into a set of decision trees (one for each state). Thus, our theoretical results hold for finite-horizon MDPs as well. However, the direct application of the lexicographic approach to possibilistic MDPs may lead to algorithms which are exponential in time and space (w.r.t. the MDP description), since the decision trees associated to a MDP may be of exponential size, while (possibilistic) MDPs can be solved in polynomial time [START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF][START_REF] Régis | Possibilistic Markov decision processes[END_REF]. Determining whether computing lexicographic optimal solutions to possibilistic MDPs is tractable is a perspective of this work.

The second perspective of this work, not unrelated, is to develop simulation-based algorithms for finding lexicographic solutions to MDPs. Reinforcement Learning algorithms [START_REF] Sutton | Reinforcement Learning:An Introduction[END_REF] allow to solve large size MDPs by making use of simulated trajectories of states to optimize a strategy. It is not immediate to develop RL algorithms for possibilistic MDPs, since no unique stochastic transition function corresponds to a possibility distribution. However, uniform simulation of trajectories (with random choice of actions) may be used to generate an approximation of the possibilistic decision tree (provided that both transition possibilities and utility of the leaf are given with the simulated trajectory). So, interleaving simulations and lexicographic dynamic programming may lead to RL-type algorithms for approximating lexicographic-optimal policies for (large) possibilistic MDPs.

5 Figure 1 .

 51 Figure 1. The possibilistic decision tree of Example 1

Figure 2 .

 2 Figure 2. A counter example at the efficiency of lmax(lmin)

1 1+10 1 1+10 - 10 Figure 3 .

 11103 Figure 3. Transformed probabilistic decision tree of possibilisic decision tree of (counter)-example 3

Figure 4 .

 4 Figure 4. Average CPU time (in ms) for h=2 to 7

Figure 5 .

 5 Figure 5. Sucess rate

  Algorithm 1: DynProgLmaxLmin(N :Node) Data: δ, the strategy built by the algorithm, is a global variable Result: Computes δ for DT N and returns the maxtrix of its

	trajectories, ρ
	begin
	// Leaves
	if N ∈ NU then ρ = [u(N )];
	// Chance nodes
	if N ∈ C then
	k = |Succ(N )|;
	for Di ∈ Succ(N ) do
	ρi ← DynP rogLmaxLmin(Di);
	ρ ← ConcatAndOrder(ρ1, . . . , ρ k , πN );
	// Decision nodes
	if N ∈ D then
	ρ ← [0]

foreach aj ∈ Out(N ) do ρj ← DynP rogLmaxLmin(Succ(N, aj)); if ρj lmax(lmin) ρ then ρ ← ρj and δ(N ) ← aj; return ρ; chance node, say Cj is reached, k = |Succ(Cj)| substrategies are built recursively and their matrices ρ1, . . . , ρ k are computed. Matrix ρ of the current (compound) strategy, for the subtree rooted in Cj, is obtained by calling ConcatAndOrder ρ1, . . . , ρ k , πC j . This function adds a column to each ρi, filled with πj(xi) ; the matrices are vertically concatenated; then the elements in the lines are ordered in decreasing (resp. increasing) order, and the lines are reordered by decreasing (resp. increasing) order w.r.t. to lmax (resp. lmin). As a matter of fact, once ρ has been reordered, ρ1,1 is always equal to uopt(δ) (resp. upes(δ)).

The proofs are omitted for the sake of brevity but are available at https://www.irit.fr/publis/ADRIA/PapersFargier/ecai2016.pdf

If the strategies have different numbers of trajectories, neutral trajectories (vectors) are added to the shortest strategy, at the bottom of the shortest list of trajectories


Hélène Fargier

Pierre-François Gimenez

Jérôme Mengin

Recommendation for product configuration: an experimental evaluation

. The second one, that we propose here, is to learn a Bayesian network from the entire sample as model of the users' preferences, and to use it to recommend a pertinent value.

Introduction

In on-line sale contexts, one of the main limiting factors is the difficulty for the user to find product(s) that satisfy her preferences, and in an orthogonal way, the difficulty for the supplier to guide potential customers. This difficulty increases with the size of the e-catalog, which is typically large when the considered products are configurable. Such products are indeed defined by a finite set of components, options, or more generally by a set of variables (or "features"), the values of which have to be chosen by the user. The search space is thus highly combinatorial. It is generally explored following a stepby-step configuration session: at each step, the user freely selects a variable that has not been assigned yet, and chooses a value. Our issue is to provide such problems with a recommendation facility, by recommending, among the allowed values for the current variable, one which is most likely to suit the user.

The problem of providing the user with an item that fulfills her preferences has been widely studied, leading to the content-based and the collaborative filtering approaches, and every variation in between [START_REF] Adomavicius | Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions[END_REF][START_REF]Recommender Systems Handbook[END_REF][START_REF] Jannach | Recommender Systems -An Introduction[END_REF]. However, these solutions can't deal with configurable products, e.g. cars, computers, kitchens, etc. The first reason is that the number of possible products is huge -exponential in the number of configuration variables. For instance, in the car configuration problem described in [START_REF] Astesana | Constraint-based vehicle configuration: A case study[END_REF] the definition of "Traffic" delivery vans involves about 150 variables, and an e-catalog of 10 27 feasible versions. The second reason is that the recommendation task considered in interactive configuration problem is quite different from the one addressed in classical product recommendation: the system is 1 IRIT, CNRS, University of Toulouse, France, email: fargier@irit.fr 2 IRIT, CNRS, University of Toulouse, France, email: pgimenez@irit.fr 3 IRIT, CNRS, University of Toulouse, France, email: mengin@irit.fr not asked to recommend a product (a car) but a value for the variable selected by the user 4 . Finally, the third reason is that we cannot assume any prior knowledge about the user, nor about its buying habits -complex configurable products, like cars, are not bought so often by one individual. So we have no information about similarity between users (upon which collaborative filtering approaches are based) nor on the preferences of the current user (upon which content-based filtering approaches are based).

The present work deals with the the recommendation of values in interactive configuration, with no prior knowledge about the user, but given a list of products previously configured and bought by other users ("sale histories"). The basic idea is to recommend, for a given variable at a given step of the configuration process, a value that has been chosen by other users in a similar context, where the context is defined by the variables that have already been decided, and the values that the current user has chosen for these variables. From this point, two directions can be explored. The first one is to select a set of similar configurations in the sale history (typically, the k closest ones, using a distance measure) and to compute the best recommendation from this set -this is the line proposed by [START_REF] Coster | Enhancing web-based configuration with recommendations and cluster-based help[END_REF]. The second one, yet not explored is to learn a from the entire sample a model of the users' preferences, e.g. a Bayesian net, and to use it to propose a pertinent value.

The paper is structured as follows: the basic notations are presented in Section 2. The next two sections present the two families of approaches that we have explored: Bayesian nets in Section 3 and k-closest neighbors in Section 4. They are experimentally compared and discussed in Section 5.

Background and notations

A configuration problem is defined by a set X of n discrete variables, each variable X taking its value in a finite domain X. A complete configuration is thus a tuple o ∈ X∈X X; we denote by X the set of all of them.

If W is a tuple of variables, W denotes the set of partial configurations X∈W X; we will often denote such a partial configuration by the corresponding lower case letter w. Also, if W and V are two sets of variables, and if

w ∈ w, then w[V ] is the projection of w onto V ∩ W . Furthermore, if w ∈ W , w is said to be compatible with v if w[V ∩ W ] = v[V ∩ W ]
; in this case we write w ∼ v. Finally, in the case where w and v are compatible, we denote by w.v the tuple that extends w with values of v for variables in V \ W (equivalently, wv extends v with values of w for variables in W \ V ).

Not all combinations represent feasible products, because of some possible feasibility or marketing constraints; let P be the subset of X that represent feasible products. In practice, the set P is still a huge set.

In interactive configuration problems, the user builds the product she is interested in through a variable by variable interaction. At each step, let Assigned be the set of variables for which she has already chosen values, u be the tuple values assigned to these variables and UnAssigned the set of free variables ; then the user freely selects the next variable to be assigned (we denoted Next this variable). The system then has to: The computation of a pertinent recommendation is the topic of the present work.

The recommendation of feature values, when any, is often limited to the proposition of a default value, generally the one advised by the seller in a static way or through a set of rules. Other approaches are based on similarity measures and propose to determine the k-nearest neighbor configuration that are similar to the current set of user requirements. These type of approaches support the idea that the user sets her most important requirements and let the system complete the configuration but seldom takes place in a process of interactive configuration (the reader shall consult [START_REF] Falkner | Recommendation technologies for configurable products[END_REF] for a survey about recommendation technologies for configurable product).

In the context considered by this paper, sales histories are available, on which the system can rely to base its recommendation. Formally, a sale history is a (multi) set H ⊆ X of complete configurations that correspond to products that have been bought by past users (thus they are feasible, i.e. belong to P ). In the sequel, for a partial configuration u, #(u) will denote the number of configurations in H that extend u.

Recommendation with Bayesian networks

Users have different preferences, depending on the taste and the environment of the user, which make them prefer different productshence a large variety of products in the histories. We do not have any information about their taste, nor do we use any information about their environment. Instead, it can be assumed that there is a ground probability distribution p over the set of complete configurations (i.e. the space of all feasible products), indicating how likely it is that each object is the one that the current user prefers. This probability may depend on her personality, and on her current environment, but it can be assumed that the sales history gives a good approximation of that probability distribution: the configured products eventually bought by the past users are the one they prefer.

Therefore, if Next is the next variable to be assigned a value, and if u is the vector of values that have been chosen for the variables already decided, we propose to estimate, for each possible value v for Next, the marginal conditional probability p(Next = v | Assigned = u): it is the marginal probability that Next has value v in the most preferred product of the current user, given the choices that she made so far; hence we can recommend the most probable value (among the admissible ones):

argmax v∈Next p(Next = v | Assigned = u).
The idea of our work is that the sale history is a sample of X according to the unknown distribution p, that we can use to estimate probabilities. A first, naive method to compute p(v | u) would be to count the proportion of v within the sold products that verify u. Even if this idea works for small u's, after a few steps the number of products that verify u would be too low and the computations would not be reliable enough (and even impossible when no product in the history verifies u). Hence the idea of learning, off-line, a Bayesian network from the data set and to use it, on-line, during the step-bystep configuration session: the user defines a partial configuration u by assigning some variables and chooses a variable Next ; the recommendation task consists in computing the marginal p(Next | Assigned = u) and recommending the user with the value of Next that maximizes this probability.

Bayesian networks

A Bayesian network (BN) [START_REF] Pearl | Probabilistic reasoning in intelligent systems -networks of plausible inference[END_REF] over set of variables X is defined by a directed acyclic graph (DAG) over a X , and a set of local conditional probability tables (CPT), one for each variable of X . If N denotes a Bayesian network, for X ∈ X we denote by PaN (X) the set of parents of X in the graph; the local probability table associated to X specifies the probability pN (X = x | u) for every x ∈ X and every u ∈ PaN (x); if U denotes the parents of X, we denote the table associated to X by ΘN (X | U ).

A Bayesian network N uniquely defines a probability distribution pN over X : the probability of a complete configuration o ∈ X is

pN (o) = X∈X ΘN (o[X] | o[PaN (X)]) = X∈X ΘN (X, o).

Example 1. Consider following Bayesian network:

A C E F D B
The probability of a configuration abcdef can be computed as:

Θ(a)Θ(c | a)Θ(e | c)Θ(f )Θ(d | cf )Θ(b | ad) and Θ(D, abdcf ) is defined to be Θ(D | cf ).
In the sequel, we will often omit the subscript N when there is no ambiguity.

Learning a Bayesian network

The learning of Bayesian networks from data proceeds in two steps: finding the structure of the network, i.e. of the DAG underlying the Bayesian network and then its parameters, i.e. the conditional probabilities table. Both aim at maximizing likelihood estimates, i.e. the probability of observing the given set.

Since learning the most probable a posteriori Bayesian network from data is an NP-hard problem [START_REF] Maxwell | Learning bayesian networks is npcomplete[END_REF], heuristic strategies had to be found. There are two main families of approaches in structure learning: the score-based ones and the constraint-based ones.

The formers search for a network that maximizes a score pointing out to what extend the network fits the data [START_REF] Gregory | A bayesian method for the induction of probabilistic networks from data[END_REF]. The score may be a Bayesian function, such as Bayesian Dirichlet scores (analysed in [START_REF] Polpo De Campos | Properties of bayesian dirichlet scores to learn bayesian network structures[END_REF]), or come from information theory, such as the Bayesian Information Criterion [START_REF] Schwarz | Estimating the dimension of a model[END_REF] or the Akaike Information Criterion [START_REF] Akaike | A new look at the statistical model identification[END_REF].

The latter approach looks for conditional independences, through independence tests, assuming the faithfulness of the network to learn. An early example is the Inductive Causation algorithm of Pearl [START_REF] Verma | Equivalence and synthesis of causal models[END_REF] ; a more recent one is PC [START_REF] Spirtes | Causation, prediction, and search[END_REF].

Finally, hybrid method exist, such as MMHC [START_REF] Tsamardinos | The max-min hill-climbing bayesian network structure learning algorithm[END_REF], that learns the undirected structure of the network with a constraint-based approach (named MMPC) and then orients the edge of the DAG with a scorebased method. Another example is Sparse Candidate (SC) [START_REF] Friedman | Learning bayesian network structure from massive datasets: the «sparse candidate «algorithm[END_REF].

Computing marginals

The computation of the posterior marginal probability p(Next | Assigned) is a classical task of Bayesian inference. In general, it is broken down into computations of two separate prior marginals, since, by definition p(Next | Assigned) = p(Next ∧ Assigned)/p(Assigned).

Recall that, for a given configuration o, p(o) is defined to be the product of local, conditional probabilities that correspond to o in the CPT's of the network. Then, given a variable X ⊆ X and a partial configuration x ∈ X, the marginal probability p(x) is the sum of the probabilities of the complete configurations that extend x:

p(x) = w ∈ X w[X] = x = w ∈ X w[X] = x Y ∈ X Θ(w[Y ] | w[P aN (Y )]).
Computing such prior marginals is known to be an NP-hard problem when p is represented by a Bayesian network [START_REF] Dagum | Approximating probabilistic inference in bayesian belief networks is np-hard[END_REF]-the size of the formula can grow exponentially fast with the number of variables. Exact inference algorithms, such as variable elimination [START_REF] Nevin | A simple approach to bayesian network computations[END_REF], value elimination [START_REF] Bacchus | Value elimination: Bayesian inference via backtracking search[END_REF], jointree algorithms [START_REF] Steffen | Local computations with probabilities on graphical structures and their application to expert systems[END_REF], cutset conditioning [START_REF] Pearl | A constraint-propagation approach to probabilistic reasoning[END_REF], recursive conditioning [START_REF] Darwiche | Recursive conditioning[END_REF], work by breaking down this sumproduct formula, into sub-sums and sub-products. These algorithms have a worst-case time complexity exponential with respect to the treewidth of the network. Variable elimination and jointree methods [START_REF] Steffen | Local computations with probabilities on graphical structures and their application to expert systems[END_REF] are costly in space while recursive conditioning allows an anyspace inference and can be polynomial in space. Even if they target a NP-hard task, the algorithms are efficient enough on real world benches to allow an on-line use.

Recommendation using Naive Bayesian Networks

In a Naive Bayesian network, one central variable (the one on which inference is to be made) is targeted and the others are assumed independent from each other conditionally to this variable of interest.

A naive Bayesian network is therefore a Bayesian network the structure of which is a tree, and where the variable of interest (in our case, Next) is the parent of every other variables (in our case, the variables in Assigned). For any value v of Next and any assignment u of Assigned, we know that P (v|u) is proportional to P (vu); under the strong assumptions of the naive Bayesian network:

P (vu) = P (v) X∈Assigned P (u[X] | v)
So we will recommend the value v that maximizes

P (v|u) ∝ P (v) X∈Assigned P (u[X] | v)
Since the variable we are recommending a value for depends on the configuration process, we would need a naive Bayesian network for every variable: to recommend a value for Next, we would use the naive Bayesian network for which Next is the variable of interest. The computation of the networks is preprocessed: (all) the prior distributions P (X) and (all) the conditional tables P (Y |X) (i.e., potentially all the naive Bayesian networks) are computed off line, before the configuration process, from the sample:

P (X = x) = #(x) |H| for each X ∈ X P (Y = y|X = x) = #(x.y) + 1 #(x) + |Y | for each pair X, Y ∈ X
The (pre)computation of n prior tables and n 2 conditional probability tables are thus sufficient to make a prediction for any variable at any moment.

The strong assumptions of naive Bayesian networks is generally inconsistent: when we want to recommend a value for Next, we assume that all the variables in Assigned are conditionally independent given Next. In spite of this naive and strong assumption, they are efficient enough for some applications. Among their qualities, they are easy to learn and easily scalable, requiring a number of parameters quadratic in the number of variables.

k-nearest neighbor

In [START_REF] Coster | Enhancing web-based configuration with recommendations and cluster-based help[END_REF], three algorithms are proposed that are based on the selection of a neighborhood: rather than computing the preference from the entire sample, the system should focus on sold configurations that are similar to the present one -i.e. use the k nearest neighbors. All the methods proposed in [START_REF] Coster | Enhancing web-based configuration with recommendations and cluster-based help[END_REF] are based on the Hamming distance; namely, given an assignment u of Assigned, and a complete configuration w, d(u, w) counts the number of variables in Assigned on which the two configurations disagree:

d(u, w) = | {x ∈ Assigned | u(x] = w[x]} |
At each step, these methods first selects the set N (k, u) of the knearest neighbors of the current partial configuration u, and compute the recommendation on this basis.

Weighted Majority Voter

The simplest algorithm is the Weighted Majority Voter, which predicts the value of Next on the basis of a weighted majority vote of the k nearest neighbors. The weight of a configuration w in N (k, u) is set equal to the degree of similarity between this configuration and the current one, u, i.e. the number of variables that are given the same value by both:

weight(u, w) = | {X ∈ Assigned | u[X] = w[X]} |
The recommended value for Next is chosen among the ones that are authorized by the constraints by maximizing:

vote(v) = w ∈ N (k, u) w[Next] = v weight(u, w)

Most Popular Choice

Most Popular Choice predicts the most popular (actually, the most probable) extension of the current configuration, u, from the knowledge of the closed neighbors and recommends the value supported by this configuration. It holds that, for any full configuration uw that extends u, P (uw) = P (u|w).P (w). [START_REF] Coster | Enhancing web-based configuration with recommendations and cluster-based help[END_REF] make the assumption that the variables that have not been assigned are mutually independent, and that the ones that are assigned are independent from one another given w. Hence we have:

P (uw) = Π X∈X \Assigned P (w[X]) . Π X∈Assigned P (u[X]|w)
The probabilities are estimated from the k nearest neighbors of u:

• for X ∈ X \ Assigned and x ∈ X :

P (x) = 1 k |{w ′ ∈ N (k, u), w[X] = x}|;
• for X ∈ Assigned and x ∈ X , let N (k, u, w) be the set of neighbors of u that agree with w on Assigned:

N (k, u, w) = {w ′ ∈ N (k, u), w ′ [Assigned] = w[Assigned]}, then P (x | w)
is the fraction of N (k, u, w) that has value x, with a kind of m-estimate correction since N (k, u, w) may be empty:

P (x|w) = |{w ′ ∈ N (k, u, w)|w ′ [X] = x}| + 1 |N (k, u, w)| + k
The value recommended for variable Next is the one prescribed by the w that maximizes P (uw). The drawback of this method is that nothing guarantees that the value computed is compatible with u according to the constraint.

Naive Bayes Voter

The Naive Bayes Voter is similar to the Naive Bayes method proposed in Section 3.4, with the difference that it uses the k nearest neighbors to build a naive Bayes network. Since these neighbors depends on the current configuration, is not possible to preprocess the computation of the probability table -this approach may be much slower than the classical naive Bayes. The recommended value for Next is chosen among the ones that are authorized by the constraints by maximizing P (v|u) ∝ p(v) X∈Assigned p(u[X] | v), where:

N ext X1 X2 . . . X k
• p(v) = 1 k |{w ∈ N (k, u)|w[Next] = v}| • for every X ∈ Assigned and every v ∈ Next, let N (k, u, v) be
the set of neighbors of u that have value v for Next, then

p(u[X] | v) = |{w ∈ N (k, u, v)|w[X] = u[X]}| + 1 |N (k, u, v)| + k

Experiments

The approaches proposed in this paper have been tested on a case study of three sales histories provided by Renault, a French automobile manufacturer 5 . These data sets, named "small", "medium" and "big", are genuine sales histories -each of them corresponds to a configurable car, and each example in the set corresponds to a configuration of this car which has been sold: -dataset "small" has 48 variables and 27088 examples.

-dataset "medium" has 44 variables and 14786 examples.

-dataset "big" has 87 variables and 17724 examples. Most of the variables are binary, but not all of them. We used the R package bnlearn to learn the Bayesian networks [START_REF] Scutari | Learning bayesian networks with the bnlearn R package[END_REF] -more precisely, we used Hill Climbing (HC) to learn the two datasets of about 50 variables (small and medium) and MMHC to learn the big dataset of about 90 variables. The average number of parents of a node in the obtained BN is about 1.17, 1.02 and 0.98 -for small, medium and big, respectively. As to Bayesian inference, we used the jointree algorithm provided by the library Jayes [START_REF] Kutschke | Jayes -bayesian network library under eclipse public license[END_REF]. We implemented the Naive Bayes approach and the algorithms based on the k nearest neighbors (k is set to 20 in the experiments reported here; other values of k do not improve the results).

Experimental protocol

We used a two-folds cross-validation: each dataset has been cut by half, an algorithm learns with one half (which constitute the sale history) and is tested with the other (which can be view as a set of online configuration sessions).

The protocol is described in Algorithm 1. Each test is a simulation of a configuration session, i.e. a sequence of variable-value assignments. In real life, a genuine variable ordering was used by the user for her configuration session and the different sessions generally obey different variable orderings. Unfortunately, the histories provided by Renault describe sales histories only, i.e. sold products, and not the sequence of configuration in each session. That is why we generate a session session for each product P in the test set by randomly ordering its variable-value assignments. Then, for each variable-value assignment (X, x) in this sequence, the recommender is asked for a recommendation for X, say r: r may be equal to x; or not, if r more probable than x according the inference process ; then X is set to x. We consider a recommendation as correct if the recommended value is the one of X in the product P (i.e. if r = x). Any other value is be considered as incorrect.

The recommendation algorithm is evaluated by (i) the time needed for computing the recommendations and (ii) its success rate, obtained by counting the number of correct and incorrect recommendations.

Oracle

In order to easily interpret the results of the cross-validation, we propose to compute the highest success rate attainable for the test set. If we where using an algorithm that already knows the testing set, it would use the probability distribution estimated from this testing set. Therefore it would recommend for the variable Next, given the assigned values u, the most probable value of X in the subset of products, in the test set, that respect u. More precisely, for any x in the domain of Next, it would estimate p(x|u) as #(ux)/#(u). Notice that #(u) is never equal to zero, since the test set contains at least one product consistent with u: the one corresponding to the current session. It is an algorithm overfitted to the testing set.

We call this algorithm "Oracle". Its success rate is higher than the one of any other strategy. Its success rate isn't 100% since there is an intrinsic variability in the users (otherwise only one product would be sold . . . ). The success rate of the "Oracle" is generally not attainable by the other algorithms, because the "Oracle" has access to the testing set, what is obviously not the case of the algorithms we evaluate.

Results

The experiment have been made on a computer with a quad-core processor i5-3570 at 3.4Ghz, using a single core. All algorithms are written in Java, and the Java Virtual Machine used was OpenJDK.

Success rate

Figures 2, 3 and 4 give the success rate of the pure BN-based approach (BN and Naive Bayes) on the one hand, and of the methods based on k closest neighbors on the other hand, on our configuration instances. The experiment is completed with the application of the configuration protocol on classical Bayesian networks benchmarks [START_REF] Scutari | Learning bayesian networks with the bnlearn R package[END_REF] 6 . The oracle is given as an ideal line.

It appears that on the configuration instances, the pure naive based approach, which makes very strong independence assumptions, has a low success rate (this error rate is bad also on classical BN benchmarks). This is not surprising, since the variables are not independent from one another, at least because of the constraints. The independence assumptions at work in the methods based on the k closest neighbors are in a sense less drastic, since the distance used to select the neighborhood implicitly captures some dependencies.

On configuration problems, 3 methods are have very good results: Classical Bayes Net, Naive Bayes Voter and Most Popular Choice. Their success rate is very good (only a few points from the Oracle). The gap with the Oracle gets larger when the number of assigned 6 On these benchmarks, the protocol remains the same but has another interpretation: the assignment of a variable corresponds to the conditioning of the knowledge base by an observation; the "recommendation" then corresponds to the inference of the most probable value for a variable of interest variables increases: the Oracle's performance becomes less and less attainable. Indeed, the prediction of the Oracle relies on the testing sample, that includes the product of the ongoing configuration. When few variables are instantiated, the Oracle uses a rather big subsample to make its estimation. When a lot of variables are instantiated, the Oracle uses a small subsample, so small that sometimes it contains only the ongoing configuration. In this case, the Oracle can't make a bad recommendation. This can be interpreted as overfitting, since the Oracle is tested on the sample it learned. This phenomena is especially visible with the dataset "big", because it has more variables that "small" or "medium". Classical Bayes is the more accurate method on BN instances we tested (hailfinder, alarm, child, insurance, see e.g. Figure 5 for the insurance bench), which is not surprising either, because the network learnt precisely captures the indepedencies (the sample is perfectly faithful to the BN). But the Naive Bayes Voter and Most Popular Choice do not perform so bad on these instances, from which it can be concluded that these approaches capture a great part of the dependencies, even not explicitly.

CPU time

The CPU time (see Figures 2, 3 and4) clearly breaks the set of algorithms in two groups: the ones that learn, off-line, the dependencies from the entire data set and the ones that compute a new neighborhood at each step.

The former group of method are one order of magnitude quicker than the latters on the small and medium instances (and some times two: Weighted Majority voter, which has good performances in terms of prediction, is much slower). This is explained by the time needed to extract the k best neighbors before computing the recommendation. On the other hand, this time is not too sensitive to the size of the problem -it remains low on the big instance.

One can check that on this data set, which corresponds to a real world application, the CPU times of all the method tested are compatible with an on line use, with less than 10 ms in any case. Unsurprisingly, the approximation by a naive Bayesian net is the one that run the fastest (less than 0.05 ms in any case). The time need by Classical Bayesian Nets is in the same order of magnitude, less than 0.1 ms, for the small and medium data set. It stays under 0.25 ms for the big data set.

Influence of the sample's size

The drawback of the methods based on a neighborhood is that their performances seem to depend on the size of the original sample: the greater, the better the prediction but the higher the time needed to make it. To confirm this, we performed another experiment, varying the size of the sample (from the full sample to a sample containing only 1 64 th of the original one). This of course leads to an improvement of the performances in terms of CPU and space, but also to a a strong degradation of the accuracy. As a matter of fact, on the small data set, the handling by Most Popular Choice of a sample of 1 32 of the original one needs twice less time, but the error rate stay over a 9% line (instead of an average of 4%). Naive Bayes Voter and Classical Bayesian Networks are more resistant: for Naive Bayes Voter the time for handling a sample of 1 32 of the original one is divided by 3, with an error rate staying over a 8% line (instead of an average of 5%).

Conclusion

This paper has proposed the use of Bayesian nets as a new approach to the problem of value recommendation in interactive product configuration.

Our experiments on real world datasets show that Bayesian Nets are compatible with an on-line context. Classical Bayesian Nets have a success rate close to the best possible one. The naive Bayes approximation is average (about 10 % of error, i.e. twice the minimal error) but very quick. The other approaches proposed by the literature (Naive Bayes Voter and Most Popular Voter) have a success rate similar to the one of Classical Bayesian Nets, and a CPU time that is independent on the size of the instance (1 to 5 ms) -but strongly depend on the size of the sample. They are outperformed by Bayesian net on configuration instances on reasonable size and of course on classical Bayesian benches. We shall thus conclude in favor of the approach based on Bayesian net learning for problems with a large sample but a limited memory resource keeping in mind that naive Bayes shall be an alternative on situations involving very big instances and a very limited memory resource. When it is possible to explicitly memorize the sample, the high accuracy of methods based on a a subsample of close neighbors constitute a simple and accurate solution.

Figure 1 .

 1 Figure 1. The naive Bayesian network built by Naïve Bayes Voter. Next is the variable of interest.

Algorithm 1 : 7 Assigned ← ∅ 8 for 9 r 11 else increment error by 1 12

 1789111 Protocol for evaluating value recommendation in interactive configuration Input: The training set Htr and the testing set Htest Output: The success rate main : 1 learning of Htr 2 success ← 0 3 error ← 0 4 Assigned ← ∅ 5 for each P ∈ Htest do 6 session ← randomly order the variable-value assignments in P each (Next, x) ∈ session do ← recommended value for Next given Assigned 10 if r = x then increment success by 1 Assigned ← Assigned ∪ {(Next, x)} 13 return success/(success + error )

Figure 2 .Figure 3 .

 23 Figure 2. Average error rate and time on dataset "small"

Figure 4 .

 4 Figure 4. Average error rate and time on dataset "big"

Figure 5 .Figure 6 .Figure 7 .

 567 Figure 5. Average error rate and time on dataset "insurance"

Note that we are not concerned here with the choice of the variable -this choice is under the control of the user, not under the one of the recommender system. It is worthwhile noticing that the fact that the variables are considered and assigned in a free order forbids the use of techniques based on decision trees.

available at http://www.irit.fr/~Helene.Fargier/BR4CP/ benches.html