Matrix factorization (MF) is the simplest and most well studied factor based model and has been applied successfully in several domains. One of the standard ways to solve MF is by nding maximum a posteriori estimate of the model parameters, which is equivalent to minimizing the regularized objective function. Stochastic gradient descent (SGD) is a common choice to minimize the regularized objective function. However, SGD su ers from the problem of over tting and entails tedious job of nding the learning rate and regularization parameters. A fully Bayesian treatment of MF avoids these problems. However, the existing Bayesian matrix factorization method based on the Markov chain Monte Carlo (MCMC) technique has cubic time complexity with respect to the target rank, which makes it less scalable. In this paper, we propose the Scalable Bayesian Matrix Factorization (SBMF), which is a MCMC Gibbs sampling algorithm for MF and has linear time complexity with respect to the target rank and linear space complexity with respect to the number of non-zero observations. Also, we show through extensive experiments on three su ciently large real word datasets that SBMF incurs only a small loss in the performance and takes much less time as compared to the baseline method for higher latent dimension.
Factor based models have been used extensively in collaborative ltering. In a factor based model, preferences of each user are represented by a latent factor vector. Matrix factorization (MF) [1{6] is the simplest and most well studied factor based model and has been applied successfully in several domains. Formally, MF recovers a low-rank latent structure of a matrix by approximating it as a product of two low-rank matrices. For delineation, consider a user-movie matrix R 2 RI J where the rij cell represents the rating provided to the jth movie by the ith user. MF decomposes the matrix R into two low-rank matrices U = [u1; u2; :::; uI ]T 2 RI K and V = [v1; v2; :::; vJ ]T 2 RJ K (K is the latent space dimension) such that:
R
U V T :
Probabilistic Matrix Factorization (PMF) [
N (rij juiT vj ;
1);
Y where is the set of all observed entries in R provided during the training and is the model precision. Zero-mean spherical Gaussian priors are placed on the latent factor vectors of users and movies. The main drawback of this model is that inferring the posterior distribution over the latent factor vectors, given the ratings, is intractable. PMF handles this intractability by providing a maximum a posteriori estimation of the model parameters by maximizing the log-posterior over the model parameters, which is equivalent to minimizing the regularized square error loss de ned as: (1) (2)
X
where is the regularization parameter and jjXjj2F is the Frobenius norm of
X. The optimization problem in Eq. (3) can be solved using stochastic gradient
descent (SGD) [
On the other hand, fully Bayesian methods [5, 8{10] for MF do not require
manual tuning of the learning rate and regularization parameters and are
robust to over tting. As direct evaluation of posterior is intractable in practice,
approximate inference techniques are adopted to learn the posterior
distribution. One of the possible choices of approximate inference is to apply variational
approximate inference technique [
In BPMF, user/item latent factor vectors are assumed to follow a multivariate Gaussian distribution, which results cubic time complexity with respect to the latent factor vector dimension. Though BPMF performs well in many applications, this cubic time complexity makes it di cult to apply BPMF on very large datasets. In this paper, we propose the Scalable Bayesian Matrix Factorization (SBMF) based on the MCMC Gibbs sampling, where we assume univariate Gaussian priors on each dimension of the latent factor. Due to this assumption, the complexity of SBMF reduces to linear with respect to the latent factor vector dimension. We also consider user and item bias terms in SBMF which are missing in BPMF. These bias terms capture the variation in rating values that are independent of any user-item interaction. Also, the proposed SBMF algorithm is parallelized for multicore environments. We show through extensive experiments on three large scale real world datasets that the adopted univariate approximation in SBMF results in only a small performance loss and provides signi cant speed up when compared with the baseline method BPMF for higher values of latent dimension. 2 2.1
+ i + j + uiT vj + ij ;
(4)
where (i; j) 2 , is the global bias, i is the bias associated with the ith
user, j is the bias associated with the jth item, ui is the latent factor vector of
dimension K associated with the ith user, and vj is the latent factor vector of
dimension K associated with the jth item. Uncertainty in the model is absorbed
by the noise ij which is generated as ij N (0; 1), where is the precision
parameter. Bias terms are particularly helpful in capturing the individual bias
for user/item: a user may have the tendency to rate all the items higher than
the other users or an item may get higher ratings if it is perceived better than
the others [
The conditional on the observed entries of R (the likelihood term) can be written as follows: p(Rj ) =
Y
N (rij j + i + j + uiT vj ; where = f ; ; f ig; f j g; U ; V g. We place independent univariate priors on all the model parameters in as follows: (5) (6) (7) (8) (9) (10) (11) H = (12) (13) (14) (15) (16) p( ) =N ( j g; g 1); p( i) =N ( ij p( j ) =N ( j j
I K p(U ) = Y Y i=1 k=1
J K p(V ) = Y Y We denote fa0; b0; g; g; 0; 0; 0; 0g as 0 for notational convenience. The joint distribution of the observations and the hidden variables can be written as: p(R; ;
I J H j 0) = p(Rj )p( ) Y p( i) Y p( j )p(U )p(V )p( i=1 j=1 ; ) p( ;
K ) Y p( uk ; uk )p( vk ; vk ): k=1
Since evaluation of the joint distribution in Eq. (16) is intractable, we adopt a
Gibbs sampling based approximate inference technique. As all our model
parameters are conditionally conjugate [
N (uikj ; ) ; where,
0 = 0
X j2 i 0 uilvjlAAA : (17) (18) (19) (20) Here, i is the set of items rated by the ith user in the training set. Now, directly sampling uik from Eq. (17) requires O(Kj ij) complexity. However if we precompute a quantity eij = rij ( + i + j + uiT vj ) for all (i; j) 2 and write Eq. (19) as: = 0
1 X vjk (eij + uikvjk)A ; j2 i then the sampling complexity of uik reduces to O(j ij). Table 1 shows the space and time complexities of SBMF and BPMF. We sample model parameters in parallel whenever they are independent to each other. Algorithm 1 describes the detailed Gibbs sampling procedure. Algorithm 1 Scalable Bayesian Marix Factorization (SBMF) Require: 0, initialize and H .
Ensure: Compute eij for all (i; j) 2 1: for t = 1 to T do 2: // Sample hyperparameters = 0 + 12 (I + 1), 3.1
In this section, we show empirical results on three large real world movie-rating datasets3;4 to validate the e ectiveness of SBMF. The details of these datasets are provided in Table 2. Both the Movielens datasets are publicly available and 90:10 split is used to create their train and test sets. For Net ix, the probe data is used as the test set. 3.2
All the experiments are run on an Intel i5 machine with 16GB RAM. We have
considered the serial as well as the parallel implementation of SBMF for all the
experiments. In the parallel implementation, SBMF is parallelized in multicore
environment using OpenMP library. Although BPMF can also be parallelized,
the base paper [
In SBMF, we initialize parameters in using a Gaussian distribution with 0
mean and 0:01 variance. All the parameters in H are set to 0. Also, a0; b0; 0; 0,
and 0 are set to 1, 0 and g are set to 0, and g is initialized to 0.01. In
BPMF, we use standard parameter setting as provided in the paper [
C
1 X
C
c=1
c +
ic + jc + uic:vjc ;
(21)
3 http://grouplens.org/datasets/movielens/
4 http://www.net ixprize.com/
where uic and vjc are the cth drawn samples of the ith user and the jth item latent
factor vectors respectively, c; ic, and jc are the cth drawn samples of the global
bias, the ith user bias, and the jth item bias, respectively. C is the number of
drawn samples. Then the Root Mean Square Error (RMSE) [
We can observe from the Fig. 2 that SBMF-P takes much less time in all
the experiments than BPMF and incurs only a small loss in the performance.
Similarly, SBMF-S also takes less time than the BPMF (except for K = f50; 100g
in Net ix dataset) and incurs only a small performance loss. Important point
to note is that total time di erence between both of the variants of SBMF and
BPMF increases with the dimension of latent factor vector and the speedup is
signi cantly high for K = 200. Table 3 shows the nal RMSE values and the total
time taken correspond to each dataset and K. We nd that the RMSE values
for SBMF-S and SBMF-P are very close for all the experiments. We also observe
that increasing the latent space dimension reduces the RMSE value in the Net ix
5 https://github.com/avijit1990, https://github.com/rishabhmisra
dataset. With high latent dimension, the running time of BPMF is signi cantly
high due to its cubic time complexity with respect to the latent space dimension
and it takes approximately 150 hours on Net ix dataset with K = 200. However,
SBMF has linear time complexity with respect to the latent space dimension and
SBMF-P and SBMF-S take only 35 and 90 hours (approximately) respectively on
the Net ix dataset with K = 200. Thus SBMF is more suited for large datasets
with large latent space dimension. Similar speed up patterns are found on the
other datasets also.
MF [1{6] is widely used in several domains because of performance and
scalability. Stochastic gradient descent [
Since performance of MF depends on the latent dimensionality, several
nonparametric MF methods [14{16] have been proposed that set the number of
latent factors automatically. Non-negative matrix factorization (NMF) [
We have proposed the Scalable Bayesian Matrix Factorization (SBMF), which is a Markov chain Monte Carlo based Gibbs sampling algorithm for matrix factorization and has linear time complexity with respect to the target rank and linear space complexity with respect to the number of non-zero observations. SBMF gives competitive performance in less time as compared to the baseline method. Experiments on several real world datasets show the e ectiveness of SBMF. In future, it would be interesting to extend this method in applications like matrix factorization with side-information, where the time complexity is cubic with respect to the number of features (which can be very large in practice). 6
This project was supported by Ericsson India.