Optimization Techniques for latent collaborative filtering

In my previous article, I wrote about Latent collaborative filtering and why it is one of the most used collaborative filtering algorithms.

In summary,

1. We have a user history of what product they rated or purchased,
2. Find hidden factors that influence the user’s probability to buy or rating the product,
3. Use those hidden factors to predict how user would like or dislike the product
4. We start by taking a user item rating history matrix R and decompose it into user factor(P) where each user mapped into hidden factor and product factor matrix(Q) where each product mapped to hidden factor.
5. This decomposition can be set as an optimization problem and this optimization is what we are going to solve.
6. We need to find product factor Pu for each user and item factor vector Qi . Find the complete set of factor vectors which minimize the error on the training set between training set and predicted rating. Predicted rating for any product is the dot product of factor vectors for user and product.
7. Taking the sum of squares of all the errors in the training set, we can calculate the error function. And minimizing the error function is the goal of our optimization problem.

Stochastic Gradient Descent

It takes each rating on the training set and perform some action on it. Say a rating be r u, i for user u and item i. Now what we are looking are two vectors P u and Q i whose dot product gives the rating that is close to the rating in the dataset or actual rating.

Algorithm:

1. Initialize some random value for P u and Q i .
2. Calculate predicted rating by (Pu . Qi) and calculate error by finding difference between actual rating and predicted rating.
3. From the initial position, calculate the slope of function and move slowly downwards, ( the goal is to reach global minimum from initial value)
4. Calculate slope at every point until you reach the minimum ( the point from where error increases ).
5. The error is given by

(equation 1) error function

6. Now you want to find the slope in this point and move slightly downwards

Here, the partial derivative term is the slope at that point, gamma is the learning rate that defines how steep we take the step downwards.

Alternating Least Squares

In stochastic gradient descent, we have to loop through entire training set to find the optimal values of pu and qi and this process is serial. But using alternating least squares, we can perform this calculation in parallel. Let’s see again in equation 1(error function) above, we have two variables in the equation pu and qi. Now what if we keep pu in the equation constant. Then the equation becomes quadratic and we can solve the value for qi. Now in next iteration we keep pu constant and solve for qi. We keep on alternating and solving the values until we reach the point where both pu and qi converge.

Use of matrix factorization in recommendation system was a big improvement. This was invented during the Netflix prize competition. It was a million dollar prize and there were lot of improvement in recommendation systems at this time. You can read more about the competition here. The other things that made a good impact on recommendation system other than matrix factorization were:

1. Normalizing for user biases( some people tend to rate all products high and there are some people who rate products low even if they like the product so we need some kind of weights to descent the ratings) and temporal effect( user’s interest and taste change along time for e.g I used to listen rock songs very much when I was kid now I don’t generally listen them ).

I will discuss more about recommendation systems in my next articles. If you like this post, don’t forget to clap the post and follow me on medium and on twitter.