Matrix Factorization for Ad Recommendation

This blog post describes how matrix factorization can be applied to the problem of ad targeting. It draws from my experience of developing a machine-learning-based solution for this task for the real-time performance marketing company twiago together with other colleagues from our Data Science team.

The problem: Ad targeting

Let us begin by framing the problem: We have an idle website floating in the endless vastness of the internet. Like this:

The page contains two div containers A and B. Whenever a user visits our page, we want to place ads in these containers. For example, such an ad could be a banner ad as in the following picture:

Typically, we would have many of these possible ads. The decision which ad should be placed in which ad container is handled by an ad server that handles the request for ad material sent by the web page. This is depicted in the following illustration:

This all should happen in a blink of a moment and finally the page renders to the users containing two ads.

Now the next interesting thing that could happen: the user clicks on one of the ads. If so, the advertiser will pay a certain amount of money to the operators of the ad server and the page owner.

There is a whole industry for this and in general a huge market for online advertising.

As we have seen in our toy example, there are two major players: the publisher (web page owner) and the advertiser (the person advertising goods and services). Typically a publisher does not host one single web site, but several sites under his domain. A newspaper or online sports magazine might be a good example. Our ad server would also serve a network of publishers. This is illustrated here:

There is a mutual benefit here: Advertisers can publish on various sites, potentially reaching different audiences, while publishers will benefit from “crowd wisdom” (or: collaborative filtering ) as ads are exposed to more users and will finally flock to the right ad spaces.

The performance indicator: Click-through rate

We can measure the performance of an ad by its click-through rate (CTR). It describes the probability of the ad receiving a click when it is shown. Mathematically it is given by this ratio:

CTR = (Number of clicks) / (Number of impressions)

In this formula you should think of the denominator as the number of  “unique views by unique users”. The click-through rate depends on the ad space and the ad. The number of clicks and impression counts are with respect to a fixed time window (one week in our case).

Side note: What technically counts as an impression can be defined by certain industry standards (e.g. those provided by www.iab.com ) and is part of the implementation of the ad serving technology. We can ignore the technical details and trust the ad server to provide a systematic way of counting “impressions” and providing this information to us.

The problem restated: Filling missing values

We can rephrase the problem stated above as in the following terms: we have to fill in missing values of the click-through rate matrix and rank ads by the thus predicted click-through rates. Of course, the predictions should somehow align with the already known values.

Assuming that we have M ad space in our complete network of publishers and N ads we could deliver, we can write down a matrix of shape (M x N) that records for each possible combination (Ad, AdSpace) the currently observed click-through rate. This matrix is called click-through matrix (for short: CTR matrix).

Of course, this matrix would contain missing values for the following reason: not every ad has been (and likely never will be) shown on all possible ad spaces. So certain combinations have not occurred yet. As said, we would like to fill in these values with the constraint that we do not want to deviate too much from the known values with our predictions.

Side note: Typically this matrix would be rather sparse. But thanks to the fact that we target ad spaces (rather than individual users) on websites with a lot of traffic, impressions and click counts for individual users aggregate rather quickly to yield a matrix with a good degree of filling in the course of a week which was the time frame for our batch job.

The solution: Matrix factorization

We are interested in predicting these missing values since they might reveal how well a yet unknown combination of ad and ad space would perform and whether it would make sense to bring them together.

How can we achieve this? A popular technique for such collaborative filtering tasks is matrix factorization, which is what we also use here.

Matrix factorization in a nutshell

To outline the geometric idea behind this, recall how the matrix product X of a matrix W with the matrix H is given in algebraic terms:

This formula computes the entry X[i,j] at position (i,j) as dot product of the i-th row of W with the j-th column of H. This is the algebraic definition usually given. A more appealing geometric picture can be obtained as follows:

This says that the j-th column of the product X is given by weighting the columns of W with the corresponding weights from the j-th row of H and summing everything up.

Depending on your taste, this might be a little bit too much of math. But let us give a interpretation of this in more layman terms: whenever we take a data matrix X of records and write it as product X=WH as in the following picture

we can use the second factor H as the new representation of the data and reconstruct the original data use the first factor W as seen here:

Now for a given matrix X there might be several ways to decompose X as product WH. A point of interest is to choose the pair (W, H) such that the number of rows of H (equivalently: the number of columns of W) is strictly lower than the number of rows of the original matrix X. This would mean that we reduce the number of features in our representation and correspond to data compression.

The idea is that during the compression we will learn what information present in X is important and which is not. But how would we learn this compressed representation?

Once again, machine learning (a.k.a. mathematical/numerical optimization) comes to the rescue. If you liked the math above, this picture is for you:

We attempt to approximate X as WH (denoted as X with a hat in the picture). For this, we try to minimize the error J(W,H). This error is given by comparing the squared errors between the known entries of X and the approximation WH. (Remember our click-through matrix has missing values; so this fits into the overall picture.) One can use the Alternating squares algorithm (ALS) to compute such an approximation.

The deployment

We delivered a software solution that runs a weekly batch job in the cloud. It first fetches the impression and click statistics from the existing ad server and then computes a table of favorable ad and as space combinations for the next week. For this, it used the mathematical optimization we outlined above.

The final solution is deployable to Amazon Web Serives (AWS)  as JAR. In this concrete case we use a single EC2 instance to run the weekly batch job.

A note on the software development part: we decided to use Apache Spark and Scala to code everything. Less so because we had to deal with big data (we are looking at a few GBs) but rather  because it allows us to write ETL pipelines and machine learning components using a single ecosystem or API. (Of course, this is also possible with other solutions.)

The outcome

In a live test we observed a performance improvement of 15 – 20 % compared to the existing system based on expert rules. This is quite good and shows the potential of using a machine-learning-based approach in this case.

Summary

In this blog post we explained how matrix factorization can be used to predict missing values from a data matrix and saw how to apply this technique to the problem of ad targeting.