Metadata-dependent Infinite Poisson Factorization for Efficiently Modelling Sparse and Large Matrices in Recommendation

1 Introduction

Recommender Systems (RSs) estimate ratings that users may give to corresponding items. One of the most popular classes of RSs is Collaborative Filtering (CF), by which ratings are estimated based on user's past behaviors and similar decisions made by other users. Based on such simple but effective intuition, CF-based recommender systems appear in many business systems e.g., Amazon. However, CF together with its central technique, Matrix Factorization (MF) [Koren et al., 2009], faces many real-life challenges. First, it is not efficient to handle very large data, e.g., the Netflix data with millions of ratings, since classic MF requires intensive mathematical computation as discussed in [Mnih and Salakhutdinov, 2008; Gopalan et al., 2015]. Second, real-life data is often very sparse, e.g., the Netflix data has 98.8% of the matrix entries missing; MF models fail to find the similar users since their way of computing similarities assumes that two users have rated at least some items in common. Lastly, choosing the suitable number of latent components (i.e., K) for large datasets in MF is a very expensive process as it requires testing many models.

To address the first MF weakness, Probabilistic-based MF models such as PMF [Mnih and Salakhutdinov, 2008] were proposed to handle large datasets. The underlying assumption of such models is that ratings are supposed to follow a specific distribution. However, they are still inefficient especially for sparse data, since they perform the computation on all data which usually consists of many missing (i.e., zero) ratings. The work on Poisson Factorization (PF) [Canny, 2004; Dunson and Herring, 2005; Gopalan et al., 2015; Basbug and Engelhardt, 2016] shows that taking Poisson (with Gamma conjugate priors) as a distribution for non-missing values in sparse matrices leads to many advantages such as capturing non-negative values or only iterating over non-missing values. PF can partly address the second MF weakness on sparse data by ignoring the missing data in computation. Although computation only on non-missing data makes PF extremely fast for large and sparse datasets, it is inefficient when working with a column or row with very few observations (corresponding to a sparse item or user) due to poor priors.

Building on the non-IID recommender system view [Cao, 2016] and metadata-based coupling learning for MF models [Cao, 2015; Li et al., 2015], this work introduces user and item metadata into PF and assume they follow the Gamma distribution as the priors of PF. A novel model: Metadatadependent Poisson Factorization (MPF) is proposed to capture the couplings between user/item metadata and incorporate them into PF to capture both explicit and implicit relations in RS.

Further, to solve the third MF weakness, the BNP technique [Teh and Jordan, 2010] is integrated into MPF to form Metadata-dependent Infinite Poisson Factorization (MIPF). BNP allows for complex models to be learned without requiring much parameter tuning at the beginning. Consequently, we do not have to choose the number of latent components K in advance. MIPF automatically determines the number of latent components with an efficient variational inference [Jordan et al., 1999] method to find the posterior.

Hence, our models make the following contributions.

• First, to the best of our knowledge, MPF is the first PF model that integrates user/item metadata into PF. MPF inherits the PF strength of modelling large and sparse datasets but provides richer priors for PF. Compared to other PF models, MPF shows its efficiency when dealing with the columns or rows with very few observations (i.e., sparse items or users).
• Further, the proposed MIPF is the first PF-based model that not only integrates the metadata but also can automatically choose the number of latent components.

Extensive experiments show that MPF outperforms the state-of-the-art models in the PF family for large datasets with sparse users/items; and MIPF retains the good performance as its finite version MPF while MPF has to fit many models before finding the best number of latent components.

2 The MPF/MIPFModels

Here we introduce the MPF and MIPF design and details.

2.1 IntegratingMetadata into PF - The MPF Model

A recommendation problem usually consists of a rating matrix, and user and item information (called metadata here, e.g., the 'age', 'location' or 'career' of users and the 'genre' or 'year of release' of the movies in the Movielens dataset) [Cao, 2016]. Assume Y represents the rating matrix, in which each entry yui is the rating given by user u to item i, and an entry with 0 indicates no rating. HU and HI represent the user and itemmetadata respectively.

Poisson Factorization [Gopalan et al., 2015] assumes the rating matrix Y follows the Poisson distribution and can be factorized to a vector of K latent preferences for each user, θuk, and a vector of K latent features, βik, for each item, where θuk and βik follow the Gamma distribution.

Building on PF, we further assume the Gamma distribution of each user's latent behavior, ξu, and each item's latent attractiveness, ηi. This hierarchical structure of GammaGamma-Poisson allows us to capture the diversity of users and items. We capture the effects of user (item) metadata by defining the product of appearance of user (item) attribute's value in the metadata as the second parameter of Gamma distribution of user's latent behavior (item's latent attractiveness). We then apply the Gamma prior to the weight of each user attribute's value, hum, e.g., the 'New York' in 'location' attribute of a user, as in Eq. (1). The weight of user attribute hum only affects the behavior of a user ξu and further affects the preference similarity of users θuk if and only if fuu,m = 1, as in Eq. (3). hum measures the degree of influence of each user attribute. For example, user 'location' may have less influence than 'age' in Movielens. The weight of an item attribute hin (e.g., 'genre' of a movie) is also given a Gamma distribution as in Eq. (2). The weight of item attribute hin only affects the item's latent attractiveness ηi when item i has the attribute n (i.e., fii,n = 1).

The graphical model of MPF is shown in Figure 1a and the generative process of MPF is as follows.

(1) For the mth user attribute in the metadata, sample the weight:

(2) For the nth item attribute, sample the weight:

(3) For each user u, sample latent behavior:

(4) For each item i, sample latent attractiveness:

1. For each component k in the PF factorization:

(a) Sample user's latent preference:

(b) Sample item's latent feature:

(6) Sample rating:

2.2 Taking the Infinite - The MIPFModel

The MIPF model extends MPF to handle infinite components by BNP. In MIPF, the user's latent preference θuk is constructed through the stick-breaking proportion vuk, since stick-breaking process is efficient and widely used in many BNP models [Teh and Jordan, 2010; Liang et al., 2007; Kurihara et al., 2007; Gopalan et al., 2014a]. After obtaining the number of latent components for users through the stick-breaking process, the distribution for items is given as in MPF.

The graphical model of MIPF is shown in Figure 1b and its generative process is below.

(1) For the mth user attribute, sample the weight:

(2) For the nth item attribute, sample the weight:

(3) For each user u(= 1, . . . ,M):

(a) Draw the user's latent behavior:

(b) For k(= 1..∞), draw stick-breaking proportion:

(c) For k(= 1..∞), set the user's latent preference:

(4) For each item i(= 1...N):

(a) Draw the item's latent attractiveness:

(b) For k = (1...∞), set the item's latent feature:

(5) For u(= 1...M) and i(= 1...N), draw

3 Inference

Applying MPF/MIPF to recommender systems has to solve the posterior inference problem. For this, the mean-field variational inference (VI) is incorporated into our models as it is more efficient for large-scale probabilistic models [Wainwright et al., 2008] than other sampling approaches like Markov Chain Monte Carlo. With VI, we find the family of distributions over the hidden variables and the members of this family by tuning the parameters to minimize the Kullback-Leibler divergence to the true posterior.

3.1 Variational Inference for MPF

Given the rating table Y together with the user/itemmetadata HU and HI, we compute the posterior distributions of the weight of user attribute in metadata hum, the weight of item attribute in metadata hin, the latent user preference θuk, the item's latent feature βik, the user's latent behavior ξu, and the item's latent attractiveness ηi. Taking the same approach as in [Gopalan et al., 2015; Dunson and Herring, 2005; Zhou et al., 2012; Gopalan et al., 2014a], the rating yui is replaced with auxiliary latent variable zui,k ∼ Poisson(θukβik). Due to the additive property of Poisson distribution, the rating yui is expressed as follows:

Similar to [Gopalan et al., 2015], the inference only considers yui ̸= 0. The mean-field family assumes each distribution is independent of the others.

We use the class of conditionally conjugate priors for hum, hin, θuk, βik, ξu, ηi and zui,k to update the variational parameters {ζ, ρ, ν, µ, κ, τ, φ}. For the Gamma distribution, we update both hyper-parameters: shape and rate.

(1) Update shape and rate of ζm:

where ℵm is the number of users having attribute m. (2) Update shape and rate of ρn:

where χn is the number of items that have attribute n. (3) Update shape and rate of κu:

where K is the number of latent components.

(4) Update shape and rate of τi:

(5) Update φui,k:

where Ψ(.) is the digamma function.

(6) Update shape and rate of νuk:

(7) Update shape and rate of µik:

Owing to the limited space, we only give the deviation of integrating user/item metadata. The details of other deviations are similar to PF and are ignored here.

The posterior probability of weight hum becomes:

where ℵm is the number of users having attribute m. The posterior Gamma distribution of hum is

hum is affected by ℵm and the user's latent behavior (i.e., ξu). Similarly, the posterior distribution for the weight of item attribute, hin, is

where χn is the number of items that have attribute n.

By the mean-field variational inference, the coordinate ascent is used to iteratively optimize each variational parameter while holding the others fixed [Jordan et al., 1999]. The variational inference of MPF is listed in Algorithm 1. We have to give the number of latent components at the beginning of the algorithm as in line 2.

3.2 Variational Inference for MIPF

Using the auxiliary variable as in Eq. (16), the completely factorized variational distribution in MIPF can be written as

Algorithm 1 Variational Inference for MPF

• 1: Initialize the variational parameters {ζ, ρ, ν, µ, κ, τ, φ}.
• 2: Set the number of components K.
• 3: Sample shape of user's latent behavior, and shape of item's latent attractiveness, as in Eqs. (22) and (24).
• 4: Sample shape of the weight of user's attribute (in metadata), and shape of the weight of item's attribute (in metadata), as in Eqs. (18) and (20).
• 5: repeat
• 6: for each rating of user u to item i that yui ̸= 0 do 7: Update the multinominal as in Eq. (26).
• 8: end for

9:

for each user do

10: Update the latent preference as in Eqs. (27) and (28)

11: Update rate of latent behavior as in Eq. (23).

12:

for each user attribute in metadata do

13:

Update rate of the weight as in Eq. (19)

14:

end for 15: end for

16:

for each item do

17: Update the latent feature as in Eqs. (29) and (30).

18: Update rate of latent attractiveness as in Eq. (25).

• 19: for each item attribute do

20:

Update rate of the weight as in Eq. (21).

• 21: end for
• 22: end for
• 23: until convergence

We update the variational parameters {ζ, ρ, µ, τ} similar to MPF. The new parameters needed to be updated are user's latent behavior κ, stick-breaking proportion σ and multinominal distribution φ. Again, owning to the limitation of space, we do not give the details of deviations of κ, σ and φ, which can be found at [Teh and Jordan, 2010; Liang et al., 2007; Kurihara et al., 2007; Gopalan et al., 2014a].

1. Update shape and rate of κu:

where E[·] is the expectation with respect to the distribution q. T is the truncate level which is the upper bound of number of latent components K as described in [Kurihara et al., 2007].

(2) Update the stick-breaking proportion σuk by solving the quadratic equation Aukσ2uk + Bukσuk + Cuk = 0:

where the details of Auk, Buk and Cuk can be found in [Gopalan et al., 2014a].

(3) Update the multinominal distribution φui,k

where

and

The variational inference for MIPF is nearly similar to MPF with the exception in lines 2, 3, 7, 10 and 11. In line 2, instead of setting the number of latent components K, we set the truncate level T . In line 7, we update the multinominal as in Eq. (40). We update the stick-breaking proportion as in Eq. (39) instead of updating the user's preference as in line 10. In lines 3 and 11, we update the shape and rate of user's latent behavior as in Eqs. (37) and (38).

4 MPF/MIPF Properties and RelatedWork

We analyze the properties and performance of MPF/MIPF in the context of the related work.

(1) MPF/MIPF improve precision when working with large and sparse data by integrating user/item metadata. Given the vector of user's latent preferences θu and the vector of the item's latent features βi, the probability of the rating by user u to item i, yui, based on Poisson distribution, is below.

When yui = 0, it does not affect the probability. Similar to PF, it does not require optimization techniques to reduce the computational time as in the classical MF [Li et al., 2015; Mairal et al., 2010]. The probability only depends on θu and βi. We provide richer priors by integrating user metadata to the user's behaviors, ξu, as in Eq. (44). The user's behaviors, ξu, in turn provide richer prior to the user's latent preferences θuk, as in Eq. (5).

Similarly, we integrate item metadata to PF.

Different from the way of integrating document-word matrix into PF [Acharya et al., 2015; Gopalan et al., 2014b; Zhang and Wang, 2015; Hu et al., 2016], MPF incorporates the user metadata, which includes more general attributes, e.g., categorical attributes, rather than just text. Recent work in [Zhao et al., 2017; Fan et al., 2017] also integrates such

general attributes into probabilistic models for link prediction, but works only on small data due to the limitation of their inference.

Our models come with the variational inference, which has proved to be efficient for probabilistic models with a large amount of data. As MPF is built on the Gamma-GammaGamma-Poisson distribution, it is fully Bayesian and conjugate. As discussed in [Ghahramani and Beal, 2001], we can easily build a variational algorithm for fully Bayesian and conjugate models. Although the VI method for MIPF is much more complicated since the distribution of MIPF is not in a closed form, there are some techniques to overcome this such as in [Liang et al., 2007; Kurihara et al., 2007; Gopalan et al., 2014a].

(2) MIPF efficiently estimates the number of latent components. We use the same technique as in such BNP models as [Teh and Jordan, 2010; Liang et al., 2007; Kurihara et al., 2007; Gopalan et al., 2014a] to estimate the number of latent components at running time. Different from the BNP MF, such as [Knowles and Ghahramani, 2011; Hoffman et al., 2010], which requires to scan both missing and non-missing ratings, MIPF only computes on nonmissing data. This makes our inference procedure extremely efficient for sparse matrices.

5 Experiments

5.1 Experimental Settings

Baseline Methods To the best of our knowledge, no existing methods have incorporated user/item metadata into PF and infinite PF. As [Gopalan et al., 2015] shows that the hierarchical PF (HPF) outperforms baselines including basic PF, Nonnegative Matrix Factorization (NMF) [Berry et al., 2007], Latent Dirichlet Allocation (LDA) [Blei et al., 2003], and Probabilistic Matrix Factorization (PMF) [Mnih and Salakhutdinov, 2008], we thus here only compare our models with HPF, in addition to Bayesian Nonparametric PF (BNPPF) [Gopalan et al., 2014a] and the latest PF: Hierarchical Compound PF (HCPF) [Basbug and Engelhardt, 2016].

Datasets MPF/MIPF are tested on four public datasets available with massive ratings and some metadata.

1. Movielens100K [Harper and Konstan, 2016] contains 100, 000 ratings (from 1 to 5); user demographic: 'age', 'gender', 'occupation' and 'zip' ('age' is partitioned into the ranges: 1 : "Under 18", 18 : "18-24", 25 : "25-34", 35 : "35-44", 45 : "45-49", 50 : "50-55", and 56 : "56+"); and item metadata: the 'genre','release date', and 'video release date' of movies.
2. Movielens1M contains 1, 000, 209 anonymous ratings and the same metadata as in Movielens100K.
3. Movielens10M contains 10, 000, 054 ratings with the metadata only containing the 'genre' of the movies.
4. Book-Crossing [Ziegler et al., 2005] contains 1, 149, 780 ratings (from 1 to 10) with the user demographic: 'location' and 'age' ('age' is encoded in the same way as in Movielens100K) and the book information: 'book title', 'book author', 'year of publication', and 'publisher'.

Parameter Settings We set a = c = a′ = c′ = 0.3 in the same way as in HPF. The metadata hyper parameters α0, α1,

γ0 and γ1 are set to a small value: 0.1, so that the user/item attribute's weight automatically grows over time.

5.2 Result Evaluation

We evaluate MPF/MIPF in terms of their performance of addressing the three PF challenges (Q1, Q2 and Q3 below) w.r.t. the following metrics and convergence.

Evaluation Metrics We use 20% of the ratings for testing and 80% for training by random splitting. The top-N recommendations are obtained in training w.r.t. the highest prediction score. In testing, we compute the precision-at-N, which measures the fraction of relevant items in a user's top-N recommendations, and recall-at-N, which is the fraction of the testing items that present in the top-N recommendations.

Convergence We measure the convergence by computing the prediction accuracy on the validation set that is extracted by randomly selecting 1% of the ratings in the training set.

Q1: How do MPF/MIPF significantly outperform other PF models? As shown in Figure 2, MPF/MIPF outperform HPF, BNPPF and HCPF in all datasets for normalized mean precision and normalized mean recall. The results on Movielens10M are not as good as on the others due to only one metadata attribute the 'genre' of the movies. MPF/MIPF make the most improvement (up to 9%) on Book-Crossing corresponding to the richest metadata available.

Q2: How does MIPF effectively estimate the number of unbounded latent components? The infinite model MIPF is compared with the finite version MPF in Figure 3 in terms of normalized mean precision. The results for the normalized mean recall are consistent with normalized mean precision, omitted here due to the limitation of space. We run MPF w.r.t. K from 1 to 200 but MIPF for just once. For MIPF, we set the truncate level T to 200. We can see that MIPF can always achieve as good as the best results of MPF. This shows MIPF is very efficient in selecting the suitable number of latent components K.

Q3: How do MPF/MIPF deal with sparse items/users? In this experiment, we choose 20 users who have the highest number of precisely recommended items. We calculate the sparsity within each item (i.e., the fraction of the number of users who gave ratings for that item in the total number of users). Figure 4 shows the percentage of number of items that have sparsity less than 1% in the total recommended items for each user for MIPF and HCPF. It shows MIPF recommends more sparse items than HCPF as the result of integrating metadata. The results for sparse users are similar to sparse items, omitted here for the limitation of space.

6 Conclusions

Two novel and efficient Poisson factorization models MPF and MIPF are proposed for sparse and large-scale recommendation. They are the first to effectively integrate user/item metadata into PF, and MIPF can effectively estimate the number of latent components in just one run. We are developing even more efficient inference for MIPF to handle increasingly bigger data.