# Patent

## Title
Robust Bayesian matrix factorization and recommender systems using same

## Abstract

In a recommender method, Bayesian Matrix Factorization (BMF) is performed on a matrix having user and item dimensions and matrix elements containing user ratings for items made by users in order to train a probabilistic collaborative filtering model. A recommendation is generated for a user using the probabilistic collaborative filtering model. The recommendation may comprise a predicted item rating, or an identification of one or more recommended items. The recommender method is suitably performed by an electronic data processing device. The BMF may employ non-Gaussian priors, such as Student-t priors. The BMF may additionally or alternatively employ a heteroscedastic noise model comprising priors that include (1) a row dependent variance component that depends upon the matrix row and (2) a column dependent variance component that depends upon the matrix column.

## Background
BACKGROUND
The following relates to the online retail arts, online service provider arts, recommender system arts, collaborative filtering arts, and related arts.
Recommender systems find application in numerous retail and service applications, among other. A recommender system attempts to predict the preferences or choices of a user, and can be used, by way of illustrative example, to provide recommendations to a user from amongst a catalog of items or services. For example, an online retailer provides a website via which a user (i.e., customer) browses the retailer's catalog of products or services. The retailer desires for the customer to identify products or services for purchase. Toward that end, it is useful for the retailer to be able to automatically identify and present to the customer specific products or services that the customer is likely to want to purchase. The recommender system, in this application, identifies products or services that are likely to be of interest to the customer, and these products are recommended to the customer.
One way to generate such recommendations is based on products or services which the customer has previously viewed or actually purchased. However, this approach assumes that there is a substantial past history of browsing or purchasing available for the customer. This will not be the case for new or infrequent customers, and also will not be the case for existing customers who have not been identified as such by the retailer's online catalog (e.g., by the customer logging into the website or by reading a “cookie” or other identifying information available on the customer's computer). Moreover, even if a substantial past history is available for the customer, it may not be useful for prediction if the customer is browsing in some portion of the online catalog that the customer has not previously visited.
Collaborative filtering is a recommender approach that makes predictions for a given user based on collected information about preferences of many other users. Conceptually, collaborative filtering is based on expectation that, for a given user, the choices of other users whose past history is similar to that of given user is likely to be probative for predicting the preferences or choices of the given user. Collaborative filtering can utilize a database of product ratings provided for various products or services by users of the retailer's product catalog.
A difficulty with collaborative filtering is that the available data is typically sparse. Using the example of a user ratings database, most users have never viewed or purchased most products of the catalog (let alone gone to the effort of inputting a rating for the product). Additionally, the ratings data is typically noisy. For example, in a rating system employing a one-to-five star scale, there is substantial subjectivity as to whether a given customer rates a product as “four stars” or “three stars” (or “three-and-a-half stars”, if fractions are allowable). Some users have a tendency to rate more negatively, while others tend to rate more positively. Different users also consider different criteria in rating a product or service. Still further, the ratings data may have substantial outlier content. For example, a customer who receives a defective product may rate the product as “one star” due to the experience of receiving a defective product, even though the product in general may be quite reliable and satisfactory for most customers.
In many collaborative filtering applications, the available data is amenable to representation in a matrix data structure. For example, product ratings can be represented as a two-dimensional matrix in which the rows correspond to customers and the columns correspond to products (or vice versa). In this representation, Probabilistic Matrix Factorization (PMF) is a known technique for performing collaborative filtering. PMF has some ability to handle difficulties such as noise and outliers. However, improved techniques that provide enhanced robustness would be advantageous.
BRIEF DESCRIPTION
In some illustrative embodiments disclosed as illustrative examples herein, an apparatus comprises an electronic data processing device configured to perform a recommender method including: performing Bayesian Matrix Factorization (BMF) on a matrix having user and item dimensions using non-Gaussian priors to train a probabilistic collaborative filtering model; and generating a recommendation for a user comprising a predicted item rating or identification of one or more recommended items using the probabilistic collaborative filtering model.
In some illustrative embodiments disclosed as illustrative examples herein, in a non-transitory storage medium stores instructions executable by an electronic data processing device to perform a recommender method including: (i) performing Bayesian Matrix Factorization (BMF) on a matrix having user and item dimensions using priors having noise terms that vary with both row and column position in the matrix to train a probabilistic collaborative filtering model and (ii) generating a recommendation for a user comprising a predicted item rating or identification of one or more recommended items using the probabilistic collaborative filtering model.
In some illustrative embodiments disclosed as illustrative examples herein, a method comprises: performing Bayesian Matrix Factorization (BMF) on a matrix having user and item dimensions and matrix elements containing user ratings for items made by users wherein the BMF employs priors that include (1) a row dependent variance component that depends upon the matrix row and (2) a column dependent variance component that depends upon the matrix column to train a probabilistic collaborative filtering model; and generating a recommendation for a user comprising a predicted item rating or identification of one or more recommended items using the probabilistic collaborative filtering model. The performing and the generating are suitably performed by an electronic data processing device.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 diagrammatically shows an illustrative recommender system.
FIG. 2 plots a histogram of empirical and predicted results obtained using Probabilistic Matrix Factorization (PMF) with Gaussian priors and homoscedastic Gaussian noise.
FIG. 3 diagrammatically shows Bayesian Matrix Factorization (BMF) models suitably employed by the recommender system of FIG. 1.



DETAILED DESCRIPTION
The following relates to recommender systems for generating a recommendation for a user comprising a predicted item rating or identification of one or more recommended items using a probabilistic collaborative filtering model. The term “user” as used herein encompasses any person acting alone or as a unit (e.g., a corporation, non-profit organization, or so forth) that rates items. Because the users are individual persons or groups of persons, the rating of an item by a user is subject to noise due to individual differences, personal biases, and so forth. An “item” as used herein is a product, service, or other subject of ratings assigned by users.
With reference to FIG. 1, In the illustrative example, the users are customers and the items are products or services offered by an online retail store website 10 that is embodied by an Internet-based server computer or computers. A customer interacts with the online retail store website 10 using an electronic device 12 such as a desktop computer, notebook computer, electronic tablet, smartphone (illustrated), personal data assistant (PDA), or so forth. The electronic device 12 is operatively connected with the online retail store website via the Internet 14 (diagrammatically indicated by a dashed line; it is to be understood the connection may also include intermediary elements such as a local area wired or wireless network, a firewall, or so forth). The electronic device 12 includes a display 16. Although the single electronic device 12 is shown, it is to be understood that the online retail store website 10 typically serves many customers who typically each use their own electronic device or devices to access the website 10, although some sharing of devices amongst customers is also contemplated.
The online retail store website 10 enables users to rate products or services available on the website 10. In the illustrative example, ratings are on a one-to-five star scale; however, any other rating scale can be employed. The ratings are stored in a user ratings database 20, and are suitably organized in a matrix in which the rows (n) correspond with users (i.e., customers in this example) and the columns (m) correspond with items (i.e., products or services in this example). The illustrative matrix includes only N=6 users and M=8 items; however, the number of users may be in the dozens, hundreds, thousands, tens of thousands, hundreds of thousands, millions or more; and the number of items may be in the dozens, hundreds, thousands, tens of thousands, hundreds of thousands, millions or more. The matrix is typically sparse since most (user, item) elements do not store a rating (that is, a given customer has typically not rated most items, and a given item typically has not been rated by most customers).
During the course of a user's session on the online retail store website 10, it is advantageous to push recommendations to the user. Toward this end, a recommender system or sub-system 24 is provided, which is embodied by an electronic data processing device 26 that is configured (e.g., by being programmed with suitable software or firmware) to perform a recommender method as disclosed herein. The electronic data processing device 26 may be the same Internet-based server computer or computers (e.g., computer cloud) embodying the online retail store website 10, or the electronic data processing device 26 may be a different computer or device that is in operative communication with the online retail store website 10. The recommender system or sub-system 24 is configured to implement a Bayesian Matrix Factorization (BMF) training module 30 that performs BMF on the user ratings matrix 20 having user and item dimensions (n,m) using suitable priors 32 and a noise model 34 in order to train a probabilistic collaborative filtering model.
The recommender system or sub-system 24 is further configured to implement a recommendation module 40 that generates a recommendation for a user using the probabilistic collaborative filtering model. More particularly, the recommendation module 40 receives a query 42, which may comprise a user or a (user, item) pair, and returns a recommendation 44. If the query 42 is a (user, item) pair, then the recommendation module 40 generates the recommendation 44 in the form of a predicted item rating for the item. The predicted item rating is a prediction of the rating that the user of the (user, item) pair would be expected to assign to the item of the (user, item) pair. On the other hand, if the query 42 is a user (alone, without a paired item), then the recommendation module 40 generates the recommendation 44 in the form of an identification of one or more recommended items, e.g. a “top-K” items. To do this, the recommendation module 40 generates predicted ratings for the user for each item available at the online retail store website 10 (or for a subset of these items, e.g. for all jazz music albums in the music department of the online retail store website 10), ranks the items according to the predicted ratings, and returns the top-K ranked items.
The online retail store website 10 then displays the recommendation 44 to the user on the display 16 of the electronic device 12. The sequence of generating the query 42, receiving the recommendation 44, and displaying the recommendation 44 on the display 16 of the electronic device 12 can occur in various settings. For example, when a user selects an item for viewing, the online retail store website 10 may generate the query 42 as the (user, item) pair, and then display the store's best guess for the user's rating of the item in the view of the item. To increase user purchases, in another variation when the user views an item in a given department the query 42 is generated as the user alone (not paired with the item) but optionally with the query constrained based on the viewed item (e.g., limited to the department of the store to which the viewed item belongs. The recommendation 44 is then a set of top-K items having the highest predicted rating for the user. These top-K items are then displayed in the view of the selected item, along with suitable language such as “You may also be interested in these other available items:” or some similar explanatory language. The displayed top-K recommended items are preferably associated with hyperlinks such that user selection of one of the recommended items causes the online retail store website 10 to generate a view of the selected recommended item.
It is also to be appreciated that the disclosed recommendation techniques may be implemented as a non-transitory storage medium storing instructions executable by an electronic data processing device (such as the illustrative computer 26, optionally comprising the server supporting the online retail store website 10) to perform the disclosed recommender methods. The non-transitory storage medium may, for example, include a hard disk, RAID, or other magnetic storage medium; a DVD or other optical storage medium; a random access memory (RAM), read-only memory (ROM), flash memory or other electronic storage medium; various combinations thereof; or so forth.
Having provided an overview of the recommendation system with reference to FIG. 1, some illustrative Bayesian Matrix Factorization (BMF) approaches suitably implemented by the BMF training module 30 are described.
A simple method to factorize a large, partially observed matrix is Singular Value Decomposition (SVD), which finds a low-rank bilinear approximation of the observation matrix. Entries of the matrix are modeled by an inner product between two low-dimensional feature vectors, which are usually estimated by minimizing a squared loss. In the fully observed case, this problem can be solved by classical SVD. It is known to have a unique solution, which can be obtained by a series of rank-1 approximations applied on the residuals, i.e. the difference between the observations and the model predictions. In collaborative filtering, however, most of the entries are missing (i.e., the matrix 20 is sparse). The corresponding optimization problem is a weighted version of SVD, which is substantially more difficult to solve. Simple EM-like algorithms estimating the distribution of missing entries are typically slow to converge when the data are sparse. See Nati et al., “Weighted low-rank approximations”, in 20th International Conference on Machine Learning, Citeseer, 2003. Most of the existing methods use block-coordinate gradient descent algorithms based on alternating regressions, sometimes called criss-cross regression. See Gabriel et al., “Lower rank approximation of matrices by least squares with any choice of weights”, Technometrics, 21(4):489-498, 1979. Robust alternating regression can be used to add robustness against outliers and to stabilize the algorithm (i.e. to avoid local minima). See Croux et al., “Fitting multiplicative models by robust alternating regressions”, Statistics and Computing, 13(1):23-36, 2003; Maronna et al., “Robust Low-Rank Approximation of Data Matrices With Elementwise Contamination”, Technometrics, 50(3):295-304, 2008. Robust estimators for the weighted SVD problem provide significant improvements in terms of parameter estimation and predictive performances. While these approaches can be applied to collaborative filtering, they are ad-hoc in the sense that they were designed to alleviate the inherent difficulties of the estimation problem, but are not justified in terms of proper probabilistic modeling.
Probabilistic approaches are known that use a Gaussian noise model, commonly denoted by the term Probabilistic Matrix Factorisation (PMF). These PMF approaches have been shown to lead to significant improvements over standard SVD. See Lim et al., “Variational Bayesian approach to movie rating prediction”, in KDD Cup and Workshop, 2007; Raiko et al., “Principal component analysis for sparse high-dimensional data”, in 14th International Conference on Neural Information Processing (ICONIP), pages 566-575, 2007; Salakhutdinov et al., “Probabilistic matrix factorization”, in Advances in Neural Information Processing Systems 21 (NIPS), 2008. The improvement over standard SVD attained by PMF is believed to be attributable to implicit smoothing included in the model. See Nakajima et al., “Implicit regularization in variational bayesian matrix factorization”, in 27th International Conference on Machine Learning (ICML), 2010. While assuming Gaussian noise makes sense when the observations are continuous, it is less justified when the observations are on an ordinal scale; however, PMF has been shown to perform well on this kind of data. A possible explanation is that a continuous noise model accounts for the user's occasional mood swings and feedback of varying quality.
The full Bayesian treatment of PMF is known as Bayesian Matrix Factorization (BMF). See Salakhutdinov et al., “Bayesian probabilistic matrix factorization using Markov chain Monte Carlo”, in 25th International Conference on Machine Learning (ICML), 2008. Existing BMF techniques further extend the probabilistic model by imposing Gaussian-Wishart priors over the low-rank decomposition. Id. A study of the posteriors obtained by BMF on standard movie recommendation benchmarks show that the tails are significantly stronger than the tails of the Gaussian distribution. Id.
Robustness is key to the success of practical supervised and unsupervised learning techniques. See, e.g., Mehta et al., “Robust collaborative filtering”, in ACM Conference On Recommender Systems, pages 49-56, 2007 (presenting an application of M-estimators to collaborative filtering). A reduced sensitivity to model misspecifications is advantageous in order to handle outliers and atypical observations. Various approaches for enhancing robustness of BMF are disclosed herein.
In BMF approaches disclosed herein, the Gaussian distributions conventionally used in BMF are replaced by heavy-tailed distributions such as the Student-t. Such heavy tailed distributions have previously been shown to be beneficial in principal component analysis (PCA) (Archambeau et al., “Robust probabilistic projections”, in 23rd International Conference on Machine Learning (ICML), pages 33-40, 2006), linear models for regression (Tipping et al., “Variational inference for Student-t models: robust Bayesian interpolation and generalized component analysis”, Neurocomputing, 69:123-141, 2005), and clustering (Archambeau et al., “Robust Bayesian clustering”, Neural Networks, 20:129-138, 2007). In conjunction with BMF, non-Gaussian distributions are incorporated in two different ways. First, the Gaussian noise model used in conventional BMF is replaced by a Gaussian scale mixture-based noise model. This model is closely related to a Student-t one, which is obtained by integrating out a Gamma distributed scale variable in a Gaussian scale mixture.
Additionally, the disclosed approaches model heteroscedastic noise by using variance values for the priors that are heteroscedastic across the matrix. Two rescaling factors per observation (i.e., matrix element) are provided: one due to the user (i.e., the row in the matrix 20) and one due to the item (i.e., the column in the matrix 20). It is empirically found that modeling row- and column-specific variances in bilinear forms significantly improves the predictive performance.
Still further, in some embodiments Student-t priors are employed on the latent features. The distribution of these features is non-Gaussian and exhibit heavy tails. These heavy-tailed priors further improve the quality of the rating predictions.
Various noise aspects are considered in more detail next.
Let N be the number of users and let M be the number of rated items. As shown in FIG. 1, in the illustrative examples the data are arranged in matrix 20 with rows n corresponding to users and columns m corresponding to items; however, the opposite configuration is also contemplated (i.e., rows corresponding to items and columns corresponding to users). The aim is to compute a factorized form of the rating matrix RεN×M. This low-rank approximation will have the effect of pooling users and items together, which in turn facilitates predicting unobserved entries. Further let WεN×M be the indicator matrix of the observed elements of R, that is wnm equals 1 if rnm has been observed and 0 otherwise. The collaborative filtering problem can then be written as a weighted SVD problem (see Nati et al., “Weighted low-rank approximations”, in 20th International Conference on Machine Learning, Citeseer, 2003):

minΦ,Ω∥W*(ΦΩT−R)∥F2  (1),

where ∥.∥F is the Frobenius norm and * is the Hadamard product. The tall matrices Φ=(φ1, . . . φN)TεN×K and Ω=(ω1, . . . , ωM)TεM×K denote respectively the user-specific and item-specific feature matrix. In these notations the rows of Φ correspond to the latent row features and the rows of Ω correspond to the latent column features. Solving the weighted SVD problem is more involved than solving standard SVD as the typically used sequence of rank-1 approximations of the residuals is not guaranteed to converge to a solution of Equation (1).

Gaussian noise is first considered. A probabilistic interpretation of Equation (1) is obtained by assuming that given the latent features φn and ωm, the observation rnm is isotropic Gaussian with mean φnTωm and constant precision τ>0. The log-likelihood of the observed ratings is then given by:




  
    
      
        
          
            ln
            ⁢
            
              
            
            ⁢
            
              p
              ⁡
              
                (
                
                  
                    R
                    |
                    Φ
                  
                  ,
                  Ω
                  ,
                  τ
                
                )
              
            
          
          =
          
            
              Σ
              l
            
            ⁢
            
              
            
            ⁢
            ln
            ⁢
            
              
            
            ⁢
            
              N
              ⁡
              
                (
                
                  
                    
                      r
                      l
                    
                    |
                    
                      
                        φ
                        
                          n
                          l
                        
                        T
                      
                      ⁢
                      
                        ω
                        
                          m
                          l
                        
                      
                    
                  
                  ,
                  τ
                
                )
              
            
          
        
        ,
      
    
    
      
        (
        2
        )
      
    
  




where l now indexes the observed ratings. Further, nl (ml) refers to the user index (item index) of the lth observed rating. The notation ln (lm) refers to all observed ratings for user n (item m). A solution to Equation (1) is obtained by maximizing Equation (2) with respect to the features. To prevent overfitting, one can impose isotropic Gaussian priors on them, leading to maximum a posteriori estimators. See Salakhutdinov et al., “Probabilistic matrix factorization”, in Advances in Neural Information Processing Systems 21 (NIPS), 2008 (employing this approach in PMF). Other Bayesian extensions consider Gaussian priors of various flavors. See Lim et al., “Variational Bayesian approach to movie rating prediction”, in KDD Cup and Workshop, 2007; Raiko et al., “Principal component analysis for sparse high-dimensional data”, in 14th International Conference on Neural Information Processing (ICONIP), pages 566-575, 2007; Salakhutdinov et al., “Bayesian probabilistic matrix factorization using Markov chain Monte Carlo”, in 25th International Conference on Machine Learning (ICML), 2008.

However, those models make strong assumptions about noise: it is not only considered to be normally distributed, but it is also assumed to be homoscedastic, that is, a constant noise level across rows and columns of R is assumed. However, this assumption is questionable for some recommendation applications. For example, in movie rating applications, some users might have the tendency to give nearly constant ratings, while others might have more diverse opinions, using the full scale of ratings. A similar observation can be made about the movies (or items in general): conventional movies might have a significantly smaller variance in their ratings than avant-garde films which tend to polarize the users' appreciation. To account for this variability, simple normalization can be used (e.g. standardizing user ratings by subtracting the mean and dividing by the standard deviation), but this pre-processing is subject to estimation error (e.g. when there are few observations per item). Also, normalization is applicable, either to the rows, or the columns of R, but not to the rows and the columns simultaneously. But this is precisely the situation that concerns collaborative filtering problems.
With reference to FIG. 2, an illustration is provided. The PMF solution was computed on 50% of the ratings of the One Million MovieLens data set (available at www.grouplens.org/node/73) and the remaining 50% were used to analyze the residuals, which are defined as rnm−φnTωm for this example. For each user, the unbiased empirical variance of their ratings was computed and plotted as the histogram in FIG. 2 (top plot). The exact distribution of these variances was also computed, by sampling ratings under the PMF model assumption (i.e. Gaussian homoscedastic model) for the same features and noise as before. The resulting predicted distribution corresponds to the curve in FIG. 2 (top plot). It is seen that there is a significant mismatch between the model predictions and the actual ratings. First, the model is biased towards higher variances. Second, the range of the estimated variances would have been much smaller if the noise had followed a homoscedastic Gaussian distribution. The bottom plot of FIG. 2 corresponds to the analysis of the residuals per movie (i.e., item). Again, there is a model mismatch in terms of bias and spread.
To improve these results, it is disclosed herein to employ a heteroscedastic noise model. A natural noise structure to account for the heterogeneity in the user- and item-specific variances is the following Gaussian scale mixture noise mode:




  
    
      
        
          ln
          ⁢
          
            
          
          ⁢
          
            p
            ⁡
            
              (
              
                
                  R
                  |
                  Φ
                
                ,
                Ω
                ,
                α
                ,
                β
                ,
                τ
              
              )
            
          
        
        =
        
          
            Σ
            l
          
          ⁢
          
            
          
          ⁢
          ln
          ⁢
          
            
          
          ⁢
          
            
              N
              ⁡
              
                (
                
                  
                    
                      r
                      l
                    
                    |
                    
                      
                        φ
                        
                          n
                          l
                        
                        T
                      
                      ⁢
                      
                        ω
                        
                          m
                          l
                        
                      
                    
                  
                  ,
                  
                    
                      τα
                      
                        n
                        l
                      
                    
                    ⁢
                    
                      β
                      
                        m
                        l
                      
                    
                  
                
                )
              
            
            .
          
        
      
    
    
      
        (
        3
        )
      
    
  




A difference between Equation (3) and Equation (2) is that the precision of rating rl is reweighted in Equation (3) by the user-specific scale αnl and the item-specific scale βml. The prior on the scale parameters is given by:





  
    
      
        
          
            p
            ⁡
            
              (
              
                α
                n
              
              )
            
          
          =
          
            G
            ⁢
            
              
            
            ⁢
            
              a
              ⁡
              
                (
                
                  
                    
                      α
                      n
                    
                    |
                    
                      
                        a
                        0
                      
                      2
                    
                  
                  ,
                  
                    
                      b
                      0
                    
                    2
                  
                
                )
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            p
            ⁡
            
              (
              
                β
                m
              
              )
            
          
          =
          
            Ga
            ⁡
            
              (
              
                
                  
                    β
                    m
                  
                  |
                  
                    
                      c
                      0
                    
                    2
                  
                
                ,
                
                  
                    d
                    0
                  
                  2
                
              
              )
            
          
        
      
    
    
      
        (
        4
        )
      
    
  




for all n and m. This specific choice of priors is motivated by the fact that (i) the scatter matrix of v independent multivariate Gaussian random variables is distributed according to a Wishart with v degrees of freedom and (ii) the Wishart Wi(Σ|ν) reduces to




  Ga
  ⁡
  
    (
    
      
        
          σ
          2
        
        |
        
          v
          2
        
      
      ,
      
        1
        
          2
          ⁢
          λ
        
      
    
    )
  




in one dimension. See Christopher M. Bishop. Pattern Recognition and Machine Learning, Springer, 2006, page 693. Note that the parameters a0 and b0 are shared by all users, while the parameters c0 and d0 are shared by all items. The quantities Ln and Lm are respectively the number of ratings made by user n and the number of ratings for item m. The linear dependence of the shape parameter of the Gamma distribution for αn (βm) on Ln (Lm) reflects an intuition that users (items) with higher number of ratings can be expected to exhibit lesser variance (higher precision). On the other hand, if it is not desired for the prior to be dependent on the number of observations per user or per item, these values can be set to 1.

Another improvement to BMF is next considered, namely the use of non-Gaussian priors.
A popular measure of “non-Gaussianity” is the kurtosis, which quantifies the peakedness of a distribution. A high kurtosis is related to the distribution tails as more of the variance is due to infrequent, possibly relatively extreme deviations. Student-t and other Gaussian scale mixtures have a kurtosis typically higher than that of the Gaussian. It has been shown that probabilistic principal component analysis (PCA) with Student-t features leads to improved models of large dimensional data. See Archambeau et al., “Robust probabilistic projections”, in 23rd International Conference on Machine Learning (ICML), pages 33-40, 2006. In the context of collaborative filtering, this is equivalent to imposing Gaussian scale mixtures priors on the feature according to:

p(Φ)=Πn∫(φn|0,αnφ)p(αn)dαn  (5)

and

p(Φ)=Πm∫(ωm|0,βmω)p(βn)dβn  (6)

where p(αn) and p(βn) are given by Equation (4).

In a suitable approach, φ and ω are restricted to be diagonal precision matrices, such as φ−1=diag{σ12, σ22, . . . , σK2} and ω−1=diag{ρ12, ρ22, . . . , ρK2}. The integrals of Equations (5) and (6) are analytically tractable and lead to multivariate Student-t distributions.
A suitable construction of the variational inference is next considered. Of interest is a deterministic approximation of the full Bayesian Matrix Factorization problem. A variational Expectation-Maximization (EM) approach is suitably employed. See Neal et al., “A view of the EM algorithm that justifies incremental, sparse, and other variants”, Learning in graphical models; H. Attias, “A variational Baysian framework for graphical models”, in Advances in Neural Information Processing Systems 12 (NIPS), 2000; Matthew J. Beal, Variational Algorithms for Approximate Bayesian Inference, PhD thesis, Gatsby Computational Neuroscience Unit, University College London, 2003. In this approach, the log-marginal likelihood is lower bounded by the negative variational free energy:

ln p()=−(q,θ)+(q(z))∥p(z|,θ))≧−(q,θ)

where z={Φ, Ω, α, β} are the latent variables, θ={τ,φ, ω, a0, b0, c0, d0} are the parameters and the variational free energy  is defined as follows:

=−ln p(R,z|θ)q−H[q]  (7)

In order to find a tractable solution, it is in general assumed that the variational approximate posterior q fully factorizes, that is q(z)=q(Φ), q(Ω), q(α), q(β). This approach is known as mean field. See, e.g., Christopher M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006. In this work we also consider a structured variational approximation (Wim Wiegerinck, “Variational approximations between mean field theory and the junction tree algorithm”, in Uncertainty in Artificial Intelligence (UAI), pages 626-633, 2000) of the form q(z)=q(Φ, α), q(Ω, β). Structured variational approximations have been shown to be beneficial in practice as the correlations between latent variables are not unnecessarily ignored and they reduce the bound gap. See, e.g. Archambeau et al., “Robust Bayesian clustering”, Neural Networks, 20:129-138, 2007.

Three illustrative embodiments are next set forth: (1) an embodiment employing Gaussian priors on features and non-Gaussian (namely Gaussian Scale Mixture) noise (called the “RG” embodiment herein); (2) an embodiment employing non-Gaussian (namely Student-t) priors and Gaussian noise (called the “GR” embodiment herein); and (3) an embodiment employing both non-Gaussian (namely Student-t) priors and non-Gaussian (namely Gaussian Scale Mixture) noise (called the “RR” embodiment herein).
The RG embodiment employing Gaussian priors on features and Gaussian Scale Mixture noise is implemented as follows. In this case, the mean field approximation leads to the following Gaussian variational posteriors for the latent features:

q(Φ)=Πn(φn| φn, Sn)

q(Ω)=Πm(ωn| ωn, Rn)

where

 φn=τ αn Sn−1Σl βml ωmlrl 

 Sn=τ αnΣlnβmlωmlωmlT+φ

 ωm=τβmm−1Σlm αnlφnlrl 

m=τ βmΣlmαnlφnlφnlT+ω

The variational posteriors for the scale parameters are




  
    q
    ⁡
    
      (
      α
      )
    
  
  =
  
    
      
        Π
        n
      
      ⁢
      
        
          G
          a
        
        ⁡
        
          (
          
            
              
                α
                n
              
              |
              
                
                  a
                  n
                
                2
              
            
            ,
            
              
                b
                n
              
              2
            
          
          )
        
      
      ⁢
      
        
      
      ⁢
      and
      ⁢
      
        
      
      ⁢
      
        q
        ⁡
        
          (
          β
          )
        
      
    
    =
    
      
        Π
        m
      
      ⁢
      
        
          
            G
            a
          
          ⁡
          
            (
            
              
                
                  β
                  m
                
                |
                
                  
                    c
                    m
                  
                  2
                
              
              ,
              
                
                  d
                  m
                
                2
              
            
            )
          
        
        .
      
    
  




Their parameters are given by:

an=a0+1,

bn=b0+τΣlnβml(rl−φnTωml)2

cm=c0+1,

dm=d0+τΣlmαnl(rl−φnlTωm)2

The GR embodiment employing Student-t priors and Gaussian noise is implemented as follows. We consider a structured variational approximation by restricting the variational posteriors for Φ and Ω to be of the same form as the priors, that is Gaussians with scaled covariances:

q(Φ|α)=Πn(φn| φn,αn Sn)  (8)

and

q(Ω|β)=Πm(ωm| ωm,βmm)  (9).

Direct maximization of the bound − with respect to φn and Sn, as well as ωm and Rm leads to:

 φn=τ{tilde over (S)}n−1Σln ωmlrl 

 Sn=ταn−1ΣlnωmlωmlT+φ

 ωm=τm−1Σlm φnlrl 

m=τβm−1ΣlmφnlφnlT+ω

where {tilde over (S)}n=τΣlnωmlωmlT+ αnφ and m=τΣlmφnlφnlT+ βmω The posterior for the scale parameters are suitably written as q(Φ, α)=Πn q(φn, αn) and q(Ω, β)=Πm (ωm, βm). The first of these posteriors is obtained as follows. Consider the observed variable x and the set of latent variables y={yk}k and z={zk}k. The posterior q(zk) can be computed as follows when considering a structured Q variational approximation with joint posterior q(y,z)=Πk q(yk,zk). Assume the marginal p(x) is analytically intractable. The variational lower bound is defined as −(q)=ln p(x,y,z)q(y,z)−H[(y,z)], where q(y,z)=Πk q(yk, zk). Denote the incomplete product Πk q(yk,zk) by q(y\k,z\k). Exploiting the specific form of the variational posterior and ignoring terms independent of zk, we obtain:





  
    
      
        
          -
          
            F
            ⁡
            
              (
              q
              )
            
          
        
        =
        
        ⁢
        
          
            ∫
            
              
                
                  〈
                  
                    ln
                    ⁢
                    
                      
                    
                    ⁢
                    
                      p
                      ⁡
                      
                        (
                        
                          x
                          ,
                          y
                          ,
                          z
                        
                        )
                      
                    
                  
                  〉
                
                
                  
                    q
                    ⁡
                    
                      (
                      
                        
                          y
                          k
                        
                        |
                        
                          z
                          k
                        
                      
                      )
                    
                  
                  ⁢
                  
                    q
                    ⁡
                    
                      (
                      
                        
                          y
                          
                            \
                            ⁢
                            k
                          
                        
                        ,
                        
                          z
                          
                            \
                            ⁢
                            k
                          
                        
                      
                      )
                    
                  
                
              
              ⁢
              
                q
                ⁡
                
                  (
                  
                    z
                    k
                  
                  )
                
              
              ⁢
              
                d
                
                  z
                  k
                
              
            
          
          +
        
      
    
  
  
    
      
        
        ⁢
        
          
            ∫
            
              
                H
                ⁡
                
                  [
                  
                    q
                    ⁡
                    
                      (
                      
                        
                          y
                          k
                        
                        |
                        
                          z
                          k
                        
                      
                      )
                    
                  
                  ]
                
              
              ⁢
              
                q
                ⁡
                
                  (
                  
                    z
                    k
                  
                  )
                
              
              ⁢
              
                d
                
                  z
                  k
                
              
            
          
          +
          
            H
            ⁡
            
              [
              
                q
                ⁡
                
                  (
                  
                    z
                    k
                  
                  )
                
              
              ]
            
          
          +
          const
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            ∫
            
              ln
              ⁢
              
                
              
              ⁢
              
                e
                
                  
                    
                      〈
                      
                        ln
                        ⁢
                        
                          
                        
                        ⁢
                        
                          p
                          ⁡
                          
                            (
                            
                              x
                              ,
                              y
                              ,
                              z
                            
                            )
                          
                        
                      
                      〉
                    
                    
                      
                        q
                        ⁡
                        
                          (
                          
                            
                              y
                              k
                            
                            |
                            
                              z
                              k
                            
                          
                          )
                        
                      
                      ⁢
                      
                        q
                        ⁡
                        
                          (
                          
                            
                              y
                              
                                \
                                ⁢
                                k
                              
                            
                            ,
                            
                              z
                              
                                \
                                ⁢
                                k
                              
                            
                          
                          )
                        
                      
                    
                  
                  +
                  
                    H
                    ⁡
                    
                      [
                      
                        q
                        ⁡
                        
                          (
                          
                            
                              y
                              k
                            
                            |
                            
                              z
                              k
                            
                          
                          )
                        
                      
                      ]
                    
                  
                
              
              ⁢
              
                q
                ⁡
                
                  (
                  
                    z
                    k
                  
                  )
                
              
              ⁢
              
                d
                
                  z
                  k
                
              
            
          
          +
        
      
    
  
  
    
      
        
        ⁢
        
          
            H
            ⁡
            
              [
              
                q
                ⁡
                
                  (
                  
                    z
                    k
                  
                  )
                
              
              ]
            
          
          +
          const
        
      
    
  




Up to a normalizing constant Z we have that −(q) is equal to:





  
    -
    K
  
  ⁢
  
    
  
  ⁢
  
    L
    ⁡
    
      (
      
        
          q
          ⁡
          
            (
            
              z
              k
            
            )
          
        
        ||
        
          
            1
            Z
          
          ⁢
          
            e
            
              
                
                  〈
                  
                    ln
                    ⁢
                    
                      
                    
                    ⁢
                    
                      p
                      ⁡
                      
                        (
                        
                          x
                          ,
                          y
                          ,
                          z
                        
                        )
                      
                    
                  
                  〉
                
                
                  
                    q
                    ⁡
                    
                      (
                      
                        
                          y
                          k
                        
                        |
                        
                          z
                          k
                        
                      
                      )
                    
                  
                  ⁢
                  
                    q
                    ⁡
                    
                      (
                      
                        
                          y
                          
                            \
                            ⁢
                            k
                          
                        
                        ,
                        
                          z
                          
                            \
                            ⁢
                            k
                          
                        
                      
                      )
                    
                  
                
              
              +
              
                H
                ⁡
                
                  [
                  
                    q
                    ⁡
                    
                      (
                      
                        
                          y
                          k
                        
                        |
                        
                          z
                          k
                        
                      
                      )
                    
                  
                  ]
                
              
            
          
        
      
      )
    
  




Hence, when assuming q (Φ, α)=Πn q(φn, αn), then the bound of Equation is maximal if:





  
    q
    ⁡
    
      (
      
        α
        n
      
      )
    
  
  ∝
  
    
      e
      
        
          〈
          
            ln
            ⁢
            
              
            
            ⁢
            
              p
              ⁡
              
                (
                
                  R
                  ,
                  Φ
                  ,
                  Ω
                  ,
                  α
                  ,
                  β
                
                )
              
            
          
          〉
        
        
          
            q
            ⁡
            
              (
              
                
                  φ
                  n
                
                |
                
                  α
                  n
                
              
              )
            
          
          ⁢
          
            q
            ⁡
            
              (
              
                
                  Φ
                  \n
                
                ,
                
                  α
                  \n
                
              
              )
            
          
          ⁢
          
            q
            ⁡
            
              (
              
                Ω
                ,
                β
              
              )
            
          
        
      
    
    ×
    
      e
      
        H
        ⁡
        
          [
          
            q
            ⁡
            
              (
              
                
                  φ
                  n
                
                |
                
                  α
                  n
                
              
              )
            
          
          ]
        
      
    
  




where q(Φ\k, α\k)=Πn′≠n (φn′, αn′). The variational posterior q(βm) is obtained in the same manner.

While the variational posteriors of the scale variables are not Gamma distributions in this case, they can be recognized as products of generalized inverse Gaussians:



  
    
      q
      ⁡
      
        (
        α
        )
      
    
    =
    
      
        ∏
        n
      
      ⁢
      
        
          N
          
            -
            1
          
        
        ⁡
        
          (
          
            
              
                α
                n
              
              |
              
                
                  v
                  n
                
                2
              
            
            ,
            
              χ
              n
            
            ,
            
              φ
              n
            
          
          )
        
      
    
  




  and




  
    
      q
      ⁡
      
        (
        β
        )
      
    
    =
    
      
        ∏
        m
      
      ⁢
      
        
          N
          
            -
            1
          
        
        ⁡
        
          (
          
            
              
                β
                m
              
              |
              
                
                  v
                  m
                
                2
              
            
            ,
            
              χ
              m
            
            ,
            
              φ
              m
            
          
          )
        
      
    
  



where the parameters are defined as follows:





  
    
      
        
          ν
          n
        
        =
        
          a
          0
        
      
    
    
      
        
          ν
          m
        
        =
        
          c
          0
        
      
    
  
  
    
      
        
          χ
          n
        
        =
        
          
            τΣ
            
              l
              n
            
          
          ⁢
          
            〈
            
              
                w
                
                  m
                  l
                
                T
              
              ⁢
              
                
                  S
                  _
                
                n
                
                  -
                  1
                
              
              ⁢
              
                w
                
                  m
                  l
                
              
            
            〉
          
        
      
    
    
      
        
          χ
          m
        
        =
        
          
            τΣ
            
              l
              m
            
          
          ⁢
          
            〈
            
              
                φ
                
                  n
                  l
                
                T
              
              ⁢
              
                
                  R
                  _
                
                m
                
                  -
                  1
                
              
              ⁢
              
                φ
                
                  n
                  l
                
              
            
            〉
          
        
      
    
  
  
    
      
        
          φ
          n
        
        =
        
          
            b
            0
          
          +
          
            
              
                φ
                _
              
              n
              T
            
            ⁢
            
              Λ
              φ
            
            ⁢
            
              
                φ
                _
              
              n
            
          
        
      
    
    
      
        
          φ
          m
        
        =
        
          
            d
            0
          
          +
          
            
              
                w
                _
              
              m
              T
            
            ⁢
            
              Λ
              w
            
            ⁢
            
              
                w
                _
              
              m
            
          
        
      
    
  




The generalized inverse Gaussian distribution is given by (see B. Jørgensen, Statistical Properties of the Generalized Inverse Gaussian Distribution, Springer-Verlag, 1982):




  
    
      
        N
        
          -
          1
        
      
      ⁡
      
        (
        
          
            x
            |
            v
          
          ,
          χ
          ,
          φ
        
        )
      
    
    =
    
      
        1
        
          Z
          ⁡
          
            (
            
              v
              ,
              χ
              ,
              φ
            
            )
          
        
      
      ⁢
      
        x
        
          v
          -
          1
        
      
      ⁢
      
        e
        
          -
          
            1
            2
          
        
      
      ⁢
      
        e
        
          
            -
            
              1
              2
            
          
          ⁢
          
            (
            
              
                χ
                ⁢
                
                  
                
                ⁢
                
                  x
                  
                    -
                    1
                  
                
              
              +
              
                φ
                ⁢
                
                  
                
                ⁢
                x
              
            
            )
          
        
      
    
  




  where




  
    
      Z
      ⁡
      
        (
        
          v
          ,
          χ
          ,
          φ
        
        )
      
    
    =
    
      2
      ⁢
      
        
          (
          
            χ
            /
            φ
          
          )
        
        
          v
          /
          2
        
      
      ⁢
      
        
          K
          v
        
        ⁡
        
          (
          
            
              χ
              ⁢
              
                
              
              ⁢
              φ
            
          
          )
        
      
    
  



with Kν(.) denoting the modified Bessel function of the second kind with index νε. The following expectations are useful:





  
    
      〈
      x
      〉
    
    =
    
      
        
          χ
          φ
        
      
      ⁢
      
        
          R
          v
        
        ⁡
        
          (
          
            
              χ
              ⁢
              
                
              
              ⁢
              φ
            
          
          )
        
      
    
  
  ,
  
    

  
  ⁢
  
    
      〈
      
        x
        
          -
          1
        
      
      〉
    
    =
    
      
        
          φ
          χ
        
      
      ⁢
      
        
          R
          
            -
            v
          
        
        ⁡
        
          (
          
            
              χ
              ⁢
              
                
              
              ⁢
              φ
            
          
          )
        
      
    
  
  ,




and





  
    
      〈
      
        ln
        ⁢
        
          
        
        ⁢
        x
      
      〉
    
    =
    
      
        ln
        ⁢
        
          
            χ
            φ
          
        
      
      +
      
        
          
            d
            ln
          
          ⁢
          
            
          
          ⁢
          
            
              K
              v
            
            (
            
              
                χ
                ⁢
                
                  
                
                ⁢
                φ
              
            
          
        
        
          d
          v
        
      
    
  
  ,




where we defined Rν(.)=Kν+1(.)/Kν(.). When χ=0 and ν>0, the generalized inverse Gaussian reduces to the Gamma:





  
    G
    ⁢
    
      
    
    ⁢
    
      a
      ⁡
      
        (
        
          
            x
            |
            a
          
          ,
          b
        
        )
      
    
  
  =
  
    
      
        b
        a
      
      
        Γ
        ⁡
        
          (
          a
          )
        
      
    
    ⁢
    
      x
      
        a
        -
        1
      
    
    ⁢
    
      e
      
        -
        bx
      
    
  




where a, b>0 and Γ(.) is the (complete) gamma function. It is straightforward to verify this result by setting a=ν and b=φ/2, and noting that limz→0 Kν(z)=Γ(ν)2ν−1z−ν for ν>0.

The RR embodiment employing both Student-t priors on the features and Gaussian Scale Mixture noise is implemented as follows. We consider a structured variational approximation for the case where both the noise and the priors are Gaussian scale mixtures. It can be shown that the form of the variational posterior that arises is given by Equations (8) and (9) with parameters now defined by:



  
    
      
        φ
        _
      
      n
    
    =
    
      τ
      ⁢
      
        
          S
          _
        
        n
        
          -
          1
        
      
      ⁢
      
        Σ
        
          l
          n
        
      
      ⁢
      
        
          β
          _
        
        
          m
          l
        
      
      ⁢
      
        
          w
          _
        
        
          m
          l
        
      
      ⁢
      
        r
        l
      
    
  




  
    
      
        S
        _
      
      n
    
    =
    
      
        
          τΣ
          
            l
            n
          
        
        ⁢
        
          〈
          
            
              β
              
                m
                l
              
            
            ⁢
            
              w
              
                m
                l
              
            
            ⁢
            
              w
              
                m
                l
              
              T
            
          
          〉
        
      
      +
      
        Λ
        φ
      
    
  




  
    
      
        w
        _
      
      m
    
    =
    
      τ
      ⁢
      
        
          R
          _
        
        m
        
          -
          1
        
      
      ⁢
      
        Σ
        
          l
          m
        
      
      ⁢
      
        
          α
          _
        
        
          n
          l
        
      
      ⁢
      
        
          φ
          _
        
        
          n
          l
        
      
      ⁢
      
        r
        l
      
    
  




  
    
      
        R
        _
      
      m
    
    =
    
      
        
          τΣ
          
            l
            m
          
        
        ⁢
        
          〈
          
            
              α
              
                n
                l
              
            
            ⁢
            
              φ
              
                n
                l
              
            
            ⁢
            
              φ
              
                n
                l
              
              T
            
          
          〉
        
      
      +
      
        Λ
        w
      
    
  



The variational posteriors for the scale parameters are Gamma distributions with parameters given by:




  
    
      a
      n
    
    =
    
      
        a
        0
      
      +
      1
    
  




  
    
      b
      n
    
    =
    
      
        b
        0
      
      +
      
        
          τΣ
          
            l
            n
          
        
        ⁢
        
          〈
          
            
              
                β
                
                  m
                  l
                
              
              ⁡
              
                (
                
                  
                    r
                    l
                  
                  -
                  
                    
                      
                        φ
                        _
                      
                      n
                      T
                    
                    ⁢
                    
                      w
                      
                        m
                        l
                      
                    
                  
                
                )
              
            
            2
          
          〉
        
      
      +
      
        
          
            φ
            _
          
          n
          T
        
        ⁢
        
          Λ
          φ
        
        ⁢
        
          
            φ
            _
          
          n
        
      
    
  




  
    
      c
      m
    
    =
    
      
        c
        0
      
      +
      1
    
  




  
    
      d
      m
    
    =
    
      
        d
        0
      
      +
      
        
          τΣ
          
            l
            m
          
        
        ⁢
        
          〈
          
            
              
                α
                
                  n
                  l
                
              
              ⁡
              
                (
                
                  
                    r
                    l
                  
                  -
                  
                    
                      φ
                      
                        n
                        l
                      
                      T
                    
                    ⁢
                    
                      
                        w
                        _
                      
                      m
                    
                  
                
                )
              
            
            2
          
          〉
        
        ⁢
        
          
            w
            _
          
          m
          T
        
        ⁢
        
          Λ
          m
        
        ⁢
        
          
            w
            _
          
          m
        
      
    
  



The BMF estimation is carried out as follows. The parameters are estimated by type II maximum likelihood (or empirical Bayes). The updates are obtained by direct maximization of −.
When the noise is a Gaussian scale mixture and the priors on the latent features are Student-t distributions, the updates for the parameters are given by:



  
    
      
        τ
        
          -
          1
        
      
      ←
      
        
          
            ∑
            l
          
          ⁢
          
            〈
            
              
                α
                
                  n
                  l
                
              
              ⁢
              
                
                  
                    β
                    
                      m
                      l
                    
                  
                  ⁡
                  
                    (
                    
                      
                        r
                        l
                      
                      -
                      
                        
                          φ
                          
                            n
                            l
                          
                          T
                        
                        ⁢
                        
                          ω
                          
                            m
                            l
                          
                        
                      
                    
                    )
                  
                
                2
              
            
            〉
          
        
        L
      
    
    ,
    
      

    
    ⁢
    
      
        σ
        k
        2
      
      ←
      
        
          
            ∑
            n
          
          ⁢
          
            
              〈
              
                
                  α
                  n
                
                ⁢
                
                  φ
                  n
                
                ⁢
                
                  φ
                  n
                  T
                
              
              〉
            
            kk
          
        
        N
      
    
    ,
    
      
    
    ⁢
    
      
        b
        0
      
      ←
      
        
          
            a
            0
          
          ⁢
          N
        
        
          
            ∑
            n
          
          ⁢
          
            
              α
              _
            
            n
          
        
      
    
  




  
    
      
        ρ
        k
        2
      
      ←
      
        
          
            ∑
            m
          
          ⁢
          
            
              〈
              
                
                  β
                  m
                
                ⁢
                
                  ω
                  m
                
                ⁢
                
                  ω
                  m
                  T
                
              
              〉
            
            kk
          
        
        M
      
    
    ,
    
      
    
    ⁢
    
      
        d
        0
      
      ←
      
        
          
            c
            0
          
          ⁢
          M
        
        
          
            ∑
            m
          
          ⁢
          
            
              β
              _
            
            m
          
        
      
    
  



Parameter ao is suitably found by solving the nonlinear equation





  
    
      ∑
      n
    
    ⁢
    
      {
      
        
          ln
          ⁢
          
            
              b
              0
            
            2
          
        
        +
        
          〈
          
            ln
            ⁢
            
              
            
            ⁢
            
              α
              n
            
          
          〉
        
        -
        
          ψ
          ⁡
          
            (
            
              
                a
                0
              
              2
            
            )
          
        
      
      }
    
  
  =
  0




by line search. Parameter c0 is updated in the same manner.

When the noise is Gaussian, the update for the precision is replaced by:




  
    τ
    
      -
      1
    
  
  ←
  
    
      
        ∑
        l
      
      ⁢
      
        〈
        
          
            (
            
              
                r
                l
              
              -
              
                
                  φ
                  
                    n
                    l
                  
                  T
                
                ⁢
                
                  ω
                  
                    m
                    l
                  
                
              
            
            )
          
          2
        
        〉
      
    
    L
  




When the priors on the latent features are Gaussians, the updates for the diagonal elements φ and ω are replaced by:



  
    
      σ
      k
      2
    
    ←
    
      
        
          ∑
          n
        
        ⁢
        
          
            〈
            
              
                φ
                n
              
              ⁢
              
                φ
                n
                T
              
            
            〉
          
          kk
        
      
      N
    
  




  and




  
    
      ρ
      k
      2
    
    ←
    
      
        
          ∑
          m
        
        ⁢
        
          
            〈
            
              
                ω
                m
              
              ⁢
              
                ω
                m
                T
              
            
            〉
          
          kk
        
      
      M
    
  



FIG. 3 shows graphical models for the different matrix factorizations. The embodiment employing both Gaussian priors and Gaussian noise (e.g., a “GG” model) is obtained when only considering the solid arrows of FIG. 3. The GR embodiment employing Student-t priors and Gaussian noise is obtained when considering the solid and dotted arrows. The RG embodiment employing Gaussian priors and Gaussian Scale Mixture noise is obtained when considering the solid and the dashed arrows. Finally, the RR embodiment employing both Student-t priors and Gaussian Scale Mixture noise is obtained when considering all the arrows.
In practice, it is important to model the user- (or item-) specific offsets. These can be incorporated into the model by appending a ‘1’ to the latent item feature ωm (or the latent user feature φn). Also, the model is only identifiable up to a rescaling of Φ and Ω. Thus, we can fix ω to the identity matrix IK and only optimize with respect to φ. In order to scale up the model to a large K, it is convenient to restrict Sn and m to be diagonal matrices. Hence, it is only required to store K variance parameters per user and per item, while the computational cost of inverting these matrices is reduced from (K3) to (K).
The disclosed recommender approaches have been tested on two datasets, referred to herein as the MovieLens dataset and the JesterJoke dataset. The MovieLens dataset (see www.grouplens.org/node/73) contains movie ratings by MovieLens users. The ratings are ordinal values on the scale 1 to 5. Users have rated at least 20 movies. The MovieLens 100K and the MovieLens 1 Million rating data sets were considered. The former consists of approximately 100,000 ratings by 943 users on 1682 movies, while the latter contains 1,000,209 ratings of approximately 3,900 movies by 6,040 users.
The JesterJoke dataset is described, for example, in Goldberg et al., “Eigentaste: A constant time collaborative filtering algorithm”, Information Retrieval, 4(2):133-151, 2001). The Jester-1 data set contains 4.1 million ratings of 100 jokes from 73,421 users. Tests used Jester-1-3, which is a subset of Jester-1 containing ratings of 24,938 users who have rated between 15 and 35 jokes. These ratings are on a continuous scale from −10.0 to 10.0.
The experimental setup was as follows. We randomly choose 70% of the ratings for training and use the remaining ratings as test data. Every movie and every user appears at least once in the training set. In the MovieLens data sets, we include only movies that have been rated at least three times. We are interested in evaluating the effect of the noise model and of the priors imposed on the latent factors. To this effect, we compare the following models on the rating prediction task: (see FIG. 3 for the graphical representation of the models): (1) the GG model (Gaussian noise, Gaussian priors, see Lim et al., “Variational Bayesian approach to movie rating prediction”, in KDD Cup and Workshop, 2007); (2) the RG model (Gaussian scale mixture noise, Gaussian priors); (3) the GR model (Gaussian noise, Student-t priors); and (4) the RR model (Gaussian scale mixture noise, Student-t priors). (In the embodiment or label notation, “G” denotes “Gaussian” while “R” denotes a heavy tailed distribution). Additionally, results are presented for the mean field approximation of the GR model, referred to as GR-mf in the following. Comparing the performance of GR and GR-mf clarifies the gains that can be obtained through the use of a structured variational inference algorithm in place of a standard mean field algorithm.
Prediction was done by using point estimates of both Φ and Ω. We compare the models in terms of predictive performance based on several metrics. The root-mean-squared-error (RMSE) is given by:




  RMSE
  =
  
    
      
        1
        T
      
      ⁢
      
        
          ∑
          t
        
        ⁢
        
          
            (
            
              
                r
                t
              
              -
              
                
                  
                    φ
                    _
                  
                  
                    n
                    t
                  
                  T
                
                ⁢
                
                  
                    ω
                    _
                  
                  
                    m
                    t
                  
                
              
            
            )
          
          2
        
      
    
  




where t indexes the test ratings. This metric is closely related to the Gaussian noise model. Another metric used was the Mean-absolute-error (MAE) given by:





  MAE
  =
  
    
      1
      T
    
    ⁢
    
      
        ∑
        t
      
      ⁢
      
        
        
          
            r
            t
          
          -
          
            
              
                φ
                _
              
              
                n
                t
              
              T
            
            ⁢
            
              
                ω
                _
              
              
                m
                t
              
            
          
        
        
      
    
  




Another metric used was the Ordinal log-likelihood (OLL). This metric is only used in the case of the MovieLens data. Since the true ratings are ordinal, the predicted rating needs to be rounded off to predict a value in the support of the original ratings. It is possible to compute the likelihood of the predicted value lying within the boundaries corresponding to the true rating. We compute this log-likelihood in the same fashion as described in Chu et al., “Gaussian processes for ordinal regression”, Journal of Machine Learning Research, 6(1):1019-1041, 2005. Let us denote the boundaries defining the ordinal scale {b0, b1, b2, b3, b4, b5}. In our experiments we do not attempt to optimize these values, but used b0=−∞, bi=i+0.5, b5=∞. The ordinal likelihood for the Gaussian noise model is given by:





  
    P
    ⁡
    
      (
      
        
          r
          t
        
        =
        i
      
      )
    
  
  ≈
  
    
      ∫
      
        
          b
          
            i
            -
            1
          
        
        -
        
          
            
              φ
              _
            
            
              n
              t
            
            T
          
          ⁢
          
            
              ω
              _
            
            
              m
              t
            
          
        
      
      
        
          b
          i
        
        -
        
          
            
              φ
              _
            
            
              n
              t
            
            T
          
          ⁢
          
            
              ω
              _
            
            
              m
              t
            
          
        
      
    
    ⁢
    
      
        N
        ⁡
        
          (
          
            
              
                ε
                t
              
              |
              0
            
            ,
            
              〈
              τ
              〉
            
          
          )
        
      
      ⁢
      
        
      
      ⁢
      
        d
        
          ε
          t
        
      
    
  




where εt is the prediction error (or residual) and iε{1,2,3,4,5}. For the Gaussian scale mixture noise model, we use again point estimates, leading to the following approximation:





  
    P
    ⁡
    
      (
      
        
          r
          t
        
        =
        i
      
      )
    
  
  ≈
  
    
      ∫
      
        
          b
          
            i
            -
            1
          
        
        -
        
          
            
              φ
              _
            
            
              n
              t
            
            T
          
          ⁢
          
            
              ω
              _
            
            
              m
              t
            
          
        
      
      
        
          b
          i
        
        -
        
          
            
              φ
              _
            
            
              n
              t
            
            T
          
          ⁢
          
            
              ω
              _
            
            
              m
              t
            
          
        
      
    
    ⁢
    
      
        N
        ⁡
        
          (
          
            
              
                ε
                t
              
              |
              0
            
            ,
            
              
                
                  α
                  _
                
                
                  n
                  t
                
              
              ⁢
              
                
                  β
                  _
                
                
                  m
                  t
                
              
              ⁢
              
                〈
                τ
                〉
              
            
          
          )
        
      
      ⁢
      
        
      
      ⁢
      
        d
        
          ε
          t
        
      
    
  




The RMSE, MAE and OLL values obtained for MovieLens 100 k data are shown in TABLE 1. The dimension of the low-rank approximation is set to K=30. Considering the GG model as the reference method, we see that the performance improves on all metrics when a Student-t prior is imposed on the latent features (the GR model) or when a Gaussian scale mixture noise is considered (the RG model). The combination of both (the RR model) further improves the results. The mean field approximation performs worse than the structure variational one. This result, however, is to be mitigated given the fact that GR-mf performs better than GR on MovieLens Million data (TABLE 2).







TABLE 1







Test results on the MovieLens 100 k dataset using K = 30












Model
RMSE
MAE
OLL







RR
0.900
0.613
−37638



RG
0.901
0.674
−37054



GR
0.906
0.621
−38193



GR-mf
0.907
0.710
−38312



GG
0.912
0.714
−38387

















TABLE 2







Test results on the MovieLens Million rating data using K = 20










Model
RMSE
MAE
OLL





RR
0.845
0.661
−356254


RG
0.846
0.662
−350607


GR
0.860
0.673
−366028


GR-mf
0.858
0.670
−366109


GG
0.851
0.666
−364736









We conducted two additional experiments on the Movielens 100K data set to check whether the priors on the scale variables αn and βm should depend on the number of ratings Ln and Lm. We observed that priors independent of the data yielded a lower test RMSE.
The Gaussian scale mixture noise models (RG and RR) performed significantly better for all metrics compared to the Gaussian noise models (GG and GR). This suggests that a user- and item-specific rescaling is beneficial. We obtained better performances in terms of RMSE and similar ones in terms of MAE as the ones reported in Nicolas et al., “Collaborative filtering with interlaced generalized linear models”, Neurocomputing, 71:1300-1310, 2008. That reference considered generalized bilinear forms. The number of latent factors K was not optimized for performances, but the BMF model is nearly optimum in this case: the best performance obtained with GG is for K=30, with RMSE=0.849, MAE=0.664 and OLL=−363690. While better than the results shown in TABLE 2, these are still worse than the ones obtained for the RG and RR models which employ Gaussian scale mixture noise models.







TABLE 3







Test results on Jester-1-3 dataset for K = 15











Model
RMSE
MAE







RR
4.454
3.439



RG
4.456
3.468



GR
4.463
3.451



GG
4.406
3.480










We also tested the algorithm on the Jester-1-3 data sets as summarized in TABLE 3. We note that the GG model performs best in terms of RMSE, but worst in terms of MAE. The RMSE corresponds exactly to the loss that is minimized in Gaussian BMF; this means that using a Gaussian model is asymptotically optimal. Since only users with at least 15 ratings were selected in this dataset, the variance reduction due to the use of a robust estimator is not large enough to improve the test RMSE. Although RMSE is the most commonly used metric in collaborative filtering, it is not a robust measure for assessing the model predictive performance (see Benjamin Marlin, Missing Data Problems in Machine Learning. PhD thesis, Department of Computer Science, University of Toronto, 2008), especially when the distribution of the data is peaked and even if they take values on a finite domain. Finally, note that we observe the same hierarchy of models in terms of MAE as the one obtained on the MovieLens 100 k data, namely RR<GR<RG<GG.
It will be appreciated that various of the above-disclosed and other features and functions, or alternatives thereof, may be desirably combined into many other different systems or applications. Also that various presently unforeseen or unanticipated alternatives, modifications, variations or improvements therein may be subsequently made by those skilled in the art which are also intended to be encompassed by the following claims.

## Claims

1. An apparatus comprising:
an electronic data processing device configured to perform a recommender method including:
performing Bayesian Matrix Factorization (BMF) on a matrix having user and item dimensions using Gaussian scale mixture priors comprising Student-t priors to train a probabilistic collaborative filtering model; and
generating a recommendation for a user comprising a predicted item rating or identification of one or more recommended items using the probabilistic collaborative filtering model.

2. The apparatus of claim 1, wherein the BMF is performed using variance values for the Gaussian scale mixture priors that are heteroscedastic across the matrix.

3. The apparatus of claim 1, wherein the Gaussian scale mixture priors have variance values that include (1) a row-dependent variance component that depends upon the matrix row and (2) a column-dependent variance component that depends upon the matrix column.

4. The apparatus of claim 1, wherein the BMF adds noise that varies with both row and column position in the matrix.

5. The apparatus of claim 1, further comprising:
an online retail store website embodied by one or more Internet-based server computers, the online retail store website displaying the recommendation to the user via an electronic device having a display that is operatively connected with the online retail store website via the Internet.

6. The apparatus of claim 5, wherein the electronic data processing device is said one or more Internet-based server computers.

7. A storage medium storing instructions executable by an electronic data processing device to perform a recommender method including: (i) performing Bayesian Matrix Factorization (BMF) on a matrix having user and item dimensions using priors having heteroscedastic noise terms that vary with both row and column position in the matrix to train a probabilistic collaborative filtering model and (ii) generating a recommendation for a user comprising a predicted item rating or identification of one or more recommended items using the probabilistic collaborative filtering model.

8. The storage medium of claim 7, wherein the priors comprise Gaussian priors.

9. The storage medium of claim 7, wherein the priors comprise non-Gaussian priors.

10. The storage medium of claim 9, wherein the non-Gaussian priors comprise Gaussian scale mixture priors.

11. The storage medium of claim 10, wherein the heteroscedastic noise terms comprise variance values of the Gaussian scale mixture priors that include (1) a row-dependent variance component that depends upon the matrix row and (2) a column-dependent variance component that depends upon the matrix column.

12. The storage medium of claim 9, wherein the non-Gaussian priors are Student-t priors.

13. A method comprising:
performing Bayesian Matrix Factorization (BMF) on a matrix having user and item dimensions and matrix elements containing user ratings for items made by users wherein the BMF employs priors that include (1) a row-dependent variance component that depends upon the matrix row and (2) a column-dependent variance component that depends upon the matrix column to train a probabilistic collaborative filtering model; and
generating a recommendation for a user comprising a predicted item rating or identification of one or more recommended items using the probabilistic collaborative filtering model;
wherein the performing and the generating are performed by an electronic data processing device.

14. The method of claim 13, wherein the priors comprise non-Gaussian priors.

15. The method of claim 14, wherein the non-Gaussian priors comprise Gaussian scale mixture priors.

16. The method of claim 13, wherein the priors comprise Student-t priors.

17. The method of claim 13, wherein one of:
(I) the rows of the matrix correspond to users and the row-dependent variance component depends on the number of user ratings made by the user corresponding to the row, and
(ii) the columns of the matrix correspond to users and the column-dependent variance component depends on the number of user ratings made by the user corresponding to the column.

18. The method of claim 13, wherein one of:
(I) the columns of the matrix correspond to items and the column-dependent variance component depends on the number of user ratings for the item corresponding to the column, and
(ii) the rows of the matrix correspond to items and the row-dependent variance component depends on the number of user ratings for the item corresponding to the row.