Margot Herin
email: margot.herin@lip6.fr

Patrice Perny
email: patrice.perny@lip6.fr

Nataliya Sokolovska
email: nataliya.sokolovska@sorbonne-universite.fr

LEARNING GAI-DECOMPOSABLE UTILITY MODELS FOR MULTIATTRIBUTE DECISION MAKING

We propose an approach to learn a multiattribute utility function to model, explain or predict the value system of a Decision Maker. The main challenge of the modeling task is to describe human values and preferences in the presence of interacting attributes while keeping the utility function as simple as possible. We focus on the generalized additive decomposable utility model which allows interactions between attributes while preserving some additive decomposability of the evaluation model. We present a learning approach able to identify the factors of interacting attributes and to learn the utility functions defined on these factors. This approach relies on the determination of a sparse representation of the ANOVA decomposition of the multiattribute utility function using multiple kernel learning. It applies to both continuous and discrete attributes. Numerical tests are performed to demonstrate the practical efficiency of the learning approach.

Introduction

An increasing number of AI systems is used to describe, explain or predict human behaviors in evaluation or decision making tasks, but also to help one or more individuals to make a relevant choice in the light of their preferences [START_REF] Domshlak | Preferences in ai: An overview[END_REF][START_REF] Pigozzi | Preferences in artificial intelligence[END_REF]. Intelligent decision systems can also be used to give machines the ability to make sophisticated decisions in complex environments in an autonomous but controlled way [START_REF] Kathleen | Human decision makers and automated decision aids: Made for each other? In Automation and human performance[END_REF]. These systems are often grounded on decision theory which proposes preference models that verify normative properties guaranteeing the internal consistency of the value system modeled and the resulting decisions [START_REF] Raiffa | Decision analysis: introductory lectures on choices under uncertainty[END_REF][START_REF] Fishburn | Utility Theory for Decision Making[END_REF][START_REF] Ralph L Keeney | Decisions with multiple objectives: preferences and value trade-offs[END_REF][START_REF] Roy | Multicriteria methodology for decision aiding[END_REF][START_REF] Peter | Prospect theory: For risk and ambiguity[END_REF].

One of the current research challenges in this area is to produce models that are sufficiently expressive to account for a diversity of possible behaviors, but at the same time sufficiently simple to remain interpretable and allow the explanation of evaluations or decisions [START_REF] Labreuche | A general framework for explaining the results of a multi-attribute preference model[END_REF]. There is also a need of automated mechanisms for preference assessment and tailoring general models to specific users [START_REF] Braziunas | Elicitation of factored utilities[END_REF]. With this in mind, we focus in this paper on learning utility functions to efficiently represent values and preferences on multiattribute objects. For this purpose, the most widely used preference model is the so-called additive utility model [START_REF] Krantz | Foundations of Measurement (Additive and Polynomial Representations)[END_REF]. It assumes a special kind of independence among attributes called "mutual preferential independence" which ensures that the overall utility of multiattribute objects can be decomposed as the sum of mono-attribute utility functions. Such decomposability significantly simplifies the construction of the model that can be achieved componentwise. However, in practice, preferential independence is often violated, when interactions among attributes are present, and the simple additive utility model does not fit. This is the reason why, in this paper, we tackle the problem of learning a more general multiattribute utility function in the presence of interacting attributes, with the aim of keeping the model as simple and decomposable as possible.

Les us consider a toy example involving a set of cars described using 3 attributes, namely car make, body color and seat color. Let X 1 = {Ferrari, Lamborghini, Porsche} be the car make domain, X 2 = {Blue, Red, Yellow} be the body color domain, and X 3 = {Black, White} the seat color domain. Assume that an individual (named the Decision Maker hereafter, DM for short) prefers a red body color for a Ferrari but a blue one for a Porsche. Then one cannot build a mono-attribute utility function on body color because the preferences on body colors depend on the car make. This is an example of interaction between two attributes. A similar problem appears when, in addition, the DM prefers a black seat color for a red car and a white seat color for a blue car. This makes it impossible to define a mono-attribute utility function on the seat color. Hence the DM's preferences over X 1 × X 2 × X 3 cannot be described by an additive utility function of the form u(x 1 , x 2 , x 3 ) = u 1 (x 1 ) + u 2 (x 2 ) + u 3 (x 3 ) due to presence of interactions among attributes {1, 2} on the one hand, and among attributes {2, 3} on the other. A less decomposable utility function can be used instead, of the form: u(x 1 , x 2 , x 3 ) = u 1,2 (x 1 , x 2 ) + u 2,3 (x 2 , x 3 ). Function u 1,2 measures the attractiveness of the pair (car make, body color) for the DM while function u 2,3 measures car and seats color matching.

We can see that some additive decomposability still remains in this decomposition but utility factors now include several interacting attributes and the factors may partially overlap (here x 2 appears in both factors). Such a decomposition over overlapping factors is called a GAI decomposition where GAI stands for Generalized Additive Independence [START_REF] Fishburn | Utility Theory for Decision Making[END_REF]. It includes additive and multilinear decompositions as special cases [START_REF] Ralph L Keeney | Decisions with multiple objectives: preferences and value trade-offs[END_REF], and also multiattribute utility models based on Choquet integrals [START_REF] Grabisch | A decade of application of the choquet and sugeno integrals in multi-criteria decision aid[END_REF], but it is much more flexible as it does not make any assumption on the kind of interactions between attributes. For this reason, it is widely used for preference modeling and decision support and was the subject of various studies in the AI community [START_REF] Bacchus | Graphical models for preference and utility[END_REF][START_REF] Gonzales | GAI networks for utility elicitation[END_REF][START_REF] Braziunas | Local utility elicitation in GAI models[END_REF][START_REF] Braziunas | Minimax regret based elicitation of generalized additive utilities[END_REF][START_REF] Brafman | Directional decomposition of multiattribute utility functions[END_REF][START_REF] Bigot | Using and learning gai-decompositions for representing ordinal rankings[END_REF].

The construction of a GAI utility model from preference information (overall evaluations or pairwise comparisons) remains a challenge. It requires the determination of the relevant factors to be used in the decomposition (groups of interacting attributes) as well as the determination of sub-utility functions on these factors. Some contributions focus on the elicitation of these sub-utility functions, assuming the decomposition of the utility into factors is known [START_REF] Gonzales | GAI networks for utility elicitation[END_REF][START_REF] Braziunas | Local utility elicitation in GAI models[END_REF]. Some other tackle the problem of learning the decomposition. For example, a procedure to learn the GAI model (structure + utility tables) has been proposed [START_REF] Bigot | Using and learning gai-decompositions for representing ordinal rankings[END_REF] in the case of boolean attributes and interactions limited to subsets of bounded size (typically 2 elements). More recently, a procedure to determine a well-formed decomposition of monotonic GAI models was proposed [START_REF] Grabisch | Well-formed decompositions of generalized additive independence models[END_REF] wherein the interactions are limited to pairs of attributes.

However, until now, the learning of general GAI models with no prior assumption on the size of the interacting groups of attributes is still understudied. All the above-mentioned contributions either assume that the structure of the GAI decomposition is known or that it is limited to interactions involving very few attributes. Moreover, most of them only consider the case of finite attribute domains. In this paper, we propose a more general procedure to learn a GAI utility model, kept as simple as possible, with no prior restriction on the size of interactions, and that applies to both continuous and discrete attribute domains.

The paper is organized as follows. In a first section we recall some background on multiattribute utility models and GAI decompositions. Then, in the second section, we present an approach to construct a GAI decomposition from data using multiple kernel learning. Finally, a third section provides the results of numerical tests on synthetic and real data.

Background and Notations

Let us consider a finite set N = {1, . . . , n} of attributes used to describe a set X of alternatives in a decision problem. Every alternative x in X is characterized by a multiattribute evaluation vector x = (x 1 , . . . , x n ) where x i is the evaluation of x with respect to attribute i, for any i ∈ N . Let X i be the attribute domain of i, i.e., the set of possible values of alternatives on attribute i. This set can be continuous or discrete. The multiattribute description space is denoted = X 1 × . . . × X n and X can be characterized as a subset of . Let denote the DM's preference relation, which is assumed to be a weak order over .

Under mild assumptions [START_REF] Debreu | Continuity properties of paretian utility[END_REF], it can be shown that is representable by a utility, i.e., there exists a utility function u : → such that xy ⇔ u(x) ≥ u(y) for all x, y ∈. As preferences are specific to each individual, utilities must be elicited using sequences of preference queries or learned using databases of preference examples. Another use of multiattribute utility functions can be to measure the intrinsic value of any alternative for the DM. In this case, the multiattribute utility function can be learned from a labeled data set wherein overall utility values are assigned by the DM to elements of . DM's preferences usually have an underlying structure induced by independence among attributes that substantially decreases the complexity of the model. This simplifies its interpretation and its use for optimization tasks [START_REF] Gonzales | Gai networks for decision making under certainty[END_REF]. The simplest case is obtained when values or preferences over = X 1 × . . . × X n are represented by an additive utility. When DM's preferences are more complex and may include interaction among attributes, a more elaborate model is needed, as illustrated in the introduction. This motivates the introduction of GAI decompositions: Definition 1 Let F be a collection of subsets of N = {1, . . . , n}. A utility function u(•) is GAI-decomposable w.r.t. F if there exist functions u S : X S →, S ∈ F such that:

u(x 1 , ..., x n ) = S∈F u S (x S ), for all (x 1 , . . . , x n ) ∈,
where x S is the tuple formed by the x j 's, j ∈ S.

Note that, in the above definition, the condition N = S∈F S is not required because some components x i in the model may appear to be unessential to explain the available preference information and could be removed to produce a more compact model. Given a multiattribute utility function u defined on X there may exist multiple distinct GAI decompositions of this function. This raises a problem of identifiability [START_REF] Thomas | Identification in parametric models[END_REF], as shown in the following example:

Example 1 Function u(x 1 , x 2 , x 3 , x 4 ) = (x 1 -x 2 ) 2 + 2x 1 (x 2 + x 3 ) + x 4 could be seen as the sum of the three following factors:

u 12 (x 1 , x 2 ) = (x 1 -x 2 ) 2 , u 1,2,3 (x 1 , x 2 , x 3 ) = 2x 1 (x 2 + x 3
) and u 4 (x 4 ) = x 4 or rewritten as the sum of four smaller factors, e.g.,

u ′ 1 (x 1 ) = x 2 1 , u ′ 2 (x 2 ) = x 2 2 , u ′ 13 (x 1 , x 3 ) = 2x 1 x 3 and u ′ 4 (x 4 ) = x 4 .
The latter decomposition is simpler because it includes factors of smaller arity that are subsets of the factors used in the former decomposition.

In order to further specify what would be a suitable representation of utilities and preferences we might consider well-formed decompositions as proposed in [START_REF] Grabisch | Well-formed decompositions of generalized additive independence models[END_REF].

Definition 2 A GAI decomposition is well-formed if each term u S appearing in the decomposition satisfies the following conditions:

• each variable in S is active, i.e., the derivative of u S w.r.t. this variable is not identically 0,

• u S cannot be further decomposed into terms involving a proper subset of variables

Coming back to Example 1, the decomposition of u into u ′ 1 +u ′ 2 +u ′ 13 +u ′
4 is well-formed and refines the decomposition u = u 12 + u 123 + u 4 that is therefore not-well formed.

Unfortunately, there may exist multiple well-formed decompositions of the same GAI utility function due to possible utility transfers from a factor to another. This is well illustrated by the following example:

Example 2 u(x 1 , x 2 ) = x 1 +x 2 can be rewritten as u α 1 (x 1 )+u α 2 (x 2 ) with u α 1 (x 1 ) = (x 1 -α) and u α 2 (x 2 ) = (x 2
+α) for any constant α, thus providing an infinity of possible decompositions of the same utility function.

In order to avoid such utility transfers and obtain a uniquely defined decomposition of the utility function, we shall consider the ANOVA decomposition as suggested in [START_REF] Ilya | Global sensitivity indices for nonlinear mathematical models and their monte carlo estimates[END_REF]:

Definition 3 An ANOVA decomposition of a function u(x 1 , . . . , x n ) defined on [0, 1] n and integrable on this domain is a representation of u in the form:

u(x) = f ∅ + S⊆N \∅ f S (x S ) (1)
where f S are factors such that 1 0 f S dx i = 0 for all non-empty S in N and all i ∈ S.

In this definition, the multiattribute space X is identified to [0, 1] n for simplicity, as in [START_REF] Ilya | Global sensitivity indices for nonlinear mathematical models and their monte carlo estimates[END_REF]. This is not restrictive since the attribute domains X i , i ∈ N can be numerically encoded and normalized. Thus, in the following, the integrals are always computed between 0 and 1.

The name ANOVA comes from ANalysis Of VAriance. Indeed, if u is square integrable and the attributes x i are random variables uniformly distributed in [0, 1], the ANOVA representation of u allows deriving a decomposition of the variance of u(x).

It is important to note that the ANOVA decomposition of a utility function is uniquely defined, which guarantees its identifiability without any ambiguity. We indeed have f ∅ = u(x)dx 1 . . . dx n by integrating Equation 1 on [0, 1] n . Then, by integrating the same equation over all variables except x i we obtain

f i (x i ) = u(x)Π k̸ =i dx k -f ∅ . Now, if we
integrate Equation 1 on all variables except x i and x j we obtain

f ij (x i , x j ) = u(x)Π k̸ =i,j dx k -f i (x i ) -f j (x j ) -f ∅ .
The process can be continued similarly to identify the factors of higher arity. For instance, the ANOVA decomposition of the utility function introduced in Example 2 is:

f ∅ = 1 0 1 0 (x 1 + x 2 )dx 1 dx 2 = 1 f 1 (x 1 ) = 1 0 (x 1 + x 2 )dx 2 -f ∅ = x 1 - 1 2 f 2 (x 2 ) = x 2 - 1 2 f 12 (x 1 , x 2 ) = x 1 + x 2 -f 1 (x 1 ) -f 2 (x 2 ) -f ∅ = 0
Now, if we consider the model given in Example 1, the same process leads to the following ANOVA decomposition:

f ∅ = 5 3 , f 1 (x 1 ) = x 1 + x 2 1 - 5 6 , f 2 (x 2 ) = x 2 2 - 1 3 (2)
f 3 (x 3 ) = x 3 - 3 7 , f 4 (x 4 ) = x 4 - 1 2 (3)
f 13 (x 1 , x 3 ) = 2x 1 x 3 -x 1 -x 3 + 3 7 (4)
In the next section, we propose a method for learning a sparse GAI decomposition of a utility function based on the identification of its ANOVA decomposition. To this end, we use the framework of multiple kernel learning (MKL) that we introduce hereafter.

A MKL Algorithm for Learning a GAI Decomposition

We want to learn utility function u from a set of examples {(x j , y j ), j ∈ E} where x j ∈ X is an alternative and y j ∈ R denotes its overall evaluation. An efficient approach to learn a multivariate function from regression examples is to use a Support Vector Regression (SVR) algorithm [START_REF] Smola | A tutorial on support vector regression[END_REF]. This algorithm consists in searching u as a linear model in some high-dimensional space H, attached to a mapping function ϕ : R n → H such that u(x) = ⟨w, ϕ(x)⟩ + b. Function ϕ makes it possible to go beyond the linear model and to fit more complex utility shapes. The learning is performed by minimizing both the error on the regression examples and the oscillation of the utility function (to maximize flatness) in the space generated by ϕ. This can be achieved by minimizing the L 2 norm of w along with the ϵ-sensitive loss as follows:

(P SV R ) min C j∈E (ϵ + j + ϵ - j ) + 1 2 ∥w∥ 2 2 y j -⟨w, ϕ(x j )⟩ -b ≤ ϵ + ϵ + j , j ∈ E ⟨w, ϕ(x j )⟩ + b -y j ≤ ϵ + ϵ - j , j ∈ E ϵ + j , ϵ - j ≥ 0, j ∈ E
where C > 0 controls the tradeoff between flatness and data fitting and ϵ > 0 is a tolerance threshold.

The efficiency of this method is due to the compact dual formulation of P SV R , the size of which only depends on the number of regression examples |E|. It can be obtained using Lagrangian duality and reads as follows:

(D SV R ) max - j,l∈E (α + j -α - j )(α + l -α - l )K(x j , x l ) + j∈E (α + j -α - j )y j -ϵ j∈E (α + j + α - j ) j∈E α + j -α - j = 0 α + j , α - j ∈ [0, C], j ∈ E
where K(x j , x l ) = ⟨ϕ(x j ), ϕ(x l )⟩ and K is referred to as the kernel associated with ϕ. This approach relies on polynomial computations of the values K(x, x ′ ) that do not require the computation of the high dimensional vectors ϕ(x). For instance, a widely used kernel is the Gaussian radial basis function (RBF) kernel. While involving a projection function ϕ of infinite dimension, it can be simply computed as follows:

K(x, x ′ ) = e -∥x-x ′ ∥ 2 2 /2σ 2
. More generally, any symmetric positive definite bi-variate function K can be used since they always represent a scalar product in some feature space H [START_REF] Schölkopf | Learning with kernels: support vector machines, regularization, optimization, and beyond[END_REF]. Finally, using the KKT conditions, the coefficients w and the intercept b can be recovered from the dual optimal variables, and the learned utility function is: u(x) = j∈E (α + j -α - j )K(x j , x) +b. Such kernel-based machine learning methods have proved to be effective for utility elicitation from preference statements [START_REF] Domshlak | Unstructuring user preferences: Efficient non-parametric utility revelation[END_REF][START_REF] Lahaie | Kernel methods for revealed preference analysis[END_REF][START_REF] Chapelle | A machine learning approach to conjoint analysis[END_REF]. In our case, we propose to use the particular framework of multiple kernel learning (MKL) [START_REF] Francis R Bach | Multiple kernel learning, duality, and the smo algorithm[END_REF] to derive a GAI-decomposition of the utility function u. In general, MKL methods replace the kernel K with a convex combination of kernels K = l d l K l (the weights d l are positive and preserve the property of definite positiveness), in order to either combine multiple kernels with different properties or combine different sources of information. Here, we consider a basis of kernel functions (K S ) S⊆N where for any S ⊆ N \ ∅, K S is a kernel attached to the sub-utility u S depending on, and only on, the attributes in S. By convention, K ∅ is a constant function equal to one. Let d = (d S ) S⊆N \∅ denote the kernel weights and d ∅ the intercept of the model. Since the product of positive definite kernels is also a positive definite kernel, this basis can be constructed using a univariate kernel k : R × R → R and defining K S (x, x ′ ) as the product j∈S k(x j , x ′ j ) for any x, x ′ ∈ X and any S ⊆ N \ ∅. Note that for d = (1, . . . , 1), the kernel K = S⊆N \∅ K S coincides with the well-known ANOVA kernel [START_REF] Stitson | Support vector regression with anova decomposition kernels[END_REF][START_REF] Saunders | Ridge regression learning algorithm in dual variables[END_REF]. However, if the name is related to the ANOVA's core idea of decomposing a function in terms depending on subsets of variables, this kernel does not provide an ANOVA decomposition since nothing guarantees that u S dx i = 0, for any S ⊆ N \ ∅ and i ∈ S (See Definition 3). Also, the ANOVA kernel uses all the possible subsets of N (or all until a given size p) and does not perform a selection of the most important subsets. In order to select the most useful coalitions and provide a simple ANOVA decomposition, we need to learn a sparse representation of the weight vector d. The objective of selecting only a few kernels in the kernel basis is at the core of MKL and the need for a simultaneous optimization over the weights d and the dual variables α + j , α - j has led to the development of many optimization algorithms (see [START_REF] Gönen | Multiple kernel learning algorithms[END_REF] for an overview). Here, we use L 1 regularization to obtain sparsity in d, as in [START_REF] Varma | Learning the discriminative power-invariance trade-off[END_REF][START_REF] Gunn | Structural modelling with sparse kernels[END_REF].

In order to implement the multiple kernel learning approach on problem P SV R with the kernel K = S⊆N \∅ d S K S and the intercept b = d ∅ , we first make explicit the associated mapping function of K. Let ϕ S denote the mapping function attached to the kernel K S for any S ⊆ N \ ∅, then ϕ = ( √ d S ϕ S ) S⊆N \∅ is the mapping function associated to K. Indeed, for any x, x ′ ∈ X , we have:

K(x, x ′ ) = S⊆N \∅ d S K S (x, x ′ ) = S⊆N \∅ d S ⟨ϕ S (x), ϕ S (x ′ )⟩ = S⊆N \∅ ⟨ d S ϕ S (x), d S ϕ S (x ′ )⟩ = ⟨ϕ(x), ϕ(x ′ )⟩
Thus, using the kernel K amounts to searching a utility function of the form u(x) = ⟨w, ϕ(x)⟩ + d ∅ = S⊆N \∅ √ d S ⟨w S , ϕ S (x)⟩ + d ∅ where w = (w S ) S⊆N \∅ . Finally, we introduce an L 1 -regularization term on weight vector d in the initial problem P SV R . Since the weights are positive, the L 1 -penalty is simply the sum of the weights. Then, the obtained approximation problem, denoted P, is the following:

(P) min C j∈E (ϵ + j + ϵ - j ) + S⊆N \∅ 1 2 ∥w S ∥ 2 2 + λ S⊆N \∅ d S y j - S⊆N \∅ d S ⟨w S , ϕ S (x j )⟩ -d ∅ ≤ ϵ + ϵ + j , j ∈ E (5) S⊆N \∅ d S ⟨w S , ϕ S (x j )⟩ + d ∅ -y j ≤ ϵ + ϵ - j , j ∈ E (6) ϵ + j , ϵ - j ≥ 0, j ∈ E, d S ≥ 0, S ⊆ N \ ∅ (7)
where λ > 0 is a regularization hyper-parameter that controls the level of sparsity we want to enforce on d.

Similarly to the SVR algorithm, one can apply Lagrangian duality to recover a dual formulation of this problem. Let α + = (α + j ) j∈E , α -= (α - j ) j∈E denote the positive dual variables respectively attached to the sets of constraints ( 5) and ( 6) and β + = (β + j ) j∈E , β -= (β - j ) j∈E , µ = (µ S ) S⊆N \∅ the positive dual variables respectively attached to the sign constraints on the primal variables ϵ + = (ϵ + j ) j∈E , ϵ -= (ϵ - j ) j∈E and d (constraints [START_REF] Roy | Multicriteria methodology for decision aiding[END_REF]). Let 1 denote the vector whose components are all equal to one. Then, the vectorial formulation of the Lagrangian function is

L = C⟨1, ϵ + + ϵ -⟩ + 1 2 ∥w∥ 2 2 +λ⟨1, d⟩+⟨α + , -ϵ1-ϵ + +Y -φw -d ∅ 1⟩+⟨α -, -ϵ1-ϵ --Y + φw +d ∅ 1⟩-⟨β + , ϵ + ⟩-⟨β -, ϵ -⟩-⟨µ
, d⟩ with φ = (ϕ(x j )) j∈E the matrix that vertically stacks the vectors ϕ(x j ) and Y = (y j ) j∈E . Also, the dual problem, denoted D, is the following problem:

(D) max

(α + ,α -,β + ,β -,µ)∈(R + ) t min ϵ + ,ϵ -,w,d,d ∅ L
where t = 4|E| + 2 n -1 is the number of dual variables. Due to the square roots √ d S present in the mapping function ϕ, L is not differentiable w.r.t. d. However, since L is differentiable w.r.t ϵ + , ϵ -, w and d ∅ , we have the following necessary optimality conditions:

∂L ∂w = w - φ( α + -α -) = 0 (8)
∂L ∂ϵ + = C1 -α + -β + = 0, ∂L ∂ϵ -= C1 -α --β -= 0 (9) ∂L ∂d ∅ = ⟨1, α + -α -⟩ = 0 (10)
Using Equations 8, 9 and 10, we obtain that for any d:

g(d) = min ϵ + ,ϵ -,w,d ∅ L = ⟨α + -α -, Y ⟩ -ϵ⟨1, α + + α -⟩ + S⊆N \∅ d S (λ -µ -1 2 (α + -α -) KS (α + -α -))
with KS = (K S (x j , x l )) j,l∈E for any S ⊆ N \ ∅. Function g is differentiable w.r.t d, and thus for any S ⊆ N \ ∅, we can derive the last necessary conditions:

∂g ∂d S = λ -µ S - 1 2 (α + -α -) KS (α + -α -)=0 (11)
Then, using Equations 8, 9, 10 and 11, and the positivity of µ, β + , β -, the dual Problem D boils down to the following optimization problem:

(D) max⟨α + -α -, Y ⟩ -ϵ⟨1, α + + α -⟩ λ - 1 2 (α + -α -) KS (α + -α -)≥0,S⊆N \∅ (12) ⟨α + -α -, 1⟩ = 0, (13)
α + j , α - j ∈ [0, C], j ∈ E Provided that the kernel basis (K S ) S⊆N \∅ is constructed with a positive definite univariate kernel k, the matrices KS are positive semi-definite, and the dual problem is convex. Then it is a convex quadratically constrained optimization problem and thus can be solved in polynomial time with interior points methods using standard solvers. We can recover the optimal weight values d S for any S ⊆ N \ ∅ and the intercept d ∅ by respectively accessing the dual values of the set of constraints ( 12) and ( 13). Finally, using Equation 8, we recover the learned utility function as follows:

u(x) = S⊆N \∅ d S j∈E (α + j -α - j )K S (x j S , x S ) + d ∅ = S⊆N \∅ u S (x S ) + d ∅ with u S (x s ) = d S j∈E (α + j -α - j )K S (x j S , x S )
, the sub-utility attached to the group of attributes S. Then the presence of a sub-utility u S in the decomposition of the utility function u is equivalent to a non-null weight d S . We thus recover simple decompositions by increasing the L 1 -penalty hyper-parameter λ in problem D.

Retrieving an ANOVA Decomposition

Finally, we guarantee the identification of an ANOVA decomposition by constraining the model so that u S dx i = 0 holds for all sub-utility factors u S , S ⊆ N \ ∅ and all i ∈ S. This is achieved by constructing an univariate kernel k 0 (x, y) the integral of which (w.r.t x or y) equals zero, as proposed in [START_REF] Durrande | Anova kernels and rkhs of zero mean functions for model-based sensitivity analysis[END_REF]:

k 0 (x, y) = k(x, y) -s k(s, y)ds t k(x, t)dt s t k(s, t)dsdt (14)
Then for any x ∈ R, k 0 (x, s)ds = 0. Also, under mild hypothesis on kernel k, it can be shown that the attached kernel k 0 is still positive definite [START_REF] Durrande | Anova kernels and rkhs of zero mean functions for model-based sensitivity analysis[END_REF]. Then, we can construct the associated basis of kernels (K 0 S ) S⊆N \∅ , defined by:

K 0 S (x s , y s ) = i∈S k 0 (x i , y i )
For any x, y ∈ [0, 1] n , S ⊆ N \ ∅ and i ∈ S we have:

K 0 S (x S , y S )dy i = j∈S\{i} k 0 (x j , y j ) k 0 (x i , y i )dy i = 0
Then, using the centered kernel basis (K 0 S ) S⊆N \∅ , each sub-utility u S (x S ) = d S j∈E (α + j -α - j )K 0 S (x j S , x S ) is guaranteed to have a zero integral with respect to x i whatever i ∈ S. Thus, the obtained decomposition is an ANOVA decomposition.

Remark that, in addition to be positive definite, the univariate kernel k is now required to verify k(s, x)ds < ∞ for any x ∈ X and k(s, t)dsdt < ∞ so that k 0 is well defined (See Equation 14). Also, in practice, these integrals have to be approximated with numerical integration. To avoid unnecessary repeated computations, we use a discretized representation of function x → k(s, x)ds that has been computed beforehand. Standard examples of univariate kernels that can be used here are the Gaussian RBF kernel k(x, y) = e -(x-y) 2 /2σ 2 , the odd order B-spline kernel k(x, y) = B 2m+1 (x -y), m ∈ N or the first order infinite spline kernel k(x, y) = 1 + xy + 1 2 |x -y| min(x, y) 2 + 1 3 min(x, y) 3 [START_REF] Schölkopf | Learning with kernels: support vector machines, regularization, optimization, and beyond[END_REF][START_REF] Izmailov | Multidimensional splines with infinite number of knots as svm kernels[END_REF].

As mentioned before, the advantage of the ANOVA decomposition is that it is uniquely defined for a given u and its factors can be learned from examples as explained above. However, although the use of penalization promotes the emergence of sparse ANOVA representations, the obtained representation can be further simplified by keeping only the maximal factors (i.e., factors having a maximal scope with respect to set inclusion), the others being included as subsets. More precisely, the non-maximal factors can be aggregated with the maximum factors containing them to reduce the number of factors without loosing the well-formed nature of the decomposition (see Definition 2). In the presence of two or more maximal factors with a non-empty intersection S, the factors whose scope is included in S could be indifferently aggregated to any maximal factor containing them or spread into all or part of them. Whatever the chosen option, it yields to a well-formed GAI decomposition of u that is possibly more compact than the learned ANOVA decomposition. Multiple GAI representations are therefore possible, sharing the same maximal factors as ANOVA decomposition.

For the sake of illustration, let us come back to Example 1 and consider the ANOVA decomposition given in Equations [START_REF] Pigozzi | Preferences in artificial intelligence[END_REF][START_REF] Kathleen | Human decision makers and automated decision aids: Made for each other? In Automation and human performance[END_REF][START_REF] Raiffa | Decision analysis: introductory lectures on choices under uncertainty[END_REF]. By aggregating f 1 (x 1 ) and f 3 (x 3 ) to f 13 (x 1 , x 3 ) and remarking that the sum of constant terms equals zero, function u can be rewritten, after simplification, as the sum of 3 terms:

u ′′ 2 (x 2 ) = x 2 2 , u ′′ 4 (x 4 ) = x 4 and u ′′ 13 (x 1 , x 3 ) = x 2 1 + 2x 1 x 3 .

Numerical Experiments

This section presents the results of numerical tests performed on synthetic and real-world preference data. We implement our method, called SMKGAI for Sparse Multiple Kernel GAI, with the Gaussian RBF kernel using σ = 1. The tolerance threshold ϵ is set to 0.01 and the regularization hyper-parameters C and λ are selected by cross-validation using a number of folds equal to 3. All tests are conducted on a 2.8 GHz Intel Core i7 processor with 16GB RAM and we used the mathematical programming Gurobi solver (version 9.1.2).

Synthetic Data

We first show the result of the learning on synthetic data generated using a 6-dimensional model u

(x) = u 1 (x 1 ) + u 2 (x 2 ) + u 34 (x 3 , x 4 ) + u 45 (x 4 , x 5
). The factors u 1 and u 2 are taken as quadratic spline functions and u 34 and u 45 are bivariate tensor products of quadratic splines. To generate the factors we use a basis of B-splines functions of zero integral forming an ANOVA decomposition of u. We generate a set E of overall evaluations of size 70 from the hidden utility function u, with a random uniform draw of alternatives x j in [0, 1] n . The data is then perturbated with a centered Gaussian noise with standard error σ = 0.05. In Figure 1 we represent the ground truth utility factors in grey and the learned utility factors in green.

Secondly, we conduct an experiment using a model with a high degree of interaction: u(x) = n i=1 x i + 1000 n i=1 x i for n = 6. In order to assess the benefit of allowing high interactions in the learning of a GAI decomposition, we compare SMKGAI with p-additive GAI utilities that do not use L 1 regularization to select the most useful factors but that include factors of size at most p for p ∈ {1, 2, 3, 4}. The case p = 1 corresponds to the learning of an additive utility. This is done using the SVR algorithm, i.e., by solving the dual formulation of the initial problem P SV R , and using the ANOVA kernel of degree p: K = S⊆N,|S|≤p K 0 S . As in the previous experiment, we generate, from the hidden utility function u, random training sets E of noisy overall evaluations of size 70. In Table 1, we compare the generalizing performances of SMKGAI and the one obtained with dense p-additive GAI models (p-GAI) over 20 simulations. The generalized performances are measured as the mean absolute errors (MAE), i.e. the average absolute differences between the normalized ground truth utility and the predicted utility over test sets of size 150. We also provide the computing times (sec.) for all the methods. We observe that SMKGAI, by capturing the interaction of size n, nearly divides by 10 the MAE compared to the p-additive models. This is achieved for a time that is only multiplied by 2 compared to the additive model (1-GAI Finally, we perform an experiment on synthetic data generated with more general models for n = 10. The models are randomly generated as sums of 10 tensor products of quadratic splines. In order to increase the complexity of the hidden models, the maximal size of the factors (max. size) is increased from 1 (additive utility) to 5. We perform 20 simulations and each time, we generate a set E of overall evaluations of size 140 perturbated with a Gaussian centered noise of standard error σ = 0.05. In Table 3 is represented the MAE on test sets of size 150 along with the maximal size of the learned factors and the False Discovery Rate (FDR), which is computed as the percentage of selected factors in the learned ANOVA decomposition that are not included in any of the factors of the hidden function. We consider that a factor S ⊆ N is selected as soon as the attached weight d S is higher than 0.01. As expected, we observe that the MAE increases as the interaction degree (max size) of the hidden model increases. However, our learning approach is able to capture these interactions since the maximal size of the learned factors increases similarly to the ground truth, with a percentage of false inclusion (FDR) in the model that stays below 20%. 3: Model recovery assessment for growing interaction degree of the hidden models in average over 20 simulations.

Real-world Datasets

In this subsection, we test our method on real preference datasets. We use standard multi-criteria decision-making benchmarks containing overall evaluations of alternatives described by continuous or discrete attributes. We use Employee Selection (ESL) which contains profiles and overall psychological evaluations of job candidates, Lecture Evaluation (LEV), containing examples of anonymous lecturer evaluations and Employee Rejection/Acceptance (ERA) 1 , which contains the judgment of a decision-maker w.r.t candidate profiles. Then from the UCI repository, we use CPU and Car MPG (MPG) which respectively contain the performances of CPU and the fuel consumption of cars, along with attributes describing the objects. Finally, we use the Movehub city ranking2 (CITY) dataset which contains overall evaluations of cities quality. The number of evaluations |E| and the number of attributes n of each dataset is given in We compare SMKGAI to standard baselines from preference modeling such as the linear regression, the 2-additive Choquet Integral [START_REF] Grabisch | A decade of application of the choquet and sugeno integrals in multi-criteria decision aid[END_REF], and p-additive GAI (p-GAI) for p = 1 and p = 2. The attribute values are normalized using a linear max-min normalization. Each dataset is split to produce a training set containing 80% of the examples and a test set with the 20% left. For 20 random splits, we compute the MAE obtained on the test set for each method and present the averaged results in Table 2. For each dataset, the best result is displayed in bold and if there is another performance close to this result, it is also displayed in bold. We can see that SMKGAI is attached to the best average MAE or is very close to the optimal result, except on the dataset ESL where the linear regression and the additive utility (1-GAI) provide the best results. In particular, for the datasets LEV and ERA, SMKGAI outperforms the baseline methods, showing the presence of interactions between more than two attributes in the data. Also, for the datasets CPU, MPG and CITY, it seems that SMKGAI is able to adapt its complexity to the underlying data since it provides results similar to the additive utility (1-GAI) or 2-additive GAI (2-GAI) depending on the case.

Conclusion

We have presented a multiple kernel learning approach that constructs a sparse GAI model from evaluation examples to describe and explain the value system of a decision maker. The core of the approach relies on the determination of a sparse ANOVA decomposition of utilities obtained thanks to the use of zero integral kernels. This decomposition can be simplified afterward to produce a more compact and still well-formed GAI decomposable utility that well fits the available preference information. The advantage of the proposed approach is to be able to capture general interactions among continuous or discrete attributes without prior restrictions on the size of interacting factors. It makes it possible to fit model complexity to the available preference information. The regularization used in the objective function ensures that model complexity is kept as low as possible, given the descriptive constraints imposed by preference data. As far as we know, this is the first learning method able to learn both the structure of the GAI decomposition (by identification of the factors that really matter), and the utility functions defined on these factors, that can handle continuous attributes and that does not use prior restrictions on the cardinality of the interactions. Also, note that the same approach can be easily implemented to extract the utility function from pairwise preference/indifference examples.

In order to go further, some directions are worth investigating. In particular, for an interaction term f S present in the ANOVA decomposition, it is likely that the subterms f S ′ for S ′ ⊆ S also appear in the ANOVA decomposition. Thus, it could be of interest to implement a grouped hierarchical regularization [START_REF] Bach | Exploring large feature spaces with hierarchical multiple kernel learning[END_REF] that would simultaneously cancel f S and its sub terms f S ′ , S ′ ⊆ S, as suggested in [START_REF] Durrande | Anova kernels and rkhs of zero mean functions for model-based sensitivity analysis[END_REF]. Another direction is to enhance the scalability of the method w.r.t the number of attributes, since the number of possible factors grows exponentially. One path could be to bound from above the size of possible interacting factors. Another possible path is to use an iterative optimization procedure based on projected gradient descent that successively optimizes over the variables α + j , α - j and the weights d, as proposed in [START_REF] Rakotomamonjy | More efficiency in multiple kernel learning[END_REF].

Figure 1 :

 1 Figure 1: Learned and ground truth utility factors u 1 (top left), u 2 (top right), u 34 (bottom left) and u 45 (bottom right).

Table 1 :

 1 ). Comparisons of the generalizing performances (MAE) and training times over 20 simulations for the product model.

			SMKGAI	1-GAI		2-GAI	3-GAI	4-GAI
		MAE	0.0065 ± 0.0016 0.0381 ± 0.0088 0.0456 ± 0.0106 0.0560 ± 0.0129 0.0543 ± 0.0121
	Training time (sec.) 75.48 ± 6.78	34.89 ± 2.35	42.92 ± 3.35	58.01 ± 4.73	70.75 ± 7.06
	Dataset	Linear Regression	2-add Choquet Integral		1-GAI	2-GAI	SMKGAI
	ESL	0.08198 ± 0.00588	0.08488 ± 0.00498	0.08266 ± 0.00619	0.08426 ± 0.00725	0.08419 ± 0.00697
	LEV	0.23540 ± 0.00551	0.25417 ± 0.01449	0.23163 ± 0.01295	0.17093 ± 0.01212	0.12381 ± 0.02662
	ERA	0.24255 ± 0.00536	0.24256 ± 0.00698	0.20071 ± 0.01115	0.11817 ± 0.00932	0.04749 ± 0.00200
	CPU	0.02795 ± 0.00357	0.01792 ± 0.00654	0.00888 ± 0.00209	0.00796 ± 0.00475 0.00805 ± 0.00455
	MPG	0.06399 ± 0.00331	0.10113 ± 0.00557	0.05628 ± 0.01115	0.05355 ± 0.00656 0.05212 ± 0.00666
	CITY	0.06282 ± 0.00861	0.06707 ± 0.00768	0.04855 ± 0.00916	0.05127 ± 0.00899	0.05054 ± 0.00893

Table 2 :

 2 Mean absolute error (MAE) averaged over 20 random splits for SMKGAI and baseline methods.

Table 4 .

 4

	Dataset ESL LEV ERA CPU MPG CITY
	n	4	4	4	6	7	5
	|E|	488 1000 1000 209	392	216

Table 4 :

 4 Datasets' number of attributes n and examples E.

www.openml.org (ESL, LEV and ERA)

www.kaggle.com/datasets/blitzr/movehub-city-rankings

Acknowledgments

This work is supported by the ANR project ANR-20-CE23-0018 THEMIS of the French National Research Agency.