Matrix factorization (recommender systems)

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

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. ^[1] 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, ^[2] where he shared his findings with the research community. The prediction results can be improved by assigning different regularization weights to the latent factors based on items' popularity and users' activeness. ^[3]

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 MF

The original algorithm proposed by Simon Funk in his blog post ^[2] 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. ^[4] Note that, in Funk MF no singular value decomposition is applied, it is a SVD-like machine learning model. ^[2] The predicted ratings can be computed as ${\displaystyle {\tilde {R}}=HW}$, where ${\displaystyle {\tilde {R}}\in \mathbb {R} ^{{\text{users}}\times {\text{items}}}}$ is the user-item rating matrix, ${\displaystyle H\in \mathbb {R} ^{{\text{users}}\times {\text{latent factors}}}}$ contains the user's latent factors and ${\displaystyle W\in \mathbb {R} ^{{\text{latent factors}}\times {\text{items}}}}$ the item's latent factors.

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

${\displaystyle {\tilde {r}}_{ui}=\sum _{f=0}^{\text{n factors}}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 ^[5] 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 factors 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. ^{[6] [7]} Funk MF was developed as a rating prediction problem, therefore it uses explicit numerical ratings as user-item interactions.

All things considered, Funk MF minimizes the following objective function:

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

Where ${\displaystyle \|.\|_{\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. ^[8]

SVD++

While Funk MF 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. ^{[9] [10]} Compared to Funk MF, SVD++ takes also into account user and item bias.

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

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

Where ${\displaystyle \mu }$ refers to the overall average rating over all items and ${\displaystyle b_{i}}$ and ${\displaystyle b_{u}}$ refers to the observed deviation of the item ${\displaystyle i}$ and the user ${\displaystyle u}$ respectively from the average. ^[11] 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, its 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. ^[12]

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, ^[13] which is an item-item model based recommender.

${\displaystyle {\tilde {r}}_{ui}=\mu +b_{i}+b_{u}+\sum _{f=0}^{\text{n factors}}{\biggl (}\sum _{j=0}^{\text{n items}}r_{uj}W_{j,f}^{T}{\biggr )}W_{f,i}}$

With this formulation, the equivalent item-item recommender would be ${\displaystyle {\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. ^[14]

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

${\displaystyle {\tilde {r}}_{ui}=\mu +b_{i}+b_{u}+\sum _{f=0}^{\text{n factors}}\sum _{j=0}^{\text{n items}}r_{uj}Q_{j,f}W_{f,i}}$

With this formulation, the equivalent item-item recommender would be ${\displaystyle {\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.

Group-specific SVD

A group-specific SVD can be an effective approach for the cold-start problem in many scenarios. ^[6] It clusters users and items based on dependency information and similarities in characteristics. Then once a new user or item arrives, we can assign a group label to it, and approximates its latent factor by the group effects (of the corresponding group). Therefore, although ratings associated with the new user or item are not necessarily available, the group effects provide immediate and effective predictions.

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

${\displaystyle {\tilde {r}}_{ui}=\sum _{f=0}^{\text{n factors}}(H_{u,f}+S_{v_{u},f})(W_{f,i}+T_{f,j_{i}})}$

Here ${\displaystyle v_{u}}$ and ${\displaystyle j_{i}}$ represent the group label of user u and item i, respectively, which are identical across members from the same group. And ${\displaystyle S}$ and ${\displaystyle T}$ are matrices of group effects. For example, for a new user ${\displaystyle u_{new}}$ whose latent factor ${\displaystyle H_{u_{new}}}$ is not available, we can at least identify their group label ${\displaystyle v_{u_{new}}}$, and predict their ratings as:

${\displaystyle {\tilde {r}}_{u_{new}i}=\sum _{f=0}^{\text{n factors}}S_{v_{u_{new}},f}(W_{f,i}+T_{f,j_{i}})}$

This provides a good approximation to the unobserved ratings.

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 ^[15] or both content and collaborative data ^{[16] [17] [18]}

Deep-learning MF

In recent years a number of neural and deep-learning techniques have been proposed, some of which generalize traditional Matrix factorization algorithms via a non-linear neural architecture. ^[19] While deep learning has been applied to many different scenarios: context-aware, sequence-aware, social tagging etc. its real effectiveness when used in a simple Collaborative filtering scenario has been put into question. Systematic analysis of publications applying deep learning or neural methods to the top-k recommendation problem, published in top conferences (SIGIR, KDD, WWW, RecSys, IJCAI), has shown that on average less than 40% of articles are reproducible, with as little as 14% in some conferences. Overall the studies identify 26 articles, only 12 of them could be reproduced and 11 of them could be outperformed by much older and simpler properly tuned baselines. The articles also highlights a number of potential problems in today's research scholarship and call for improved scientific practices in that area. ^{[20] [21]} Similar issues have been spotted also in sequence-aware recommender systems. ^[22]

See also

• Collaborative filtering
• Recommender system

References

1. Koren, Yehuda; Bell, Robert; Volinsky, Chris (August 2009). "Matrix Factorization Techniques for Recommender Systems". Computer. 42 (8): 30–37. CiteSeerX   10.1.1.147.8295 . doi:10.1109/MC.2009.263. S2CID   58370896.
2. Funk, Simon. "Netflix Update: Try This at Home".
3. ChenHung-Hsuan; ChenPu (2019-01-09). "Differentiating Regularization Weights – A Simple Mechanism to Alleviate Cold Start in Recommender Systems". ACM Transactions on Knowledge Discovery from Data. 13: 1–22. doi:10.1145/3285954. S2CID   59337456.
4. Agarwal, Deepak; Chen, Bee-Chung (28 June 2009). "Regression-based latent factor models". Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining – KDD '09. ACM. pp. 19–28. doi:10.1145/1557019.1557029. ISBN   9781605584959. S2CID   17484284.
5. Jannach, Dietmar; Lerche, Lukas; Gedikli, Fatih; Bonnin, Geoffray (2013). "What Recommenders Recommend – an Analysis of Accuracy, Popularity, and Sales Diversity Effects". User Modeling, Adaptation, and Personalization. Lecture Notes in Computer Science. Vol. 7899. Springer Berlin Heidelberg. pp. 25–37. CiteSeerX   10.1.1.465.96 . doi:10.1007/978-3-642-38844-6_3. ISBN   978-3-642-38843-9.
6. Bi, Xuan; Qu, Annie; Wang, Junhui; Shen, Xiaotong (2017). "A group-specific recommender system". Journal of the American Statistical Association. 112 (519): 1344–1353. doi:10.1080/01621459.2016.1219261. S2CID   125187672.
7. Zhu, Yunzhang; Shen, Xiaotong; Ye, Changqing (2016). "Personalized prediction and sparsity pursuit in latent factor models" (PDF). Journal of the American Statistical Association. 111 (513): 241–252. doi:10.1080/01621459.2016.1219261. S2CID   125187672.
8. Paterek, Arkadiusz (2007). "Improving regularized singular value decomposition for collaborative filtering" (PDF). Proceedings of KDD Cup and Workshop.
9. Cao, Jian; Hu, Hengkui; Luo, Tianyan; Wang, Jia; Huang, May; Wang, Karl; Wu, Zhonghai; Zhang, Xing (2015). Distributed Design and Implementation of SVD++ Algorithm for E-commerce Personalized Recommender System. Communications in Computer and Information Science. Vol. 572. Springer Singapore. pp. 30–44. doi:10.1007/978-981-10-0421-6_4. ISBN   978-981-10-0420-9.
10. Jia, Yancheng (September 2014). "Users' brands preference based on SVD++ in recommender systems". 2014 IEEE Workshop on Advanced Research and Technology in Industry Applications (WARTIA). IEEE. pp. 1175–1178. doi:10.1109/wartia.2014.6976489. ISBN   978-1-4799-6989-0. S2CID   742206.
11. Koren, Yehuda; Bell, Robert; Volinsky, Chris (August 2009). "Matrix factorization techniques for recommender systems" (PDF). Computer: 45.
12. Kluver, Daniel; Konstan, Joseph A. (6 October 2014). "Evaluating recommender behavior for new users". Proceedings of the 8th ACM Conference on Recommender systems – Rec Sys '14. ACM. pp. 121–128. doi:10.1145/2645710.2645742. ISBN   9781450326681. S2CID   18509558.
13. Zheng, Yong; Mobasher, Bamshad; Burke, Robin (6 October 2014). "CSLIM". CSLIM: contextual SLIM recommendation algorithms. ACM. pp. 301–304. doi:10.1145/2645710.2645756. ISBN   9781450326681. S2CID   15931532.
14. Pu, Li; Faltings, Boi (12 October 2013). "Understanding and improving relational matrix factorization in recommender systems". Proceedings of the 7th ACM conference on Recommender systems – Rec Sys '13. ACM. pp. 41–48. doi:10.1145/2507157.2507178. ISBN   9781450324090. S2CID   14106198.
15. Zhao, Changwei; Sun, Suhuan; Han, Linqian; Peng, Qinke (2016). "Hybrid Matrix Factorization for Recommender Systems in Social Networks". Neural Network World. 26 (6): 559–569. doi: 10.14311/NNW.2016.26.032 .
16. Zhou, Tinghui; Shan, Hanhuai; Banerjee, Arindam; Sapiro, Guillermo (26 April 2012). "Kernelized Probabilistic Matrix Factorization: Exploiting Graphs and Side Information". Proceedings of the 2012 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics. pp. 403–414. doi:10.1137/1.9781611972825.35. ISBN   978-1-61197-232-0.
17. Adams, Ryan Prescott; Dahl, George E.; Murray, Iain (25 March 2010). "Incorporating Side Information in Probabilistic Matrix Factorization with Gaussian Processes 1003.4944". arXiv: 1003.4944 [stat.ML].
18. Fang, Yi; Si, Luo (27 October 2011). "Matrix co-factorization for recommendation with rich side information and implicit feedback". Proceedings of the 2nd International Workshop on Information Heterogeneity and Fusion in Recommender Systems – Het Rec '11. ACM. pp. 65–69. doi:10.1145/2039320.2039330. ISBN   9781450310277. S2CID   13850687.
19. He, Xiangnan; Liao, Lizi; Zhang, Hanwang; Nie, Liqiang; Hu, Xia; Chua, Tat-Seng (2017). "Neural Collaborative Filtering". Proceedings of the 26th International Conference on World Wide Web. International World Wide Web Conferences Steering Committee. pp. 173–182. arXiv: 1708.05031 . doi:10.1145/3038912.3052569. ISBN   9781450349130. S2CID   13907106 . Retrieved 16 October 2019.
20. Rendle, Steffen; Krichene, Walid; Zhang, Li; Anderson, John (22 September 2020). "Neural Collaborative Filtering vs. Matrix Factorization Revisited". Fourteenth ACM Conference on Recommender Systems. pp. 240–248. arXiv: 2005.09683 . doi: 10.1145/3383313.3412488 . ISBN   9781450375832.
21. Dacrema; Ferrari (2021). "A Troubling Analysis of Reproducibility and Progress in Recommender Systems Research". ACM Transactions on Information Systems. 39 (2): 39.2. arXiv: 1911.07698 . doi:10.1145/3434185. S2CID   208138060.
22. Ludewig, Malte; Mauro, Noemi; Latifi, Sara; Jannach, Dietmar (2019). "Performance comparison of neural and non-neural approaches to session-based recommendation". Proceedings of the 13th ACM Conference on Recommender Systems. ACM. pp. 462–466. doi: 10.1145/3298689.3347041 . ISBN   9781450362436.