What is Singular Value Decomposition (SVD) and how does it work?

-
Singular value decomposition (SVD) is one of the jewels of linear algebra. In modern times it has found applications in machine learning and Artificial intelligence. The most important feature of SVD is that of dimension reduction so that we are able to make predictions on very large data sets with a small subspace of variables.  Let’s try to understand how it works through a real-life example.


Netflix has many subscribers and they have a collection of movies. When we watch a movie, we often see similar movies being recommended to us next time we go to Netflix and we wonder how did they figure out the kind the movies I like! The answer is SVD.

As an example, suppose Netflix has 5 movies and multiple subscribers. Netflix gets the data for every user with a rating going from 0 to 5 with 0 implying the user did not watch a particular movie and 5 implying the user has watched it multiple times. A sample data set will look like this. 

Each row in this matrix A will correspond to a user and each column will correspond to a movie. As it turns out that any real (has no complex values) matrix can always be expressed as the product of 3 matrices
A = U Σ VT, where
  • U, Σ, V: are unique (Here VT  is the transpose of V- switching rows and columns)
  •       U,V: orthonormal columns  ( dot product is zero and are orthogonal unit vectors)
    U    T U=I, VT V=I (I: identity matrix)
  •  Σ: is a diagonal matrix (It has off diagonal values as 0s) Entries (singular values) are positive, and sorted in decreasing order (σ1 ≥ σ2 ≥…≥ 0)
Therefore, our inputs matrix of users or subscribers and movies can be written as

Also, the movies can be classified as “concepts” – Action movies or romantic stories. The first 3 movies are action movies and the last 2 movies are romantic movies.

  • A: Input Data matrix m × n
    matrix (e.g., m users, n movies)
  • U: Left singular vectors m × r
    matrix (m users, r concepts)
  • Σ: Singular values r × r diagonal
    matrix (strength of each ‘concept’)
    (r: rank of the matrix A- How many linearly independent columns or rows the matrix has)
  • V: Right singular vectors n × r
    matrix (n movies, r concepts) 
It is always possible to decompose a real matrix A into

Where

 σi … scalar
ui … vector
vi … vector

We can now show the SVD of our input matrix which was obtained from the software MATLAB. 


The first column of U corresponds to the Action movies and the second column corresponds to romantic movies. As can be seen, the first 4 users like the action movies while  in the second column the last 3 users like romantic movies.

The second matrix  Σ tells us about the strength of each concept – Action movies and Romantic movies. Clearly, users are more fond of Action movies as its strength (12.4) is greater than for romantic movies (9.5).

The third matrix VT tells us about movies to concept. The first 3 movies belong to Action movie concept and the last two movies belong to the romantic movie concept. 

 Typically both the number of subscribers and the choice of movies is huge than our example and through the prudent choice of concepts we are able to quickly determine the taste of the subscriber. 

It is to be noted that we have some “noise” in the data so we ignore the last column of U and last row of VT as seen from the relatively weak strength of 1.3 in the Σ matrix.

It is quite amazing to observe all the useful information that can be derived from the input matrix about subscribers and movies.

There you have it! How Netflix generally determines what recommended movies to show you. This is one potential application of SVD and there many more.

Hope this article helped you understand singular value decomposition and how it can be used a little better! 

Comments

Post a Comment

Popular posts from this blog

How to make a cool million Dollars by solving a math problem?

-
Image
The Millennium Prize Problems are seven problems in mathematics that were stated by the Clay Mathematics Institute in 2000. As of June 2020, six of the problems remain unsolved. A correct solution to any of the problems results in a US $1,000,000 prize sometimes called a Millennium Prize being awarded by the institute.  Solved Problem: -  Poincare conjecture. When the Clay institute first announced these seven problems, it was generally perceived by the mathematics community that these seven problems would remain unsolved for the foreseeable future. To their surprise, Grigori Perelman a recluse Russian mathematician solved the Poincare conjecture and in July 2010 he famously declined the 1 million dollar prize!   Furthermore, in August 2006, he declined the Fields medal which is considered even more prestigious than the Nobel Prize as it is given every four years to a mathematician under the age of 40. The Nobel Prize is given every year with n...
Read more

The Famous Basel Problem: The process that led Euler to the answer!

-
Image
Euler is considered to be one of the greatest mathematician of the 18 th century and many believe that he was among the greatest of all time. The answer to the Basel problem is considered to be among his many gems. It is the sum of the series shown below and the answer is astounding! What is π doing there? Mathematician at the time summed up the series to the first 10, 100, and 1000 terms and the slow rate of convergence gave very little clue to what the answer could be.  Euler realized that he would have to find a function that would converge much faster. After some trial and error he found the function shown below whose power series expansion is shown.   So if we integrate the above expression from 0 to 1 This is what he was looking for! To evaluate the integral in the left, he broke it into two parts. Then he evaluated each of the integrals in turn. Then the next integral Put x=1-t When x=1/2, t=1/2 When ...
Read more

Millennium Problem: Riemann Hypothesis

-
Image
A prime number is a number that is divisible only by itself and 1. Some examples being  2, 3, 5, 7, 9, 11, 13.…   The great mathematician Euclid proved centuries ago that there are an infinite number of them continuing without pattern ad infinitum. However, their real importance is given by what is known as the Fundamental Theorem of Arithmetic. It states that every number can be uniquely expressed as a product of prime numbers. Let’s take the example of 364 = 2 × 2 × 7 × 13. This is the only way that 364 can be obtained by prime numbers! Therefore, they are the atoms or building blocks of numbers. But in 1859, the great German mathematician Bernhard Riemann hypothesized that the spacing of the primes logically follows from other numbers, now known as the “nontrivial zeros” of the Riemann zeta function. The Riemann zeta function takes inputs not only real numbers but also  complex numbers — meaning they have both “real” and “imaginary” components — and yields ...
Read more