Back in the days of print & TV advertising, it was practically impossible to accurately measure the effectiveness of an advertising campaign. Today with digital ads we can accurately track how many people saw an ad, for how long, whether they clicked on it and if they ended up purchasing the advertised product. Given that advertisers can close the loop, it makes sense for advertising technology to try and systematically make better choices about what ads it displays to whom in as real-time as possible.
When we first launched Imprint, even before it was called Imprint, we were faced with a problem: each campaign we ran had hundreds of creatives. It’s easy to see how that can happen, the number of combinations between images, calls to action, creative types and devices can become unwieldy really quick.
Creatives * Calls To Action * Devices = way too many combinations
The way we handled it was by importing everything in a spreadsheet and once a week, after a lot of sorting and table pivoting, we would simply disable all creatives that were performing badly. This approach of course has a number of very obvious problems:
- It required a significant chunk of time and manual labor
- Between each cycle of manual optimization, we were potentially losing out by running badly performing creatives
- It is very hard for humans to reason about correlations when there are multiple variables at play
The approach we took to solve the problem is commonly referred as multiple bandits and the web is full of information about the technique. Most articles about multiple bandits focus a lot on the math behind the algorithms or go on long rants about the benefits of bayesian methods vs frequentist statistics. Today, I want to share the solution we used for Imprint using some simple Python and Redis and as little math as possible. We employ this technique to help us optimize a wide variety of variables such as picking out the most engaging content, biasing distribution towards publishers that perform better and improve clickthrough rates for display creatives that are embedded in the content.
We will first start with a very naive version of our optimizer and refine it as we go. We will need two methods:
def update_creative(creative_id, is_success, **kwargs):
"""
Updates what we know for a given creative.
:param is_success set to True if the user has clicked the creative, False if it is just an impression
"""
def sort_creatives(*args, **kwargs):
"""
:return a list of display creatives in descending order such that index 0 is the best known creative
"""
We also need somewhere to store our results. We want to be as real-time as possible (aside: you can choose to use a batch process to update the results but note that different bandit algorithms make different assumptions about the amount of delay they can tolerate) which gives us a convenient excuse to use Redis. We will use a single Redis hashtable where each individual creative will have two entries, one to count impressions and the other to count clicks. Given that data structure, what do our two methods look like?
HASH_KEY = 'CREATIVES_DATA'
def update_creative(creative_id, is_success, **kwargs):
clicks_key = 'clicks:%d' % creative_id
impressions_key = 'impressions:%d' % creative_id
if is_success:
redis_server.hincrby(HASH_KEY, clicks_key, 1)
else:
redis_server.hincrby(HASH_KEY, impressions_key, 1)
def sort_creatives(*args, **kwargs):
"""
Sort by CTR and return in descending order where the creative with the highest CTR is first
:return list of tuples (creative_id, ctr), sorted in descending CTR
"""
# data is a python dict that looks like {'impressions:<id1>': 10000, 'clicks:<id1>': 10,
# 'impressions:<id2>': 15000, 'clicks:<id2>': 5}
data = redis_server.hgetall(HASH_KEY)
ids = set(x.split(':')[1] for x in data.iteritems())
scores = [(id, data['clicks:%d' % id] / data['impressions:%d' % id]) for id in ids]
return sorted(scores, key=lambda x: x[1], reverse=True)
Ok, not bad for a first effort. We have a way to update our state every time we see an impressions and or a click and an easy way to retrieve the creatives with the best CTRs. This approach however is horribly ineffective — it will always be biased towards creatives that perhaps “got lucky” early on in the process and will ignore all others. What we want is a systematic way of being biased towards the best performing creatives but occasionally give the opportunity to other creatives. For this, we will use a process called Thompson Sampling. In this process, instead of sorting by CTR, we sort by a number drawn from a Beta distribution. If you are not familiar with Beta distribution, think of it like a black box where we plug in the number of trials (=impressions) and the number of successes (=clicks) and it gives us a random number. The more clicks, the higher that number is likely to be. However, given the probabilistic nature of the process, it is entirely possible for a worse performing creative to generate a random number larger than another, better performing one. Let’s look at some code
def sort_creatives(*args, **kwargs):
"""
Sort by CTR and return in descending order where the creative with the highest thompson sampling score is first
:return list of tuples (creative_id, random_number), where random_number is drawn from a beta distribution
"""
# data is a python dict that looks like {'impressions:': 10000, 'clicks:': 10,
# 'impressions:': 15000, 'clicks:': 5}
data = redis_server.hgetall(HASH_KEY)
ids = list(set(x.split(':')[1] for x in data.iteritems()))
scores = itertools.imap(lambda id, clicks, imp: (id, random.betavariate(clicks, imp-clicks)),
ids,
[int(data['clicks:%d' % id]) for id in ids],
[int(data['impressions:%d' % id]) for id in ids])
return sorted(scores, key=lambda x: x[1], reverse=True)
Great! We now have a way to give all creatives a chance to shine but at the same time, be more likely to choose the ones that are performing better. Still, there are still a few problems we want to address.
- What if some creatives perform better under certain circumstances, for example mobile vs desktop users. Is it fair to lump everything together?
- In some cases, we want to keep track of make decisions based on different objectives. In the real-world case of Imprint, some of our customers are more interested in optimizing for time spent, others for clickthrough rates and others for conversions at the destination.
- Our function above always considers all creatives. What if some creatives need to be excluded occasionally due to external factors, e.g. geotargeting?
- There is a numerical stability issue above. For things like click-through where the number of impressions is much larger than the number of clicks, the beta distribution always returns very small numbers, making it hard to distinguish between a creative with a 0.5% CTR and one with 0.8% CTR, a difference that can cost tens of thousands of dollars.
To address the above issues, we modify our update_creative function signature to take some additional parameters.
def update_creative(context, kpi, creative_id, is_success):
"""
Generic function that updates a creative under a given context. The context can be any string.
:param context: Create using `create_context_key`
:param kpi: a string if we want to track different KPIs for the same objects under the same context (e.g. CTRs + Time Spent)
:param creative_id: a unique id for the object to be tracked, typical to use the PK of the object in a DB
:param is_success: true if there was a reward (i.e a click), false if a trial (i.e. an impression)
:return: nothing
"""
The above signature takes care of problems 1 & 2. Here, the context can be anything and depends on your use case. For example, after a few models, we’ve found that device and screen size separate planes very cleanly so our context is a string ‘context:device:%(device)s:breakpoint:%(breakpoint)s’ where device can be iOS, Android, Windows Mobile, Windows Desktop, OSX, etc and breakpoint is xs, sm, md, lg. Now let’s look at how the signature for sort_creatives changes.
def sort_creatives(context, kpi, creatives):
"""
Use Thompson Sampling to sort creatives, with the creatives we should use being first
"""
As you may have guessed, we now need to pass in the context and KPI we are interested in. In addition to those though, we pass in the list of creatives and ask the function to sort them for us using Thompson Sampling. That way, instead of considering all creatives in the system, a top-level filtering function (e.g. geofiltering) can only ask for the ones it is interested in and under what context.
The above changes necessitate some redis-fu. In particular, we reorganize a little bit how we store the data and use Redis atomic transaction feature. The way Redis achieves atomic transactions is not through some intricate locking mechanism that you may be used to in mature relational databases but instead by using the MONITOR() command. Before we start our update sequence, we monitor a particular key and let Redis know to only go ahead with the update if that key hasn’t been altered. If it has, the update fails and we have to retry. Redis’ python library has a convenient function to handle all this logic for us. Take a look:
def update_creative(context, kpi, creative_id, is_success):
hash_key = 'context:%s:kpi:%s' % (context, kpi)
trials_key = 'trials:%s' % (creative_id,)
success_key = 'successes:%s' % (creative_id,)
smoothing_threshold = 1000
smoothing_factor = smoothing_threshold/(smoothing_threshold+1.0)
def _atomic_redis_update(pipeline):
trials_value = pipeline.hget(hash_key, trials_key)
success_value = pipeline.hget(hash_key, success_key)
if trials_value is None:
trials_value = 0
else:
trials_value = float(trials_value)
if success_value is None:
success_value = 0
else:
success_value = float(success_value)
pipeline.multi()
if is_success:
if (trials_value + success_value) > smoothing_threshold:
pipeline.hset(hash_key, success_key, (success_value + 1) * smoothing_factor)
pipeline.hset(hash_key, trials_key, trials_value * smoothing_factor)
elif success_value == 0:
# set initial prior to 2 to ensure unimodal distribution if you don't have a better prior
pipeline.hset(hash_key, success_key, 2.0)
else:
pipeline.hincrbyfloat(hash_key, success_key, 1.0)
else:
if (trials_value + success_value) > smoothing_threshold:
pipeline.hset(hash_key, trials_key, (trials_value + 1) * smoothing_factor)
pipeline.hset(hash_key, success_key, success_value * smoothing_factor)
elif trials_value == 0:
# set initial prior to 2 to ensure unimodal distribution if you don't have a better prior
pipeline.hset(hash_key, trials_key, 2.0)
else:
pipeline.hincrbyfloat(hash_key, trials_key, 1.0)
# don't forget that this is an I/O call that could throw
redis_server.transaction(_atomic_redis_update, hash_key)
You are probably wondering what this arbitrary 1000 limit is in the code above and what’s the point of all that logic? Well, remember the numerical stability problem we mentioned above? That method solves it by virtue of starting to forget older results once we get to a higher number of updates. Note also how everything happens in one transaction; this is critical because we fetch and check existing values and perform our update based on those. Had we not gone through the extra trouble of doing so, our ability to guarantee correctness would have been severely diminished. Given all the above, we modify the sort code slightly as well:
def sort_creatives(context, kpi, creatives):
trials_key = 'trials:%s'
success_key = 'successes:%s'
if len(creatives) == 0:
return []
hash_key = 'context:%s:kpi:%s' % (context, kpi)
pipeline = redis_server.pipeline()
pipeline.hmget(hash_key, [success_key % (x.pk,) for x in creatives])
pipeline.hmget(hash_key, [trials_key % (x.pk,) for x in creatives])
successes, trials = pipeline.execute()
res = itertools.imap(lambda obj, a, b: (obj, random.betavariate(max(1 + float(a), 2.0), max(1 + float(b) - float(a), 2.0))),
creatives,
[x if x is not None else 2 for x in successes],
[x if x is not None else 2 for x in trials])
sorted_res = sorted(res, key=lambda x: x[1], reverse=True)
return [x[0] for x in sorted_res]
So there you have it, a generic way to automatically optimize anything, under different contexts and for different objective goals. By using Redis we have efficient lookups that can be done in real-time and we can even ensure that our updates are done atomically. The algorithm we use in Imprint has evolved significantly since the above was implemented, taking into account things like changing conversion rates, negative rewards and even support modeling rewards as a distribution. Nevertheless, the approach discussed above though should suffice for most implementations.