Hello and welcome to this art tutorial.
So in the previous section we introduced a multi-armed bandit problem for this
ad click through rate optimization problem
and we already tried two algorithms.
The first algorithm was the simple random selection algorithm
that consists of selecting a pure random, an ad at each round.
And this algorithm gave us a total reward of 1002 hundred on average.
Because, you know, there is this random factor.
But on average we got 1002 hundred total reward.
And of course, when we plotted the histogram,
every ad was selected more or less the same number of times.
And then we tried another algorithm which was the upper confidence
bound algorithm.
And there we got much better results because not only we managed to
almost double the total reward because we got a total reward of 2178.
So almost a double of what we obtained with the random selection.
And the even better thing is that we managed
to figure out which ad version was the best to show
to the user, that is, which ad version had the highest conversion
rate, the highest CTR, that is the highest click through rate.
And now in this section
we are going to try a new algorithm which is called Thompson Sampling.
And so in this section we are going to look at two things.
First thing is Ken Thompson sampling beat the upper confidence bound.
That is Ken Thompson sampling.
Give us a total reward that is even higher than 2178.
You know, we almost doubled the total reward of random selection.
Let's see if we can beat that again.
Like more than double it or even triple it I don't know.
Let's see.
And the second thing that we're going to look at is
if we get the same ad version that has the highest conversion rate.
Let's see if we get ad version number five,
which was the ad found by the upper confidence bound algorithm.
It found ad version number five.
So let's hope that we also get the ad version number five.
This should logically be the case
if we managed to be the upper confidence bound in terms of total reward.
So let's do this.
Let's implement Thompson sampling in this section.
We're actually going to do that in one step.
Because when you think about it
we will only need to change the strategy here in this for n loop.
And then keep the same to implement Thompson sampling.
Because you know we'll give these parameters here.
That is this number of rounds, this number of ads, this ad selected
vector that contains all the different ads selected at each round.
And this we will need to change because these are the parameters
of the upper confidence bound algorithm.
So we will need to change it.
And of course we will give this total reward
because we want to get the total reward accumulated
through the execution of this Thompson sampling algorithm.
So what we're going to do now is simply take everything from here
to here, copy, and then paste it here.
And we will only change what we need to change.
That is the right parameters for the Thompson sampling algorithm.
All right. So let's do it.
We can already replace UCB here by Thompson sampling.
And now let's change the strategy.
But before let's start with the basics.
Let's set the right folder as working directory.
So let's go to our Machine learning
A-Z folder then part six Reinforcement learning Thompson Sampling.
And then make sure that you have this as CTR optimization CSV file that is
of course the same CSV file as the one we had in upper confidence bound.
So if you have this data set, you're now ready
to click on this more button here and then set as working directory.
All right.
So now let's implement our Thompson sampling algorithm.
So let's directly jump to the slide of the Thompson sampling algorithm.
All right.
So what do we see here.
This Thompson sampling algorithm takes three steps.
First step is at each round we need to consider two numbers for each eye.
The first number is the number of times the ad I got reward one up to round
n, and the second number is the number of times the ad I got.
We weren't zero up to round N, so that's the first thing we'll do here.
We will consider these parameters
and declare the variables corresponding to these parameters.
And we can notice that if we compare this Thompson sampling algorithm to the UCB
algorithm, well it's the same step one with different parameters.
Because as you can notice here in the step one of the upper
confidence bound algorithm, we also consider two numbers.
And these two numbers are the number of times the ad I was selected up to round
n, and the sum of rewards of the ad I up to round n.
So if we have a look at this code section here, which is the code section
for the upper confidence bound algorithm,
well, we can see that these two parameters are here
and that these parameters are no longer the parameters for Thompson sampling.
And these two parameters
that we considered in step one in the UCB algorithm are actually replaced
by two new parameters in the Thompson sampling algorithm.
So what we'll do right now is simply to remove these two parameters
that are the parameters considered in the step one of the UCB algorithm,
and replace them by these two new parameters
that we need to consider for Thompson sampling algorithm.
So let's replace them right away.
And therefore let's declare two new variables.
So first number the number of times the ad I got we want one up to round n.
So let's call this number numbers of rewards and then underscore.
And one to specify that it's the number of times the ad got reward one.
And then the second number
is the number of times the ad I got reward zero up to run.
And so same we're going to create this variable numbers of rewards zero.
Now what are going to be these two variables.
So these are the parameters of Thompson sampling
at the essence of the future strategy that we're going to have here.
So these two variables here are going to be some vectors
of the elements that has ten elements.
And as you might have guessed they will contain for each ad
the number of times they got rewards, one up to round N and zero up to one.
And so we're going to initialize
these vectors the same way as we did for upper confidence bound.
That is we're going to take this integer d
that creates a vector of the elements.
And those d elements are zeros.
So that's exactly how we are going to initialize these two variables here
by a vector of ten zeros.
Because of course at the beginning the number of rewards of each ad is
of course zero because simply each ad wasn't selected yet.
All right. So we have our two arguments.
That means that step one is done and we can move on to step two.
So step two is for each ad I we take a random draw
from this distribution below which is the beta distribution.
And why is that?
It's because we have
two important assumptions here which are related to Bayesian inference.
So the first assumption is this first line.
Here we suppose that each ad I gets rewards from a Bernoulli
distribution of parameter theta I, which is the probability of success.
And you can picture this probability of success by showing the ad
to a huge amount of users, like 1 million users and theta.
I could be interpreted as the number of times the ad because we were one.
That is, the number of successes divided by the total number of times we selected
the ad. That is 1 million.
So basically theta I is the probability of success.
That is the probability of getting reward one when we select the ad.
And so the assumption is that each ad I get rewards zero and one from this
Bernoulli distribution of parameter theta I, which is the probability of success.
And then the second assumption, a less strong assumption than the first one,
which is the strongest assumption that we have.
The second assumption, which is this second line here,
and that is that we assume that theta I has a uniform distribution
which has the prior distribution.
And then we use the Bayes rule to get the posterior distribution,
which is p c to I.
Given the rewards that we got up to the round n.
And so by using Bayes rule,
that's how we get this beta distribution in this step two here.
And so by taking at each round these random draws of these
beta distribution, well, since these random draws represent
nothing else, then this probability of success,
we get the strategy here, which is to take the maximum of these random draws.
Because the maximum of these random draws
is approximating the highest probability of success.
And that's the whole idea behind Thompson sampling.
It's that we are trying to estimate these parameter theta
that are the probability of success of each of these ten ads.
Then by taking these random draws and taking the highest of them,
we are estimating the highest probability of success.
And this highest probability of success corresponds to one specific
ad at each round.
So when we take these random draws at a specific round, we might be wrong.
But when we take these random draws over thousands of rounds, well,
just based on the essence of probability, we obtain over all the theta
that corresponds to the ad that has the highest probability
of success, that is, the highest probability of getting reward equals one.
And that's the idea behind Thompson sampling.
And by the way taking these maximum of these random draws that is this maximum
of these estimations of the probability of getting reward equals one.
Well that's nothing else but step three.
And so right now what we'll do is to implement
the strategy composed of step two and step three in this code section here
replacing the old strategy of getting the upper confidence bound okay.
So let's do it efficiently.
Let's keep the logic behind this code section.
Let's not delete everything too quickly.
You know, since we'll get the different random draws of each add at each round.
And since we need to take this highest random draw, well,
we should keep this coding strategy here that gets the maximum value of something.
So we'll replace this max upper bound here
by a max random.
Because you know, in the UCB algorithm we needed to take the maximum upper
confidence bound.
And here for Thompson sampling we need to take the maximum random draw.
So we call this maximum random draw max random.
All right.
And then of course we keep this at zero because you know that's just to initialize
the add that we'll select at a specific round.
Because of course with Thompson sampling we will need to pick a not to show
to the user.
So we will keep this at zero in this at equals I here.
But then once we absolutely need to change here is this if else because this
if else is directly specific to the upper confidence bound strategy.
So we will remove this.
And now we will implement the Thompson sampling strategy.
So first thing we need to do is to generate
the random draws of each of the ten ads.
So we keep this for I in 1D, because we will need this loop
to go through the ten ads.
And so now we need to take the random draws.
So we are going to declare here a new variable that we'll call random
underscore data.
And that of course will correspond to the different random draws.
Because these are random draws taken from the data distribution.
So then equals.
And now we're going to use a function of R
which is the or beta function, which will give us exactly what we want.
That is it will give us some random draws of the beta distribution of parameters
that we choose.
And as we can see on this slide here, the first parameter is
the number of times the aversion I got reward one plus one.
And the second parameter is the number of times the ad I got reward zero plus one.
So let's do it.
Let's press F1 here to get some info about this our beta function.
So we will need only three of these arguments here.
The first argument we need is m the number of observations.
So here n equals one because we only want to take one random draw and then shape
one and shape two of the two parameters of our beta distribution.
That is, shape one is the number of times the aggregate reward one plus one,
and shape two is the number of times the ad that we want zero plus one.
So here for shape one we input shape one equals
numbers of rewards one.
And of course, since this corresponds to a specific ad,
I will add some brackets here and take the ad version I.
This we're dealing with at the specific time in this for I loop
here, that is, this corresponds to a specific ad.
And let's not forget the plus one here.
And then comma to input the second parameter.
And of course the second parameter is going to be
the i'th index of this numbers of rewards zero vector.
And then let's not forget the plus one here.
And that's our two parameters of this beta distribution
from which we are getting the random draws okay.
So we have everything we need.
And now of course we will need to play with this
if condition here to get the maximum of these random draws.
So a good exercise for you would be to pause on this video
and try to finish this code section here to guess the last elements
of this code here.
So I'm going to tell you right now, well right now we need to take
the maximum of these random draws.
We already declared this max random variable here.
That will be this maximum of these random draws.
And so well you guessed it.
Now we need to replace this max upper bound here by max random.
And here of course we need to replace this upper bound here
by random data okay.
And then same here.
We replace max upper bound here by max
random and upper bound here by random data.
And eventually of course we keep this as equals I here okay.
So let's re
explain quickly what's happening here for each at I in this for I loop here.
Well we're taking a random draw from this data distribution of parameters.
Number of times the adequate reward one plus one and number of times the add.
Good. We were zero plus one.
And then each time we take a random draw from this distribution,
well we check to see if this random draw is higher than this max random here.
So of course for the first add this will be the case because max random
was initialized to zero.
So this condition will be true for the first add and therefore max
random will be equal to this first random draw here.
And so we keep this first add here.
And then when we move on to the next add, what happens
is that we take another random draw from this data, distribute
one of these parameters here that corresponds to this new at I.
And then if this new random draw is higher than this max random here
that was equal to the previous random draw.
Well, that means that this condition is true
and therefore max random takes the value of this new random draw.
And therefore
we select this new add version I here that has the highest random draw,
and we forget about the previous add that we selected
because simply it has a lower random draw. All right.
So that's the idea.
And that's the strategy of Thompson
sampling that we are implementing at each round.
Great.
So now we almost have everything we need.
The thing that we need to update now is what's happening here.
Because this comes from the upper confidence bound algorithm.
So this is you know, the parameter of step one in the UCB algorithm.
So we will need to remove this line.
We don't need this.
And we have to keep this because this is to get the real reward.
As we explained in the YouTube algorithm.
You know, this is actually how we proceed to get the reward in this simulation
data set.
And then what do we have?
We have this line containing the sums of rewards.
And of course the sums of rewards is a parameter of the UCB algorithm.
So we need to remove that as well.
And now we are ready to update
what we need to update for the Thompson sampling algorithm.
All right.
And then we have the total reward that
of course we must keep because this is the exciting result.
And this is kind of a performance evaluator.
So now according to you what do we need to update.
Well of course what we need to update are these two vectors here
numbers of rewards one and numbers of rewards zero.
Because you know in this strategy here we are in putting the ith
index of these two vectors.
But you know we need to update them in each round because otherwise
they will always be equal to zero because they were initialized as zero.
So now what do we need to do.
We need to increment their values when we get the reward.
So let's see what we need to increment for this variable here
the numbers of rewards one.
Well these corresponds
to the different numbers of times each add gets reward one at round n.
So we need to increment it only when the ads go to reward one.
And what about this vector.
Well that's the same.
That's the vector
containing the different numbers of times each add got reward zero up to round n.
And so we need to increment this vector
only when the add that we selected got reward zero.
So since this depends on the reward we get
when we select the add, we will need an if condition.
And so we're going to write this if condition here if
and so the condition is simply if reward equals equals one.
So if this reward we get at this specific round
when we select this specific ad here, if this reward is one
then what do we need to do.
We need to increment this numbers of rewards one but only for the index ad.
Because this index ad here corresponds to the index of the ad that was selected.
So let's do it.
Let's increment this numbers of rewards one.
Let's copy that. And let's face it here.
And now let's take the ad index
corresponding to the index of the ad that was selected.
And then that's where we need to increment it.
So I'm going to copy this and paste
it here and add a plus one.
All right.
So when reward is one well of course what we need to do is to add a plus
one to the number of times this ad here gets reward one.
All right.
And then we have this else.
And this else corresponds to the situation where reward here is equal to zero.
That is when the ad that we selected got a zero reward at the specific amount end.
And therefore when that happens
we need to increment the numbers of rewards zero this time.
So I'm copying this line and
basing it right here.
And then replace the index I by ad because we need to increment the numbers
of rewards zero, but only for the value corresponding to this ad index here.
All right.
And now we're done.
Thompson sampling is actually fully implemented.
So now time for the exciting step visualizing the results.
So we'll do that in the next tutorial.
And until then enjoy machine learning.