All right, now it's finally time to do the hard part. 1
We're going to write our own algorithm that will find the lowest cost. 2
And this is the famous gradient descent algorithm, and gradient is well you guessed it just another word 3
for slope. 4
So I'm going to give you a very, very Austrian perspective to think about the gradient descent algorithm. 5
You know, we've got a lot of mountains back in Austria and they're very, very beautiful and you can go 6
ski down them, but a mountain is a force of nature. 7
You have to respect the mountains. You see, the weather can change very, very quickly and this is especially 8
unpredictable in winter 9
and at high altitude. 10
So you know imagine yourself that you've wandered off the beaten track and the fog comes rolling in 11
and at this point you find yourself in a survival situation. 12
This is when you can't see very far and you can only feel the ground beneath your feet. 13
The cold is going to be creeping in through your jacket and you find yourself thinking: How do I get 14
down? 15
How do I get back down? Well, to figure out which way is down and towards that hot cup of tea waiting 16
for you at the end of your journey, 17
you got a feel like, 18
which way is down, 19
what is the slope, right? 20
You're going to look at your feet and you're going to figure out that the fastest way down is in the 21
direction where the slope is steepest. 22
Right? Where the descent is the most steep. 23
And if you take a step downwards in that direction and then kind of get a feel for it again, like which 24
way, which way is the slope and then take another step where the slope is steepest, you'll be down in 25
that valley in no time. 26
And you can sit on that hot cup of tea, right? 27
And this is how you can think about gradient descent, except, instead of a mountain, yeah, gradient descent 28
is going to take place on a cost function and the cost function actually doesn't tend to look like this - 29
it doesn't kind of have a peak, if you will. 30
Right? 31
Because if a function had a peak then it would be called concave, 32
it has a maximum. 33
But with our cost functions, we're going to be looking for minimums. 34
Right? 35
So if you imagine that mountain flipped upside down and all you've got is a valley, 36
right, 37
that you have to kind of find then your cost function is going to look more like this. 38
This is a kind of function that's called convex. 39
It will have a minimum and a hard job is to get to the bottom of it because that's where the cost is 40
lowest. 41
Now, gradient descent isn't always called gradient descent, 42
there's another word for it that you might see as well in the literature. 43
Sometimes it's referred to as Steepest Descent and yes it's an optimization algorithm for finding the 44
minimum of a function. 45
So, you know, think about our mountain example - to find the minimum the function takes these little steps, 46
right? 47
It takes a step in that direction where the slope is steepest, in the direction of the negative of the 48
gradient and bit by bit ends up in the bottom of the valley. 49
All right. 50
So let's implement this in Jupyter notebook. 51
Let's add another markdown cell here. 52
And I'm going to go to "Cell" > "Cell Type" > "Markdown" and put two hash tags there for a section heading and that section 53
heading is gonna be "Python Loops and Gradient Descent". 54
Now, if you're a seasoned programmer you're gonna be familiar with writing loops but if you're new to 55
Python or you're new to programming, then the next couple of minutes are going to be the introduction to this 56
topic of loops. Loops are little bits of code that are executed over and over again. 57
We're going to walk down that mountain. 58
We're going to walk down into the valley with our gradient descent algorithm. 59
So this is going to be a very, very useful tool for accomplishing that because our algorithm has to complete 60
that famous three step process. 61
Right? 62
Predict, calculate error and learn, and repeat. 63
So instead of writing the same Python instructions over and over again we're going to be using loops 64
to simplify that for us. 65
Speaking of "for", this is the first loop I'm going to introduce to you, guys. 66
So this is gonna be the for loop in Python. So I'll just write a little comment here "Python for loop" and 67
this is what the syntax looks like. We're going to have the keyword "for". 68
And then there's gonna be a variable, in this case I'm gonna call it "n", and then then other keyword 69
"in" and then I'm going to say "range(5):", new line and now we're inside the loop here 70
we're gonna print famous first words "Hello World". 71
OK, let's hit Shift + Enter. 72
See what happens. 73
All right. 74
So we've printed "Hello World" five times. 75
Right? 76
One, two, three, four, five. 77
If I change this range to 3, l print it three times. If I change it to a thousand, it'll print it a thousand 78
times, but let's stick to the stick to five for the time being, and let's take a closer look at this value 79
n here. 80
Right. 81
n is just a variable and it's going to keep track of how often our for loop has run. 82
So if I say "'Hello World', n", then I can see what the value is of the variable n each time the 83
loop is run. 84
So it starts at zero. 85
Programmers like to start counting from zero. 86
And that's the very first time the loop runs. 87
Then this print statement is executed another time. 88
So second time, third time, fourth time, fifth time. 89
And at this point the loop stops. 90
Right. 91
Show you that - "print( 92
'End of Loop')". 93
So the Python program will come in here 94
and execute whatever's inside the loop, and you can tell what's inside 95
by the spacing, a predefined number of times, in this case five times. 96
Right. 97
0, 1, 2, 3 ,4 . 98
Now we can call a little counter variable here and we can call it "i", 99
this is another one that is often used. 100
So if I call it "i", I get exactly the same result. 101
It really doesn't matter what you call it. 102
You can call it counter. As long as you're consistent, 103
you can access the variable, the looping counter, inside of the loop by its name. All right, 104
so that's the that's the for loop. 105
It executes a predefined number of times and it's got this very, very simple syntax "for n in range", 106
And then some number here. 107
So this is how often times you want to execute the loop. With that out of the way, 108
let me show you another type of loop. This type of loop is also very, very common. 109
And this is the so-called "while" loop. 110
A while loop works a little differently. 111
Right. 112
It has a condition that it checks every time it runs, right. 113
So it will check the condition and then if that condition holds, it's going to run the code inside the 114
loop and it's going to continue doing that until the condition fails. 115
So if I have a counter and I say it's equal to zero and then I can write my while loop like this I can 116
say "while", which is a key word and say, counter is smaller than, I don't know what, 7, colon print 117
Counting 118
counter. 119
So print the value of my counter inside my loop and then I'll say "counter = counter + 1". 120
So I'm going to increment my counter variable by 1 every time the loop runs. 121
And then when I finish with the loop I'll print something else. 122
Yeah. 123
"Ready or not, here I come"!. 124
Yeah let's make that loop a little bit more menacing than the last one. 125
So if I hit Shift+Enter now, I can see my print statement inside my loop executed seven times, 126
right? Starts at zero and executes it until our condition fails. 127
This is the condition, so whatever follows the while keyword is the condition that's checked. 128
And this fails when counter is equal to seven. 129
Seven is equal to seven, it's not smaller than seven. 130
So this will be false at this point. 131
The loop terminates and the code inside is not executed anymore. 132
And we jump to our print statement below. 133
Right, this one "Ready or not, here I come!". 134
And this is what we're seeing here. 135
Again, I can accomplish the very, very same thing as with the for loop so I can execute it five times. 136
So if you want you can also execute a while loop a predefined number of times. 137
Yeah there's a small catch, there's a small gotcha 138
that can happen with while loops that you won't get with for loops. 139
Any guess what this gotcha is? Any guess what it is that can trip you up and where you can shoot yourself 140
in the foot? 141
So with while loops you can get into a situation where they don't stop, where they don't terminate. 142
So, for example, if I had made a typo here and instead of that plus I had hit minus, then my loop would 143
actually run forever, right, because it would start at a zero, 144
then when it reaches this line my counter would go to negative 1, then would come here and go to negative 145
2 and then here negative 3. 146
And this thing would just continue going, right? 147
Which is clearly not my intention, right? It would continue going and cause a lot of problems. 148
So with while loops you have to be careful that you don't accidentally write an infinite loop. 149
So, for loops by their very nature run a predefined number of times, while loops run while a certain condition 150
holds true. 151
And this is where you gotta be, gotta be careful. So with your while loops, you've got to make sure they terminate 152
and the easiest way to remember this is with an old programming joke. 153
Yeah, that goes something like this. 154
A programmer once said to his wife "Honey I'm heading to the supermarket to buy some groceries", to which 155
his wife responded "While you're there, buy some milk". 156
And alas he never returned home again. 157
Oh. 158
Crickets. 159
Back to gradient descent. 160
Let's tackle that in the new cell here at the bottom. 161
The thing with gradient descent is that we need a couple of ingredients right. 162
We need a starting point. 163
Then we need a learning rate, and we're gonna need some maybe temporary value to hold onto something 164
while our program is executing. 165
So I'm gonna create these three things here. 166
I'm going to say "new_x" which is gonna be our starting point, I'm going to set it equal to 3, I'm going to start with 167
3 as the starting point. 168
I'm going to say "previous_x" and this is gonna be my temp value if you will. 169
That only matters inside of the loop. 170
And then I'm going to also specify a learning rate. 171
Yeah. 172
Or gamma or whatever you call it. 173
So I'll call it a step multiplier 174
and I'll set it equal to 0.1. Now it's time to write that loop. 175
It's gonna be a for loop for us. So I'm going to say for and in range and maybe start at 30, 176
colon, 177
and now for the first step - 178
What's the first thing that we have to do? 179
Well, we have to make a guess, right? 180
We have to make some prediction. 181
This is step one of the machine learning process. 182
So I'm going to take our temp value, previous_x and I'm going to set it equal to our random guess. 183
Yeah. 184
new_x = 3 185
Three was a random guess, just our starting point for our gradient descent. 186
I'm going to set them equal to each other. 187
Now we get to step two. Step two is calculating the error because we need to know how far off we were. 188
From the previous lesson, 189
you will know that the steepness of the slope tells us how far off we are, right, from the minimum, because 190
at the minimum the slope is equal to zero. 191
And everywhere else it's equal to some number that isn't zero. 192
So our gradient is gonna be equal to df of the previous_x. 193
Yeah. 194
So we're gonna call our derivative function. I'm going to pass in the temp value. 195
So at the point where we are, in our function, I'm going to store the the slope, yeah, at this point in a variable 196
called gradient. So one thing you might ask at this point is - Why is calculating the gradient 197
step two or calculating the error? 198
What's the link between those two things? 199
And the way to think about it is that the further away we are from our minimum, the steeper our slope. 200
So if the slope is very, very steep then it's indicative of being very, very far away from where we want 201
to be. A steep slope means that we've got a high error. 202
And if the slope is zero or close to it then our error is small. 203
And now it's time for that adjustment step, for that learning step. 204
So the new value of x is gonna be equal to the previous value of x minus, because we get to go down the 205
hill, minus our step multiplier 206
times the slope, times the gradient and remember this is the value of the slope at the previous value 207
of x. 208
So what we're doing here is we're taking a step that's proportional to the negative of the gradient 209
of the function at the point that we're at. 210
And then we're subtracting from the previous x value because we want to move against the gradient towards 211
the minimum and this is where the learning in machine learning takes place. 212
So this loop is going to run 30 times and after it's finished let's print out our results. 213
So I'm going to say "Local minimum occurs at", 214
at what? Well the new value of x, right? 215
Because that's what we're updating in our for loop, and we're gonna print out the slope. 216
Yeah. 217
So we just have to make sure our slope is close to zero. 218
Right? 219
Or the value of df(x) 220
Yeah. 221
yeah, "at this point". 222
So this is gonna be our derivative function and as an input it's gonna get the latest value of x. Finally 223
we're going to print out what the what the cost is at this point. 224
So this is the f(x) value or cost at this point is, 225
and this is gonna be our cost function at the point where the cost is lowest. Now, before I run this, 226
make sure you've got a plus sign here because if you ever have to go to "Restart and Run All" or "Run All 227
Above", 228
yeah, 229
then you may want to make sure that this loop doesn't continue going. 230
I just caught myself out there. 231
So I'm going to hit Shift+Enter now here and I get my print statements shooting off the results of our gradient descent. 232
So, what can we learn from this? 233
What can we deduce from the values that we're seeing here? 234
Well, the first thing is that we can see that they're approximations, right? 235
This isn't an exact value. 236
We're not getting a very clean answer here. 237
But that might be the case because maybe we haven't run our loop often enough. 238
So if I increase the value here from say 30 to 50 let's see what happens with our values that we get 239
printed out. So one thing that we're seeing is that our slope is getting a lot closer to zero here than 240
before. 241
The second thing is is that this value here on f(x) is also getting a lot more precise and so is our 242
new value of x. 243
So it's getting much, much closer to a -0.5. 244
Yeah if I run this 500 times, let's see what happens. 245
So, as you can see, we're converging on this local minimum by brute force, right? 246
We didn't solve our cost function here analytically. 247
What we're doing is we're iterating and going down that valley, that cost function 248
until we reach the minimum point and at the minimum our slope is equal to zero, 249
our cost is equal to 0.75. 250
And this is when the x is equal to -0.5. 251
So obviously you can run this thing a thousand times or what have you. 252
Right? 253
But often times you actually know ahead of time how precise a calculation you need, right. from the resource 254
management point of view. 255
What you can actually do is you can tell the loop to stop running once a certain level of precision 256
is met. 257
And I'm sure you're looking up. 258
Yeah. 259
You scrolling up and you looking at this while loop here and you're thinking ah yeah the while loop seems 260
ideal for this, right. 261
We can run the while loop as long as our calculation is within a certain level of precision - and you'd 262
be right. 263
That's exactly something you could implement if you wanted to, with the structure of the while loop. 264
Let me show you how to do this with the for loop as well. 265
We're going to modify our code here a little bit to include a cutoff point for a certain level of precision 266
and the way I'm going to do this is by adding another variable up top and say "precision" 267
is gonna be equal to 0.0001. 268
Yeah. 269
So this is how precise I want my answer to be. 270
Now, where does this come into play? 271
Well, what we're interested in, in with our precision estimate is what's the difference between the new 272
and the old x, right.x 273
So if those two are getting closer and closer and closer together then our calculation is getting much 274
more precise. 275
So what we can do is we can say well the step size is gonna be the difference between our new x minus 276
our previous x. 277
Yeah that's gonna be the step size. 278
And just to make sure that step size is always a positive number, we're going to say well what we care 279
about is actually the absolute value of our step size and, uh, now, change the number of times this loop 280
runs to maybe 10. 281
Yeah. 282
And I'm going to print out the step size, just we can see how it it evolves over time as the as the loop 283
runs. 284
So let me run this. 285
Let me press Shift+Enter here. 286
And we can see here our step size initially starts out with 0.7. 287
And then it decreases. 288
Right? 289
The new x and the old x are getting closer and closer together. 290
So we can see here our step size is decreasing. 291
Commenting out this print statement so it doesn't execute anymore. 292
And I'm going to add the condition for terminating this for loop. 293
Yeah I'm going to say well if the step size is smaller than the precision, 294
so in other words - if the difference between the new x and the previous x is smaller than 295
0.0001, then we can terminate our loop, then we can stop with our calculations. 296
So, I'm going to put a colon there and then the Python keyword for stopping this loop 297
it's called break. 298
We'll leave it at that. 299
And uh I'm going to say, well, run 500 times. 300
Yeah, for loop run from 0 to 500, but if the step size is smaller than our predetermined precision, 301
then stop running. Let's see how often our loop runs according to this logic. 302
Well, we don't know, right? 303
Could have run any number of times. We probably have to print the value of n - so, print("Loop ran this 304
many times:", n) 305
Forgot the s. 306
So, given these constraints, our loop ran 40 times. 307
It's actually not that much. 308
Not that many times. 309
If we add an extra zero here on the precision that we're looking for and press Shift+Enter again, we 310
can see that it ran 50 times, so it actually never gets up to 500. 311
Yeah. 312
Doesn't, doesn't go up all that way and that's because it reaches that terminating condition, 313
this break statement, a lot sooner, but still the way we wrote this code we have two conditions where 314
it can stop. 315
It can either reach 500 and it will stop there or when it reaches the minimum and that step size becomes 316
very, very, very small 317
then it can also terminate. Now running the Python loop and calculating the minimum is very well and 318
good, but I'm a very, very visual person and I'm sure you might be too. 319
So I find graphing things very, very helpful. The way we're gonna go about graphing it is 320
first off we have to kind of keep track of all the values that we've calculated inside of our loop. 321
So we're going to create two lists. 322
Yeah. 323
Two Python lists - one of them is going to hold onto our x values, 324
so it's gonna be a list and it's going to contain the new x values. And the other thing is I'm going 325
to also create a list for all the slopes. 326
So I'm going to call this "slope_list" and it's going to contain whatever value our derivative has at 327
this x position. 328
Yeah. 329
Now, within our loop we're actually doing these calculations anyhow. 330
So all we need to do is we need to append the x values and the slope values to our list. 331
So I'm going to say "x_list.append()" to add a new value to it of the new x value. 332
And this is the x value that we've updated after we've taken our step down the cost function. 333
So I'm going to append this value to our list and also for our slope list we're going to append 334
the output from our derivative function at the new x value. 335
Yeah. 336
And that's it. 337
That gives us the basis for plotting out charts. 338
So let's do that now. 339
I'm gonna go up here and I'm actually going to copy this cell here, I'm going to go "Edit" > "Copy Cell" and I'm going to reuse 340
it down here a lot of this code. 341
So I'm going to place the cell above. I'm going to edit my comment to, uh, say that we're gonna superimpose the 342
gradient descent calculations. 343
Yeah 344
So this is the goal. Now we've got two charts and what we're gonna do is we're gonna add a scatter plot on 345
top of these with the data that we've captured from our loop. 346
Here's how we're gonna do it. 347
For our first chart, 348
we're gonna say "plt.scatter()" and then we have to supply some arguments. 349
So on the x axis, it's gonna be our list of x values and for our y axis we want to feed our list of values 350
into our cost function. 351
Right? 352
So this is our f(x). 353
Now you might think I can actually just put the x_list in here and press Shift+Enter but this isn't 354
going to work. I'm going to get an error. 355
Yeah, and this is because our function, the way that we've written it cannot process a list. 356
It's unable to process this list as it is. 357
So I'm gonna have to do a little type conversion first. So I'm going to create a variable called values 358
and set it equal to a numpy array which is gonna take as an argument our list of x values. 359
So, our function can work with an array but it can't work with a list and when I press Shift+Enter we should 360
see that now we have a little scatter plot on top of our graph. 361
But in terms of data visualization that was very, very poor. 362
Right? 363
So I'm going to say the color of these dots should be red. 364
They should be a lot larger so that the size equal to maybe 100 and give them a little bit of transparency. 365
So I'm going to say the alpha should be equal to maybe 0.6. 366
See how that looks. 367
It's looking a lot better. 368
Yeah. 369
So we can see here - as our algorithm runs going closer and closer to this minimum. But we can also show 370
this on our second chart as well. 371
Right. 372
So we can see how we're inching closer to where the slope is zero on this right hand chart and we can 373
do that by making use of the other list that we've captured. 374
So, in this case it is a little bit simpler because we just have to write "plt.scatter( 375
x_list)", x values still the same, but for the y values we've done a bit of a calculation already, so 376
we can say "slope_list" 377
and let's also make it a red color, 378
make the dots big, size 100, and alpha 0.5 or something. 379
Let's see how it goes. 380
It's looking not bad, but I do wonder if there maybe should be some transparency on the line itself. 381
So if this thing had an alpha of say 0.6, would it look a bit better? Yeah. 382
Yeah this looks this looks better. Let's do the same thing with our plot at the top as well. 383
Let's give this an alpha of maybe 0.6 as well. 384
See or 0.7 perhaps. 385
0.8 386
Let's try. 387
Yeah. 388
This is looking pretty good. 389
So you can see here that now we have our scatter plot superimposed on our derivative function and it 390
stops when the slope is equal to zero. 391
And on the regular cost function we're moving down and down and down and down into the minimum at the 392
bottom of this parabola. 393
You know the cool thing is that we can even zoom in a little bit and we can even do a little close up 394
of our slope. 395
Let me show you what I mean. 396
So if I take this bit of code here, copy it and paste it and say chart number three, and call this 397
"Derivative 398
(Close up)" and then I change the title and say "Gradient Descent (Close up)" might get rid of the y label. 399
don't need that, I'm going to keep the grid but I'm going to change what's on the axes and go from say 400
0.55 to -0.2. 401
So, zooming in here on the x axis and on the y axis I'm going to do the same, 402
I'm going to zoom in from 0.3 to 0.8. I'm still gonna leave it sky blue. 403
Change the linewidth to 6, alpha is 0.8. 404
Change these values around a little bit to make it a bit more distinct, make the dots a little bigger. 405
And if a press Shift+Enter now, then nothing will happen because I need to adjust my subplot. 406
Right. 407
I'm adding a third plot here. 408
So I have to make sure that I have in this case, what, three columns, right, I've got three charts. 409
This is chart number three of the lot. 410
And this is gonna be also edited to chart number two, right? 411
On the three column subplot, and same with this. This chart number one on the three column subplot. 412
And it's now that I can run this. 413
See what happens. 414
Huh. 415
So I'd say this is pretty good right. 416
We've got a close up here where we can actually watch the gradient descent converge upon that zero value. 417
And you can see those steps getting smaller and smaller and smaller and smaller as we're getting closer 418
to our goal. 419
I think this is incredibly cool. 420
The charts look a little bit squished. 421
Maybe what I'll do is I'll change this from 15 to I don't know 20 on the width. 422
See if that helps. Yeah that definitely looks a little better. 423
Okay brilliant. 424
We've done quite a lot of work in this lesson. 425
This has been a long and difficult lesson but writing the code definitely helps us play around with 426
the gradient descent. 427
Yeah, because what we can do now is we can change a couple of these values and see how it behaves differently. 428
So for example if instead of at 3, we start at -3 with our gradient descent. 429
Let's take a look here. 430
If I starting value is -3 and I rerun the loop and rerun all the calculations and rerun the 431
graphs then we can see how the gradient descent comes in from the other side. 432
So in this case it's from the bottom here instead of from the top. 433
This is really, really cool in being able to actually play with the algorithm. 434
And this is the advantage of writing all the code out and actually running it and rerunning it to see 435
how differently it behaves. Because not only can we change the starting point but we can also change 436
say how many steps we're taking, right? 437
So if we rerun our algorithm to only run about 10 times instead of the usual amount then we can see 438
how we're not getting that close to the minimum. 439
Right? 440
So we should be getting about here, but we're actually not reaching it. 441
So yeah, I think this is really really cool. 442
And in the next couple of lessons we're going to be exploring a couple more of the idiosyncrasies and 443
the strengths and weaknesses of this algorithm 444
now that we've written it and graphed it. I'll see you there.