James Neufeld suggests that Bayesian Bandit algorithms can be applied to this problem. The basic idea is that you would define a stochastic quality metric whose distribution for each comment depends on the up and down votes that comment has received.
Normal ranking algorithms try to estimate the single best value for this quality metric. Neufeld suggests that this value should be sampled from a beta distribution which models the probability that a user would mark the comment positively given that they have marked the comment at all. To present comments to a user, the metric would be sampled independently for each comment and the comments would be sorted according to the resulting scores. Different presentations would necessarily result in different orders, but as users mark comments positively or negatively, the order should converge to one where the comments presented near the top of the list have the highest probability of being marked positively.
One very nice thing about this approach is that it doesn't waste any cycles on determining the ranking of low quality comments. Once the quality of these comments has been determined to be relatively lower than the best columns, no more learning need be done with those comments. This accelerates learning of the ranking of the best options dramatically.
This idea is interesting enough that I built a quick implementation which you can find on github. The main sample code there invents several hundred "comments" each with a uniformly sampled probability of getting a positive rating. The ideal behavior for ordering the comments would be to put the comment with the highest probability of getting a positive rating first and the one with the lowest probability last. The way that the program proceeds is that it picks a pageful of twenty comments to show and then proceeds to generate ratings for each of the comments on that page according to the underlying probability associated with the items displayed. The process of generating pages of comments to show and applying feedback is repeated and performance is measured.
Here are some results of running the program. Here we have 200 total comments, of which 20 are shown on the page that defines which comments are rated. Precision is measured here to determine how many of the best 10 comments are shown on the page. As can be seen, the system shows immediate improvement as ratings are collected. The performance rises from the initially random 10% precision and passes 50% after 30 pages of ratings.
As James demonstrated in his article and as others have demonstrated elsewhere, this class of algorithm is very effective for this sort of bandit problem. What is much less well known is how easily you can build a system like this.
Try it yourself
To run this code, you will need git, maven and java 1.7. To download the source code and compile the system, do this
$ git clone git://github.com/tdunning/bandit-ranking.git
$ cd bandit-ranking
$ mvn package
This will download all dependencies of the code, compile the code and run some tests. To run the test program, do this
$ java -jar target/bandit-ranking-*-with-dependencies.jar
$ java -jar target/bandit-ranking-*-with-dependencies.jar
The output is a thousand lines of numbers that you can drop into R, OmniGraphSketcher or even Excel to produce a plot like the one above.
Quick code dissection
In com.mapr.bandit.BanditRanking, the main program for this demo, a BetaBayesFactory is used to construct several BayesianBandit objects (for average results later). This pattern can be used with other kinds of bandit factories.
The BayesianBandit objects allow you to do a variety of things include sampling (BayesianBandit.sample) for the current best alternative, ranking (BayesianBandit.rank) a number of alternatives and providing training data (BayesianBandit.train). Sampling is used in a traditional multi-armed bandit setting such as with A/B testing. Ranking is used as it is here for getting a list of best alternatives and training is used ubiquitously for feeding back training data to the bandit.
Evaluation can be done by computing precision as is done here (how many good items are in the top 20?) or by computing regret. Regret is defined as the difference between the mean payoff of the best possible choice and the mean payoff of the choice made by the bandit. For the ranking problem here, I assume that payoff of a page is the sum of the probabilities of positively rating each item on a page.
The BetaBayesFactory internally uses a beta-binomial distribution to model the likelihood of a positive rating for each rank. A more general alternative would be to use a gamma-normal distribution. This can be done by using the GammaNormalBayesFactory instead. This extra generality comes at a cost, however, as the graph to the left shows. Here, the beta-binomial distribution results in considerably faster convergence to perfect precision than the gamma-normal. This is to be expected since the beta-binomial starts off with the assumption that we are modeling a binary random variable that can only take on values of 0 and 1. The gamma-normal distribution has to learn about this constraint itself. That extra learning costs about 50 pages of ratings. Put another way, the cumulative regret is nearly doubled by the choice of the gamma-normal distribution.
In order to understand what the algorithm is really doing at a high level, the graph on the right is helpful. What it shows is the number of times comments that are at different ranks are shown. What is striking here is that comments that are below the fourth page get very few trials and even on the second page, the number of impression falls precipitously relative to the first page of comments. This is what you would expect because in this experiment, it takes only a few ratings on the worst comments to know that they stand essentially no chance of being one of the best. It is this pattern of not sampling comments that don't need precise ranking that makes Bayesian Bandits so powerful.
Posts
6 comments:
Can this be modified so the weight of votes decays overtime? While comment quality isn't going to change overtime (and all your votes are going to happen in a short period of time) this isn't true for voting on things like apps. In the case of apps you'd like to give an app that has a poor score it a chance to re-assert itself if it hasn't received a vote for a while. And similarly a highly scored app should be able to drop if all the recent votes are negative (even if they have been positive for a long time).
Yes. Decaying feedback is very easy to implement, though a bit dangerous as well since eventually everything can decay to complete ignorance (which you probably don't want).
With the beta distribution, there are two parameters which can be equated with the number of positive and the number of negative ratings. If these decay with time, the system reverts to its prior.
My own feeling is that the preferable way to do this decay is to use a mixture of very long-term and medium to short term decays. That way the system won't revert to complete ignorance, but will revert to a less emphatic state.
It is also possible to restart new bandits at intervals and use a meta-bandit to decide which bandit is better, the brand-new naive one or the wise old one. The meta-bandit can have a simple forgetting strategy. This effectively implements change-point detection.
Your idea to use this sort of system for app rating is an excellent idea.
Nicely done, the analysis makes for a pretty compelling case all together.
Although I'm certainly an advocate of this approach over any existing implementations, I do have one small word of caution, although it's more of a theoretical issue. Essentially, there is a very subtle assumption being made here, namely, that the vote percentage of each comment is independent of it's position, and of the comments surrounding it. Which, of course, is not true in practice.
In this context, this is best illustrated by considering the case where two people post roughly the same joke (something that happens a lot on reddit, hah). The comment that appears secondly in ordering given to the user will obviously suffer more downvotes. In this situation this would likely be addressed by one of the comments slowly losing out over time. However, there is certainly a nonzero chance that this approach will converge to some suboptimal ordering.
While this final ordering is probably going to be pretty close to the best one in practice, in any theoretical analysis, this fact directly implies the algorithm must have O(n) regret.
We could, though, find the optimal ordering in O(log n) time by simply making each "arm" define an entire ordering (the payoff would be the total ratio of up/down votes for that sample). Of course, this would create K! arms, which is a rather large constant multiplier on that log term.
James,
In the implementation I give, the order is heavily randomized. That should mean that context effects are randomized as well.
If the process is preserving order and merely changing visibility, then what you say is fair, but I think that it won't matter in practice since the first comment of a duplicative high quality pair will tend to dominate the second if only because it will get more training by appearing first. If the second appears very soon and is significantly better, then the early training of the first can be over-ridden.
@Terry,
Yes. Many communities do choose to hear only from people that they agree with. It is hardly limited to people who downvote Republicans or religionists since Republicans and religionists do the same thing.
I would not demean teenage girls by assuming that they are the archetypal example of this behavior. They do exhibit this behavior, as do pretty much all humans.
None of this changes the mathematics involved in trying to predict down-voting behavior and that is all that is addressed in my blog. Rectifying all of human misbehavior is not the goal of the mathematics I do.
Post a Comment