Have you ever recommended a movie you loved to someone – and then felt surprised when she or he didn't like it? "I guess we don't have the same taste for movies!" is the response you might have heard. Giving good recommendations for anything – from books or movies, to clothes or sports equipment – is very difficult, especially if you know little about the person.
Online algorithm-based recommendation systems face the same challenge. Consider Netflix, which relies on its in-house movie recommendation system to help viewers discover movies they will like. Most of the time, recommended movies should make sense to you as a viewer. But this is not always the case. Here’s a comment from one of Netflix' own blog posts a couple of years ago:
And here’s an even more radical one:
So, what's going on here? Are these people just trolling? Maybe, but there is a different plausible explanation:
It's hard to please everyone
Product recommendation systems such as the ones used by Netflix, Goodreads, or YouTube, are complex pieces of software that generate recommendations in real time for millions of people across hundreds of countries every day. These systems are designed to serve recommendations individually to each visitor based on his or her profile, whether the visitor logged in or is anonymous.
These systems work well for most people, most of the time (more on this later). However, it’s enough for the system to work poorly for even a tiny fraction of users, for these users to get frustrated.
The source of the problem
A potential problem lies in how performance is tracked. When you suggest a movie to a friend, your goal is clear: make the best possible recommendation. The objective for online recommendation systems is less clear. Even though recommendations are served individually, the performance is measured across all users – and this makes things more complicated. Imagine these two different goals:
- to have the best possible average performance (over all users), or
- to have the best possible worst-case performance. No user should get very bad recommendations.
Ideally, you would want to have a system that works equally well for all users. Unfortunately, this is not possible. As a result, you can end up trying to find a good trade-off between the two examples. However, it’s difficult to ensure that no sub-set of users gets bad recommendations. Read what Yves Raimond and Justin Basilico from Netflix say themselves:
The objective is to build recommendation algorithms that work equally well for all of our members; no matter where they live or what language they speak. But with so many members in so many countries speaking so many languages, a challenge we now face is how to even figure out when an algorithm is sub-optimal for some subset of our members.
In other words, the system might perform very poorly for some users, but it’s difficult to figure out who is affected and why. This is an interesting problem that bears a little more detailed explanation.
How recommendation systems work
Algorithms that recommend products to users often rely on interaction data between users and items. This interaction data can be represented as a matrix:
The rows of the matrix represent individual users, while the columns represent individual products. An online shop with a catalog of 1,000 products and 100,000 unique visitors in the last month can therefore be represented as a matrix of size 100,000 x 1,000. (This might not be the best representation, as this matrix tends to be huge and therefore difficult to process, but the exact representation does not matter for our discussion.)
Every time a visitor interacts with a product (sees a product page, or watches/rates a movie), the corresponding cell in the matrix can be filled with a score; say "1" if the user interacted with the product in any way. If there has been no interaction between a user and an item, the corresponding cell in the matrix does not have a value.
Most visitors of online shops interact with only one or two products on the site. This means that most rows will have just one cell with a known value ("1" in our case). Hence, the matrix of interaction data is very sparse: most values of the matrix are unknown. The problem the product recommendation algorithm tries to solve is to guess the unknown values. In other words:
"What score rui would a user u give to a product i ?"
This question is interesting, because the predicted value of rui gives us an indication of how likely a user u is to interact with an item i in the future. High values represent high probabilities of future interaction, and vice versa. To make, say, ten product recommendations to a given user, we need to find the ten products (columns) that have the highest predicted rui value.
But how are the missing rui predicted?
In the science of recommendation systems, the approach of using the behavior of all visitors to predict the behavior of one individual visitor is called collaborative filtering. More precisely, since we are talking about guessing the missing values of a sparse matrix, this is also a matrix completion problem.
Collaborative filtering is one approach to the problem. There are other techniques (such as content-based filtering) and other challenges related to the type of data which is analyzed (e.g., differences in popularity of products, importance of context page on which the recommendation is given) that are interesting to talk about. But we’ll keep that for another blog post.
These methods have a number of internal parameters that have to be optimized (or trained), using the matrix of interaction data (the rui values) as input. This training procedure attempts to optimize the result on a pre-defined goal, or metric, such as:
- the average click-through rate of recommendations, or
- the number of products added to cart after a click on a recommendation, or
- the root-mean-square error (RMSE), which was used, for example, during the famous Netflix prize.
Note that these metrics all attempt to optimize the average performance of the system. An online shop usually monitors conversion ratio (percentage of visitors converted into paying customers), which is an average metric across all of the shop. Giving good recommendations to most visitors is "good enough": it will most likely have a positive effect on conversion. But what about the visitors who don't like the recommendations they see?
Let us assume that a system was optimized with the goal of having a good average performance, with a metric such as the RMSE. The performance of the system, and therefore the perceived quality of recommendations, will likely be very different for each user. To train the system to work equally well for all users, we would have to:
- figure out for which users the system does not work well, and
- design a new metric that attempts to prevent the system from performing poorly on this group of users.
These two steps are hard to automate, since it is unlikely that there is a well-defined group (such as "all users in South America") for which the system does not perform well. But putting this difficulty aside, we would then optimize the system again, this time on our newly defined metric. The likely result is that we would now observe that the system performs poorly on a new and different subset of users. We could then repeat the whole procedure ad infinitum, without ever completely solving the problem.
Exploration vs. Exploitation
Another important consideration regarding the effectiveness of recommendations for individual users is the so-called exploration vs. exploitation trade-off.
Recommendation systems can be thought of as making hypotheses on users’ tastes, such as "I bet Bob will like X." If Bob indeed buys/watches/clicks on X, the recommendation system's hypothesis is confirmed. Otherwise, perhaps the recommendation system needs to make a new hypothesis regarding Bob's tastes.
The recommendation system is in full exploitation mode when it makes no new hypotheses regarding Bob's tastes. It exploits the knowledge on Bob it already has (i.e., it uses all available knowledge to make informed predictions for the missing rui). In this mode, Bob is unlikely to be surprised by any recommendations he sees. If he watched a lot of action movies, it's likely he will see recommendations for more action movies.
In contrast, the system is in full exploration mode if it tries out a lot of new and risky hypotheses (i.e., it makes wild, perhaps random, predictions for the missing rui). As an extreme example, the system might try to recommend romance movies to Bob, even though he previously only watched action movies. After all, it is possible that Bob likes both action and romance movies. The exploration mode is important because it is helpful in exploring and discovering new facets of a user's tastes.
A delicate balance has to be found between the exploration and exploitation modes for the system to be perceived as useful. If too much emphasis is put on the exploitation mode, the system will be perceived as too predictable and users might complain that the system did not let them discover new things. If too much emphasis is put on the exploration mode, the system will give the appearance of not working at all. Striking the right balance is difficult enough in itself, but an additional difficulty lies in the fact that each user probably prefers a different trade-off between the two modes.
Solution: Putting users in control
We’ve talked about two apparently insurmountable problems in making a perfect recommender system that is 100% automatic. A potential solution to the problem is to create a system that is not 100% automatic, but provides some level of control to the users.
There are widgets that do exactly that: recommendations are automatic by default, but the user has various ways of interacting with, and modifying the recommendations he or she receives; such as settings filters on various attributes of the items (price, brand, or color.)
Conceptually, it’s a mix between a search bar (manual operation) and a personalized product feed (automatic operation), with the aim of getting the best of both worlds. These types of widgets are particularly effective in mobile environments, where screens are small and bandwidth is scarce.
In a system that is 100% automatic, there is no way for the users to tell the system that it’s wrong, which can be very frustrating. Giving users the ability to easily modify the recommendations is therefore helpful in avoiding user frustration.
An added benefit of a system that is not 100% automatic, but in which the users interact with the system itself, is that more interaction data is collected. In fact, this type of interaction data is likely to be of higher quality than simple product page visits, because it provides explicit feedback on the quality of the recommendations. The collection of additional, high-quality data is useful in making the automatic recommendations better.
Fully automatic recommendation systems are unlikely to always provide recommendations that are perceived as useful. One reason is that it’s very difficult to build a data-driven algorithm that works well in all situations. Systems that are used by a large number of users, or have a large number of items, are particularly at risk of being perceived as "wrong" or "useless" by some users, even if the performance is good on a global scale and brings value to the site using it.
It’s important to understand that users like to interact with recommendations by picking content, setting filters and discarding products they don't like. Giving some amount of control back to the user is a good solution for making it useful to the user, while learning more on his or her tastes.