Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

20 lines of code that beat A/B testing every time

stevehanov.ca

Post reply on HN
Print view View original

61–70 of 152 posts

Re: 20 lines of code that beat A/B testing every time

#61

Post by steve8918 »

I actually noticed that Google was doing this with my Adwords account a couple of weeks ago.

I have 2 ads in an Ad Group, and the wording between the two is different by a single word. One ad had over double the clickthru rate than the other one, just because of that single word difference.

I noticed that Google was serving the two ads about 50% of the time, and was going to shut off the one ad that had the lower CTR, but then I let it go, and the next day, I saw that the more successful ad had almost all the views, and the less successful one was barely being served.

Re: 20 lines of code that beat A/B testing every time

#62

Post by IgorPartola »

treeface wrote: post #38
IgorPartola wrote: post #18

Earlier quoted context omitted.

Better than a forgetting factor, add a Kalman filter ( http://en.wikipedia.org/wiki/Kalman_filter ). This way you can trust your "new" data more than really "old" data, etc. The beauty of it is that it only adds three attributes to each data sample.

Could you expound on this a bit? What attributes would you have to add? How would you calculate scores?

You would add a variance (P), estimate of the value and the timestamp of the last measurement. Using the last timestamp you can calculate Q. Generally, the older the last measurement, the higher Q.

The calculation is straightforward once you let some things be the value of identity:

  P1 = P0 + Q
  K = P0 / (P0 + R)
  x1 = x0 + K * (z - x0)
  P1 = (1 - K) * P0
Now you have the new score for your data (x1) and a new variance to store (P1). Other values are:

x0, P0 - previous score, previous covariance Q - Roughly related to the age of the last measurement. Goes up with age. R - Measurement error. Set it close to 0 if you are sure your measurements are always error-free. z - the most recent measured value.

Let's say you measure number of clicks per 1000 impressions. Now you can estimate the expectation value (x1) for the next 1000. After the second 1000 re-estimate again.

Re: 20 lines of code that beat A/B testing every time

#63

Post by jasonwatkinspdx »

daeken wrote: post #39
heyitsnick wrote: post #34

Maybe i'm missing it (it's late), but nowhere in the article does it explain why 10% of the time it picks a choice at random ("explores"). In fact, the article basically argues why it's not needed (it self-rights if the wrong choice becomes temporarily dominant). It also doesn't explain why specifically it should be a 10% randomization.

A random choice is needed to allow people to give rewards to options other than the dominant. I'm sure this doesn't have to be random -- and I'd be curious to see the logic behind the 10% choice -- but you have to have something that gives the other options a chance. Makes me wonder if the 10% number couldn't be changed to something that's a function of the number of rewards total; the longer it runs, the less variat…

Like many things in machine learning, this is a simplified version of Metropolis-Hastings.

Re: 20 lines of code that beat A/B testing every time

#64

Post by Jare »

chc wrote: post #21
phildeschaine wrote: post #10

Earlier quoted context omitted.

OK, in AB testing that same 0% design, you're showing it 50% of the time. You seem to be saying "I'll AB test it just for a little, then weed out the 0% one. but in the case of this new algorithm, I'll let it run for a long time." That's not exactly fair. Not to mention, both algorithms would allow you to clearly see the 0% option sucks.

But the only way this testing method is superior (at least as explained in the article) is that it automatically adjusts itself. If you're going in and adjusting manually, it sounds like this is — at best — precisely as reliable as A/B testing and subject to the same critique the OP levels at A/B testing.

It will adjust itself in the sense that while it is still enabled and testing (a suboptimal state for your product), it will let your product perform better than plain old A/B.

At some point you still step in and decide based on the data, especially if you detect degenerate cases, and move on to the next experiment.

Re: 20 lines of code that beat A/B testing every time

#65

Post by IgorPartola »

JeanPierre wrote: post #47
IgorPartola wrote: post #18

Earlier quoted context omitted.

Better than a forgetting factor, add a Kalman filter ( http://en.wikipedia.org/wiki/Kalman_filter ). This way you can trust your "new" data more than really "old" data, etc. The beauty of it is that it only adds three attributes to each data sample.

How does a decay factor not "trust your 'new' data more than really 'old' data"?

The Kalman filter is much more sophisticated. Typical re-estimation will be:

  x1 = x0 + alpha * (z - x0)
where alpha is static. The Kalman filter will make it dynamic, taking into account how you obtained the measurements, how old the last re-estimation was, how noisy the process is, etc. Want to do multi-variate analysis? Make alpha a matrix transform.

Re: 20 lines of code that beat A/B testing every time

#67

Post by robomartin »

A lot of the reasons for which this algo can optimize in the wrong direction have been covered here. In general terms, I agree with all of it.

I am a big fan of two techniques that I feel would enhance an approach like the one suggested: FIR filters and Decay.

Simply put: I believe it is important to have a mechanism through which decisions are not made too quickly. A finite impulse response filter would take care of this very well.

In addition to that, older measurements should not carry the same importance as nice-fresh data. Who cares what people thought about the buttons (or whatever) a month or two ago? The crowd visiting the site this week could have been affected by solar flares. Maybe they prefer something else.

Obviously you need enough traffic to be able to use such techniques.

Not sure it's worth the complexity in all cases.

Re: 20 lines of code that beat A/B testing every time

#68

Post by treeface »

IgorPartola wrote: post #62
treeface wrote: post #38

Earlier quoted context omitted.

Could you expound on this a bit? What attributes would you have to add? How would you calculate scores?

You would add a variance (P), estimate of the value and the timestamp of the last measurement. Using the last timestamp you can calculate Q. Generally, the older the last measurement, the higher Q. The calculation is straightforward once you let some things be the value of identity: P1 = P0 + Q K = P0 / (P0 + R) x1 = x0 + K * (z - x0) P1 = (1 - K) * P0 Now you have the new score for your data (x1) and a new variance…

Thanks for explaining that!

Re: 20 lines of code that beat A/B testing every time

#69

Post by shadowmint »

I like this.

See, we've spent the last year doing an Omniture implementation, using T&T, and frankly, its been a waste of money and time.

This isn't a criticism of the T&T tools; its a criticism of our own internal analytics handling and analysis team, and possibly the implementation guidance we received from a few places.

You can guess at generalizations from the A/B/N changes you've made and try them again, but practically speaking? Meh. It seems like the learnings from one page are very hard to transfer to another page.

That's why you don't see posts like "Top ten generalizations about how to make your website better!" instead you pay "SEO Expects" and "Analytics Ninjas" as consultants and they tell you things like "pages with images convert more, generally, but that may not be the case for your specific website because of blah". Handy. Do you have any more generic and obvious advice that doesn't tangibly translate into practical changes to my website?

Here's the thing: Running an A/B is easy, but analyzing the results is really hard. Generating some kind of general analytics rules is very hard.

The reason I like this approach is simple: it's easy. It's easy to implement. It's easy to explain. It's easy to convey to the designers that you're doing a 'throw at the wall and see what sticks' approach to pages. It's easy to explain to managers how why the best page has been picked. You don't need a self important analytics ninja who will go on endlessly about user segments and how if you segment the data differently you can see kittens in the page view statistics.

Just make lots of pages, and see what happens.

It's not perfect, but it's enough to get started~ (...and honestly, that's the most important thing when you're working with analytics; it beats the hell out of a 3 month implementation cycle that ends up with... page views <-- to be fair, personal opinion about uselessness of implementation not presently shared by marketing department, who likes the pretty graphs. Whatever they mean.)

Re: 20 lines of code that beat A/B testing every time

#70

Post by vibrunazo »

wpietri wrote: post #50
timr wrote: post #45

Earlier quoted context omitted.

Bandit optimization has been discussed previously on HN: http://news.ycombinator.com/item?id=2831455 The problem with this article is that it's a) not very detailed, and b) the conclusion is linkbait. Bandit optimization is a useful tool, but it has drawbacks, and it's not always better than A/B testing. In particular, bandit approaches take longer to converge (on average), and don't give you reliable ways to know wh…

Agreed. And I'd add that for me, the point of A/B testing is to learn something. We're not just interested in whether A or B is better; we're interesting in getting better at doing what we do. Studying the A/B results is half the fun.

Why can't you do the same study from the bandit results? From what I understand, this the same as A/B testing, except it will only show a suboptimal result to 10% of the users instead of 50% (or more). After a few days of testing, can't you take a look at the statistics and analyze them the same way that you would for an A/B test? Then just stop testing?

The A/B test just gives you the conversion rate of each option. And so does the bandit. As I understand, the only difference is that the bandit will be bugging your users with bad results less often.

Post reply on HN