Support Vector Machines - The Math of Intelligence (Week 1)

Key Takeaways

hello world it's SJ and today we're going to build a support Vector machine to classify two classes of data I've already recorded this video before but I'm re-recording it because the sound quality and the video quality was not good and we have a standard to keep on this channel so listen up here we go we're going to build a support Vector machine to classify two classes of data right and the way we're going to optimize the support of vector machine this type of machine learning model is to use gradient descent okay so that's what we're going to do and this is what it looks like it's it looks like this so say we've got two classes we have one class that's going to be denoted by red dots and the other class is going to be denoted by blue dots so if we were to plot both classes on a 2d graph an XY uh graph then we could draw a line a decision boundary that best separates both of these classes and that line is is called a hyperplane and our support Vector machine helps us create it okay that's what our support Vector machine helps us do and we're going to talk about all the details of how this thing works but this is at a high level what it looks like and we're going to build it with just numpy and map plot live okay to graph it so no tensor flow or any of that all right so I hope you're as excited as I am for this because we are going to go into the theory as well as the code as well okay here we go so to start off with what are some use cases for an SP SPM so classification is one which we're going to do and that is in fact the main case that svms are used for that is the most popular case but they can also be used for other types of machine learning problems regression that is if we have some set of data points and we're trying to predict the next point in that set of data so stock prediction would be a good example and also time or call also called time series prediction there's also outl detection so say you have a security system and you're tracking all of your users and all of your users have a set of metrics a set of features that identifies them like the time that they've logged in and what they're doing there could be an anomaly and the anomaly could be your bad guy the guy who's trying to break into your security system and svms help you detect who that person is there's also clustering but we're not going to talk about which which is also um which is a form of unsupervised learn learning as there's outlier detection but we are going to do supervised classification that is when our data has labels right we are trying to learn the mapping between the labels and the data and if we learn the mapping that is a function the function represents the mapping the relationship between these variables if we learn this function then our machine learning model has done its job then we can use this function to plug in some new input data and it's going to Output the prediction right and this is all of machine learning really so let's look at this so in this example we're going to use toy data right because it's more it's it's about the uh it's about the math and the algorithms but I have these two other examples for you just in case you want to do something a little more useful so the first one is for handwritten digit classification right you have our we we have a set of digits and they all have their labels and we want to learn the mapping between the labels and the digits and so that's what this repository will help us do and the great thing about this repository is it's using scikit learn which is a very popular machine learning library in one line of code you could Implement an spvm but we're going to implement it from scratch because we want to learn how this thing works but once you've done that then you can go on to using something easier something simpler like this okay and it's a real world use case I've got one more example here that I've that I have for you guys and that's for pulse classification so the idea is that for a human given some metrics like their age and their what was the other one their pulse rate obviously we can predict what their emotions will be so it's emotion classification and we're using an svm in this repository as well as well as psych it learn to implement that svm so check out those two repositories once you really understand the math behind support Vector machines from this video and from the associated code okay so uh yeah so those are two other examples so how does this thing compare to the other machine learning algor and there are so many of them there are random forests there are neural networks well as a rule of thumb svms are great if you have small data sets so I'm saying like a thousand rows or less of data right a thousand data points or less if we have that then spms are great for classification and they are very popular however other algorithms random forests deep neural networks Etc require more data but almost always come up with a very robust model and the decision of of which classifier to use depends on both your problem and your data and as you build this mathematical intuition all of these choices will become very clear to you so we're starting off with the support Vector machine okay and so I also have this quote by this famous computer science Professor Donald K who no I know the ks Island Donald new who said that premature optimization is the root of all evil or at least most of it in programming and what does he mean by that that means if you can make a performance gain by using something way more complicated like a deep neural network but it's only going to be like it's only going to be by like 0.1% then it's unnecessary your time as a programmer is very valuable and you only want to do the minimum amount of work that you have to to get the results that you want so if you're trying to use a deep nural Network for a problem that only requires is something very simple like a support Vector machine you should use a support Vector machine not the Deep nural Network just because it's hot and it's outperforming everything else almost all the time because it requires more Computing data and way more uh it requires more computing power and way more data right two things um which if you don't have don't use it use a support Vector machine right these are all methods of intelligence the this is all about the math of intelligence and there are many ways toach it so what is a support Vector machine so this thing can be used for both classification is it this is it this is it this and regression got these points what's the next point in the series so given two or more labeled classes of data remember we are using supervised learning it can create a discriminative classifier that is a classifier that can discriminate between different classes is it this is it this is it this right and the opposite to discriminative by the way is generative where we generate new data we take some training data variate vary it in some way using our model and that output is very similar to the train data but it's novel data but that's for later on anyway so the way we build this hyper plane and we'll talk about that term but the way we build this hyperplane or line this decision boundary between the classes is by maximizing the margin that is the space between that line and both of those classes what do I mean by by that when I say both of those classes what I actually mean are the points in each check out this image are the points in each of those classes that are closest to the decision boundary and these points are called support vectors okay we call them support vectors because they are vectors they are data point vectors that support the creation of this hyperplane that our support Vector machine will create right so we are maximizing the margin and why do we do that because we want to draw a line that is in the absolute perfectly the perfect middle spot between both of these sets of data such so that when we plot a new data point if if it is of a certain class it will have the maximum likelihood of falling on that side of of the decision boundary where it should and the only way to do that to maximize the space with which a a a new data point can fall into its correct class category is to maximize the space between data points and put a line right in the middle of that space do you see what I'm saying I can't get feedback but I'm just going to assume that that that that was intuitive right so right so small margin we're maximizing the margin and we're going to draw a decision boundary a line of best not a line of best fit but a line of best classification between both of those and we call this line a hyperplane okay so what is a hyperplane well a hyperplane is a decision surface so given n Dimensions right so let's say our data is n dimensional where n is the number of features that you have length width height tongue color tongue color where did that come from tongue color and skin color and whatever other colors and so um a hyperplane is n minus one Dimensions so if you have a two dimensional graph where just like this on the left right here where I'm pointing my mouse where this R symbol with the two uh exponent denotes a two- dimensional graph a hyper plane would then be 2 - one right n minus one so one dimension so it would be a line right but if if we are in three-dimensional space r r to the3 then a hyperplane is going to be two dimensional because it's 3 - 1 which is two right so we have a plane and so you we can extrapolate this to many dimensions so if we had a 400 dimensional space which we often do in machine learning our data doesn't just have two or three features it has many many features right it's not so neatly packaged for us to visualize and that's where techniques like dimensionality reduction and all this come into play which we'll talk about but right now if we have a 400 dimensional space uh graph of points then a hyperplane would be 399 Dimensions which we can't really visualize I mean think about it humans we are not that good at visualizing or in fact it's impossible for us to visualize anything in more than three dimensions but for machines it's very easy it's very intuitive and that's all that matters as long as our machine is able to draw this decision boundary of n minus one dimensions then given some new data point if we put it into that uh model that functions that functions um if we put it into that function if we plug it in then it's going to Output the correct class of whatever it is okay so and this actually comes from geometry so I guess there is a little bit of geometry in machine learning right so nonlinear versus linear well we're only going to talk about linear classification because nonlinear classification is more complicated and we'll get to that but the idea here is that let's say you have some uh you know some sets of data some some two data sets right two classes of data the best let's say the best uh the line that best separates these two classes of data isn't linear let's say it's got curves like in this in this example right here how are we supposed to build a hyperplane like that it well it would be more complicated and there is actually a trick to do this called the kernel trick and we'll talk about that later but there's a way to take that map that input space into a feature space such that the hyperplane that you draw is linear even though it wouldn't be otherwise and so that's called the kernel trick and we'll talk about that later right so we're only talking about linear classification for support Vector machines super supervised linear classification right as opposed to unsupervised anyway there's so many different ways that we can frame this problem right there's so many different ways we can frame the learning process and more will be discovered so it's a very exciting time to be in this field okay so let's get let's go ahead and uh get to building shall we but first of all I also want to say uh one more thing so no matter what model you're using a random Forest a support Vector machine a deep neural network in the end we are approx IM ating we are guessing uh iteratively close we are we educated guessing I'm trying to think of a different word for approximation but we are approximating a function right we are trying to find what is the what is that optimal function and that function represents the relationship between all the variables in our data right that function is that is that is that relationship it's that mapping and if we can find that function then we have learned we have learned from our data and so every machine learning model under the hood is just a function that we are trying to approximate and its coefficients are its weights and they are being updated over time through some optimization technique be that gradient descent usually or Newton's method which we'll learn about or you know whatever it is okay so yeah so whatever it is we're just trying to approximate a function right this is a way of thinking approximating a function whatever we're using decision Forest whatever we're using it's all about approximating a function decision trees all right so let's go ahead and and get to building right so first we're going to uh import nump and so numpy is going to help us perform math operations Matrix math and then we're going to plot our data using map plot Li okay so the first step is for us to Define our data so our data is going to be of this form XY bias so the first so there are five data points here right there are five data points and we've got the x coordinate the y-coordinate and we've just input our bias into our data to make things easier later on but we can for all intensive purposes ignore this bias term but we are basically just H we we have this set of XY coordinate pairs that we can plot on a graph and each of these data points has an Associated label an output label that output label is either a Nega -1 or a one okay so for the first two they're going to be negative 1 and for the last three they're going to be one so these last three so what we can do is we can plot these examples on a 2d graph okay so we can say let's plot the let's plot the first two with the negative marker and let's plot the last three with the Positive marker okay and so when we plot it it looks like this and what we're also going to do is we're going to print is is we're going to plot a possible hyperplane that is a hyperplane that is just a line that we don't know it's just our naive guess we don't know if it's the optimal hyperplane in fact it's not but just so happens to perfectly separate our training data classes just so for us to just see what it looks like right this is just for that example okay so that's that so now what we can do is get into the math so I hope you're ready for this all right so let's get into our calculus all right so right machine learning machine learning is all about optimizing for an objective function and the way we optimize for an objective function is by minimizing a hope you said loss or error function because that is the correct answer we are minimizing a loss or error function so let's go ahead and first Define our loss function our loss function in this case is going to be called the hinge loss so the hinge loss is a very popular type of loss function for support Vector machines okay and the class of algorithms that support Vector machines fall under are maximum margin classification algorithms right we are trying to maximize the margin that is the distance between classes such that we can draw the best uh decision boundary between those classes that best separates both of those classes okay so this is what it looks like this is what the hinge loss looks like the hinge loss looks like this with the word c that's how we denote the hinge loss given these three terms the three terms are going to be x y and F ofx where X is the sample data Y is the true label and F ofx is the predicted label right so it's going to be 1 - y * time F ofx and this little plus sign down here just means that if this result if the result of this op these sets of operations is negative then we're going to just set it to zero because we always want the result to be positive okay so what what this means is we can break this down into this equation right here where my where where my mouse is now over where we can say if y * f ofx is greater than or equal to 1 which would make this come out to be 1 minus a number that's greater than one which would be zero or a negative number then set the result to zero because we want it to be positive and if it's not then it's going to be some non- negative number greater than zero okay so that's our loss that's how we Define our loss and remember these this Y and this F ofx both of these values these scalar values these single values are going to be a single number right and that's what that's why we can multiply them and so our objective function then is going to consist of the loss function which noticed how it looks a little different but it's it's really the same thing this 1 - y * x uh xw it's the same as this law up here it's just a different way of denoting it and we can say the sigma term means that we're going to take the sum of terms where the number of terms is n and n is the number of data points that we have so for all five data points we'll find the loss of each of those data points using this this loss function the hinge loss and we'll sum them all up together and that that that total sum will represent our total loss for our data right that's a single number it's going to be a single number and then once we have that we're going to Define our objective function so our objective function in this case is going to be denoted by this Min Lambda W okay with the square sign and so what is this our so our objective function is going to be denoted by the loss plus this regularizer term which is denoted right here with this Min and the Lambda so a regularizer is is a tuning knob and what the regularizer does is it tells us how best to fit our data so if the regularizer term is too high then our model will be overfit to the training data and it's not going to generalize well to new data points it's going to be overfit but if the regularizer term is too low then our model is going to be underfit so that means it's going to be too generalized and it will have a large training error so we need the perfect regularizer term to for our model to be as iable as possible and fit to our training data it's that balance term right and it's it's also it also comes out to be a single scalar so given our weights we square that um and then we use this lamb Lambda term here uh we multiply by by this Lambda term okay so um right so that's our objective function our objective function consists of our regularizer and our loss function we add them both together so what we want to do is we want to optimize for this objective and by optimizing for this objective we're going to find the optimal regularizer term and we're going to minimize the loss so we're going to do two things by optimizing for this objective and so the way we are going to optimize is we're going to perform gradient descent right and so the way we're going to perform gradient descent is by taking the partial derivative of both of these two terms of both of these terms we're going to take the partial derivative of the regularizer and we're going to take the partial derivative of the um of the loss term okay so this is what it looks like right so remember from the power rule for partial derivatives all we have to do is move the power to the coefficient and then subtract one from the coefficient and then for the other term we do the we do the same thing and so for the loss term we do the same thing and it comes out to this and so it's it's going to be zero or it's going to be- y * X so there's a there's a case for both of them okay so then what we what we then have is a misclassification condition and a classification condition so we can so we can so basically we can say if it's misclassified so if we misclassify our data depending on these partial derivatives then we can update our weights a certain way and what I what do I mean by a certain way I mean we can update our weights by using both the regularizer term and the loss function term okay because this isn't zero it's going to be negative y * X but else if if we if we have correctly classified then this value is going to be zero it's going to be a zero so we don't need to update our loss we only update our reg we only update our weights using our regularizer term and so this term right here is a learning rate by the way so it's weights plus learning rate times the regularizer term the learning rate by the way is how we um it's our is another tuning knob for how we uh how fast we learn so if the learning rate is too high as our model is learning it could just it could just miss it could just overshoot that Minima entirely it could just keep going but if it's too low it could take way too long to converge or in fact it could just never converge so we want to have that optimal learning rate okay so those are our terms and so now um now let me plug into some power here okay so so now let's get into the code for this right we've talked about the math let's get into the code so for the code part we can say all right well we want to initialize a support Vector machine we're going to perform stochastic gradient descent by the way but we're going to initialize a support Vector machine with a set of weight vectors and these weight vectors are the coefficient of the model that we're trying to approximate there are three values that we initialize with a set of zeros then we have a learning rate which is one a number of epoch which is a which is iterations to train for over the data set over the entire data set and then a list of errors that we're going to store all of our errors in okay so basically we could say and now here's the machine learning part here's all of that math that we just did we can fit into these 10 lines of code right we are literally just taking those equations and converting them into code right now so we'll say for the number of epochs for so for 100,000 times we'll set our error to initially zero let's iterate through every single data point that we have so for all five data points so we have five data points we're going to iterate through all of them 100,000 times okay and so then we have our first case which is the misclassification case so in the misclassification case let's see what that was y * x w is less than 1 this is exactly what it comes out to programmatically y * the dotproduct of X and W is when it's less than one so if it's less than one then we have misclassified our data so we can update our weights using that full uh equation that we saw right up here right up here where we're using both our regularizer and our loss function to update our weights right because this is non zero it's going to be negative y * X using our partial derivatives and our partial derivatives are the gradient right they are the they are the gradient value that so that we can update our weights in a dire ction such that such that the such that the error is minimized that's what they're going to help us do okay and so we'll update our weights doing that and then we'll say well we got an error so let's make our error count one else if we've correctly classified then we update our weights using just the regularizer term which is one over the number of epoch by the way our regularizer term I think I might have forgotten to say that our regularizer term is one over the number of epochs so it's inversely correlated so that the regularizer parameter will decrease as the number of epoch increase and so the update rule for correct classification looks like this where we're only using the regularizer term all right so we've got that and so once we have that we can plot it out and we'll also uh add all those errors to this list of Errors so we just have that you know we want to see how the error frequency decreases over time during training that's the actual machine learning and so when we plot that we'll see that the error decreases over time the error value decreases over time and that's what we want right so we've trained our model right we've trained it on those five toy data points and so now what we can do is we can now plot this model we can plot this model and uh we can we can add testing data as well right but we have we had a misclassification case and we had had a correct classification case and depending on whether it was misclassified or classified correctly we updated our weights using a different strategy okay and the whole goal is to make those weights the optimal values that they should be such that our error value is minimized and we have the equations for that right here and the reason we took the partial deriv derivative is so that we can best update our weights to optimize for our objective function which consists of these two terms minimizing the loss and optimizing the regularizer term such that our data is best fit to both our training data and any novel data points we give it that is its generalizability right so hopefully that all makes sense that's essentially what we just did if you if you understood like 80% of that pat yourself on the back because you are a boss all right we are all bosses all right so machine learning bosses okay so back to this okay so now we're going to plot this data all right let's so let's plot it so if we have less than two samp examp samples then we'll plot it again so this is the same thing that we did before so we'll we'll do it again and then we're going to add our test samples so our test samples are going to be just two points and they're also going to be two toy data points but just assume that we know what class this data point you know consist of and so we'll add our two test samples plot our hyper plane that's trained on the training data and hopefully it classifies both the training data and the testing data accurately such that they all lie on the perfect uh side of the decision boundary so that they are correctly classified and so when we plot it we'll see that that is the case all the positive labeled data points are on one side of the line and all the negative label data points are on the other side of the line we have correctly classified both our training and our testing data by optimizing for our objective and by doing so we are minimizing our hinge loss so that we maximize the margin or the space between uh the two data classes so that we can draw the optimal hyper plane and we use the regularizer term that we also uh found the optimal value for by including it in the objective function so that our model was best fit to both the training and the testing data all right so that in a nutshell is how support Vector machines work so um to to go over uh this again let me just say that right so the gradient is a vector whose components consist of the derivative so in all of calculus we have derivatives and so the reason we take the derivative is because calculus is the is the math of the rate of change we want to know how something changes and the way we we study how it changes we use it in physics a lot too right for moving bodies the derivative is how we is is is how we is how we understand which direction Something is moving in right it's we derive the direction from it and there's several ways of representing the derivative in calculus we use the obviously the derivative which is the derivative operator but then we also use the gradient operator and so the gradient and so you hear these terms a lot you hear gradient and you hear derivative a lot but they're really the same thing in that the gradient is a vector who components consist of the partial derivatives of whatever coefficients of whatever function that we're trying to approximate okay and so that's the gradient and the derivative and and in the next week's lesson we're going to talk about the Jacobian which is a matrix of first order partial derivatives and also the hessen which is a matrix of second order partial derivatives and these are all words that represent how we organize and represent change in data in in functions right and with the reason we want to represent change is so that we can minimize for a loss we can optimize for an objective we can iteratively get closer and closer to approximating to educatedly guessing what the optimal function is so that we learn the mapping between data points okay so hopefully that all made sense all right so that's it for this lesson Please Subscribe for more programming videos and for now I've got to go invent a new type of svm so thanks for watching