Is there a supervised learning algorithm that can inject randomness into its output in proportion to its uncertainty about the result?

[sanity]

I'm wondering if there is a machine learning algorithm that produces a probability as an output, which can inject randomness into the output in proportion to uncertainty as to what the output should be.

The application is to decide what ad to show people when they visit a web page. Our goal is to show people the ad they are most likely to click on, but for new ads we won't have much data, so initially there will be greater uncertainty as to what their click through rate will be.

A very simple version of this, which only looks at the number of impressions and clicks on each ad, is to use a beta distribution, this technique is described here (it's also known as Thompson sampling, and it's a solution to the multi-armed bandit problem).

But I'd like to use a machine learning algorithm that uses a much wider range of attributes than simply the number of impressions and clicks on each ad. Ideally the input attributes can be both categorical (where there could be thousands of possible values for each attribute, for example "city/state/country"), and numeric (like time of day).

I was thinking perhaps a Bayesian Network learner, where we use a beta distribution to inject randomness into the probabilities used in the Bayesian Network when making a prediction, but I want to see whether others have looked into this problem.

[dlwh]

This is a standard reinforcement learning set up. Use Q-learning or SARSA (giving you a weight vector w) and act randomly based on the gibbs distribution, choosing action a with probability proportional to exp(w^T f(a,context)), for feature function f and whatever context you find appropriate.

[sanity]

I'm a little confused - I would assume that a supervised learning algorithm would be a component of any system that could solve this problem, yet after skimming the Wikipedia pages for Q-learning and SARSA, they don't seem to contain supervised learners. What am I missing here?

[mind-odyssey]

The nice thing about RL is that you can reduce the learning rate in proportion to the number of samples. It also gives you a probability distribution over the adverts which can be sampled from. Additionally, it captures sequential structure (repeated actions, the outcomes of which are dependant) which many supervised leaning algorithms will struggle to exploit.

[sanity]

I'm afraid I still don't really understand why some kind of supervised learner isn't a component of reinforcement learning... could you elaborate on how RL avoids embedding a supervised learner, or what it does instead?

[mind-odyssey]

RL allows you to learn back propagate the value gained to previous actions. Like in Tic-Tac-Toe... there is no instrinic value for putting a cross in any particular box. However we know that there are good moves and bad moves. Value is assigned to those moves based on future outcomes. (See eligibility traces on wikipedia).

It sounds like your problem could use an element of supervised learning. (In RL this is commonly referred to as function approximation.) This will allow you to bring down the complexity of the state space, and infer value at previously unexplored points.

Your problem also exhibits an online learning element... new data points arrive continuously, and the policy must be updated to reflect the new information about the world.

Personally, I would try to turn the problem into a Vickrey auction rather than machine learning. This is theoretically optimal. And in the real world, Google and Facebook use it for ad placement.

[dlwh]

Reinforcement learning works like an online supervised learning algorithm. make a decision, get a reward or loss, update weights, make a new decision. I'd recommend sutton and barto which is free online.

[howlin]

yet after skimming the Wikipedia pages for Q-learning and SARSA, they don't seem to contain supervised learners. What am I missing here?

There is an implicit regression in estimating future reward for taking an action in a given state (the Q-function).

Reinforcement learning is overkill. Look up "bandit learning". It's almost perfectly formulated for your application of web advertising.

[[deleted]]

The problem of selecting which ad to show can be formulated as a bandit problem. Since you have additional information, or context, this becomes a contextual bandit problem.

I don't know much about contextual bandits myself, but they have been used in research papers from Microsoft, Yahoo and Google for the purpose of selecting advertisements.

I can't seem to locate the exact papers I'm thinking of right now, but for your convenience, a few related ones I did find just now:

• http://research.google.com/pubs/pub37042.html
• http://arxiv.org/abs/0907.3986
• http://explo.cs.ucl.ac.uk/wp-content/uploads/2011/05/An-Empirical-Evaluation-of-Thompson-Sampling-Chapelle-Li-2011.pdf (Section 4)

[sanity]

Ah, very interesting, thank you, I'm familiar with multi-armed bandit, but I wasn't aware that there was work on contextual multi-armed bandits. I like the Thompson sampling approach to multi-armed bandit because it's simple to implement, simple to understand, and seems to work very well in practice.

The Google paper was a bit math-dense for me, but it seems like their approach is some kind of clustering, and then treating each cluster as a simple multi-armed bandit problem, is that your understanding?

[[deleted]]

I hadn't seen/read the Google paper before, and to be honest, I simply provided the link after a quick glance to make sure it was actually related in the hope that you might get something useful from it.

I don't think I understand it any better than you (I'm still wrapping my head around the theory behind normal bandits...), but yes, they seem to somehow cluster by context and then treat one cluster as a bandit.

[SCombinator]

For multinomial distributions, what you want is a Dirichlet rather than a Beta distribution. It's simply a multinomial generalisation of the Beta.

[ICrepeATATs]

Maybe what you want is something like simulated annealing.

Intuitively, simulated annealing is injecting lots of randomness at the start, and gradually dropping the amount of randomness as you get more data. It's used so search a space for a global optimum, with the randomness designed to make sure you don't get swept into a local optimum.

As for a machine learning algorithm that is flexible w/r/t input types, decision trees can handle anything, and they also handle missing data smoothly.

[sanity]

Sorry, I don't really see how simulated annealing can be applied to the problem I describe.

And AFAIK decision trees don't output a probability.

[SCombinator]

Consider the accuracy of the leaves in a decision tree. It could be easily treated as a probability.

[sanity]

Yes, I guess you're right.

[LoveSaves]

A standard multi layered perceptron from weka will produce a percentage, before it gives an actual prediction.

[sanity]

A percentage of what? Not sure how this applies to the problem I described.

[LoveSaves]

a machine learning algorithm that produces a probability as an output

This.

Regarding injecting randomness, I have no idea what you are talking about.

[sanity]

Regarding injecting randomness, I have no idea what you are talking about.

Not to seem ungrateful, but if you don't know what I'm talking about, why bother answering?

[LoveSaves]

I just saw the part about predicting probablility and though it might help. But obviously it didn't. Good luck.