References for On-line Algorithms

[See also my more recent blog on this talking about using bandits for ranking rated items like comments]

I have been speaking lately about how various on-line algorithms have substantial potential for various real-time learning applications.  The most notable of these algorithms are Thompson sampling for real-time handling of multi-armed bandit and contextual bandit problems and an algorithm due to Shindler, Myerson and Wang for fast $k$-means clustering of data.  Since I have had a number of requests for references back to the original sources for these works, I figured a few blog posts would be a good thing.  This post will describe the multi-armed bandit work and the next will describe the clustering work.

The Basic Problem - Multi-armed Bandits

For the bandit problems, there are two basic problems to be dealt with.  The first and most basic problem is that of the multi-armed bandit.  In this problem, you can sample from any of a finite number of distributions and your goal is to maximize the average value of the values that you get.  This can be cast into a number of practical settings in which you select which slot machine to put a quarter into, or you select which on-line ad to present to a user or you select which landing page to deliver to a user's browser should see when they visit a particular URL.  It is common to simplify this case further by assuming a stationary distribution.  Obviously, at least one of the distributions you are picking from has a mean equal to the large mean of any alternative.  Any time you take a sample from a distribution that has a smaller mean, you fall behind the theoretical best, on average, that you could have achieved by picking from (one of) the best distributions.  The degree by which you fall behind is known as the regret that you incur.

The key to the multi-armed bandit problem is that you cannot know which distribution might have the largest mean.  This means that you have to sample all of the distributions in order to estimate their means, but this implies that you have to sample from the lesser distributions in order to determine that their are, in fact, inferior.

There are well known bounds on how well you can actually solve this problem.  There are also a number of algorithms that have regret on par with these bounds or come reasonably close to these bounds.  Mostly, however, these known solutions have limitations either on the number of distributions they can consider or on the complexity of the solution.

Kuleshov and Precup provide some good examples of how to compare different bandit algorithms in their paper.  This tutorial on bandits provides a wider view of different forms of multi-armed bandit problems with a number of references.

Conspicuously missing from most lists of references, however, is all the recent work using Thompson sampling.  These algorithms, which I have referred to as Bayesian Bandits, have particularly nice properties of simplicity and optimality.  Chapelle and Li provide an empirical look at performance with these algorithms compared to upper confidence bound (UCB) algorithms.  The last paragraph of that paper laments the lack of a theoretical analysis of these algorithms, but that lack was cured shortly in this paper by Agrawal and Goyal.  Scott provided a more comprehensive view of these algorithms under the name of randomized probability matching.  

The idea behind Bayesian Bandits is quite simple.  For each bandit, we maintain use the observations so far to build a posterior distribution for the mean of the associated payoff distribution.  For binary payoffs, it is common to use a $\beta$-binomial distribution and for other cases a $\gamma$-normal distribution works well.  To pick a bandit, we sample a mean for each bandit from these posterior distributions and then pick the bandit with the largest sampled mean.  The new sample from that bandit gives us more data which refines the posterior distribution for that bandit.  We can repeat this process as long as desired.

Extensions to Contextual Bandits

One of the most important characteristics of the Thompson sampling approaches (aka randomized probability matching aka Bayesian Bandits) is that they can be extended to more complex situations.  One setting that I have found particularly useful involves optimizing return not just from a few bandits, but from a parameterized set of bandits that could conceivably even be infinite.  The transformation from the parameters to the bandit distribution is unknown, but if we could know that, we would be able to search the parameter space to find the bandit with the highest mean payoff.  

This formulation is a generalization of the previous case because we can take the parameter to be an integer from $1 \ldots k$ where there are $k$ bandits and the transformation consists of the mean payoffs for each of the $k$ bandits.

The algorithm in the contextual case simply consists of sampling the transformation from some posterior distribution and then solving for the parameters of the bandit that we would like to use.  Some of the parameters might be fixed by the context we are working in which is where the name contextual bandits comes in.

The paper by Scott alludes to this formulation, but the most approachable work on this that I know of is the paper by Graepel, Candela, Borchert, and Herbrich.  In this paper, they describe the operation of AdPredictor, a system used by the Bing search engine to target ads using context.

Bayesian Bandits

The basic idea with Bayesian Bandits is to solve the problem of the explore/exploit trade-off in a multi-armed bandit by keeping a distributional estimates for the probability of payoff for each bandit, but avoiding the cost of manipulating distributions by sampling from those distributions and then proceeding on each iteration as if that were a point estimate.

The advantage that this is that bandwidth assignments will be made according to the best estimate of the probability that each bandit could possibly be the best.  This automatically causes the system to do exploration as long as it is plausible and causes the system to smoothly transition to exploitation when it becomes clear which bandit is the best.  Essentially what this gives us is a Bayesian implementation of active learning.

To illustrate this, here is a graph that shows the posterior distribution of conversion probability for two bandits where we have lots of history for one and only a little history for the other.

You can see that the red bandit with 100 conversions out of 1000 impressions mostly like has a probability of conversion of 0.1, more or less a bit.  The blue bandit with no conversions out of 10 impressions is very likely worse than the red bandit, but there is a small possibility that it is better.  If we just picked the average or mode of these distributions, we would conclude that the blue bandit is worse and wouldn't give it any bandwidth without substantial mechanisms to over-ride this decision.

On the other hand, if we estimate a conversion probability by sampling and use that sampled estimate for targeting, then we will give the blue bandit a little bandwidth and thus a chance to redeem itself.

There are several aspects of the Bayesian Bandit algorithm that are exciting.

• exploration and exploitation are handled uniformly in the same framework
• our internal representation encodes all of the information that we have so we don't confuse evidence of failure with lack of evidence for success
• the algorithm only requires a few lines of code
• the updates for the algorithm can be expressed in terms of back-propagation or stochastic gradient descent
• the performance is really good.

As a bit of a teaser, here are a few graphs that describe how the Bayesian Bandit converges in simulated runs. The first graph shows how the average total regret for the Bayesian Bandit algorithm approaches the ideal as the number of trials increases. This experiment uses normally distributed rewards with $\sigma = 0.1$.  Any algorithm that meets the optimal $O(\log n)$ convergence lower bound is said to "solve" the bandit problem.

The convergence here is very close to the ideal convergence rate.  Note that this graph includes the convergence to optimal payoff, not the convergence knowing which is the better bandit.  This is actually an interesting aspect of the problem since the algorithm will converge almost instantly for cases where the conversion probabilities are highly disparate which will make the payoff converge quickly.  For cases where the conversion probabilities are nearly the same, it will take a long time for the algorithm to determine which is the better bandit, but exploration is not expensive in such a case so the convergence to near-optimal payoff will be even faster than the case where the conversion rates are very different.

For example, here is a graph of the probability of picking the better bandit where the conversion rates are nearly the same.  As you can see, it takes quite a while for the algorithm to split these two options.   The average payoff, however, only changes from 0.11 to 0.12 during this entire convergence and it has already reached 0.118 by the time it is 20% into the process so the cost of a long experiment is not that high.

Sample code for the Bayesian bandit is available at https://github.com/tdunning/storm-counts.

Buzzwords Keynote - Conclusion

In the end, it is up to us to make things better.  We need a way for non-Apache entities to interact with Apache productively.  If we can't do that, then it is quite possible that all of the momentum and excitement that Hadoop now has will be lost.  

Conclusion

The key is that we now have an eco-system, not just a community.  We can make it work.  Or we can elect to let it not work.  Not working is the default state.  We have to take positive action to avoid the default.

Apache can stay a strong voice for business friendly open source by remaining Apache.  Trying to make Apache broad enough to include all of the players in Hadoop and Hadoop derivatives will simply debase the voice of Apache into the average of opposing viewpoints, i.e. into nothing.

There are, however, many other players who are not part of Apache and who should probably not be part of Apache.  There needs to be a way for these others to engage with the Apache viewpoint.  It can't just be on the level of individuals from Apache trying to informally spread the Apache way even though that is critical to have.  It is likely to require a venue in which corporate entities can deal with something comparable to themselves.  A good analogy is how Mozilla participation in W3C has made the web a better place.

But we can make our eco-system work.   It isn’t what it was and it never will be again.

But it can be astonishing

Let's make it so.

Buzzwords Keynote - Part 3

In the third part of my talk, I talked a bit about where Hadoop has come from and where it is going.  Importantly, this involves a choice about where Hadoop and the related companies products and individuals might be able to take things.

Where we are and how we got here

My second section described the rough state of the Hadoop eco-system is a slightly provocative way.  In particular, I described a time when I was on a British train and in partial compensation for delays the operators announced that "free beer would be on sale in the galley car".  Free beer for sale is a wonderful analogy for the recent state of Hadoop and related software.

That said, there are serious problems brewing.  The current world of Hadoop is largely based on the assumption that the current community is all that there is.  This is a problem, however, because the current (Apache-based) community presumes interaction by individuals with a relatively common agenda.  More and more, however, the presence of a fundable business opportunity means that this happy world of individuals building software for the greater good has been invaded by non-human, non-individual corporations.  Corporations can't share the same agenda as the individuals involved in Apache and Apache is constitutively unable to allow corporate entities as members.

This means that the current community can no longer be the current world.  What we now have is not just a community with shared values but is now an eco-system with different kinds of entities, multiple agendas, direct competition and conflicting goals.  The Apache community is one piece of this eco-system.

Our choice of roads

Much as Dante once described his own situation, Hadoop now finds itself in the middle of the road of its life in a dark wood.  The members of the Apache community have a large voice in the future of Hadoop and related software.

As a darker option, the community can pretend that the eco-system that now exists of human and corporate participants is really a community.  If so, it is likely that the recent problems in moving Hadoop forward will continue and even get worse.  Commit wars and factionalization are likely to increase as corporate entities, denied a direct voice in Apache affairs, will tend to gain influence indirectly.  Paralysis in development will stall forward progress of Hadoop itself leading to death by a thousand forks.  Such a dark world would let alternative frameworks such as Azure to gain footholds and possibly to dominate.

In this brighter alternative future, I think that there are ways to create a larger forum in which corporate voices can be heard in their true form rather than via conflicts of interest.  In this scenario, Apache would be stronger because it really can be a strong voice of the open source community.  Rather than being the average of conflicting views, Apache would be free to express the shared values of open source developers.  Corporations would be able to express their goals, some shared, some not in a more direct form and would not need so much to pull the strings of Apache committers.  Importantly, I would hope that Hadoop could become something analogous to a reference implementation and that commercial products derived from Hadoop would have a good way to honor their lineage without finding it difficult to differentiate themselves from the original.  Hopefully in this world innovation would be welcomed, but users would be able to get a more predictable experience because they would be able to pick products offering whatever innovation rate/stability trade-off that they desire.  Importantly, there would be many winners in such a world since different players would measure success in different terms.

We have a key task ahead of us to define just what kind of eco-system we want.  It can be mercenary and driven entirely be corporate goals.  This could easily happen if Apache doesn't somehow facilitate the creation of a forum for eco-system discussion.  In such an eco-system, it is to be expected that the companies that have shown a strong talent at dominating standards processes and competing in often unethical ways will dominate.  My first thought when I imagine such a company is Microsoft, but that is largely based on having been on the receiving end of their business practices.  I have no illusions that talent for that kind of work is exclusively found in Redmond.

In my talk, I proposed some colorful cosmological metaphors for possible worlds, but the key question is how we can build a way for different kinds of entities to talk.  It is important to recognize different values and viewpoints.  Apache members need to understand that not everything is based on individual action, nor do corporation hold the same values.  Companies need to take a strong stance to recognize the incredible debt owed to the Apache community for creating the opportunities we all see.

If we can do this, then Hadoop (and off-spring) really does have a potential to dominate business computing.

Buzzwords Keynote - Part 2

In the first part of the talk, I made the case that Apache Hadoop has lots of head-room in terms of performance.  This translates into lots of opportunity both for open source developers to make Hadoop itself better, but also for companies to build products that derive from Hadoop but improve it in various ways.

The $S$ score

In honor of Steve Jobs whose highest praise is reputedly to say "that doesn't suck", I proposed an $S$ score whose highest score is zero, but for all real systems is always negative.  For a batch, data processing system like Hadoop, I proposed that a good definition of $S$ was the log base 10 of the ratio of the actual performance to the performance implied by hardware limits.

Not suprisingly, the overall score for Hadoop comes out to be somewhere between -5 to -2 depending on desired workload (i.e. Hadoop runs programs somewhere between 100 and 100,000 times slower than the hardware would allow).  For some aspects, Hadoop's $S$ score can be as good as $-0.5$ but generally there are multiple choke-points and some of these are additive.  This is hardly news and isn't even a mark of discredit to Hadoop since the developers of Hadoop have always prized getting things to work and to work at scale above getting things to work within an iota of the best the hardware can do at a particular scale.  Another factor that drives $S$ down for Hadoop is the fact that the hardware we use has changed dramatically over the 6-7 year life of Hadoop.

In defining the value of $S$ for current Hadoop versions, I don't mean to include algorithm changes.  Michael Stonebraker has become a bit famous for running down Hadoop for not doing database-like things with database-like algorithms, but I would like to stick to the question of how fast Hadoop could do what Hadoop is normally and currently used to do.

The key conclusion is that having such a low $S$ combined with high demand for Hadoop-like computation represents a lot of opportunity.  This opportunity involves opportunities for the open source community to make things better.  It also represents opportunities for commercial companies to make money.  The latter kind of opportunity is what is going to shake up the currently cozy Hadoop community the most.

Buzzwords Keynote ... blog edition

There has been a bit of demand for an expanded version of my Buzzwords keynote from a few weeks ago.  This demand has been increased by a particular unfortunate mis-quote in a tweet that suggested that I thought that there was a need for a new organization "to supersede Apache".  Of course, I suggested nothing of the sort so it is a good idea to walk through the ideas that I presented.  The buzz words site has the video of my talk and pdf of my slides in case you want to follow along.

The talk was divided into several sections.  The first one proposed the uncontroversial thesis that Hadoop performs at a level far below the potential offered by modern hardware.  A second section pointed out difficulties with the current social structure surrounding the development of Hadoop and related software.  I then examined what I see as possible futures while describing how I think we will be choosing between these alternative futures.  I will post each section in a separate blog entry.

As I spoke, I encouraged the audience to tweet using the hash-tag #bbuzz and to keep communal notes on a shared Google document.  The tweets are a bit hard to find as befits ephemeral media, but the shared notes are still accessible.

Sections:

The S Score
Possible Futures
Conclusion

Buzzwords Wrapup

Well, Buzzwords is over and my primary conclusion is that I wish I had come last year as well as this year. Isabel and Simon are really making Buzzwords into a major open source conference and with the demise of the European ApacheCon, Buzzwords is probably the the first or second most important open source conference in Europe.  If you only can choose one, I would strongly recommend geeking in Berlin.  It isn't just the conference; there are bunches of related events such as informal dinners, bar camps and hackathons.  Since Buzzwords makes such a strong effort to include North American participants you may even have a better chance of connecting globally by going to Europe than going to a conference in the US or Canada.

The conference itself consisted of two days of scheduled events anchored by keynotes each day.  Doug Cutting gave the first keynote and covered a lot of the history and current state of Hadoop.  As always, his talk was very well done and contained quite a bit of technical information which is refreshing in a keynote.  I gave the second keynote and talked a bit about the state and future of Hadoop, related Apache projects and the burgeoning commercial marketplace.  Some of what I said stirred up a bit of talk, which is good since my primary thesis that we aren't talking enough about how the world of Hadoop and related software is rapidly changing in ways that aren't well recognized.  Stay tuned here for a blog edition of my talk.

There were quite a few excellent technical talks as well.  Among the scheduled talks, Jonathan Gray gave a talk which his usual and customary dose of excellent technical information about how Facebook is using Hbase.  A notable moment came when he was asked about the state of Cassandra at Facebook.  Check out the upcoming video for details on his answer.

Dawid Weiss gave an excellent talk on finite state automata and the difference between deterministic and non-deterministic variants.  The only defect I could see in his presentation was that we couldn't see the eagles on the coins.  Based on the fact that the room was packed (I sat in the aisle on the floor) and the very eager audience questions, I would say that there is a surprisingly strong market place for information on foundational algorithms like finite state transformers.

The lightning talks at the end of day two also had some gems.  Thomas Hall's northern accent blended charmingly with the frank assessment of some of his experiences with certain technical approaches.  I can't possibly convey the tone and content so, yet again, you will need to refer to his slides and the video on the conference web-site.

Frank Scholten also had a lightning talk that contained a very nice walk-through of Mahout document clustering.  What he showed is a work in progress, but already what he has provides a highly requested set of recipes to illustrate a lot of the software in Mahout.

Outside of the conference there was an (excellent) barcamp run by Nick Burch.  I think I learned as much about how to run a barcamp by watching him as anybody did from any of the technical discussions and the technical discussions were pretty excellent.

I have to say that if you want to see me next year in early June, there is a high likelihood that you will have to be in Berlin to do it.

See http://berlinbuzzwords.de/wiki/linkstoslides to get slides from talks.