>> Okay. So, we're still talking about support vector
machines, although I haven't told you what support vector
machines are yet, we're getting there, Michael. Bear with
me. And what we got from our last discussion is
that what we want to do somehow is maximize
a particular equation, that is, 2 over the length of
W. And as a reminder, W the parameters of
our hyperplane. So somehow, we want to maximize that equation,
subject to the constraints that we still classify everything correctly.
Okay, so we want to maximize 2 over the length of W while classifying everything
correctly. But, while classifying everything correctly
is not a very mathematically satisfying expression,
but it turns out we can turn that into a mathematically satisfying expression.
And let me show you how to do that. So
here's a simple equation. While classifying everything correctly turns out to
be the same as, and I'm just going to write, I'm
going to write it out for you, Michael, and see if
you can, you can guess why this works. So, what I've
written here is YI times W transpose XI plus B greater
than or equal to 1 for all I. That is, for
all of our training data examples. So why does this work?
>> Well, what we
really want is that the, that linear classifier, WTXI plus
B, is greater than or equal to 1 for the positive
examples, and less than or equal to negative one for
the negative examples. But you cleverly multiply it by the label
on the lefthand side, which does exactly that. If YI
is 1, it leaves it untouched. And if YI is negative
1, it flips everything around. So that we're really talking about
less than or equal to minus 1. That's, that's very clever.
>> It is very clever, and I'm going to pretend that I came up with that
idea myself. So, it turns out that trying
to solve this particular problem, maximizing 2 over
W, while satisfying that constraint, is a little
painful to do. But that we can solve
an equivalent problem, which turns out to be
much easier to do, and that is this problem.
That is, rather than trying to maximize 2 over W, we can instead try to minimize
1/2 times W squared. Now can you see
that those will always have the same answer?
>> Yes, so, well, not the same answer, but it will be minimum,
the point that maximizes one will minimize the other. Yeah, because the, we
took the reciprocal. As long as we're talking about positive things. And since
these are lengths, they'll be positive. Taking
the reciprocal exactly, you know, changes the
direction, of what the answer is. And the squaring is, is,
makes it monotone. It doesn't, it doesn't, it magnifies it but it
doesn't change the ordering of things. So yeah. That, that, that seems
fine. I don't why that's any easier, but it seems the same.
>> Well, do you want to know why it's easier? Cause I'll tell you.
>> Please.
>> This is easier because when you have an optimization
problem of this form, something like minimizing a W squared,
subject to a bunch of constraints,
that is called a quadratic programming problem.
And people know how to solve
quadratic programming problems in relatively straightforward ways.
>> Awesome.
>> Now, what else is nice about that is a couple of
things. One is, it turns out that these always have a solution, and
in fact have a unique solution. Now I am not going to
tell you how to solve quadratic programming problems because I don't know how
to do it other than to call it up in the MATLAB.
But there's a whole set of classes out there, where they teach
you how to do quadratic programming. We could take an aside, I
could learn all about quadratic programming, and then we could talk about it
for two hours. But it's really beside the point. The important thing
is, that we have defined a specific optimization problem, and that there
are known techniques that come from linear algebra that tell us how
to solve them. And we can just plug and play and go. Okay?
>> Okay, fair enough.
>> Okay, fair enough. So, in particular, it
turns out that we can transform, again, this
particular quadratic programming problem into a different quadratic
programming problem. Or actually, truthfully, into the normal form
for a quadratic programming problem, that has the
following form. So here's what this equation tells
you, Michael. We have basically started out by
trying to maximize the margin. And that's the same
thing as trying to maximize 2 over the length of
W, I think I convinced you of, subject to a particular
set of constraints, which are how we codify that we
want to classify every data point correctly in the training set.
We've argued that that's equivalent to minimizing 1/2 times the
length of W squared, subject to the same constraints. And then
notice, because we happen to know this, that you can
convert that into a quadratic programming problem, which we know how
to solve. And it turns out that quadratic
programming problem has a very particular form. Rather than
try to minimize 1/2 of W squared, we can
try to maximize another function that has a different
set of parameters, which I'll call alpha. And that
equation has the following form. It's the sum over
all of the data points I, indexed by I,
of this new set of parameters alpha, minus 1/2
times, for every pair of examples, the product of their alphas, their labels,
and their values, subject to a different set of constraints. Namely that all
of the alphas are non-negative, and that the sum of the product of
the alphas, and the labels that go along with them, are equal to zero.
>> Holy cow.
>> Now, it's so obvious how you get from one
step to the other I'm not going to bother to explain
it to you. But instead tell you to go read a
quadratic programming book. What I really need you to believe, though,
mainly because I'm asserting it, is that these are equivalent. So
if you buy up to the point that we are trying to
maximize the margin, and that is the same thing as maximizing
2 over the length of W, and you buy that it's the
same as trying to minimize 1/2 times W squared, then you
just have to take a leap of faith here that, if we
instead maximize this other equation, it turns out that we
are solving the same problem. And that we know how
to do it using quadratic programming. Or other people know
how to do it and they've written code for us. Okay?
>> All right.
>> All right, so trust me on this. This is what it
is that we want to solve. Now, it turns out that we
can run little programs to solve this, and you end up with
answers. But what's really interesting is what this equation actually tells us
about what we're trying to do. So let me
just show you. This'll be just, talk a little bit
about the properties of this equation, and the property
of the solutions to this equation for a second. Okay?
>> hm.
>> Okay. So let me move a few things around so that we can look at it