Hello and welcome to this art tutorial.
So let's pick up where we left off.
That is, let's try to figure out why we're using this upper bound equal to this
very large number ten of the power of 400 given
to this upper bound variable here in this else condition.
Well let's see what happens.
You know, let's see what happens at first round.
Well, at first round we will go through the ten versions of the Add
thanks to this four eye loop here.
And since that the first round no add was selected.
Well this condition here, if numbers of selections
eye is higher than zero will never be true.
And therefore we will directly go to this else here.
And accordingly, the upper bound will be set
equal to ten to the power of 400.
Then we move on to this condition because this is the next step of this for
loop here.
And it says that if upper bound is larger than max upper bound,
which is true, of course,
because upper bound is ten of the power of 400 and max upper bound is zero.
So this condition is true.
So what happens next is that max upper bound is equal to upper bound.
So max upper bound will be equal to ten at the power of 400
and add equals I.
And so since we're at the beginning of the for loop here I equals one.
So add will be equal to one.
And then what happens.
Then we go to the next step of this for I loop here which is I equals
two and I equals two corresponds to the second add.
And the second add hasn't been selected yet.
So numbers of selections I here will not be larger than zero.
So this condition will not be true here.
So again we will get to this else here.
And therefore upper bound will be equal to ten to the power of 400.
And then we go to this if here.
So now let's see if this condition is true.
Upper bound is equal to ten to the power of 400.
And remember, from the previous round, max upper bound was set equal
to ten at the power of 400, because it was set equal to upper bound.
So this condition, translated in real terms, is
if ten of the power of 400 is larger than ten at the power of 400.
And that is not true,
then at the power of 400 is not larger than ten to the power 400.
So that condition is not true, and therefore add is not set equal to two,
because right now I equals two, but it remains equal to one.
And that's why at the first round the add
that will be selected is add equals one.
That is the first add.
You can try with the other values of I here.
Upper bound will always be equal to ten to the power 400.
And max upper bound will stay equal to ten of the power 400.
So therefore this condition will never be verified for the nine remaining at here.
And therefore we keep this at equals one.
And that's the same principle for the next round.
Up to ten at round n equals two.
This number of selections I here will be larger than zero only
for the first add, because the first add was selected at round one.
And therefore this condition will be true only for the first add.
So upper bound will be equal to this average reward plus delta I.
Here.
But then we'll move on to I plus one which will correspond to at version two.
And since add version two wasn't selected yet,
well this number of selections I here will be equal to zero.
And therefore this condition won't be verified.
And therefore we will go to this else here.
And upper bound will be equal to ten at the power of 400.
We will forget this upper bound value here computed at the previous I here.
And therefore what happens next
is the same upper bound will be larger than max upper bound,
because max upper bound was equal to the upper bound at the previous I,
and the upper bound of the previous I was average reward plus delta I,
which is of course lower than this ten at the power of 400.
And that's why, by the way, we set it to a very large value.
It's in order to have this
upper bound here lower than this ten at the power of 400.
And therefore max upper bound will be ten at the power of 400.
And we will select add equals I, that is add number two.
And then same principle as before when we'll move on to the next
i's upper bound will be equal to ten to the power of 400.
Max upper bound will also be equal to ten to the power of 400.
So this condition won't be verified and therefore we will keep add number two.
So that's why this nice little trick here works perfectly
well for us and gives us exactly what we want.
All right so the ten first round select the ten add.
And then after round ten we use this strategy to select the add.
All right.
So now the only thing that we need to do is to append
the selected add here in this add selected vector here.
And that's exactly what we'll do now.
So let's do it.
We just need to get out of the for I loop because we're done with this loop.
We did exactly what we had to do.
That is to select the right add.
And now we need to get out of this for eye loop.
But remain in this for loop because we are still at a specific round end.
And what we have to do now is to append
the add that was selected here to this huge vector.
Add selected that contains all the different add selected at each round.
Okay, so now things are easy.
We just need to use the append function on this
add selected huge vector and then append.
Here it is.
All right.
And now in this append function we enter as input.
First input add selected and second input add.
Because it corresponds
to the index of the add that was selected in this for I loop here.
All right.
So done. Add appended.
And now since we've just selected a new add here,
what we need to do is to update this vector number of selections here.
That is you know the vector telling for each add the number of times
it was selected.
So since here we know which index of the L was just selected,
what we need to do is to add a plus one in this particular
index of this numbers of selections vector to update this vector.
So let's do it right now.
We will stay of course in this for end loop because this vector
will contain the numbers of times each add was selected at the specific round.
And so we need to stay in the loop.
And we will simply take this vector here.
Copy and paste it here to update it.
And so what we need to update is the add
index of this numbers of selections vector.
Because this add index corresponds to the index of the add
that was just selected.
Here a selection that is based on all this strategy.
And so what we simply need to do is increment by one this vector here.
So we will copy that.
Again copy equals paste.
And then a little plus one here. All right.
So now these numbers of selections vector is well updated.
And that's all we need to do for this vector at this specific round.
Because of course only one add was selected okay.
And now we need to take care of the rewards
because indeed we have this sums of rewards vector here
that we need to update, because this vector contains
the different sums of rewards of each of the ten ads at each round.
So we need to update it.
And of course afterwards we would like to get the total reward
that you know will be a variable containing the unique
sum of rewards we accumulate it over the N rounds.
So let's first take care of this sums of rewards vector here.
And then we'll take care of a total reward.
So to update this sums of rewards vector here, what we need to get
now is the reward we get at this specific round n
because you know we just selected this ad here.
But we haven't got its reward yet.
We just selected the ad so far.
Now we need to get the reward.
So in real life what happens is that, you know, we show the ad to the user
and then the user clicks yes or no on the ad.
But here we're not in real life.
As much as I would have loved to show you a real experiment of this
right now in front of your eyes.
This would not be that simple, but we have this simulation data set.
You know, this data set here that, you know,
contains the real results only known by God.
You know, because we have no idea of which ad each user would click on.
So as a reminder,
the first user clicks on ad one at five and AD nine, not the rest of them.
So that's just a simulation data set.
And so what we have to do now is get the reward at each round.
And based on the ad there was selected thanks to this data set.
So let's do it.
What we'll simply do is get the reward that is either 1
or 0 at this specific round end where we are at.
And so to get this it's really simple.
What we need to do is, you know, take our data set and in the brackets
we'll need to specify the index of the line where we are at, which is
you know, the round n corresponding to the round where we are right now.
So since all the lines of this data set here are nothing else
but the rounds, well, the first index will be the round.
So for example, let's say we are at round nine.
Well we will need to take the line index nine of the data set.
And then for the columns.
Since the columns here correspond to the rewards of the ten different ads,
well we will need to take the index of the ad to a selected.
That is nothing else than this ad index.
Here.
So that's the idea.
That's what we have to do.
But of course, in real life you'll get what really happens with the users.
So I'm going to close this.
And right now I'm going to get the real reward at round N
that we get with the selection of this ad index here.
So let's do it.
We will call this real reward.
Simply reward. All right.
And now as I just explained we need to take the data set and then brackets.
Then we need to take the index of the line that corresponds to round n.
So n here and then we need to take the index of the column
that corresponds to the index of the ad that was just selected.
So it's ad here.
And that's all.
We simply get the real reward at round N for this specific selection of this
ad by using this.
Okay. So great.
We've just got the real reward.
And now we can update this sum of rewards vector here.
That as a reminder, gives
to sons of rewards of each of the ten ads at each one end.
So we will take this copy.
And then just below we will increment this vector.
And of course we need to take the ad index of this vector.
Because only the ad that was selected at this specific
round end will have its sum of rewards changed.
So that's the only sum of rewards we need to update.
And therefore what we need to do is to increment it by the reward,
not by one of course, only by the reward, because the reward is either 0 or 1.
So equals here.
And then we take that again.
And then plus reward.
So if we go to zero reward, the sum of rewards for this specific ad won't change.
And if the reward equals one,
this sum of rewards for this specific ad will be incremented by one.
Okay.
And now we just have to do one last thing.
It's of course to get the total reward accumulated over the N rounds.
Well, the total reward is not very interesting for us at any round
N, but at the last round end that is at the ten thousands round,
because we will compare it, of course, to the total reward
we got with this random selection algorithm,
which as a reminder, was 1002 hundred on average.
So that's why we're very excited to find out about this total reward.
But at the end of the 10,000 rounds.
So of course we need to initialize this total reward variable because,
you know, we are updating it at each round.
So we need to give it initial value like in physics.
And this initial value will give is of course zero because at around
zero at the beginning of this experiment, the total reward is of course zero.
We haven't accumulated any reward yet.
So let's declare this new variable a total reward
right here and then set it equal to zero.
And now very simply, what we need to do
is to compute the total reward that we accumulate at each round.
And very simply we need to do another increment
the same as the one we just did.
So I'm copying total reward here,
pasting it here and equal.
And then paste it again and adding a plus.
And then according to you what do we need to add.
Of course we need to add the reward that we get at each round n and that's done.
The UCB algorithm is implemented.
Congratulate us.
This is the first algorithm we implement from scratch in this course.
That's very exciting.
And as you notice we built and implemented this algorithm
as if we would do it in real life.
You know we didn't add the lines one by one.
We implemented it as a developer would do it step
by step, you know, with the same logical thinking process.
So congratulations.
And now I'm so excited to look at the results and find out by
how much the UCB algorithm will beat the random selection algorithm.
So as a reminder, the random selection algorithm gave us a reward of 1002
hundred.
Let's see how UCB beats that and let's hope we get a nice result.
So I'm going to select everything from here to here.
All right.
And there we go.
Here it is.
Let's immediately have a look at the total reward.
We can see that the total reward is 2178.
We almost doubled the total reward earned by the random selection algorithm.
So that's great.
You know, if you are the casino and if the ads are not ads, but,
you know, slot machines, that means that you would earn twice as much money.
And that's not all, because this is just the total reward of the experiment.
But what's very interesting to see now is the specific ad
that has the highest conversion rate.
You know, simply what is the best ad to show to the users.
And how can we find out about this?
Well, what we simply need to look at is this ad selected vector here.
So let's have a look first.
What we can see is that as expected, you know, as the expected result
of our implementation here.
Well, we can see that during the ten first rounds the ten ads are selected.
You know, round one we select at one, round two at two, round three at three.
Up to round ten at ten.
So that's exactly the result of what we did here with this huge
value trick to get these ten ads at the ten first rounds.
And then the strategy starts, you know, since we get some informations
based on the selections of these ten ads here during the ten first rounds,
then we get the sums of rewards info and the numbers of selections info.
And that's when the strategy can start.
And that's exactly what happens here.
From here the strategy is running and different selections appear.
And what's really interesting to see now
is to look at the last round that is, you know, the rounds close to 10,000.
Because if the strategy works well, logically,
this algorithm should select always the same ad during the last rounds
because, you know, there is one ad that is the best,
that has the highest conversion rate.
You know, maybe it's the ad where the car is on the beautiful bridge.
So there is this winner ad that we don't know, of course,
but that's what this ad selected vector will tell us if we look at the last round.
So let's do it.
We will go down and down and down.
Okay. Here we go.
So as you can see as I'm going down, it appears that there are more and more
fine with them at a different rounds.
As you can see, there are more and more five that we're selecting at each round.
And if I go down again and go down more and more, well, we get even more five.
And that the last rounds, that is during the last thousand
rounds, well, we select only five.
As you can see right now we are at around 9800 and we can only observe five.
So clearly the best ad that we should pick to show to the user.
And that has the highest conversion rate is ad number five.
So great.
Not only we almost doubled the total reward with this 2178 total reward.
But also we get to know what is the best ad to show to the users.
And of course we're interested in both.
We're interested in knowing what's the best
ad, but also to optimize this total we want here because, you know,
experimenting this placement of these ads on the social network costs money.
And, you know, I said at the beginning, we have a limited budget, and that's
generally the case for the departments of marketing or any business.
We have a limited budget.
So we need to optimize this total reward here to compensate the costs
and hopefully already earn some money.
So these two results are very important.
And so thank you very much through this UCB algorithm.
And now as usual as promised we will finish this UCB algorithm section
with the last step, the exciting step about visualizing the results.
And simply what we'll do is plot a histogram
showing for each ad the number of times it was selected.
So we'll do that in the next tutorial.
And until then, enjoy machine learning.