27. Find Partial Derivatives
2.71M subscribers
SUBSCRIBED
MIT 18.065 Matrix Methods in Data Analysis, Signal Processing, and Machine Learning, Spring 2018 Instructor: Gilbert Strang View the complete course: https://ocw.mit.edu/18-065S18YouTube Playlist: https://www.youtube.com/playlist?list...In this lecture, Professor Strang presents Professor Sra's theorem which proves the convergence of stochastic gradient descent (SGD). He then reviews backpropagation, a method to compute derivatives quickly, using the chain rule. Note: Videos of Lectures 28 and 29 are not available because those were in-class lab sessions that were not recorded. License: Creative Commons BY-NC-SA More information at https://ocw.mit.edu/termsMore courses at https://ocw.mit.edu
00:00
00:01
The following content is provided under a Creative
00:03
Commons license.
00:05
Your support will help MIT OpenCourseWare
00:07
continue to offer high-quality educational resources for free.
00:11
To make a donation or to view additional materials
00:14
from hundreds of MIT courses, visit MIT OpenCourseWare
00:18
at ocw.mit.edu.
00:19
00:22
GILBERT STRANG: OK, here we go.
00:25
All set, and two topics for today--
00:29
one is to go back to Professor Sra's lecture.
00:34
That was last Friday.
00:37
And he promised a theorem and proof.
00:41
And this morning, he sent it to me.
00:45
So it's proving the convergence of stochastic gradient descent.
00:51
And really, what's important, maybe,
00:54
and useful is not so much the details of the proof,
00:58
which I'm just learning, but the assumptions--
01:03
what's the logic here, what do you
01:05
have to assume about the gradient and about
01:10
the algorithm to get the answer?
01:14
But now I actually look back at the video of his lecture.
01:22
And it was excellent.
01:25
And as I looked at it, there were a couple of things
01:29
later in the lecture that I thought
01:33
would make good projects.
01:35
So I don't know if anybody is still
01:37
open to what to do on a project.
01:40
But here are my two ideas.
01:44
And if you've already finished your project,
01:47
well, you get an A-plus by considering one of these.
01:53
So you remember-- and this will remind you
01:56
of the lecture, which is a good thing.
01:59
So do you remember that question 1 was whether,
02:03
in the stochastic part, after you've sampled one or some mini
02:10
batch-- but let's just say one of the lost functions,
02:16
coming from one sample--
02:17
you remember, the whole point is that if we do all zillion
02:22
samples at every iteration, we're really, really slow.
02:27
So the stochastic idea is to randomly pick
02:31
one or a mini batch of the samples
02:35
and just reduce their loss, just deal with the loss--
02:41
say, the square loss.
02:43
Or later we'll see cross-entropy loss.
02:46
But whatever the cost is, just do a few or one.
02:54
And then the question was, after you've done that one,
02:57
do you put it back in the pot every time
03:01
you sample over the whole collection?
03:04
But that's expensive.
03:06
Or do you just make a list of random order of all the samples
03:15
and go through them?
03:17
Which is then without replacement, which
03:20
is a sort of semi-illegal.
03:22
That is, the logic in the randomization
03:31
asks you to replace every time.
03:34
But nobody does it.
03:36
It costs a lot--
03:38
probably not worth it.
03:39
So the project would be, suppose you take 1,000--
03:43
or, say, just 100.
03:46
100 random numbers-- say you use MATLAB, just
03:54
the command "rand."
03:56
So you get numbers whose average is a half from rand.
04:00
They're between 0 and 1.
04:02
OK.
04:03
So we know what the average is.
04:06
So let's compute it two ways.
04:08
One is by not replacing.
04:13
And that's the interesting one.
04:16
So take 100 samples.
04:19
Well, I guess we know that, after we've
04:22
got through the full 100, we're going to get
04:25
exactly the right answer.
04:27
But anyway, my question would be, how much difference do you
04:34
see in the eventual approach-- so the law of large numbers,
04:40
I guess, would tell us we get a average
04:43
of a half for these numbers with uniform distribution
04:50
between 0 and 1.
04:51
Should I be writing anything here?
04:54
Maybe I should.
04:55
OK.
04:56
So this is project 1.
04:58
05:02
You pick numbers ak, which is from rand--
05:13
so uniformly on 0,1.
05:22
And then my question is, what about convergence
05:25
to the final--
05:29
the average is a half.
05:32
So this may be too simple an example.
05:35
But could we see what happens for the convergence
05:39
of the average as you either do replacements or don't
05:46
do replacements?
05:48
And in fact, I would like to see a figure that looks
05:53
like those in his lecture.
05:54
Do you remember?
05:55
He started it somewhere--
05:58
start-- and then here's the finish.
06:03
06:05
But you remember, the stochastic gradient descent
06:08
was kind of pretty effective at the beginning.
06:11
Well, the beginning, those might be 100
06:14
iterations each-- one epoch, one run through the full number.
06:20
But then when it got to here, got closer,
06:23
it started oscillating.
06:27
You remember, he identified the region of confusion
06:30
around the thing.
06:33
Well, my suggestion is just, I think
06:38
those videos should be accessible to you on--
06:40
are they on Stellar?
06:43
Yeah.
06:43
So I'd love to see that behavior and some good examples
06:54
of that behavior and some pictures to you.
06:56
So that would be one idea with and with--
06:59
oh, yeah, that's also idea 2.
07:03
Idea 2 is the good start and then
07:07
the bad finish for a stochastic gradient descent.
07:12
And of course, even without this,
07:17
the magic words in computations is "early stopping."
07:25
We don't over-fit.
07:29
07:35
So we wanted to stop early, anyway.
07:38
And early stopping just is a good idea
07:44
if that's what the approach to the x
07:51
star that you're looking for.
07:53
This would be the place where the--
07:57
that's x star where grad f at x star is 0.
08:05
That's the minimum point.
08:07
That's ARG MIN-- exactly what we're looking for.
08:14
And we don't find it very well.
08:17
But we get close to it fast.
08:20
OK.
08:21
Two ideas on projects--
08:25
so maybe I'll go to the main topic of today--
08:31
the topic I promised--
08:35
the idea of back propagation.
08:39
This is all to compute grad f--
08:48
the gradient.
08:50
All the derivatives-- this is the df dx1 to df dxm,
09:02
maybe, I'll say, where I have m features for the sample.
09:14
OK.
09:15
So that's back propagation.
09:17
And that's the thing whose discovery, or rediscovery,
09:25
put neural nets on the map.
09:29
That's the key calculation, of course, to find the gradient.
09:32
In the steepest descent algorithm,
09:34
every step needs a gradient.
09:38
And if you can't compute it quickly, you're in bad shape.
09:45
But you can compute it quickly by
09:48
this automatic differentiation in reverse mode, which
09:54
is otherwise known--
09:56
I don't think the people-- maybe Hinton was the leader
10:09
in developing deep neural net--
10:12
deep learning.
10:13
10:16
So I give him big credit for that--
10:18
that back propagation would work and would give him
10:22
fast gradients.
10:23
But it actually had been studied before under the name AD--
10:30
Automatic Differentiation.
10:32
So may I just tell you that idea?
10:35
Some of you may know it, may know about it,
10:39
may know more than I, and might know a good website
10:47
to see this description.
10:49
There will be, of course, a section of the notes,
10:56
you already have it.
10:57
This is section 7.2.
11:02
So this is the chapter on deep learning.
11:06
And the first section was about the structure of F of x.
11:11
And you remember the key point about the structure
11:13
of F of x is that I start with x and apply some function, F1
11:19
of x.
11:21
And to that, I apply some function, F2 of x.
11:24
And to that, I apply some function
11:26
of F3 of F2 of F1 of x.
11:30
And that's the thing whose derivative I need.
11:35
So I'll just take ordinary derivative--
11:38
well, partial derivatives, really.
11:40
Yeah, I better say partial derivatives.
11:42
So suppose x is a pair, xy.
11:45
11:48
Example-- so here, let me show you my example.
11:57
So suppose F of x is--
12:02
let me take a simple example--
12:04
x cubed times x plus 2y.
12:06
12:10
OK.
12:11
So I want to think of that function the way anybody would,
12:18
as the product of two functions.
12:20
So there is a product rule to get into the derivative.
12:26
And then we need the derivatives of each piece.
12:30
So there's a power rule and a linear combination rule.
12:36
So it's got a few of the rules that we use.
12:40
And the point is to think about the computation
12:45
of F of x and the computation of dF dx
12:51
and the computation of dF dy.
12:54
Those are the derivatives that we need.
12:57
This is the function we need and how
13:01
to do those computations quickly.
13:03
OK.
13:04
And this is section 7.2, which benefited a lot from a blog.
13:15
I'm not a blog reader or a blog writer.
13:18
But somehow I found this blog.
13:21
13:27
It's Christopher Olah, is his name.
13:35
And he really writes clear things.
13:38
13:41
He works for one of the big companies
13:43
and does the deeper research.
13:47
But he's also a really good expositor.
13:51
And the website that he now uses is
13:55
called Distill dot something.
14:00
But I think maybe this blog was earlier than
14:04
before the start of Distill.
14:06
But it might be loaded onto Distill.
14:08
Anyway, that's where I got this simple description
14:14
of back propagation.
14:16
And let's just do calculus, first of all.
14:21
If I just have a function of maybe even one variable,
14:24
what's the derivative?
14:25
What is dF dx here, just to remember
14:29
what calculation we have to do?
14:32
So dF dx, this is with n equal one--
14:38
one variable.
14:40
So I use ordinary derivative and not partial derivative.
14:47
But that's what really has to be done.
14:53
But just, what's the derivative of that--
14:55
of a chain of functions?
14:58
Well, of course, the chain rule.
15:01
So what does the chain rule say?
15:04
I differentiate dF.
15:05
15:10
I don't know.
15:12
What do I put that it's differentiated with respect to?
15:15
15:19
dF3, dF2-- is that what I should put?
15:21
OK.
15:22
15:26
And where do I evaluate that derivative?
15:28
15:31
So yeah, I don't evaluate it at x.
15:37
I'm differentiated to F2.
15:39
So do I evaluate it at F2 of F1 of x?
15:45
This is where the chain rule gets sort of a little chain-ey.
15:54
OK.
15:54
Then we know that dF2 dF1.
15:57
16:01
And again, that's now evaluated at F1 of x.
16:05
And then the final factor is dF1 dx evaluated at x.
16:14
That's somehow what we have to do.
16:17
And that's just for an ordinary one-variable function.
16:22
And I have here a two-variable function.
16:24
And deep learning has a million-variable function.
16:27
16:31
So I think we won't go to a million.
16:33
But two, we could manage.
16:35
So let's compute the function, first of all.
16:42
Compute F. So I'm given x equals, say, 2,
16:58
and y equals, say, 3.
17:01
17:04
And I'm going to create a computational graph.
17:09
17:13
So I'm actually going to draw the computational graph
17:27
to compute for F. And then it'll be a variation of that graph
17:37
to find the derivatives.
17:40
So let's just start with the graph, first of all,
17:42
for the function, because we're going to need that.
17:46
So again, it's x cubed plus--
17:49
so can I write that function again? x cubed times x plus 2y.
17:54
17:58
So I think the first step will be to find x plus x cubed--
18:06
that factor, which will be 8.
18:08
18:11
And we have to find the other factor, x plus 2y.
18:16
So then that uses y and x.
18:19
So it's a directed graph in going forward
18:23
with this computation.
18:26
So x plus 2y equals whatever it is--
18:29
2 and 6-- oh, 8 again.
18:31
Not brilliant.
18:33
What shall I change here?
18:36
Make it 3y?
18:37
18:42
3y, just to get a different number here.
18:47
So now x is 2.
18:49
y is 3.
18:50
I get 11.
18:50
That's a good number.
18:52
11.
18:53
18:57
OK.
18:59
So far, so good?
19:01
And now the next step on this graph will be,
19:05
I have a product of those.
19:07
So that will go to the product.
19:10
19:15
F equals 8 times 11--
19:18
88.
19:19
19:22
OK.
19:22
So we've got the answer, 88, which, normally, I
19:28
wouldn't take that much of a book
19:31
to compute F. I would have said, 2 cubed times 2 plus 3 times 3.
19:41
And I'd have simplified that to 8 times 11.
19:47
And I would have got 88.
19:50
So if we were just writing normally, that would do it.
19:54
But this is the picture of the computational graph.
19:59
OK.
20:00
Good.
20:00
Good.
20:01
Good.
20:02
Now it's the derivatives--
20:05
two derivatives to find-- dF dx and dF dy.
20:08
Suppose we go forward first.
20:12
My point is going to be-- or the great point
20:15
is that backward is better.
20:17
Reverse mode is better.
20:19
But we don't know what that means until we've gone forward.
20:22
So let me go forward.
20:24
So now I'm going to go forward.
20:25
20:38
Let's do dF dx.
20:41
Everybody is up for dF dx-- the partial derivative
20:44
with respect to x?
20:46
So here we have x equal 2 and y equal 3.
20:54
21:01
OK.
21:04
And then I take the derivative of that step.
21:11
The first step was x 2x cubed.
21:15
So I need the derivative.
21:16
The whole point of AD is that every computation
21:23
of a derivative breaks down like this into very simple pieces.
21:30
And the derivatives of those simple pieces
21:34
are also simple pieces.
21:36
So the whole point is to replace appropriately
21:44
those intermediate steps with derivatives,
21:50
so as to compute the x derivative.
21:52
So I have to use the fact that the derivative of x
22:00
cubed, with respect to x--
22:02
oh, I better do partial derivative-- partial
22:04
derivatives of x cube, with respect to x, is 3x squared.
22:09
I'll put maybe a formula and then a number.
22:14
So that gives 3 times 4--
22:21
12.
22:22
22:25
And the derivative of x cubed, with respect to y,
22:31
gives 0, clearly.
22:34
So that's 0.
22:35
22:40
So I'm doing the x derivative.
22:44
So the derivative of y, with respect to x, is--
22:51
you get to tell me.
22:54
If I'm computing partial derivatives, it is 0.
22:58
It is 0.
22:59
y and x are independent.
23:03
And this is the reason, in my view,
23:06
that the forward method is wasteful,
23:10
because I'm going to have to do another whole graph for the y
23:15
derivative.
23:16
In other words, tracking the x derivatives,
23:21
a whole lot of stuff never got off the ground.
23:25
So we never should have looked at it.
23:28
So anyway, I have this x plus 3y, maybe.
23:41
I don't know whether to erase that.
23:43
I think I will, just because I don't
23:45
know what to do with it there.
23:49
Yeah.
23:49
So now let me take the ones that I really need,
23:56
is the derivative, with respect to x, of x plus 3y, which is 1.
24:08
And so that gives me the answer 1 for any x actually.
24:14
OK.
24:17
And now what?
24:18
24:20
Oh, yeah, I don't need these.
24:23
This is a waste of time.
24:25
Isn't it?
24:26
24:29
Is it only x derivatives I want?
24:33
Anyway, let's just keep going.
24:36
You can see, this takes a little organization.
24:40
And I'm not practiced with it.
24:42
So what am I going to do?
24:44
I'm looking for the x derivative of--
24:47
I've got to use our product rule now.
24:50
I found the x derivative of that factor was 12.
24:54
The x derivative of this factor is 1.
24:58
And now the x derivative of the product--
25:03
so now I'm going to do, somehow, a product rule--
25:10
the x derivative of this product.
25:15
I should have given these two terms a name.
25:20
Let me call that first term x cubed, and the second term x
25:25
plus 3y--
25:26
call it s.
25:27
So I'll call the two terms c and s.
25:32
25:38
So that's dc ds.
25:41
This is dc dx.
25:43
This is dc dx.
25:46
And this one is ds dx and dc dy.
25:56
Do I need to know that?
25:57
I'm sorry, this computational graph has thrown me.
26:02
But now I want to use the product rule.
26:07
And I'm taking x derivatives.
26:09
So I should have computed c and s.
26:13
Yes, I see I need those in the product rule.
26:16
So I should have computed c as being 8 and s as being 5.
26:30
Is that right?
26:30
2 plus 3-- so 11.
26:35
Yeah, I needed the 8.
26:37
Oh, is that-- what's up?
26:43
I've just been running along here
26:45
without getting myself in the whole picture.
26:49
Yeah, 8 and 11 is right.
26:51
But now I'm looking for the derivatives.
26:53
So I don't multiply those.
26:55
That's not the product rule.
26:57
27:00
So the product rule is what?
27:01
27:07
So this product rule, I have to do this combination of--
27:13
this is now the product rule--
27:14
27:20
for the derivative of c times s.
27:25
So I want c ds dx plus s dc dx.
27:30
I think I'm on track now.
27:32
And now I want to put it in numbers.
27:36
So c is 8.
27:40
ds dx-- have we computed ds dx?
27:45
Yes, ds dx is 1.
27:48
And now s itself is computed as 11.
27:53
And dc dx, we computed as 12.
27:58
I don't dare look.
28:00
28:06
I don't think I'm going to get--
28:08
oh, no, I don't know the answer yet.
28:09
Sorry, I'm not trying to get 88.
28:12
28:14
You guys are not helping.
28:16
[LAUGHS]
28:18
You see I'm in trouble.
28:20
But what I imagine here is, that's 8 and that's 132.
28:24
So I'm getting 140.
28:28
Is there any possibility that that's
28:29
the right answer for dF dx?
28:34
This is dF dx I computed.
28:36
28:40
By watching me struggle here, you're seeing the idea.
28:44
28:47
Every step, I take the derivative of each step.
28:52
So it was a power step, x cubed.
28:55
So I had a 3x squared.
28:57
And a sum step, so I had a 1.
29:00
Then the next step was a multiplication.
29:04
So I needed the product rule for that.
29:08
I have these separate numbers.
29:11
So I put them in.
29:12
And so it's the computational graph finished.
29:18
We only needed two levels.
29:21
And we got 8 and 132--
29:23
140.
29:25
OK.
29:26
But we didn't get dF dy yet.
29:29
29:34
And for that, I'd need to redo this again.
29:37
29:40
And I don't want to do that.
29:43
I would rather do the reverse mode and do them both at once.
29:48
That's the point of the reverse mode.
29:50
It's very efficient.
29:51
It's very efficient, actually.
29:55
Computing the gradient after you've
29:59
done the work for the function, computing first derivatives--
30:03
you could compute n first derivatives
30:05
with about four or five times the cost, not n times.
30:10
That's amazing to me.
30:12
That is amazing that I can compute the gradient very
30:17
efficiently by the back prop.
30:23
So I have to show you the backwards way.
30:25
30:29
Yeah.
30:31
I'm just going to follow all the paths backwards so that I
30:35
get both dF dx and dF dy.
30:38
You see, the idea is to take the derivative of each step--
30:43
each small step.
30:45
That's really what we do in calculus.
30:48
If you think about the start of a calculus course,
30:51
what derivatives do we actually know?
30:53
Do we actually use F at x plus delta x minus F?
31:00
What derivatives do we grind out?
31:02
31:05
We do the derivatives of x to the n.
31:10
Every calculus book starts with x squared and finds
31:14
the derivative of x to the n.
31:15
Then you do sine x and cos x.
31:18
31:21
Then what others?
31:22
Are there any more?
31:25
e to the x-- good, e to the x.
31:28
And it's the inverse function log.
31:31
In freshman calculus, you always write ln, just
31:35
to be out of date.
31:37
OK.
31:38
And now that may be the list.
31:39
Is it?
31:40
And then the chain rule.
31:43
Are there others that you actually do a computation of?
31:50
Actually, e to the x is defined by the property
31:53
that its derivative is e to the x.
31:57
And then you discover what log x has to be.
32:00
And sine x-- how do you do sine of x plus delta x?
32:04
Well, compare minus sine of x.
32:07
How do you find the hard way, once-and-for-all way?
32:12
You draw a little unit circle and mess with some angles.
32:17
And you discover that the derivative of the sine
32:21
is the cosine.
32:24
That's if you've defined the sine as a ratio of sides
32:30
in a right triangle.
32:31
Of course, you could define it as an infinite series.
32:34
And then you would be back to just using that.
32:37
OK.
32:38
32:40
So calculus does exactly what we're doing here--
32:44
finds all derivatives by the chain rule
32:48
applied to a few ones that it has worked out in detail.
32:56
But tangent of x, we would use the quotient rule.
33:02
Secant of x, we would use the quotient rule, 1 over cosine.
33:06
And the products, we use the product rule.
33:09
So really, calculus tends to seem fairly simple
33:17
when you look back to see what, actually, you did.
33:22
And then integration-- what is integral calculus about?
33:26
More or less guessing the answer.
33:29
You have to integrate f of x dx.
33:34
So really, what you have to do is sort of think, OK,
33:38
what had this derivative?
33:40
What function had that derivative?
33:42
And mess around and get it.
33:46
So really, it's a freshman course, I guess.
33:54
OK.
33:54
So where am I?
33:57
Backward.
33:58
Right.
33:59
That's the thing still to do.
34:01
How does the backward system work?
34:04
OK, I'll try my best.
34:07
OK.
34:07
So here is the big goal.
34:10
Back-- so reverse mode AD.
34:14
34:21
Right.
34:21
And let me make myself a little note.
34:25
The little note is to give you another example where
34:30
the order that you do the computations
34:34
makes a big difference.
34:37
And that's not obvious that it will.
34:39
There are many things in math that you
34:41
could do in either order.
34:44
And it seems like, logically, you've done the same things.
34:48
So another, and simpler, example which
34:53
shows how one way could be way faster than another way
34:58
is when I'm multiplying three matrices.
35:04
So I'm multiplying three matrices--
35:06
A times B times C.
35:08
And the question is, do I do BC first and then multiply by A?
35:14
Or do I do AB first and then multiply that by C?
35:20
And of course, I kept them in order--
35:22
in the order ABC.
35:24
But the order of computations can be different.
35:31
You get the right answer both ways.
35:33
But those can be completely, completely different.
35:36
One can be 1,000 times faster than the other.
35:40
So that's just to show--
35:42
actually, it kind of connects to this.
35:45
And there is also another--
35:49
so I'll do that, too.
35:53
So this is example 2, where this is meant to be example 1.
36:01
And example 3 leads to something called the adjoint method
36:09
in differential equations or in optimization--
36:17
in computing optimum and maximizing it.
36:23
Yeah.
36:24
36:28
Really, the underlying reason it gives us speed-up
36:32
is, it makes the right choice in a product of three things.
36:38
Yeah.
36:39
So it'll be enough to do example 1 and example 2.
36:43
OK, let me go with example 1.
36:48
This is now back propagation.
36:50
Finally, we got to it.
36:52
OK.
36:52
36:59
Well, I look at my notes is how I do it.
37:03
37:07
So the notes-- this is section 7.2--
37:10
does these computational graphs.
37:12
And then here is reverse mode.
37:15
37:18
So it starts over here with the--
37:20
so I'm going to use the chain rule.
37:22
So dF dF is 1.
37:26
And then I'm going backwards.
37:28
37:31
And of course, I have to use the right rule.
37:38
So I have to use the product rule.
37:41
And then soon I'll have to use these power
37:43
rule and linear rules.
37:45
So of course, no change there.
37:47
The change is that by going backwards--
37:52
oh, I don't know if I completed that sentence,
37:55
that I could find 100 partial derivatives,
37:59
if the function depended on 100 variables,
38:02
in about five times the cost of one variable--
38:07
three to five times the cost of one.
38:10
So you would expect 100 chain rules would cost 100 times.
38:16
But you see, we're reusing the pieces in the chain
38:22
and just having a larger--
38:26
our chain is wider.
38:28
But it's not longer.
38:29
And it's not repeated.
38:30
Anyway, so here I'm going to use whatever it is--
38:36
dF dc and dF ds.
38:43
And I'm remembering that--
38:44
38:47
yeah, OK.
38:49
So dF dc is s, and dF ds is c.
38:54
That was because F started out as c times s.
39:01
It was the product.
39:02
OK.
39:03
Then we've got to evaluate those.
39:06
And I'll look again to see that I'm hopefully writing down
39:10
some of the correct things.
39:11
39:14
OK.
39:16
So now what I've written down next is dF dc is 5.
39:21
Or no, 5 on that example.
39:24
What is it here? dF dc is--
39:30
c is x cubed.
39:35
So dF-- oh, sorry, dF dc--
39:40
yeah, I want s.
39:42
I'm looking for s here.
39:43
Yeah.
39:44
I'm looking for s.
39:45
39:50
So I'm looking for s.
39:53
And that's x plus 3y.
39:58
Am I doing this well?
39:59
40:04
I want, in the end, to get the derivatives with respect
40:08
to x and y-- the whole gradient.
40:10
OK.
40:11
I think we started right.
40:13
The first derivatives is to write c and s.
40:16
And then let me leave these boxes open,
40:20
just to get the picture.
40:21
40:24
Then I'll need dc dx, dc dy, ds dx, and ds dy.
40:43
I think that's right.
40:44
40:47
Here, I had a product of c and s.
40:49
So I had two derivatives.
40:52
Here I have c and s, each to differentiate.
40:57
So have an x and a y derivative of x and a y derivative.
41:01
And now it's just a matter of putting in those numbers
41:05
and following the chain backwards.
41:07
41:13
Maybe I'm not going to put those numbers in,
41:15
because if I didn't reach 140, you wouldn't
41:19
believe in back propagation.
41:21
And that would be an unhappy outcome.
41:25
41:28
So I'll leave you to put them in maybe.
41:31
Or the notes have a separate example that you can see.
41:35
But do you see the point--
41:37
that in the end, I'm going to find dF dx and dF
41:47
dy from the chain--
41:53
from one chain and not from a separate chain for x
41:59
and a separate chain for y.
42:02
To me, that's the point of reverse mode.
42:06
It's a little bit of magic.
42:09
But you see the steps--
42:12
the ingredient.
42:13
And some of you have seen this before and maybe
42:17
know a better exposition.
42:19
I found this blog by Christopher Olah clear.
42:24
And these very simple things, you'll see,
42:26
are clear in the notes.
42:28
But maybe another blog brings out other points to make here.
42:36
It's not obvious, maybe, that I could have 100 variables
42:41
and do the calculation in four or five times the cost--
42:48
four or five times being instead of 100.
42:52
Yeah.
42:53
But it's possible.
42:55
OK.
42:56
So could I close today with this one?
43:00
43:05
How could those be different?
43:07
You're computing the same numbers, the same AIJ, BJKs,
43:12
CKLs, and doing these sums.
43:17
But it certainly is different.
43:19
So let's just do that.
43:21
OK.
43:21
I'll do it here.
43:22
43:28
And then at the right time-- and I
43:31
guess it'll be after Professor Rao on Friday and Monday,
43:36
I'll come back to Professor Sra's short proof
43:42
of the convergence of stochastic gradient descent.
43:48
The whole point is to show you what assumptions do you need.
43:52
You need some assumptions on the gradient, some assumptions
43:56
on the step size.
43:58
And for a good proof, all the assumptions fit together,
44:02
and, dong, out comes the conclusion.
44:06
And the conclusion would be how fast it converges--
44:10
stochastic gradient descent.
44:11
So there's some expected things, because it's stochastic.
44:18
We expect some assumptions about the mean and the variance
44:25
to go into the proof.
44:28
So you'll see that.
44:29
But maybe it's too much for today.
44:33
So I'll come back to that.
44:36
I might even put it on Stellar and just close with this.
44:45
So suppose A is m by n, B is n by p, and C is p by q.
44:56
OK.
44:57
How many steps does it take to find A times B times C--
45:04
the product of those three matrices?
45:06
Well, if I go this way, I have to do BC first.
45:14
So BC costs-- how many operations
45:18
to multiply that times that?
45:20
45:24
npq-- nice formula.
45:25
npq.
45:26
45:28
Why is that?
45:30
Well, I could say that the answer is n by q.
45:36
And every number in there was an inner product
45:41
of a row and column of length p.
45:45
So I have nq inner products.
45:50
And each one costs p--
45:52
45:54
multiply, adds.
45:58
So now I have BC, which will be--
46:04
so now I have m by n.
46:06
Then I have m by n, which is the A times
46:14
B by C, which is now n by q.
46:17
That's BC.
46:18
This is A, BC.
46:20
And this one costs--
46:23
what's the cost here?
46:25
m by n, m by q--
46:28
by the same rule, it'll be mnq.
46:30
46:32
Good.
46:34
That's the first way--
46:36
A times BC.
46:38
Now, the second way is AB times C. Let me write in again,
46:44
m by n, n by p, p by q.
46:47
46:51
So now I'm doing this first--
46:53
so AB costs.
46:56
Tell me again now, what's the rule
46:58
for the cost of a matrix multiplication?
47:03
mnp.
47:04
mnp.
47:04
47:08
And then I multiply m by p--
47:16
that's AB-- times p by q.
47:18
That's C.
47:20
So I have mpq.
47:22
47:27
So I have that together with that, or that
47:32
together with that.
47:35
That sum-- those two or these two.
47:41
And they're different.
47:43
And let's just recognize the most important example.
47:48
Suppose C is a column vector--
47:50
C for column vector.
47:52
So q is 1.
47:54
There's only one column.
47:56
So if q is 1, this way did np--
48:00
let's just specialize to that.
48:02
48:06
So specialize to C equal a column vector,
48:16
which means that q is 1.
48:19
I only have one column.
48:20
So then A times BC is versus AB times C.
48:30
So let's just figure that out when q is 1.
48:33
So npq is just np.
48:37
And mnq is just mn, where AB is m and p.
48:48
Oh, that's a bad one.
48:51
Disaster already.
48:52
48:55
Those are potentially two big matrices,
48:58
multiplying a column vector.
49:01
So here I've done a matrix multiplication.
49:03
I never should have done that.
49:04
This is a matrix vector.
49:07
It gives me a vector.
49:09
And then this is a matrix vector.
49:11
So I get nice numbers here.
49:14
But I get a terrible number for AB.
49:17
And then I multiply that by C. So that's mpq.
49:21
49:25
mpq.
49:26
49:29
So mp is factoring out.
49:31
So if I write it as n times m plus p versus this one
49:42
is m that's factoring out times m--
49:50
no.
49:51
Yeah.
49:53
What's up here?
49:54
49:56
Yeah.
49:57
Sorry.
49:58
What am I doing?
49:59
50:05
Yeah.
50:06
Is it p that factors out from this one?
50:09
OK.
50:11
p times m plus n, I guess.
50:15
Sorry.
50:16
50:19
Anyway, the difference is--
50:24
AUDIENCE: I think it's mp times p plus q.
50:29
[INAUDIBLE]
50:30
GILBERT STRANG: Shall I go over it again or write--?
50:34
Let me do just this thinking again.
50:36
If q is 1, if I go this way, was that
50:39
my final total when q was 1?
50:42
And that's this?
50:45
No.
50:46
m factors out times n plus p.
50:49
Let's just get that right.
50:52
Oh, no, n factors out.
50:54
Sorry, n factors out times m plus p.
50:58
And this way was all these things.
51:03
AUDIENCE: Both the m and the p factor out.
51:07
GILBERT STRANG: Both the m and the p factor out.
51:10
OK.
51:11
Thanks.
51:12
51:16
Times n plus q.
51:22
n plus q was 1.
51:24
OK.
51:24
51:29
The whole point is, we've got this horrible multiplication
51:32
of three big numbers.
51:36
And this only had two big numbers.
51:38
So this is orders of magnitude faster than that.
51:42
And of course, you would have done the calculation.
51:45
That way, you would have multiplied the column vector
51:48
by a matrix to get another column vector.
51:52
And you would have multiplied that by a matrix
51:54
to get another column vector, where here,
51:57
you crazily multiplied two big matrices together and then got
52:02
a column vector.
52:02
So there is a bad move.
52:07
OK, thanks.
52:08
Oh, I'm past the time on this ABC.
52:11
It's just to show that on a very familiar calculation,
52:16
you have to do it in the right order.
52:18
And back propagation is the right order
52:21
for partial derivatives.
52:24
OK.
52:24
Thank you.
52:25
And so bring laptops Friday.
52:29
And look forward to Professor Rao.
52:35
Give him a good welcome.
English - CC (English)
###