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 at the general mathematics of how we build up to support
vector machines and we'll also discuss how the mathematics is related to the secular and class calls.
We'll begin with a brief review of using margin based classifiers slowly expanding from maximum margin
classifier to 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 we discuss.
You could check out the original publication by Cortez and if APNIC called Support Vector Networks in
the Machine Learning Journal.
Now, let's first talk about hyper plaints defined mathematically here, I can imagine a two dimensional
space with two features X1 and X2.
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 X1 plus beta two times x2 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 a number of dimensions, just continuing this where there's
a single Beita coefficient for every single feature.
Now, this is the mathematical definition of a hyper plane for some number of features.
Let's talk about separating hyper 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
hybrid 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 hyper plane.
Similarly, the values below zero are going to fall on the other side of the hyper plane.
So now I have a set of equations that is able to define what side of the hyper 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 NP 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 panda's 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 N is the number of
points themselves.
One therapy is the number of actual features.
So in this case, we would have two features X1 and X2, given the diagram on the right and we would
have six points.
So one through six would be one through.
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 hydroplaned.
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 NP.
And we want to do is make sure that we fulfill 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 sum 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 why have I multiplied by these beta coefficients times?
The feature value gives you the perpendicular distance from the point to the hyper plain, 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 plain.
And here we have the full definition, mathematically speaking, of Emax margin classifier again, given
this transpose matrix of data points, we want to figure out the beta coefficients that are going to
maximize this em 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, some coefficient being equal to one in order to determine the
orthogonal distance from the points to the hyper plain.
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
the squared being equal to one in order to be able to determine the orthogonal distance from the vectors
to the plane itself.
But because there'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 or 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's being Lessner 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 additions 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 on a max margin classifier,
essentially not allowing for any errors.
Now, a quick note on this value of SI, you should notice that the way you've defined it here mathematically,
the larger the sea value, the more errors we allow ourselves in.
Saikat learn due to the fact that they want to remain consistent across multiple models.
They say C is 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 learn it's inversely proportional
to the equation shown here.
Obviously, they'll be more clear as we begin to experiment with Saikat learn.
But it's just something to keep in mind that the C in cyclers 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.
OK, 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 were 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 the line.
We have a bunch of points in the middle and then another class surrounding it.
So what we do, as we previously discussed, is transform this to some sort of higher dimension or feature
space.
So right now I could have features x1 x2 all the way to XP number of features, and I could use something
like a polynomial transformation using X1 and x1 squared x2 next to squared all the way to expand XP
squared in order to try to figure out if there's a hyper hydroplane in this larger feature space that
will successfully be able to separate out these two classes.
And I can still allow for mis classifications 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 square, essentially one of the simplest support vector machines we can possibly do.
So we're no longer just considering x1 x2 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 mis classifications, which you'll notice are actually in the subject to y if
I where it's greater than or equal to the margin times one minus Epsilon or Epsilon is again defined
by this user parameter C essentially allowing for some mis classifications 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 now considering some larger feature space of things like X squared or X2 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?
While 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 product to just be between two vectors and recall that vectors can
be more than just two dimensions that's 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 A1 and B one along the X axis,
and then A two and B two along the Y axis.
Now you can imagine that as we move on to three dimensional vectors, four dimensional vectors, cetera,
there will 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 it.
That product, the DOT 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 note notice that if we start thinking of a product in this format,
it's essentially a similarity between the vectors.
So this is going to result in the same calculation as saying A1 Times B1 plus A two times B2.
It's essentially another definition for the DOT 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 one hundred percent 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 the inner product is equal to zero.
And then if they are pointing in exact opposite directions, that is cosine of one hundred and eighty
degrees, then we would have 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 Colonel, Eric.
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 Beita, not plus the sum of some alpha term times, the inner
product of each pair of turning points.
We essentially calculate the inner products of all pairs of training observations.
And you can check out the reading in Chapter nine of eSolar for a more in-depth look.
Or you can check out the publication from Cortez and Chapnick, 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 inner products.
Now, since I'm able to calculate the inner 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 in 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 the finding that margin by the first support vectors it comes the
contact with, which means you're already saving yourself a lot of computation, but 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 any number of points and instead
only consider I said s where s is a collection of the indices of these 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 colonel function, so we're going to find a colonel function as a function K between
two training points, training point eye and training point I prime, and we can show that this is going
to be equal to the following.
Some X of IFJ multiplied by X by prime of J.
And this should obviously look familiar because it looks like an inner product and a colonel.
You can think of it as a function that just quantifies the similarity of two observations.
And we just talked about how they dot product and inner product is essentially a similarity measurements.
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 Col's as a replacement is known as the COL trick, and that is what actually happens when
we use support.
Vector machines were able to rewrite that relationship from the support vector classifier in terms of
an inner product.
And then we have a variety of Khalsa choose from that are essentially defined as similarity functions,
which I can swap in wherever I see the inner product happening.
And then Col's allow us to avoid computations in the enlarged feature space.
They only need to perform computations for each distinct pair of turning points where I really only
need to consider those support vectors themselves.
The full details behind this can be found in Section nine point three point two, eSolar.
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 and the enlarged feature space, I can
say the 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.
OK, 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.