Learning Community-Based Preferences via Dirichlet Process Mixtures of Gaussian Processes

1 Introduction

Preference learning has become an important subfield in machine learning transcending multiple disciplines such as economics, operations research and social sciences. A wide range of applications in areas such as recommender systems, autonomous agents, human-computer interaction and e-commerce has motivated machine learning researchers to investigate flexible and effective ways to construct predictive preference models from preference observations [F¨urnkranz and H¨ullermeier, 2010].

This is a challenging problem since complex relations between users and their preferred items must be uncovered. Furthermore, flexible and principled ways to handle uncertainty over the users' preferences are required in order to balance what the system knows. To address these challenges, nonparametric Bayesian approaches based on Gaussian processes

(GPs) [Rasmussen and Williams, 2006] have shown to be effective in real applications [Chu and Ghahramani, 2005a; Bonilla et al., 2010; Platt et al., 2002; Xu et al., 2010]. However, one of the major limitations of preference learning approaches based on GPs is their cubic time complexity in both the number of users and items.

While the number of items in many preference prediction applications may be computationally manageable in a GP framework, the number of users may be much larger and often poses the greatest computational challenge. Fortunately, it is well-known that preferences across a user population often decompose into a smaller number of communities of commonly shared preferences [Postlewaite, 2011].

To exploit community structure in preferences, we propose a novel mixture model of GP-based preference learning. While we might first take a finite mixture model approach to modeling community-based preferences, we note that one of the most difficult parts of modeling communities is determining their number. Fortunately, we can exploit the Dirichlet Process [M¨uller and Quintana, 2004] framework to build infinite mixture models where the number of mixture components (communities) is inferred automatically. Hence, we model user preferences as an infinite Dirichlet Process (DP) mixture of communities and learn (a) the expected number of preference communities represented in the data, (b) a GPbased preference model over items within each community, and (c) the mixture weights representing each user's fraction of community membership. This results in a learning and inference process that scales linearly in the number of users rather than cubicly and as a side benefit provides the ability to analyze individual communities of preference while also learning how user preferences align with each community and each other.

We evaluate our approach on a variety of data including human preference data collected from Amazon Mechanical Turk showing that our method is more scalable than previous GP-based preference learning and as accurate since it is able to uncover latent shared-preference community structure present in our data.

2 GP-based Preference Learning

In this section, we briefly review the multi-user Gaussian Process based framework for Bayesian preference learning originally proposed by [Bonilla et al., 2010] before modifying it to a Dirichlet Process mixture in Section 3.

Let U = {u1, u2, . . . , un} be a set of n users and let X = {x1, x2, . . . , xm} be a set of m items and denote the set of observed preferences of each user u ∈ U with Du = {xi ≻ xj} where 1 ≤ i ≤ m and 1 ≤ j ≤ m. Given the preferences Du for u, satisfaction of the von NeumannMorgenstern axioms [Neumann and Morgenstern, 1944] justify the existence of utilities f u i ∈ R for each item xi ∈ X s.t. xui ≻ xuj ∈ Du iff f u i > f u j . In order to model the distribution over these utilities, we denote a latent utility vector f for all users and items with f = [f u1 1 , f u1 2 , . . . , f un m ]T . Then, we can define the likelihood over all the preferences given the latent functions as:

where Φ(x) = ∫ x -∞ N(y)dy and N(y) is a zero-mean Gaussian distribution with unit variance and α ∈ R is the discriminal dispersion hyperparameter (indicating how strongly users discriminate differences of utility) as specified in Thurstone's model of comparative judgment [Thurstone, 1959].

In this model, p(f|K) is the prior over the latent utilities f and is defined via a GP with zero-mean function and a covariance matrix K that factorizes over users and items [Bonilla et al., 2010]. Therefore:

where K is a kernel matrix composed of the Kronecker product of the kernel matrix over the users Ku and the kernel matrix over the items Kx. One interesting feature of this model is the inherent transfer of preferences across users through the correlated prior (which can be learned through hyperparameter optimization of K), intended to help the prediction generalize to users u for which few preferences are recorded in Du.

The posterior of the latent utility function f for each user and item given all the preferences is:

with Z being the normalizer. This posterior is analytically intractable due to the non-Gaussian nature of the likelihood, requiring approximation as detailed in [Bonilla et al., 2010]. What is simply critical to note for the purposes of this paper is that prediction with this Gaussian Process model requires a matrix inversion of dimensions equivalent to K (i.e., mn), thus having O(m3n3 ) time complexity. In the next section we seek to mitigate this computational complexity while at the same time exploiting community structure often present in social preference data [Postlewaite, 2011].

3 Dirichlet Process Mixtures of Community-based Preference GPs

In this section we propose to alter the GP preference based model of Section 2 to model users as a (potentially) infinite mixture of GP-based communities. Hence, we now assume there are an infinite number of possible communities of preference C = {1 . . . ∞} where for every user u there is a latent indicator cu ∈ C indicating to which community u belongs. Further, we assume each community c ∈ C has it's own latent utility function over items only fc = [f c 1 , f c 2 , . . . , f cm]T since we assume all members of the community share common preferences. Hence, we can now define a likelihood in this model for the preference data conditioned on all latent utilities f = [f1, . . . , f∞] (where we have redefined f from the previous section) and the vector of latent community indicators for each user c = [cu1 , . . . , cun ]T :

with p(xi ≻ xj|f cu i , f cu j , α) as defined in the previous section and a community-specific kernel prior Kcx for each fc (c ∈ C) over items only.

It is important to emphasize here that one important feature of our infinite community-based mixture model is that the hyper-parameters Kcx of the utilities fc are communitydependent and can be optimized as part of the learning process as described in Section 3.3 leading to improved community modeling and generalization over all item preferences within that community.

We assume that c is generated according to an infinite multinomial distribution with parameters π ∈ R|C| (∑|C| i=1 πi = 1), hence

Since the number of possible communities |C| is infinite, we resort to Dirichlet processes by defining an infinite Dirichlet prior on the community distribution with concentration parameter λ [Neal, 1998; Rasmussen, 2000]:

Altogether this generative framework is represented in the graphical model of Figure 1.

Our primary goal in inference is to obtain a sample posterior estimate over f and c to be used for future prediction. To this end, we begin by multiplying all of the likelihood and prior factors of our generative model in Figure 1 to obtain a superset of the desired joint posterior parameters:

Here of course, we don't necessarily require a posterior estimate over π and we will see in Section 3.1 that it is in fact important to marginalize over π in the posterior to facilitate Gibbs sampling inference for Dirichlet processes.

However, before we dive into specific details, we first provide a general overview of our posterior inference framework. To perform inference in this Dirichlet Process mixture of GPs, we utilize the joint probability in Equation 9 and devise a collapsed, blocked Gibbs sampler that breaks the Gibbs sampling inference into two distinct steps, for which different inference algorithms are appropriate. Specifically, collapsing comes from marginalizing over π and blocking stems from repeating joint inference of f given c followed by Gibbs sampling of each cu given f and c\u until convergence:

• Infer p(cu|c\u, f,D, λ, α,K) via Gibbs sampling as discussed in Section 3.1.
• Infer p(f|c,D, λ, α,K) via Expectation Propagation (EP) as discussed in Section 3.2 with hyperparameters optimized as discussed in Section 3.3.

Here we have merged all kernel hyperparameters into the set K = {Kcx |c ∈ C}.

3.1 Inferring CommunityMembership

In our Gibbs sampler, given f , we now wish to sample c - the community memberships for all users. Assuming that our blocked Gibbs sampler has already provided us with a sample of f for some fixed c∗ sampled on the previous iteration, we now wish to sample each new cu in turn for the current iteration provided that we can define p(cu|c\u, f , D, λ, α).

While we could sample f from p(f|c∗ ,D, λ, α) to compute p(cu|c\u, f,D, λ, α), this seems inefficient given that we can derive the full posterior p(f|c∗ ,D, λ, α) in closed-form given our Gaussian Process inference machinery in Section 3.2. So instead we propose to compute

Now we derive an efficiently computable closed-form for sampling cu where we abbreviate the previous expectation to the shorter form Ef |c∗ [p(c|f , D, λ, α)]: 2

Thus in (10) we arrive at a closed-form computation that is straightforward to compute. In the square brackets, we need only use our GP posterior f|c∗ to compute the product of the probabilities of each of user u's preferences xi ≻ xj ∈ Du as defined in the next sections. This leaves us only to compute p(cu = c|c\u, λ) as is standard in Gibbs sampling for Dirichlet processes:

where N is the number of non-empty communities.

1. Else c is a new community so

Hence all quantities required to sample cu have now been defined permitting sampling of each cu in turn to complete the community process sampling portion of the Gibbs sampling inference for our model. And the result is intuitive: a user u is more likely to join a community which provides a higher likelihood on its preference data Du. Additionally, this sampling process displays the well-known "rich-get-richer" effect of Dirichlet Processes since communities with more members have a higher probability of being selected.

3.2 Inferring Community Utility

Once we have sampled the block of all user assignments c, it is now time to sample the block of Gaussian Process latent utilities f for each active community given c. Thus, we first derive our target conditional distribution:

As seen in Equation 1, since the likelihood is factorized we can take advantage of sequential approximation methods such as Expectation Propagation (EP) [Minka, 2001].

1 Of course, one can always sample f and avoid this expectation if preferred, but we conjecture that using the expectation will induce a lower-variance Gibbs sampling process with faster convergence.

2 A detailed derivation of all math derived in these sections is provided in an online appendix at the authors' web pages.

EP approximates the posterior p(f |c, D, λ,K) by a tractable distribution q(f|c). EP assumes that each likelihood term p(xi ≻ xj|f cu i , f cu j , α) can be approximated by a distribution q(f cu i , f cu j |θcu ) such that the approximated posterior q(f|c) factorizes over q(f cu i , f cu j |θcu ). Then EP iteratively approximates each q(f u i , f u j |cu) in turn by dividing it out from the approximated posterior q(f|c) (obtaining the cavity distribution), multiplying in the true likelihood p(xi ≻ xj|f cu i , f cu j , α), and projecting the result back to its factorized form by matching its moments to an updated q(f cu i , f cu j |θcu ).

This overall procedure is motivated by the aim to minimize the KL-divergence between the true posterior p(f |D, c, α, K) and its approximation q(f |c).

In the preference learning case we detailed earlier, we can approximate the posterior with a Gaussian:

where μc and Σc denote the mean and covariance of the Gaussian distribution for the community user u belongs to corresponding to θcu . We are interested in locally approximating each likelihood term in Equation 1 as:

where N(f u i , f u j ; ˜ μc u,[i,j], ˜ Σc u,[i,j]) denotes the local twodimensional Gaussian over [f u i , f u j ]⊤ withmean ˜ μc u,[i,j] and covariance ˜ Σc u,[i,j] corresponding to items i and j. Full details are provided in an online appendix. 2

3.3 Optimizing Kernel Hyper-parameters

One advantage of our model is that the hyper-parameters of the model can be learned independently for each community. Even though we can define distributions over covariance (Inverse-Wishart), here due to the computational cost of a full Bayesian update of K we instead optimize the hyperparameters by maximizing the marginal likelihood in a gradient descent algorithm. The marginal likelihood can be obtained from the normalizer ˜ Z c in Equation 14 as:

where both p(fc|θc) and q(f u i , f u j |cu) are Gaussian distributions and their product produces an unnormalized Gaussian distribution. Therefore, the log likelihood is:

The derivative of the marginal likelihood with respect to the kernel hyper-parameters can be used in a gradient descent algorithm to optimize the kernel.

3.4 Prediction

Given a pair of items x∗1 , x∗2 for a particular user, we will be able to determine the predictive distribution over the latent utility functions as:

where Σ∗ is the 2 × 2 kernel matrix built from the item pair x∗1 and x∗2 ; K∗ represents the kernel matrix of test items with all the items in the training set; K∗c is the kernel matrix of the queried user with other users in the same community; and K∗x is the 2×m kernel matrix of the queried pair of items with other items. Subsequently, their preference for a user is determined by integrating out the latent utility functions we have p(x∗1 ≻ x∗2 |D, α, K) equals:

We see that the mean and covariance of the predictive distribution require the inversion of a much smaller matrix leading to O(n3 ) time complexity compared to the case where the community of the users is not considered in Section 2 which has O(n3m3 ) time complexity.

Algorithm 1 Blocked Gibbs Sampling Routine

input: X, U, D, λ, α Initialize c to arbitrary assignments for each user while not converged do // Infer community utilities and hyperparameters for c ∈ C do 1. Obtain Kc from Eq. 17. 2. Perform EP to infer p(f |c, D, α, K) (Sec 3.2). end for // Sample community membership assignments for u ∈ U do 3. Sample cu from Eq. 10. end for end while

3.5 Final Algorithm

Having found the communities and users' utilities, the algorithm for community-based preference learning is presented in Algorithm 1. After initializing with class assignments for each user, hyperparameters for each community GP are optimized followed by inference of f and then c, which repeats until convergence.

4 Empirical Evaluation

In this section we empirically evaluate the performance of our algorithm to determine (1) how well the DP mixture of GPs is capable of reducing prediction time vs. Full-GP defined in Section 2, (2) how well the DP mixture of GPs works in accurately learning the preferences of each user compared to Full-GP, (3) whether each community learned has a distinct set of preferences, and (4) how effectively the true number of communities in data is recovered. We perform our evaluation on three datasets: one synthetic and two real-world datasets. The synthetic experiment assesses the effectiveness of our approach in a controlled setting and the real-world datasets include the data obtained from preferences over cars that we have created using Amazon Mechanical Turk as well as a publicly available sushi preference dataset.

It is assumed that we are given a set of users and items with their corresponding features. For each user and item we also augment their features with their ID index, that is, a vector that is only one for that particular user or item (this is a common practice in collaborative filtering). The pairwise item preferences of each user are split into two sets for performing the inference (60%), and testing (40%) where the algorithm performance is evaluated. We use the squared exponential covariance with automatic relevance determination (ARD) for both users and items. We manually tuned λ and α (for Full-GP as well).

Synthetic Dataset: We generated a hypothetical set of 60 users and 10 items and assigned each user to one of four communities. We randomly assigned each item to be liked by one of the communities (high utility) and disliked by the other three communities (low utility). From these communities and their associated utility functions, we generate the preferences of each user (without noise to make a pure synthetic test data set). Our approach is able to converge to exactly four communities with the correct memberships (as shown in Figure 3), demonstrating that our algorithm is effective in recovering latent community structure present in data. As observed in Table 1, the accuracy and the time consumed by the proposed approach is also improved compared to Full-GP.

Sushi Dataset: Here we describe the results on the sushi dataset [Kamishima, 2003]. It is a dataset of preferences of people about 10 types of sushis which leads to 45 preferences (pairs of sushis) per user. Each user and item (sushi) is specified by a set of features and where we have categorical features, they are converted to binary ones. Moreover, similar to the collaborative filtering setting, we included the IDs of the users and items as well. We discovered 8 communities in this dataset (as shown in Figure 3 while performing as accurately as Full-GP with two orders of magnitude less running time as shown in Table 1.

Car Preference Dataset using Amazon Mechanical Turk 3 : Amazon Mechanical Turk 4 (AMT) provides an excellent crowdsourcing opportunity for performing online experiments and user studies. Since the number of publicly available preference learning datasets are limited, we set up an experiment in AMT to collect real pair-wise preferences over users. In this experiment users are presented with a choice to prefer a car over another based on their attributes. The car attributes used are:

• Body type: Sedan, SUV
• Engine capacity: 2.5L, 3.5L, 4.5L, etc.
• Transmission: Manual, Automatic
• Fuel consumed: Hybrid, Non-Hybrid

The set is then split into two sets with 60% of all the preferences kept for inference and the rest for testing. The dataset is collected so that 10 unique cars (items) are considered and users are required to answer all 45 possible pair-wise preferences. We targeted US users mainly to have a localized and consequently more meaningful preference dataset. For each user, a set of attributes in terms of general questions (age range, education level, residential region and gender) is collected. Every categorical attribute is converted to binary ones. We collected these preferences from 60 unique users.

As observed in Table 1, the proposed approach is as accurate and faster than Full-GP. Through learning the communities, we can also analyze the most frequently chosen attributes selected by a community as shown in Table 2, where inference converged to 7 communities.

5 RelatedWork

Probabilistic models for utility functions in preference learning and elicitation have previously been proposed in the machine learning community [Chajewska and Koller, 2000; Guo and Sanner, 2010]. Extensions to non-parametric models have also been developed. In particular, [Chu and Ghahramani, 2005b] proposed a preference learning framework based on Gaussian processes and [Eric et al., 2008] used this model for active learning with discrete choice data. Multiuser GP-based preference models have been given by [Birlutiu et al., 2010] and [Bonilla et al., 2010]. However, none of these methods directly address the efficiency problem nor discovered any community structure.

3 http://users.cecs.anu.edu.au/ ∼u4940058/CarPreferences.html

4 http://mturk.com

Stochastic blocked models [Nowicki and Snijders, 2001; Airoldi et al., 2008] are another class of related approaches that model the dependencies between users and infer the graphical structure under which users interact. Such models implicitly find the communities users belong to, even though not directly applied to preference learning in the setting we discussed here.

Furthermore, [Rasmussen and Ghahramani, 2002] proposed the infinite mixture of Gaussian processes for regression and later extended in [Meeds and Osindero, 2005] that is similar to the mixture of Gaussian processes detailed here. Our work however further extends the mixture of GPs to social preference learning.

6 Conclusion

We exploited the observation that user populations often decompose into communities of shared preferences and modeled user preferences as an infinite Dirichlet Process (DP) mixture of communities. The resulting inference algorithm scales linearly in the number of users unlike previous Gaussian Process preference learning approaches that scaled cubicly in the number of users. We evaluated our approach on a variety of preference data sources including Amazon Mechanical Turk showing that our method is more scalable and as accurate as previous work with only a small number of inferred communities, validating our community-based modeling approach.

For future work, we note that the differing levels of similarity between communities observed in Figure 2 and Table 2 suggest that a hierarchical non-parametric Bayesian approach may be useful for directly modeling the differing relationships between communities.

Acknowledgements

NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council through the ICT Centre of Excellence program.