Remember the movie recommendation engine we looked at earlier? What if we had 10,000 movies to recommend and we had to choose only 10 to give to the user? We'd have to take a dot product between the user profile and each of the 10,000 movies. Linear algebra provides the tools to make these calculations much more efficient.
It is an area of mathematics that deals with the math of matrices and vectors. It has the aim of breaking down these objects and reconstructing them in order to provide practical applications. Let's look at a few linear algebra rules before proceeding.
Like numbers, we can multiply matrices together. Multiplying matrices is, in essence, a mass-produced way of taking several dot products at once. Let's, for example, try to multiply the following matrices:
We need to consider a couple of things:
- Unlike numbers, multiplication of matrices is not commutative, meaning that the order in which you multiply matrices matters a great deal.
- In order to multiply matrices, their dimensions must match up. This means that the first matrix must have the same number of columns as the second matrix has rows.
To remember this, write out the dimensions of the matrices. In this case, we have a 3 x 2 times a 2 x 2 matrix. You can multiply matrices together if the second number in the first dimension pair is the same as the first number in the second dimension pair:
The resulting matrix will always have dimensions equal to the outer numbers in the dimension pairs (the ones you did not circle). In this case, the resulting matrix will have a dimension of 3 x 2.
To multiply matrices, there is actually quite a simple procedure. Essentially, we are performing a bunch of dot products.
Recall our earlier sample problem, which was as follows:
We know that our resulting matrix will have a dimension of 3 x 2. So, we know it will look something like the following:
Note
Note that each element of the matrix is indexed using a double index. The first number represents the row, and the second number represents the column. So, the m32 element is the element in the third row of the second column. Each element is the result of a dot product between rows and columns of the original matrices.
The mxy element is the result of the dot product of the xth row of the first matrix and the yth column of the second matrix. Let's solve a few:
Moving on, we will eventually get a resulting matrix that looks as follows:
Way to go! Let's come back to the movie recommendation example. Recall the user's movie genre preferences of comedy, romance, and action, which are illustrated as follows:
Now suppose we have 10,000 movies, all with a rating for these three categories. To make a recommendation, we need to take the dot product of the preference vector with each of the 10,000 movies. We can use matrix multiplication to represent this.
Instead of writing them all out, let's express them using the matrix notation. We already have U, defined here as the user's preference vector (it can also be thought of as a 3 x 1 matrix), and we also need a movie matrix:
So, now we have two matrices; one is 3 x 1 and the other is 3 x 10,000. We can't multiply these matrices as they are, because the dimensions do not work out. We will have to change U a bit. We can take the transpose of the matrix (turning all rows into columns and columns into rows). This will switch the dimensions around:
So, now we have two matrices that can be multiplied together. Let's visualize what this looks like:
The resulting matrix will be a 1 x 1,000 matrix (a vector) of 10,000 predictions for each individual movie. Let's try this out in Python:
import numpy as np # create user preferences user_pref = np.array([5, 1, 3]) # create a random movie matrix of 10,000 movies movies = np.random.randint(5,size=(3,1000))+1 # Note that the randint will make random integers from 0-4 # so I added a 1 at the end to increase the scale from 1-5
We are using the numpy array function to create our matrices. We will have both a user_pref and a movies matrix to represent our data.
To check our dimensions, we can use the numpy shape variable, as shown:
print(user_pref.shape) # (1, 3) print(movies.shape) # (3, 1000)
This checks out. Last but not least, let's use the matrix multiplication method of numpy (called dot) to perform the operation, as illustrated:
# np.dot does both dot products and matrix multiplication np.dot(user_pref, movies)
The result is an array of integers that represents the recommendations for each movie.
For a quick extension of this, let's run some code that predicts across more than 10,000 movies, as shown:
import numpy as npimport time
for num_movies in (10000, 100000, 1000000, 10000000, 100000000):
movies = np.random.randint(5,size=(3, num_movies))+1
now = time.time()
np.dot(user_pref, movies)
print((time.time() - now), "seconds to run", num_movies, "movies")
0.000160932540894 seconds to run 10000 movies
0.00121188163757 seconds to run 100000 movies
0.0105860233307 seconds to run 1000000 movies
0.096577167511 seconds to run 10000000 movies
4.16197991371 seconds to run 100000000 movies It took only a bit over four seconds to run through 100,000,000 movies using matrix multiplication.