Lecture 14: Regression, Bias-Variance Tradeoff, and Regularization

Recording. Download the text transcript.

Automatic transcript; technical terms and equations may contain recognition errors.

00:00:00 This is the second last lecture for the module of machine learning. This part has been learned already for most of you.

00:00:12 So we haven't spent too much time on this module, but we chose to review the key concepts.

00:00:22 So previously we talked about in machine learning we talked about in what cases you would like to do machine learning.

00:00:34 When you face a complex system without a lot of principles or enough details about the inner workings,

00:00:42 but you have a lot of IO relationships, a lot of data.

00:00:46 So in that case, you'd like to construct a machine learning model to replicate, reproduce or replicate such IO relationships as much as possible.

00:00:58 We also talked about when we do the supervised machine learning in the case of classification, for instance,

00:01:06 how do we evaluate classifiers?

00:01:09 And we also talked about when you have heterogeneous data, like in our case of protein function prediction,

00:01:16 what are the major categories of approaches to integrate this heterogeneous data, right?

00:01:24 We have seen how feature integration, kernel integration, and predictor integration or ensemble methods work, right?

00:01:35 In the ensemble methods we talked about bagging. We also talked about feature bagging in random forest, right?

00:01:42 If you remember one thing I said that was the fact that the random forest is, or this ensemble methods in general,

00:01:50 is reducing the variance. And I said that it's part of the generalization error.

00:01:56 So I don't have the opportunity to talk about that in details, but today when we talk about regression,

00:02:03 I think it's time to talk about the bias variance trade-off.

00:02:07 And a way to balance the trade-off by regularizing the model complexity.

00:02:14 So again, many of you have learned this before, so please try to recall and make sure you master this concept.

00:02:22 For others, it's entirely fine if you have never learned it, you can still have this part of the contents very accessible.

00:02:32 Okay? All right, how many of you have learned the bias variance trade-off?

00:02:38 You must have learned it. Yes, yes, yes, yes.

00:02:44 Okay, we have a very diverse group, so no matter you have learned it before or not,

00:02:50 today you should be able to review or master the content.

00:02:54 Okay, this is a very important theoretical results for our guidelines.

00:02:59 Okay? Next Tuesday is going to be the last lecture for the machine learning module.

00:03:06 And we'll talk about how to diagnose machine learning models, specifically using some shadow models as examples.

00:03:16 Then we'll have one lecture to start the third module of deep learning slash AI.

00:03:25 Then we'll have the spring break, and then after the spring break, we'll have about ten more lectures on the third module.

00:03:35 Okay? And that's also the module when we start the journal club assignment, so please wait for the poll.

00:03:44 We'll give a list of the papers.

00:03:47 Just like the examples you were given from last year, the journal club.

00:03:53 And you will have to choose your priorities like, you know, top choice, second choice, third choice.

00:04:01 And then we actually will solve an integer programming problem to find the optimal assignment.

00:04:09 So that cumulatively or collectively you get the highest priority you want.

00:04:17 Okay? So let's get started.

00:04:21 So today we're going to talk about the regression and bios variance trade-off.

00:04:25 So let's talk about the regression.

00:04:27 So we know that it's in the category of supervised machine learning.

00:04:32 And in this case, we do have labels.

00:04:35 And these labels are in a continuous domain.

00:04:38 So these labels are continuous.

00:04:41 So this is the example I gave you before.

00:04:46 That is the relationship between the boiling temperature and the altitude.

00:04:52 Okay?

00:04:53 So you could fit any kind of function to make predictions.

00:04:59 Right? Some people used to say that machine learning is nothing but, you know,

00:05:04 fitting functions to points or data fitting.

00:05:08 It is right and it's wrong.

00:05:10 Okay?

00:05:11 You will see that machine learning is not about how well, or it's not just about how well you, your model fit the observed points.

00:05:22 What's more important is how accurate it's going to be for the future prediction task.

00:05:29 So that's much more important.

00:05:31 So, and then we had different elements for regression.

00:05:37 So first you can talk about what models you're going to use.

00:05:40 Why we could use linear models or general linear using their kernel trick.

00:05:45 Right?

00:05:46 When you extend the X to phi of X, then using this kernel trick, right?

00:05:50 You could have a linear kernel in the higher dimensional phi of X space, but in the original X space is nonlinear.

00:05:57 Right?

00:05:58 And you could have different fitting criteria.

00:06:02 Right?

00:06:03 You could have a least squares.

00:06:04 Right?

00:06:05 Which can sometimes give you the closed form solution because in the case of the linear function, then the objective function is quadratic in the parameters, which is the coefficients of the linear models.

00:06:20 Right?

00:06:21 So, let's look at these two categories.

00:06:25 So, you can use linear models.

00:06:28 As I said, it's just a function linear in X.

00:06:31 You can also make it more generally linear.

00:06:33 Right?

00:06:34 As I said, changing X to phi of X.

00:06:36 Right?

00:06:37 We have seen this notation phi of X before in their kernel trick.

00:06:41 Right?

00:06:42 So, this is generalized linear and it can still very easy to help you get nonlinear relationships between X and Y.

00:06:51 Because from phi to Y is linear, but from X to Y is nonlinear.

00:06:55 Right?

00:06:56 So, that's the kernel trick we have learned before.

00:06:58 Right?

00:06:59 So, in the case of the kernel methods like the k-nearest neighborhood or support vector machines, right, we can handle expansions of the raw data that use a huge number of nonlinear, non-adaptive methods.

00:07:12 Right?

00:07:13 Because, you know, in the case of the kernel methods, right, they don't care about what's the dimensionality of the raw feature space.

00:07:25 Right?

00:07:26 It doesn't matter.

00:07:27 It doesn't matter.

00:07:28 Because how the training example enter the formulation, specifically in the dual problem, is the inner product.

00:07:37 Right?

00:07:38 It doesn't matter what's the dimension of phi or phi .

00:07:41 What matters is inner product or kernel.

00:07:44 Right?

00:07:45 Similarly, in the case of the optimal solution, it's the inner product between phi and, sorry, X sub i, the support vectors, and X.

00:07:54 Right?

00:07:55 So, or phi of X i and phi of X.

00:07:59 Right?

00:08:00 In the nonlinear case.

00:08:01 So, it can deal with this high dimensional case very easily.

00:08:05 Right?

00:08:06 So, we can incorporate the soft margins as we introduced before in the support vector machines to avoid overfitting.

00:08:15 But we'll talk about overfitting more in next Tuesday's lecture.

00:08:19 What about the loss function?

00:08:22 Right?

00:08:23 The loss function is very important.

00:08:24 As we said, you can pay attention to the search algorithm for optimization.

00:08:29 But you probably need to pay equal or more attention to the objective function itself.

00:08:35 Because the optimality is defined by the objective function.

00:08:40 Right?

00:08:41 So, you need to carefully choose this loss function to minimize.

00:08:45 So, what criteria should we choose?

00:08:48 Right?

00:08:49 So, sometimes you can choose one that makes the math easy.

00:08:53 So, as I said, the squared error is quadratic in the coefficients or parameters if you are using a linear model.

00:09:03 So, this sometimes gives you an analytically solvable solution if your constraints are linear.

00:09:09 Right?

00:09:10 And the functions are linear.

00:09:12 Right?

00:09:13 You can also choose something that makes the fitting corresponding to maximizing the likelihood of the training

00:09:19 given some noise model for the observed outputs.

00:09:24 Okay?

00:09:25 So, for instance, you can choose to maximize the probability of the observed XIYI given your theta.

00:09:36 Right?

00:09:37 So, that's another possibility.

00:09:39 Right?

00:09:40 So, you can also choose a model that makes it easy to interpret the learned coefficients.

00:09:46 That means sparsity is important to you.

00:09:48 So, that means you would like to have most of the coefficients in front of the features to be zero.

00:09:54 Right?

00:09:55 That's probably another consideration.

00:09:56 Right?

00:09:57 You could also consider some real-world applications.

00:10:02 Right?

00:10:03 For instance, you may think that the squared error is a good idea than the absolute error or the error itself.

00:10:12 Right?

00:10:13 But what if the error we are talking about is the difference between your arrival time at the check-in counter at the airport minus the departure time of the flight?

00:10:33 Would you rather be half an hour earlier or half an hour late?

00:10:39 Right?

00:10:40 So, apparently, you don't want to be late.

00:10:41 Right?

00:10:42 You know, there's some drama I have seen before.

00:10:44 People have to catch international flight which is only once a day and they're just like late for five minutes.

00:10:50 The gate is closed.

00:10:52 You know, all kinds of the drama.

00:10:53 You must have witnessed those.

00:10:55 So, in those cases, you definitely don't want to have a symmetric loss like a squared error.

00:11:01 Right?

00:11:02 By symmetric, I mean that plus or minus delta give you the same loss.

00:11:07 But in our case, apparently not.

00:11:09 Right?

00:11:10 Right?

00:11:11 So, you have to consider all this when you construct your loss functions.

00:11:14 Okay?

00:11:15 So, it's an art.

00:11:17 So, let's start with a simple example.

00:11:21 And I want you to remind yourself of the optimization formulation we talked about before.

00:11:28 As I said, a lot of machine learning problems are formulated as optimization problems and solved by optimization algorithms.

00:11:36 So, I want you to have that kind of perspective.

00:11:39 We started with a linear model, but we know that we can easily extend it to generally linear.

00:11:44 And the error is a squared error.

00:11:48 Right?

00:11:49 So, we can divide it by one over, you can divide it by a number of the samples.

00:11:53 To have the mean squared error, it's the same.

00:11:55 It's a constant.

00:11:56 Right?

00:11:57 So, in this case, if there were no constraint at all, if there's no constraint at all, we have a quadratic optimization problem with no constraints.

00:12:10 Right?

00:12:11 And in this case, we can actually analytically solve the optimal solutions very easily.

00:12:17 So, in this case, what you have is this x transpose times x, where x is the matrix of the training example.

00:12:27 Okay?

00:12:28 And you take the inverse times x transpose times t, which is the target, the vector of target values or labels.

00:12:38 So, the ith row of that vector is the ith example's label or t sub i.

00:12:45 Okay?

00:12:46 So, you will find that actually the optimal weight is this matrix.

00:12:51 Right?

00:12:52 So, we have to do this matrix.

00:12:53 Right?

00:12:54 Times x transpose times t.

00:12:55 Right?

00:12:56 Times x transpose times t.

00:12:57 What is this matrix?

00:12:58 X transpose times x and then take an inverse.

00:13:03 X transpose times x is the covariance matrix of the input vectors.

00:13:10 Right?

00:13:11 So, if we assume like, you know, that x is already centered, meaning that expectation of x is already zero.

00:13:18 Right?

00:13:19 So, in that case, we are looking at a covariance matrix.

00:13:23 And x transpose is just a transposed matrix.

00:13:27 We call this a design matrix x because it's only dependent on the training examples features.

00:13:36 And the t is a vector, right?

00:13:38 So, it's just a vector of target values.

00:13:41 If we have a single label, then this is just a column vector.

00:13:46 Okay?

00:13:47 In the end, you have a column vector for w star.

00:13:49 Right?

00:13:50 So, that's the analytical solution.

00:13:52 This echoed what I said.

00:13:54 Sometimes you want something, sometimes you want a loss that gives you easy math.

00:14:00 Okay?

00:14:01 This is one example.

00:14:03 Okay.

00:14:04 But if we only consider the loss function, what we are doing is optimize the fitting to the existing data.

00:14:14 Right?

00:14:15 As I said, this is machine learning is not data fitting.

00:14:18 Right?

00:14:19 It's not about optimizing the fitting to the existing data.

00:14:22 The more important thing is that it should optimize making decisions or predictions for the unseen data.

00:14:31 Right?

00:14:32 Sometimes you make examples like whether the unseen data are also, you know, having the identical distribution or different distribution.

00:14:39 You may or may not have to consider how to transfer your, the distributions between the source and the target domains.

00:14:49 But you need to keep in mind that it's not about fitting.

00:14:54 So, machine learning is not fitting.

00:14:56 So, what do we care about?

00:14:59 Again, is the generalization error.

00:15:04 Meaning that this is the error for the test data.

00:15:08 Okay?

00:15:09 The test data is not something, you know, that the model has seen when it's being trained.

00:15:16 Okay?

00:15:17 But if you think about how to minimize the test error, right?

00:15:21 So, we can think about this error.

00:15:23 So, we have this, if we don't look at this triangular, which means this expectation.

00:15:32 Okay?

00:15:33 In physics, sometimes you see this triangular or angle bracket for expectation.

00:15:38 Okay?

00:15:39 So, you can rewrite it as E sub D.

00:15:42 It's the same.

00:15:43 Okay?

00:15:44 So, we are looking at the expectation of the squared error.

00:15:49 Okay?

00:15:50 So, X.

00:15:51 Okay?

00:15:52 So, we have this model trained.

00:15:54 Model is Y.

00:15:55 And it's trained on the training data D.

00:15:58 And it's now making an inference on the test example, X sub N.

00:16:04 Okay?

00:16:05 And the T bar N is the average target value for the test case.

00:16:11 So, it's a constant.

00:16:12 Okay?

00:16:13 So, we are looking at the squared error and then we taking the mean because, right, we are

00:16:21 looking at the expectation over the training data.

00:16:23 Right?

00:16:24 Right?

00:16:25 So, this is what we care about.

00:16:27 What's the expected generalization error?

00:16:30 In this case, the squared error.

00:16:33 Okay?

00:16:34 So, this is actually a very easy proof that, you know, after you learned,

00:16:41 the undergrad level probability, you should be able to prove this very easily.

00:16:48 Okay?

00:16:49 So, you will find out that you can rewrite this left-hand side, the expected generalization

00:16:59 error.

00:17:00 And to find out that actually it consists of two terms.

00:17:03 Actually, there's a third term.

00:17:04 Okay?

00:17:05 But it's ignored.

00:17:07 So, the first term is the squared expectation minus, you know, so it's a squared difference

00:17:21 between the expected model prediction and the average label.

00:17:28 Okay?

00:17:29 In other words, this is the bias.

00:17:33 So, this is the model, you know, this is the average model prediction minus the actual, the

00:17:42 actual average labels.

00:17:44 So, we have the square of the bias in the first term.

00:17:53 Okay?

00:17:54 In the second term, what we have is the expectation of this y minus the expectation of y.

00:18:05 Okay, and then take a square.

00:18:08 What is this?

00:18:10 Let's call this y like z.

00:18:12 What's the expectation of z?

00:18:15 What's the expectation of the squared z minus expectation of z?

00:18:28 The variance, right?

00:18:30 So if you replace z by y, you have the variance term of this y, right?

00:18:36 This is a variance over all training data sets.

00:18:40 This is a variance over the model estimate.

00:18:43 Y is a model estimate, okay?

00:18:45 So depending on how your training data is collected or used, this is the variance.

00:18:50 So one is about how much bias is there, how much one is about the model variance, right?

00:18:58 Please pay attention that the bias term is, you know, the bias relative to the actual label, average actual label.

00:19:06 So that enters t bar, okay?

00:19:09 But the variance term, the variance term has nothing to do with the actual target label.

00:19:16 It's just about how the model's prediction is varying according to different training data, okay?

00:19:23 So these are two different concepts.

00:19:25 So in short, you can say that, well, the expected generalization error that we care the most about, by the way,

00:19:32 is not the least squared error for the observed data, okay?

00:19:36 It's for the test data, while treating the observed data as a random variable, okay?

00:19:45 So in other words, this expected generalization error, excuse me, is squared bias plus variance, okay?

00:19:54 So this is the first major results that we want to talk about.

00:20:00 So once you have this idea, right, the expected squared loss equal to the squared bias plus variance,

00:20:07 plus a term I said I ignored, which is a noise, okay?

00:20:12 So this noise is, you know, due to the fact that the target values are noisy, which we have no control over, right?

00:20:18 Actually, there's a third term I ignored when deriving that.

00:20:22 I strongly recommend you to derive that expectation, I think.

00:20:26 It's a good exercise for the PhD qualified exam, I think.

00:20:31 So see where that noise term is coming from, okay?

00:20:36 So, but let's try to interpret these three terms again.

00:20:42 So the bias is the systematic error in the model's estimate, right?

00:20:49 And the variance is only about the estimate or the model prediction alone, right?

00:21:10 This is the noise in the model estimation, right, caused by sampling noise in the training set, right?

00:21:18 Because the training set, D is a distribution, right?

00:21:22 And the last term, as I said, is a noise term, which is due to the fact that the target values, right,

00:21:29 there's some measurement noise.

00:21:32 That's something we cannot control over, so we only pay attention to the first two terms, okay?

00:21:38 So to be exact, the expected squared loss is equal to the sum of the three terms, not just the first two.

00:21:48 Okay?

00:21:49 Let's look at the first two that we can control over, right?

00:21:53 Because, you know, it's about the model that we can control, right?

00:21:58 So, how can we improve a model, right?

00:22:01 Knowing that there is a bias-variance trade-off, right?

00:22:04 Right, because, well, I haven't talked about the trade-off yet, because, can I say that, well, if I want to minimize the expected squared error,

00:22:12 why don't I reduce both bias and variance to be as close as possible to zero?

00:22:19 Can I do that?

00:22:24 Can I reduce both bias and variance toward zero as close as possible?

00:22:32 So, can I reduce both bias and variance?

00:22:47 So, there's always a trade-off?

00:22:49 Why is there always a trade-off?

00:22:51 Why can I reduce both?

00:22:52 Why can I reduce both?

00:22:54 If the equation is, sorry, we are reducing one, then the second one will decrease.

00:23:02 How do you see that if one increases, the other might decrease?

00:23:15 Well, I'm not saying that the left-hand side is fixed, right?

00:23:19 No, not this one.

00:23:20 The equation for bias and variance.

00:23:23 Which one?

00:23:24 The equation for bias and variance.

00:23:27 This one, yes.

00:23:29 Can you say that again?

00:23:31 No, I didn't.

00:23:32 Yes, so if bias is decreasing.

00:23:37 If the bias is increasing.

00:23:39 Then, in various ways, we can see if you have this, it will definitely decrease.

00:23:56 We can put some values and see if it's...

00:24:01 Okay.

00:24:02 That's...

00:24:05 Thanks for the answers.

00:24:09 Any other additions?

00:24:13 Additions?

00:24:14 To be honest, I cannot easily draw a conclusion about the trade-off from what I have talked

00:24:23 about so far.

00:24:24 So, for that, I suggest you to read into the Cramer's theorem or the Cramer's inequality,

00:24:32 which basically tells you that you cannot arbitrarily reduce both of them.

00:24:38 And so there is a trade-off.

00:24:40 So that is not included in my slides.

00:24:43 Okay.

00:24:44 The key word is the Cramer's inequality.

00:24:46 So, the theoretical results, you know, that's not covered in the slides, right?

00:24:56 It's telling us that it's probably not possible to reduce both.

00:24:59 So, usually, when the bias is low, the variance is high, and vice versa.

00:25:03 So there is a trade-off, okay?

00:25:05 I didn't, again, include in the slides why there is a trade-off.

00:25:10 There is a theoretical results, okay?

00:25:12 So...

00:25:13 When the variance is high, we are completely both reading and the bias is high, we are completely

00:25:19 under-reading.

00:25:20 So, it's not that we cannot obtain both of them to zero or...

00:25:28 That is a possibility to...

00:25:30 Yeah, you can interpret it that way.

00:25:32 It's not rigorous, but it's intuitive.

00:25:35 Yes.

00:25:36 So, you will see a similar claim in the next Tuesday's lecture about over-fitting, under-fitting.

00:25:45 Some very intuitive illustrations, like when you are hitting the...

00:25:50 Like a target, and you want to hit right in the middle, right?

00:25:56 As close as possible, right?

00:25:58 So, how far your landing points are from each other is like the variance, but how close they

00:26:04 are to the center of the target is about the variance, is a bias, right?

00:26:08 Right?

00:26:09 So, that tells you over-fitting, under-fitting.

00:26:12 So...

00:26:13 So...

00:26:14 Acknowledging the trade-off, right?

00:26:18 Either you like to please read more into the theory part, or you acknowledge it intuitively.

00:26:25 There is a trade-off, and then we want to sort of find a sweet spot, right?

00:26:32 So, we want to guide our estimators to find that sweet spot, right?

00:26:38 So, let's think about the individual bias and the variance separately before we talk about

00:26:46 how to change the model for the sweet spot, okay?

00:26:50 So, we can reduce the variance by having more training data, and we can also reduce the variance

00:26:56 by creating different data sets by bootstrapping, and then from the different example, this is called

00:27:04 the backing that we have learned before, right?

00:27:07 So, there are different ways for you to reduce the variance alone, right?

00:27:12 As we said, this is actually why ensemble methods work better, right?

00:27:18 The generalized linear models can be regularized to decrease their variance at the cost of increasing their bias sometimes.

00:27:27 So, then the question is, what can we do?

00:27:32 I mean, what is the knob on this model that I can, you know, turn left or right, so that I can reach a sweet spot of this trade-off?

00:27:45 So, that's the question, okay?

00:27:46 So, now the question is the following.

00:27:48 What's the knob on that model?

00:27:50 What can I modulate for the model?

00:27:52 So that I can adjust between these bias-variance trade-off, okay?

00:27:59 That's the question.

00:28:00 So, actually, that knob I just talked about can often be defined as the model complexity, okay?

00:28:15 By the way, I didn't define model complexity, okay?

00:28:18 So, the model complexity is often measured by the number of independent parameters to fit or the degrees of freedom, okay?

00:28:27 The intuition of the bias-variance trade-off, you know, now that we have the knob of the model complexity is the following.

00:28:35 Right?

00:28:36 Something like Salman was saying earlier, if you have a complex model, very complex, then as the data change,

00:28:42 the model output or estimate also changes drastically.

00:28:46 So, it's very sensitive to the data, right?

00:28:49 So, when X changes a little bit, then the predicted Y changes a lot.

00:28:54 That means the variance can be very high, even though your model complexity gives you some low bias, right?

00:29:02 If you have a simple model, it could be high bias, right?

00:29:08 Because it's too simple for the pattern to fit or estimate, excuse me.

00:29:14 So, in this case, the model is more rigid in the sense that the output or the model estimate does not change as much with the change in X or the input.

00:29:24 In other words, the model estimate is of low variance, right?

00:29:29 But high bias, as we said before.

00:29:31 So, one of the most important goals in learning is to find a model that is just right in the bias-variance trade-off,

00:29:40 and seemingly, model complexity is that knob on the model that we can tune for this sweet spot, okay?

00:29:50 But, as you can see, model complexity is a very vague definition, okay?

00:30:03 So, we'll ask you more about how to measure the model complexity later on, but now let's look at the ideal scenario, right?

00:30:14 Let's say we can modulate the model complexity somehow, right?

00:30:18 As we said, as the model complexity increases, the squared bias will decrease, and the squared, I'm sorry, the variance will increase,

00:30:27 and the sum of the two, as expected generalization error, less noise, probably have a shape like this.

00:30:34 So, there's some sweet spot, right?

00:30:36 Now, the question is, you know, what do you use to measure the model complexity so that you can modulate that directly on the model, right?

00:30:47 So, the idea of regularization is tune the level of model complexity to lower generalization error.

00:30:56 So, the idea is that, you know, you can decrease the variance substantially while increasing the bias just a little bit, okay?

00:31:04 So, you can, because you're regularizing the model complexity, you're making it less sensitive, okay?

00:31:10 It will sacrifice the bias, right?

00:31:15 It will increase the bias, but hopefully the variance will decrease substantially and overcome and overcompensate, okay?

00:31:22 So, the common approach, okay, I directly give you the answer, right?

00:31:29 So, the reason why I'm using the model complexity is actually people use this LP norm to, as a way to regularize model complexity.

00:31:40 So, you may wonder, well, why don't you use a definition, the number of independent parameters?

00:31:48 Why don't we use that to modulate model complexity?

00:32:00 Can we use a number of independent parameters to directly modulate or regularize model complexity?

00:32:09 Any ideas?

00:32:22 Let me first drop the word independent.

00:32:26 Can I just use the number of parameters?

00:32:28 Yes.

00:32:29 Yes, I can.

00:32:31 Can we increase the parameters in the model complexity?

00:32:41 Uh-huh.

00:32:42 What if these parameters are largely correlated with each other or even redundant?

00:32:53 So, you see the part of independent coming, right?

00:32:57 But even if that's the case, it's kind of hard for you to estimate the number of independent parameters.

00:33:03 Not to mention that whether the model complexity is enough or not is not decided by the absolute quantity, which is only determined by the model.

00:33:21 Because your number of independent parameters is only determined by the model.

00:33:25 Did you realize that?

00:33:26 You don't care about your data, actually.

00:33:29 Right?

00:33:30 But actually, when you talk about the model is too complex or not enough complex, it should be relative to the training data, isn't it?

00:33:39 It's not absolute in the sense that it shouldn't be irregardless of the data.

00:33:45 Right?

00:33:46 So, these are the two reasons that led to this LP norm to be a better measure for the model complexity.

00:33:54 Okay?

00:33:55 So, we talked about, you know, this y just not use the number of parameters, right?

00:34:01 We can include this as a penalty, right?

00:34:04 You can minimize the, you know, the mean squared error and then minus the number of parameters, right?

00:34:12 You can minimize the number of parameters simultaneously.

00:34:15 Okay?

00:34:16 Well, first of all, this is a little bit too simplistic, right?

00:34:20 First of all, you know, it's kind of independent.

00:34:24 It's kind of hard for you to figure out the independent parameters.

00:34:28 Okay?

00:34:29 As I said, in this case, I'm using a kernel method, right?

00:34:32 I'm going from x to phi of x.

00:34:34 You see that, you know, actually some features are highly correlated, right?

00:34:38 Secondly, it should be dependent on the data.

00:34:41 The same model with the same number of parameters might be too simple for some data, but might be too complex for some other data.

00:34:49 So, it's not just about the model itself, right?

00:34:53 So, in that sense, actually, you know, the answer was using the LP norm of the learned W, because the W is reflecting both your model and your data, right?

00:35:07 So, this is actually a better choice and we'll try to motivate you through an example, right?

00:35:13 From the, you know, classical book you can recognize from, you know, Chris Bishop, his pattern recognition book, right?

00:35:20 Very classical book.

00:35:22 So, here there is an underlying natural process, which we don't see, the green one, right?

00:35:29 It generates essentially a, you know, like a sinusoidal kind of input-output relationship, but unfortunately we don't know that.

00:35:38 Okay?

00:35:39 The green one is, you know, the unseen one.

00:35:42 And also, we actually don't have the perfect measurement.

00:35:47 So, all we can see are the blue circles, which are the noisy measurement of the hidden or underlying green function.

00:35:56 Okay?

00:35:57 So, that's why the blue circles are on and off.

00:35:59 Okay?

00:36:00 The green curves.

00:36:02 So, the machine learning goal is to construct a new model, which is red, right?

00:36:09 To estimate the blue circle.

00:36:11 I'm sorry, to fit the blue circles so that it can approximate the hidden unseen function, right?

00:36:19 Including the test points in this curve, on this curve, right?

00:36:22 As much as possible, right?

00:36:24 So, now let's make some observation, okay?

00:36:29 If the, let's use a class of polynomial functions for this estimator.

00:36:35 And let's say the order is m.

00:36:38 So, if the order is one, it's just a linear function, right?

00:36:41 It's very robust, right?

00:36:44 And if the order is three, it's a cubical function.

00:36:47 And if the order is nine, so you have this ninth order polynomial, right?

00:36:52 But you can see, indeed, as you go from left to right, the bias is decreasing and decreasing, right?

00:36:58 But the variance is going to be increasing and increasing, because the model complexity is increasing.

00:37:04 But I want you to pay attention to the learned parameters, w.

00:37:09 Okay?

00:37:10 As you can see that, as the model complexity increases, in this case, m, you know, in this case,

00:37:17 I shouldn't say model complexity increases, because I haven't defined that yet.

00:37:21 Numerically, let's say, when the order of the polynomial function increases, at least,

00:37:27 we noticed that, intriguingly, the magnitude of the learned or the optimal w is getting bigger and bigger, right?

00:37:38 It's actually that easy to understand, because it's trying to fit these noisy observations as much as possible.

00:37:46 So it needs some extreme values.

00:37:49 So that's just the numerical motivation for you to see that, okay, well, we can model or penalize model complexity, right?

00:37:59 Use the shrinkage methods.

00:38:01 That is, we can use the size of w.

00:38:04 The size of w.

00:38:06 By size of w, I mean the LP norm.

00:38:09 For instance, if p equal to 2, we basically have the L2 norm, which is like the Euclidean distance between w and 0, right?

00:38:19 Right?

00:38:20 If p equal to 1, what we have is what?

00:38:24 The mean absolute error compared to 0, right?

00:38:27 Then p can change.

00:38:28 So this is a very appropriate term as a penalty, which reflects the model complexity, and it's suitable to be added to the loss function.

00:38:40 Okay?

00:38:41 So now we see that, well, you can use your loss function, in this case, mean squared error, plus, for instance, L2 norm.

00:38:51 Okay?

00:38:52 And then you have a lambda, which is a way to adjust between the two objectives, because you want to fit as much as possible, but you know that it's not about fitting the existing data.

00:39:03 It's about minimizing the generalization error, so I better modulate the model complexity through this shrinkage method, so that I can more or less find a sweet spot, right?

00:39:14 Okay, so this penalty is actually, you know,

00:39:21 very friendly because, why do I choose p equal to 2 for the LP norm or the penalty?

00:39:31 Well, in this case, I have this penalty as a quadratic function in w, just like the loss function, mean squared error, right?

00:39:45 So I still have a squared loss in w, right?

00:39:50 So it's very friendly, right?

00:39:52 This is called, you know, ridge regression, where this is L2 regressor, okay?

00:40:00 Because it's still a quadratic function, we can actually still get the analytical solution for the optimal w, actually.

00:40:08 You can still do that, okay?

00:40:11 Compared to what you have seen before, without this term, the only thing that's changing is here.

00:40:18 So if I let lambda equal to zero without lambda times the identity matrix, you have exactly what you have before,

00:40:25 the inverse of the covariance times the design, the transpose of the design matrix times the label vector.

00:40:32 But here, we have lambda times i here, okay?

00:40:38 So this is very natural, right?

00:40:41 So now let's try to understand this geometrically, okay?

00:40:47 Let me rewrite it, let me rewrite it, okay?

00:40:50 Let me rewrite this optimization problem, okay?

00:40:53 So, you know, I have n examples, right?

00:40:59 And then I have observed xi and yi, okay?

00:41:03 So my model is a linear model w transpose times xi, and the error is yi minus w transpose times i,

00:41:10 and I take the square root of the error and I add them together.

00:41:13 That's the squared error, okay?

00:41:19 Plus lambda times the L2 norm.

00:41:22 So here I just look at all the m dimensions of w, right?

00:41:26 And I take the squared sum, okay?

00:41:31 So that's the definition of the squared L2 norm.

00:41:34 I can actually rewrite this optimization problem for the sake of geometric interpretation

00:41:41 because you can move this penalty or restraint.

00:41:47 It's like a restraint.

00:41:48 It's part of your loss function is a restraint.

00:41:51 But you can actually move this restraint to be a constraint, okay?

00:41:57 So one is a soft restraint and one is a hard constraint.

00:42:03 But you can adjust, you know, how strict or soft this constraint is depending on this t, okay?

00:42:11 So just like lambda in the first formulation for the restraint, t is also the similar counterpart for the constraint.

00:42:23 Okay?

00:42:24 So it's adjusting how much you enforce this constraint.

00:42:28 In this case, how much you value this restraint relative to the squared error, okay?

00:42:34 So this is something, you know, that you can find the correspondence between lambda and t using the Lagrangular multipliers, right?

00:42:44 So this is something that we rewrote as a constrained optimization problem for the sake of geometric interpretation, okay?

00:42:53 I'm going to show you again.

00:42:54 We have done this before for linear programming.

00:42:57 Now we are doing this for quadratic programming with linear constraints, okay?

00:43:05 Let's do that together.

00:43:07 So let's now interpret this, okay?

00:43:11 So essentially our, let's look at the feasible set, okay?

00:43:19 Let's say w is in two-dimensional space, okay?

00:43:24 So w1 squared plus w2 squared less than or equal to t defines a feasible set which is within the circle, isn't it?

00:43:34 So the blue is, what's within the blue circle is your feasible set, right?

00:43:41 Now let's look at your objective function which is also quadratic but, you know, it's rotated, right?

00:43:49 And so let's say it's like this, you know, contour is like this, okay?

00:43:54 So in the middle it's the smallest but then, you know, it's following this contour, okay?

00:43:59 The points on the same line have the same values and as you get further and further away from this center point,

00:44:07 the value gets smaller and smaller, right?

00:44:12 Sorry, the value gets bigger and bigger, okay?

00:44:15 Let's, in this case, let's say it's getting bigger and bigger, okay?

00:44:18 So, so now let's see.

00:44:21 If, let's see, this, oh, in this case we are doing the argmax already.

00:44:29 So if we take, you know, here in this case, let's be careful.

00:44:34 We are not minimizing this one but maximizing the minus of this value.

00:44:39 So this point should be the maximum value, okay?

00:44:42 So as you get further and further away from this center point, the value is getting smaller and smaller, okay?

00:44:49 All right.

00:44:51 So as we've seen before, if there's no constraint at all, right?

00:44:57 Then this optimal solution is right here, right?

00:45:09 That's what we have simple for, x transpose times x and then takes the inverse times x transpose times y, right?

00:45:17 That's the w hat ml.

00:45:19 That's what we have simple for, but we know that is not a good solution because it's only optimal for fitting the existing data, right?

00:45:27 So now we actually have additional regularization, which is reflected as a feasible set, right?

00:45:34 So we cannot pick a point that's outside of the circle anymore, right?

00:45:39 So now that we know that, you know, this function value is to be maximized and then the further it gets away from this center point, the smaller it gets, right?

00:45:51 Then where is the optimal solution for this constraint optimization?

00:45:56 Or what's the optimal solution of this ridge regression problem?

00:46:02 It's when this contour line first hit the border of the feasible set, isn't it?

00:46:12 Right?

00:46:13 Because the further away, the smaller the value gets, right?

00:46:18 In my case, I want to maximize this negative value, right?

00:46:21 So the first feasible point I can reach starting from the, you know, the center point, the further away I get smaller function value.

00:46:30 So I might as well just keep this first feasible solution, right?

00:46:37 When, you know, this contour line reaches, that gives me the feasible solution, right?

00:46:42 The optimal solution, right?

00:46:43 So this is a geometric interpretation of the optimal solution without regularization or with ridge regression.

00:46:55 Okay?

00:46:56 So we have done this before.

00:46:58 Remember when we do the linear programming, our objective function is linear.

00:47:03 So we have a linear function, we have to move it this way or that way.

00:47:07 If it's following the direction of the C vector, then it's getting bigger and bigger, right?

00:47:11 We're trying to minimize, so we try to sweep it to the opposite of C direction.

00:47:16 And our feasible set, this blue region is a polyhedron, right?

00:47:21 So in our case, actually, because it was closed, the visualization was a polytope, actually.

00:47:31 Right?

00:47:32 So that's something you want to remind yourself, okay?

00:47:36 Notice that this optimal ridge solution is not invariant to the scaling of X, okay?

00:47:44 So maybe, you know, you'd like to preprocess the data so that X is standardized like zero mean and unit variance.

00:47:51 And Y is centered like zero mean.

00:47:53 So this is something that people usually do, especially in the age of machine learning.

00:47:58 But, you know, now people are doing deep learning, less people are paying attention to this.

00:48:02 But maybe sometimes the model directly takes care of that before you know it, okay?

00:48:07 Okay, now let's look at a different choice of P, okay?

00:48:15 When P equal to two, when the penalty is L2, we're talking about the ridge regression.

00:48:20 But when the penalty is L1, right, then it's called a lasso, okay?

00:48:27 So this lasso, you know, we'll see whether we have some analytical expression or not.

00:48:37 So how to calculate, right?

00:48:39 So, lasso is an acronym for least absolute selection and shrinkage operator.

00:48:46 So, you know every word of it, right?

00:48:49 It's a least absolute selection because we are using L1, which involves absolute value.

00:48:54 And it's a shrinkage operator, right?

00:48:56 It's LP norm.

00:48:58 So, if we have the absolute value of W1 plus absolute value of W2 less than or equal to a T value,

00:49:06 the corresponding feasible set is actually this, you know, rumble shape, okay?

00:49:15 Right?

00:49:16 So, actually it's not a rumble because you have W1 norm plus W2 norm.

00:49:21 It's just a square in this case, okay?

00:49:24 Right?

00:49:25 So, there's no factor in front of W1 or W2, okay?

00:49:29 So, it's actually a square.

00:49:32 So, now let's ask ourselves, right?

00:49:35 If the optimal solution of the regression, right, is right here, where is the optimal solution for the lasso regression?

00:49:44 Well, actually, it's like here.

00:49:49 Okay?

00:49:50 Again, the first time, you know, we go downhill and reach the first feasible point.

00:49:56 But there is a fundamental difference between the rigid regression and the lasso regression in the sense of their feasible set.

00:50:04 What is it?

00:50:05 What is it?

00:50:12 There's no corner on that circle, but there are four corners in this two-dimensional space of this square, right?

00:50:24 What do these corners mean here?

00:50:26 What is it?

00:50:27 What is it?

00:50:28 0?

00:50:29 Yes.

00:50:30 As Nami said, some W must be equal to 0, right?

00:50:36 Because, you know, they are on some axis, right?

00:50:41 So, that means lasso actually promotes a so-called sparse solution because some W will be equal to 0.

00:50:50 So, we've said before, you can choose your loss function in different ways.

00:50:53 One way is to make sure that the model is interpretable in the sense that it can select a small number of features that are important for the prediction.

00:51:01 So, if you prefer sparsity, right, then you can use L1, and there's a great geometric interpretation for that.

00:51:10 Okay?

00:51:11 It may not have more predictive power than the ridge, but it's much interpretable and more sparse.

00:51:18 Okay?

00:51:19 It's very useful for the feature selection.

00:51:21 Okay?

00:51:22 And, and the lambda, as I said, is a trade-off between these two objectives.

00:51:29 Okay?

00:51:30 So, now let's ask ourselves, right?

00:51:34 You said the ridge regression actually have, you know, formal analytical solution right here.

00:51:40 I said yes, because your L2 norm is also quadratic, just like the mean error, mean squared error.

00:51:47 Actually, no mean, just squared error.

00:51:49 Okay?

00:51:50 But what about LASSO?

00:51:54 Well, unfortunately, the objective function is, you know, well, it's, it's not that easy to solve.

00:52:07 Okay?

00:52:08 We're maximizing the concave function or minimizing its negative, which is convex, right?

00:52:13 So, local equal to global optimum.

00:52:16 Okay?

00:52:17 So, there is no closed form solution like the ridge regression.

00:52:23 And there's no gradient descent that works because it's not smooth.

00:52:27 Okay?

00:52:28 Okay?

00:52:29 Okay?

00:52:30 So, when you move that corner, when you move that constraints with cornered feasible set to the restraint,

00:52:42 then it ends up giving you non-smooth because you have a lot of absolute values, right?

00:52:47 You know, if you have the absolute value of W1, you know, you know what absolute value of W1 is like.

00:52:53 At zero, there's no gradient, right?

00:52:55 Defined.

00:52:56 So, it's not smooth.

00:52:58 So, then that's actually a problem.

00:53:00 Okay?

00:53:01 How do you solve LASSO?

00:53:03 So, this is a non-trivial problem.

00:53:05 And the first nice solution is called a LAS least angle regression.

00:53:12 So, it's implemented as a package.

00:53:17 And there's a modified version that's very easy to implement.

00:53:21 I would strongly recommend you, if you are interested in reading into this NAPS 25 paper from this,

00:53:30 we all know which hasty we are talking about.

00:53:35 Okay?

00:53:36 This is, again, one of the three authors from another classical book, okay?

00:53:41 For machine learning.

00:53:42 Okay?

00:53:43 All right.

00:53:44 Now, you said when P equal to 2, it's, you know, rigid regression, analytical solution is nice, right?

00:53:56 When P equal to 1, it's not analytically solvable or with gradient solvable, but there are ways to do that now.

00:54:04 But how do I choose P?

00:54:07 What if I have other choice of P, right?

00:54:10 So, you see that when P equal to 1, that's the shape you have symbol 4.

00:54:15 As P is less than 1, you have this kind of shape, right?

00:54:19 As P is equal to 2, you know, it's like you're blowing this box and then it's getting like a rounder and becomes a circle, right?

00:54:29 And if you keep blowing this as P equal to 4 or increasing, it's getting closer and closer to that, right?

00:54:37 Cube, but there's, it's very smooth here, right?

00:54:39 So, it's getting closer and closer to that.

00:54:42 So, my question is, what values of P would you prefer and why?

00:54:54 So, good.

00:54:58 So, one thing Nami said that is I still prefer convex optimization.

00:55:03 You told me that LASO was already difficult to solve even though it's convex, right?

00:55:08 Then it's definitely not my, you know, interest to make it even non-convex, right?

00:55:14 So, in other words, I probably don't want P to be less than 1, right?

00:55:19 Okay.

00:55:20 And then also, when P is bigger than 1, you know, there's no, this, you know, corner points anymore.

00:55:31 So, there's no sparsity, okay?

00:55:33 It depends on what you want, okay?

00:55:36 Sometimes people even use a weighted sum of L1 and L2 together.

00:55:41 They call this elastic net, right?

00:55:45 So, right.

00:55:49 So, what about lambda?

00:55:50 As I said, lambda is like a hyperparameter which controls how much you value the regularization versus the, you know, squared error, okay?

00:56:00 So, if lambda goes to zero, you just go back to the least squares fitting, right?

00:56:05 And, and then you see that, you know,

00:56:10 if you choose different lambda, you see if there's lambda equal to zero, the norm is like bigger than 10 to 12, right?

00:56:19 As lambda increases, you see that the size of W is also decreasing.

00:56:25 That's exactly what we want because we want to control model complexity for the sake of, you know, bias variance trade-off.

00:56:34 And we want to control in the size of W, right?

00:56:39 So that model complexity can be regularized for the optimal trade-off, right?

00:56:44 You see that it's indeed as lambda increases, the size is decreasing, right?

00:56:48 That's good, right?

00:56:49 But how do you know what is the optimal lambda?

00:56:54 How do you choose lambda?

00:56:57 How do you choose lambda?

00:56:58 Validation is one idea, yeah, right.

00:57:07 So again, if we don't consider, you know, the, the, the complicated cases including transfer learning or including small sample cases, right?

00:57:16 So in hindsight, there is optimal lambda, right?

00:57:22 Again, but you just need the procedure, right?

00:57:25 So you need to use something like cross-validation, as I said before.

00:57:28 You treat lambda as a hyperparameter, right?

00:57:31 And then you do this k-fold cross-validation.

00:57:35 And for each value of lambda, right, you just use that lambda and train your model for that loss function.

00:57:43 And you train your model and evaluate it on the validation set, this yellow fault, okay?

00:57:50 And I would recommend you to use a grid of lambda or discrete choice of lambda, which is more or less log uniform, okay?

00:58:00 In other words, there's, you know, more sophisticated analysis showing this shrinkage path, showing that, you know, the effect of the lambda is actually, you know, in the log scale.

00:58:12 So it's much preferable to sample uniformly in log lambda.

00:58:19 So in other words, you use a log uniform grid of lambda, so that you can have more or less uniform strength on regularizing the model, okay?

00:58:30 So that's something you should be all aware of.

00:58:33 So let's see any money points we have so far.

00:58:41 So today we talked about regression, right?

00:58:45 And we talked about two elements.

00:58:49 One is what model class you use.

00:58:51 One is what is the loss function you use, right?

00:58:54 So we also used this to show that intuitively, you can already use a complicated model class and potentially decreasing the bias.

00:59:14 But there's something that is changing that is a variance, okay?

00:59:18 And in the bagging case, we actually reduce the variance.

00:59:21 So there's a lot of things going on.

00:59:23 And the theoretical basis is actually the bias of variance straight off.

00:59:28 The core idea is that machine learning is not data fitting.

00:59:33 It's not least squares fitting, okay?

00:59:36 It's not about fitting to the existing data.

00:59:39 It's about minimizing the expected generalization error for the unseen data, right?

00:59:45 Even if you assume it's following the same distribution.

00:59:48 So in other words, you have to find a sweet spot between the bias and the variance, right?

00:59:55 So if your model is too complex, the bias is expected to be low, but the variance is going to be high and vice versa.

01:00:03 So if we can somehow modularize the model complexity so that it's a little bit biased, increased compared to the optimal point, but the variance is going to drop tremendously.

01:00:18 So the sum of the two is still going to be decreasing.

01:00:21 So that's the idea of regularization.

01:00:24 So in other words, we're going to include a penalty in the loss function to penalize the model complexity, right?

01:00:32 But we also learned that model complexity is something hard to quantify, right?

01:00:37 You cannot use the number of independent parameters that easily.

01:00:42 First of all, it's hard for you to figure out what are the independent parameters.

01:00:47 Secondly, this number of independent parameters is only about the model.

01:00:53 It's not about the data at all.

01:00:55 Whereas model complexity being too much or too little is relative to the data is kind of trying to estimate, right?

01:01:05 So then we learned that while we actually use the size of the learned parameters w, right?

01:01:12 Which is about both the model and the data, right?

01:01:15 So that size can be measured by the LP norm.

01:01:19 And we see that using the mean, using the squared error estimation.

01:01:24 We see that this can be reformulated as a constraint optimization.

01:01:29 And we see that with different LP norm, your feasible set actually has different shapes, right?

01:01:35 And then sometimes you do have analytical solution when P equal to 2, for instance, is math easy.

01:01:44 Sometimes you don't and it's even not welcoming gradient based optimization algorithms like P equal to 1.

01:01:55 So it's 1, but it has its value of promoting diversity, right?

01:02:01 By the way, by the way, with L1 norm, are you guaranteed to have a sparse solution?

01:02:16 Let's look at this figure again.

01:02:19 Can you imagine a scenario that the optimal solution is not going to hit a corner point?

01:02:26 Could it be like hitting any of this borderline which is not sparse?

01:02:38 It's still possible, okay?

01:02:40 So that's why I'm saying that L1 norm is promoting sparsity, okay?

01:02:46 I'm not saying it's guaranteeing, okay?

01:02:49 And let's come back to the summary.

01:02:55 And we learned that this choice of P is actually, you know, very interesting, right?

01:03:00 So we use this geometric interpretation and see that how these convexity sparsity are playing in a role.

01:03:07 And then in practice, how we regularize with the proper choice of the lambda, okay?

01:03:15 So with this, I'm, you know, done with today's lecture.

01:03:20 Is there any question?

01:03:24 Okay, if not,

01:03:25 if not,