Linear models remain essential in machine learning despite the dominance of deep neural networks because they provide a simpler theoretical foundation, are still widely used with limited data, and serve as the final layer in modern deep networks. Linear regression minimizes squared loss through the closed-form solution w = (X^T X)^(-1) X^T y, while classification uses logistic regression with sigmoid or softmax functions. Regularization techniques like ridge regression (L2) and LASSO (L1) prevent overfitting by controlling model complexity. The representer theorem shows that optimal solutions depend only on inner products between data points, enabling kernel methods that transform data into higher-dimensional spaces efficiently. Optimization algorithms like gradient descent, stochastic gradient descent, and Adam are fundamental to training these models, with convex optimization providing theoretical guarantees for convergence.
Lecture 1: Learning with Linear Models (Mário Figueiredo)
Added:All right. Okay.
So, uh, welcome to the 16th edition of the Lisbon Machine Learning School. Um, so you're currently in an auditorium from Technic. Um, the school is organized by Technical and by research labs associated with Technic. We're very grateful for the support that Technic has been giving to the school over the years. And before we begin, we have here with us the president of technique, professor class who will share a few words with us. Okay.
>> Hello. Good morning.
Thank you. So my mission here is quite simple is just to give you a very warm welcome to to this uh 2026 LC's MLS school. I was I I in in the last five or six years in I think not in the covid here in 2020 but I was here to to welcome the students and I think this this I was passing through the lobby and and hearing you talk and speaking with each other and I think there is a a great mood in this school this year. So uh let me just welcome to ISC to thank to all the organizers. I I will there is a number of organizers I will they are sitting here in front of me. So I just ask you to give them a big applause and uh thank you very much and I wish to you all a very nice week in this school here at Thank you. Bye.
I think they were expecting that I have more words to you, but in fact, okay.
Okay.
So, uh well, even before the first lecture here, so we have a couple of words on logistics.
Uh again so the school is uh organized by technical and by research labs associated with technical. So during this week if you like what you see um please uh visit us in another opportunity. So Technical has lots of activities related to the area and um yeah on this website for instance doctoral school at technical PT you can for instance find information about PhD programs um for instance related to these areas running in technical you can visit us also in the context of varmus mobility uh for small research visits there are several research units in technical that have activities in connection to machine learning and there's actually a a helis unit running here as well.
So, we are also very grateful to our sponsors. Uh I imagine that a few of you have scholarships. These would not be possible without uh our sponsors. This year we have as silver sponsors Zenesk and Fidly.
And um in terms of the organizers um so uh most of us will be here throughout the week. You will have a chat to to talk with us. Um you have here some photos. Now, of course, these photos, well, if you take a time machine, you'll be able to see these people. Uh, now you in during the week, you'll able to see people that much that are much wiser.
[sighs] Uh, so we also have a steering committee. Uh, again, I won't go over the names, but uh, several of the people in the steering committee are also organizers. We have a couple of external individuals as well.
And uh more importantly in campus you'll see people wearing uh blue shirts. These are monitors from the school. They'll be helping you find the different facilities here. They'll be helping you throughout the labs as well. Okay. One of the organizers Kamo is is coordinating uh these individuals.
Now uh in terms of logistics and the places where the school will take place.
So right now we are in this building.
Oops.
Well, I won't be able to use this, but we are in building two. Uh, so the civil uh engineering building, lectures are taking place here. The morning coffee breaks take place uh here as well. Okay.
In the afternoon, coffee breaks take place in the garden that is right in front uh of this building. And before the afternoon coffee breaks, you'll have uh labs. The lab sessions take place in another building, the informatics building basically on the other side uh of the campus uh in that direction over there.
Now I imagine that some of you have received this information by email. Uh there are a couple of channels used to discuss aspects related to the school.
So for instance there's um mailing list.
You have the address here. There's also a discord channel that you can join. uh you can use these channels to discuss um um um aspects of the school with other students with the organizers as well. So if you haven't done so already please try to to join this these channels okay most of the information that we'll be sharing throughout the week will be made through this.
Now in terms of the complete schedule for the school uh all the information is on the website. Um I have here the schedule for today but in most of the days u um events take place in a very similar way. So we have morning lectures from 9 uh a.m. and 12:30. There's a morning coffee break at the middle 10:30 and then uh at 12:30 there's lunch.
Lunch takes place in this building as well on the ground level floor uh in one of the corners. Okay. So the monitors will help you to get there. In the afternoon there are labs. Then in most of the days we have an evening uh lecture as well. Today there's a reception taking place in the garden in front of this building. Okay. The complete schedule uh is on the website.
In terms of internet access um several of you will have uh access through edome. I guess that's the easiest way.
Those of you that don't have ad home access, you can use um these other instructions that are shown here on the website. There are a couple of sheets of paper outside with this information as well. We'll probably place it on the website as well. Okay, so if you want, you can take a picture of this slide.
Okay, I guess we're ready.
And yeah, all this information is is is on the website as well.
Uh on Wednesday we'll have the social main social event. Okay. So there's a banquet taking place at this um place downtown called Kaza Dentu. It has been a tradition of the school to have the banquet there. I hope you enjoy it. Uh so the this QR code gives you the address. Um the location is posted on the website as well. Usually there's a group of students that goes from here to Kazadente walking on on Wednesday. Okay.
So you can't miss it. Uh if you want you can join this group as well.
And in terms of logistics, I guess this is it. Okay. So we can start now with the first lecture. Professor Mario Figured a distinguished professor in in technique with uh uh extensive and well-known work in signal processing, vision, machine learning will be giving this first lecture on linear models.
Okay. So, let's welcome Mario.
So, thank you Bruno. Welcome everybody.
Very important question before we start.
Anyone knows how to mute an iPad?
>> No.
share disable no.
>> Yeah, it was ready earlier today.
No.
>> What's down?
>> Yeah.
You have to come to the Okay, I'll do it from the computer.
>> Sorry, we have a technical glitch which will solve in a minute.
appreciate.
>> Don't connect to >> Don't connect to Don't connect. You turn off my window.
>> Turn off my lecture.
>> Lecture lectures.
>> Lecture.
You got a >> ship.
Sh.
Full screen. Full screen.
Desktop.
>> Yes. Now it's working. Sorry.
In the day and age of AI, there's still no these problems still arise whenever you want to connect stuff. So connections are very difficult. So welcome to the first lecture. Um so we've been doing this uh you're now in the 16th edition of of LXMLS. Uh we've been doing this for a long time. So things have evolved a lot as you know in the past 16 years.
So some of you were small kids 16 years ago. Um but a lot of things happened. Um so we're going to do to today start the school to start warming up your brains for what comes next is this uh sort of foundation lecture on on on machine learning. We're going to be focusing on learning with linear models and I will justify why it still makes sense to to talk about linear models as as a starting point for for studying machine learning. So this should move. Yes, it moves. So that it's a very simple structure for the for the for the lecture. We'll start with an introduction. Then we'll talk about regression which if you don't know what it is, I'm guessing most of you do and classification which I also think most of you know what it is. And then there will be a section on optimization for supervised learning because a lot of machine learning is is about uh in practice is about solving optimization problems. So let's look a little bit about this at this. So just a big picture of of what machine learning not all of machine learning but say classical machine learning. So you can divide it into into supervised and unsupervised. Oh by the way interrupt me ask questions. Okay I I tend to talk a lot so uh but it's okay please ask questions.
Fire alarm. No. Okay. So classical division of machine learning is uh supervised and unsupervised.
uh as you probably some of you know uh in in the supervised case we we have um the data that we see from which we do the learning is is precatategorized if it's a classification problem or there's a there's a known response that that should be sort of mimicked by the system and in this supervised side we have both classification and regression. The distinction we'll see it in a second more in detail is whether you want to classify things uh or if you want to estimate quantities or or collections of quantities could be from just a single number to a full image or even a video.
And on the other side we have unsupervised where the task is is much more um sort of abstract and unspecified. It can be many different things from clustering dimensionality reduction session many of the things.
We're not going to look at unsupervised learning. We're just going to look at supervised learning. uh and I very much like this painting which is sort of a supervision right there's a teacher supervising the students uh so this is the idea just to start with a little bit of art um in the beginning so this again is another just another global view of of machine learning we have now another blob down here which is called reinforcement learning which most of you probably have heard of uh or some of you actually may even be experts in it u which is about uh learning how to interact how to act in the world we're not going to talk about that at We're going to stay on the top right corner.
Supervised learning which can be as simple as predicting the the the fuel consumption of a car from a few of its characteristics down to classifying medical images like in this case um theoscopic images into into benign or malignant lesions. So there many many applications many many uh topics that are that fall into this topic of of supervised learning. So important question actually this question was inherited from Andre's slides why I just updated the the year and and a little bit tweaked the reasons why should we talk about linear models in 2026 where machine learning is completely dominated by deep neural networks which are very very nonlinear uh and of course there are many many reasons many good reasons uh so well first of all the underlying machine learning concepts are the same so it's the same problems that we're solving um although Some problems cannot be solved with linear models. The problems at its at their core are the same. So the theory is simpler both from the statistical point of view and optimization point of view. So we'll see a little bit of theory in in optimization not not a lot of theory or not any theory at all in in um in in the statistics side. It's still widely used especially when you have don't have a lot of data. It's still used there.
There's a very famous saying which I I had in a slide, maybe it's not as true as it used to be, which is uh when you are hiring when when you are fundraising for companies. When you're fundraising, you say that what you're doing is AI.
When you're hiring people to work, you say it's machine learning and in the end it's just linear regression. Um but it's it's it's a bit exaggerated, but it's not too far from truth. So they are a component of deep neural networks. So DNN's will be deep neural networks as we will see. uh and they are a natural starting point for studying machine learning. So it's kind of an analogy is like before studying brains it makes sense to study individual neurons and so in a sense a linear system is sort of like one neuron um in a in a in a very complicated system that could be a deep neural network. Another analogy which I like is a spherical cow. Have you seen this? Do you know what a spherical cow is? Who doesn't know what a spherical cow is? Okay. Wow. I thought everybody knew what a spherical cow. So spherical cow is an analogy used a lot in in in science to represent it's it's a it's a joke about physicists that would start a sentence by saying imagine a spherical cow. Of course there are no spherical cows. The idea is that the spherical cow simplifies and and and removes all the complexities of of the problem to put it in the simplest possible version from which we can start by understanding what's going on. So spherical so in a in a sense linear models are the spherical cows of of machine learning. and it's a cute picture. Uh so another reason as I was saying is that linear classifiers are are still present in in in all of modern machine learning essentially for example in classification if even if you're using a deep network a CNN whatever you want to use the final layer is a linear classifier. So this final layer is linear classifier and you can understand you can understand a deep network as a linear classifier preceded by a very complicated structure where the goal is to extract features from whatever you want to classify. Okay. And this is true not only for like distinguishes cat from dogs but also from to generating text. Okay. Um I I will justify this. So for example if you have a transformer this is now very famous picture. Everybody knows this picture or most of you know this picture on the left. So if you look this is the the original picture of the transformer in the 2017 paper and on the right is a decoder only model as you can see up there at the end linear classifiers. Uh so it's still there still a very important part of of even very sophisticated and complicated model models they're still there. Okay so are you convinced should we study linear models or just jump to the next lecture tomorrow. Okay so just uh let's set up notation. So this talk has some math. I I I'm a very strong defender that to understand things these technical types of things uh machine learning in particular you need to to look at the math. You need to understand the math formulations. That's how that's the only way to really understand what's going on. You can look at code but code is kind of masks what's going on. So for me at least the math uh version of things is the clearest one. Sometimes people are a bit put off because looks heavy but if you clearly and carefully read what's going on it's the it's the most transparent way of of expressing ideas uh that there is so input we will use throughout all the lecture input uh to the system will be called X little X uh and the big calligraphic X is the set from which the input to which the input belongs it could be I'm going to keep it really abstract it could be many different things be some text could be an email message, could be a face image, could be a collection of lab test results for a patient, could be the features of a credit card transaction, could be a sequence of words, could be whatever you want. Okay? And the output is the the the output corresponding to this input. For example, for a news article, it could be the result of deciding whether this um this news article is fake or true or if it's an email message to classify it as spam or or not spam and so on and so forth. So face image the identity of the person for the lab test results diagnostic of some disease for the features of a credit card transaction is it a fraud uh or is it a legitimate transaction and so on. So for and and of course for large language models nowadays uh for a sequence of words the output of the system is going to be the next word or the next token.
I'm not going to talk about tokens because I'm not going to talk about NLP at all but you will learn about that in in future lectures. So of course an input output pair is a pair of these things. It could be something like a news article together with a topic, a sentence together with a translation, a sequence of words or tokens together with the next one, an image partition into segmentation into segments. If it's segmentation image, it could be a noisy image and a clean image could be many many different things. So it's very very very generic. So of course the the goal of a model like this is to take an input and classify it and as as for example in the first picture on the left classifies emails as being spam or non-spam for example a regression problem where you estimate the quantity in this case would be estimating from from features of a patient estimating the length of stay in a hospital which would be very important for the hospital managers in a large language model it would be like taking the previous words and predicting the next one. So they're all fall in the same general formulation. Given some input, produce an output.
And of course, um the goal is to create this function genetically denoted here as H that goes from can I point is yeah, it's visible. Oh, it's Why is that up there? Cut.
Fernando.
any way of >> better now. Okay, sorry for that. Um, so it's a it's this function that maps from from the inputs to the outputs. So it's a function from X to Y uh that where the task is to predict some some predict the value for what the correct Y should be.
And let me start with optimal. I'm calling these optimal decisions because we're going to start in a ideal situation where you would know uh the joint distribution of the inputs and the outputs. Suppose you do know this. Okay.
In this case, if you know this, you're not in the realm of machine learning, you're in the realm of optimal decision theory. And there's a there's whole books about these. If you know the joint distribution of two objects and you observe one, what's your best guess of the other one? Okay. Uh and for these by best of course you need a way of assessing how good they are and this is done by a ubiquitous uh object of all of machine learning and decision theory which is called the loss function and the loss function is something that measures the loss that you incur if you decide yhat and the truth was why okay so it could be many different things there's no there's a lot of theory but it's outside of the scope of decision theory so decision theory and machine learning assume that sort of this is given for some reason. Uh and um once you have it, you can decide, you can formulate what you mean by an optimal decision. And an optimal decision is the function denoted as har. You can just read the first line if you want. The second one is just a detailed expression of that. You look for the har that minimizes the expected value of the loss across all distribution, a possible x and possible ys. And this is called an optimal decision. It minimizes the expected loss or expected risk and uh this function this function will belong to some set of allowed functions. It's or not or it could be an arbitrary function. However, of course, as you know the joint distribution of inputs and outputs is unknown. You don't know.
Suppose you well in any problem that you will face even assuming that it exists is a very strong leap of faith.
Typically even if it is if you assume and it's correct that it exists whatever that means the philosophical issue here you don't know it okay everything is okay uh and in and because this is unknown you need to resort to not decision theory but something called supervised learning which is what we're going to see so the idea is that instead of knowing instead of full knowledge of the joint distribution of inputs and outputs what you have is a collection of examples okay this would be say collection of of images of cats and dogs and the corresponding label. This is a cat. This is a dog. Okay, so the training data. Now the goal is to learn the optimal predictor not from the knowledge of the joint distribution but from the data from from this data. And there are two ways you can go about this. Okay, so there's the the generative approach which would be take this data estimate the joint distribution of the inputs and outputs and go back to the previous slide and go back to optimal decision theory. This is something you can do in principle.
some cases you actually do it. The other approach is to replace the thing that you would like to minimize which is the expected value of the loss which was in the previous slide right it was here expected value computed from knowledge of the joint distribution by the empirical version of this expectation which is just summing across all the data the value of the loss for each example for a given choice of what the decision function would be H. Okay. And this formulation is called empirical risk minimization because this is sort of called empirical risk. It's not the expected risk. It's an empirical version obtained from data. Okay. And this is how most of well I'd say all of supervised machine learning works nowadays. Okay. And this lecture will focus precisely on these uh discriminative supervised learning not generative. We're not going to go into generative formulations.
Okay. So now there's lots of um nomenclature that is classical and probably I guess many of you know. So what the difference between regression and classification in regression the prediction is of a quantity or a collection of quantities and a classification it's a category. Okay.
And even if the category you call it 1 2 3 4 5 which looks like a number uh the the the main feature of classification is that there is no order. So the the the the set of possible outputs has no intrinsic order. there's no reason why um making an error between a certain class a certain face and another face if they're classifi classifying faces of of people there's no natural notion of distance between these objects it's just a bunch of classes okay in general so in simple regression this output would be say a real number or a number between zero and one or a non- negative number or whatever uh so for example given a news article regression problem would be trying to estimate how much time a user will spend reading it. So you have in many websites like uh blog uh sites and stuff you have an article and on the top you have this estimated reading time 7 minutes and this is obtained with a with a model like this. It could be multivaried not only one number but a collection of numbers. Okay. And this can be now extremely generic. It could be an image. You could you trying for example all all the software that you have in your phone or in computers to say perfect your image like in Google photos like remove noise or increase sharpness or something like this is something like this. It's a method that takes in collection of pixels and produces another collection of pixels which are essentially quantities. Not they're not exactly real numbers because they're they're written with a finite number of bits but we can abstract them as being real numbers.
Classification could be can go all the way from just binary classification say spam detection is it a spam or not? Is it fraud or not for whatever or multiclass classification where you have more than two classes or even structured classification where the collection of possible outputs is very large and it's structured and you don't know a priority how how how large it will be. Imagine the classical example would be machine translation where the you have a small sentence some sentence and you have the output is again a sentence a sentence is a collection of words you have an finite number of possible uh sentences of each length but you don't know how priority which length the sentence will be because there are possible translations with different lengths and so all of these like machine translation caption generation image segmentation for is another example because given an image you don't know a priority how many segments it will have and [clears throat] so this is a structure classification problem.
So another another thing I want to contrast right now is is is feature engineering or feature representation.
Sometimes the the objects the inputs X are not uh addressed directly uh by by the machine learning system. They are there are features extracted like I've shown in the picture of the dog [clears throat] with the neural network extracting features for classification is or maybe was an important very important step for for linear models. So stuff like bag of words feature for text part of speech all a lot of things that uh Andreas uh worked a lot many years ago and many other people in this in in this group for example in computer vision sift feature so in I'd say up to 2012 2013 2014 most of computer vision and image processing conferences were about what are the good features that I should extract from an image so that I can solve a certain task say locating buildings or whatever. Okay. Um so many other types of of features that you can extract categorical, boolean, continuous. So decades literally decades of research in machine learning, natural language processing, computer vision, image analysis, speech processing on engineering what would be the good features. So experts in the in the domain of the problem would come up with good ideas on how to extract good features that would be useful for u or some task downstream task like classification or something or recognition or whatever.
So more formally a feature would be something like you take an object say an image and you apply to it uh a function fi which transforms it into a vector of numbers. Okay. Okay. And this is ubiquitous nowadays in in in machine learning. Of course, this could be a very high dimensional, maybe not, maybe depends on the problem. Uh feature vector, it's a vector. Okay. Um it's very common if you have categorical features. For example, if these features are words or tokens in a sentence, they can be represented still can be represented as vectors, which are called embeddings as as you know, I'm sure many of you know. Um and and this is absolutely ubiquitous nowadays. Sorry, embeddings play a very central role in modern machine learning. How to represent objects, even if they're not naturally vectors of numbers, how to represent them as vectors of numbers.
And this makes a huge different because it puts everything in the math of real numbers and vectors and algebra and all that and optimization. It's much simpler than dealing with structured things like classes and categories and and logical objects. So in a sense feature engineering um is sort of alchemy because it requires deep domain knowledge. So a lot of people in in early NLP collaborated a lot with linguists because they have deep knowledge of the structure of language and some good knowledge of of how human vision for example or primate vision works for computer vision and so on.
It's usually very timeconuming.
On the other hand, on the other hand, it's it has an important feature that it it well important aspect which is it allows incorporating knowledge. So you can bring some some knowledge of the world of the problem into the into the into the structure that you're going to develop. It is a form of something called inductive bias. You're you're forcing your solution to have a certain type of characteristic if if you know that's good. Um it's still widely used in practice especially if you don't have enough data to learn good features. And of course the modern alternative uh which is either called deep learning or representation learning uh and this will be the talk this will be the lecture tomorrow of a big garage. So tomorrow morning you'll be learning about u deep learning. So for for some reason that you probably some of you know the the main or one of the main conferences in deep learning is called ICLR or I clear and which stands for international conference on learning representations and so learning representation is sort of synonymous with deep learning. Uh it's it's arguably a good idea but it it is what it is.
Okay. What about um self-supervised learning which is all the rage. I don't know if you maybe of [snorts] some of you have seen uh Yan Lukun very famous uh researcher um one of the pioneers of uh of of deep learning has a very famous slide which is a cake I I didn't I don't you won't see the slide I don't have it which is a cake it says the data cake and it says like the the supervised learning is the icing on the cake but the real the real meat of the cake let's say it's inside it's the cake itself and that you can only access using self-supervised Okay. So we will not talk about self-supervised learning. I just want to say because I get this question a lot. So you talked about supervised unsupervised. What about self-supervised? Well, self-supervised is essentially just supervised learning.
Okay. But with programmatically defined training outputs. So it's you don't it's not humans that say this is a cat, this is a dog. You create other tasks for which you can generate labels in an automatic way in a programmatic way with a computer which is do not require uh human intervention. For example, next word prediction. It's very easy to construct the data set. We have huge huge amount of data. You take sentences, you mask the next word and you train a system to predict the next word and you can do it at scale because you don't you don't need humans to say what the next word is. The word is there. You just pretend that it's not. Um so this is how large language models are trained. Um and so this is one classical task. So there are many many other tasks. So there's there's huge literature on self-supervised learning for example in in vision in image you can train a system these are called pretext tasks why are they called pretext task is not the real task you're interested in it's something that you use uh before to to train the system and I'll explain what that means so for example image in painting you can cover a little piece of the image and train the system to recover that that thing that was covered and you don't need a human to do it you can do it programmatically or you can colorize you and remove color and have a system that is trained to recover color.
Or you can rotate the image uh and and build a system that learns how to detect the rotation and or estimate the angle of rotation or something like that. And so how it works you have uh these on the left side you have this pre-training uh unlabelled data you and you want to acquire you want essentially to learn the feature extraction that is good for some task but this is the expensive part. So you you build a classifier let's say or or some regression problem on a predex task which is not the task that you're really interested in. Okay.
And then when it comes the time comes to actually use your data the task that you're interested in you use the same feature you use the same feature extracting the same function file and now you have a task specific data which is now maybe labeled by humans but in a much smaller amount but then you don't have to train this difficult part which is the feature extraction. just learn the predictor you can fine-tune or adapt or update or whatever. Okay, so this is the idea behind self-supervised learning but we'll stay on the left side. Uh let's just see it as a self just a supervised learning pro.
Okay, so of course both phases of self-supervised learning are essentially supervised learning in there are other more sophisticated things but it's okay.
Okay, any questions? This is just introduction. Any questions? No. Okay, linear regression picture on linear regression. Okay, everybody done linear, everybody knows what linear regression is. You just have points and you want to fit a straight line or some some line through them. Um, so actually I had this sentence I thought I had removed it but I haven't. Uh, this is a bit outdated I'd say but it's still fun. Uh, so when you're fundraising it's AI when you're hiring it's machine learning. When you're implementing it's just linear regression. So in many in many problems that this is true. Um another aspect and I always need to have an XKCD cartoon in any talk. So here's one. Uh so linear regression may be nonlinear. Okay, which sounds contradictory but it's not. We will see in a second. And this is extremely important actually have it this here because of the inductive bias.
Okay. So this example I'm not going to go into the detail of this. This is a cartoon. I'm sure many of you know this cartoon site XKCD. There's a book and and all. Uh so if you have some data and the the the function that you decide to fit to the data for the same data will carry different messages. For example, in this case there have this these points you fit a straight line you say hey I did a regression there's no message but now if you if you if you fit a quadratic function or a logarithmic function they both seem okay.
uh but uh so this one kind of seems to suggest that the whatever the phenomenon is accelerating what whatever these while these ones kind of suggests that it's slowing down. Okay. And it depends on your your choice and if you fit an exponential it seems to be growing even more and so on and so forth. Okay. So the the the things that we choose the problem that we choose to solve to do regression or classification or whatever brings this um so-called inductive bias sometimes in a in a subtle way and we need to be careful with that.
So what is regression? Well, I guess many of you know um in a nutshell it's just the task of building a machine system a program. I I don't like the word machine that's why I put it quote unquote. It's not a machine, it's a program um that predicts or estimates or guesses a quantity from other quantities or features. Okay, so this is the picture. You have an input p uh numbers, quantities, labels and you have some machine that predicts some output. Okay, this is of course a fundamental tool.
There are very few scientific papers that have data that do not include some sort of regression. Okay, almost all plots that have data points on some experiment on any field and and then there's some conclusion about some functional dependency of these of these data could be many different things. So it's it's a fundamental tool in data analysis in mo much of science everywhere and of course in engineering.
Okay. And as as I said in the beginning we're going to attack this from a machine learning perspective not from a decision theory perspective. So we assume that we don't know the distribution. We have data. Okay, we have a collection of examples, inputs, output, input, output, input, output.
And the goal is to find the best predictor, the best decision that for a new sample will give you a good estimate of what the corresponding y is for a given x.
And just a small caveat on the notation, I'll use bold uh to denote a vector or a matrix. Um, but not always necessarily.
I we we'll see have a few exceptions just to keep it clear. So [clears throat] what is linear regression? So linear regression because we are in the linear models u lecture um is when the only type of function that you allow is a linear function actually in the fine function which is which is the following. My prediction is going to be some offset w0 plus a linear combination of the components of x. Very simple.
I'm going to this can be written in many different ways. This is my favorite one in linear algebra notation wranspose x or inner product. In more mathy more abstract version this is another notation for inner product the weights times x and in machine learning this is the more machine learning type of notation which is with the dots. So they're all the same. Of course I f I prefer this one. U sometimes we use this. This is more generic because this also works for infinite dimensional objects and this is the more current [cough and clears throat] the more machine learning type version because of the dot product because inner product and dot product are the same. So the standard loss that people use remember we need to to do to do supervised regression we need a loss function. We need to know how how serious a certain error is. If if the true value is y and I predict y hat how bad is that? Um and the standard one is the squared loss. [snorts] Okay. Any reason why this is good?
Anyone knows why we use squared loss?
Almost always.
You're still shy. I'm sure many of you know the log likelihood of what?
And the what assumption?
Yes.
Yes.
>> Perfect. That's perfect. There's one word missing that's very important.
You need Gaussian assumption on the noise. Yeah. So the square comes from the Gaussian. the sum that fact that you can sum the losses across the data set comes from the independence as as you said. Uh the fact that it's a square comes from the assumption that the observation is some true value plus some gausian noise. [clears throat] Um we'll we'll see in a second. So the empirical risk is just take whatever the for a given choice of w and w0 just take the estim estimate which we'll call yhat compare it with y compute the difference square it sum across all the points divide by n if you want it's not important and this goes by many different names. So from a machine learning point of view, this is usually called empirical risk. [clears throat] In statistics, this is usually called the residual sum of squares. Of course, it's the same. And um empirical risk minimization or list squares because I'm minimizing the squares. They just different names for the same thing. It's just what is the value of what is this vector w and this value w0 that minimize this quantity that minimize this square this sum of squares. [clears throat] So the statistical assumption this is what we were seeing right now that the assumption is that the inputs are deterministic fixed given I'm not going to model them some some given them to me the y's are conditional independent as you said very well given the x axis so each y is an observation of a corresponding x and they're all independent from each other sorry and the observations yi are gausian noisy versions of some ideal clean value which you would if you knew the correct W and the correct W0 okay and with some noise and this noise has zero mean and and variance sigma square okay which means that don't want to go too much into this but that that I'm using this notation to mean the density the conditional density of the response given the input is a gaussian where the mean is the clean output and the noise variance is sigma 2 it's very simple now as you said because everything is independent the joint density is just product of all of these.
Now, as you said also very well, you take the log, you transform the product into a sum, and the exponent, I'm not going to write what the exponential of a Gaussian looks like, but Gaussian, as many of you know, is a some constant exponential of squares. Once you take the log, you just get the squares up there in the exponential and you get that expression. Which means that uh this le squares estimate or empirical risk minimization is the maximum likelihood estimate under this assumption that my observations are noisy versions of clean values uh that were contaminated by gausian noise.
Okay. So a nice picture uh from this very famous book by Hasty Tip Shirani Freriedman um elements of statistical learning which is from 2009 um yeah I was here it's covered and so this is a nice picture because it shows all these elements so if you're doing linear regression say in two dimensions um you're essentially finding this flat surface that best fits the points that you have which are those red points So when when the x1 and x2 when the the components of each x of each ele each point is zero which is exactly here the prediction is w0 right because there's this wrpose x is zero just get w0 that's w0 and these u these um vertical uh lines are the distance between the prediction the prediction the predictions are all on the surface this is the predicted function And the distance between the points and the prediction are these vertical lines.
Okay? And these vertical lines if you square them you get and you add all of them you get the total list squares total total squared error loss of residual sum of squares. You can if you if you like if you have a if you like physics intuitions you can think of these vertical lines as elastic bands because elastic band the energy if you anyone from physics you know hooks constant you know what hooks constant is as you elongate a band or or a spring the accumulated energy is proportional to the to the square of the length and so essentially the the the the optimal solution is the one that minimizes the accumulated energy in these elastic bands.
Okay, it's a nice physical analogy, but it's not very useful in practice, but it's just to understand it. Okay. Um, so it's very annoying to have always this W plus W plus. So there's a classical way of getting rid of this W0 plus, which is attach an extra component to each X I to each each object, each sample will have an extra component which is fixed at one. Okay, we don't touch it. So now the the vector become P plus one dimensional instead of P and you put W 0 inside W.
Of course now when you compute the inner product between that vector and that vector you have W0 plus the rest the other rest of the inner product. This is very common. So it's the offset or bias is absorbed into the inner product and does everything becomes a bit simpler.
Um and so from now on I just mostly ignore W0. I assume it's absorbed. There are other ways to get rid of W0 but this one is the simplest one. Um okay so it's very common next step when you learn the things is okay this is bit I have sums and squares and stuff this of course is begging for a linear algebra notation and this is what what we do. So you can write this sum of squares of blah blah blah as in this very nice and much more compact linear algebra notation where y this y bold now is the collection of all the responses have n of them because you have n examples and this matrix x which has uh p columns by n rows so n by p has as many rows as examples as many columns as the dimensions of x and you can write so x * w is W are the weights. When you multiply the weights by the matrix, what you get is the predicted value for each sample. And now if you compute the difference between that predicted value and the observed value and you square and you sum everything when you sum squares of a vector, you get theian norm as you know square norm. So this is written in this way. I'm sure many of you have seen this before. And so how do we minimize or want to minimize a function? Minimizing a function uh is done by computing the derivative and setting to zero. In this case, everything is simple because it's just a square. And so in a multivaried case, which is this case, W is a vector. You need to compute the gradient, which is just a collection of all the derivatives with respect to each component of W. You compute this gradient. Now, a little bit of linear algebra and and calculus for for vectors and matrices shows that this is just this. This is exactly the generalization of the derivative of the square. when you comput the derivative of ax^2 is 2 ax um this is exactly it um in in in the multivaried case and so you want to compute the gradient and set to zero to find the minimum it's easy to show that we'll come back to this later that this is a convex function oops so it's a convex function it has a minimizer uh you just need to find the minimizer by looking at the gra where the gradient is zero so you set to zero you set the gradient to zero and you get when you equate equate these thing to zero, you get a this linear system. This is a linear system of equations. If you if you look at it carefully, it's xrpose x w equals xrpose y. Uh and so the solution is this and you can just compute it this classical linear algebra problem by inverting the system matrix which is xrpose x. And so xrpose x inverse xrpose y is the solution to the le squ problem. This is a very classical thing. this come this is I think Gaus already knew this um I yeah I think he did I'm sure it is uh and of course this is only possible if xrpose x is invertible okay so you can think of this system here this is a linear system of course of how many equations how many unknowns how many unknowns do we have it's a dimension of w All right. So the system is a a system with P well dimension of W is P. So it's system of P equations in P unknowns and that's okay because you can you can solve it you by just invert the matrix. Now if it happens that some of these equations in this system are not linearly independent as you know then you cannot solve the system then it's undetermined. Okay. Or if you have more unknowns than equations then again that you cannot solve it. There are three conditions under which you can solve this like this. One of the things is that n needs to be larger or equal than p. So you cannot solve you cannot find le square solutions if you have fewer observations than the size of the parameter that you're estimating. This would be an underdetermined system.
There are other ways to do it but we'll see about that.
Okay. So a classical this is from this would be like a from a statistics class basic statistics book when you're doing regression a quantity is this R2 which is called the coefficient of determination which kind of assesses how good uh your linear regressions are. So you do this by computing two things. So one of them is called the total sum of squares and I I'll I'll illustrate it with a picture. This is it. So suppose you have those five or four points and you want to do linear regression and you do the regression on the right and you want to see how good it is. How how well does it fit the data and one way of doing it is this. So the total sum of squares up there is the distance is the square of the distance between each point and the average of their y values.
Okay. So each of these distances is these um distance between y hat y bar the average and each of the y's and squaring means computing the area of the square with that side. So if you sum the pink areas of these squares you get something called total sum of squares.
Now you do the regression in this case linear regression. And now what you do is compute the residual sum of squares which is so once you have the line you comput the distance from the point to the line you square it which means computing the area of that little blue square. And now of course the smaller the blue is with respect to the pink the better the better this points fit the data the line fits the points. And this coefficient called R2 expresses precisely that is one minus the ratio between the uh sum of squared residuals and the [clears throat] total sum of squares. So the smaller this is with respect to this the better the higher R2. Okay this is sometimes also um referred to as fraction of variance that was unexplained. So this variance here, this this these blue distances are is that variation of the points that is not fully explained by [clears throat] this linear regression. And here's another XKCD cartoon uh where the some researcher did this linear regression fit to those points. He got R2 0.06 which is really low. And so is the comment is I don't trust linear regression if when it's harder to guess the direction of the correlation from the scatter plot than to find new constellations on it. It's just a joke, not my joke.
Okay.
So another important object in in linear regression is something called the the hat matrix or the projection. Okay, what is this? So essentially this point will give you I'm going to show it here. So exactly at the same x values where you have your training data what is the value that's on top of the prediction?
What is the predicted value for that same x? What is the predicted y for that same x? Okay which is called yhat.
And it's very easy because we know that the clean values should be something like w * x. Those are the predicted values. So once you plug these le squares estimate of w there which depends on y of course and you multiply by x you get yhat okay which is the predicted y values and this because you know exactly how this is computed is xrpose x - 1 xrpose you just multiply on the left by x and you get something which is called the hat matrix. It goes by the name of hat matrix which is a bit of a stupid name because it puts the hat on y. So you take Y without hat and you get Y with a hat. So it's the matrix that puts the hat on Y.
Sorry, I need water.
Okay, so this is a projection matrix. It is item potent in the sense that if you apply it again, nothing happens.
Okay, of course, intuitively that's obvious because if you take the x values and you project them on the line that you just estimated, if you project again, nothing happens because the points are already on the line. Okay, that's the the intuition. Another way of seeing it is that what you're doing is finding the the the the points that are necessarily in the range of x. What mean what does it mean to be in the range or the span is you want y the vector the vector y to be some linear combination of columns of x because when you multiply any matrix by a vector you get a linear combination of the columns of x. So you're looking for what is what is the the the projection what is the the vector in this in the range of of the columns of x span of columns of x range of x that is closest to my original y. Okay. And this can be written in this way. It's not not super important now. It will be in a [clears throat] second this called. So this is your orthogonal projection. So there's a picture that shows what's going on when you do linear regression.
Uh this picture is in Rn. It's not it's not in the dimension of the point. It's in the dimension of the number of samples. Okay. So in this case we have three we are in three dimensions. It's a picture. It's a threedimensional picture which means that we have three points.
at a very simple regression problem with three examples. Okay, this vector Y is the responses of the three examples. Y1, Y2, Y3. These are the the the components and we only have P equals 2. We only have two U X is two dimensional. So we have only two dimensions. Okay, so there are two only two columns in X. The X matrix has only three rows but two columns. Okay. So in the in the maximum the response can be in a space of dimension two because there are only two columns. Okay. And this is the projection. So this is the projection that gives you Y which is somewhere in the space generated by the two columns of the of the of the design matrix of the matrix X. Okay. So this is it's important if you want to deeply understand linear regression you need to kind of understand this this picture.
Okay. Okay. So now as I said in the beginning and I even showed the the XKCD cartoon on [clears throat] nonlinear regression.
How can we transform these in a nonlinear regression tool without making it more difficult? Okay, it's possible to do it's very simple. I mentioned this already. You just replace X with five of X. So you have some operation that operates on your vector x and produces another vector maybe in this case with dimensions um where typically 50 is one. Remember why we have these one of the components of the vector should be one to get take care of the offset.
Um and these components of x of phi are often called features. Um and phi is usually called a feature map. Okay, this could be for example the final layer of a deep network. Okay, so you have an input whatever it is an image a signal whatever and the role of the whole of the network is just to compute these five values which are the inputs to the final layer which could be classified or regression in this case it could be regression okay so you can think of all of these as just computing these functions five and we're not going to see how to train this we're just going to see how to estimate these W's which is what we're doing so the the other part training all of these will be uh today's tomorrow's lecture topic.
Okay, that's what I just said. So nothing changes essentially because now you can still write you can still write the same objective function. It's still the sum across all the data of the square of the difference between the observed response and the predicted response. And now the predicted response is a linear combination. So Wrpose of the features. just w1 * w 0 * 5 0 w1 * 51 and so on that's all and so you can still write it in the linear algebra notation standard linear algebra notation if you just redefine what the matrix is now this matrix instead of having these x values what it has is the transformations of the x values so basically it's the same actually nothing prevent you from just saying that the x values themselves are transformations of something else so this is actually a little bit of a redundant notation But um it's it's common to do to to call the attention and to make this transformation explicit and visible in the notation. Okay. So again if you're looking for the least square solution it's still the same. It's xrpose x - 1 xrpose y. It's a very famous u very famous expression. This also goes by the name of ordinary list squares or os.
Okay. So it can be many many different things. For example, if you want to do polomial regression, the transformation in in the real lines is just fit a polomial to points, what you do need to do is to compute powers of each point.
Okay, if you take that one, as I said, we need to start with one because of the offset x itself x^2 x to some power k that you that you predefine.
If you want to do order k polomial in R2. Say you have to fit a polomial to two dimensional data the transformation will be all the monomials of order up to k. So 1 x1 x2 x1 2 x1 x2 x2 and so on.
Okay. All these and then your function will be combination of these some linear combination of these is a polomial in R2. In RP it's just the same. It would be just a vector of all monomials of degree up to K. Okay. This grows exponentially fast. So you don't really use this a lot but you use it in low dimensions quite quite a lot actually.
Another [clears throat] type of nonlinear regression which is very common and it's also actually used to to to understand deep deep networks. It's radial basis functions. Okay, radial basis functions. I'll I'll show you a picture is just this. So each of these say think of this blue line here or this blue line there. It's just a little gausian blob located somewhere. Okay. And the goal is have you have your points these blue dots and the goal is to write these approximate these blue dots by a function that can be written as a linear combination of gausian functions in different locations. Okay, that's all.
So this more more abstract view each of these function is just some function. It could be gausian. So exponential minus square of this of the distance between the point where you are and some location. Okay, this is an example u very simple example. What what we have here the red the final line which is this red line is the sum of all the others. Okay, including this flat one which is the constant which is sort of an offset and they are already multiplied by the corresponding constant. the the original ones were this a blob here a blob all possitive blobs and then some are multiplied by positive numbers others are multiplied by negative numbers this would be the w's and in the end the total sum is this red line okay this would be called RBF regression radial basis function regression any questions okay regression also known as weight if you're a deep learning Um if the rank of the matrix remember what the rank is is the number of nonzero singular values of a of a matrix is less than p. So remember it's like if you have linear system of equations that will give you the weights but this linear system of equations has either fewer equations than unknowns or it has as enough equations but they're not independent. Okay, in this case you say that the rank is is deficient. It has a deficient rank and you cannot compute the le square solution because system has no solution. Okay, [clears throat] which means this matrix does not exist.
You cannot invert this matrix. What's the classical solution to solve this?
It's called bridge regression and it amounts to adding the norm squared of w to the objective function. So the objective function before for le squares is just this part here. If you know that this cannot be invertible, it cannot be inverted because it would be the minimizer of this. Minimize this by inverting this matrix in as we have in the previous slide here. This we need this object. If you cannot compute it then you add this and it's very easy to do. It's just you comput now you repeat the procedure you compute the gradient.
The gradient of this part is just lambda times the identity. And so what happens is that you're adding an identity matrix to this matrix xrpose x. Okay? So if you know a bit of algebra, you know that the igen values of a matrix time plus lambda* identity are the original values plus lambda. This all of the igen values go up by lambda. And if this matrix this matrix is positive semidefinite so it has no negative values. It may have zero values which is in the case when these rank division sorry singular values but none are negative. So it's either zero or positive. If you add lambda they all become lambda or or or something plus lambda. So they all go away from zero.
So the now this system this matrix is invertible for sure for any lambda larger than zero. And so you can you can compute rig regression always. It's what I was saying xrpose x is positive semidefinite. So this is invertible for sure if lambda is larger than zero. So this is a trick can also be seen as a basian estimate of w under some gausian prior we come back to this. So this was invented and reinvented many times and goes by different names. Nowadays it's called weight decay. It statisticians typically call it penalized list squares. In signal processing it's called ton of regularization. In approximation theory it's called L2 regularization. There are many different name. There are more names for this but it's all the same. It's all a linear algebra trick to transform a matrix that's not invertible into a matrix that's invertible. Okay just by adding something to the diagonal.
very very simple.
Um okay it happens in actually in practice that even if uh the least square solution can be computed sometimes the ridge estimate or the one you obtain like this is better it has lower MSE this is just this is from Kevin Murphy's book so this problem is I'm going to try to fit 14 order 14 polomial to 21 points you can do that it's not a lot 21 points is not a lot order 14 polomial seems really exaggerated it's going to be very wiggly as you see there. So this is essentially the list square solution is for logarithm of lambda minus 20. So it's essentially zero and it the solution is very wiggly. If it if lambda was actually zero this function would go exactly through each point it would be very very wiggly. Okay no not exactly because the order is 14 but close. Uh and this is what you get on the bottom left. Um if you use lambda log of lambda minus 8 so it's a bigger lambda. Okay.
And of course you get a much smoother function because you're you're forcing the weights to be smaller essentially.
And on the right what you have is um on on the on the the blue line is the train MSE is the residual sum of squares that you get for different choices of lambda.
This is log of lambda. Okay. So when you have log of lambda really negative which means lambda very small the residual sum of squares is small because you allow the function to wiggle very much to go very close to each point. So you have a very small training error. But then if you sample suppose you know that there is some true underlying function you sample more points from that and now you test each of these functions which is called test MSE. So test MSE is the red line and what we see is that the the behavior of the function is like this which means that the the test MSE is minimized not for zero lambda. So it's not a monotonically increasing function that says the bigger the lambda the worse. It's actually there's an intermediate value of lambda that's the best one. Okay.
And this is a lot of a lot of work in this area is how do I come up with a good lambda? Okay. How do I choose the regularization constant actually this is an illustration as you will see of something called the bias variance de composition. Okay. In any of these problems there's something called the bias and something called the the compos the the variance which I will illustrate in a very very simple case.
Okay. So as you I'm assuming you know these basic statistics and basic linear algebra and basic statistics you know that the variance of a variable it's the expected value of the square minus the square of the expected value. You all know this yeah basic statistics okay which means that when you're computing the MSE which is the expected value of the square so expected value of a square is the variance plus the square of the expectation. Okay, if you move this minus towards the other side here, which means that the MSE mean square error is the variance plus the square of the of the difference not this not the expected of the square but the square of the expected value and this is called the squared bias. So the variance and the squared bias the mean square error has two components. One is the variance I will illustrate it with the picture.
Another is the the squared bias. Okay, let's go into this picture first and then I'll come back to this one. Suppose what what does this mean? So suppose you're doing linear regression that so suppose the true function is this quadratic function there and you have three different training sets all extracted from this green parabola plus a little bit of noise. You have training set one, training set two, training set two. Okay. And then you fit um straight lines which are order one polomials to these points. So they're all very similar. So they don't wiggle around a lot, but they're all very wrong. Okay, if you compute the expected val the the difference between the function that you estimated and the true function, it's almost everywhere pretty large. And so if you square it, you get a high bias.
So it's a very biased function estimate although it has very little variance because it doesn't float a lot. On the other hand, now if you do very very wild approach which is just let's join the points by a straight line. So take all the blue points and and say that my function is this wiggling line that goes like here which goes exactly through each point. Okay. Now there's very low bias because on average the difference between these different points at at each location at each x value the average of the difference between these and the true function is small. Some are above some are below. On average they're not too big. Okay.
So the variance is very the the the variance is is the difference is is low.
the bias is low but the variance is high because that if you square everything before computing the average which is the other way around you get a big variation you get a lot of fluctuation okay so low bias high variance a lot of fluctuation although on expectation everything is okay high bias low variance not a lot of fluctuation but it's very wrong okay and here this is for a simple example so these kinds of curves always look sort of like this. So, um the the variance always goes down as you increase lambda because you're forcing you're you're shrinking the the coefficients to go close to zero. The bias goes up because you're forcing the function to be simpler. So, it doesn't have the enough flexibility to feed the data and there's a sweet spot somewhere which is the optimal um value of the regressation parameter um which needs to be chosen.
Okay, this is a picture by the tutorial by Sebastian Ra Rashka from uh University of Wisconsin. Some very nice tutorials on machine learning online.
This is a nice picture. Okay, so how do you do it? One practical way of choosing this parameter is something called cross validation. I'll probably skip the math which is quite simple actually but I'll just show you the picture. So the idea is the following. You have a training set with say a thousand points. You do the regression only on 900 of them and test on the other 100 and then you repeat this say a number of times say in this case it's 10fold CV so you repeat it 10 times for each of these you train on these and test on these then you train on the gray ones test on the blue and so on and then you average and then you find for each lambda you do these and then you choose lambda that minimizes this average quantity actually I'm not going to do this. I'm not going to explain why, but in linear regression, there's a way of doing this without having to do it. Okay, there's a way of doing this analytically which is extremely powerful called generalized cross validation where you can do it leave one out cross. Leave one out cross validation means the test that you leave out is only one point. Okay, so suppose you have a thousand points, you [snorts] do the regression on 999 and test on one of them and then you do this for every point. Okay, which seems to be extremely expensive because you would need to do these a thousand times if you have a thousand points. But in linear regression, there's a way of doing it using analytical tools, using tricks from linear algebra where you only have to do the regression once and you get this function for you get this for free.
So if you're interested, there's just look it up called generalized CV generalized cost validation.
Any questions?
So sort of this is the basics of linear regression up to bias varian composition and um and finding the ridge regression and finding the optimal ridge parameter. Now we're going to sort of jump a little bit. This is not so standard. Maybe if you took a a linear regression if you studied linear regression say in a statistics course or in the basic machine learning course you probably have seen everything up to here. Who has seen what we have seen up to now? linear regression CV. Okay, good. So maybe this part you are not seeing which is how do we write this in dual variables? What what do you mean by dual variables?
Okay, so suppose that um we're trying to do ridge regression. So this is the system that we're solving, right? Remember we invert this matrix and multiply it on the other side to get the W ridge. Let's rewrite this in a different way which is let's take this lambda* identity w okay leave it on the left side and then divide everything by lambda and move everything else to the other side. So this is xrpose y which is here minus xrpose xw which comes xrpose xw comes on the other side. So it seems like a stupid idea because now I have I had such a nice system which I could solve by just inverting this matrix. Now I have my unknown on both sides here and there. Why did I do this? Just for a simple reason that I can show this shows explicitly that if I just call these which I don't this y minus x w I just call it alpha which is okay. It depends on w but that's okay. It shows that w hat. So this the solution to this problem will have the form xrpose something times a vector. Okay remember what xrpose is. So X this big X matrix is the matrix that has each and each each point in training [clears throat] set in a row all rows. So X transpose is transpose of these. Okay. So it's now the columns are going to be data points.
Okay. In in X the rows are data points.
In Xrpose the columns are data points.
Okay. Which means that W hat is a linear combination of data points. Okay. which is what this form reveal. It reveals that your W in linear regression or ridge or list squares or or ridge is a linear combination of data points. It's always a linear combination of data points. We can actually solve for alpha but it doesn't really matter. It's whatever it is. Okay. And so written in a in explicitly it says that what reach is some linear combination of the x i of the points in the training set multiplied by constants alpha i. the linear combination of rows of X, columns of X transpose. Which means that when you want to predict an estimate, you want to predict the response the output at some point X. When you compute the inner product between this point X and your W estimate because this is like this. When you multiply this inner product with this, inner product with the sum is the sum of the inner products and you get these which means that the response is a linear combination of inner products between your points and the point in the training set. Okay. Uh so um this is very um very relevant as we will see in a second because it shows that everything you need to do with your points is in the product. It's nothing else. There's no other operation involved. Okay.
um that go back to this is the same same equation.
So we have the expression for alpha there. So alpha is 1 / lambda y - xxrpose alpha. Once we replace w by xrpose alpha and now we can solve this.
This is a linear system. We can write it again in a convenient way by putting everything alpha on one side and everything that does not have alpha on the other side. And we can solve this problem. It looks very similar.
It looks very similar to the ridge regression. Ridge regression remember I'm going to show it again just so that you don't forget. It's xrpose x plus lambda i. If I want to solve this, I need to invert this matrix xrpose x plus lambda i. If I want to solve this instead of xrpose x is xrpose which is in the other order. So where wherever whereas xrpose x is a p byp matrix, xxrpose is a n byn matrix. Okay, I'll have it this. So this one is an n byn inversion.
Okay, and this one is a p by p inversion.
And so which one will you choose? It depends. If you have a big data set but where p is not too big, you can choose this one. It's much smaller. But if you have another situation where P is very large, you have lots of parameters but you don't have a lot of data, you can solve this one which is much much smaller. So you know that inverting matrices if you want to invert it analytically is a cubic operation. It costs the computation cost grows approximately with a cube with the third power of the size. So you should always choose uh the one that is smaller and they both exist because both matrices this and these are positive semidefinite. So once you add lambda i um the matrix becomes invertible. Notice that this lambda i here and this lambda i there are not the same size. So this identity matrix needs to match the size of this matrix. And and the same happens there. Okay. This matrix not xrpose x but xrpose is called the gram matrix. If you any of you have studied kernel methods you've seen it a lot. It contains all the inner products between all the pairs of of elements. So it's a square matrix of size n by n. And in position 7 n it has the inner product between x7 and x9.
It's just all the inner product between all pairs of examples in the training set which is called the gram matrix. So now question is this a particular feature?
So the fact that W is a linear combination of data points is this a particular feature of of rigid regression or is it a more general property actually it is a more general property uh it's given by something called the represented theorem um which is very simple to to state it just says the following so it's a very very general situation I'm not no longer just thinking of linear regression I'm thinking of any problem about which you can write an empirical risk empirical risk is zero Remember the sum across all the data points of the loss between the prediction and the true y. Okay, whatever. Okay. And any regularizer that depends on the norm of w could be reach which is just norm squared but it could be anything. Anything as long as this function is nondereasing it's okay. Then the solution necessarily satisfies that it is a linear combination of data points. Okay. It's a very very strong result. It says that no matter what type of machine learning problem you solve that has this form loss loss regularizer where the loss only sees the points through the inner product is a very important aspect okay then it is the solution necessarily is a linear combination of data points okay or some weights okay why does it matter because it shows that the optimal w lives in an atmost n dimensional subace where n is size of the data number of data points Even if P is infinite, even if you have an infinite dimensional, if you're solving this with respect to functions in infinite dimensional spaces, the solution will always depend only on n numbers, which is the number of data points.
And the loss is completely arbitrary. It needs not be square. It could be whatever. And the regularizer is also arbitrary as long as it's a non-deasreasing function of the norm of W. Why is this true? The I'm not I'm not going to do any proofs, but this one is extremely simple. It it just it just goes like this. If you take W and you decouple this orthogonal decomposition, you take some part of W that is can be written as a linear combination of of X I and whatever is left which is the orthogonal complement. It's of course true that whenever you compute the inner product of W of this part with X I you get zero because this component of the vector is orthogonal to W. Okay. And then uh the the fundamental thing is that the loss function only sees the weight vector through this part which is parallel to it. The other thing is invisible. Okay. And because the norm because they're orthogonal, the norm is the sum of squared norms. Pythagoras theorem, right? You can only do better by just putting this part to zero.
Okay? because this is just adding to the regularizer and doing nothing to the loss. Okay, so it's it's irrelevant. You just throw it away. Okay, so that's don't worry too much about this. Okay, so everything depends only on data only through the inner products and so it's ready to be kernelized.
So what do you mean by kernel regression?
Okay. Um, recall that uh in the dual formulation we had this like a few slides ago here. Okay. Everything depends only on inner products. So this matrix x xrpose depends only on inner products and the prediction only depends on inner products. So the only thing I need to be able to do with points is inner products. Nothing else.
We go.
So prediction at a new point x is a linear combination of inner products of x with all the points in the training set and the weights are given by this solution where this matrix xxrpose itself only depends again on inner products. So if you're if you know how to compute inner products between x values you're in game. Okay. So the data points are only involve inner products both in the computation of the gram matrix and in the prediction. Okay. So how do we transform this cheaply into a nonlinear regression problem? Well, we saw this. We just take this function fi and apply it to each point. Okay, which means that now in the transformed points now your prediction is a linear combination of inner products between the transformation of the point where you want to compute the prediction and each of the points in the training set.
Okay. and alpha is given by the solution of this problem where this I'm just calling this matrix G is Xrpose remember it has contains the inner product but now it's inner products between transformation of X I and transformation of XJ okay this is still called the gram matrix or sometimes called the kernel matrix so now what we see is that when you compute the feature map you're moving from the original dimension P where each X lives to a dimension D. Okay. And maybe D is bigger than P. Okay. Is this bad or good? Well, it depends.
There's a hint which we already saw that in the worst case we never need to solve a problem which is bigger than N byN even if P is much much bigger because we can always resort to this form which is N byN. This matrix is N byN. Okay. Let me give you this very classical uh motivating example. So suppose you want to do order two polomial in R2. Okay, you have each point in R2 is a pair of numbers X1, X2. Okay, if you want to do order two polomial, you need all the monomials of order two, which is order zero and then order 2 X1 2 X2 and square root. And let's weight them in this particular particular weight. Square root of 2 X1 * X2. Now let's compute the inner product between two of these. So phi at at some point and five at some other point. Okay, five at some point at some other point. Don't worry too much.
Just inner product between two vectors that look like this. All of these. It's very easy to show that this can be written compactly as 1 plus the square of the inner product between the original points before the transformation.
Okay, which shows that the inner product after the transformation is some function of the inner product before the transformation.
Okay, which so this inner product in R4 because this is four components is just a function of an inner product in R2. So you only need to compute inner products in R2 not in R4. This is and this would be the same if you have instead of order two if you have order whatever it does it doesn't matter. This is called the kernel. So a function that you can compute directly from the objects and which is equal to the inner product of the transformed objects is called a kernel. Okay. And what you have is that now wherever you have an inner product you can replace it by this function K.
The gram matrix is just of course the the the kernel function between pairs of points. Uh and this is called kernel squares. Okay. It's a linear combination of kernels between the point at which you want to compute the prediction and each point in the training set weighted by these alphas where alphas have this closed form solution which are given by this linear system where this matrix G contains all the kernel functions between all pairs of points. Okay, [clears throat] this is n byn because this matrix is n byn because I have n points. Okay, so this is called kernel kernel list squares and uh it's a very classical thing. Okay, now why do I need kernels?
Okay, uh the main argument for so kernels were very very hot topic in machine learning around 20 years ago. Um and the the main reason why they they were very important because they encapsulate the learning part from the representation part. Okay. So you take if you know how to compute. So a kernel is in a sense a form of similarity measure. So if this number if I take two two objects x1 and x2 compute the kernel and the value is high it means that the objects are quite similar because the transformation for the for the task that you're interested in they have a relevant similarity. They're very similar. Okay which means that your prediction will be a weighted function of how similar the new point is to points in the training set. Okay. And the encapsulation works in in this way.
First of all, there is no need for any structure in X. X can be whatever any set. It can be a set of chairs. Not images of chairs, actual chairs. Okay?
Could be a set an arbitrary set. Okay?
As long as you can compute a function between pairs of objects in this function in this set. If you have some way of comparing two chairs, I give you one chair and another chair and you give me back a number seven.
which means this the similarity between these two chairs is seven then we can do chair classification um using kernel methods. Okay. And so I say that this function K is called a kernel if if it is true that there is some feature transformation such that this function is the same as first doing the feature transformation and then doing an inner product in this high dimensional space doesn't really matter if this is true then I call this a kernel function.
Okay, don't don't worry about what the Hilbert space is. And it's very very easy to see if a function is a kernel or not. There's his famous theorem called Mercer theorem that says a symmetric function. What's a symmetric function?
It's a function that doesn't care about the order of the arguments. If I give you two chairs, it does the similarity between chairs doesn't matter which one is chair number one and one is chair number two. Is a symmetric function between the two chairs.
uh it's a kernel if and only if the gram matrix is positive semi-definite which means I I give you 20 chairs you compute all the similarities between this each chair and all the other 19 you build the matrix if this matrix is positive semidefinite which you know how to compute you comput values and they're all non- negative then this is this function is a kernel which means that there is some fidget transformation for which this similarity corresponds to an inner product but I don't need to know it. It's irrelevant. It exists but I don't care about it. Okay. Um which means as as we know it an implication very important implication that G being positive semidefinite is that I can solve the problem because this matrix exists for any lambda and so on. Okay. So examples of kernels. So of we already saw so linear kernels would be take each object which is a if it's a vector and multiply it by some matrix.
This is obviously a feature mapping that it's just multiplying x by some a quadratic kernel we already saw is just the sum of all the monomials of order two polomial kernels of any order and so on. There are kernels for many types of log. So a lot of machine learning papers in the early 2000s was taking some linear taking some classical machine learning algorithm technique from PCA to many others and massage it until it's written only using inner products. Once you have inner products you apply something called the kernel trick and you have a kernelized version of the algorithm. Okay. Um there are kernels for many types of objects for sets for strings for images for graphs for probability distributions for point sets for many many different objects and the idea that the kernel will encapsulate you don't really care what the object is as long as you know how to compare two of them. Okay. And then the rest of the algorithm is the same no matter what the objects are. So this is it was very relevant. So for example for this is a classical one the gausian kernel um which simply transforms each point into a into a function which is a gausian function located at that point and now this is an infinite dimensional space but it doesn't matter you can your kernel your transformation can be infinite dimensional it doesn't matter because in the end you only need to solve problems in size n okay so every time I teach this I get this anxiety Is it still relevant to talk about kernels in 2026? So I ask Claude, in the day and age of deep learning, transformers, LLMs, AI, when learning the foundations of machine learning, is it still relevant to study kernels and kernel methods? Please provide a short answer otherwise it will go on forever.
And I'm not going to read everything.
You have the slide later. You can read it. Yes, kernel methods remain worth studying for several reasons. Okay. Um, so they build mathematical maturity.
They're still practically useful in many small to medium data sets. They're connected directly to deploying theory as u maybe we'll see tomorrow uh through something called the neural tangent kernel. So that there still I think still there was studying if you studying machine learning. So let me make a a pointer to to a very high level pointer to the Andreas lecture on uh Thursday right? Thursday. Yeah. So I'm not going to explain to you what a transformer is.
Maybe some of you know. So you know that you can write the output of a transformer as this in a linear transformer in this way. So we have these these matrices these query key and value transformation matrices. It's called linear detention then you have a if it's for network and and maybe another weight. Uh first of all it's I'm I'm not going to explain it in detail. There's this paper down there if you want to take a look.
Um, this thing that appears here, this inner product between Q and K. So this Q and K. So the query and key is in in a sense a gram matrix is a matrix of inner products between transformations of of the inputs. Uh the attention is a weighted combination of the values. So it is essentially similar um similarity weighted combination. It is dual version this dual view of linear regression. Uh and so in this paper they make this claim that for some choice of these weight matrices in a in a transformer this is exactly the orthogonal list the ordinary list squares projection which you saw which is the hat matrix uh yhat equals py not going to go in any details uh I just want to claim this that projections gram matrices inner products and all of this stuff they are the tools that you need to understand attention and they are exactly what we are studying. in in this lecture. So I need to justify this only for myself.
Okay. And uh we let's five more minutes.
Okay. To compensate. Yeah. Okay. Because we reach in the beginning before the break. Okay. So uh actually not far from the end of this part. So now consider that the situation where we have um the number of points in the in your training set is smaller than the the dimension of the parameters n less than p. But let's suppose that X is full rank because that means that there are no repeated essentially no colinear examples. They're all they're all different. Okay. So now we know that we cannot solve these, right? We cannot solve linear regress regression because the problem is underdetermined, right? If I have um fewer points than uh than the dimension of the parameter vector, the problem has many solutions.
It's not that it's overdetermined, it's underdetermined. have fewer equations than unknowns. Right? This is the number of equations essentially number of observations and this is the number of unknowns. So this problem does not have unique solution. Actually it has infinitely many solutions. Okay. There are many combinations. There are many W's that get zero that achieve zero here. Okay. Um it's not that it has no solution. It has infinitely many solutions. So minimum norm solution means take the set of all possible solutions all the W's that satisfy y= xw and choose the one with the minimum norm okay this is called minimum norm solution and it's it's very easy I'm not going to show it that can be written like this instead of xrpose x - 1 xrpose y now it's this the other way around okay for those of you who studied these anyone knows min rose pill inverses from linear algebra No one one two okay this is called a mur penrose so it's very for I think for machine learning it's it's should be always taught so mur penrose you know penrose is a nobel prize Nobel prize winner physicist it's Roger Penrose won the nobel prize in physics I think in 2018 2019 he was the he was the PhD supervisor of um what was that guy who died um Stephen Hawking uh so he's a very famous physicist who worked on black holes and stuff like that but early in his career he worked in linear algebra and he proposed this so if you have a linear system of equations either you can solve the system if you have as many equations as unknowns and the equations are all independent there's one unique solution if there are more unknowns than equations which is this there are many solutions one that you can choose is this one which is minimum norm solution called M pen rows zero inverse the other situation which is if you have more observations more equations than unknowns the problem is overdetermined and then you find the least square solution which is the other multin extends the solution of linear systems of equations beyond the situation where they have a unique solution to whether they have more than one and you choose one with the minimum norm or they have none and you choose the one that's the least bad which is the least square solution. Okay, so this is called a perfect interpolating regime because now in this case you know that you can find a solution that you get because it satisfies this property yhat and y are the same. This is imagine for example a polomial that goes exactly through all the points. So it has zero error. Okay.
Um this will reappear later as something called implicit bias of gradient descent even without regular. So this is I'm talking about this because this is very important to understand modern machine learning. So this is a paper from 2019 but very very famous paper nowadays is very very discussed in previous six years called the double descent phenomenon. So the idea is this. So remember we saw this a picture like this earlier. This is a classical view in uh in standard machine learning which is say capacity of age. Think of fitting the simplest example fitting a polomial to data and you are increasing the order of the polomial on the right. When the order of the polomial exceeds a certain number for example for poloms is when the order of polinomial exceeds the number of points you get zero error because you can have a polinomial that goes exactly through all the points.
Okay. But if you test if you have an underlying function and you have you are able to sample more points and test you know that it's not a good idea to fit a polomial of the same order as the number of points because you get a very weakly situation. Okay. Now it turns out that if you change the solution beyond if beyond this point you change the solution and you start looking for the minimum norm solution and now you look at what happens to the prediction error.
You see that if you keep on increasing the the the capacity and if you make polomials of order higher and higher and higher you eventually the estimation error the the prediction error will go down down down and you actually become lower than the best thing that you had on the other side. This is called um doubleend phenomenon. I'm going to illustrate it here. Yeah, maybe I'll illustrate it here and then I come back to these plots. Okay, this is a real a real example. Although this is a function you want to estimate this is this function a very strange function 2x plus cosine of 25x okay and I'm going to fit it with legendary poloms is just a type of polomials okay let's see so we have 1 2 3 4 5 6 7 8 I think I have 20 points or 25 points which are those black dots okay if you use a lower order polomial you get this orange line which is smooth it's nice it has high bias low variance because It goes through this like this function like this. Now when you are exactly at the interpolating threshold you have a very high order polomial. It goes exactly through the points. Okay. So you have zero training error but it's very bad.
It's it's very off the charts in between points. Okay. So this is exactly at the interpolation threshold. This is one point before and one point after. But if you keep on going. Okay. And this is for order around I think you have 25 points this is like 50 or 60 a polinomial of order 50 you get this okay I'm going to zoom in so that you see although the function is very wiggly it still go through all the points it's very wiggly in the middle but because you're very strongly shrinking the the norm of the coefficients the function behaves quite well in the in the in between points okay and why can it do these here and it's not able to do this. Oops. Oops.
Oops.
It's okay. Yeah. Why can't it do this here? Because here it only has a little so the the the the the number of degrees of freedom that the function has to adjust to the minimum norm criterion is very small because it needs to keep those coefficients very high in order to be able to go through the points. But as you add more and more coefficients the function will have many more degrees of freedom and they can combine in certain way destructive constructive in different places such that it can minimize the norm and still go through the points. Okay. So this is the idea behind um the double descent phenomena. So this is a true example.
This is true data uh from an experimental illustration. So this is uh u with these functions uh the sort of relu type of functions doesn't matter what they are this is mean square error before the interpolating regime and after the interpolating regime and but very important to notice that what the problem that's being solved on this side is different from the problem that's being solved on this side. On this side you're solving le squares on this side you're solving minimum norm solution. So you're forcing the the function to go through ex exactly through the points but have the minimum norm possible which has a closed form solution. It's just this. Okay.
Um okay so the next thing I have and we're going to stop in 30 seconds would be the basian view of read of ridge regression which I'm I'm gonna skip probably you can you can read it. I just want to if you do if you do the full basian view of this which you can because you know the likelihood you know the prior know everything you can get something which is very important which is these uncertainty bars for the prediction. If you just do what we've been seeing up to now which is just linear regression with fixed weights and then you estimate the weights and then you plot a function the uncertainty that you have around the the function that you estimate is essentially the noise variance and it's fixed everywhere. But if you do it correctly, if you do it uh with a full basian machinery, you can actually estimate these uncertainty and uncertainty depends on where you are. Of course, it mean in this case it's very intuitive because it says that uh close to the points that you observe the the uncertainty is not too high. As you get away from the points, the uncertainty increases. It's it's [clears throat and snorts] just this.
And if you sample functions from the posterior from the distribution of the of the weights, you get a lot of wiggle here, a lot of wiggle there. So that's why you have a lot of variance there and not a lot of variance here near the point. So I'm not I'm going to skip the the equations for this and I'm also going to skip this in the interest of time because you're going to go to the coffee break. Is it okay? Can we go to the coffee break now? We'll be back in uh half an hour. Okay.
See you in a sec.
Okay.
Okay.
Should we go on? Okay.
So just before we before we close the regression part uh just to call your attention to the fact that in remember when we doing grid regression we added this squared uklidian norm of the weight vector to the to the loss function to the to the squared residuals. Another alternative actually you can use both of them is to add something called the L1 norm which I'm guessing a lot of you know is the sum of the absolute values of the weights instead of the sum of the squares of the weights it's the sum of the absolute values of the weights it's called the L1 norm and it has the effect of also of course of shrinking the parameters but it has even a stronger effect as I'll explain in a second this is invent it was invented in statistics in the 90s it goes by the name of lassu list absolute shrinkage and selection operator um can be seen the the key difference uh just in a simple linear regression problem with respect to ridge is is captured in this in these plots. So on the right, so this is a very famous, very small, very simple data set which is called the prostate cancer data set.
Not very uh uh happy data set, but it's what it is. Um on on the right side, what we have is is a plot of the the the value of each component of the parameter vector W. So, so when lambda is zero, so when there's no regularization, so it's just le square solution. Okay, these are the values. These are the names of the variables. It doesn't matter what they are. As as you increase lambda, the parameters go to zero because you're increasing the weight. You're increasing the weight of this term. And so, of course, this minimizing the norm of a vector. You want to minimize the component of the vector, of course, too.
Okay? And as lambda goes to to infinity all the coefficients go to zero. When lambda actually is really really big everything is zero. Okay. And this is for ridge regression. When you penalizing the square of the the sum of the squares of the of the parameters. If instead of that you you penalize as in lasso the sum of the absolute values without the square. Okay. The effect is different. What happens is something like this. So these values here are the same. When lambda is zero nothing happens. It's just lit square solution up here. But then as you increase lambda here as you increase the lambda you increase the weight of this uh term the parameters again will also decrease in value and in the in the limit they will all be zero but what happens is that in the meantime some of them become exactly zero. Okay, so there are solutions for certain choices of lambda. Some coefficients are exactly zero, not just small, exactly zero. And this is u that's why this thing is called selection operator because the ones that are zero are unselected. They are considered not relevant for this problem. So you have a problem where the goal is to estimate a value from a collection of values of other the features as a linear combination. If the weight of this linear combination is zero for some of these features, it means that this feature is not important. Okay, this is also used um quite quite widely quite wildly widely not wildly in in deep learning. Um although the problem is more difficult to to solve because we know that in rigid regression this is just a linear system. We can solve analytical tools when we put the L1 norm here. The the absolute value because the absolute value is a non-ifferiable function. You know how the absolute value is just this function absolute value of a of a number is non- differentiable at the origin. It has no derivative because it's not it's not the derivative on the right and the derivative on the left are different. U you cannot just compute gradient and set to zero. you need to use algorithms for that. However, in typically when you're doing deep learning and you're just doing gradient descent or stoastic gradient descent, you completely ignore this non- differentiability. Just compute the gradient and and use it.
Okay, so it's it's not you pretend that it's differentiable and but then you need to be careful in adapting the step size. Okay, this is very use. So almost all well I'd say all toolboxes for deep learning have an option of using L1 regularization.
um if if you want to it has this effect of encouraging [snorts] coefficients to become zero if they're not very important.
Okay, let's jump to classification.
Okay, so this the picture here is is essentially the same as in a regression.
The goal is to obtain this this box that takes in uh points x which have p um components and produce an estimate a guess uh of a class. Now it's not a number, it's a class. It's very important that this is a set and as you know in mathematics sets have no order.
So the order of these is irrelevant.
That what becomes what makes it a classification problem.
It's maybe the core machine learning problem. The first thing you think of is think of machine learning is learning classifier. It's kind of the the obvious machine learning problem. And again we are in the this setting where we have data uh examples of objects and their class images of dogs and cats labeled dog cat or whatever.
>> Let's see let's look at the simplest of all cases which is the binary case uh where the the the output the the prediction is a binary prediction say 01 or one two or a whatever any set with two numbers with two things is the same.
So it doesn't matter what you call them.
It could be like u spam detection. Is it spam or not spam or or what a diagnostic problem? Is it a sick or healthy person?
Whatever. And typically in classification we are after not only a class not just a decision but how confident we are in that decision. Okay.
So we want and for that we can use probabilities. So we are looking at we're after an output which is a probability that the true class is class one. Okay. Not just decision that the class is one from the probability then we can uh make a decision. Okay. If we want okay and if we are in this in the case of linear regression as we will be the prediction will depend on on on on X through some linear function. We can have nonlinearities in this function fi but with respect to the parameter it's linear. So it's a linear combination of features exactly as we had in in regression. So this will be a feature map and it the feature map can even be just X itself and so it's in this case it would be fully linear classifier.
Okay. Now the problem we have is that this inner product in general is just an arbitrary real number. It because W is vector of real numbers the fi transformation is also a real vector and so when you compute the inner product you get a real number but the probabilities must lie in 01. Okay.
What's the solution? As you may many of you probably know, you need to squash this real number into 01 to make it look like a probability. Okay, so in a in a nutshell in a picture something like this. So the picture above is the picture of linear regression you have an input vector some linear uh combination of a feature transformation and the output is just this linear combination of the features. In the case of classification, binary classification, if what you want to produce is the probability of one of the classes, you can make these real number wrpose fi go through this squashing function that will map any real number into 01 and 01 numbers between 0 and one can be seen as probabilities that so since sigma belongs to 01, we can take sigma to mean the probability that the class is one given that x that I'm having in the input or which I'll use this more compact notation conditional probability of class being one given the input okay is it clear okay so now what is the typical choice for these uh for this uh squashing function there are others but for binary problems the classical one is something called a sigmoid which looks like that it's exponential of the argument divided by 1 plus the exponential Okay, it looks like this.
Okay, this function for if for an argument u x u / 1 + xq looks like this.
So it squashes any real number into the interval 01. Um and obviously if the probability of one class if I have only two classes if the probability of one of class is this the probability of the other class is one minus this because this probability sum to one and one minus this can be written in this way. Okay. So actually what we we see immediately that what we have is we have two probabilities. one is before normalization assume that one probability is one and the other is the exponential but they don't they're not normalized so they're not correct probabilities. So what you do is you add them and divide both numbers by this sum. So it's one divided by one plus exponential and exponential divided by one plus exponential. If you add these two of course you get one because probabilities need to sum to one.
So what does this um what does this classifier look like? So the probability of of one of the classes looks like this. So the the space this space is in the feature space fi not in x could be whatever could be an image assuming that I have only two features fi 1 and fi 2.
So it's in R2. W is also in R2. And so the classification looks like this. So this um this color uh this colors from red to blue can be seen as as as encoding the level of confidence in in class one or in class zero it doesn't matter it's not it's just a just a drawing and the white the white region here is where the boundary is if you define the boundary as the probability of class one is one half. So if the probability of class one is one half or bigger you decide for plus one.
If it's below you decide for plus zero.
And this occurs precisely when this inner product is zero as we see here. So the one half threshold is passed when this argument is zero. Okay. So which is this. Okay. So in a in a sense you can you can think of this wrpose phi this quantity as a score for class one. It's a number that says how likely it is that this is class one and you transform this score into a probability by making it become a a probability and for that you need two things. It cannot be negative because probabilities cannot be negative and to do that you exponentiate it. When you exponentiate a number the result is always non- negative and then you need to normalize because it needs to be probability. So first you exponentiate and then you divide by the sum of everything that can happen and then it's non- negative and normalized. Okay. So this is what um binary logistic regression does.
Okay. Now how do we solve how do we attack this problem of solving of finding this w. Okay. So again same scenario we have points and we are assuming again as before that the y's are conditional independent given the axis. So I have a collection of samples and each corresponding label is independent from all the other labels and all the other samples. Everything is only one by one. and the probability that I have class Y. So this is um this is a a big jump but um just bear with me for a second. So these Y's are binary.
So they are zeros and ones. Maybe you've seen this before some of you. These Y's are are one and zero. Okay. So if Y is one, you get the probability of class one, which is here what we already saw, right? Probability of class one. It's this exponential divided by one plus exponential.
If y is one raised to one any number raised to one is just a number right doesn't change but if y is [clears throat] one one minus y is zero and this is the probability of the other class the other class is class zero any number raised to zero is one right so you get this all of these is one multiplied by the probability of class one whenever y is one if y is zero it's the other way around if y is zero this number gets raised to zero and you get just a one and this number gets raised to 1 minus 0 which is one you get this number. So this is a compact way of writing this probability or this probability depending on whether y is one or zero by using these exponents which are y and 1 minus y. Okay. Um and now you do as we did before someone mentioned it there for regression we write the joint negative log likelihood for everything. So because everything is they are all independent it's a sum and already take the log when you take the log of these you get when you take the log of a product is a sum of the logs the log of an an exponential is the exponent times the log of the base. So you get this y time log of all of these plus 1 minus y time the log of all of these summed across all the points. So this is the negative log likelihood. And now just like three or four lines of math will allow you to simplify these.
Notice that when you have a log of a ratio, it's a log of the numerator minus the log of the denominator. The log of the numerator, this log will cancel with this exponential. You get only the exponent and blah blah blah. And you there's some cancellations and it turns out to be like this. Okay.
And now the maximum likelihood estimate or which is obtained by minimizing this which is maximizing the likelihood um is is just amount to solving this problem and this thing is called the cross entropy loss which you if you've done any deep learning you've seen it.
Uh now in this case derived from from this way. So it has no closed form unfortunately unlike in the linear regression case which has a very simple closed form. It's just inverting a matrix here we need optimization algorithms. This does not have a closed form. needs to be solved numerically always. Okay, but this function is smooth. I'm not going to show it, but it's smooth because it's it's like logs and exponentials and inner products. So there are no discontinuities. There's nothing strange. It's easy to show that it's convex. We'll see what this is. So it should not be too hard to optimize.
What happens when we have more than two classes? Not just a binary problem 01 or one two, but uh multiple classes, K classes. Okay. So what what is done in this case is you give each class each class its own parameter wy and then you normalize. Okay. So this this inner product. So you have a new point x. You compute the features and now you compute the inner product with the parameters of each class w1 w2 w3 and you get a collection of numbers. These numbers are just real numbers. Now you need to transform these into probabilities. How do you do that? first exponentiate. When you exponentiate, these numbers become uh non- negative because exponentials are non- negative. But now you have a collection of non- negative numbers, but they're not normalized. So they're not probabilities. How do you make them probabilities? Divide by the sum. And so this is what this is doing here. It's just exponentiating. So notice that because I want to interpret this as a score that says how likely it is that this is a true class, I need to use a function that's monotonically increasing. So exponential is monotonically increasing. So bigger scores correspond to bigger probabilities.
Okay. And then normalized. So this is known as soft max. Maybe you've seen it before. So for a given y, so soft max will is exactly this. You have a vector of numbers. You compute the exponential of each of them and divide by the sum and you get something which is called a softmax transformation. In this case for the given Y it's just the white component of the soft max to summation.
I'm going to come back to this more detail in a second. So this is called this go by many names. Again this was invented in different communities with different names. In statistics this is called the generalized linear model. In machine learning it's called multinormalistic regression. It in in many areas such as in speech processing it was called maximum entropy. U in machine learning it's also called soft max and so on. Okay, consistency check. Let's see if this expression recovers the one we had for the binary case. What happens when k equals 2? When k equals 2, if you divide both numerator and denominator here by one of them by the exponential of w0, let's say, you get exactly the sigmoid because you get when this has only two things, one of them is one uh because you divide by w.
So you have exponential of w blah blah blah divided by exponential w 0 blah blah you get test one and so you get precisely the sigmoid with w equal to the difference between w1 and w0. So this is an over parameterized mod. This is another parameterized model because it has k parameter vectors one per class but actually you only need k minus one parameter vectors which is obvious because you don't need to compute all the probabilities because if you're able to compute k minus one probabilities you already know the final one because it's one minus the sum of the others. Okay.
So this this formulation is over parameterized but but that's it's a common one. Now how do we solve this?
Well usual thing. So we know we need to optimize this. We need to minimize this function which will give us the the maximum likelihood estimator. Uh and we can just use the usual things. You can do ridge regression. You can minimize instead of the squared loss. Now you have this um logistic loss, cross entropy loss, maximum entropy loss, all these names. And then if you want to do ridge, you can add as we did for regression the squared the square of the uklidian norm of the parameters. It's still smooth. It's still convex. It's well behaved function. You can do it with lasso by adding the L1 norm.
Actually, you can do it with both. You can add plus say another lambda plus lambda omega 1. You can do both. You can add both regulariz. And it's very commonly done actually.
Okay.
So, we just saw this. So we have the generalized linear model or multiclass logistic which gives me the probability of each class as exponential of this score after normalization. Okay, again I've just set this. So and now the negative log likelihood which you have not seen for the for the multiclass case is obtained like this. So you sum across all the points as we did before. It's here. But now if I want to select specifically the label of point Y of point of the E example which is Yi one way of doing this which is very convenient is to sum across all the classes but then multiply by this indicator function. So this one yi equals K means this is one if K equals YI it's zero if it's not. So this thing here inside with inside the inner summation in K is exactly the same thing we have on the other side. It's like I have put here the yi because all the others are are zero. Okay, this is called the cross entropy cross entropy loss typically the way to see this is that to say that this my my labels instead of being a number from one to k or a label are one hot representations. So you've seen one hot representations, you know what it is. Who knows what one hot representations are? A lot of people.
Okay. So one hot representation, you know what they are. It's a vector of dimension K. Zeros everywhere, a one somewhere. Okay. And so with the one hot representation, now we can write these the multinnomial logistic loss um in in this form. It's the sum across all the points, sum across all the classes with the one hot um components inside of of there. Okay. Now again using the same tricks okay we can uh rewrite this in this way okay using again the fact that now we can we know how to write this remember when we f_y of k given x i and w is given by this form okay it's this when you plug this in there okay we can simplify it into this form it looks like this so it's a sum across all the points of the log log of the normalization constant which is the denominator of the logistic loss minus this linear term. Okay. And now this one is very easy to interpret what's going on. If x i is in class k only y i k is one. All the other yis are zero. Okay. And so to minimize this because there's a minus sign, you're trying to maximize the inner product between that example and the corresponding parameter of class K.
Okay. So what is what this loss function is trying to do is for each point that is in class 7, it's trying to maximize the inner product of the point in that class with the parameter vector of class 7. So it tries to make parameter vector of class 7 as close as possible to the examples from class 7. Okay? So that they align well. they have high in products have high scores thus high probabilities.
Okay. So I'm going to skip this part. We could do uh as we did not I skipped you can read these if you want. If I if we can do if you want to do a uncertainty quantification carefully we don't actually just solve this optimization problem. We can actually do a basin formulation come up with the post distribution of the weights and then we can compute the predictive distribution which in in the regression case allowed me to show you these error bars in the regression function. [clears throat] Here it's not easy to do that because none of these has close form solution not even the optimizer but you can do it using optimiz using the numerical tools and so on and it's also possible to come up with these uncertainty bands. So this classification problem where you have uh examples from one class, examples from another class and you have the uncertainty width of the classifiers with classifier goes here and it's more uncertain far away from the points. It's less uncertain close to the points and so on. So it's also possible to do this.
You can read the there's a reference if you want if you're interested in basin basin classification. Okay.
There's another view uh of these which I actually I could have started here. It's another it's an alternative way of seeing it that which will connect actually to to the lecture on transformers on Thursday by Andre which is uh again looking at the problem from this perspective. So when you're doing classification what you have is say this box that takes an input and computes some linear function which is this which we already saw in the sorry for going back it's horrible to go back I know it's this right it produces in this case just a number but in the in just one number if I'm doing binary classification if I'm doing kclass classification I need to produce k numbers Okay, here they are. I have K numbers which are called the scores of each of the classes. So this is score for class one, a score for class two and so on all the way down to a score for class K.
This can be seen as how likely it is that the that the class is class one, class two. But these numbers are not normalized. They're not necessarily positive. They're just numbers. They result from some inner products or something. Okay. And now I want to transform these numbers into probabilities. Okay, what does that mean? Okay, so these numbers these Z's this should be called itas. I don't know this typo and I want these u y I want these probabilities. This is okay this is wrong. This should be Q's. Sorry I need to correct this typo. So think of this as Q's and this as itas. And I want these Q's to live in something called the simplex. Okay, the simplex means that these numbers, these Q's, sorry, they're wise, I need to correct, are non- negative because they are probabilities and they sum to one. Okay, question is, how do you map from an arbitrary vector in K dimensions to a vector which is a vector of probabilities in satisfying the two following properties. If the scores are the same, the probabilities need to be the same.
So if one class has a certain score and another class has the same score, there's no reason why I should give more probability to one class than to the other. It should be the same. And if one score is bigger than the other score, then the probabilities cannot be small.
So it doesn't make sense to have one score being bigger than another one and having the probabilities have the reverse order.
Okay? So I need to have these two things. So one first possibility, let's find the probability vector that is most aligned with the scores.
Okay, so this would mean looking for a probability vector P. So a vector that has non non- negative entries and they're all sum to one that maximizes the inner product with the vector Z which is an arbitrary vector. Okay, now this is if you've studied linear optimization sometime in your past, you know that this solution is always in the vertex of the problem, which means that um the what this will give you is a vector that has zero everywhere except one.
It's a one hot vector where the one is at the location of the maximum value of Z.
Okay? And if there are there are ties if there are two classes that have the same score it will have 1/2 one half in these two or if there are three 1/3.
So it's a vector that it's called argmax okay called arg max operator which looks for the score vector and produces a vector that has zeros everywhere except in the maximum of the scores.
Well this is greedy. It means that you you ignore all the other scores. Uh second possibility is to let let's try to encourage a little bit more uniform probability distribution. Let's not so be so greedy and so instead of solving this problem like this we add something which is called the Shannon entropy. Who knows what the Shannon entropy is? what the entropy is a lot of people. Okay. So you add the Shannon entropy because you're trying to maintain the the entropy is a characterization of a distribution which is high if the distribution is very uniform and it's low if the distribution is very not uniform. It's very peaked in some values. Okay. Um some of you know about it some don't have no time. So the main property is this. It's a non- negative quantity. It's always non- negative.
It's can be no larger than the log of the number of possibilities and it this maximum is attained when all the probabilities are the same. So you're trying to encourage on on one hand trying to encourage the probability to align with the scores but not be too greedy not have zeros everywhere except in some places. Okay. And if you do this remarkably the result that you get the solution to this problem is the soft max of Z. Okay. which is this exponential of the Z's divided by the sum of the exponential of the Z's which we saw the soft max right here.
Yeah, there you go.
Soft max there. Exponential of disease divided by the sum of the exponentials.
So this is the re actually I mentioned sorry for going back uh I know it's really bad.
This is the reason why the soft max is also called the maximum entropy transformation.
There you go. Okay. Softmax transformation.
I'm going to skip there's a proof. It's a very simple proof, but I'm going to skip it. Okay. Another possibility.
Okay. Let's look for the vector in the simplex that is closer to the vector of scores Z. So this slightly different modification. look for P, a vector of probabilities that minimizes the square of the uklitian distance between P and my vector of scores. Okay? And this goes by the name of sparse max. I'll show you how it looks like. Okay?
Notice that when you compute these, you're minimizing a problem with respect, you're solving this problem with respect to P. If you expand this, you get norm of P^ squ. There you go.
you get norm of z^ squ which doesn't matter because you're minimizing with respect to p and you get the inner product between p and z which is here okay this would be with the 1/2 over there okay this can be written in in this way and it turns out that this quantity here is not very important now this quantity here it's a sort of an entropy it's called a sal's entropy and so it also maximizing an entropy in a sense but it's not chen entropy it's another entropy and there's a a general family of of of of formulations of this sort where you can just take any entropy and put it there and actually you can have this parameter beta there which will control how how much weight you give to each of these if you give more weight to the attempt to maximize the inner product with the scores or if you give more weight to the maximization of the entropy Andre is going to come back to this on on Thursday so all of these transformations so arm max which is finding the maximum one soft Max exponential divide by sum of exponential sparse max uclidian projection on the simplex have the same uh type of properties. One of them is that if you add a constant to all the scores nothing changes. Okay. So if you have the scores and you add them alpha times all ones so nothing changes. Okay. If you permute the scores after this the same permutation applies to the result of the projection. Of course if you permute the the scores if you permute score one with score two the probability that wasn't one now is in two they permutation equivariant and it looks like this. Okay. So for example, let's look only in the in the binary case. In the binary case, you remember this function. This is a sigmoid function.
This is e to the if this is t. This is e to the t. This blue one, it's e to the t / 1 plus e to the t which looks like this, which is can be seen as probability of one of the classes. It goes from zero to one on the right. In the sparse max case, it looks like the red one. Okay. So when the score is below minus one the sparse max says probability of class one is zero probability of class the other class is one and then the probability increases linearly until it reaches a maximum and beyond one probability of class one is one not close to one exactly one and the other is zero. Okay, so it makes a hard transition from one class having zero probability then it moves slowly to the other class and then it saturates. Okay, in two classes it looks like this. It the soft max looks like this and the sparse max looks looks like this.
Another way of seeing it is more interesting like this. So suppose you have these scores. Okay, so you have this network you have uh five classes you have the scores for this class. The score for the class suggests that the most probable class is class one because this number is bigger than all the others. Second most probable class is probably class 4. Yeah, this second biggest number and so on. So if you do soft max, you get these blue numbers.
These blue numbers, these are non- negative numbers all of them. And they're all summed to one. These are probabilities.
If you do arguable, which is this one, the first one, and you get so one here and zero everywhere else. If you do sparse max, you get something in between. You get this class one with probability 0.8 something, class 4 with probability 0.1 something, and all the others with with probability zero. Okay, so it's not arc max, it's not soft max, it's something in between.
But most importantly the number of non-zeros depends on how these points how these values are distributed. So it's an adaptive type of sparity. It will give you non-zero probabilities for classes which are which have sufficiently high um scores and it will adaptively if one of them is really really much bigger than the others it will be the same as armax but if not it will adapt the sparity to the to the uncertainty. So sparse marks unlike softmax may yield exact zeros. So now you probably heard when you talk about large language models about this temperature parameter. So the the the temperature which I we called beta here beta it's one over the temperature if you want uh if you scale the argument of soft max or sparse max by a number which we call t okay the temperature it happens the following thing happens in the limit as the temperature go to zero. So when Z when t goes to zero the the norm of Z goes to infinity the norm of of Z divided by T goes to infinity it's a vector that becomes bigger and bigger and bigger okay in this limit this becomes the arg max okay suppose that one of them is slightly bigger than the other if you multiply by a million the difference increases increase increases and the the dominant one will win with respect to all the others in the zero limit temperature so this is the zero to the zero temperature in the high temperature limit which means when t goes to infinity since you're dividing everything goes to zero and every the sparse max and the soft max of all zeros is just a uniform distribution because you do exponential of zero is one everywhere it's so it's one one one divided by the sum of all the ones which is one over k okay so these are the two the two extreme values of the temperature so in the sense the temperature controls how peaked the soft max is and how sparse the sparse max is.
So in you probably heard about it in language generation say transformers and stuff like that there's a soft marked at the end. I showed it to you in the beginning and the temperature controls how distributed the the probabilities are and how how likely it is that to sample only the most probable token or or spread this probability through more tokens. Um just back to attention just to call that so we saw that uh ju just to to make this point to Andreas lecture on on Thursday we saw that earlier earlier that linear attention can be seen as a list squares projection when you do rev so I'm going to go this in detail not not now I'm not going to just fly over this when you actually do attention we have a soft mark so the soft marks will appear there um and this scaled product attention. The square root of the of the size of the of the of the vector is precisely the temperature. It's exactly the same as the temperature. So it controls the the the the peakness of the distribution. It's obvious that because of the soft max is a vector that sums to one and non- negative and sums to one.
It means that the output is a convex combination of the rows of V. So everything is the same. And if you replace soft marks by sparse marks, you get something called sparse attention which will have exactly zero weight on some positions. So more on these, don't miss Andre's lecture on Thursday. He will tell you everything about sparse attention and attention in general.
Okay, so [clears throat] how are we in time? Okay, we're okay. Um let's let's go back to to classification in general actually to supervised learning problems in general but we can start with the the the binary classifier and consider the binary classifiers that have this form u so the sign sign function plus one if you're above zero minus one if you're below zero uh in this case I'm considering the labels as being plus one minus one okay and let's assume the linear case now I've changed the notation from w to theta Um I don't know why but but I did. Um so all everything you've seen up to now can be summarized can be written in general terms like this. So you're trying looking for the parameter that minimizes the average of the loss function in all the points in the training set. You're summing across a training set loss predicted value given value divide by n to get the average plus a regularizer.
Okay. So this could be logistic loss can be written compactly in in this form.
It's log of one plus exponential of this product. The hinge loss which we will not cover uh is is given by this this function. I'll show it in the next slide. Italize support vector machines which we will not cover today.
Um so in a sense we can we can say that what we would really like to have is some function that that measures how wrong I am if I'm wrong or right in a classification problem. So this remember this indicator means that it's one if this condition is true is zero if it's false. So if it's one when the sign of f is different from the label I pay one.
If the sign of f is the same as the label, I pay zero, which means this this error loss is the one that I would like to minimize is in my training set. I find the classifier that minimize the training loss.
I could use other losses in in general.
So here it is. So the the error loss is this gray function, gray gray value here, gray line here. So because I'm using a classifier that suggest plus one, minus one, and the labels are also plus one minus one. When they disagree the product is negative, I'm wrong. I pay one unit because I'm wrong. It's this error loss. When they agree, they have the same sign. The product is positive, I pay zero. Okay. But now all the other ones that you've seen mclassification, the exponential, an exponential, which you have not seen, binomial devian, it's by what in this picture is the logistic loss, square data loss, this red one, which is soft for regression. In a sense, they're all can be seen as trying to approximate this one. Okay. By functions which are better behaved. Why? Why can I not use this one for optimization? Any idea? Why don't we just use this one for binary classification?
There's no gradient. It's very hard to optimize. Actually it can be shown that for a even for a binary classification problem solving this problem with a with a with this objective function is an np hard problem you need to consider all possible combinations uh these other functions are all continuous convex they have derivatives we can do gradient descent on them okay that's why we typically do not use the error loss okay so let's continue looking at this function what what is this this this function this this loss which we the average across the training set of the loss function uh can be seen as the thing that I would really like to minimize okay which is the expected value of the loss remember we saw it in the beginning if we knew the density if we knew the joint distribution of the x's and the y's then we would not need to have data we could solve something called optimal decision problem directly using this function but we don't know it so we cannot compute the expected value of the loss which is called the risk or expected loss or risk. So what we have is so we can see we can look at these as we already mentioned this as a a sample based or empirical version of these. So it's an expectation that I cannot compute because I don't know the probabilities. So approximate by a sample version by taking all my points and averaging over them the value of the loss. Okay, that's what's written there.
Of course, the risk cannot be computed because the joint distribution of X and Y is unknown. Instead, we have training data and so on. And so all of these methods, logistic regression, SVMs, ridge regression, all all of them can be seen as uh using surrogates for the error loss because I cannot use the error loss because it's intractable because the derivative is zero everywhere and so I cannot do gradient descent and I cannot solve it analytically. It's actually NP hard.
Okay, any questions, comments, nothing. Okay, that's good or bad, I don't know. Okay, finally, optimization.
Optimization plays a central role in modern machine learning. Very very central role. Okay, so back to the same expression we had.
So when we have a supervised learning problem formulated in this empirical risk minimization to have the empirical risk which is the average of the loss across the training set maybe I have a regularizer and so my goal is going to be to solve this optimization problem okay and this a lot of work on this so at least maybe more than a million papers written on this this could be the loss could be if we're doing linear regression Could be quadratic loss, could be the logistic loss, could be the hinge loss for SVMs, could be the absolute error loss. Why not? Okay. Uh actually a lot there's when I asked let me go back to the very very beginning when I ask why squared error loss and so yeah because it's assumes that the noise is quadratic the noise is a Gaussian but some people say no no no the real reason why we use quadratic loss is because it's analytically tractable.
The gausianity is just an excuse but it makes the problem easy. Okay, because when you compute gradient or derivatives of squares it's very simple. Okay, so you can argue that well you can get you have these gaussian xqs but in in reality we use squared because it's easy to deal with. Okay, well you can see as see it as you want. Okay so what do you mean? So we have an optimization problem um and let's call this function that we want to optimize all of these let's call it f big f okay okay and you want to optimize it with respect to this parameter vector okay what do you mean by minimizer so a minimizer obviously is a some location in the function that has a minimum value with respect to all other values so there are different types of minimizers maybe you've know something about this so we have a global minimizer if No other point has a slower value than this one. Nowhere anywhere we can have just one or several. Okay, so this is one global minimizer. This is infinitely many global minimizers because any point here is a minimizer or you can have very many local minimizers.
So a local minimizer is a point that it's less than the points around it but not not necessarily less than all the others. Okay, so in this example here, we'd have one global minimizer here and several local minimizers. So uh just a detail on the name. So we typically use minima to mean the value of the function there and minimizer to refer to where it is. So the value that achieves the minimum. Okay, so minimum and minimizer.
So of course global minimizers are also local because they're also minima around this area but local minimizers are not necessarily global. Okay, it depends on whether they are or not. So for example, this one is global minimizer and of course a local minimizer but these other three are not global minimizers although they are local minimizers.
Convexity another very fundamental property for optimization. Forget about the expressions. We can look at only at the plots you see here. So I say that the convex function is convex with if when I take two points on the graph of the function and I join these points by a straight line. This line stays above the graph of the function. So this is what I call a convex function like a cup. Okay. This is a non-convex function and this is a convex function but not strictly convex. What what does it mean to be strictly convex? It means that this line stays above the graph of the function strictly above without touching it except at the two ends. Okay. So this one is not strictly convex. This is strictly convex.
Do you know about this? Everybody who knew who knew about convexity? Oh, a lot of people. Good. So convexity implies local minima implies that local minima are equal to local global minima or local global. It also implies a very important property which is convex functions are necessarily continuous.
You cannot have a discontinuous convex function except in infinite dimensions but that's no big deal. So if the function is differentiable there are second order conditions which say that a function is convex when I compute the hessen. So hassian as I guess many of you will know is the matrix of all the partial derivatives second order partial derivatives of the function with respect to pairs of parameters. A function is convex if and only if um the hessen is positive semidefinite it has no uh negative values and if the is strictly uh positive definite implies that the function convex but not the other way around. Do you know the counter example?
Can you give me a function that's strictly convex but such that the hassen or second derivative is not positive in one dimension.
So x² is convex. What's the second derivative of x^2?
First derivative of x^2x.
Second derivative two. So give me a function that is strictly convex but that has zero somewhere in the second derivative x to the 4th right x to the 4th first derivative 4x to the 3r second derivative 12x^2 at x it's zero so it's flatter at the origin so it's uh it is strictly convex obviously but but there is a point where the second derivative is exactly zero It's a classical it's in all textbooks on coation. Um so desent directions if we want to minimize a function I want to know where to in what direction to go when I'm in some point theta 0 I want to go down okay and going down I want to see if there is some direction such that if I take a step of size alpha in that direction I get a lower value than than where I was. So if f is differentiable u I have a descent direction if there is some direction which has an inner product with the gradient that's negative. Remember that the gradient of a function is the direction of highest increase. So the negative of the gradient is the direction of highest decrease. Okay. If there is a direction in which I can decrease this property will hold. Okay. Thus, if I have a differentiable function, if I have a local minimizer, it's guaranteed that the gradient is zero because there will be no disinterctions otherwise it's not a minimizer. But the reverse is not true.
I can have a gradient being equal to zero but still not be a local minimizer.
And the classical example is this settle points. Okay, the gradient there exactly at the middle of the saddle, the gradient is zero because it's it's at a maximum in one direction, it's at the minimum in the other direction. So it's not at the minimum, it's at something called the settle point. If you move in one direction, you go up. If you go in the other direction, you go down. Um so but if f is convex, this cannot happen because the hen of this function is not positive definite. Okay, if f is convex then um this becomes an equivalence.
Okay, so global minimizers have zero gradient. So how do we work with this?
So gradient descent maybe you've seen some of these before. Gradient descent is just classical thing. You start with some point and you choose a step size and you then compute the gradient of the function and take a step of size that size in the direction of the negative gradient. minus the gradient and then you go on and you keep on doing this. So there are many many many many ways of choosing alpha. This is a big research topic in optimization. There are at least tens of thousands of papers on step size selection in optimization and you need to use some stopping criterion.
You need to know when to stop. Typical things would be like say the norm of the gradient is less than some parameter.
In the convex case, uh this is not well this is easy to analyze or not so easy but it's it's feasible. Uh there are two properties that characterize convex functions that will allow you to to to extract some some theoretical result.
One of them is something called l smoothness. So smoothness is the following property. I say that the function is l smooth if the following happens. So what is this? This is the norm of the difference between the gradient at two different points.
There's a gradient at this point, a gradient at that point. And if this difference between the gradients is upper bounded by some constant L times the difference between the points themselves, then I say the function is out moves. It means that the gradient does not change too fast. If the points are close enough, the gradient is also going to be close to each other.
uh if if if f is twice differentable smoothness is the same as the the being upper bounded by some constant l the reverse of this is I I have a picture that will show this is something called mu strong convexity which means that the function is looks at least as convex as a quadratic function with constant mu okay let me show you the picture which is nicer so suppose this is this function f over there the black line.
Okay. The other black line below is the linear it's a sort of tailor expansion is it's a tangent function to this function f. Okay. And this function is l smooth and mu strongly convex if the following happens. the function is it bends up faster than a quadratic function with parameter mu but not as fast as a quadratic function with parameter l. So it's it's that sandwich this function f is sandwiched between two quadratic functions and so and so it essentially what it says that it behaves like a quadratic function. So there's a quadratic function which is more convex and a quadratic function is less convex and they're both quadratic.
Okay, let's u let's keep this in mind. So I have these two parameters mu and l. So l says how smooth it is. Mu tells how quadratic it is. Okay, how how strongly it is. And there's a very important number that characterizes function. It's called the condition number which is l over mu. Okay. And uh the the bigger L the bigger k is the more difficult the problem is. Okay. It's condition number.
If l equals mu the function is exactly quadratic. Okay. It's a quadratic function. It's the easiest case.
Okay. So gradient descent. I'm going to skip the I'm going to just mention the results very very quickly. Um if you do a step fixed step size of size one over L you can show that the the function value goes down in this way. It's k minus one divided by k raised to t. So because this number is less than one it goes down. This is called linear convergence. Okay I'll show you a plot in a second. If the function is not strongly convex then the best you can do is one over t. Notice that this is a number less than one raised to t versus something divided by t. This goes to zero much much much faster than this.
Okay?
Like this. Okay? So this is log plot.
This is linear convergence which is when you have if the function is strongly convex it goes down really really fast gradient descent. If not, if the function is not strongly convex, the best you can do is sublinear, which looks like this. Okay, there's a even much faster algorithms called quadratic or superlinear. But this cannot be so that's if you've studied these, you kind of have like Newton methods and and second order methods which can achieve these kind of rates, but they're not achievable using only gradient methods.
Okay, so just the final comment here, optimization is central to machine learning. It is a huge field. Probably the most cited paper ever in machine learning is an optimization paper which I'll show you in a sec.
Okay, stochastic gradient descent. This is the workhorse of modern machine learning. Okay, so remember that our goal is to minimize this function which is an average across all the data points of loss functions maybe with some regularizer. Let's ignore it for now.
Okay. And if you have a very large n just computing this function or the gradient of the function is very expensive because you need to sum across all the points. If you have 10 million points every time you need to compute the gradient step you need to compute 10 million gradients. Okay, which is very very expensive. So what is stoastic gradient descent? Sure many of you know start somewhere. Okay. And now you iterate and at each iteration you choose a point maybe at random in the stoastic case at random choose a step size and then you take a step of that size in the direction of the negative gradient but only of one of the terms of this function not of all the function but only one of them. Okay. Um which is the gradient of the loss only the loss computed for that example for that sample in the training set. Okay.
I think everybody the first time you see this is this is really stupid. This is a very bad idea because I need I have this huge average of 10 million points. I need to go down in this function. How can I go down if I just look at one at a time? It looks like it's impossible.
Doesn't make sense.
Let me show you two motivating examples.
Maybe you've seen it before, maybe not.
The first one is is uh the best known probably is computing a mean. So you have to compute the mean of a Have you seen this example? computing a mean. You you want to compute the mean of a collection of numbers. Okay, one over n sum of the number or vectors matter.
Okay, it is well known that the mean of a collection of numbers is the solution to this optimization problem. You take so you have suppose these black dots blue dots are the numbers these x i and I want to find their mean. By mean I mean sum them all and divide by n. Okay, it's easy to show that this mean is the minimizer of this problem which is sum across all the points. The difference between the mean and all the point and each of the points squared. Okay, which is shown here. So if you minimize the sum of all these parabas, the solution to the minimization of the sum of all these parabas is this point which is the mean of the points. Okay, look this looks exactly like u this right sum of losses across points sum of losses the loss in this case is just squared let's compute the gradient okay so each of these functions is this the gradient of the square of the difference is just the difference itself there's a 1/2 to cancel out the two so the gradient of this loss is theta minus x i right are you with Okay, so you know it started at point zero and now you're going to sweep all the points and you do the following. At each iteration you take one one of the points the next point use a step size one over t. So the steps the step size is going down 1 / t and you take a step of size alpha t which is 1 / t in the direction of the negative gradient. So you take the previous theta, you compute the gradient which is there theta minus xt here and you multiply by the step size which is 1 / t.
Okay. Now because theta t minus one is there and there this can be written as t minus 1 / t * theta t minus one plus 1 / t minus cancel with this minus one over txi.
What is this doing?
Notice that t minus one t theta t minus one. What is t theta t minus one? t theta t minus one is the mean of the points from 1 to t minus one. When you multiply by t minus one instead of the mean you get the sum of the points because you unnormalize the mean. So now once you unnormalize the mean you add the new point and now you divide everything by t. So you're computing a mean of of points. you have you're in seven, you have the mean at 7.
If instead of the mean of the first seven points, you want the sum of the first seven points, you multiply the mean by seven and you get the sum. Now you add the new point and divide by eight. Okay, so what this is doing is computing an average in a recursive way.
Okay. So what and [snorts] it is crucial that you use the step size one over t because you need to normalize by the correct number of points up to that point. Okay. So this is first motivating example. Second motivating example.
Computing an expected value.
Suppose you want to compute expected value of some random variable mu which again can be seen as the value that minimizes the expected value of the square of this thing I'm trying to look for and the all possible samples of x.
Okay, now let's do SGD. Now it's not sequential. It's not a sequence of numbers. It's a it's samples. Now you sample you obtain a sample from X. Okay.
And you keep on doing the same algorithm again with step size one over t.
Okay. So what you do w now notice that these ws now are random variables because it depends on the samples that you get. Same as before previous value plus step size this the the loss because this when you compute the gradient of this you just get w minus xt okay because it's the gradient of a square. It's just a difference. Okay, so this is just a random sequence. Okay, now this is a bit more complicated. I'm not going to do it in detail. Uh but the expected cost, which is the expected value of the thing you're trying to minimize, which is this r is sigma over 2 over2 multiplied by this quantity. The optimal cost, you know what it is because you know what the expected value is. If you just plug that the expected value, you get sigma over two. So when you subtract the two you know that the error that you obtain by doing this goes down as something which is unavoidable which is the the variance of the variable divided by n.
So as n goes to infinity this go to zero and so this process will convert to the expected value of the variable. Okay. So um another view which is actually the I think the strongest one is um looking at what we really would like to do.
Remember that what I would really like to do is minimize the risk which is the expected value of the loss. I cannot do it because I don't know the I don't know the distribution. I have samples. But suppose I pretend that I know this and I'm going to apply stoastic gradient descent to this by sampling obtaining samples from X and Y. Okay. So to do gradient descent, I would need to compute the gradient of the risk. The gradient of the risk is the gradient of the expected value of the loss. But as I'm sure you know, gradient of the expected value or expected value of the gradient are the same because they're both linear operations. Okay? So which means that this gradient the gradient is an unbiased estimate of the of the gradient of the risk. So the gradient of the loss is an unbiased estimate of the gradient of the risk because its expected value is actually the gradient of the risk. Okay. So now if you do stoastic gradient descent with samples from this okay you just sample and you do stoastic gradient descent. So t theta t + 1 is theta t minus step size gradient of the loss at that particular sample that you obtained.
These are all random variables. If you compute expectation of everything expectation of the t + one equals expectation of these minus alpha expectation of this but expectation of the gradient is precisely the risk. So essentially if you're doing stocastic gradient descent you're actually doing gradient descent on the risk.
Exactly the monstrally like this. So you're just doing what you really would like to do. Okay. So in expectation what stoastic gradient descent is doing is gradient descent on the risk which is your ultimate goal. Okay. Of course you need to go on forever until it converges but but it's exactly what you want to do.
Actually it can be proved I'm going to skip this more theoretical result that if the function is convex or strongly convex you can go down. This converges at a rate which is log t over square root of t or log t over t. Uh so it actually converges to the to the optimal value.
There are a few caveat here but I'll skip this. So sgd is actually very very old. Okay. Stoastic gradient descent.
The original paper that proposed this was from 1951. Okay.
Long before I was born actually. I'm old and I was not even I think my parents were not even married then was really old and it got a really really strong boost uh maybe 20 years ago in a very famous paper by Bhut actually we will have Leon Bhutu tomorrow at afternoon talk going to talk about something else but he is one of the the the founding fathers let's say of the modern use of stoastic gradient descent uh in in machine learning so this is a slide I usually he used in my life and everything. It's a it's a picture by Gabriel Pere. I don't know if any of you know Gabriel Pere. Anyone knows Gabriel Pere?
Couple of people. He's a a French researcher from in Paris. And he used to tweet when Twitter when X was called Twitter. Math little math tweets which are very useful. If you you can search for them, they're still there with very simple and nice summaries of important ideas in math and and machine learning.
This is one. This is precisely this idea that we've been looking at.
The idea is that if you want to find the minimum of a function which is a sum of functions for finite sums like for the average and you know to compute the gradients then instead of sampling the idea is that the average of the gradients is essentially the actual gradient of this total sum. And so and the same thing in expectation which is what we saw in the previous slide. If you sample from the distribution, you get a gradient whose expectation is the actual gradient that you want to minimize. And then they showed it's possible to show this is famous paper from 51 of Robin and [clears throat] Muro. This is Herbert Robbins. It goes down as one over K if the function is strongly convex.
Actually, this is Herbert Robbins. He's a very very famous mathematician. I don't know if any of you ever seen a book called What is Mathematics by Kuran Robbins. No anyone knows the book highly recommend very very interesting book called what's mathematics and uh it's one erot Robbins is one of the authors of that book is a very famous mathematician okay tricks of the trade in practice how is this used of course choosing step size is critical it's a active research area as I as I mentioned decay so the step size needs to decay we know you know that often needs to go in theory often needs to go down as as we've seen either continuously there are lots of when when it comes to dealing with non-convex functions all of the theory falls and we need to get some some hacks and some uristics shuffling the data usually helps and most importantly mini batching so nowadays very rarely use pure stocastic gradient descent with sample by sample typically we use a collection of samples called a mini batch and we average the gradients not of the whole data set but over a mini batch. You have 10 million points, use mini batches of size 10 or 50 or or 100 or whatever and you average over them. So there's a trade-off, right? Suppose this is the function you want to minimize. If you're doing full batch, which means all the data points typically this you go actually go down very fast to the minimum. If you use purely stoastic gradient descent, you get very noisy local gradients. On average, they're pointing in the right direction, but each one of them may point in stupid direction. And if you use mini batch, you have a compromise between the two. The bigger the mini batch, the smoother the the smoother the the optimization path is. But there's a trade-off because the bigger the mini batch, the more expensive each step is.
Okay. So, this is like a a drunken walk.
Like if you ply sober here, you're very drunk. Here you're kind of mildly drunk.
um kind of path.
So there's a very particular very important property of of of stoastic gradient descent actually of gradient descent in general in the particular case of linear of linear classification and linear regression actually. So remember [clears throat] that in in in in many loss functions as we saw before the loss function can be written as some function of the product between um the label and the prediction. Remember this we had like sign or logistic or exponential or hinge or one of those applied to this thing which is called the margin. Okay, remember this my prediction would be something like if this is positive and this is positive then the loss is zero or small. If this is positive and this is negative or vice versa and the loss is high okay something like this it could be the hinge loss logistic loss squared loss all of these can be written in in this way. Now suppose we're going to do gradient descent or stoastic gradient descent doesn't really matter when you compute the gradient of each of these with respect to theta following thing happens. So this is a composite function there's an a linear function inside and then there's a nonlinear function outside which is one of these. So to compute the gradient how do you do you do you compute the gradient of these at the value of the argument times the gradient of the argument. That's how you compute the gradient of a composite function. Right? So it's derivative of L with respect to its argument with the argument computed that where it is right now times the gradient of this. But the gradient of these is a linear function.
What is the gradient of this? It's just with respect to theta. Of course, all the gradients are with respect to theta.
The gradient of this with respect to theta is just yi * x i because yi is just a scalar and the gradient of an inner product is just the other vector. Right? So this looks like this. It's a gradient or whatever you are times yi times x i which means that each of these gradients points exactly is colinear with the corresponding sample x i.
Which means that every time you take a step stocastic gradient descent with a G with some point you're taking a step in the direction of that point either in the positive or negative direction doesn't matter because it depends on this function here. Okay, which mean is each SGD update moves TT in a direction parallel to sample to go to the corresponding sample that you visited.
If you do a mini batch instead of being in this sample is in the average of the samples in the mini batch.
Okay, so this has a very interesting consequence. One of them is historical.
It's this one. Okay, suppose that the loss function we're using is the hinge loss. So remember the hinge loss. Sorry for going back. I doing this. I know it's very very horrendous for one everyone watching.
Hinge loss is the green one. It's this one straight line up to tow or one and then zero from this point on. Okay.
Is the one that underlies support vector machines.
Okay. Oh, in loss. Okay. So, because it's like a straight line and then zero.
If you compute the derivative, it's minus one all the way to when it touches zero and then it's zero from that point on. So, it looks like this. Okay.
How do I hide that?
It will go away.
Yeah. Okay. So which means that when you when you do an SGD iteration okay what you're doing is you take the current parameter current parameter and you multiply by alpha which is the step size times this in this case this is minus one so because gradient descent the minus becomes a plus if this is less than toao which is this point where the kink happens there okay and it's zero otherwise okay so intuition is very simple the points with the wrong classification, okay, or insufficient margin such that this is not big enough will move the parameter towards or away depending on the Y. If the Y, if the example is positive and the score is not high enough, what the step will do is approximate theta from the point to make it higher. The next time it visits this point, it will be more likely to be correctly classified. If the class is minus one, it moved it in the other direction.
Okay? And this is a very very famous algorithm called the perception algorithm invented proposed in 1957 by a very famous u person called Frank Rosenblot actually with tow equals zero which is a simple case and it is a precursor of modern neural networks. So this gradient descent on a loss function goes back all the way to 57. So anyone here heard about Rosen blood perceptron many people good. So I like to bit the history. So this was 1957 and even at that time they already have very strong hype surrounding machine learning. Right? So this is a this is a an interview he gave to the New York Times or an article and it says Dr. Frank Rosenlot designer of the he was a psychologist actually he worked for the Navy. Dr. Frank Rosenlot designed the perception conducted demonstration. He said that the machine would be the first device to think as the human brain as the human beings. Perceptions will make mistakes at first but will grow wiser as it gain experience. Dr. Rosenlot, a research psychologist at the Cornell Areronatic Laboratory said perceptions might be fired to the planets as mechanical space explorers. And there's in another part I don't have it here. He says that it's expected that perceptrons will become conscious of themselves and be able to reproduce. So this idea of very very strong hype around these machines is not recent. Uh okay I I'll skip the story.
So there's after few years later there was this very very famous book called perceptrons written by Marvin Minsky and Sim Papard that showed that in a sense these machines were very very limited because they were only able of doing linear classification and uh and this kind of shot the all the enthusiasm around perceptrons and it it became very they were abandoned for many many years.
This the the implementation was amazing because the these thetas these thetas nowadays we think of them as variables in a in pro in a program right code right there's no machine right machine is just a computer GPUs and TPUs and stuff and the thetas are numbers okay but in the perceptron these numbers were potentiometers we know what potentiometer is like a a dial to move and the algorithm used little electric engines to move potentiometers it was electromechanical made noise when it was learning. It was an amazing machine.
Okay. So, um actually soon after so in ' 62 there's a very famous u theoretical paper which is called the perceptron mistake bomb by Novikov um which showed that perceptums worked. So it's the first um machine learning theoretical result. Um it uh it it showed that if the training data is linearly separable which mean that if the points in the two classes are linearly separable there is a linear separation that separates them well uh with a certain margin which essentially means that they are sufficiently well separated. I'm going to skip and if the the radius of the data is limited if you don't if you you know that what they are inside this ball of radius R then the perception algorithm is guaranteed to find a separating hyper plane in at most are two divided by gamma 2 mistakes. Okay.
So it makes sense because gamma 2 if gamma is small it means that the points are not very clearly separable that the clouds are close to each other. It takes a while it takes long to find the boundary. If the if the if the gamma is if the margin is large, it means that the clouds of points are very well separated. So it's very easy to find separating. And the proof I'm not going to go over it. The proof is one slide.
If you like math, you can uh look at the proof. It's based like almost every important proof in mathematics on the Koshy Schwarz inequality. Um and it's a very elegant, very simple proof. It's a and it's the first considered the first theoretical result in machine learning and it's it's cool. It's interesting to know. Finally, uh implicit regularization. So remember that we just saw that every time you take a step in stoastic gradient descent if you're doing linear for a linear problem uh where it means the sample that you choose at random in iteration t. So this is the step you take. you are at some position theta t minus one you compute the gradient and the gradient is always necessarily in the direction of the some point that's what we saw in the previous slide here okay so the gradient is always something times x i always moving in the direction of of one of the axis one of the samples okay same is true for mini batch okay it's just not just one it's bunch of them but a bunch a linear combination of points is is is just in this in the span of these points. Okay. So it means that if you initialize gradient descent or stoastic gradient descent mini batch or full batch it's just this sum is either a small subset or all of them. Okay. If you initialize at zero this means that you're always inside the span of this training point because you're always adding some constant times training points. you never moving out of them.
So, so in the over parameterizer interpolating regime, okay, we know that fstar equals zero has many solutions and we know that as we saw in the represented theorem with the optimal solution is necessarily in the subspace that is generated by the sample. It's never outside. Okay. And so what what this does is that when you do gradient descent, you guarantee that this is always true. You start with theta equals 0 and you always move by adding or subtracting to theta linear combinations of axis. So you're always in the space generated by this axis never outside. Okay. So recall the represented theorem that we saw. Um there the the theta be belonged to the span of x of the x i from this explicit penalty which was the minimum norm solution that we were looking for. Actually when we're doing gradient descent we don't even need to do that because if we start at zero it's guaranteed that you are inside the span of the point. So this is actually this is a starting point for a lot of theory about deep learning and understanding why deep learning works because this graded descent has this very interesting very interesting properties. Of course, you can also do explicit regularization which nowadays is called well we saw it was called regression but nowadays it's called weight by adding this squared norm. Um and if you let gradient be a batch or a stoastic gradient of the empirical risk and you have this uh this gradient the gradient of these of course is just lambda* theta because the gradient of a squared is just the parameter itself.
And now if you add if this is the gradient of these the gradient of the sum is the sum of the gradients you just have this new version which is theta t minus one step size gradient of all of these.
But now you have theta t minus one in two places here and here. So this is one minus lambda* alpha t theta t minus one minus the gradient of the loss. And as long as alpha and lambda are small enough, this quantity here is less than one. So what this does is if you use these and you do gradient descent, the resulting algorithm looks like this.
Take your current parameter estimate, shrink it by a bit and then do the gradient descent step. Okay, this shrink it by a bit means multiplying by one minus something. This would be like 0.99 or something because the product of these two is something like 0.01 or 0 something. Okay. So this is a 0.9 0.99 depends on the choice of the parameters.
So theta t minus one is shrank or decay before being updated. This is why it's called weight decay.
Another very important trick is momentum. Okay. So momentum is this other part here. Okay. So gradient descent without momentum is this thing here. Wherever you are minus step size times the gradient. And momentum says also consider moving in the same direction from which you were coming.
Okay, it's like the point that's traveling in the parameter space has mass and inertia. That's why it's called momentum and it wants to keeps on going in the same direction that it was coming from. Okay. So this is a very easy nice picture. I usually project this on the board and go there with the pen but here I cannot do that. So for example, take this uh point here. Okay, consider these level curves of the function. So darker is lower, lighter is higher. So if you're here, right here, can you see my Yeah, you can hear. In what direction is going down? It's in this direction right here. It's going to the darker region.
Oh, it's not so easy. Going down is going in that direction. Okay, but I was coming from there. So I'm coming in this direction.
And if I want to continue going in this direction because it's this term here, I would if I had nothing, no gravity around me, inertia would take me in this direction here. But gravity is pulling me in this direction.
So the resulting is the sum of this direction given by the momentum with this direction given by the gravity of the function. And so the resulting is something in the middle. Okay. So, it's like it's it's like if you have you're going you're a skier, okay? And if you are a very very very very light skier and you're going down this valley, you wiggle a lot around before you get to the bottom. If you're a pretty heavy skier, you have a lot of momentum and so it's not easy to change your direction.
Okay? And so this is like a mildly heavy skier going down this valley until it reaches a solution. If it had no momentum at all, this would be much much worse. So for example here it would go in that direction and then coming in this direction and then going in that direction and then coming in this direction. Okay, momentum makes a huge difference in accelerating all all these algorithms. So finally the three um sort of that I usually sometimes have this more detailed. So all the modern techniques namely Adam okay you've probably used who has used Adam?
>> Yeah. A lot of people. So Adam, the key idea behind Adam is that you're going to do a separate step size per component of theta. It's not one step size for all the components. Each component has its own step size. So the step size is no longer just a number. It's just it's a it's a vector of numbers, one per component. If you have a million parameters, you have a million step sizes, one per component. And the step size looks like this. It's like some fixed number divided by the square root of some quantity. Okay, which is trying to adjust. So it depends on J. J is the component. T is the iteration time.
Gradient is the gradient computed that wherever you are right now. Okay. And so there are there's this this family of methods. Historically first it was adrad then RMS prop which was proposed. This was never published actually. It was it was described by Jeffrey Hinton in a lecture and it's known from that lecture. No one never wrote a paper on this. it's it's just known. Uh so the gradient the idea is that you should accumulate values of the gradient because if the gradient is is very is very large in several consecutive steps it means that you're going down too fast then you should slow down a little bit in that direction and you do that by accumulating squares of gradients and then making the step size inversely proportional to that. Okay. The problem is with this is that the step size vanishes because you're always adding positive step or non- negative step. So G can only go up because you're adding squares to it. And so the the the algorithm even if it's for no reason if not even if the gradients are zero it will slow down very fast because of this. Then Hinton said yes no let's do something clever. Let's multiply this gamma by a constant. Let's do this convex combination of the previous G with square and because of this even when the G's are zero when the little G's the gradients are zero the fact that we have this constant here which is something like 0.9 will make G not necessarily increase and so it's no longer true that the step size is going to go to zero okay and finally atom is a combination of all of these it's combination of RMS prop with momentum with another with a couple of other tricks and uh it's also bias correction and so on. And this is probably I think it is the paper that proposed Adam is probably the most cited paper in machine learning. It has a quarter of a million citations uh in 10 years and it's a it's a the def facto standard in most optimization.
Okay. No, at the end I always have this uh should we bother with convex optimization in 2026 when all deep networks are very very strongly nonconvex uh objection deep learning objectives are severely nonconvex almost nothing above applies that's true okay but uh the algorithms are the same there were no algorithms designed for non-convex optimization there are but they're not used in machine learning at all so all std momentum atom all the analysis based convex ideas and they still use the applied. There's no such thing as a non-convex optimizer being used in machine learning. Um the practice inherits from the theory. All of these ideas step size decay averaging momentum preconditioning which you haven't mentioned. They were all born in the convex setting and they're still standard stuff like layer normalization and all this stuff they have their justification from inside convex optimization.
The last layer is convex as we saw is the softmax linear but softmax. So in that case we're actually doing what all of these says we should do. And it's also good to know this theory of convex optimization because when things fail typically we can find the the the the reason in some assumption that's being that's broken that's not valid. It's not smooth. It's that maybe the gradients are too large. Maybe there's poor conditioning. So a lot of tricks in deep learning come from these observations from inside convex analysis. And finally the implicit regularization that we saw in gradient descent and scastic gradient methods provide insight on why deep learning works and there's a lot of lot of work on on on this.
Okay this brings us to the end not too late. Uh recommended books or reading.
So it depends on what you like and what your taste is and what your interests are. So this the first one is currently my favorite book in machine learning.
It's a an excellent amazing book uh by Maurice Moritard and Ben Re. It's and it's freely available online. They're all freely available online all of them legally. Um the other one is by Francis Bach. This the second one is by by far the most theoretical and and most difficult. The other one is very very very big. It's Kevin Murphy's. So the second edition of Kevin Murphy's very famous book now it's a probabilistic machine learning from three years ago and this other this other one is very good too by Andreas Krauss and and Johannes Ubot uh from from 205. It's more recent. It's also pretty light. This is a very nice book too. They're all very good different types of books um but they're all good to have and they're free and available so you can have them all. Okay. Thank you. I'm I'm be glad to take questions either now or I'll be around the whole week. Thank you.
Or we can all just go to lunch.
I'll be
Related Videos
TOP 15 Data compression Interview Questions and Answers 2019 Part-2 | Data compression | Wisdom jobs
wisdomjobs
281 views•2019-06-28
CTS 158: 802.11w Management Frame Protection
ClearToSend
4K views•2019-02-04
NDSS 2019 Send Hardest Problems My Way: Probabilistic Path Prioritization for Hybrid Fuzzing
NDSSSymposium
496 views•2019-04-02
How realistic is Cities: Skylines?
CityBeautiful
159K views•2019-02-14
GUIs & TUIs: Choosing a User Interface for Your Python Project | Real Python Podcast
realpython
2K views•2025-04-04
The OSI Model - Explained by Example
hnasr
225K views•2019-05-12
Cloud Computing - Introduction
elithecomputerguy
98K views•2019-10-07
From Traveler's Dilemma to Dynamic Routing | Demystifying Networking
IITBombayJuly
5K views•2019-08-04
Trending
WOW! Judge TURNS THE TABLES on Trump in His OWN $10B LAWSUIT!!!
MeidasTouch
197K views•2026-07-23
Playstation NO DISC/NO BUY Fight Is Over...
DavidJaffeGames
4K views•2026-07-23
Steam and Xbox Just Dropped The Hammer On PlayStation
OhNoItsAlexx
9K views•2026-07-23
Americans Confused in Australia for 17 Minutes Straight
IWrocker
17K views•2026-07-23