‫Welcome back, everyone, to this continued discussion of the theory and intuition behind support vector
‫machines.
‫In this lecture, we're really going to focus on the kernel trick and the mathematics behind support
‫vector machines.
‫Previously, we've really only discussed the intuition behind these methods.
‫So we're going to do now is briefly go over the general mathematics of how we build up to support vector
‫machines.
‫And we'll also discuss how the mathematics is related to the psychic learn class calls.
‫We'll begin with a brief review of using margin based classifiers.
‫So expanding from maximum margin classifier to a support vector classifier, and then finally using
‫the kernel trick for support vector machines.
‫Now feel free to consider this an optional lecture which you can replace with the relative reading.
‫The background reading can be found in Chapter nine of an Introduction to Statistical Learning.
‫For a deep, comprehensive overview of everything discussed, you could check out the original publication
‫by Cortez and of APNIC called Support Vector Networks in the Machine Learning Journal.
‫Now let's first talk about hyper points defined mathematically.
‫Here I can imagine a two dimensional space with two features x one and x two.
‫A hyper plane is just a line in two features, which means I could define this mathematically as the
‫lines we've seen before.
‫A beta, not for the intercept plus beta one times x one plus beta two times x two and set this equal
‫to zero.
‫And there's going to be some set of betas that is going to define this line.
‫Now keep in mind, I could expand this to p number of dimensions, just continuing this where there's
‫a single beta coefficient for every single feature.
‫Now this is the mathematical definition of a plane for some P number of features.
‫Let's talk about separating planes.
‫The whole idea behind hyper planes for support vector machines is that they're separating out the classes,
‫which means I should start thinking about not just the plane line itself, but the mathematical definitions
‫of what I'm going to consider as a separating factor.
‫So I want to consider the values that are above zero are going to fall on one side of this plane.
‫Similarly, the values below zero are going to fall on the other side of the plane.
‫So now I have a set of equations that is able to define what side of the plane you fall on.
‫The last consideration we need to make in order to mathematically define something like a max margin
‫classifier are the data points themselves.
‫Something to note here is that when we actually type this out mathematically, typically we show the
‫actual feature points or data points as the transposed matrix of X.
‫That is to say that x one through n represents the number of data points and one through P represents
‫the number of features.
‫So notice that this is transposed from the way that we typically write out our data.
‫In something like a PANDAS data frame, it's the same data just transpose.
‫So then the columns of the rows and the rows of the columns, again, one through NN is the number of
‫points themselves, one through P is the number of actual features.
‫So in this case we would have two features x one and x two, given the diagram on the right and we would
‫have six points.
‫So one through six would be one through N.
‫Now let's use all this information to mathematically define a max margin classifier.
‫Recall that the whole purpose of a max margin classifier is to maximize M where M is this margin extending
‫from the hyper plane.
‫So we're essentially trying to choose the best beta coefficients that can maximize this margin, but
‫we do have some constraints.
‫We're subject to these two constraints given the data set.
‫So what does this actually mean?
‫Well, all this means is that what we're trying to do is consider the data points here.
‫In this case, we have six data points or one through RN.
‫And what we want to do is make sure that we fulfil this subject requirement where essentially the data
‫points are either going to be equal to or greater than the margin, depending on what side of the margin
‫they actually fall on.
‫This essentially is just a mathematical way of saying that for a max margin classifier, no data points
‫can actually be within the margin.
‫We're also subject to this some of squares for the beta coefficients being equal to one.
‫Now, this actually helps correspond to the other equation by determining that if you were to plug in
‫the features values into the equation below, if you're subject to beta squared and the sum of those
‫being equal to one, then y of EI multiplied by these beta coefficients times the feature value gives
‫you the perpendicular distance from the point to the hyper plane, and it ensures that that distance
‫is at least as large as the margin itself.
‫This is just to say that with this constraint, we are able to mathematically calculate the orthogonal
‫distance from any point to the hyper plane.
‫And here we have the full definition, mathematically speaking of a max margin classifier.
‫Again, given this transposed matrix of data points, we want to figure out the beta coefficients that
‫are going to maximize this m subject to these two equations, which essentially makes sure that the
‫points are outside of those margins and are falling on the correct side of the margin given their class.
‫And we're subject to this beta squared sum coefficient being equal to one in order to determine the
‫orthogonal distance from the points to the hyper plane.
‫Now let's move on to a support vector classifier.
‫Recall, a support vector classifier is different from a maximum margin classifier because it does allow
‫for MIS classifications, essentially allowing for some number of points to fall within the margin.
‫So we still want to maximize this margin and we still want to make sure we're subject to the sum of
‫beta squared being equal to one in order to be able to determine the orthogonal distance from the vectors
‫to the plane itself.
‫But because it's a support vector classifier, I now allow for some error term.
‫So notice I'm using epsilon and this epsilon is a relationship between some set C value where this C
‫value is going to determine how many mis classifications you actually allow yourself.
‫So it's pretty much the same equation, except now the margin has this error factor, epsilon factor
‫determined by the sum of the epsilon being less than or equal to see where the C can be provided by
‫the user.
‫And we're going to be able to use cross validation to solve for the optimal C in order to maximize accuracy
‫or maximize precision or recall depending on what we're actually trying to optimize here.
‫But this is the full definition of a support vector classifier, essentially the same thing as a max
‫margin classifier.
‫But with these added constraints or addition of the fact that we can actually have mis classifications
‫constrained by some value of C and as C goes to zero, then we actually back at a max margin classifier,
‫essentially not allowing for any errors.
‫Now a quick note on this value of C.
‫You should notice that the way we've defined it here mathematically, the larger the C value, the more
‫errors we allow ourselves.
‫Insight could learn due to the fact that they want to remain consistent across multiple models.
‫They say C as a regularization parameter, inversely proportional to the C shown in the equation here.
‫That is all to say that mathematically speaking, in the equations we're showing here, as you increase
‫C, you increase the number of mis classifications you allow insight could learn.
‫It's inversely proportional to the equation shown here.
‫Obviously they'll be more clear as we begin to experiment with psychic learn, but it's just something
‫to keep in mind that the C in psychic learns documentation and class call for support vector machines
‫is not exactly the same thing that I'm showing here in the equations or that you will typically read
‫when you're actually reading the equations for support vector machines.
‫It's actually inversely proportional to C, and that's just because they want that regularization parameter
‫to remain consistent across multiple models.
‫Okay.
‫So finally, let's move on to support vector machines and how we define these mathematically.
‫Recall that we need to use support vector machines where we're not able to find any clearly separable
‫hyper plane for our data points.
‫Here we have what looks like something we can't really separate with a line.
‫We have a bunch of points in the middle and then another class surrounding it.
‫So what we do as we previously discuss, is transform this to some sort of higher dimension or feature
‫space.
‫So right now I could have features x1x2 all the way to exp number of features and I could use something
‫like a polynomial transformation using x one and x one squared x to an x two squared all the way to
‫XP and xp squared.
‫In order to try to figure out if there's a hyper plane in this larger feature space that will successfully
‫be able to separate out these two classes.
‫And I can still allow for misclassification in this higher feature space.
‫So again, what I want to do is maximize this margin.
‫But now I have a lot more beta coefficients to consider depending on the feature space that I'm expanding
‫this to.
‫So if we just lay this out all mathematically, what we're doing here is we're adding the addition for
‫this simple case of a square polynomial.
‫Keep in mind, this is not a generalized support vector machine.
‫I'm just showing the support vector machine that we previously showed where the expansion of the feature
‫space was squared.
‫Essentially one of the simplest support vector machines we can possibly do.
‫So we're no longer just considering x1x2 all the way to XP, but we are also considering the squared
‫feature value.
‫I still want to maximize my margin.
‫M, but now I have coefficients not just for the original features but also coefficients for the squared
‫features.
‫And I am allowing for miss classifications which you'll notice are actually in the subject to Y where
‫it's greater than or equal to the margin times one minus epsilon, where epsilon is again defined by
‫this user parameter C essentially allowing for some misclassification even in this higher feature space.
‫So then the support vector machine with the utilization of this larger feature space would allow me
‫to figure out how to separate the actual feature space in order to classify these points correctly,
‫even beyond the constraint of the original features.
‫Since I'm now considering some larger feature space of things like x squared or x two squared, etc..
‫Now the main question that arises as we move on to a larger feature space is how do we actually deal
‫with this growing complexity?
‫Well, we only showed a simple example of a polynomial degree of two.
‫It's very likely that for more complex datasets, we'll need to grow this polynomial to a much larger
‫degree.
‫And as the polynomial order grows larger, the number of computations necessary to solve for margins
‫also grows to a point where it may be infeasible to actually compute that many margin calculations.
‫The answer to deal of this lies in the kernel trick, which makes use of the inner product of vectors.
‫This is also known as the DOT product.
‫Before we show you how we can actually use the kernel trick with our support vector machine calculation,
‫let's quickly review what a dot product or inner product actually represents.
‫So here we're going to simplify a dot product to just be between two vectors and recall that vectors
‫can be more than just two dimensions as shown here can be many, many dimensions.
‫But for simplicity, we're just going to use this in a two dimensional space.
‫I have vector A and vector B and the DOT product or inner product between these two vectors is defined
‫as the sum of each of their subcomponents multiplied together.
‫That is to say, if I have two dimensional vector shown here, then there's a subcomponent along the
‫x axis and a subcomponent along the y axis, which I could define as a one and b one along the x axis,
‫and then a two and B two along the y axis.
‫And you can imagine that as we move on to three dimensional vectors, four dimensional vectors, etc.,
‫there would be subcomponents for each of those dimensions and for the DOT product.
‫That would mean in this particular case, the inner product or DOT product between A and B would just
‫be the sum of each of those subcomponents multiplied together.
‫Now, you may also remember from your math classes that this is not the only definition or mathematical
‫notation for a product.
‫The product can also be defined as a multiplication of the magnitude of each of the vectors multiplied
‫by the cosine of the degree between them.
‫Now why is this important to also know?
‫Notice that if we start thinking of a dot product in this format, it's essentially a similarity between
‫the vectors.
‫So this is going to result in the same calculation as saying A one times B one plus a two times B two.
‫It's essentially another definition for the product.
‫The reason this is useful is because with this production of cosine of theta, it's a similarity measurement
‫between the vectors.
‫You can think of this by considering extreme cases.
‫Imagine that the degree between these was zero.
‫Cosine of zero is equal to one where that means that that product is essentially the multiplication
‫of the magnitude of vector A and vector B.
‫That makes sense because if the degree was zero, that means both these vectors are pointing in the
‫exact same direction, meaning that their degree or cosine theta is 100% similar, so it should be equal
‫to one.
‫You'll also notice in the case that these two vectors are perpendicular or orthogonal to each other
‫cosine of 90 degrees that would be equal to zero, meaning that in a product is equal to zero.
‫And then if they are pointing in exact opposite directions, that is cosine of 180 degrees, then we
‫would have a negative one, essentially saying it's negative one times the magnitude of a and the magnitude
‫of B.
‫So clearly we can think of this inner product as a similarity measurement.
‫So let's now move on to discussing the cardinal trick.
‫We can think of a linear support vector classifier in terms of this inner product, or we can say that
‫we have some function of X is equal to beta naught plus the sum of some alpha term times the inner product
‫of each pair of training points.
‫We essentially calculate the inner products of all pairs of training observations, and you can check
‫out the reading in chapter nine of Esler.
‫For a more in-depth look or you can check out the publication from Cortez and APNIC, as well as why
‫we're able to actually perform this calculation of inner products.
‫But for now, it's kind of just take it as is that I'm able to rewrite a linear support vector classifier
‫in terms of inter products.
‫Now, since I'm able to calculate the inter products of all pairs of training observations multiplied
‫by some alpha parameter, you'll realize that in this particular case, the alpha parameter is only
‫non-zero for the support vectors.
‫So let's back up a second and see if this makes sense.
‫I just told you I can rewrite the linear support vector classifier using this equation, which says
‫instead of calculating this beta coefficient times the feature value itself, I'm going to try to calculate
‫this alpha multiplied by the inner product of all the pairs of training observations.
‫But if I rewrite it this way, you'll soon realize that Alpha is only non zero for the support vectors
‫marked and yellow on that plot.
‫Now, does that make sense?
‫Well, intuitively speaking, it does recall the margin only depends on the support vectors.
‫From the margins point of view, it doesn't really matter.
‫Once you hit the support vector, what vectors lie beyond it because you're only defining that margin
‫by the first support vectors it comes into contact with, which means you're already saving yourself
‫a lot of computation by only having to worry about the support vectors.
‫That is the vectors that come into contact with the margin.
‫Now because of this I can rewrite from I equals one all the way to n number of points and instead only
‫consider I set s where s is a collection of the indices of the support points.
‫Essentially the same equation, but I'm only considering the support vector points because we can show
‫that alpha is only dependent on those supporting points, essentially not having to do as many calculations.
‫Then comes the kernel function.
‫So we're going to define a colonel function as a function K between two training points.
‫Training point I and training point I prime.
‫And we can show that this is going to be equal to the following sum x of of j multiply by x v prime
‫of j and this should obviously look familiar because it looks like an inner product and a kernel.
‫You can think of it as a function that just quantifies the similarity of two observations.
‫And we just talked about how the DOT product and inner product is essentially a similarity measurement.
‫That means if you begin to actually look at that linear support vector classifier equation, we define
‫that using an inner product.
‫So now I can use my relationship of an inner product being equal to the sum of these multiplications
‫of each subcomponent in order to swap in my kernel function into this newly rewritten support vector
‫classifier, essentially giving us a support vector machine where I can easily swap in any kernel function
‫I want, where again, the kernel function is essentially a similarity measurement.
‫And there's actually many kernel functions to choose from.
‫Here we're showing the simplest kernel function, which is just a linear kernel, but I can also have
‫a polynomial kernel notice.
‫I'm now just calculating this kernel function where I have a relationship between the kernel function
‫and the degree of what I want to calculate.
‫Saving myself a lot of computation because I'm no longer actually computing calculations in the full
‫feature space.
‫I'm computing the kernel, which is an inner product.
‫Another popular colonel is the radio bassist Colonel or otherwise known as RBF radio bassist function.
‫This is a much more complicated colonel and in fact, if you try to actually compute this without using
‫the inner products, it actually creates in theory an infinite number of computational comparisons.
‫So the only way to mathematically do this is with a kernel function that is going to use the inner product.
‫So the use of kernels as a replacement is known as the kernel trick.
‫And that is what actually happens when we use support vector machines.
‫We're able to rewrite that relationship from the support vector classifier in terms of an inner product.
‫And then we have a variety of kernels to choose from that are essentially defined as similarity functions,
‫which I can swap in wherever I see that inner product happening.
‫And then kernels allow us to avoid computations in the enlarged feature space by only needing to perform
‫computations for each distinct pair of training points.
‫We're really only need to consider those support vectors themselves.
‫The full details behind this can be found in section 9.3.2 and Eisler.
‫Now, intuitively, what we've already seen is that Inner Products act as a measurement of similarity
‫between vectors and the best way I can intuitively explain support vector machines, in case you were
‫a little unclear by the kernel trick, is that the use of kernels can be thought of as a measure of
‫similarity between the original feature space and the enlarged feature space.
‫So instead of having to actually perform the raw calculations in the enlarged feature space, I can
‫say that Kernels will give me a measure of similarity between the original feature space and the large
‫feature space, and use the kernels to perform a calculations instead, saving me a lot of computational
‫work in that enlarged feature space.
‫Okay.
‫Now that we understand the theory and intuition behind support vector machines, let's move on to actually
‫using them with code.
‫I'll see you in the next lecture.