Matrix Factorization – Singular Value Decomposition (SVD) Explained

This article will outline the intuition and the Python implementation of matrix factorization for recommendation systems. The following is the outline of the article.

Table of Contents

• Intuition behind Matrix Factorization
• Singular Value Decomposition (SVD)
• Mathematics of SVD
• Example Walkthrough
• Problem Statement
• Data
• Requirements
• Solution Architecture
• SVD Recommendation System Implementation
• Generate User-Item Matrix
• Calculate SVD
• Generate Recommendations
• Challenges
• Concluding Remarks
• Resources

Intuition behind Matrix Factorization

A recommendation engine is a subcategory of machine learning which aims to provide a rating for some user or item. Matrix factorization falls under the category of collaborative filtering in recommendation systems. Intuitively, collaborative filtering aims to identify items that a user A would like based on the interactions of other user(s) which are similar to user A. You can think of this as an optimization problem where we aim to find a method which yields the best ratings for a given product / user.

There are a variety of problems related to recommendation engines which are used across numerous companies and industries. When logging on Facebook / Meta, Instagram, Twitter, Pinterest, Amazon, etc. the platform recommends posts / items for you to interact with based on your own history and the history of other users who you’re similar to. Similarity is a broad term, you can be considered similar users because you have similar taste, follow the same people, like / interact with the same posts & users, etc.

The intuition behind matrix factorization is fairly simple, given some user-item matrix, you want to decompose that matrix such that you have a user matrix and an item matrix independently. This allows us to apply different regularization to each latent factor of the original matrix. For example, when products are songs, factors might measure the comparison between rap and country, count of times the song was played vs song duration, etc. The image below illustrates the decomposition of an input user-item (song) matrix M.

This approach was popularized by Simon Funk in 2006 due to its widespread popularity during the Netflix challenge [1]. Funk SVD is the name of the algorithm proposed by Simon Funk. Although SVD (support vector decomposition) is in the name, there are no SVD techniques applied to it [1].

Singular Value Decomposition (SVD)

Mathematics of SVD

Given some input matrix M, the formula for SVD can be outlined as seen below:

M : An m x n matrix which you want to decompose
U : An m x m complex unitary matrix (left singular vectors)
Σ : An m x n rectangular diagonal matrix (holds the eigenvalues)
V : An n x n complex unitary matrix (right singular vectors)

Step 1 : Transform the matrix M into a square matrix by multiplying it by its transpose : M*Mᵀ

Step 2 : Calculate the eigenvalues & eigenvectors of matrix M*Mᵀ. The results of this will correspond to the Σ and U matrices.

Eigenvector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted by λ, is the factor by which the eigenvector is scaled.

• [4] https://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors

Step 3 : Solve for V by using the following formula : V = 1/Σ Mᵀ U

Example Walkthrough

Let’s calculate the SVD of the following matrix M.

Step 1 : M*Mᵀ

Step 2 : Calculate the eigenvalues & eigenvectors

You can use the following calculator to calculate the associated eigenvalues & eigenvectors. This link below has a step by step guide as to how the values are calculated. If you’re not interested in that, then just use numpy to calculate the eigenvalues and eigenvectors

• eigenvalues and eigenvectors calculator

Take the square roots of the non zero eigenvalues and generate the Σ matrix :

To calculate the U matrix you must calculate the unit vector in the direction of each of the eigenvectors. The link below outlines how to calculate the unit vector.

• unit vector calculator

This yields the resulting U matrix.

Step 3 : Solve for V through the formula : V = 1/Σ Mᵀ U

You can reference the following resource for an in depth guide on the calculations behind SVD.

• SVD Calculator

Problem Statement

We want to build a collaborative filtering recommendation system using a music dataset. Generate the user-item matrix and use singular value decomposition in conjunction with cosine similarity to identify songs a user would be interested in.

Data

For the purposes of this tutorial, we’re going to synthesize the dataset using pandas, numpy and random. This section will provide a script which will synthesize a dataset associated with music. The dataset will be used for applications of recommendation systems in the following sections. The aim of this tutorial is not to get meaningful results but to show the user the implementation behind singular value decomposition. Hence the results of these recommendations will be meaningless but the methodologies will be similar to those in production grade environments in industry.

Requirements

python=3.8.8
pandas=1.2.4
numpy=1.20.1

After running this script, you should see some sample data generated similar (not exact since it’s generated randomly) to the image below.

Solution Architecture

Now that we have a dataset to work with, we can think about how we’re going to approach solving this problem. We’ll begin by generating the user-item matrix based on the value associated with the number of listens. The items in this case would be the song_ids while the users would correspond to the user_id. Following from that, we can use SVD to compute the associated U, Σ, and V matrices. Finally, we can use cosine similarity comparing user vectors to item vectors to identify the top N items this user would be interested in.

SVD Recommendation System Implementation

Generate User-Item Matrix

Calculate SVD

Generate Recommendations

Challenges

There are a variety of challenges when working with collaborative filtering approaches in recommendation systems, the most common one is the cold start problem. The cold start problem refers to a recommendation engines inability to generate decent predictions for new items / users. Or users / items which have a low amount of interactions, essentially the user-item matrix it generates is very sparse. This is because of a lack of information for new items or product releases.

Another common problem with collaborative filtering which stems from the cold start problem is the diversity of the recommendations. This approach recommends products / users based on the historical interactions other users / products have had, essentially meaning that highly popular products will almost always get recommended over other products with a little too few interactions.

Scalability is a common issue for collaborative filtering algorithms, as the number of users, products and interactions increase, the size of the user-item matrix increases proportionally. This causes issues when data expands substantially and will yield an increase of computation time. Usually, the trade off with working larger datasets is that there should be an increase in performance while there’s a decrease in speed and vice versa for small datasets.

Concluding Remarks

This article outlined the intuition, mathematics and implementation behind matrix factorization, in particular, singular value decomposition (SVD). I showcased how to use SVD to create a collaborative filtering recommendation engine using a music dataset we’ve synthesized in Python.

Feel free to checkout the repository associated with this tutorial on my GitHub page here.

If you’re looking to transition into the data industry and want mentorship and guidance from seasoned mentors then you might want to check out Sharpest Minds. Sharpest Minds is a mentorship platform where mentors (who are seasoned practicing data scientists, machine learning engineers, research scientists, CTO, etc.) would aid in your development and learning to land a job in data. Check them out here.

Resources

• [1]https://en.wikipedia.org/wiki/Matrixfactorization(recommender_systems)
• [2] https://www.emathhelp.net/en/calculators/linear-algebra/svd-calculator/
• [3] https://en.wikipedia.org/wiki/Singular_value_decomposition
• [4] https://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors

---

If you enjoyed reading this article, here is a list of others related to Data Science and machine learning which you might find interesting.

Active Learning in Machine Learning Explained

Link Prediction Recommendation Engines with Node2Vec

Text Summarization in Python with Jaro-Winkler and PageRank

Recommendation Systems Explained

Word2Vec Explained

Support Vector Machine (SVM) Explained

Build a Collaborative Filtering Music Recommendation System in SQL