Collaborative Filtering In Simple Language
Nowadays everybody somehow knows what recommender systems are. But do we know how do these magical systems work and how they understand what products we might like?
In last few years, large e-commerce websites as Amazon caused a massive growth in the number of users’ choices. These websites provide more and more products everyday. On the one hand this gives users much more options and on the other hand more options make it harder for users to find their needed items. Recommender Systems are an emerging technology to solve this problem by estimating which users will like which items. Then the e-commerce website can make personal recommendation for each user. The most famous approach that is used by recommender engines is Collaborative Filtering, which I will try to simply explain in this post.
Collaborative Filtering
Collaborative approach is a well-known approach in RS that many of the famous systems use it. This approach follows a simple rule: users tend to buy items that other users with same taste have bought it. For example, consider the table below. It shows users rating to different items. In this table we can estimate that user U1 probably will like Item I2, as users U1 and U4 both like item I1 and user U4 has given a high rate to item I2.
═══════════════════════════════════
I1 I2 I3 I4
════════╬══════════════════════════
U1 ║ 4 - 5 5
U2 ║ 4 2 1 -
U3 ║ 3 - 2 4
U4 ║ 4 4 - -
U5 ║ 2 1 3 5
════════╩══════════════════════════Collaborative filtering has different methods. In the following section i will explain a little about Neighbor Based method and Matrix Factorization.
Neighbor Based methods
Neighbor Based methods calculate the similarities between items (item-based) or between users (user-based). When it is item-based, these methods estimate the rating of a user to an item, based on the ratings of the user to similar items. And when it is user-based, these methods estimate the rating of a user to an item based on the ratings of similar users to that item.
Neighbor Based Method has two main phases: 1.Calculation of similarities 2.Estimation of Ratings.
In the first phase, we calculate entity similarities. Similarities can be calculated simply by Pearson Correlation or Cosine Similarity or by more recent approaches. Then these similarities are used to make sets of similar users for each user or similar items for each item and estimate the rating based on these similar items or users.
Neighbor Based methods have the following cons:
- As we just need to calculate similarities, it’s easy to implement.
- These methods are scalable
- These methods can easily handle new items or users.
- These methods make it easy to explain to users that why we are suggesting this item
Matrix Factorization
Matrix Factorization is the most famous Collaborative Filtering approach which is used massively. I will try to explain this method as simple as I can.
In rate based recommendation systems, our dataset is usually a rating matrix. This rating matrix is as above table, But much bigger and much more sparse. To consider how sparse this matrix is, imagine IMDB users and items. It has millions of users and thousands of items. Each user has probably rated to just few items. So if we make user-item matrix, it will be a very large and sparse matrix. Let’s consider IMDB users and movies and let’s imagine we are in the business of recommending movies to users. One way to recommend movies is to define some factors that help us to estimate ratings. These factors can be genre, director, year and etc for movies. Now I can use these variables to guess what movies an specific user might like. For example, if we know Lord Of The Ring genre and if we have a prior knowledge that Bob likes this genre, we can guess that Bob will probably like this movie so we should recommend it to him. The main problem here is to define these factors and find the interest of each user to each factor. Doing so is very hard; almost impossible. That’s where machine learning comes to save us!
If we can factorize the rating matrix, R, into two matrices U and V in a way that U^T . V = R we will have a vector U_i for each user and a vector V_j for each item that their inner products gonna yield estimated rating of user i to item j. This problem can be solved by SVD. But as R matrix is very sparse, we can solve it by minimizing the below:
Where r is given rate to item i by user u, and lambda is the regularization parameter. After minimizing that using methods like Gradient Descent, we will capture a vector for each user and item. Now for estimating rating of a user to an item, we just need to calculate inner product of their vectors.
