How to rank products based on user input

This is a post I’ve been meaning to write for over a year, since I first came across an article entitled How Not to Sort by Average Rating (made popular on, amongst other places, Hacker News). Recent mentions of that article have finally spurred me to finish this off. Well, better late than never.

The Context

Let’s say you have a lot of things. Let’s say your users can vote on how much they like those things. And let’s say that you want rank those things, so that you can list them by how good they are. How should you do it?

You can find examples of this pattern all over the web. Amazon ranks products, Hacker News ranks links, and Yelp ranks businesses, all based on reviews or votes from their users.

These sites all rank the same way: they compile user votes into a score, and items are ranked by that score. So how the score is calculated determines entirely how the items are ranked.¹

So how might we generate such a score? The most obvious approach is to simply use the average of the users’ votes. And, in fact, that is what these sites do. (Hacker news also mixes in a time-based measure of freshness.)

Unfortunately, there’s a big problem with using the average: when you only have a few votes, the average can take on extreme values. For example, if you have only one vote, the average is that vote. (And if you have no votes… well, what do you do then?) The result is that low-vote items can easily occupy the extreme points on the list—-at the very top or very bottom.

You see this problem every time you go to Amazon and sort by average customer review. The top-most items are a morass of single-vote products, and you have to wade through them before you get to the good stuff.

So what would be a better ranking? Well, we’d probably like to see an item with 50 5-star votes before we see an item with a single 5-star vote. Intuitively speaking, the more votes, the more certain we are of an item’s usefulness, so we should be focusing our attention on high-score, high-vote-count items.

And, although we’re less likely to be concerned with what’s at the bottom of the list, the symmetric case also seems right: an item with 50 1-star votes should be ranked lower than one with a single 1-star vote, since the 50-star one is more certain to be bad.

Taken together, these two observations suggest that the best ordering is one where the low-vote items are placed somewhere in the middle, and where high-confidence items occupy the extremes—good at the top, and bad at the bottom.

(We could develop this argument more formally, by talking about things like expected utility / risk, but I’m going to leave it just intuitive for this post.)

The Problem with Confidence Intervals

The “How Not To” article linked above suggests that the right way to rank products to avoid the problem with the average is to construct a confidence interval around the average vote, and rank by the the lower bound of that interval. This confidence interval has the following behavior: when the amount of data is large, it is a tight bound around the average vote; when the amount of data is small, it is a very loose bound around the average.

Taking the lower bound of the confidence interval is fine when the number of votes for an item is large: the lower bound will be close to the average itself. But, just as with the average, the problem with this approach occurs when the number of votes is small. In this case, the lower bound of the confidence interval will be very low.

The result is that new items with few votes will always be ranked alongside the bad items with many votes, at the bottom of the list. In other words, if you rank by the lower bound of a confidence interval, you will rank an item with no votes alongside an item with 1,000 bad votes.

If you use this approach, every new item will start out at the bottom of the list.

Enter Bayesian Statistics

Is there a better alternative? Fortunately, this kind of paucity-of-data problem is tailor-made for Bayesian statistics.

A Bayesian approach gives us a framework to model not only the votes themselves, but also a prior belief of what we think an item looks like, before seeing any votes. We can use this prior to do smoothing: take the average vote, which can be jumpy, and “smooth” it towards the prior, which is steady. And the smoothing is done in such a way that, with a small numbers of votes, the score mostly reflects the prior, and as more votes arrive, the score move towards the average vote. In other words, the votes are eventually able to “override” the prior when there are enough of them.

Being able to incorporate a prior has two advantages. First, it gives us a principled way of modeling what should happen with zero votes. We are no longer at the mercy of the confidence interval; we can decide explicitly how low-vote products should be treated. Second, it provides a convenient mechanism for us to plug in any extra information that we have on hand. This extra information becomes the prior belief.

But what kind of extra information do we have? Equivalently, how do we determine the prior? Consider: when you decide to watch a Coen brothers movie, you make that decision based on past Coen brothers movies. When you buy a Sony product, you make a decision based on what you know of the brand.

In general, when you know nothing about an item, you can generalize from information about related items, items from similar sources, etc. We will do the same thing to create a prior.

Let’s see how we can use Bayesian statistics to do smoothing towards a meaningful prior.

Solution #1: the “True Bayesian Average”

The first solution, made popular by IMDB, is the so-called “true Bayesian average” (although so far as I know that terminology does not actually come from statistics). Using TBA, to compute a score , we do:

where is the average vote for the item, is the number of votes, is the smoothing target, and is a tuning parameter that controls how quickly the score moves away from as the number of votes increases. (You can read more about the Bayesian interpretation of the ‘true Bayesian average’.)

This formula has a nice interpretation: is a pseudo-count, a number of “pseudo” votes, each for exactly the value . These votes are automatically added to the votes for every item, and then we take the average of the pseudo-votes and “real” votes combined.

In this formula, the prior is , the smoothing target. What value should we choose for it? It turns out that if we set to the average vote over all items (or over some representative class of items), we get the behavior we wanted above: low-vote items start life near the middle of the herd, not near the bottom, and make their way up or down the list as the votes come in. (You can read a more rigorous argument about why using the global average is a good target for smoothing.)

The TBA is easy to implement, and it’s trivial to adapt an existing system that already uses average votes to use it.

But we can do better.

The Problem with the “True Bayesian Average”

The problem with the TBA is that it assumes a Normal distribution over user votes.

Taken at face value, we know this assumption is bad for two reasons: one, we have discrete, not continuous, votes, and two, we have no actual expectation that votes will be normally distributed, except in the limit. But in reality, neither of these are significant problems. We will always have some modeling assumptions of dubious correctness for the sake of tractability, and these are within the realm of plausibility.

The bigger problem with the assumption of Normality is that it forces us to model items as if they had some “true” score, sitting at the mean of a Normal distribution. But we know some items are simply divisive. Some Amazon products accrue large numbers of both 5-star and 1-star reviews. Some movies are loved and hated in equal measure. Being able to model those kinds of distributions accurately would be to our advantage, and a Normal distribution won’t let us do that.

Ultimately, of course, we need to produce an ordering, so we need to condense everything we know about an item into a single value.² But it would be to our advantage to do this in an explicit, controllable manner.

This suggests we would like a solution which decomposes scoring into three parts:

1. Our prior beliefs about an item;
2. The users’ votes on an item; and
3. The mapping between the vote histogram and a score.

Such a system could both account for paucity-of-data problems, and provide us with explicit control on how the items are ranked.

Let’s see how we can do this.

Solution #2: Dirichlet Priors and an Explicit Value Function

To accomplish these goals, we have to forsake the normal distribution for the multinomial. A multinomial model will let us represent the complete histogram of the votes received for each items. For example, for Amazon products, a multinomial model will capture how many votes for one star, how many votes for two stars, and so on, a product had. If there are types of votes that users can assign to an item, we can parameterize (i.e. fully specify) the corresponding multinomial with an -dimensional vector.

(I’m glossing over one technicality, which is that a multinomial really measures only the relative proportion, not the actual counts, of the histogram. But this detail won’t matter in our case.)

To fit the multinomial into a Bayesian framework, we will model our prior belief as a Dirichlet distribution. Just as a multinomial distribution represents a single -dimensional vector, a Dirichlet distribution is a probability distributions over all such -dimensional vectors. In effect, it is a distribution over all possible vote histograms for an item.

We use the Dirichlet because it is a conjugate prior of the multinomial. This means that when we use Bayes’s rule to combine the Dirichlet with the multinomial (we’ll see how to do this below), the resulting distribution is also a Dirichlet. This property is very convenient because it allows us to keep the representation to a single form, and use the same technique iteratively—we start with a Dirichlet, and every new set of votes we incorporate leaves us with a Dirichlet.

The Dirichlet is a complicated distribution. Luckily, the properties we’re interested in make it very simple to use.

For one, it is parameterized by a histogram just as well as a multinomial is. That is, if we write for a Dirichlet distribution and for a multinomial, describes a multinomial distribution corresponding to a vote histogram for a particular item with 7 one-star votes, 3 two-star reviews, etc., and describes a Dirchelet. Of course, the meaning of the Dirichlet is quite different from the meaning of the multinomial, and for the sake of brevity we won’t go into how to interpret it here. But for our purposes, this is a nice property because it means that specifying a Dirichlet given a vote histogram is trivial.

The other very handy property of Dirichlets is that when they’re combined with multinomials using Bayes’s Rule, not only is the result a Dirichlet, it’s a Dirichlet that’s easily specifiable in terms of the two input distributions. Recall that Bayes’s Rule states:

where is the set of observed votes and is a possible model of the item. In our case, that means that is our prior belief, is what our actual votes look like given the model, is our updated model, and is some normalizing constant, which we can ignore for now.

If we call our prior belief the Dirichlet and our conditional distribution the multinomial , and skip over all the difficult math, then we can turn Bayes’s rule into a rule for updating our model:

In other words, to create the posterior (that is, resulting) distribution, all we need to do is add the two input histograms. (Note that falls away.)

So now we have a way of taking our prior information, incorporating the user votes, and finding the resulting distribution. The resulting distribution is also a vote histogram for an item, smoothed, just as in the TBA case, towards the prior belief histogram. (And, in fact, the same pseudo-count analogy applies: are the pseudo-votes, and the real votes, and we’re simply adding them together. Neat, huh?)

But what do we do with that?

The final step of the puzzle is to transform this distribution into a single score for ranking. The best way to do this is to take a function that describes the score of a particular vote histogram, and compute the expected value of that function under our distribution. The expected value will represents the function as evaluated over every possible value in the distribution, weighted by the probability of seeing that value. In effect, it will capture the function as applied to the entire distribution, and package it up nicely into a single number for us, ready to be used as a score.

To compute the expected value, in general, you are required to solve a nasty integral. Happily, we can take advantage of one final property of the Dirichlet, which is that, if your Dirichlet is parameterized by , the expected value of the proportion of votes in category is simply:

In other words, the expected value of the proportion of votes in the th bucket is simply the proportion of that parameter over the total sum of the parameters.

If we stick to a linear scoring functions, we can take advantage of the linearity of expectation and use this result, avoiding anything more complicated than multiplication.

For example, sticking with our Amazon case, let’s use the “obvious” function:

where we give each one-star vote a 1, each 2-star vote a 2, and so on, and just sum these up to produce a score. Because this is linear, the expected value of this function under our Dirichlet is simply:

Of course, this simple function has many issues. For example, are these weights really want you want in practice? They imply that a five-star score worth exactly 5 times a one-star score, which is may not be the case. And it does not do anything special with “divisive” items, which you might want to up- or down-rank.

But, this framework will allow you to plug in any function you want at that point, with the caveat that non-linear functions may involve some nasty integration.³

So there you have it! We’ve achived all three of our desired goals. We can take a prior belief, any number of user votes (including none at all), and a custom scoring function, and combine them all to produce an ranking.

The final question is what prior belief we should use. Intuitively (and reasoning by analogy from the TBA case above), if we use the mean vote histogram over all items, scaled down by some tuning parameter, we should have the desired behavior introducted in the first section, where low-vote items start near the middle of the list, and high-vote high-score items are at the top, and high-vote low-score items at the bottom. Proof of the correctness of this statement is left as an exercise to the reader. (Hint: see the related blog post.)

At Long Last, Some Code

Let’s wrap it up with some Ruby code. If you’ve skipped to this point, congratulations—all of the above was a very long, very discursive way of arriving at something that is, in fact, very simple:

## assumes 5 possible vote categories, but easily adaptable

DEFAULT_PRIOR = [2, 2, 2, 2, 2]

## input is a five-element array of integers
## output is a score between 1.0 and 5.0
def score votes, prior=DEFAULT_PRIOR
  posterior = votes.zip(prior).map { |a, b| a + b }
  sum = posterior.inject { |a, b| a + b }
  posterior.
    map.with_index { |v, i| (i + 1) * v }.
    inject { |a, b| a + b }.
    to_f / sum
end

If you play around with this method, you can see:

• With no votes, you get a score in the middle of the range, 3.0.
• As you add high scores, the value increases, and as you add low scores, it decreases.
• If the score is, say, 4.0, adding more 4-star votes doesn’t change it.
• If you make the default prior bigger, you need more votes to move away from 3.0.

Enjoy!

¹ Strictly speaking, there’s no reason you need to generate an intermediate score if all you’re interested in is a ranking. You could generate an ordering of the items directly and skip the middle step. But on these sites, the intermediate score value has useful semantics and is exposed to the user anyways.

² Basically. Don’t get nitpicky with me.

³ You can probably get away with just running the function on directly, i.e. using a “point estimate” instead of an expected value. Be sure to understand the implications.

• stats.