Matrix factorization (recommender systems)

For the decomposition of matrices as studied in linear algebra, see Matrix decomposition.

Recommender systems
Concepts
Collective intelligence Relevance Star ratings Long tail
Methods and challenges
Cold start Collaborative filtering Dimensionality reduction Implicit data collection Item-item collaborative filtering Matrix factorization Preference elicitation Similarity search Social loafing
Implementations
Collaborative search engine Content discovery platform Decision support system Music Genome Project Product finder
Research
GroupLens Research MovieLens Netflix Prize

Matrix factorization is a class of collaborative filtering algorithms used in recommender systems. Matrix factorization algorithms work by decomposing the user-item interaction matrix into the product of two lower dimensionality rectangular matrices. This family of methods became widely known during the Netflix prize challenge due to its effectiveness as reported by Simon Funk in his 2006 blog post, where he shared his findings with the research community.

Techniques

The idea behind matrix factorization is to represent users and items in a lower dimensional latent space . Since the initial work by Funk in 2006 a multitude of matrix factorization approaches have been proposed for recommender systems. Some of the most used and simpler ones are listed in the following sections.

Funk SVD

The original algorithm proposed by Simon Funk in his blog post factorized the user-item rating matrix as the product of two lower dimensional matrices, the first one has a row for each user, while the second has a column for each item. The row or column associated to a specific user or item is referred to as latent factors. Note that, despite its name, in FunkSVD no singular value decomposition is applied. The predicted ratings can be computed as ${\tilde {R}}=HW$, where ${\tilde {R}}\in \mathbb {R} ^{users\times items}$ is the user-item rating matrix, $H\in \mathbb {R} ^{users\times latentfactors}$ contains the user's latent factors and $W\in \mathbb {R} ^{latentfactors\times items}$ the item's latent factors.

Specifically, the predicted rating user u will give to item i is computed as:

${\tilde {r}}_{ui}=\sum _{f=0}^{nfactors}H_{u,f}W_{f,i}$

It is possible to tune the expressive power of the model by changing the number of latent factors. It has been demonstrated that a matrix factorization with one latent factor is equivalent to a most popular or top popular recommender (e.g. recommends the items with the most interactions without any personalization). Increasing the number of latent factor will improve personalization, therefore recommendation quality, until the number of factors becomes too high, at which point the model starts to overfit and the recommendation quality will decrease. A common strategy to avoid overfitting is to add regularization terms to the objective function. FunkSVD was developed as a rating prediction problem, therefore it uses explicit numerical ratings as user-item interactions.

All things considered, FunkSVD minimizes the following objective function:

${\underset {H,W}{\operatorname {arg\,min} }}\,\|R-{\tilde {R}}\|_{\rm {F}}+\alpha \|H\|+\beta \|W\|$

Where $\|.\|_{\rm {F}}$ is defined to be the frobenius norm whereas the other norms might be either frobenius or another norm depending on the specific recommending problem.

SVD++

While FunkSVD is able to provide very good recommendation quality, its ability to use only explicit numerical ratings as user-items interactions constitutes a limitation. Modern day recommender systems should exploit all available interactions both explicit (e.g. numerical ratings) and implicit (e.g. likes, purchases, skipped, bookmarked). To this end SVD++ was designed to take into account implicit interactions as well. Compared to FunkSVD, SVD++ takes also into account user and item bias.

The predicted rating user u will give to item i is computed as:

${\tilde {r}}_{ui}=\mu +b_{i}+b_{u}+\sum _{f=0}^{nfactors}H_{u,f}W_{f,i}$

SVD++ has however some disadvantages, with the main drawback being that this method is not model-based. This means that if a new user is added, the algorithm is incapable of modeling it unless the whole model is retrained. Even though the system might have gathered some interactions for that new user, it's latent factors are not available and therefore no recommendations can be computed. This is an example of a cold-start problem, that is the recommender cannot deal efficiently with new users or items and specific strategies should be put in place to handle this disadvantage.

A possible way to address this cold start problem is to modify SVD++ in order for it to become a model-based algorithm, therefore allowing to easily manage new items and new users.

As previously mentioned in SVD++ we don't have the latent factors of new users, therefore it is necessary to represent them in a different way. The user's latent factors represent the preference of that user for the corresponding item's latent factors, therefore user's latent factors can be estimated via the past user interactions. If the system is able to gather some interactions for the new user it is possible to estimate its latent factors. Note that this does not entirely solve the cold-start problem, since the recommender still requires some reliable interactions for new users, but at least there is no need to recompute the whole model every time. It has been demonstrated that this formulation is almost equivalent to a SLIM model, which is an item-item model based recommender.

${\tilde {r}}_{ui}=\mu +b_{i}+b_{u}+\sum _{f=0}^{nfactors}{\biggl (}\sum _{j=0}^{nitems}r_{uj}W_{j,f}{\biggr )}W_{f,i}$

With this formulation, the equivalent item-item recommender would be ${\tilde {R}}=RS=RW^{\rm {T}}W$. Therefore the similarity matrix is symmetric.

Asymmetric SVD

Asymmetric SVD aims at combining the advantages of SVD++ while being a model based algorithm, therefore being able to consider new users with a few ratings without needing to retrain the whole model. As opposed to the model-based SVD here the user latent factor matrix H is replaced by Q, which learns the user's preferences as function of their ratings.

The predicted rating user u will give to item i is computed as:

${\tilde {r}}_{ui}=\mu +b_{i}+b_{u}+\sum _{f=0}^{nfactors}\sum _{j=0}^{nitems}r_{uj}Q_{j,f}W_{f,i}$

With this formulation, the equivalent item-item recommender would be ${\tilde {R}}=RS=RQ^{\rm {T}}W$. Since matrices Q and W are different the similarity matrix is asymmetric, hence the name of the model.

Hybrid MF

In recent years many other matrix factorization models have been developed to exploit the ever increasing amount and variety of available interaction data and use cases. Hybrid matrix factorization algorithms are capable of merging explicit and implicit interactions or both content and collaborative data

See also

• Collaborative filtering
• Recommender system