Fast Recommendations using GAI Models

1 Introduction

Current works in preference modeling and algorithmic decision theory aim at developing compact preference models achieving a good compromise between descriptive and prescriptive objectives. On the one hand, they aim at proposing new sophisticated models able to capture the diversity of observed decision making behaviors. On the other hand, the models are kept as simple as possible to preserve efficiency both in elicitation and recommendation tasks. This very active flow of research is motivated by the increasing need of decision support systems on the web, to help users in making decisions among a combinatorial sets of possibilities.

In this context, extensive representation of preferences is not feasible and decision procedures cannot resort to exhaustive enumerations of options due to the large size of the domains to be explored. In this paper we consider such situations where the set of items on which recommendations must be done is all or part of a product set of attributes the size of which is huge. Current works on this matter include advances on qualitative preference models (CP-nets [Boutilier et al., 2004a; 2004b; Brafman et al., 2006]). These are naturally suited to applications in which preferences can easily be approximated by almost lexicographic rules on attributes with small domains (e.g. recommender systems to buy books on the web). However, as observed in [Boutilier et al., 2001], when a deeper preference investigation is possible, quantitative representations such as utilities can significantly outperform qualitative models due to their higher descriptive power.

In the literature, different quantitative models based on utilities have been developed to take into account different preference structures. The most popular assumes a special kind of independence among attributes called "mutual preferential independence". It ensures that preferences are representable by an additive utility [Krantz et al., 1971; Bacchus and Grove, 1995]. Such decomposability makes both the elicitation process and the query optimizations very fast and simple. However, in practice, it may fail to hold as it rules out any interaction among attributes. Generalizations have thus been proposed in the literature to increase the descriptive power of additive utilities. Among them, multilinear utilities [Keeney and Raiffa, 1993] and GAI (generalized additive independence) decompositions [Braziunas and Boutilier, 2005; Gonzales and Perny, 2004; Bacchus and Grove, 1995] allow quite general interactions between attributes while preserving some decomposability. The latter has been used to endow CP-nets with utilities (UCP-nets) [Boutilier et al., 2001; Brafman et al., 2004].

Studies on GAI utilities have been mainly devoted to their elicitation [Braziunas and Boutilier, 2005; 2007; Gonzales and Perny, 2004; 2005], efficient algorithms for answering queries being similar to those used in the Bayes net or junction tree community [Jensen et al., 1990; Madsen and Jensen, 1999]. However, queries of interest in GAI-based recommender systems are very special: generally, they consist in finding the element most preferred by the user (choice problem), or a list of the top k elements (ranking problem). The specificities of these queries are not taken into account by the general junction tree-based methods mentioned above. This paper proposes a new algorithm that takes advantage of these particularities, thus significantly increasing the efficiency of the junction tree-based algorithms. This proves to be particularly useful when dealing, e.g., with recommendation tasks under constraints and collective Decision-Making, where GAI nets tend to have a substantial size.

More precisely, Section 2 recalls the basics of GAI utilities and their graphical counterparts, the so-called GAI networks. It also briefly recalls how recommendation tasks can be performed using these networks. Section 3 shows how these computations can be significantly sped up by solving a special ranking task within a secondary sparse GAI structure. Section 4 presents benchmarks that illustrate the practical efficiency of our method. Finally, the last section concludes the paper and suggests some perspectives for future research.

2 GAI-Networks Fundamentals

Throughout the paper, ≿ denotes a decision maker's (DM) preference relation (a weak order over some set X). x ≿ y means that x is at least as good as y. ≻ refers to the asymmetric part of ≿ and ∼ to the symmetric one. In practice, X is often described by a set of attributes. For simplicity, we assume that X is the product set of these attributes domains ∏ni=1 Xi. The combinatorial nature of X prevents any recommender system to perform an exhaustive search for determining the best element w.r.t. ≿ and the aim of this paper is to present an efficient procedure for its computation. Note that recommendations over subsets Y's of product set X can be dealt with simply by imposing that elements y ∈ Y have low preference levels. In the sequel, bold letters represent sets of attributes indices, uppercase letters such as A, X1, denote attributes and their domains (as this is unambiguous) and lowercase letters denote their values: x, x1 (resp. xi, x1i ) are thus values of X (resp. Xi). For any set Y ⊆ {1, . . . , n}, xY refers to the projection of x ∈ X on ∏i∈Y Xi.

2.1 GAI-Networks' Definition

Under mild hypotheses [Debreu, 1964], ≿ is representable by a utility u : X ↦→ R such that x ≿ y ⇔ u(x) ≥ u(y) for all x, y ∈ X . However, in general, such a function is impractical because: i) as preferences are specific to each individual, utilities must be elicited for each DM, which is impossible due to the combinatorial nature of X; and ii) in recommendation systems with multiple users, storing explicitly for each user the utility of every x∈X is too prohibitive. Fortunately, DM's preferences usually have a structure induced by independencies among attributes that substantially decreases the elicitation burden and the memory needed to store preferences, thus making the model usable in practice. The simplest case is obtained when preferences are represented by an additive utility u(x) = ∑ni=1 ui(xi) for any x = (x1, ..., xn) ∈ X [Wakker, 1989; Keeney and Raiffa, 1993]. This model only requires to elicit and store ui(xi) for all xi ∈ Xi, i = 1, . . . , n. However, such a decomposition is not always convenient because it rules out any interaction between attributes. When DM's preferences are more complex, a more elaborate model is needed as shown next:

if nextchar[

Example 1 Consider a recommender system for train tickets where the set X of possible configurations for a train ticket is described by three attributes: class x1 ∈ X1 = {first class (c11 ), second class (c21 )}; type of car x2 ∈ X2 = {smoking (s2), smoking-free (¯ s2)}; and pricing period x3 ∈ X3 = {discount period (d3), normal period (n3)}. Suppose that an individual's preferences are as follows:

1. I prefer a smoking-free train car to a smoking one;
2. I prefer to travel in first class during the discount period and in second class during the normal period;
3. Given the option between a second class smoking train car and a first class smoking-free one, I prefer the latter.

These statements are assumed to be ceteris paribus, i.e. all else being equal. Such preferences are not representable by a fully additively decomposable utility because (c11 , s2, d3) ≻ (c21 , s2, d3) ⇒ u1(c11 ) > u1(c21 ) whereas (c21 , s2, n3) ≻ (c11 , s2, n3) ⇒ u1(c21 ) > u1(c11 ). Actually, the additive decomposition is ruled out by the interactions between attributes X1 and X3 (rule 2). However the DM's preferences can be represented by a decomposable utility of the form: u(x) = u1,2(x1, x2) + u1,3(x1, x3), setting for instance:

Note that CP-nets are also unable to represent compactly these preferences due to rule 3. ■

Such a decomposition over overlapping factors is called a GAI decomposition [Bacchus and Grove, 1995]. It includes additive and multilinear decompositions as special cases. It is also very flexible since it does not make any assumption on the kind of interactions between attributes. GAI decompositions can be defined more formally as follows:

Definition 1 (GAI decomposition) Let X = ∏ni=1 Xi. Let Z1, . . . ,Zr be some subsets of N = {1, . . . , n} such that N = ∪ri=1Zi. For every i, let XZi = ∏j∈Zi Xj . Utility u(·) representing ≿ is GAI-decomposable w.r.t. the XZi 's iff there exist functions ui : XZi ↦→R such that:

GAI decompositions can be represented by graphical structures called GAI networks [Gonzales and Perny, 2004] which are essentially similar to the junction graphs used for Bayesian networks [Jensen, 1996; Cowell et al., 1999]:

Definition 2 (GAI network) Let X = ∏ni=1 Xi. Let Z1, . . . ,Zr be some subsets of N = {1, . . . , n} such that ⋃ri=1 Zi = N. Assume that ≿ is representable by a GAI utility u(x) = ∑ri=1 ui(xZi ) for all x ∈ X. Then a GAI network representing u(·) is an undirected graph G = (V, E), satisfying the following two properties:

1. V = {XZ1 , . . . ,XZr };
2. For every (XZi ,XZj ) ∈ E, Zi ∩ Zj ̸= ∅. For every pair of nodes XZi ,XZj such that Zi ∩ Zj = Tij ̸= ∅, there exists a path in G linking XZi and XZj such that all of its nodes contain all the indices of Tij (Running intersection property).

Nodes of V are called cliques. Every edge (XZi ,XZj ) ∈ E is labeled by XTij = XZi∩Zj and is called a separator.

Cliques are drawn as ellipses and separators as rectangles. In this paper, we shall only be interested in GAI trees. As mentioned in [Gonzales and Perny, 2004], this is not restrictive as general GAI networks can always be compiled into GAI trees. For any GAI decomposition, by Definition 2, the cliques of the GAI network should be the sets of variables of the subutilities. For instance, if u(a, b, c, d, e, f, g, h) = u1(a, b, c)+u2(a, g)+u3(b, d)+u4(b, f )+u5(d, e)+u6(d, h) then the cliques are: ABC, AG, BD, BF , DE and DH (see Fig. 1). By Property 2 of Definition 2, the set of edges of a GAI network can be determined by any algorithm preserving the running intersection property (see the Bayesian network literature on this matter [Cowell et al., 1999]). Within the GAI net, subutilities are stored into their respective clique.

2.2 Basic Procedures for Choice and Ranking

Finding the optimal choice for the GAI net of Figure 1 is equivalent to solving:

This can be computed by eliminating variables one by one using absorption defined below, that is, by maximizing locally within a clique the subutility stored into it and, then, sending the result to its neighbors.

Definition 3 (Absorption of clique XCj by XCi ) Let Sij = Ci ∩ Cj and Dj = Cj\Sij. Assume that XCi and XCj contain respectively utilities ui and uj. Let vij(xSij ) = maxxDj ∈XDj uj(xSij , xDj ) for all xSij ∈XSij . Clique XCi is said to absorb XCj if ui is substituted by u′i = ui + vij.

Function Collect(clique XCi )

• 01 for all cliques XCj adjacent to XCi except, if any, that which called Collect (XCi ) do

After calling Collect on any clique XCi , the max of the subutility stored into XCi clearly corresponds to the value of the overall utility for the optimal choice. Now, there just remains to propagate back Argmax's to get the latter.

Definition 4 (Propagation of xCi into clique XCj ) Let Sij = Ci ∩ Cj and Dj = Cj\Sij. Let xCi ∈ XCi . Assume that XCj contains utilitiy uj. xCj propagates xCi to XCj if xCj = (xSij , ArgmaxxDj ∈XDj uj (xSij , xDj )).

Function Instantiate(clique XCi )

• 01 if Instantiate (XCi ) was called from clique XCj
• 02 then Propagate the argmax's value of XCj to XCi
• 03 else let xCi be the argmax of the subutility of XCi
• 04 for all cliques XCj adjacent to XCi except, if any, that which called Instantiate (XCi ) do call Instantiate (XCj )

Function Optimal choice(GAI-net)

• 01 Let XC0 be any clique in the GAI-net
• 02 call Collect (XC0 ) and, then, Instantiate (XC0 )
• 03 x∗ ← the tuple of the argmax's computed by Instantiate 04 return the optimal choice x∗

As suggested by [Nilsson, 1998] for finding the k most probable configurations in Bayes nets, determining the k-best elements in a GAI net can be performed by slightly modifying Instantiate. First, compute the optimal choice x∗ . The next best element differs from x∗ by at least the values of the attributes of one clique. Assume that this clique is XC0 , then calling Instantiate (XC0 ) and preventing x∗C0 to be chosen leads to the element we look for. Else if it is a neighbor XCi of XC0 , then the element we look for can be found by calling Instantiate (XCi ) and i) imposing xCi∩C0 to be equal to x∗Ci∩C0 , and ii) preventing calls to Instantiate (XC0 ). The same process can be applied for all the other cliques. As we do not know actually from which clique Instantiate should be called to get the element we look for, we call it from every clique and the second best element is, among all those returned by the calls to Instantiate, that which has the maximal utility value. Of course, the same scheme can be applied to get the third best element, and so on till the k-best element. A feature that is important for our algorithm is that all the heavy computations are performed during the Collect phase, Instantiate having no matrix manipulation to do. As a consequence, the latter is much faster than the former and, even for large k's, ranking the k-best elements is not much more time consuming than computing the optimal choice.

3 An Efficient Exact Choice Procedure

Of course, for "small" GAI nets, we cannot expect to speed up significantly the above ranking and choice procedures. However, when working on large GAI nets, as is often the case when hard constraints are added to the network 1 or when dealing with collective decision making, substantial benefits can be gained using the method described below. The key idea is to approximate the DM's GAI utility -call it u- by another GAI function -call it g- which is much more decomposable than the former (i.e., the cliques of its GAI tree are smaller than those of u's GAI tree), and which acts as an upper-bound on the DM's utility values. Being more decomposable, its GAI net is thus of smaller size and answering choice and ranking queries can be done quickly. Of course, as g is only an upper bound on u, the best element for g is certainly not that for u. However, we show that ranking enough elements with g, we can extract from these elements the best element for u. As ranking involves only one Collect phase followed by multiple Instantiate calls, which are very light in terms of time consumption, the ranking process with g significantly outperforms answering a choice query with u. As we shall see in the next section, this intuition is confirmed by our experiments.

1 Hard constraints can be encoded as additional utilities such that feasible tuples are assigned utility 0 and infeasible ones utility -∞.

3.1 Fast Exact Choice Using Upper-Bound g

Let u be a GAI function representing relation ≿ on X , and let g : X ↦→ R be a GAI function such that, for all x ∈ X, g(x) ≥ u(x). Assume that x1 , ..., xk are the k-best elements on X w.r.t. g. Compute ˆx = Argmaxi=1,...,k u(xi ). If u(ˆx) ≥ g(xk ), then ˆx is the optimal choice for u. Indeed, as we rank elements w.r.t. g, for any k′ > k, g(xk′ ) ≤ g(xk ), and since g(x) ≥ u(x) for all x ∈ X, u(xk′ ) ≤ g(xk′ ) ≤ g(xk ) ≤ u(ˆx). Consequently, the optimal choice for u can be obtained by ranking elements xi w.r.t. g until the maximum value of the u(xj )'s for all the xj 's found so far, exceeds the value of g(xi ). Recall that rankings are not much more time consuming than optimal choice computations. Hence, if the GAI net related to g is much smaller than that of u, its optimal choice computation is much faster, and the overall response time for g's ranking is much smaller than a direct choice computation using u. Now, the main problem is to find an efficient way for determining a "good" candidate for g.

3.2 Construction of Upper-Bound Function g

Let X = ∏ni=1 Xi and let Z1, . . . ,Zr be some subsets of N = {1, . . . , n} such that N = ∪ri=1Zi. Consider a GAI function u = ∑ri=1 ui, with ui : XZi ↦→ R. Without additional constraints on the ui's domains, it may happen that u's GAI net is not singly connected. For instance, if u(A,B,C,D) = u1(A,B) + u2(B,C) + u3(C,D) + u4(D, A), then the running intersection property requires that the GAI net contains a loop. But a GAI tree is needed to apply the preceding section. Hence, before computing optimal choice with u, the latter must be compiled into a GAI tree. This compilation process is similar that of junction trees for Bayes nets [Kjærulff, 1990; van den Eijkhof and Bodlaender, 2002]. First an undirected graph G = (V, E) is created with V = {X1, . . . ,Xn} and E = {(Xi,Xj) : there exists h such that {i, j} ⊆ Zh}. Next, G is triangulated by eliminating one by one the nodes of V. Each time a node, say Xi, is eliminated, edges (fill-ins) are added to G so that Xi's neighbors form a complete subgraph (a clique) and, then, Xi and its adjacent edges are removed from G. [Rose, 1970] guarantees that, whatever the elimination sequence, the cliques thus created can be linked to form a GAI tree. The compactness of the resulting GAI tree heavily depends on the sequence chosen. However finding the best sequence is out of the scope of this paper and the reader interested may refer for instance to [Kjærulff, 1990; van den Eijkhof and Bodlaender, 2002].

GAI cliques are thus created during the triangulation process. Clearly, the smaller the cliques the faster the choice and ranking procedures, the size of a clique being the product of the domain sizes of its attributes [Nilsson, 1998]. To determine a good upper bound function g, we should thus perform a triangulation that ensures that no clique is too large. Assume that, during the triangulation, nodes Xi1 , . . . ,Xip have already been eliminated and that we are currently eliminating Xip+1 . If the size of the new clique is above a given threshold, then we advocate removing some edges adjacent to Xip+1 in order to reduce the size of the clique. The resulting GAI tree will thus represent an approximation of u. When removing edges, care should nevertheless be taken in order to avoid the GAI network to contain loops: consider the triangulation of function u of the preceding paragraph. At the beginning, graph G is that of Fig.3.a. Eliminating A results in the creation of clique ABC and edge (B, C) (Fig. 3.b). Now, eliminating B creates clique BCD. But if BCD is too large, we may be willing to remove edge (B, C) to reduce its size. The resulting clique would be BD. Finally, removing C and D would create clique CD, thus resulting in the multiplyconnected graph of Fig. 3.d. The problem stems from the fact that (B,C) is compulsory for A and its neighbors to form a clique when A is eliminated. Hence, removing (B,C) requires that either B or C be no more a neighbor of A or, equivalently, that either edge (A,C) or (A,B) be removed as well. Of course, if A is not the first node eliminated, then removing edge (A,C) or (A,B) adds similar constraints on edges involved in previous node eliminations. Fortunately, all these constraints can be organized as a set of linear inequalities: assume we eliminate Xi and that Xj and Xk are neighbors of Xi; consider inequality eij + eik ≥ ejk, where eij, eik, ejk are Booleans equal to 1 iff their corresponding edge ((Xi,Xj), (Xi,Xk) or (Xj,Xk)) is removed. Then, obviously the edge linking Xi's neighbors, i.e., (Xj,Xk), can be removed only if either (Xi,Xj) or (Xi,Xk) is removed as well. Our system of inequalities is thus constructed incrementally each time a node elimination is performed, adding a new inequality for each pair of nodes adjacent to the one eliminated. Each time we wish to compel an edge removal, we just add to the system that the corresponding Boolean is equal to 1. Clearly, any solution of this system will lead to a triangulated graph and, consequently, to a GAI tree.

Of course, removing an edge from the triangulated graph has a cost: that of approximating the original function u by another function g. As a result, the more the discrepancy between u and g, the higher the number of elements required to be ranked with g. Hence, in addition to our system of inequalities, we should add a cost function measuring how far apart g is from u. Consider a subutility ui : XZi ↦→ R of u. In the GAI graph of u, XZi forms a clique. Assume we remove from this clique some edges, hence resulting in m smaller cliques XCj , each one representing a function, say gj : XCj ↦→ R. Then, ui is approximated by ∑mj=1 gj. In this paper, the discrepancy measure we chose between ui and ∑mj=1 gj is simply: ∑xZi ∈XZi | ∑mj=1 gj(xCj ) - ui(xZi )|. Hence we should find some functions gj's minimizing this measure while approximating ui from above. So we should solve the following linear program whose variables are the values of the gj(xCj )'s for all xCj ∈ XCj :

Usually, the original GAI subutilities ui's do not contain many attributes, so optimal gj's functions can be computed quickly as a preprocess for any subset of edges of cliques XZi 's. Now, when removing a given set of edges, the set of linear inequalities described in the preceding paragraph can be used to compute which additional edges need be removed to prevent loops in the resulting GAI graph and, using the gj's computed in (1), the discrepancy between u and g can be measured. This guides us in selecting, at each node elimination step, the right set of edges to be removed in order to minimize the discrepancy between u and g while preventing cliques sizes to be greater than a given value. Actually, this minimization problem can be completely specified as a linear program with Boolean variables.

3.3 Practical Determination of Function g

In practice, the above method involves solving many linear programs of type (1): one for each set of edges selected to be removed at each node elimination step. Fortunately, this process can be significantly sped-up by approximating the discrepancy measure. The objective function in (1) actually measures the gap between u and g for a given set S of removed edges. If we approximate this measure by the sum of the discrepancies induced separately by each edge in S, then it can be estimated using dynamic programming techniques. Consider a clique XZi of the original GAI function from which we have removed p edges (Xjt ,Xkt ), t ∈ {1, . . . , p}. Instead of using (1) as the discrepancy measure, for each removed edge (Xjt , Xkt ), compute the discrepancy measure in the case where only this edge is removed, i.e., djtkt = min{values of ht,ft} ∑xZi ∈XZi ht(xZi\{jt}) + ft(xZi\{kt})-ui(xZi ), where ht +ft approximates ui from above, and ht (resp. ft) is defined on clique XZi without node Xjt (resp Xkt ). We then estimate the discrepancy between u and its approximation g when all the p edges (Xjt ,Xkt )'s have been removed as ∑pt=1 djtkt . As such, to each edge of the graph being triangulated can be attached its djtkt value, computed once and for all. During triangulation, if the clique resulting from a node elimination is too large, the edges to be removed to reduce its size can thus be determined minimizing ∑ djkejk under the constraints of the type eij + eik ≥ ejk described above, where the ejk's are the Booleans indicating whether edge (Xj,Xk) is deleted. When djk is taken into account in this objective function to be minimized, ejk = 1, which implies that either eij = 1 or eik = 1. Hence, the resulting graph is triangulated. ∑ djkejk can be approximated from above using dynamic programming by defining:

Djk actually approximates from above ∑ djkejk as it selects between edges (Xi,Xj) and (Xi,Xk) that which seems, locally, to minimize the discrepancy between u and its approximation. The dynamic programming nature of Djk makes it computable incrementally very quickly during triangulation and avoids needing to solve any Boolean linear program. This is the very process we used in our experiments to determine the GAI tree of the upper-bound function g. It enables a fast computation of this tree and, as we shall see in the next section, its result significantly speeds up the computation of the most preferred element w.r.t. the original GAI utility.

4 Experimentations

To evaluate the performance of our method in practice, we chose to compare it with the basic GAI net' choice algorithm [Gonzales and Perny, 2005] as well as with an adaptation of Mini-Buckets Branch and Bound to GAI networks [Kask and Dechter, 1999]. We performed two different sets of experiments, the difference lying in the maximal number of attributes of product set X: for comparisons with the classical choice algorithm, X had up to 20 attributes whereas for comparisons with mini-buckets, it could contain up to 40 attributes (in this case, X could have up to 100 trillion elements). In each experiment, attributes' domain sizes have been chosen randomly between 3 and 5, and GAI subutilities ui's have been created randomly, with values drawn between 0 and 1000. Fig. 4 summarizes the results of 20000 choice experiments: the X-axis represents the sum of the sizes of the cliques in the GAI net (the size of a clique being the product of the domain sizes of its attributes), whereas the Y-axis represents the response times (in seconds) for solving the choice problem. Note that scales are logarithmic. As expected, when cliques' sizes are large, our algorithm clearly outperforms both the classical algorithm and Mini-Buckets B&B. Actually, experimentally, it tends to be exponentially faster than the classical algorithm. When cliques are small, i.e., their size is smaller than 107 , the resolution times of the linear programs used in our method cancel the gain induced by using g's network instead of that of u. Note that, even if the sizes of the subutilities representing the DM's preferences are small, the addition of subutilities representing hard constraints may result in GAI trees with large cliques.

5 Conclusion

We showed in this paper that approximating a GAI utility by an appropriate more decomposable function acting as an upper-bound significantly speeds-up the exact determination of optimal tuples. Besides this direct application, this technique will probably also open new possibilities in solving utility-based search problems under constraints. Indeed feasibility constraints can easily be incorporated in a GAI-utility maximization problem, under the form of additional GAI factors. Such factors model new dependencies that might induce, after triangulation of the Markov graph, a significant increase in the size of cliques, with a drastic impact on computation times. Similarly, in collective decision making on combinatorial domains, it might be useful to optimize a multiagent GAI utility function defined as the sum of individual GAI utilities. Since individuals may have different value systems, it may happen that the independence structure significantly varies from an individual to another, thus multiplying the GAI factors of the utility function. In both cases, the possibility of approximating the utility function so as to add artificial decompositions of cliques will significantly speed-up resolution times without departing from optimality, and will increase the size of the problems solved.

For future research, different approximating schemes seem quite promising. In particular, alternative criteria for deciding whether a clique need be approximated should further enhance the efficiency of our approach.