Support Vector Machines for Non Linearly Separable Data Video Lecture | What is Data Analytics? - Data & Analytics

now we look at the case where the data
is not so well-behaved as we would want
it to be right
specifically the data is not separable
right it is not linearly separable so we
look at the not separable case so I'm
going to introduce some additional data
points or whatever have been looking at
so far
huh so this is a non-separable case
right linearly non-separable case
because some of my data points are
really mixed up here right I would still
like to have a large margin but not only
am i allowing data that is not separable
but I'm also allowing data points to
fall within the margin so it's
essentially two sides of the same coin
right so if I'm allowing data to fall
within the margin so in some sense I am
having the flexibility to make some kind
of errors as well
so I essentially look at how far away am
i from the margin right in the wrong
direction
right so I'm going to denote these
distances by which I'm away from the
margin by the symbol Zeta so we still
have our same constraints here but now
going back to our optimization problem
what I'm really looking to do here is
I'm going to modify my constraints such
that so Y I times X I transpose beta
plus beta naught it is really greater
than or equal to
1 minus Zeta where Zeta I is some kind
of a slack variable okay that allows me
to satisfy this constraint with some
error in it so essentially if you look
at this first data point that I drew
here if you look at the first data point
I drew here right so it has a slack of
Zeta 1 right then the second data point
has a slack of Zeta 2 right and this one
has a really fairly large slack but I
still it is possible under the
circumstances so this allows me to have
a larger margin right so if you think
about it if I did not let's say even if
this data point was not there if I did
not allow these kinds of data points to
appear in the margins right if I didn't
allow these things to appear in the
margin my classifier would actually have
been here right my classifier would have
been here trying to separate this X and
from this oh and and the margin would
have been very small and in all
likelihood I'm fitting a noise data
point here which is not an optimal thing
to do right so now by allowing some
amount of data points to fall within the
margin right I'm able to expand the size
of the margin that I can have and I can
also incorporate linearly the the the
small number of errors that I have to
make because the data is not linearly
separable right but then I don't want
this to become arbitrarily large right I
just can't say that hey doesn't matter
you can have a slack variable for every
data point that you have and the slack
variable can be as large as you want it
which I need to have a control on this
as well and therefore I
I try to minimize that
so are these conditions sufficient for
us to define a new problem now there's
still one more condition that we need so
we are really measuring zetas in one
direction and not in the other direction
right so we have to be careful so I also
need to add another set of constraints
let's say that that the Zetas have to be
positives so that is the complete
constrained optimization problem for us
in the case where the data is not
linearly separable so you have to
minimize beta squared now beta squared
plus the sum of the Zetas that you are
using subject to the condition that the
y:i XA transpose beta plus beta naught
is greater than 1 minus Chi Chi and seat
I is greater than equal to 0 so what
happens to a primal objective function
now so you notice that we need a
component that corresponds to the actual
objective function and we need a
component that corresponds to the
constraints that we are using right so
the first part of it remains as it is
right but then we have to add the the
newer components that we are bringing in
right so this is the second part of the
objective function and this is the first
constraint right and this is the second
constraint and since this has this has
to apply to each and every data point so
you have the summation over all the data
points there likewise here
so how do we go about deriving the dual
in this case so just like we did earlier
so we start differentiating the primal
with respect to the various parameters
so you end up with the same condition
that you had earlier okay and here you
end up with the same condition then when
you differentiate with respect to the
the Zetas you end up with
so one condition for each eye right so
alpha equal to C minus mu I right so I
can put everything back in to the primal
do some algebra and derive my dual which
turns out to look exactly like this
except that
except that my alpha has to lie between
zero and C that you can actually see
from that condition that we have that
right and alpha iyi stopped to be equal
to zero that we already have as a
condition so the remainder of the KKT
conditions that we have I'm just going
to go through this very quickly because
I don't want to do the complete
derivation here so the remainder of the
KKT conditions would be
this is what we had last time except for
the Zeta I part right somebody also have
which is essentially our initial
constraint written in a slightly
different form right so the third
constraint here it's just the the
original constraint with the I 1 minus
Zeta is taken to the other side so what
this is that you notice from here so
let's go back and let's do the same
argument if alpha is greater than zero
then Y I XA transpose beta beta naught
this actually less than 1 right only
then this will be 0 because right so
that would mean that for the particular
choice of Zeta is so this goes to 0 that
would mean that this is on the wrong
side of the margin right or on or on the
margin or equal to 1
either if Zeta is or zero then it will
be on the margin if theta is or nonzero
it will be within the margin so all the
data points that are one side of the
margin are all support vectors
because again like last time so beta is
depends only on those vectors for which
alpha is greater than zero right so if
the data happens to be on the right side
of the margin right then your alpha is
have to be zero as we saw earlier and so
those data points have no role in
computing so this essentially kind of
takes us over the entire optimal
separating hyperplane part right so when
it was linearly separable so we had a
very easy solution but when the data is
not linearly separable and so we have to
allow for the possibility of data points
to lie on the wrong side of the margin
so when we do that we can essentially
take advantage of the fact and try to
push our margin away but allowing data
points which are correctly classified
but are within the margin a small
fraction of such data points are
permitted and therefore that loves us to
expand the margin a little bit and so we
can't come up with a solution so you
don't have to at this point you don't
have to worry about the details of
solving this optimization problem but
there are many many powerful
optimization techniques that have been
developed that love you to solve this
these kinds of problems and in fact
SVM's
have led to the revival of a popular
class of optimization algorithms called
interior point methods because they were
very efficient in solving these kinds of
optimization problems and they are
pretty robust classifiers and very very
widely used for a wide variety of
applications but some of you are
probably thinking right now but whenever
I talk about support vector machines
people always tell me something about
kernels right
and I thought support vector machines
are all about kernels and I am NOT
talking talked about kernels at all at
any point here yes so the kernel
is very crucial in suppo return machines
and I'll be looking at that in more
detail in the next module but what they
should remember is the basic
optimization problem that you are trying
to solve with support vector machines is
the one of optimal separating
hyperplanes I think so in fact the the
kernel idea is called a kernel trick
because it loves you to solve a really
wide variety of problems which which are
not easily amenable to linear
classification by using a very powerful
idea but then the underlying
optimization problem that you're solving
is still this the same optimization
problem that I written out on the board
so far in the last two modules