Support Vector Machines(contd) Video Lecture | What is Data Analytics? - Data & Analytics

hello and welcome back to our discussion
on support vector machines so we were
looking at the optimization problem
corresponding to the optimal separating
hyperplane right so to solve this
problem right so with one of the
techniques for solving these kinds of
constrained optimization problems is to
set up a Lagrangian which essentially
looks at the original objective function
which is half beta squared and a second
component corresponding to
corresponding to the constraints that we
have so if you look at this quantity in
the square brackets here so you can see
that this is the term on the left-hand
side of the inequality and that's the
term on the right-hand side of the
inequality right and we really want to
make sure that this difference right
it's not negative right if this
difference is negative then that would
mean that Y I times X I transpose beta
plus beta naught is actually less than 1
we don't want this to be negative so
what we essentially say this this we
then add it here - same right so the
essentially means that when I minimize
this whole expression right so this term
will become as large as possible as
largely positive as possible so that
essentially means that I'm going to try
and make this as larger than 1 as
possible right so this term here alpha I
lets me control how much weight I want
to give to satisfying the constraints
versus how much I really want to
minimize the objective function right so
we really need to satisfy the
constraints as much as possible and
since there are solutions that will be
that will satisfy the constraint and
give you a good Optima all right so we
should essentially be trying to drive
this thing to as large the value as
possible right so this is called the
primal of the problem and your goal is
to minimize the primal so so I'm going
to do something fairly technical right
now so if you don't understand all of it
in the first go that's fine you might
have to do a little bit more reading on
the side but this is essentially give
you an idea of how people go about
solving these kinds of problems right so
we are going to try and create what is
called the
duel of this the primal objective
function so the duel is a way to create
something and create an optimization
problem that is simpler to solve in some
sense than the primal and the dual at
all points provides you some kind of a
lower bound on the kind of solutions
that you can achieve with the primal and
at the optoma of the duel you ideally
like the optimum of the primal also to
be achieved so we're going to create a
problem called the dual we're going to
solve the dual right and when you reach
the optimum of the dual you would like
the Optima of the primal to be also
achieve the same solution that gives you
the optimal in the dual problem should
give you the optimum and the primal
problem right and there are technical
conditions under which this is set now
this is satisfied right and we are not
going to go into those technical
conditions and this going to give you a
flavor of kind of results that we'll be
looking at so let's start by
by setting the derivative of LP to zero
derivative with respect to beta and beta
naught so taking the derivative with
respect to beta and setting it to zero
and solving for beta gives me so you can
you can figure that out by little bit of
algebra here likewise setting that
derivative with respect to beta out to
zero and solving it gives me
okay
so I can substitute these back into the
primal problem right and do a lot of
algebra load a lot of algebra really and
then I can simplify this and I will get
what is known as the dual let me write
the dual here so this is just really
obtained by substituting your beta into
the expressions here right and then
using the fact that alpha iyi would be 0
at the optimal so that's the thing but
then it's subject to the constraint
so note that I said so your duel is
always going to give you a lower bound
on the solution of the primal problem so
really if you are minimizing the
solution in your primal you should be
maximizing the solution in the dual so
that the two of them can coincide at
some point so essentially you would be
maximizing this subject to the
constraint that all your alpha is for
greater than or equal to zero right so
if we think about it this is a much
easier constraint to wrap our heads
around because it just say I said hey
you'd only be doing it in the positive
coordinates right and while this had a
more complex set of constraints so we're
kind of reduce T constrained into
something easier and therefore the
primer the dual problem is sometimes
easier to solve so for the dual and
their primal to be at the Optima at the
same time right so we really want them
to satisfy a set of conditions which are
essentially two with the derivative of T
the primal problem so we require that
this should hold we require that this
should hold I'm going to write them as
one two and three in addition we require
that this condition should also be
require that this condition should also
be satisfied these are called D
they're called the KKT or the
karush-kuhn-tucker conditions right and
so for the optimization problem to have
the same solution we require that the
KKT conditions should be satisfied so
once you have an optimal solution for
the dual and the primal problem because
these KKT conditions have to be
satisfied you can make certain
observations right especially when
working from condition 3 here so if
alpha eyes is greater than 0 if alpha is
greater than zero so what does it mean
so this has to be equal to 0 then the
term in the square bracket has to be
equal to 0
hey that means why I into X I transpose
beta plus beta naught should be 1 so
what does that mean it means that it's
exactly on the edge of the margin right
when it is equal to 1 because if greater
than or equal to 1 is what we need it to
satisfy so n is equal to 1 that means
it's exactly on the margin right
likewise if
so if the quantity in the square bracket
is greater than one then alpha I has to
be zero so that essentially means is if
your data point is something that is far
away from the hyperplane that says more
than the margin away from the hyperplane
then the corresponding alpha is will
become zero so what does this mean for
us so if we think about it so the
solution that we get right which is
essentially beta that's a solution that
we want to get right it's formed by
taking the product of alpha is y ice and
Excise right so if I'm saying and alpha
I is going to be zero it essentially
means that the corresponding X I has no
role to play in determining what my beta
should be right if I say that it implies
if X is zero that implies that X I has
no role in no role in computing beta
so which are the data points which will
actually affect the solution beta they
are exactly those points for which Y I
times XA transpose beta plus beta or not
is one that means they are exactly the
points which lie on the margin so only
these points will influence how the
solution beta looks like right and all
the other data points that you have
which are farther away from the
separating hyperplane than these points
do not matter in the solution so these
points are called
support vectors
so do note that you really don't have to
solve this optimization problems
yourself there are enough tools that
actually can do it for you the whole
goal of this lecture is to get you to
appreciate what is it that you are doing
when you are using a support vector
machine for solving a problem right so
at the end of the day all you're going
to do is fire up a tool that's going to
tell you what is the separating
hyperplane given a bunch of data but
it's good to have an appreciation of how
the classifier is actually built right
so once you figure out a beta right then
I can substitute that I can substitute
that into the KKT the third condition
here and solve for beta naught so
typically what you do is that you use
every X I that that's a support vector
right and you substitute that here and
then try to solve for beta naught and
typically end up taking the average
value of that so a couple of things
which I want to point out about support
vector machines so one thing is you
should be very clear that the training
data okay none of the training data will
fall within the margin but that is not
to say that the test data might fall it
might not fall within the margin right
the testator I might fall within the
margin it might actually fall on the
other side of the hyperplane so for all
we know that's the test day that could
be errors on the test data we just just
on the training data okay it tries to
fit something that is as far away as
possible from the data points so the
idea here is that so if I give as much
gap between the classes as possible
right then the classifier would be more
robust to noise on either side so this
is assuming that that noise could meet
in this class or in this class if you
know for sure that one class is noisier
than the other or if you want class is
more valuable than the other so you
might want to actually modify your
objective so that the line doesn't go
in the middle but its moves to one side
or the other so having said that under
the assumptions of the support vector
machines if the assumptions hold good
then is a very very robust classifier so
the reason is it pays attention when
lead to the points that are closest to
the class boundary you know so I can
have as many data points here I say want
I can have as many data points here as I
want of the corresponding class it
really does not affect my classification
because truly the ones that are close to
the boundary are the ones that need
attention so that essentially makes
support vector machines more more robust
right right on the other hand if you're
going to have some kind of a stochastic
process that is generating the data
right so if there are a few data points
that are by chance for noise data points
that actually are close to the
hyperplane right that'll affect the
support vector machines tremendously and
therefore it will try to reduce the
margin by a large extent well a
classifier that looks at the entire data
and tries to find a distribution for the
entire data might be a little bit more
robust to this kind of noise so this is
the this is how you solve the basic
optimization problem for support vector
machines