Lecture 19.2: Neural Network Computation - Optimization
Recording. Download the text transcript.
Automatic transcript; technical terms and equations may contain recognition errors.
00:00:00 Now we are ready to talk about the optimizer. As I said, these optimizers are heavily gradient-based. As a reminder, these are iterative starting from x0 and we generate a sequence x sub k where k goes from 1 to K.
00:00:17 And these updates are usually deterministic, right? Pre-fabricated update rules. And they are more used for local optimization as the gradients only carry very local information and not to mention that we have the curse of the dimensionality, right? Our number of parameters is very high even for convolutional neural networks, right? Not to mention about other kind of networks.
00:00:47 So back in the protein structure prediction, we used the gradient-based algorithm to do the local optimization like remove clashes or bad geometries and so on, right? Which are like the high frequency terms that dominate the local scale, right?
00:01:02 But in this case, you know, let's see how it needs to be done, okay? So I want to introduce a concept called computation graph, okay?
00:01:14 I want you to again understand, you know, of course, you understand already to some extent that the math behind the illustration.
00:01:28 But I also want you to be aware of the mathematical operation behind this illustration. So that's called a computational graph.
00:01:37 For instance, we have a very simple forward propagation with just one hidden layer, right?
00:01:45 And this is the expression, mathematical expression, right?
00:01:50 And we have, you know,
00:01:55 W1 times X, that gives us a Z, right? And Z has a
00:02:01 nonlinear transformation.
00:02:02 And then it's fed to
00:02:04 the next hidden layer.
00:02:08 And then it's getting the readout of O, and we may do some softmax or other kind of operations to get the final label, right?
00:02:18 Estimated label.
00:02:20 And for
00:02:21 each point, we have a loss function comparing, right?
00:02:26 Comparing the predicted and actual labels. And then we may have some regularization terms, right?
00:02:32 If you try to put all these mathematical operations in the model class and
00:02:40 eventually calculating the loss, right, together into a graph, you get such computational graph.
00:02:47 Why do you care about such computational graph? Keep in mind that here my goal is to figure out
00:02:55 how to train this model. In other words, how to find the optimal W that can minimize the J,
00:03:04 right? I need to see
00:03:07 forwardly
00:03:08 how X
00:03:11 all the way propagates forwardly to J.
00:03:14 This is called the forward propagation. So in this process,
00:03:19 sometimes I have a multiplication, right?
00:03:22 Right? Sometimes I have other kind of operations, right? Sum and so on.
00:03:28 So this gives us the computational graph for the forward propagation from input X to the cost function J, right?
00:03:38 Right?
00:03:40 And keep in mind that to minimize J and find out the optimal corresponding X and the W star, excuse me,
00:03:51 right? Because, you know, X and Y's are given data, right? W's are the parameters we need to
00:03:58 train. These are the decision variables, right?
00:04:00 So to calculate the gradient, right? We actually have to, you know, use something that's called back propagation, right?
00:04:11 I said before that,
00:04:15 you know, this was something that
00:04:18 So that's something that has prevented, you know, the multi-layer perceptrons to be,
00:04:28 to reach its potential, largely because back then people don't know exactly how to effectively train or optimize for such multi-layer parameters, okay?
00:04:38 So if you want to calculate the gradient, right?
00:04:43 As you can see, right?
00:04:45 This, you know, J depends on the O, right?
00:04:50 And O depends on the Z and then Z depends on X, right?
00:04:56 So you can use the change rule to calculate the gradient, right?
00:05:01 So DJ, DW, for instance, equal to, you know,
00:05:08 excuse me, in this case, right?
00:05:11 So DJ, DO first, right?
00:05:14 And then you have the, you know, DO, DW2 and you keep going backwards, right?
00:05:19 So you can use the change rule, right?
00:05:22 But it's more complicated than just the change rule itself.
00:05:27 Again, because this is not a general class of, you know, parameters.
00:05:35 But our parameters are structured.
00:05:38 Remember, our parameters correspond to different layers.
00:05:41 And sometimes we have the repeated quantities, okay?
00:05:45 So it's a particular implementation of the change rule because it uses dynamic programming and reusing some quantities and filling the table.
00:05:56 And it will avoid recomputation of the repeated sub-expressions.
00:06:03 And it, you know, achieves some trade-off between the speed and memory.
00:06:06 So it's way more than just change rule, okay?
00:06:10 It's utilizing the special structure.
00:06:12 So let's try to see a simple example, a backpropagation, okay?
00:06:20 So we said before that, this is a very simple one-dimensional, I'm sorry, one hidden layer, right?
00:06:27 We said before that there is a forward propagation, right, from x to y to the loss, right?
00:06:34 But there is always a backward propagation using the change rule to figure out the gradient of DJ, DW, right?
00:06:41 So these are the two directions, forward propagation and the backpropagation.
00:06:47 The backpropagation is to compute the derivatives, okay?
00:06:54 All right, so let's see.
00:06:57 Let's look at the computational graphs again.
00:07:00 I introduced previously that, for instance, if you have the multiplication or you have the dot product or sum or some kind of sigma activation, right,
00:07:09 you can sort of express them in such a computational graph, right?
00:07:14 See, I think compared to the previous computational graph, for simplicity, I put these operations in these next to the arrows
00:07:24 instead of using a separate node to express them, right?
00:07:29 So this is what the ReLU does, right?
00:07:32 And this is what linear regression and weight decade does, right?
00:07:38 So this is a computation graphs for the forward propagation, right?
00:07:43 A few simple examples.
00:07:47 So now let's look at the change rule.
00:07:50 Let's look at the change rule, right?
00:07:53 So essentially, we have, forwardly, we have, you know, W,
00:08:00 so let's look at this expression, okay?
00:08:04 So let's look at
00:08:08 this example, right?
00:08:09 Let's say W to X to Y to Z, right?
00:08:13 So you can easily write this change rule, right?
00:08:17 Calculating the partial derivative, so
00:08:20 Z to Y and then Y to X and X to W, right?
00:08:25 And then you notice that,
00:08:27 you know, I can replace, in this case, I can, you know, replace some of them
00:08:36 because some expressions or sub-expressions are repeated.
00:08:41 For instance, to calculate these gradients, partial derivatives, with regard to X,
00:08:49 X, I would have to use FW, right?
00:08:54 I would have to use it, right?
00:08:57 And then for this one, I would have to use FW as well, right?
00:09:02 Right?
00:09:03 Right?
00:09:03 So these can be repeatedly used, right?
00:09:08 Without recomputing.
00:09:09 So you can, you know, store them in a table and access them, right?
00:09:18 So now let's look at the symbol to symbol differentiation, right?
00:09:22 So let's now try to make it more clearly, right?
00:09:26 Using this illustration.
00:09:27 Again, we have this linear forward propagation, right?
00:09:32 Sorry, not linear, forward propagation.
00:09:34 And to calculate the gradient, remember, right?
00:09:38 Apparently, we can calculate dz dy, and then we need to multiply, you know, dz dy to, you know, dy dx, right?
00:09:52 And then that give us, you know, dz dx, right?
00:09:55 And then we need to multiply that to dx dw, and then that eventually give us dz dw, right?
00:10:03 Right?
00:10:03 So that's what we want, right?
00:10:05 So this is what we want, right?
00:10:11 So now let's look at backward, back propagation again in this example, right?
00:10:18 Again, this is, you know, one hidden layer, right?
00:10:21 So previously, I used a very abstract suggestions, right?
00:10:26 This example is just going from w to x to y to z.
00:10:30 But now let's look at a very specific neural network, right?
00:10:34 Where we have one hidden layer, right?
00:10:37 Where z equal to w x and h is a nonlinear activated z.
00:10:43 And then h is multiplied to w2 to get the output o, right?
00:10:50 And the last function is a comparison between the predicted o and the actual y.
00:10:55 And then we're going to add some regularization term s to get the j, okay?
00:11:02 So apparently, what we are interested in is this all sort of kind of partial derivatives,
00:11:09 like j with regard to w2, and then j with regard to w1.
00:11:15 That's our goal, right?
00:11:16 Because we are trying to adjust w1 and w2 to minimize j.
00:11:22 So we need to find the gradient of j with regard to w1 and w2, okay?
00:11:28 So now let's keep in mind that in our case, we know the relationship, right?
00:11:34 Forwardly, how these propagate from w to o to j, right?
00:11:40 So now let's apply this special case to our previous general expressions and see how it works, right?
00:11:50 So apparently, you know, you can get the partial derivative of j with regard to o, right?
00:11:56 And that's, you know, the product of this two.
00:11:59 So that's the regularization term, right?
00:12:11 And that is just, you know, lambda times w1 because w1 is quadratic, right?
00:12:21 And then the regularization term with regard to w2 is also lambda times w2,
00:12:26 because again, we are using the l2 norm here, okay?
00:12:30 So l2 norm makes it differentiable, that's good.
00:12:33 If it's l1 norm, then it's probably getting more complicated because it's not differentiable everywhere, right?
00:12:41 So that's just the s part with regard to w1 and w2, okay?
00:12:46 The more difficult part is l part, so that we need to pay attention to, right?
00:12:52 So the l part is, again, you know, j with regard to o and times o with regard to w2, right?
00:13:06 And what is the derivative of o with regard to w2?
00:13:11 Let's look at this one, right?
00:13:13 It's just h transposed, right?
00:13:15 So we have h transposed times the j with regard to o, right?
00:13:20 That's what we have here.
00:13:22 And the second term is the gradient for partial derivative for s,
00:13:26 and that is lambda times w2, which is copied here, okay?
00:13:31 So this is relatively simple because this is the last hidden layer, w2, okay?
00:13:40 Now let's look at w1, right?
00:13:42 It's a little bit more complicated, but it's not that difficult, right?
00:13:46 So we can similarly calculate a j with regard to h, right?
00:13:53 By multiplying these two partial derivatives, right?
00:13:57 Again, one is j to o with regard to o, and the o with regard to h is, again, just a w2,
00:14:06 is just a w2 transposed, okay?
00:14:10 So that's what we have here as a product.
00:14:17 But then you have, you know, let's see, j to z, right?
00:14:24 So j to z, right?
00:14:25 So we can reuse j with regard to h, right?
00:14:29 We can, you know, multiply, keep propagating backwards, right?
00:14:33 So j with regard to h, but now let's go one upstream back to, closer to the input to figure out
00:14:42 j with regard to z, right?
00:14:44 Remember, the relationship between h and z is defined by this function.
00:14:49 So I just need to multiply, right?
00:14:53 I just, you know, need to do this product.
00:14:56 But be careful here, this is a different kind of product here, okay?
00:15:01 And lastly, I have to go all the way back to w1, right?
00:15:07 But I can reuse the partial derivative of j with regard to z,
00:15:14 and times z with regard to w1.
00:15:18 And z with regard to w1 is very simple.
00:15:21 It's just x transposed, right?
00:15:23 x transposed.
00:15:25 Then the second term is about the regularization term, right?
00:15:28 I have j with regard to s, and s with regard to w1.
00:15:34 So s with regard to w1 is already known, lambda times w1.
00:15:39 Then you also have j with regard to s.
00:15:42 That's just a one, right?
00:15:44 So you multiply them together.
00:15:45 And that's eventually what you have here, right?
00:15:48 So as you can see that, you know, essentially, just like the name suggests, right,
00:15:54 you're really backpropagating the gradients using the change rule.
00:15:59 But what backpropagation is good at is utilizing the structure of the parameters.
00:16:05 And it's, you know, balancing the CPU and memory in an efficient way.
00:16:10 Sometimes they reuse terms without recomputing them.
00:16:14 And there are some more details about dynamic programming.
00:16:17 So I'm not talking about here, okay?
00:16:20 So I have two exercises to you after the lectures.
00:16:25 If you to show, to see whether you really understood these concepts, right?
00:16:29 First, I would ask you to draw the computation graph for an LP with just one hidden layer, okay?
00:16:35 So it should be a very simple example.
00:16:38 The second one is can you implement the forward and backward propagation for this MLP, right,
00:16:49 with numerical Python only?
00:16:52 So in fact, I think the second practice should be one of the golden standards to test whether you
00:17:03 really understood what backpropagation means, okay?
00:17:06 Okay, and the answer lies in this block, okay?
00:17:12 Okay, by the way, I was at a conference in San Francisco, and I went across a UC Berkeley student
00:17:21 who's in, I think, in medical school.
00:17:25 So they were having some kind of machine learning course, and this is one of their homework, okay?
00:17:32 So this is a background.
00:17:35 I think it's a great example, right?
00:17:38 So any questions so far about backpropagation?
00:17:43 So this is just about how to do the backpropagation for gradient descent, but
00:17:50 in our case, you know, we have deep neural network in facing big data, right?
00:18:01 We actually don't use just the gradient descent, right?
00:18:05 So we're going to use stochastic gradient descent, sometimes with mini-batches, right?
00:18:11 And in addition to such mini-batches, stochastic gradient descent, we're going to sometimes have to use momentum and other information,
00:18:23 and eventually reaches one of the most powerful optimizer to train neural networks that's called Adam, okay?
00:18:31 So that's what we're going to talk about next.
00:18:36 So gradient descent, right?
00:18:39 Very simple, and we now even have an effective way of backpropagation, right?
00:18:45 Okay.
00:18:47 But what about the fact that we are facing big data?
00:18:52 In other words, we're calculating loss over many examples where this N can be huge, right?
00:18:58 So calculating the gradient is order of n, right?
00:19:04 But if n is large, right, you still don't want to see that kind of linear cost.
00:19:10 So the solution is the following, right?
00:19:14 Instead of the gradient, let's use stochastic gradient, okay?
00:19:19 So in other words, if you look at this one, I'm not calculating, you know, the gradient of f of x, right?
00:19:26 I'm actually calculating just the one term, fi, okay?
00:19:32 The nabla fi of x, where i is a random example, okay?
00:19:40 So i is a random example, right?
00:19:43 So this may sound very simple for you, right?
00:19:48 How do I know that?
00:19:50 Excuse me.
00:19:51 How do I know that it's, you know, it's a good idea or it's a bad idea?
00:19:54 One starting point to believe that it may not be a bad idea, actually to make sense, is to realize that this is, you know, this nabla fi of x, which is calculating the gradient according to a random example i called stochastic gradient, right?
00:20:17 If I take the expectation, right?
00:20:20 Because this example is randomly drawn.
00:20:23 If I calculate the expectation of this stochastic gradient, right?
00:20:29 Then it's very simple that, you know, if we rewrite the probability of every example to be drawn, because you are choosing examples randomly.
00:20:42 So every example has 1 over n chance to be observed.
00:20:47 So the expectation is simply the average, which equals to the gradient over the whole data set, right?
00:20:58 So in other words, the stochastic gradient is an unbiased estimate of the gradient nabla f of x, right?
00:21:09 The gradient of f of x with regard to the parameters, right?
00:21:16 So it's unbiased estimate.
00:21:18 So it's not bad, right?
00:21:20 So that's about stochastic, okay?
00:21:23 Now, what about mini-batch, right?
00:21:29 So GD, using all observations or examples at once, right, is not particularly data efficient when, you know, data is very...
00:21:42 GD is not particularly data efficient when data is very similar.
00:21:58 Let me try to understand whether I had a typo here or not.
00:22:02 The stochastic gradient, right, with one observation at a time is particularly, is not particularly computationally efficient.
00:22:09 Since CPUs and GPUs cannot exploit the full power of the vectorization.
00:22:17 So the dilemma here is that SGD is not particularly computationally efficient.
00:22:28 Since CPUs and GPUs cannot exploit the full power of vectorization, right?
00:22:35 Because every time you take one observation at a time and utilize this gradient.
00:22:42 On the other hand, gradient descent, as we said, is not particularly data efficient when the data is very large, right?
00:22:53 So in this case, can we have a sweet spot in between, right?
00:22:58 The sweet spot is we do not use all the data because that's not data efficient for big data.
00:23:06 But we do not just use a single point each time either, right?
00:23:13 If you use a single point every time, right?
00:23:15 Every time you do a single point calculation and you take a lot of iterations.
00:23:19 And what about somewhere between?
00:23:23 Let's use a mini-batch of samples.
00:23:27 That's not all the samples, not one sample, but some number of samples, right?
00:23:34 And then we can calculate the gradient, right?
00:23:38 Using the stochastic gradient calculated over the mini-batch, right?
00:23:46 Let's say this is the batch, right?
00:23:48 This is the batch size, right?
00:23:51 Again, we take this sum and then calculate the gradient and average them.
00:23:56 And that's called mini-batch, okay?
00:23:59 So it's actually achieving a sweet spot between GD and SGD, okay?
00:24:06 And lastly, besides gradients, right?
00:24:11 Now stochastic and mini-batch, right?
00:24:13 What else can we do, right?
00:24:17 So one thing you have to realize is that the mini-batch SGD, we said that its expectation,
00:24:25 right, just like the SGD, its expectation is equal to the full function's gradient.
00:24:33 So it's an unbiased estimate.
00:24:35 But we also know that in estimation theory, besides the estimation, right?
00:24:41 Besides it's unbiased, another thing is also important is the variance, right?
00:24:47 For instance, if you have a lot of estimations centered around the true value, right, symmetrically,
00:24:56 then that is unbiased estimate.
00:24:58 But there is a difference between very narrowly distributed estimations around, closely around the ground truth versus very dispersed, right?
00:25:11 High variance estimates around the ground truth, right?
00:25:16 So besides the unbiased estimate about expectation, that's, you know, expectation of X, we also want to do something about the second term, I'm sorry, second moment, which is a variance, okay?
00:25:34 So we want to reduce the variance as much as possible to have not only unbiased, also tight estimate, okay?
00:25:43 So can we do more for variance reduction, right?
00:25:48 It turned out that you can replace the instantaneous gradient at iteration T by accumulating past gradients, right?
00:25:58 This idea we have seen before as well in, for instance, the limited memory BFGS, that we use, you know, earlier iterations gradients in a parameterized way to estimate the second order information, the Hessian or the inverse of the Hessian, right?
00:26:18 This is very similar, but, you know, the concept that they're calling here is momentum.
00:26:23 It's like you're accumulating the gradients over time, right?
00:26:28 So it's like momentum because it's similar to how a heavy ball rolling down the objective function landscape integrates over past forces, right?
00:26:38 So you're utilizing the gradients in the past, right?
00:26:41 So I think this is something that we have seen, for instance, in the shallow models.
00:26:46 We have seen it in conjugated gradient.
00:26:49 We have seen it in the BFGS for different reasons.
00:26:51 Some to avoid zigzagging, some to approximate Hessian, right?
00:26:56 But in this case, it has a very, you know, specific form, right?
00:27:01 You see, like, the exponential decay, right?
00:27:04 Older gradients gonna decay faster into this linear contribution.
00:27:09 That's what the momentum means.
00:27:12 So once you have mini-batch SGD, right?
00:27:18 Once you have momentum, you are close to have the product of Atom.
00:27:25 Atom is an optimizer that apparently uses mini-batch SGD and momentum.
00:27:30 But it's also doing something more like, you know, it's scale per coordinate or direction to allow for a computationally efficient preconditioner.
00:27:40 Okay, this is something that numerically people usually do a lot.
00:27:44 There's also a decoupled per coordinate scaling from a learning rate adjustment.
00:27:49 So it has some learning rate scheduling that is, you know, decoupled from how these scaling are done per coordinates.
00:27:57 So if you are interested in the details, I suggest you reading the dive into learning chapter 11, section 7 and 8.
00:28:09 So these are the details about Atom.
00:28:13 Okay.
00:28:13 So now I think you have already learned almost everything needed for the computation.
00:28:22 We talked about what?
00:28:23 We talked about the models.
00:28:25 Why theoretically, according to the universal representation theorem, we could use MLPs or other kind of neural networks to approximate Borel measurable functions and including their gradients even.
00:28:41 And the conditions are they have to have enough hidden units.
00:28:45 And we know that the contribution of the depth is much more than the width.
00:28:51 And it also reduces overfitting issue.
00:28:54 Right.
00:28:55 We have also learned the loss function.
00:28:58 Right.
00:28:59 That for different kind of labels and the desired distribution of the labels.
00:29:05 Right.
00:29:06 And for different kind of neural network layers, we have different choices of the loss functions.
00:29:13 And on top of the loss functions, we can add LpNorm.
00:29:17 But we can do more than that to regularize model complexity, especially dropout.
00:29:24 Because, again, our parameters W have very special structures.
00:29:31 They map to these interconnections across the input layers or the hidden layers.
00:29:38 Right.
00:29:38 And in the end, we have optimizers.
00:29:43 Right.
00:29:44 We've seen that starting from the GD, we had the need to go to stochastic gradient descent facing big data.
00:29:52 And then we need to include the mini-batch SGD to have more efficiency that utilize the vectorization.
00:29:59 Because we have a lot of multiple examples in each batch.
00:30:04 We still have an unbiased estimate of the gradient.
00:30:10 But we also have less variance.
00:30:13 Right.
00:30:14 And then additional techniques, including momentum, that is aggregating the history of past gradients, can accelerate convergence.
00:30:24 Okay.
00:30:25 One of the big issues of training deep neural networks is, of course, we are optimizing an extremely non-convex function in a high-dimensional space.
00:30:36 Okay.
00:30:37 Very often, it's about how to escape some steady, sorry, stationary points.
00:30:44 Especially the saddle points, because there are a lot of saddle points in such high-dimensional, sophisticated landscape.
00:30:52 And knowing how to get away and without being trapped there is extremely important.