Exploring Recommender Systems

July 19, 2015

User-Based Filtering

If there are almost no missing values, the Minkowski distance metric ( $L^p$ norm) can be used:

$$ \mathrm{distance(x,y)}=\left(\sum\limits_{i=1}^{n}|x_i-y_i|^p\right)^{\frac{1}{p}} $$

Setting $p = 1$ , gives the Manhattan distance or taxicab distance. $p = 2$ gives the Euclidean distance. If there are missing values, the difference in dimensionality skews the results. In the $L^p$ norm, the influence of a large difference on the total difference increases with the value of $p$ . Setting $p=\infty$ gives the $L^\infty$ norm $\max_{i} |x_i-y_i|$ . In most applications, the taxicab metric or the Euclidean metric is sufficient.

Take this user-item matrix for example.

	Item 1	Item 2	Item 3	Item 4	Item 5
User 1	1	-	5	1	4
User 2	2	2	5	3	5
User 3	5	2	3	5	-
User 4	4	1	4	2	3
User 5	3	3	2	4	1
User 6	-	3	5	1	4

Find the users who are close to others (based on a metric of choice). Find the items that are not common between the target and the similar users and recommend those items. The nearest neighbors from Scikit-Learn can be used. The unfilled ratings are replaced with a 0.

import numpy as np
from sklearn.neighbors import NearestNeighbors

mat = [[1,0,5,1,4],[2,2,5,3,5],[5,2,3,5,0],[4,1,4,2,3],[3,3,2,4,1],[0,3,5,1,4]]

n = NearestNeighbors(metric='cityblock')
n.fit(mat)
n.kneighbors([3,1,5,2,3]) #default n_neighbors is 5
#for radius based learning, look up radius_neighbors in scipy documentation

One striking problem is subjectivity. The ratings maybe biased because of several uncommon factors. Or, the user could be stingy or overly generous in rating items uniformly. The almost-uniform generosity or stinginess problem can be solved by using Pearson correlation (scipy.stats.pearsonr(x,y) or using metric='correlation' in the NearestNeighbors example). It is a good idea to use libraries for numerical computations, especially in Python. They are optimized and are vigilant to numerical instability and exceptional cases. The data can be standardized by computing the z-scores $\left(\frac{x-\mu}{\sigma}\right)$ . All this solves is the difference in scale of values if different features are included for each item.

Another problem is replacing unrated items with 0. With a higher $p$ in the Minkowski metric, the distance increases substantially for uncommon items between users. This can be solved by using the Cosine Similarity (metric='cosine'). This is used when the data available is sparse (as in most real-world scenarios). Training data in examples and tutorials normally have handcrafted or well organized datasets. Basing the choice of metric on just training data is not a good idea.

The accuracy of recommendations is limited by the data available. People often don’t rate at all or update an item’s rating. This is one of the reasons for the sparsity even in a small user-item universe. In reality, the number of people buying a product is very small compared to the number of products available. So, the user-item matrix (highly impractical in its current form) is sparse.

An increasingly relevant drawback is scalability. The user-item matrix will take up a lot of memory. With increase in number of users and/or items, it is bound to run out of memory. A nearest neighbor method like kNN (k-Nearest Neighbors) simply remembers the training data and answers queries. Scikit-Learn gives the option of using brute, kdtree and balltree. The training and query complexities are detailed in the Nearest Neighbor documentation. Although these improve the running times, the solution isn’t scalable. For what it’s worth, sparse matrices might speed things up. A more detailed analysis can be found here.

Verbosity aside, the paragraphs condense to find similar users using kNN with Pearson correlation as the metric. The next stop is to actually recommend items. Considering the simplicity of this, it took me way too long to figure it out . The next step is to iterate through the items unrated by the target user but rated by the similar users. If the user $u$ has a Pearson correlation $p_u$ , the predicted rating for an item is the weighted sum of ratings of the users:

$$\mathrm{Rating_{i}} = \frac{\sum\limits_{u\in U}p_u\cdot R_u}{\sum\limits_{u\in U}p_u} $$

Here, $U$ is the list of users from kNN, $R_u$ is the rating for item $i$ by user $u$ and $p_u$ is the Pearson correlation with the target user. This list is sorted by the predicted rating and is the final list of recommendations.

Item-based Filtering

The similarity metric used is the Adjusted Cosine Similarity mentioned in this paper.

One fundamental difference between the similarity computation in the user-based CF and item-based CF is that in case of the user-based CF the similarity is computed along the rows of the matrix but in case of the item-based CF the similarity is computed along the columns, i.e, each pair in the co-rated set corresponds to a different user

The adjustment in this metric is the subtraction of the mean of that particular user’s ratings from their ratings to take care of stinginess or generosity in rating. The similarity measure looks like this in all its glory:

$$\begin{equation}\mathrm{similarity(x,y)}=\frac{\sum\limits_{u\in U}{\left(R_{u,x}-\hat{R_u}\right)\left(R_{u,y}-\hat{R_u}\right)}}{\sqrt{\sum\limits_{u\in U}{\left(R_{u,x}-\hat{R_u}\right)^2}}\sqrt{\sum\limits_{u\in U}{\left(R_{u,y}-\hat{R_u}\right)^2}}}\end{equation}$$

The difference between the adjusted cosine similarity and the vanilla variety is that apart from the space vector angle between the two items, the former normalizes the user ratings. Normalization turns out to be important since it is a cross-user metric.

A similarity matrix can be computed and with every new user, only the weighted sum needs to be updated. This reduced overhead compared to user-based filtering makes it scalable. Apache Spark’s broadcast variable and a cyclic dataflow model unlike MapReduce or Dryad on Hadoop makes it suitable for parallelizing this approach. The data is cached in the memory of each worker node. This reduces the latency in interacting with the similarity matrix. A detailed exposition with implementation can be found here. Parallelizing it by hand is a slightly tedious task. Scikit-Learn uses joblib to parallelize its pairwise computations. It partially (with delay in joblib) applies the metric function to the first array and an evenly sliced second array.

The predicted rating of an item $x$ for a user $u$ is again a weighted sum of the ratings given by that user to similar items:

$$\mathrm{Rating_{u,x}} = \frac{\sum\limits_{i\in \mathrm{similar(x)}}C_{x,i}\cdot R_{u,i}}{\sum\limits_{i\in \mathrm{similar(x)}}|C_{x,i}|} $$

The ratings $R_{u,i}$ are the user’s rating scaled to $[-1,1]$ . The rating $R_{u,x}$ is rescaled to $[0,5]$ finally. This is to accomodate the right magnitude of the similarity to the rating.

Dealing with explicit ratings or features can be quite unreliable. Apart from people’s laziness, their mindset while rating an item matters too. For example, film ratings are highly biased. A user could rate a film high because of hype or a “fanboy bias”. In the case of the movie The Interview, people rated it 10 without having seen the movie. Fake ratings such as this are another concern. So, websites scour for implicit data. Not just numerical ratings, but words in product reviews or the number of times a song has been listened to and so on. These are implicit ratings and are much harder to study in an organized fashion.