Comment by evolutioner | Hacker News Reader

Comment by evolutioner | Hacker News Reader

Parent Full thread

Sentient employee here. I'll give an example on a problem for which we use evolutionary algorithms: website optimization.

Say you want to try many various changes like the title of your page, the color of the background, the position of your buy button etc. We solve this problem by trying out random variations of these websites - like A/B testing with more candidates - and by crossing the best performing ones to create a new generation of websites. This helps us find good performing variations in a very big search space.

This would be hard to do with deep learning as we start with no data at all, measuring the performance is quite noisy and you can't compute a gradient to know how to evolve your website. There is no smoothness between a title and another.

Also you could try to make a linear model for to see what effect each change has, but that doesn't take into account all the dependencies that can be complex, for example what title goes well with what background color. Evolutionary computation helps implicitly optimize without having to formulate a model.

What is the advantage of using evolutionary algos in this case over using something like Thompson Sampling or Contextual Multi-Armed Bandit? (http://www.kdd.org/kdd2017/papers/view/an-efficient-bandit-a...)

They can actually work together.

Thompson Sampling / Multi-armed bandit algorithms are traffic allocation strategies to use the least amount of traffic to find the optimal variant.

So say you have version A/B/../N variants of a website, you can split the traffic equally or use a a bandit algorithm and find the best performing variant of it.

But that only helps you test N variants. If you want to test for 4 titles and 3 color buttons, 3 layouts and 5 images you already have 4x3x3x5=180 different variations and you can't test them all. Evolutionary algorithms can help you search through a much bigger search space:

First you try 10 variations, and allocate traffic equally or through a bandit algorithm. Then you combine the top performing candidates multiple times to create a new generation and start over again.

Evolution helps you find which candidates to try in a large search space and then a bandits algorithm can help you allocate traffic optimally.

You have to be careful with A/B testing with Bandit algorithms though. If the conversion rate changes over time or if you have visitors that don't always convert instantly you have to take that into account: https://www.chrisstucchio.com/blog/2015/dont_use_bandits.htm...

The paper linked above does directly address the case of multiple experiments occurring in the same context. They address this with hill-climbing over those 180 different variations. The use of a bayesian linear regression takes place of the exploration found with Thompson sampling.

You're right, the paper linked above is a different way of solving the same problem. In their case they use a model to decide which website variants to show. Their model accounts for independent effects and pairwise dependencies. Evolution allows you to optimize without needing an explicit model.

I don't think they account for potentially changing conversion rates over time or delayed conversions.

Aside from that, I'd be curious to see how these two approaches compare in a real-life situation.

They can work in conjunction - In the domain of website optimization, where visitor attributes are often greater predictors of value than website content, a system driven by search space optimization can more easily take into account changes in those variables - eg; time of day, traffic source, device type - and incorporate those inputs to climb multiple 'hills' simultaneously.

The allocation of traffic based on the evolving optimal search space (blue button for visitors from Facebook) can then be driven through an MAB or something similar.

I think, not much. This is an optimization problem to which you can apply any algorithm that "fits" --- no closed-form functional form, interactive feedback --- so bayesian optimization (with GPs), some form of RL, evolutionary algorithms et al.

Thanks everybody for your responses. Food for thought :-)

Ok... so... let's say your A/B only optimizes the colour and location of a single CTA button, and conversion rate is your fitness. 2 previous generations have top/blue and bottom/red. How does the next one look?

Each generation has like 10~20 candidate websites. The better the conversion rate, the more likely it is to get chosen as a parent.

With your example, let's say two parents with top/blue and bottom/red are chosen, then their offspring will either be top/red or bottom/blue because we make sure the same website isn't tested twice.

More generally each feature of the offspring will be randomly picked from the features of the two parents.

So two parents A/A/B and B/C/B can give the offspring A/C/B or B/A/B. There is also some random mutations that are possible with a low likelihood.

link to the product: https://www.ascend.ai/

Reply on news.ycombinator.com