Lecture 19.1: Neural Network Computation - Model Class, Loss, and Regularization
Recording. Download the text transcript.
Automatic transcript; technical terms and equations may contain recognition errors.
00:00:00 We're gonna start talking about
00:00:08 neural network computation and then RNNs.
00:00:12 So I think we have spent enough time talking about
00:00:15 artificial neural networks as well as
00:00:18 convolutional neural networks.
00:00:20 We talked about a lot of details
00:00:23 for this kind of grid data or image data.
00:00:27 And I think through this process,
00:00:29 we have already noticed a lot of things
00:00:32 that we need to understand the details even more,
00:00:35 including how it's done computationally.
00:00:38 So we mentioned back propagation a lot of times,
00:00:42 but I think it's very important to really understand them.
00:00:46 And then starting on Thursday,
00:00:49 we'll start talking about sequence data or text data,
00:00:53 and the corresponding architecture
00:00:56 that is a recurrent neural networks.
00:00:58 I think we should include the language models next week,
00:01:01 because that's sort of the state of the art.
00:01:04 And we'll include some case studies.
00:01:07 Okay?
00:01:09 Okay, so what do we have learned last week?
00:01:12 We talked about image data that is very special, right?
00:01:18 2D, 3D grids of pixels,
00:01:20 and there is a very structured information.
00:01:22 So apparently using MLP is not utilizing the structure,
00:01:30 and it's also a very expensive process, right?
00:01:34 So what we learned was that we want to kind of reduce
00:01:37 or regularize the model, right?
00:01:41 But we don't have ideas that just come from nowhere.
00:01:44 The ideas actually came from how our vision systems work, right?
00:01:51 And we have learned about the locality.
00:01:54 We learned about the equivalence of our vision systems.
00:02:00 Then we decided that, you know,
00:02:02 these are the knowledge that can drive this model reduction
00:02:06 relative to MLP, such as sparse interactions,
00:02:10 parameter sharing, and equivalence to translations.
00:02:14 Motivated by these desired properties,
00:02:18 we introduce the corresponding math mathematical operators,
00:02:24 such as convolutions.
00:02:25 We spend a lot of time talking about the fact that
00:02:29 convolution actually cater to these desired properties,
00:02:34 and actually it's much smarter than it appears, right?
00:02:38 Remember how the receptive,
00:02:40 how wide the receptive field can become
00:02:43 when you increase the depths of the intermediate layers, right?
00:02:49 We talked about the channels,
00:02:52 how it can be very easily incorporated
00:02:55 into the tensor calculations.
00:02:57 We talked about the pooling.
00:02:59 It's very similar to convolutions, right?
00:03:02 It's local, but it's parameter-free, right?
00:03:06 We talked about strides that can, you know,
00:03:10 control the resolution, right?
00:03:12 Pooling that can control the image size, right?
00:03:16 And then padding that can maintain that image size
00:03:20 from one layer to the next layers.
00:03:24 We talked about how much computations can be saved
00:03:27 using one concrete examples, right?
00:03:31 Using convolutions versus using MLPs.
00:03:34 Those are examples we have talked about.
00:03:37 We also talked about what else can be done
00:03:39 ever since convolutional neural networks
00:03:42 or, you know, the net, right?
00:03:45 Or AlexNet later on.
00:03:47 We have seen how the later models for computer vision
00:03:53 have been developed.
00:03:54 We have some summaries about, like,
00:03:56 you know, GoogleNet or VGG,
00:03:58 and what are their contributions or resonant, right?
00:04:03 So now I think it's time to talk about the computations
00:04:07 and a little bit of theory behind these neural networks,
00:04:12 right, in general, not just convolution,
00:04:14 but neural networks in general.
00:04:17 So a little bit of background, right?
00:04:20 So remember we talked about, at the beginning,
00:04:22 logistic linear regression or, you know,
00:04:25 other kind of simple neural networks, right?
00:04:29 We said that you can look at them from the perspective
00:04:32 of optimization, right?
00:04:34 So you first have the data, right?
00:04:37 The IO relationships, right?
00:04:39 And the examples of IO relationships.
00:04:42 And then you have the model, right?
00:04:44 This model class is defined by, you know,
00:04:47 MLP or CNN or other kind, right?
00:04:50 More general than the linear classifier you have seen
00:04:53 in the shallow machine learning models.
00:04:55 So once the data and the models are determined,
00:04:58 training the model is equal to solving
00:05:02 an optimization problem,
00:05:04 where the decision variables are model parameters, right?
00:05:09 And the objective function or the cost function
00:05:12 is a loss plus the regularization, right?
00:05:16 And the optimization algorithm,
00:05:18 or the optimizer is to find the optimal parameters, right?
00:05:23 And I can give you the conclusion
00:05:25 that they are dominated by gradient-based methods.
00:05:28 We introduced the classical gradient-based methods before,
00:05:32 right, a lot of, you know, gradient descent,
00:05:34 conjugate gradient, Newton, quasi-Newton, you know,
00:05:39 and, you know, limited memory BFGS, right?
00:05:44 But we'll see how they should be changed or evolved
00:05:49 in the case of big data, right?
00:05:51 So now, first of all, I want to ask you the question, right?
00:05:56 Why do you think that the deep neural networks
00:05:59 or MLP would work, right?
00:06:02 Let's talk about the model class, right?
00:06:04 You think that your model class is adequate
00:06:07 for the problems at hand.
00:06:09 So how do you get that belief?
00:06:11 So it comes from theory.
00:06:13 So there are two approximation theorems
00:06:17 for you to understand, right?
00:06:20 So the first series of papers, 1989,
00:06:25 state the following universal approximation theorem,
00:06:28 which says that a feedforward network
00:06:32 with a linear output layer
00:06:34 and at least one hidden layer
00:06:37 with any squashing activation function,
00:06:40 such as the logistic sigmoid that you have seen before,
00:06:43 such feedforward network
00:06:45 can approximate any Borel measurable function,
00:06:49 by Borel measurable, I mean any continuous function
00:06:53 on a closed and bounded subset
00:06:55 of n-dimensional real space, okay?
00:06:58 So a feedforward network like that
00:07:02 can approximate any Borel measurable function
00:07:05 from one finite dimensional space to another, okay?
00:07:09 With any desired non-zero amount of error.
00:07:13 So, right, that's the conclusion.
00:07:15 The condition is that to have that property
00:07:21 is that provided that the network
00:07:22 is given enough hidden units.
00:07:26 Okay, so this is what
00:07:27 the universal approximation theorem says, right?
00:07:30 So it's about what kind of feedforward network
00:07:35 can approximate what kind of function
00:07:39 to the zeroes order, right?
00:07:42 That's the conclusion.
00:07:44 And there's another version actually
00:07:46 that can also talk about the first order information,
00:07:50 that is the derivatives of the feedforward network
00:07:53 can also approximate the derivatives
00:07:56 of the function arbitrarily well.
00:07:58 That is the 1990 result.
00:08:02 So these theoretical results, you know,
00:08:05 for the zeroes order and the first order approximability,
00:08:10 shows that if you have a large MLP,
00:08:14 they can represent the function of interest.
00:08:17 You have to pay attention, okay?
00:08:18 Because this is a universal approximation theorem,
00:08:21 which says that the MLP model is a model class
00:08:26 that can represent the function of interest,
00:08:29 like the Borel measurable function, right?
00:08:32 It doesn't mean that, you know,
00:08:35 you can train an LP and learn the function of interest precisely.
00:08:41 I didn't say that, right?
00:08:44 Right?
00:08:44 Because in the end, it determined by the data
00:08:48 and the training algorithm, right?
00:08:50 It's algorithm that learned the function, right?
00:08:52 The model class is, you know,
00:08:54 covering or representing the function of interest,
00:08:57 but in the end, you need to learn the function
00:08:59 and, you know, the optimizer have to operate
00:09:03 on the loss function, minimize the loss function,
00:09:07 given the data.
00:09:08 And you have to consider, for instance,
00:09:11 if there is a lack of convergence or kind of overfitting,
00:09:15 then even though the model class is general enough
00:09:18 to cover the function of interest,
00:09:21 you may still not able to learn that function
00:09:25 with your MLP, right?
00:09:27 So that's something you have to pay attention to.
00:09:29 One is representing and one is learning.
00:09:33 So let's understand the universal approximator theorem
00:09:38 a little bit more, right?
00:09:40 And let's say, you know, one hidden layer
00:09:44 is enough to represent, okay, not learn,
00:09:49 an approximation of any function
00:09:51 to an arbitrary degree of freedom, right?
00:09:53 So, you know, because the, remember,
00:09:57 the condition is that as long as there are
00:09:59 enough hidden units, right?
00:10:01 So then if I have one hidden layer,
00:10:03 and then if I have many neurons in the hidden layer,
00:10:07 that's called the width, then that's enough, right?
00:10:10 But you have learned much better than that is
00:10:13 deep neural network is really about the depths, right?
00:10:18 Right?
00:10:19 Right?
00:10:20 The magic come from the depths.
00:10:22 So if you can, you know, have the same amount of hidden neurons
00:10:26 using one or multiple layers, hidden layers,
00:10:31 why do you prefer going with a deeper neural network
00:10:40 or more hidden layers?
00:10:42 Apparently I wrote something, but what is your understanding?
00:10:46 What's the big deal about the depths?
00:10:49 Anya?
00:10:51 Anya try?
00:10:55 Pardon me?
00:10:59 Is it for learning?
00:11:01 Pardon me?
00:11:02 Is it for learning because like,
00:11:04 it just represents what I'm not sure?
00:11:08 I'm not sure.
00:11:09 Okay, good point.
00:11:10 You are saying that maybe it's same amount of representability,
00:11:14 but it's easier for learning.
00:11:16 Is that right?
00:11:17 That is a good point.
00:11:19 I think, is it easier for learning?
00:11:34 I'd say the depths actually brought in more challenge to optimization.
00:11:43 But could it be still benefiting learning in some way?
00:11:49 That's a good point.
00:11:51 Let me think about it a little bit more.
00:11:53 And my argument is that I think you're looking at the right perspective.
00:11:58 You're looking at the representation and the learning, right?
00:12:02 But you seem to have assumed that, you know,
00:12:05 as long as there are the same amount of hidden neurons,
00:12:10 then there is the same level of representability or expressiveness of these two MLPs.
00:12:17 In fact, that's not the case that you can get more, a better representation.
00:12:27 Okay, let me put it in this way, okay?
00:12:31 These theoretical results are like the convergence proof that we have seen before,
00:12:36 which is an asymptotic result, saying that when the samples go to infinity or when,
00:12:44 you know, the number of hidden layers is large enough, right?
00:12:48 So in reality, of course, we don't always have, we never have that.
00:12:52 We always have, you know, a small or, you know, medium finite number of the hidden units, right?
00:13:00 So I'd like to put in this way that, you know, the width and the depths affect the expressiveness of the model differently, right?
00:13:16 One is like, you know, in the base and one is like in the exponential term, if you get what I mean.
00:13:23 Okay, I will show you with illustration next page, okay?
00:13:28 But a simple, you know, a simple quick points are first, right?
00:13:39 If you have a shallow network, then you need more width, more neurons.
00:13:44 But, you know, to compensate a loss of a layer, you have to use exponentially more width.
00:13:52 In other words, width and the depths affect the expressiveness of the model differently, okay?
00:13:58 And you will see right away why depth is more or less exponential term,
00:14:02 because you are composing, you know, layers after layers.
00:14:06 We'll see that, you know, intuitively.
00:14:07 Next slide.
00:14:10 And secondly, the shallow network may overfit more, okay?
00:14:16 So does anyone have any doubt about my second claim?
00:14:25 So please don't take this as conclusions, right?
00:14:28 I know some people say that tuning machine learning or especially deep learning models during training sometimes,
00:14:36 you know, is very empirical recipe-based, but here I think we do have very deep theoretical reasons, okay?
00:14:44 We'll talk about overfitting in a few slides, but let me show you this deeper network, right?
00:14:54 The exponential representation advantage of depths, right?
00:14:59 So now let's look at a very concrete example.
00:15:02 This is like a, you know, two-dimensional space where we have blue versus red samples, right?
00:15:12 Our goal is to design a classifier that can separate the two, right?
00:15:17 So apparently, well, for some reason, let me see if I use it, show it as smaller, interesting.
00:15:29 So it appears that, you know, I just copied a figure, but something in the figure is missing.
00:15:42 So let me see whether I can draw in the figure.
00:15:45 Okay, so let me see whether I can draw in the figure, okay?
00:15:50 So apparently the ideal classifier, right, is something like, okay?
00:16:04 Right?
00:16:05 Right?
00:16:06 So this is, you know, in the original domain, right?
00:16:09 So let's, you know, so this is, you know, it's, you know, in this case, right?
00:16:15 So this is, you know, decision boundary in the two-dimensional space, right?
00:16:20 So now let's see what the depths can do to you.
00:16:24 It's like folding, right?
00:16:26 Remember, I said before, the key of deep neural works, right, using so many linear layers,
00:16:33 followed by activation, and composing the linear layers, is really to decompose a high-dimensional manifold, right,
00:16:43 into piecewise flat facet, right?
00:16:48 Right?
00:16:49 The key is really like, you know, the reason is that when you compose layers after layers,
00:16:54 it's like you're folding this paper or, you know, doing this piecewise approximation.
00:16:59 So now imagine that, right?
00:17:03 So now imagine that, you know, when I try to get this function, right?
00:17:10 You know, this is the function that I want to learn, represent and learn, right?
00:17:15 So apparently, you know, you can see that these, I want to learn this sophisticated function, right,
00:17:25 by aggregating or composing simple functions.
00:17:30 So one thing I notice is that, you know, this function, for instance, is like a symmetric, right, along, you know, this axis.
00:17:38 So if I fold my paper along this, you know, symmetry axis to the right, so this is where I fold, right,
00:17:48 then you realize that in this new space, in this new space, I just have to learn this simpler function.
00:17:56 Right?
00:17:57 So this function can be obtained by folding the space around the axis of symmetry, right?
00:18:03 And then I observe a local symmetry here again, so then I fold again, you know, to the left, right, along this axis of symmetry,
00:18:17 and then I end up having this, right?
00:18:20 And then in the end, if I keep folding, right, I have a way simpler function, right?
00:18:28 So remember, by folding the papers, what I'm doing is actually trying to see how sequential folding, right, right,
00:18:41 can reduce a complex function into a very simple function in one, you know, in this final fold.
00:18:52 If I go backward, it's equal or equivalent to ask, how can I start with a simple function, right, like represented by a layer, right?
00:19:03 MLP, I'm sorry, single layer perceptron followed by activation function nonlinear, right?
00:19:09 So you can think of this function as a single layer function.
00:19:14 Then, if I keep, right, you know, if I keep composing additional layers, then in the paper, it's like, you know, I'm, you know, expanding to these more and more complicated functions, right?
00:19:32 So this shows the power of the depth because the depth is the number of times you fold.
00:19:40 And then apparently, right, if you look at here, we fold one, two, two times, then we are basically having approximation of a function with kind of one global and another local symmetry.
00:19:58 So this kind of complexity, but if we keep folding, right, then we see that that is something like the exponential, right, two to the power of the depths that we can cover the complexity.
00:20:14 So this shows this exponential representation advantage of the depths, right?
00:20:20 Any question about this visualization? Is it clear to you?
00:20:25 The relationship between paper folding and composing linear, not necessarily linear, but composing the hidden layers.
00:20:36 Okay, so this is about a model class, why we believe that DNN, especially MLP, can approximate, right, and then why the depths matter, right?
00:20:49 And about the second claim I had that, you know, with greater depths, you have a better generalization, right?
00:20:59 So this is some figures that, you know, looking at the test accuracy versus the layers, right?
00:21:14 So, you know, if we look at the other end that are large but shallow models, right?
00:21:24 So if we look at this one, right, so let's look at the number of parameters versus the test accuracy, right?
00:21:31 So this is post hoc assessed.
00:21:34 So we have the fully connected MLP, right?
00:21:39 That is three layer, right?
00:21:41 So they tend to have a lot of parameters, right?
00:21:44 So more to the right.
00:21:46 Then for the same depths, three layer convolutional neural networks, we have much less parameters, right, compared to the green.
00:21:56 Now with roughly the same number of parameters, we can afford having much deeper convolutional neural networks because convolutional neural networks have sparse interactions and parameter sharing, right?
00:22:10 So if you look at the outcome of the test accuracy, right?
00:22:15 So of course, this is something that you don't know a priori, right?
00:22:18 This is like the, you know, bias-variance trade-off that you observe in the post hoc assessment.
00:22:29 But to find the sweet spot, right, you have to use cross-validation, right?
00:22:33 So here you see that apparently, you know, the shallow convolutional neural networks compared to the deep convolutional neural networks, you see their performance difference, right?
00:22:46 And the large shallow models, you know, tend to overfit, right?
00:22:54 Right?
00:22:56 So besides the model class, right, the second thing we should look at from the perspective of optimization is the loss function, right?
00:23:10 So the loss function we have learned a lot before.
00:23:13 For instance, we learned we can maximize the log likelihood, right?
00:23:19 And we can, you know, maximize or minimize the mean squared error, right?
00:23:26 Depending on what kind of task, right?
00:23:28 Here I want to talk about, you know, the choice of the loss function, right?
00:23:35 Tied to the kind of the predictions you want to make and the desired output distribution and the choice of the output layer, okay?
00:23:46 So for instance, if you are trying to model a Bernoulli distribution, that basically the output is binary, right?
00:23:54 Zero or one, right?
00:23:56 And in the output layer, we usually use a softmax, right?
00:24:02 Right?
00:24:03 Which is, you know, giving the probability of p and one minus p for the two classes.
00:24:11 And the cost function you usually use is a binary cross entropy, right?
00:24:15 Remember this question I asked before, right?
00:24:18 And, you know, essentially is a minus log likelihood, right?
00:24:24 In the case of the multiple classes, it's a, you know, not Bernoulli but multi-newly distribution, right?
00:24:32 So your output is not like binary but multiple discrete choices.
00:24:37 But then you have a softmax again, right?
00:24:39 And then in this case, you have the generalized cross entropy.
00:24:43 That's not for binary but for the general cases, okay?
00:24:46 So now if your labels or the output type is continuous, right?
00:24:52 And the distribution is kind of like a Gaussian, right?
00:24:56 And your output linear, output layer is linear, right?
00:25:00 Then you can prove that this, you know, cross entropy, in this case, a Gaussian cross entropy is essentially the, you know, mean squared error, right?
00:25:12 That you usually use.
00:25:14 But if the continuous output has a desired distribution, which is like a mixture of Gaussian, right?
00:25:23 So the output layer is giving you the mixture density, then the cost function is cross entropy again, right?
00:25:30 And then if you have other kind of assumptions, right?
00:25:34 You know, including the output distribution, and you have different kind of output layer, then your cost function will be, you know, dependent on the choices.
00:25:46 The cost functions are very different, right?
00:25:48 So if you want to look into more details, you can look into the deep learning book whose electronic version is available online, right?
00:25:57 So it's in the chapter six, right?
00:26:00 So I think you should be, some of you should know, right, what is the cost function in generative adversarial networks.
00:26:10 Anyone?
00:26:11 What is the cost function?
00:26:20 Okay, we'll talk about them again in the close to the final weeks, okay?
00:26:27 But I think you should know about them.
00:26:29 But one thing I want to emphasize here is that you haven't learned a lot of isolated knowledge points.
00:26:37 I'm pretty sure.
00:26:39 But here I hope that I can thread them together in a systematic way so that, you know, you can see those seemingly disparate or isolated knowledge points better.
00:26:55 In other words, understanding them better, okay?
00:26:58 So here, for instance, if you think about the choice of the cost function, together with the output layer and the output distribution, output type, you have a much better understanding than just, you know, trying to accept them as they are.
00:27:15 Okay.
00:27:16 Okay, so then in the last function, remember, we talked about the regularization before, right?
00:27:25 So in the shallow machine learning model, we try to, you know, have a, you know, better generalization error.
00:27:33 And one way to achieve that, according to the bias-variance trade-off, is to sacrifice the bias a little bit by making your model less complex.
00:27:51 And the hope is that the variance part gets reduced much more.
00:27:56 So the sum, right, gets lower.
00:28:00 That's for the generalization error.
00:28:02 So that effort is called a regularization, right?
00:28:06 So how you regularize your model complexity, we said before, model complexity cannot be easily estimated just by the number of parameters alone, because it's, you know, data dependent, right?
00:28:18 One way is actually to use the LP regularization, that is to use the LP norm of the, you know, parameter weight vector, right?
00:28:31 And you see that by regularizing the length or the size of the parameter weight vector, you can regularize the model complexity, right?
00:28:43 So in neural networks, you can still include L1, L2, or LP norm, right?
00:28:51 In your loss function, that you can still do that.
00:28:54 But you can do more than that.
00:28:57 Why?
00:28:58 Because your parameters W, right, are now structured.
00:29:05 What do I mean?
00:29:07 You have some Ws belonging to the first hidden layer.
00:29:13 You have some parameters belonging to the second hidden layer, and so on, right?
00:29:19 So this, you know, some parameters belong to this, you know, linear, the W, some belong to the activation function.
00:29:27 So in other words, your parameters are very structured, so you can actually use additional regularization approaches, right?
00:29:36 Besides simply L1 norm.
00:29:38 One way is drop out, right?
00:29:42 Because the parameters, you know, in our cases, are very often related or associated with the interconnections between the neighboring layers neurons, right?
00:29:55 So if we can reduce such interactions, then we can reduce the number of parameters, right?
00:30:03 So the drop out is basically, sometimes we call it a drop out layer after the fully connected.
00:30:09 That is, you will remove some percentage of random nodes at each training iteration.
00:30:16 And, you know, this is random, okay?
00:30:20 So you are dropping out some percentage of random nodes, and of course, their associated interactions and the parameters, WIs.
00:30:29 This is random, okay?
00:30:32 And this is done at each training iteration.
00:30:35 The nature of this method is actually, you know, essentially equivalent to an ensemble method that can reduce the variance.
00:30:47 Okay, so that's why drop out would work.
00:30:51 Another thing is, when you're doing the training, you can do early stopping, right?
00:30:56 So you can save checkpoints during the training and choose the best according to the validation instead of choosing the, you know, the last or the ones, you know, close to the saturation or convergent.
00:31:09 This early stopping can also prevent you from overfitting, right?
00:31:16 And lastly, you can always, you can always try to provide more data.
00:31:23 So we talked about bootstrapping, right?
00:31:27 The approach of bootstrapping in the case of shallow models, right?
00:31:32 In the deep models, you can do more partly because we are not telling some properties of the desired functions directly to the neural network model class.
00:31:49 For instance, for instance, in computer vision, we know that, you know, for the object detection, right?
00:31:57 Or labeling of the image, these pixels belong to the cat, right?
00:32:03 We don't care about where they are, right?
00:32:06 Whether they are rotated, translated, or rescaled, right?
00:32:11 The label would remain the same, right?
00:32:16 But our convolutional neural networks is only equivalent to the translation, right?
00:32:27 Because, you know, we are using the CNNs, which are like local filters that are glanced through, right?
00:32:36 But it's not invariant to the rotations or scaling.
00:32:43 So in computer vision, it becomes a must that if you have an image, right, you have to randomly rotate them in multiple copies
00:32:55 and give all of them to the model training.
00:32:59 This is a way to tell, you know, the model that, you know, this model should be relatively invariant to the rotations, but it's a very indirect way, right?
00:33:13 So this is called a data augmentation.
00:33:16 So there's no general recipe.
00:33:19 It's a way to try to mimic the real-world variations, okay?
00:33:24 So these are the loss function, right?
00:33:29 About what kind of loss function and what kind of regularization we really have to choose.
00:33:33 So this is the loss function, right?