So the next question is,
how do we really go and
find the vector W that
maximizes the margin?
So the question is,
how do we precisely compute the margin?
So now what we will learn
is where the name of
the support vector machines
really comes from.
And our idea, right, so
far was to find the separating
like that maximizes the margin.
And if we think about it,
we can draw the following picture, right?
We have our, let's say negative training
examples, our minuses on the top, and
we have our pluses on the bottom,
and what we want to do is we want to
find the line that maximizes the distance
of the closest point to that line.
And the way this line is simply defined,
it's defined by a few points
that are closest to it, right?
What this means is that we could ignore
all other data points, if we would have
these three separate data point because
they already uniquely define the line.
And these three circled
data points they are,
they are called support vectors, right?
The line that separating hyperplane
is uniquely defined in this
case by three supporting support vectors.
So now, the question will be how do
we go find the support vectors and
how do find the line?
Generally if our data is, is kind of
non-degenerate, then if you he, have,
are in d dimensional space, we need d plus
1 support vectors to define such line.
While we have already talked that
gamma corresponds to the margin.
Basically corresponds to the distance of
the point from the hyperplane, here is a,
here is a problem.
The problem is, imagine the following.
Imagine that I have a data point x.
I multiply it with w add this b
multiply with, with the class.
And I call this gamma,
which is the margin.
So now imagine that I take my vector w but
make it twice as long.
So I just kind of take that twice, twice
the w plus plus x plus twice b times y.
What this gives me now is,
twice as big margin.
So it seems, based on this simple
calculation is that the longer we make w,
kind of the bigger the w is,
the bigger our margin will be.
And this basically means that there is
kind of, very hard to optimize this.
Because we can just make w
as large as possible and
the margins will also get
as large as possible.
So we are not doing anything useful.
So the solution to this problem is
that we need to work not with w.
But with a normalized version of w,
in the sense that we want to think of
w as a vector that has length of 1.
So what this means now is that we will
change the definition of margin slightly.
We are still taking wx plus b times y, but
now we are working with
a normalized version of w,
so we are also dividing by the length,
by the euclidean length of w, in a sense.
And the euclidean length is simply
the sum over all the coordinates,
taking the square of those coordinates,
and then the square root of the sum.
So now, this is the first thing we do,
is write the first changes that we will be
working with a normalized version of w.
And this changes the notion
of the margin a bit.
The other thing that
will also work is not,
now that we will require
support vectors x.
These are these three circled data
points to be defined by the line
w times x plus b equals plus or
minus 1, right?
So, going back to my picture, our
decision boundary is wx plus b equals 0.
So now the, the left support
factors are wx plus b equals
minus 1 and the right support factors
are wx plus b equals plus 1, right?
So we are in some sense requiring
that this here is of unit 1.
So now the question is how can
we put all this together and
find the optimization problem that
will allow us to maximize the margin?
So, the goal is still
to maximize the margin.
Now the question is what is
the relationship between data point x1?
Which kind of is here on
the margin on the other side.
And data point x2 which is
our red data point here.
What do we know is the following.
We know that x, x1, the value of
the data point here is simply x2 plus
twice the margin times the normalized
version of the vector w, right.
So if I have my vector w,
then what's the distance between x and y.
I simply have to take this vector w,
and multiply it by twice the margin.
Because there's one unit
of margin gamma here, and
another unit of margin
gamma at the bottom.
So that's the first kind
of equation that we know.
The second equation that we know is based
on our assumption in the previous slide.
That the left side of the margin is
defined by wx plus b equals minus 1.
While the right hand side of
the margin is over the bottom of,
on the other side of the decision boundary
is defined by wx plus b equals plus 1.
So, I can also go and
write out both of these constraints.
So, what I can do now is I can
take this system of equations and
try to solve it, all right?
So, the, I take, I take the first the
first equation and I enter, instead of,
and I substitute x1 from from the, from
the top equation to obtain the next one.
Now if I go multiply this through, I get
that w times x2 plus b equals twice gamma.
And then I have w times w equals plus 1.
What what we notice now is that I
can use the the last equation and
notice that wx2 plus b equals minus 1,
that's the first thing we notice.
And this already now solves the whole,
the whole, equation for gamma, right?
What we see is that we can solve now for
gamma.
So, we see that gamma equals the length
of w times the w dot product with itself.
What do we note now is that w
times the dot product with itself,
that is simply the square
of the length of w.
So the square root of the length divided
by the square of the length is just 1
over the length.
So what we arrived to is that gamma
our margin is 1 over the length of w.
So to summarize what we know so
far, we started with the first
optimization problem that simply says
we want to find w such that the margin
is maximized and what is the margin?
The margin is the distance of that,
all, all the data points that we have,
have the classification of
the confidence greater than gamma.
So that was our initial
optimization problem.
What we noted then that this initial
optimization problem can trivially be
solved by making w as large as possible or
arbitrarily large.
So there is nothing kind of
useful in solving this problem.
So, what, what we did then was, we said,
okay, let's normalize our
margin by the length of w.
So, we said is maximizing
the margin gamma is
the same as maximizing
1 over the length of w.
Which is the, kind of the same or
equivalent to minimizing the length of w.
Which is the same as minimizing
one-half times the length of w squared.
And just for some technical reasons, at
the end, our goal will be to minimize the,
one-half the length of w squared.
So now that we have transform kind of
maximization of gamma to
the minimization of the length of w.
We can now write down
the support vector machine's
margin maximization optimization problem.
So our goal right now is the following,
and
equivalent to the optimization above
modulo the problems that we resolved.
We want to minimize the length of w, so
we want to find w,
such that it has the smallest length.
While the our classification margin,
our confidence in
classification of all the training
data points is greater than 1.
And this optimization problem that
I wrote down here is called SVM or
support vector machine
with hard constraints.