Recommendation Systems : How that works ?

Learning about Recommendation Systems

Wondered ever how YouTube knows which video you might me interested in? How Netflix predicts which movie or web series you can watch next? This is all done by their Recommendation Systems. Each app or website uses some sort of Recommendation System to improve the user’s interactivity with their product (About 60–70% of YouTube’s watch time comes from recommended videos). In this article we will see how a basic Recommendation System works.

Types of Recommendations

1. Home Page Recommendations — Home Page Recommendations are the items or products recommended to user based on user’s interest and past searches.
2. Related Item Recommendations — These are the recommendations based on a particular item or a search. For example, a user on Amazon looking for a mobile phone may also see its accessories along with it.

Items and Queries

Before moving forward, you should know what are items and queries. Items are the Videos on YouTube, Movies on Netflix, Apps of Play Store or Posts on Instagram. So basically, Items are what is to be recommended.

Queries are the information required to recommend an item. Most of the time query is the user’s search or past searches. But some additional information like user’s location, user’s age can also make up a query.

Embeddings

Embeddings are the multi-dimensional representation of an item or a query.

In this picture each object has a 3-d representation. For example, rocket has a representation of (0,4,2). First axis corresponds to the wings, second axis corresponds to engine and the third axis represents the sky. What an axis represents may or may not be known in a embedding depending upon for what they are used. Generally, the embedding are learnt by the model and the axis names are unknown.

Main work of a recommendation system is to learn a appropriate embeddings for items and queries.

Steps in a Recommendation Systems

To recommend one or more items to user, the recommendation system goes through a series of steps

The first step includes Picking out the candidates for Recommendation. For example, YouTube filters say thousand videos from a collection of several billion videos. This is the main and the most important step in a recommendation system.

In the second step, the recommendation system gives scores to the candidates generated by the first step. In this step more queries can be used for more accurate recommendations

The third steps alters some scores based on some criteria like reducing score of the items that are old or increasing the score of items that were liked by the user earlier

Candidate Generation

There are mainly two ways for candidate generation.

1. Content Based Filtering
2. Collaborative Filtering

Content Based Filtering

In this approach the recommendations are based on the items to what the user shows interest. Every user gets different recommendations and interests of one user do not effect the recommendations for other users

Let’s take the example of apps on play store. We denote the apps by a feature vector (embedding) and this time each axis has a name which are hand engineered. Users are also represented by same feature space.

Let’s say that the user downloaded apps related to education, apps by Science R Us and by healthcare recently. Out of the 3 apps in the table which app is most likely to be downloaded by the user ?

We can define a similarity function and then find the similarity between user’s feature vector and the app’s feature vector. Common similarity functions are

1. Cosine Similarity
2. Dot Product
3. Euclidean Distance

Cosine Similarity is generally the best choice for calculating similarity in higher dimensional vectors.

Disadvantages of Content based filtering

1. Most of the features of items are hand engineered which takes a lot of time.
2. This method is less flexible and generated candidates based on a limited information

Collaborative Filtering

In this method, the embedding are automatically learnt and doesn’t require hand engineering. Recommendations are made based on the items similar to what user have shown interest in and the items similar users have a positive feedback. Meaning of positive feedback here is undefined. Positive feedback may be when user gives high rating to a item, or when he likes a item, or even when he searched for a particular item.

The first step of collaborative filtering is to create a matrix A. A is a matrix in which the rows represent the users and the columns represent the items. A<i,j> is 1 if the i user gives a positive feedback for item j or 0 otherwise.

Note: A will be of shape (m x d)

In the above picture user 1 have shown interest in Harry Potter, Shrek and The dark Knight Rises. Thus A<1,1>, A<1,3> and A<1,4> is 1 and rest are 0.

The main objective of this method is to learn the Embedding matrix for users (query) and items. Lets denote the user’s embedding matrix by U and item’s embedding matrix by V. U is of the shape (m x d) and V is of the shape (n x d). m is the total users, n is the total items and d is dimensionality of the vector representing a query or an item.

Each item is represented by a 2-D vector

U and V are chosen at random initially and then U x V (matrix multiplication) is calculated. Let’s call it B. An optimizing algorithm, like SGD (Stochastic Gradient Descent) is used to make B matrix similar to matrix A. The loss function to be minimized is often chosen as Σ W*(A<i,j>- B<i,j>)² where W is 1 if A<i,j> is 1 and <1 (hyper parameter) otherwise.

Rather than using SGD, WALS (Weighted altering least squares) is commonly used for recommendation systems. WALS work by alternating between fixing U and solving for V and fixing V and solving for U.

Advantages of WALS

1. It is faster than SGD

2. This method is guaranteed to converge because we are decreasing loss at each step.

Why Collaborative Filtering ?

1. No hand Engineering is required. Embedding are learnt automatically
2. It can help users to develop new interests and explore more as an item may be recommended is similar users are showing in interest in that item.

Drawback of Collaborative Filtering

1. A major drawback of this method is that it cannot create an embedding for a new item or a new user.

This problem can be solved to an extent by using some techniques like, asking a new user their interest before-hand can help in creating their feature vector.

Feature space of the item can be calculated as the average of same category items ( like averaging features of all videos of the same YouTube channel )

2. Hard to include additional features like user’s location, user’s age etc.

Is there any better way to generate Candidates ?

Yes, now a days, Deep Neural Network have become the backbone of ML algorithms. Deep Neural Networks can be used to generate Candidates more accurately. Also, using additional information becomes easy in deep neural networks so the recommendations are more precise.

Retrieval

To apply the similarity function and get the candidates out of huge data, generally K-Nearest Neighbors (KNN) are used. The distance in K Nearest Neighbor is dependent on the similarity function. For example if cosine similarity is used, then the distance 1- cos(query,item) can be used.

To make the Retrieval computationally efficient, Approximate K-Nearest Neighbors ( for example, using locality hashing) is used. Home Page recommendations can be generated before hand rather than generating candidates when the user opens the app.

Scoring

In this step, the recommendation system scores the candidates (for example, on order of 10) based on the following

1. Embedding
2. Trending items
3. Additional information like user’s location
4. Social Graph, scores the item high if liked by social friends. This step is common and vital in social sites like Instagram, Facebook etc.

You should also be careful while selecting a criteria for scoring the items. For example, in YouTube if videos with more views are scored higher, then most of the recommendations will consist of click baits.

It is common to use a different model to score the candidates rather than using similarity in the candidate generator because, for a different model additional queries can also be included and thus the precision in recommendations increases.

Re-Ranking

It is the final step in the recommendation system architecture. Re-Ranking is done on the basis of some pre-defined criteria like

1. Removing disliked Content
2. Removing age restricted content
3. Removing Click baits to the best extent
4. Reducing Score of Long Videos (in YouTube)

Source : https://developers.google.com/machine-learning/recommendation/