26. Structure of Neural Nets for Deep Learning
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...This lecture is about the central structure of deep neural networks, which are a major force in machine learning. The aim is to find the function that's constructed to learn the training data and then apply it to the test data. 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, so this is an important day,
00:25
and Friday was an important day.
00:27
I hope you enjoyed Professor Sra's terrific lecture as much
00:32
as I did.
00:33
You probably saw me taking notes like mad for the section that's
00:39
now to be written about stochastic gradient descent.
00:44
And he promised a theorem, if you remember,
00:49
and there wasn't time.
00:50
And so he was going to send it to me
00:52
or still is going to send it to me.
00:54
I'll report, I haven't got it yet,
00:57
but I'll bring it to class, waiting to see, hopefully.
01:04
And that will give us a chance to review stochastic gradient
01:09
descent, the central algorithm of deep learning.
01:13
And then this today is about the central structure
01:20
of deep neural nets.
01:22
And some of you will know already how they're connected,
01:28
what the function F, the learning function--
01:36
you could call it the learning function--
01:40
that's constructed.
01:41
The whole system is aiming at constructing this function
01:46
F which learns the training data and then
01:52
applying it to the test data.
01:55
And the miracle is that it does so well in practice.
02:01
That's what has transformed deep learning into such
02:07
an important application.
02:11
02:17
Chapter 7 has been up for months on the
02:22
math.mit.edu/learningfromdata site,
02:27
and I'll add it to Stellar.
02:28
Of course, that's where you'll be looking for it.
02:33
OK, and then the second, the back propagation,
02:37
the way to compute the gradient, I'll
02:42
probably reach that idea today.
02:45
And you'll see it's the chain rule, but how is it organized.
02:51
OK, so what's the structure?
02:53
What's the plan for deep neural nets?
02:57
Good.
02:58
Starting here, so what we have is training data.
03:02
03:06
So we have vectors, x1 to x--
03:13
what should I use for the number of samples
03:17
that we have in the training data?
03:21
Well, let's say D for Data.
03:24
OK.
03:26
And each vector, those are called feature vectors,
03:30
so equals feature vectors.
03:37
03:40
So each one, each x, has like m features.
03:48
So maybe my notation isn't so hot here.
03:55
I have a whole lot of vectors.
03:58
Let me not use the subscript for those right away.
04:03
So vectors, feature vectors, and each vector
04:08
has got maybe shall we say m features?
04:13
Like, if we were measuring height and age and weight
04:17
and so on, those would be features.
04:19
04:23
The job of the neural network is to create--
04:28
and we're going to classify.
04:29
Maybe we're going to classify men and women or boys
04:35
and girls.
04:36
So let's make it a classification problem,
04:41
just binary.
04:43
So the classification problem is--
04:47
what shall we say?
04:48
Minus 1 or 1, or 0 or 1, or boy or girl,
04:59
or cat or dog, or truck or car, or anyway, just two classes.
05:05
05:08
So I'm just going to do two-class classification.
05:12
05:15
We know which class the training data is in.
05:18
For each vector x, we know the right answer.
05:21
So we want to create a function that gives the right answer,
05:25
and then we'll use that function on other data.
05:30
So let me write that down.
05:33
Create a function F of x so that gets--
05:42
most of gets the class correct.
05:50
In other words, F of x should be negative for when
05:58
the classification is minus 1, and F of x
06:04
should be positive when the classification is plus 1.
06:11
And as we know, we don't necessarily
06:14
have to get every x, every sample, right.
06:17
That may be over-fitting.
06:19
If there's some sample that's just truly weird, by getting
06:24
that right we're going to be looking
06:26
for a truly weird data in the test set,
06:32
and that's not a good idea.
06:33
06:39
We're trying to discover the rule that
06:41
covers almost all cases but not every crazy, weird case.
06:46
OK?
06:47
So that's our job, to create a function
06:50
F of x that is correct on almost all of the training data.
06:58
07:01
Yeah.
07:02
07:05
So before I draw the picture of the network,
07:12
let me just remember to mention the site Playground.
07:23
I don't know if you've looked at that, so I'm going to ask you,
07:26
playground@tensorflow.org.
07:28
07:36
How many of you know that site or have met with it?
07:40
Just a few, OK.
07:42
OK, so it's not a very sophisticated site.
07:46
It's got only four examples, four examples.
07:49
07:57
So one example is a whole lot of points that are blue,
08:03
B for Blue, inside a bunch of points
08:08
that are another set that are O for Orange, orange, blue.
08:18
OK, so those are the two classes, orange and blue.
08:23
So the points x and the feature vector here is just the xy,
08:34
the coordinates features are the xy coordinates of the points.
08:42
And our job is to find a function that's
08:46
positive on these points and negative on those points.
08:51
So there is a simple model problem, and I recommend--
08:55
well, just partly--
08:58
if you're a expert in deep learning.
09:00
This is for children, but morally here, I certainly
09:07
learned from playing in this playground.
09:10
So you set the step size.
09:19
09:22
Do you set it, or does it set it?
09:25
I guess you can change it.
09:27
I don't think I've changed it.
09:30
What else do you set?
09:31
Oh, you set the nonlinear activation, the nonlinear
09:41
activation function, active I'll say function.
09:46
And let me just go over here and say what function people now
09:51
mostly use.
09:52
The activation function is called
09:59
ReLU pronounced different ways.
10:03
I don't know how we got into that crazy thing.
10:06
For this function, that is 0 and x.
10:13
So the function, ReLU is a function
10:15
of x is the maximum the larger of 0 and x.
10:20
10:24
The point is, it's not linear, and the point
10:27
is that if we didn't allow nonlinearity in here somewhere,
10:31
we couldn't even solve this playground problem.
10:34
Because if our classifiers were all linear classifiers,
10:38
like support vector machines, I couldn't separate the blue
10:44
from the orange with a plane.
10:48
It's got to somehow create some nonlinear function which maybe
10:53
the function is trying to be--
10:55
a good function would be a function of r and theta maybe,
11:03
maybe r minus 5.
11:07
So maybe the distance out to that.
11:10
Let's suppose that distance is 5.
11:13
Then, r minus 5 will be negative on the blues,
11:17
because r is small.
11:19
And r minus 5 will be positive on the oranges,
11:22
because r is bigger.
11:24
And therefore, we will have the right signs, less than 0
11:30
or greater than 0, and it'll classify
11:35
this data, this training data.
11:39
Yeah.
11:41
So it has to do that.
11:43
This is not a hard one to do.
11:45
There are four examples, as I say, two are trivial.
11:51
It finds a good function.
11:53
Well yeah, I've forgotten, they're so trivial,
11:56
they shouldn't be mentioned, and then this is the medium test.
12:07
And then the hard test is when you
12:10
have a sort of spiral of oranges,
12:17
and inside, you have a spiral of blues.
12:20
That was cooked up by a fiend.
12:24
12:29
So the system is trying to find a function
12:35
that's positive on one spiral and negative on the other
12:39
spiral, and that takes quite a bit of time, many, many epochs.
12:45
I learned what an epoch is.
12:47
12:50
Did you know what an epoch is?
12:51
I didn't know whether it was just
12:53
a fancy word for counting the steps in gradient descent.
12:58
But it counts the steps, all right,
13:03
but one epoch is the number of steps that matches
13:07
the size of the training data.
13:11
So if you have a million samples--
13:14
where ordinary gradient descent you would be doing a million--
13:18
you'd have a million by a million problem per step.
13:23
Of course, stochastic gradient descent
13:27
just does a mini-batch of 1 or 32 or something, but anyway.
13:32
13:37
So you have to do it enough mini-batches
13:41
so that the total number you've covered
13:44
is the equivalent of one full run through the training data,
13:54
and that was an interesting point.
13:55
Did you pick up that point?
13:57
That in stochastic gradient descent,
14:01
you could either do a mini-batch,
14:05
and then put them back in the soup, so with replacement.
14:11
Or you could just put your data in some order,
14:17
from one to a zillion.
14:20
So here's a first x and then more and more
14:25
x's, and then just randomize the order.
14:30
So you'd have to randomize the order for stochastic gradient
14:34
descent to be reasonable, and then
14:36
take a mini-batch and a mini-batch
14:38
and a mini-batch and a mini-batch.
14:40
And when you get to the bottom, you've finished one epoch.
14:44
And then you'd probably randomize again, maybe,
14:47
if you wanted to live right.
14:51
And go through the mini-batches again,
14:56
and probably do 1,000 times or more.
15:01
Anyway, so I haven't said yet what you do, what this F of x
15:06
is like, but you can sort of see it on the screen.
15:09
Because as it creates this function F,
15:14
it kind of plots it.
15:17
And what you see on the screen is the 0 set for that function.
15:23
So perfect would be for it to go through 0--
15:27
if I had another color.
15:29
Oh, I do have another color.
15:31
Look, this is the first time the whole semester blue is up here.
15:36
OK, so if the function was positive there--
15:43
in this part, on the blues--
15:45
and negative outside that region for the oranges, that
15:51
would be just what we want.
15:52
Right?
15:53
That would be what this little Playground site is creating.
15:57
And on the screen, you'll see it.
15:59
You'll see this curve, where it crosses 0.
16:05
So that curve, where it crosses 0,
16:07
is supposed to separate the two sets.
16:10
One set is positive, one set is negative,
16:12
where 0 is in between.
16:15
And the point is, it's not a straight line, because we've
16:19
got this nonlinear function.
16:22
This is nonlinear, and it allows us to have
16:33
functions like r minus 5.
16:36
And so at 5, that's where the function would be 0,
16:42
and you'll see that on the screen.
16:45
You might just go to playground@tensorflow.
16:50
Of course, TensorFlow is a big system.
16:53
This is the child's department, but I
17:00
thought it was pretty good.
17:01
And then on this site, you decide
17:04
how many layers there will be, how many neurons in each layer.
17:08
So you create the structure that I'm about to draw.
17:13
And you won't be able to get to solve this problem
17:21
to find a function F that learns that data
17:25
without a number of layers and a number of neurons.
17:31
If you don't give it enough, you'll see it struggling.
17:34
17:39
The 0 set tries to follow this, but it gives up at some point.
17:46
This one doesn't take too many layers,
17:48
and the two trivial examples, just a few neurons do the job.
17:54
OK.
17:55
So now, that's a little commented on one website.
18:02
If you know other websites that I should know
18:05
and should call attention to, could you send me an email?
18:10
I'm just not aware of everything that's out there.
18:15
Or if you know a good Convolutional Neural Net, CNN,
18:22
that is available to practice on,
18:27
where you could give it the training set.
18:32
That's what I'm talking about here.
18:34
18:38
I'd be glad to know, because I just
18:41
don't know all that I should.
18:43
OK.
18:43
So what does the function look like?
18:47
Well, as I say, linear isn't going to do it,
18:51
but linear is a very important part of it, of this function
18:56
F. So the function F really has the form--
19:01
well, so we start here with a vector of one,
19:08
two, three, four, m is five.
19:11
This is the vector x, five components.
19:19
OK, so let me erase that now.
19:23
OK, so then we have layer 1 with some number of points.
19:36
Let's say, n1 is 6 neurons, and let me make this simple.
19:47
I'll just have that one layer, and then I'll have the output.
19:51
This will be the output layer, and it's just
19:57
going to be one number.
19:58
20:01
So I'm going to have a matrix, A1, that takes me from this.
20:08
A1 will be 6 by 5, because I want 6 outputs and 5 inputs.
20:18
6 by 5 matrix, so I have 30 weights to choose there.
20:23
And so the y that comes out is going
20:31
to be y1 will be A1 times x0.
20:36
So x0 is the feature vector with 5 components.
20:44
So that's a purely linear thing, but we also
20:47
want an offset function, offset vector.
20:54
So that's a vector.
20:56
Then, this, the y that's coming out, has 6 components.
21:02
The A1 is 6 by 5, the x0 was 5 by 1,
21:07
and then of course, this is 6 by 1.
21:10
So these are the weights.
21:12
21:15
Yeah, I'll call them all weights, weights to compute.
21:19
21:25
So these are connected.
21:27
The usual picture is to show all these connections.
21:34
I'll just put in some of them.
21:38
So in here, we have 30 plus 6 parameters, 36 parameters,
21:49
and then I'm going to close this.
21:52
It's going to be a very shallow thing, so that will be just 1
22:02
by 6.
22:03
Yeah.
22:04
OK.
22:05
22:08
Right, so we're just getting one output.
22:11
So that's just a vector at this final point, but of course,
22:18
that the whole idea of deep neural nets
22:21
is that you have many layers.
22:23
So 36 more realistically is in the tens of thousands,
22:29
and you have it multiple times.
22:32
And the idea seems to be that you can separate what
22:42
layer one learns about the data and from what layer two learns
22:49
about the data.
22:50
Layer one-- this A1, apparently by just looking after
22:57
the computation--
22:58
this learns some basic facts about the data.
23:04
The next, A2 which would go in here, would learn more detail,
23:13
and then A3 would learn more details.
23:16
So we would have a number of layers,
23:19
and it's that construction that has made neural net successful.
23:27
But I haven't finished, because right now, it's only linear.
23:32
Right now, I just have, I'll call it A2 in here.
23:36
Right now, I would just have a matrix multiplication
23:38
apply A1 and then apply A2, but in between there is a 1
23:47
by 1 action on each by this function.
23:55
23:58
So that function acts on that number
24:02
to give that number back again or to give 0.
24:06
So in there is ReLU.
24:09
In this comes ReLU on each, 6 copies of ReLU acting
24:18
on each of those 6 numbers.
24:20
Right?
24:21
So really x1 comes from y1 by applying ReLU to it.
24:32
Then, that gives the x.
24:34
So here are the y's from the linear part,
24:37
and here are the x--
24:39
that's y1.
24:40
That's a vector y1 from just the linear plus an affine map.
24:46
Linear plus constant, that's affine.
24:51
And then the next step is component by component
24:55
we apply this function, and we get x1, and then do it
25:03
again and again and again.
25:05
So do you see the function?
25:07
How do I describe now the function F of x?
25:10
25:14
So the learning function which depends on the weights,
25:26
on the A's and b's.
25:28
25:32
So I start with an x, I apply A1 to it.
25:39
Yeah, let me do this.
25:41
This is the function F of x.
25:44
F of x is going to be F3, let's say,
25:48
of F2 of F1 of x, one, two, three, parentheses, right?
25:58
OK, so it's a chain, you could say.
26:01
F is a-- what's the right word for a chain of functions,
26:06
if I take a function of a function?
26:09
The reason I use the word chain is that the chain rule
26:12
gives the derivative.
26:14
So a function of a function of a function, that's
26:19
called composition, composing function.
26:23
So this is a composition.
26:27
I don't know if there's a standard symbol for starting
26:30
with F1 and do some composition and do some composition.
26:36
And now what are those separate F's?
26:38
26:43
So the separate F's are the--
26:47
F1 of a vector would be-- it includes
26:52
the ReLU part, the nonlinear part, of A1, x0 plus b1.
27:01
So two parts, you do the linear or affine map
27:07
on your feature vector, and then component
27:13
by component you apply that nonlinear function.
27:18
And it took some years before that nonlinear function
27:22
became a big favorite.
27:27
People imagined that it was better,
27:29
it was important, to have a smooth function.
27:33
So the original functions were sigmoids, like S curves,
27:42
but of course, it turned out that experiments showed
27:46
that this worked even better.
27:48
Yeah, so that would be F1, and then F2
27:52
would have the same form, and F3 would have the same form.
27:55
So maybe this had 36 weights, and the next one
27:59
would have another number and the next another number.
28:04
You get quite complicated functions by composition,
28:08
by like e to the sine of x, or e to the sign of the logarithm
28:14
of x, or things like that.
28:18
Pure math has asked, what functions can you get?
28:23
Try to think of them all.
28:24
Now, what kind of functions do we have here?
28:27
What can I say about F of x as a function, as a math person?
28:33
What kind of a function is it?
28:37
So it's created out of matrices and vectors,
28:42
out of a linear or affine map, followed by a nonlinear,
28:49
by that particular nonlinear function.
28:54
So what kind of a function is it?
28:56
Well, I've written those words down up here, and F of x
29:04
is going to be a continuous piecewise linear function.
29:07
29:10
Because every step is continuous,
29:15
that's a continuous function.
29:17
Linear functions are a continuous functions,
29:19
so we're taking a composition of continuous function,
29:24
so it's continuous.
29:26
And it's piecewise linear, because part of it is linear,
29:30
and part of it is piecewise linear.
29:32
29:35
So this is some continuous, piecewise, linear function
29:51
of x, x in m dimensions.
29:58
OK.
29:59
30:02
So one little math question which I think
30:07
helps to understand, to like to swallow
30:13
the idea of a chain, of the kind of chain we have here,
30:19
of linear followed by ReLU.
30:22
30:27
So here's my question.
30:29
This is the question I'm going to ask.
30:31
And by the way, back propagation is certainly
30:34
going to come Wednesday rather than today.
30:37
That's a major topic in itself.
30:41
So let me keep going with this function.
30:44
30:47
Could you get any function whatsoever this way?
30:50
Well, no, you only get continuous, piecewise,
30:53
linear functions.
30:56
It's an interesting case.
30:59
Let me just ask you.
31:01
One of the exercises says, if I took
31:04
two continuous, piecewise, linear functions--
31:09
the next 20 minutes are an attempt
31:12
to give us a picture of the graph of a piecewise,
31:16
linear function in say a function of two variables.
31:23
So I have m equal to 2, and I draw its graph.
31:30
OK, help me to draw this graph.
31:32
So this would be a graph of F of x1, x2,
31:38
and it's going to be continuous and piecewise linear.
31:41
So what does its graph look like?
31:43
That's the question.
31:45
What's the graph of a piecewise, linear function looks like?
31:50
Well, it's got flat pieces in between the change from--
32:00
I do say piecewise, that means it's got different pieces.
32:04
But within a piece, it's linear, and the pieces with each other,
32:12
because it's continuous.
32:13
So I visualize, well, it's like origami.
32:20
This is the theory of origami almost.
32:24
So right, origami, you take a flat thing,
32:27
and you fold it along straight folds.
32:32
So what's different from origami?
32:34
Maybe not much.
32:35
32:38
Well, maybe origami allows more than we allow here,
32:43
or origami would allow you to fold it up and over.
32:46
So origami would give you a multi-valued thing,
32:51
because it's got a top and a bottom and other folds.
32:55
This is just going out to infinity in flat pieces,
33:02
and the question will be, how many pieces?
33:06
So let me ask you that question.
33:07
How many pieces do I have?
33:11
Do you see what I mean by a piece?
33:15
So I'm thinking of a graph that has these flat pieces,
33:19
and they're connected along straight edges.
33:23
And those straight edges come from the ReLU operation.
33:30
Well, that's got two pieces.
33:33
Actually, we could do it 1D.
33:35
In 1D, we could count the number of pieces pretty easily.
33:39
So what would be a piecewise linear?
33:41
Let me put it over here on the side and erase it soon.
33:45
OK.
33:48
So here's m equal 1, a continuous, piecewise, linear
33:56
F. I'll just draw its graph.
34:00
So OK, so it's got straight pieces,
34:08
straight pieces like so.
34:11
Yeah, you've got the idea.
34:12
It's a broken line type.
34:14
Sometimes, people say broken line,
34:16
but I'm never sure that's a good description of this.
34:21
Piecewise, linear, continuous, so it's continuous
34:24
because the pieces meet, and it's piecewise,
34:30
linear, obviously.
34:31
OK, so that's the kind of picture
34:34
I have for a function of one variable.
34:39
Now, my question is--
34:42
as an aid to try to visualize this function in 2D--
34:47
is to see if we can count the pieces,
34:51
see if we can count the pieces.
34:53
Yes.
34:55
So that's in the notes.
34:58
I found it in a paper by five authors for a meeting.
35:06
35:08
So actually, the whole world of neural nets,
35:16
it's the conferences every couple of years
35:21
that everybody prepares for, submits more than one paper.
35:27
So it's kind of a piecewise, linear conference,
35:30
and those are the big conferences.
35:35
OK.
35:36
So this is the back propagation section,
35:38
and I want to look at the--
35:42
OK.
35:43
35:46
So this is a paper by Kleinberg and four others.
35:49
Kleinberg, he's a computer science guy at Cornell.
35:54
He was a PhD from here in math, and he's
35:57
a very cool and significant person,
36:04
not so much on neural networks as just this whole part
36:13
of computer science.
36:15
Right.
36:15
So anyway, they and other people too
36:19
have asked this same problem.
36:20
36:23
Suppose I'm in two variables.
36:24
36:28
So what are you imagining now for the surface,
36:33
the graph of F of x and y?
36:39
It has these lines, fold lines, right?
36:43
I'm thinking it has fold lines.
36:45
36:48
So I can start with a complete plane, and I fold it
36:51
along one line.
36:53
So now, it's like ReLU.
36:55
It's one half plane there going into a different half plane
37:00
there.
37:00
Everybody with it?
37:03
And now, I take that function, that surface
37:08
which just has two parts, and I put in another fold.
37:14
OK, how many parts have I got now?
37:17
I think four, am I right?
37:20
Four parts, yes, because this will be different from this,
37:26
because it was folded along that line.
37:28
So these will be four different pieces.
37:31
They have the same value at the center there,
37:34
and they match along the lines.
37:39
So the number of flat pieces is four for this.
37:43
So that's with two folds, and now I just want to ask you,
37:47
with m folds how many pieces are there?
37:51
Can I get up to three folds?
37:53
37:56
So I'm going to look for the number of folds.
37:59
So let me just use a notation, maybe r.
38:04
r is the number of flat pieces, and m is the dimension of x.
38:22
In my picture, it's two, and N is the number of folds.
38:29
38:33
So let me say it again.
38:35
I'm taking a plane.
38:36
38:40
I'll fold that plane--
38:42
because the dimension was two--
38:45
I'll fold it N times.
38:47
38:51
How many pieces?
38:52
How many flat pieces?
38:53
39:06
This would be a central step in understanding
39:10
how close the function--
39:13
what freedom you have in the function F. For example,
39:18
can you approximate any continuous function
39:22
by one of these functions F by taking enough folds?
39:27
Seems like the answer should be yes, and it is yes.
39:30
39:34
For pure math, that's one question.
39:38
Is this class of functions universal?
39:41
So the universality theorem would
39:44
be to say that any function--
39:49
sine x, whatever-- could be approximated
39:53
as close as you like by one of these guys with enough folds.
39:59
And over here, we're kind of making it more numerical.
40:05
We're going to count the number of pieces
40:07
just to see how quickly do they grow.
40:10
So what happens here?
40:12
So I have four folds.
40:14
Right now, I have N equal 2.
40:18
m is 2 here in this picture.
40:23
And I'm trying to draw this surface, in here I've put in 2.
40:27
Did I take N?
40:28
Yeah, two folds, and now I'm going to go up to three folds.
40:34
OK.
40:34
So let me fold it along that line.
40:37
How many pieces of I got now?
40:39
40:44
Let's see, can I count those pieces?
40:49
Is it seven?
40:52
So what is a formula?
40:54
What if I do another fold?
40:55
40:59
Yeah, let's pretend we do another fold.
41:01
Yeah?
41:02
AUDIENCE: [INAUDIBLE]
41:04
GILBERT STRANG: Uh, yeah.
41:06
Well, maybe that's going to be it.
41:10
41:12
It's a kind of nice question, because it asks
41:15
you to visualize this thing.
41:16
OK.
41:17
41:20
So what happened?
41:22
How many of those lines will be--
41:24
if I put in a fourth line--
41:27
how many?
41:29
Yeah, how many new folds do I create?
41:33
That's kind of the question, and I'm
41:34
assuming that fourth line doesn't
41:37
go through any of these points.
41:39
It's sort of in general position.
41:40
41:43
So I put it in a fourth line, da-da-da-da, there it is.
41:47
OK, so what happened here?
41:50
How many new ones did it create?
41:53
How many new ones did it create?
41:55
41:58
Let me make that one green, because I'm
42:01
distinguishing that's the guy that's
42:03
added after the original.
42:06
We had seven.
42:07
We had seven pieces, and now we've got more.
42:14
Was it seven?
42:15
It was, wasn't it?
42:16
One, two, three, four, five, six, seven, but now how many
42:20
pieces have I got?
42:22
Or how many pieces did this new line create?
42:30
We want to build it up, use a recursion.
42:32
How many pieces did this new--
42:35
well, this new line created one new piece there.
42:39
Right?
42:40
One new piece there, one new piece there,
42:43
one new piece there, so there are four new pieces.
42:50
OK.
42:52
Yes, so there's some formula that's
42:55
going to tell us that, and now what would the next one create?
42:59
Well, now I have one, two, three, four lines.
43:03
So now, I'm going to put through a fifth line,
43:06
and that will create a whole bunch of pieces.
43:09
I'm losing the thread of this argument, but you're onto it.
43:14
Right?
43:16
Yeah, so any suggestions?
43:19
Yeah.
43:20
AUDIENCE: Yeah, I think you add essentially the number of lines
43:23
that you have each time you add a line at most.
43:26
GILBERT STRANG: OK.
43:27
Yes.
43:30
That's right.
43:30
So there is a recursion formula that I want to know,
43:34
and I learned it from Kleinberg's paper.
43:36
43:39
And then we have an addition to do,
43:42
so the recursion will tell me how much it goes up
43:45
with each new function, and then we have to add.
43:49
OK.
43:49
So the recursion formula, let me write that down.
43:52
43:56
So this is r of N and m that I'd like to find a formula for.
44:06
It's the number of flat pieces with an m dimensional surface--
44:12
well, we're taking m to be 2--
44:14
and N folds.
44:16
44:18
So N equal 1, 2, 3.
44:22
Let's write down the numbers we know.
44:25
With one fold, how many pieces?
44:29
Two, good, so far so good.
44:32
44:35
With one fold, there were two pieces.
44:38
So this is the count r, and then with two folds, how many?
44:44
Oh, we've gone past that point.
44:46
So can we get back to just those two?
44:50
Was it four?
44:51
AUDIENCE: Yes.
44:52
GILBERT STRANG: OK, thanks.
44:55
Now, when I put in that third fold, how many did I have
44:59
without the green line yet?
45:02
Seven, was it seven?
45:06
And when the fourth one went in, that green one, how many have I
45:12
got in this picture?
45:13
45:15
So the question is how many new ones did I create, I guess.
45:19
So that line got chopped into that piece, that piece,
45:24
that piece, that piece, four pieces for the new line.
45:27
Four pieces for the new line, and then each of those pieces
45:32
like added a flat bit.
45:36
Because that piece from here to here
45:40
separated these two which were previously
45:43
just one piece, one flat piece.
45:45
I folded on that line.
45:47
I folded on this.
45:48
I folded there.
45:49
I think it went up by 4 to 11.
45:51
45:55
So now, we just have to guess a formula that
45:59
matches those numbers, and then of course, we really
46:02
should guess it for any m and any N.
46:09
And I'll write down the formula that they found.
46:13
46:16
It involves binomial numbers.
46:19
Everything in the world involves binomial numbers,
46:24
because they satisfy every identity you could think of.
46:28
46:34
So here's their formula.
46:35
46:38
r with N folds, and we're in m dimensions.
46:43
So we've really in our thinking had m equal to 2,
46:46
but we should grow up and get m to be five dimensional.
46:53
So we have a five dimensional--
46:55
let's not think about that.
46:57
OK.
47:00
So it turns out it's binomial numbers--
47:03
N 0, N 1, up to N m.
47:11
47:16
So for m equals 2, which is my picture, it's N 0 plus N 1
47:28
plus N 2, and what are these?
47:32
What does that N 2 mean, for example?
47:37
That's a binomial number.
47:41
I don't know if you're keen on binomial numbers.
47:45
Some people, their whole lives go into binomial numbers.
47:50
So it's something like--
47:53
is it N factorial divided by N minus 2 factorial and 2
48:00
factorial?
48:01
48:05
I think that's what that number means.
48:08
That's the binomial number.
48:09
48:12
So at this point, I'm hoping to get the answer seven, I think.
48:17
48:22
I'm in m equal to--
48:25
I've gone up to 2.
48:27
Yeah, so I think I've obviously allowed for three cuts,
48:36
and the r, when we had just three, was 7.
48:41
48:46
So this is now I'm taking N to be 3,
48:49
and I'm hoping for answer is 7.
48:56
49:01
So I add these three things.
49:03
So what is 3, the binomial number 3 with 2?
49:08
I've forgotten how to say that.
49:10
I'm ashamed to admit.
49:11
3 choose 2, thanks.
49:13
I knew there was a good way.
49:14
So what is 3 choose 2?
49:15
49:18
Well, put in 3, and 2 is in there already,
49:23
so that'd be 6 over 1 times 2.
49:28
This would be 3.
49:29
Would that be 3?
49:30
49:35
And what is 3 choose 1?
49:39
AUDIENCE: 3.
49:41
GILBERT STRANG: How do you know that?
49:42
You're probably right.
49:45
3, I think, yeah.
49:48
Oh yeah, probably a theorem that if these add 3.
49:52
Yeah, so I'm doing N equals 3 here.
49:55
OK.
49:55
So yeah, I agree.
49:57
That's 3, and what about N to 0?
50:01
That you have to live with 0 factorial,
50:05
but 0 factorial is by no means 0.
50:10
So what is 0 factorial?
50:13
1, yeah.
50:17
I remember when I was an undergraduate having
50:19
a bet on that.
50:20
50:24
I won, but he didn't pay off.
50:29
Yeah, so it's 3.
50:31
This is 3 factorial over 3 factorial times 0 factorial.
50:35
So it's 6 over 6 times 1.
50:37
So it's 1.
50:38
Yeah, 1 and 3 and 3 make 7.
50:41
So that proves the formula.
50:44
Well, it doesn't quite prove the formula,
50:46
but the way to prove it is by an induction.
50:51
If you like this stuff, the recursion that you use
51:00
induction on.
51:01
Which is just what we did now, what we did here.
51:04
Here comes in a number 4, and it cuts through,
51:11
and then we just counted the 4 pieces there.
51:14
So yeah, so let me just tell you what the r then and m.
51:23
The number we're looking for is the number
51:26
that we had with one less cut.
51:30
So that's the previous count of flat pieces
51:35
plus the number that was here was 4, the number of pieces
51:43
that cut that.
51:44
And that's r of N minus 1, m minus 1.
51:52
Yeah, and I won't go further.
51:57
Time's up, but that rule for recursion
52:02
is proved in the section 7.1 taken from the paper
52:08
by Kleinberg and others.
52:11
Yeah.
52:11
So OK, I think this is--
52:14
I don't know what you feel.
52:16
For me, this like gave me a better feeling
52:20
that I was understanding what kind of functions we had here.
52:25
And so then the question is--
52:30
52:33
with this family of functions, we
52:35
want to choose the A's and the weights, the A's and b's,
52:45
to match the training data.
52:50
So that we have a problem in minimizing the total loss,
52:56
and we have a gradient descent problem.
53:00
So we have to find the gradient, so that Wednesday's job.
53:04
Wednesday's job is to find the gradient of F,
53:09
and that's back propagation.
53:11
Good.
53:11
Thank you very much.
53:14
7.1 is done.
English - CC (English)
###