Welcome back to Mining
of Massive Datasets.
We continue our discussion
of online algorithms.
Now, we just warmed up by looking
at an online algorithm called
a greedy algorithm for
the bipartite graph matching problem.
We're going to look now at
an application of online algorithms,
which is performance based advertising and
in particular,
we're going to look at a problem
called the AdWords problem.
Let's a start with a short history
of advertising on the web.
Now, from you know, web advertising
started almost simultaneously with
the World Wide Web itself.
In the early days of the web,
the only kind of ads that you
see online were banner ads.
And these reigned supreme
from til about 2001.
And banner ads were very, very simple.
They were graphical units that,
that you saw on webpages.
And popular websites charged
certain number of dollars for
every 1,000 impressions of the ad.
This is called the, the CPM rate, or the
cost per thousand impressions, where M is
the Roman numeral for, for a thousand,
and that's why it's called a CPM rate.
And this, this model comes to
us from TV or magazine ads,
which are priced similarly based on
the circulation of the magazine or the, or
the number of viewers of the,
of the TV show.
And this was a good initial model to,
to start off with but
it doesn't really you know, exploit a lot
of information that we have available
on the web that we don't have available,
you know, on TV or in a magazine ad.
In particular, these ads are very,
very untargeted so the same ad is shown to
everyone who comes to a website or, or
sees a particular page on a website.
And so these ads, not surprisingly,
performed really, really poorly.
Now, how do you measure performance?
Typically, advertisers measure
performance of ads by looking at
how many people click on, on the ad.
What they look at is what's called the
click through rate which is the ratio of
the number of clicks the ad
receives divided by the number of
impressions of that ad.
Remember, impressions are what
the advertiser is paying for
in the CPM rate,and the clicks
are what they want uh,and so
they measure the return on advertise,
the return on investment.
RO or ROI by looking at the ratio
of clicks to impressions.
Not surprisingly, the early banner ads,
which are completely untargeted,
have very low click-through rates and
very low ROI for advertisers.
And this sort of prompted a move
of banner advertising that went
from untargeted and then it's going to
move to demographically targeted.
You can sort of give
demographic information,
broad demographic information about
the kinds of people who are likely to
see a given webpage, and
target, ads to those people.
For example, you can place,
automobile ads, on, on a site about
car repair for instance, right?
So, you can sort of broadly,
demographically target ads to specific,
to specific websites,
but in general these ads
still don't perform really well because
they are very broadly targeted.
Now all this changed
with with the advent of
next new form of advertising called
performance based advertising.
And, performance based advertising
was first introduced by
a company called Robiture.
Around the year, 2000.
Now, a lot of you may not
remember Overture, but,
it was another search engine, you know,
that, existed, around the year 2000.
and, their innovation, i, it at Overture,
was that they, allowed advertisers
to bid on search keywords.
So people searched on Overture, much as
they search on search engines like Google
and Bing today and
advertisers bid to appear you know,
on those search results by bidding
on specific search keywords.
And when somebody searches for
that keyword, then Overture used to
show the ad of the highest bidder.
Followed by the actual search results.
But the key innovation
that Overture made was
that the advertisers was charged only
if the ad was actually clicked on.
Right?
The advertiser did not charge you know,
did not pay for the impression.
But they pay only for the click.
And so
this is called performance-based ad,
advertising, or cost per click advertising
to distinguish it from the, the,
the, the impression based or
CTM advertising that preceded it.
Now it turns out that advertisers really
like performance-based advertising, or
CPC advertising.
And and Overture did really well and
ended up being acquired by, by Yahoo.
Um,much later on, however Google,
which was another site and
it was just getting started at
roughly the same time you know,
adopted a very similar model to
around 2002 and they call it AdWords.
Now we're all familiar with AdWords
when we search on Google today,
when we see these, see these ads.
On Google, which are ads that are targeted
to the searches that we do and
the, the idea originally came from, from
Overture and then was adopted by Google.
And as we will see, Google made some
important changes to the Overture
model in terms of how advertisers bid.
And what ads gets shown.
Now it turns out that performance-based
advertising actually works.
Advertisers they like to pay on pay
per click as opposed to impressions.
And so, it is a multi-billion
dollar industry primarily
around search marketing.
And there are a number of
algorithmic challenges around
performance-based advertising.
There are, you know, they,
they roughly fall in to two buckets.
The first bucket is,
from the point of view of a search engine,
which is what ads do I show for
a given query?
And that's the topic of today's lecture.
And the second set of challenges come
from an advertiser point of view.
And the problem here is,
if I'm an advertiser,
which search term should I bid on, and
how much should I bid for the search term?
Now this is not the focus
of today's lecture, but
it's in fact a very important problem.
And there's an entire industry segment
that focuses around this problem as well.
So we formalize, the, the problem, of,
from the search engine's point of view.
We call it the AdWords problem,
because formulated in the context
of Google's, AdWords.
And in the AdWords problem, a stream of
queries arrives at the search engine and
let's, let's say it's q1,
q2, q3, and so on.
And, in general, a search engine
knows the query that it has seen so
far, but it cannot predict
the queries it's going to see next.
Now, several advertisers have
bid on each search query.
When a query qi arrives the search
engine must pick a subset of
advertisers whose ads are shown.
Right?
When you search, there's a number of,
advertisers who bid for that, keyword.
Now there's usually a larger set of
advertisers that have bid for a keyword.
Than the search engine can show.
Most search engines have a policy that,
that said they will show, at most, one ad.
Or two ads, or three ads for
each search query.
Then there may be tens of hundreds
of bidders for each search query.
So the search engine must decide which
subset of advertisers it'll pick and
show their ads for that search query.
And remember, this looks very
very similar to the model for
bipartite graph matching,
and it's no coincidence.
The goal is to maximize a search engine's,
revenues by showing the,
the appropriate set of ads.
And, clearly we need an online
algorithm in this case because the,
the search engine can only
see one query at a time.
And it must make an irrevocable decision
of, of deciding which ads to show, but
it cannot go back and change,
the ad that showed in the past, nor
does it know what queries
are going to come in the future.
So, we need, an online algorithm,
for this problem,
very similar to the algorithm that we had
for the bipartite graph matching problem.
Now, it turns out that there is a very
simple heuristic that you can use to
create an online algorithm for
the AdWords problem.
And that heuristic is
called expected revenue.
Let's first look at a very simple example.
Let's say we have a particular query, Q,
and we have three advertisers, A, B, and
C, who have each bid on query Q.
And their bids are shown
in this table here.
Advertiser A has bid $1 for each click.
Advertiser B has bid $0.75 for each click.
And Advertiser C has bid $0.50 per click.
Remember now, these are bids per click.
So, if the search engines decides
to show Advertiser As ad,
then Advertiser A pays if'
there is a click at that time.
The advertiser A doesn't pay anything
if the user doesn't click on the ad but
the ad just gets shown, right?
Now, the search engine doesn't know
apriori whether the ad is going to get
clicked or not.
so.
The simple, heuristic that
Overture used when they first,
introduced, you know, performance based
advertising was to just show the,
the ad from the highest paying advertiser.
They used to,
sort advertisers by bid as shown here.
and, you know, from top to bottom.
So, Advertiser A, A has the highest bid.
Advertiser B has the second highest bid,
and
Advertiser C has the third highest bid.
So, if I'm going to show only one ad,
I might as well show Advertisers A's ad,
because adver, Advertiser A is willing
to pay the most for a, per click.
You know, if I'm going to show two ads
I should just show advertiser A's and
B's ads but not C's.
Because A and B are both willing
to pay more than C for each click.
So this is a simple heuristic that,
which are used.ah, for
a you know, for, for, for
deciding which ads to show.
Now, it turns out that this is not
the optimal, algorithm for this, for
this scenario.
and, the, the, the important
reason is that ads behave very
differently in terms of
how they get clicked.
So.
What we should instead measure is
something called the click through rate of
each ad.
Now suppose advertisers A's ads
on average let's say we show,
show all these ads many, many times and
measure how often they are clicked.
Let's say advertiser A's ads
are clicked 1% of the time,
B's ads are clicked 2% of the time and
C's ads are clicked 2.5% of the time.
All right.
Now, if I show advertiser A's ad and
it's just clicked 1% of the time.
Then each time I show advertiser A's
ad there's a 1% chance that's it's
going to be clicked.
And if it does get clicked I get paid $1
and so my expected revenue from showing
advertiser's A's ad is $1 times 1%,
which is a penny, right?
And similarly, my expected revenue
from showing advertiser's B's
ad once is $0.75 times 2%.
And, and similarly for C,
my expected revenue is $0.50 times 2.5%.
And so we can go ahead and
compute the expected revenue for
each advertiser by multiplying their
bid and the CTR and in this case,
we find out that expected revenue for
Advertiser A is $0.01.
The expected for Advertiser B is $0.015,
and the expected revenue for
Advertiser C is $0.01125.
Right?
Now, the important innovation that Google
did, that over, you know, beyond the model
that Overture had introduced, was to
observe this, and notice that it's much
better to sort advertisers by expected
revenue than it is to sort them by bid.
Right?
So, when you sort by bid,
you place advertiser A first,.
Whereas when you saw by expected revenue,
you observe that advertiser B
is actually a much better advertiser,
advertiser's ad to show.
So we just had to show one ad.
You'd much rather show advertisers B's
ad because expected revenue is $0.015.
As opposed to showing advertiser A's ad,
where the expected revenue is just $0.01.
So, so in fact if you sort by by expected
revenue rather than actual bid amount
you get a different sort order with B,
C, A instead of A, B, C.
And this is in fact the AdWords
innovation that Google introduced.
It turns out that sorting by expected
revenue is a very, very good heuristic.
And it it works well for
the AdWords problem.
Now it turns out though that there
are a few more constraints in
the AdWords problem that the, just the
sorting by expected revenue doesn't solve.
Let's look at some of those,
those constraints.
So let's, formally state,
the AdWords problem.
We are given a set of bids by
advertisers for search queries.
Now, we just looked at one search query
but in general remember there are many,
many search queries.
and, there are many, many advertisers and
each advertiser bids for
some set of search queries.
So, so there's a set of bids.
By advertiser for surf,
advertisers for search queries.
You can think of this as a bipartite
graph with advertisers on one side and
search queries on the other.
And the ranges between advertisers and
search queries.
We are also given a click-through rate for
each advertiser-query pair that,
that has been estimated.
Now, the new thing that we haven't seen so
far is that each advertiser has a budget.
Right?
Now, advertisers don't have
infinite advertising budget.
An advertiser might say, look, I'm
willing to spend at most $1,000 a day, or
at most maybe spend $100,000 a month.
Or a million dollars a month.
But there's always a limit to how
much an advertiser can spend.
Which is defined by their
advertising budget.
So each advertiser has a budget which
they which they tell the search engine.
Now the search engine also has a limit
on the number of ads we display with
each such query.
Right?
For example a search engine may say look,
I'm going to show,
at most, one ad for
each search query, or two or three.
Now in, some modern search
engines the number ads actually,
depends on the kind of query as well.
But in a simple scenario,
let's imagine that, there is a fixed limit
on the number of ads to be
displayed with each search query.
Now the AdWords problem is,
then given all these, to respond to
each search query with a set of ads.
And we have defined the set of ads so
that the size of the set is no,
no larger than the limit of
the number of ads per query.
Right?
And we also have to make sure that we only
show advertisers who actually bid for
the search query.
Otherwise we aren't going to get paid.
And finally, and most critically,
we have to make sure that not only has,
have the advertiser bid on the query.
But the advertiser has
budget left over to pay for
the ad if it is actually clicked upon.
All right, if you show an ad from
an advertiser whose budget has been
exhausted because lots of ads have been
clicked on from that advertiser then if
somebody clicks on the ad, then
the advertiser doesn't have enough budget
left over to pay for the AdWord's click
and the search engine doesn't get paid.
So there's no point showing
that advertiser's ad.
So once a, the budget of an advertiser
has been exhausted, we can,
effectively assume that
the advertiser's out of the game,
and it's no longer bidding on,
on any, any search queries.
So the AdWords problem is,
therefore, to find a set of ads for
each search query that
satisfy this this criteria.
So here's a simple algorithm that you've
seen, which is sort by expected revenue.
Which is bid times CTR.
And it turns out that if the CTR
of each ad is known, and
if advertisers have unlimited
budgets then the simple algorithm.
Which is to sort by expected
revenue is actually optimal.
However, advertisers don't have
unlimited budgets in practice.
And the CTR of an ad is unknown.
And so we have to do something different.
Let's start with problem one, which is to
estimate the click through rate of an ad.
And in the next lecture we'll look at an
algorithm called balance which deals with
the fact that advertisers
have limited budgets.
To look at the problem of estimating
the click through rate of an ad.
Now this looks like a very simple problem.
All we have to do is to measure
the clickthrough rate of
a query-ad pair historically.
Which has, we just have to show
an ad a large number of times right?
Let's say a thousand or 10,000 and
you're to measure the number of clicks for
that ad, query-ad pair and then we have
the CTR for that query-ad query-ad pair.
And so far so good.
This is, in fact, the right way to do it.
But there are a couple of challenges.
Which we actually won't have
time to cover in this lecture.
The first is that the click through
rate is actually position dependent.
So remember a search engine may show
more than one ad for a given query.
So an ad that's shown in
position one generally gets
more clicks than an ad that's
shown in position number two.
Right?
So, so
therefore we actually have to
measure the click-through rate for
a query-ad pair for each position,
not just for a query-ad pair.
Because the click query-ad
is position dependent.
And the second problem that we
have is something called ex,
explore v exploit trade-off.
Now, imagine that we have a lot of ads for
a given query.
And we, we show, we've shown them a lot,
and we know their CTR.
And now a new advertiser comes in,
and also bids on the query.
Now, we don't know the CTR of the new ad.
However, ne, be,
we know the CTR of the old ads.
Now should we show the new ad at all?
And take the risk that it doesn't get
clicked on much and we lose some revenue.
Or should we just ignore the new ad,
just go with the ads that we
already know their CTR and
keep showing them to optimize revenue.
All right, so we just exploit
the known information, the known CTRs,
the known ads or
should we explore one of the new ad does,
perhaps the new ad is really good and
has a high CTR but we don't know.
Perhaps it's actually bad and
has a low CTR.
So this problem is called explore
the exploit trade-off and there's, it's,
it's a very richly studied
branch of you know, research.
Which again we won't have time
to cover in this lecture.
We'll just assume that we know
the click-through rate for
each query-ad pair because
it's been giving to us.