I recently became interested in recommender systems. You know, the thing on Amazon that tells you which products you might be interested in. Or the stuff on Spotify that gives you a song you might like. On YouTube the next videos shown. On StumbleUpon, your next stumble. On a news page, another article.

Conceptual Approaches

There are three basic approaches:

Product Similarity: You watched Saw I, Saw II and Saw III. All of them are similar to Saw IV.
User similarity: Users that liked Saw I, Saw II and Saw III usually also liked Saw IV.
Basket analysis: You bought eggs and sugar, maybe you want to buy milk as well.

Recommender systems based on product similarity are also called "content-based recommender systems". The New York Times article recommendation is an example for that.

Recommander systems based on user similarity are also called "collaborative filtering".

Pandora is an example for content-based recommendation + collaborative filtering.

Basic Content-based Recommendations

Levenshteins edit distance applied on the product name is probably the simplest approach that has a mimimal chance of some reasonable results.

The next level in complexity are rules:

Movies by a director you liked
Movies with a actor you liked
Count "links" (actors, directors, producers, ...) and rank by most links

One more level of complexity is using clustering algorithms. One way is to make a product to a vector and use a similarity measure (e.g. cosine similarity). If you have natural laguage descriptions you can use tf-idf features and then use a similarity measure. You would then recommend the most similar products.

Cosine-Similarity: Let $x$ and $y$ be items. Their cosine similarity is defined as $$f(x, y) := \frac{\sum_i x_i y_i}{\sqrt{\sum_i x_i^2} \sqrt{\sum_i y_i^2}}$$

User-Based Collaborative Filtering

Users can have different scales on which they rate stuff:

Binary: Like / Dislike (and "not seen")
Ternary: Like / Neutral / Dislike (and "not seen")
5 Stars
100 points

So you want to find the utility function $u: C \times I \rightarrow R$ where $C$ is the set of customers, $I$ is the set of items and $R$ is the ordered set of ratings. By a simple transformation you can make it $R = [0, 1]$.

The utility function $u$ can be fully defined by a user-item rating matrix. Most elements of the matrix are not known, though.

Based on the user-item rating matrix you build up a user-user similarity matrix.

You look up similar users, generate candidates for recommendation, score and filter candidates (items the user already knows).

Basic Basket Analysis

See Association Rule Mining

Evaluation

One way to evaluate if recommendation systems work is by the typical train-test split.

Possible Metrics, where $y$ is the real value and $p(x)$ is the predicted value:

Mean Absolute Error (MAE): $\frac{1}{n} \sum_{i=1}^n |y_i - p(x_i)| \in [0, 1]$, where lower is better
Root Mean Square Error (RMSE): $\sqrt{\frac{1}{n} \sum_{i=1}^n {(y_i - p(x_i))}^2} \in [0, \infty)$, where lower is better

The problem with those two ways is that low-rated items don't matter much. If 95% of the users look at $n$ items, then you want the Top-$n$ recommendations to be (1) more relevant than the rest for the user and (2) the order of the top-$n$ elements to be correct.

Metrics for top-n recommenders:

Hit Rate: Number of hits in your $n$ recommendations, divided by the number of users
Average Reciprocal Hit Rank (ARHR): $\frac{1}{|Users| \cdot \sum_{i=1}^n \frac{1}{rank_i}}$
Cumulative Hit Rate (cHR): Throw away low-ranking stuff (hence you need a threshold)

Other quality indicators for a recommendation system

Diversity: How broad is the variety of items recommended to people?
Novelty: How many new/unfamiliar things do get recommended to a user? The higher the novelty, the more likely the user will discover something new. If it is too high, the user doesn't trust the recommendation anymore.
Churn: How often do recommendations for a user change?
Responsiveness: How quickly are recommendations adjusted?

Typical Problems

Cold-Start Problem

The cold-start problem is central and only fixable by content-based recommendation. If there is a new product, not a single user has rated it. It is not possible by collaborative filtering to recommend it.

Sparsity

You have so many items, that two users have no item in common and two items usually don't have properties in common.

Wrong Recommendation Mode

You have bought the DVD "Lord of the Rings" and get the Blue Ray recommended.
You have liked the normal version of a song and you get the techno/rap/christmas version recommended

The Bubble

You will never be recommended a movie where you didn't like the genre before.

Surrogate-Problem

Ultimatively, we want to maximize user engagement. In order to achieve this, we define a surrogate (e.g. accuracy of predicting user ratings).

The problem is that the choice of the surrogate matters a lot. A different surrogate might have way bigger impact on our real goal than an improvement in achieving the surrogate goal.

Vocabulary

Top-N Recommendation: Recommend N items
mise en scène: The idea in content-based filtering for movies to extract properties directly from the movie itself. It includes: Average shot length, color variance, mean motion average across all the frames, lightning, number of shots

Papers

Paul Covington, Jay Adams, Emre Sargin: Deep Neural Networks for YouTube Recommendations
Yashar Deldjoo, Mehdi Elahi, Paolo Cremonesi: Using Visual Features and Latent Factors for Movie Recommendations, 2016.

Recommender Systems