Building a Big Data Machine Learning Recommender System

What is a Recommender System?

You might not have heard about recommender systems, but if you have shopped, read, or watched movies online, you have likely seen or used one. On these sites, you are frequently offered “other items that you might be interested in...”, or “other stories just for you…”. Amazon, Netflix, and many news/entertainment sites constantly recommend products, movies, and stories when you’re using their service. These offers and “recommendations” stem from recommender systems, with the objective of narrowing down choices among your vast options for browsing and consuming an item, and to make choice selection faster and easier for you.

Before getting into the details of how recommender systems work, lets discuss the differences between these systems and a few other similar systems for the sake of making definitions and semantics more clear. Recommender systems may sound very similar to Decision Support Systems (DSS), where the system is designed to select a top few (or sometimes all) decision alternatives for a decision maker given a decision problem. However, recommender systems, as is commonly known, are about systems that recommend one or more items that are predicted to be close to the preferences of a decision maker for their selection. Unlike a DSS, there is a significant emphasis on preference here. That is, the main objective of a recommender system is to compute and predict a decision maker’s preference. Recommender systems are sometimes categorized in the class of systems called information filtering systems (IFS). Though, IFS have a broader outlook for filtering information and providing a subset selection for some purpose, while recommender systems are more specific and targeted to someone’s preference for a given item.

Recommender systems may also seem familiar to advertisement systems. After all, ad systems also want to extract a purchaser's (decision maker) preferences. The difference is that, ad systems have a broader scope of extracting or predicting a purchaser's preferences to display a certain message, in order to influence a further action by the potential purchaser. More narrowly, recommender systems are focused on recommending particular items to a user, with the action of the user in accepting and potentially rating the item feeding back into our understanding of the user’s preferences. Technically, this means that current ad systems are mostly focused on more accurately predicting a user’s preference based on what we already know (data collected) about the user, but recommender systems have an emphasis on continuously learning the preference of a user for specific item categories.

In practice, recommender systems, DSS, and ad systems tie into the application for which we want to employ these systems for. So the application should largely influence how we design, implement, and improve a system. For example you can see this influence in the terminology e.g. “decision maker”, “purchaser”, and “user”.

In summary, a recommender system is a system that attempts to predict a user’s preference for an item, in order to recommend items closest to the user’s preferences, while learning the user’s preferences as the user provides feedback.

There are several computational approaches to developing recommender systems. In the modern sense of it, the two main approaches are the data mining approach and the machine learning approach. In practice, the most common algorithms and methods end up being very similar, with the difference between the approaches being related to the historical developments of each field. The difference between the approaches of data mining and machine learning is an interesting topic on its own. Here we will take the machine learning route. So, how do we, or more accurately, our machines learn a user’s preferences?

Learning User Preferences

To predict a user’s preferences for a new item, a machine learning method must first train on available data to learn to compute the user’s current preferences. If we assume that each item of a specific item category, e.g. movies, has a feature set that represents the properties of that item (\(X\)), and each item can be expressed in terms of those features, then each user can also be represented with parameters (\(\theta\)) with specific values related to each feature of an item category. Having the parameter set of a user, and the feature set of an item, a hypothesis function can be found that maps the features and parameters to a value that can represent the preference of user for that item, i.e. the preference of user \(j\) for item \(i\) would be:

\(Preference(i, j) = h(\theta, X)\)

Now if we collect data on user’s preferences and calculate either directly or indirectly their preferences for certain items, and we name this the true preference \(y(i, j)\), then for our machine to learn a model of a user's preferences, the objective becomes minimizing the difference between the model’s predicted value (hypothesis) for the user’s preference and the user’s true preference for a given item (the cost function):

\(min J = difference(h, y)\)

Fundamentally, there are two basic ways to learn a user’s preferences:

1. Content-based: the properties (features) related to a certain item category are pre-set (someone sets it based on our knowledge) for all items, so the learning will mainly be focused on computing the user parameter set
2. Collaborative-learning (more formally collaborative-filtering): we don’t know the values of the items' feature sets, therefore the system must guess the value of features based on the current preference data that includes other user’s preferences. This way, the machine learning model must keep improving the current guess as the users rate items

In both cases, learning requires feedback from the user. This feedback can be direct (explicit feedback), e.g. the user rates the item after accepting it. Feedback can also be indirect (implicit feedback), e.g. the mere act of the user accepting an item. Sometimes other factors like time spent viewing an item can be used as a heuristic for guessing user preferences. This is called inference from behavior, and it’s a type of implicit feedback. Quantitatively, one way to express this is as a binary “prefers” or “doesn't prefer” (yes/no) with a confidence interval related to that binary preference. This is an example of how the business logic of an application influences a system’s methods, here, improving the system’s understanding of user preferences.

Since we want the machine to do all the learning, lets dive into the machine learning methods for recommender systems. For the sake of familiarity and to have a more concrete discussion, let's consider a Netflix like application where we want to recommend movies to users.

Recommender Systems, the Machine Learning Approach

As discussed, the two main machine learning methods for recommender systems are Content-based systems or Collaborative Filtering systems. The difference between the two methods is that with the former, the item features are pre-set, while the latter uses data collected from all users to guess (and improve on the guess) the values for item feature sets.

In both cases, learning happens when we receive feedback from the users. What happens is that the users label the data for the system, explicitly or implicitly, indicating their preference for the movies they have watched. In the movie recommendation context, let’s assume that our feedback (labelling) mechanism is that the user may rate their selection after watching. For example Jen might rate “The Terminator” 4 stars out of 5. As mentioned, other indirect ways to label the data can be used such as those that infer from user behavior. Back to the movie example, lets use the following notation for the problem:

\(n_{u}\): number of users
\(n_{i}\): number of items (movies in this case)
\(r(i,j)\) = 1 if user \(j\) has rated item \(i\)
\(y(i,j)\): the rating of item \(j\) given by user \(i\), only if \(r(i,j)\) = 1
\(X(i)\): the feature vector for item \(i\), i.e. the set of properties for the item category related to item \(i\)

In the case of movies, the feature set can be movie genre, actors, director, year screened, action level, romance level, humor level, etc.

Content-based recommender systems

In content-based recommender systems, the values for the features of each item is pre-set, and the objective is to compute parameters for each user, based on their past ratings, in order to predict their preference for a new item. In this case:

\(\theta(j)\): the vector of parameters for user \(j\)
\(m_{j}\): number of items rated by user \(j\)

The predicted rating for a new item \(i\) for user \(j\) is then \(\theta(j)^{T} X(i)\), and the cost function can be written similar to that of the least square linear regression expression, and therefore the objective will be to minimize:

\(argmin_{\theta(j)}\frac{1}{2m_{j}} \sum_i(\theta(j)^{T} X(i) - y(i,j))^{2} + \frac{\lambda}{2m_{j}}\sum_{k=1}^n(\theta_{k}(j))^{2}\)
with the first term being summed where \(r(i,j)\)=1, and where \(\lambda\) is the regularization factor. For all users, this becomes:

\(argmin_{\theta}\frac{1}{2}\sum_{j=1}^{n_{u}} \sum_i(\theta(j)^{T} X(i) - y(i,j))^{2} + \frac{\lambda}{2}\sum_{j=1}^{n_{u}}\sum_{k=1}^n(\theta_{k}(j))^{2}\)
with the first term being summed where \(r(i,j)\)=1.

To compute the \(\theta\)s (user parameter values), an optimization algorithm like gradient descent can be used, which in this case can be written as:
Iteration to convergence:

\(\theta_k^{new}(j) = \theta_{k}^{old}(j) - \alpha(\sum_i(\theta^{old}(j)^{T} X(i) - y(i,j)X_{k}(i) + \lambda\theta_{k}^{old}(j)))\)
with the last term being zero for \(k\)=0, and the first term being summed where \(r(i,j)\)=1.

Now what if we don’t pre-set the feature values for each item? and want to learn that from data?

Collaborative filtering recommender systems

In collaborative filtering, values for item features are computed based on currently known or computed user preferences. This means given the \(\theta\) values for users, learn \(X(i)\). By estimating \(X(i)\), new \(\theta\)s can be computed resulting in more accurate estimations. To start this cycle, the machine can start with a guess for the parameter vector, compute the feature vector, compute the new parameter vector, and so on…

In practice, using the least square linear regression method, the feature and parameter values can be computed at the same time. So the expression becomes:

\(\small argmin_{\theta X}\frac{1}{2}\sum_{i,j}(\theta(j)^{T} X(i) - y(i,j))^{2} + \frac{\lambda}{2}\sum_{i=1}^{n_{m}}\sum_{k=1}^n(X_{k}(i))^{2} + \frac{\lambda}{2}\sum_{j=1}^{n_{u}}\sum_{k=1}^n(\theta_{k}(j))^{2}\)
with the first term being summed where \(r(i,j)\)=1.

The procedure for the algorithm is to first, initialize the feature vector and parameter vector to some arbitrary value. In practice values between 0.05 to 0.1 works OK (in general small values are recommended). Then use an optimization algorithm, such as gradient descent, to minimize the joint cost function for computing the values for all item features and user parameters. And finally predict user preference for items by computing the \(\theta(j)^{T} X(i)\) for each user-item pair.

Now how do we find the movies similar to a preferred one? We search for the movies with feature values that are mathematically (or semantically) nearest in distance to the features values of the highly preferred ones!

Big Data Implementation

Today in practice, typically lots of data is collected continuously from user preferences. This means an engineer has to process and run these algorithms on very large data sets, and needs to bring in the big guns. Fortunately, several tools are at your fingertips, with the most convenient, I believe, being Apache Spark. In their own words, “Apache Spark™ is a fast and general engine for large-scale data processing”. Apache Spark is built with the Scala programming language and uses the Apache Hadoop big data file system HDFS, has Java and Python connector libraries, and has a machine learning library named MLlib that fortunately supports developing recommender systems. I will walk you through an example of building a movie recommender system that was presented at the Spark Summit 2014 using data from MovieLens.

Setting up Apache Spark

Setting up Spark is extremely easy if you have Java and Python (with NumPy) installed on your machine. If you don’t have these installed, on an Ubuntu machine using one of the recent LTS releases, first install Oracle’s latest JDK. Then install the Python package from the folks at Anaconda, which has been tuned for advanced engineering and scientific computing.

Then download a standalone compiled version of Spark, e.g. the "pre-built for Hadoop 2.4", and extract it using "tar -xzvf path/to/file". That’s it, you have everything you need to run Spark Python scripts.

Coding the system in Python

The movie recommender code here is adapted from the recommender program at the Spark Summit 2014 and slightly modified for a quick practice building a recommender system with Spark. The recommender system in Spark uses the collaborative filtering approach with the Alternative Least Squares (ALS) method, which is very similar to what we discussed in the previous section (with further enhancements). You can learn more about the method here. The spark implementation is based on this, and more information on how it's implemented here. Our complete script is:


Now lets go through the code. The main function starts with setting up the Spark configuration object with certain parameters. Here the Master node is set to local, the application name is given, and the execution memory limit is set to 2Gb. This is done in the SparkConf() and SparkContext() lines (lots of good info in Spark documentation about this).

Then the training file with all the rating is loaded as a spark Resilient Distributed Dataset (RDD), and the parseRating function is applied to each line that has been read from the file. The parseRating funciton takes a line in the format of userId[tab]movieId[tab]rating[tab]timestamp[tab], and returns a set in the form of (key, userId, movieId, rating) where the key is the last digit of that record's timestamp (we’ll see why later).

Then a quick head count on the data is performed to output the number of ratings, users, and movies.

Next The data is divided into three parts for training, validation, and testing. This is why the sets were keyed with integers < 10. These methods are very quick and scalable big-data tricks to make random key-value buckets without using any randomizing functions.

The next section is where the ALS method is used for training the system. The program uses a list of ranks (the number of movie features \(X\) also known as latent factors), regularization factors (\(\lambda\)s), and number of iterations to find the best combination of these values that result in the best training-validation result. The “best” is determined based on computing the RMSE of the validation data with the smallest RMSE representing the best model.

The program finally computes the RMSE for the test data and prints the results.

Running the program

First, download movie training data from MovieLens to a project directory. There are three different data packages, each with 100k, 1M, and 10M movie ratings. You can start playing around with the 100k first. The rating files are named u*.base, u*.test containing 80/20 splits of the data. The rating data is re-arranged into 5 training and test files, containing disjoint test sets for 5 fold cross validation. Since we use a 60/20/20 split on data for for training, validation, and test, we can use only one file, e.g. u1.base (we will lose 20% of data in the u1.test, so you can make a combined file to load or just leave it for practice purposes).

To run the program, you can simply copy the python script file to the directory with the movie rating training data and run the following in the directory:

$path/to/sparkdirectory/bin/spark-submit recommender_spark.py /path/to/ratings-training-data-file
$~/Applications/spark-1.1.0-bin-hadoop2.4/bin/spark-submit recommender_spark.py u1.base

Experimenting

Now you can start experimenting with different regularization factors, ranks, and number of iterations in the program. To build a cloud big data recommender system, try setting up the program and running it on an Amazon AWS Ubuntu machine instance. As an update to this post, I will add a discussion on issues and performance enhancement for recommender systems.