1
00:00:00,540 --> 00:00:03,370
So the next question is,
how do we really go and

2
00:00:03,370 --> 00:00:06,490
find the vector W that
maximizes the margin?

3
00:00:06,490 --> 00:00:08,850
So the question is,
how do we precisely compute the margin?

4
00:00:09,920 --> 00:00:13,350
So now what we will learn
is where the name of

5
00:00:13,350 --> 00:00:15,940
the support vector machines
really comes from.

6
00:00:15,940 --> 00:00:17,390
And our idea, right, so

7
00:00:17,390 --> 00:00:21,370
far was to find the separating
like that maximizes the margin.

8
00:00:21,370 --> 00:00:24,890
And if we think about it,
we can draw the following picture, right?

9
00:00:24,890 --> 00:00:29,370
We have our, let's say negative training
examples, our minuses on the top, and

10
00:00:29,370 --> 00:00:32,900
we have our pluses on the bottom,
and what we want to do is we want to

11
00:00:32,900 --> 00:00:37,900
find the line that maximizes the distance
of the closest point to that line.

12
00:00:37,900 --> 00:00:41,370
And the way this line is simply defined,

13
00:00:41,370 --> 00:00:45,570
it's defined by a few points
that are closest to it, right?

14
00:00:45,570 --> 00:00:49,130
What this means is that we could ignore
all other data points, if we would have

15
00:00:49,130 --> 00:00:53,500
these three separate data point because
they already uniquely define the line.

16
00:00:53,500 --> 00:00:55,800
And these three circled
data points they are,

17
00:00:55,800 --> 00:00:58,270
they are called support vectors, right?

18
00:00:58,270 --> 00:01:02,250
The line that separating hyperplane
is uniquely defined in this

19
00:01:02,250 --> 00:01:06,850
case by three supporting support vectors.

20
00:01:06,850 --> 00:01:11,020
So now, the question will be how do
we go find the support vectors and

21
00:01:11,020 --> 00:01:12,890
how do find the line?

22
00:01:12,890 --> 00:01:17,720
Generally if our data is, is kind of
non-degenerate, then if you he, have,

23
00:01:17,720 --> 00:01:22,780
are in d dimensional space, we need d plus
1 support vectors to define such line.

24
00:01:24,320 --> 00:01:28,602
While we have already talked that
gamma corresponds to the margin.

25
00:01:28,602 --> 00:01:32,967
Basically corresponds to the distance of
the point from the hyperplane, here is a,

26
00:01:32,967 --> 00:01:34,590
here is a problem.

27
00:01:34,590 --> 00:01:36,320
The problem is, imagine the following.

28
00:01:36,320 --> 00:01:38,210
Imagine that I have a data point x.

29
00:01:38,210 --> 00:01:42,220
I multiply it with w add this b
multiply with, with the class.

30
00:01:42,220 --> 00:01:45,930
And I call this gamma,
which is the margin.

31
00:01:45,930 --> 00:01:49,690
So now imagine that I take my vector w but
make it twice as long.

32
00:01:49,690 --> 00:01:57,240
So I just kind of take that twice, twice
the w plus plus x plus twice b times y.

33
00:01:57,240 --> 00:02:01,020
What this gives me now is,
twice as big margin.

34
00:02:01,020 --> 00:02:06,400
So it seems, based on this simple
calculation is that the longer we make w,

35
00:02:06,400 --> 00:02:10,120
kind of the bigger the w is,
the bigger our margin will be.

36
00:02:10,120 --> 00:02:13,169
And this basically means that there is
kind of, very hard to optimize this.

37
00:02:13,169 --> 00:02:16,994
Because we can just make w
as large as possible and

38
00:02:16,994 --> 00:02:20,400
the margins will also get
as large as possible.

39
00:02:20,400 --> 00:02:22,420
So we are not doing anything useful.

40
00:02:22,420 --> 00:02:26,702
So the solution to this problem is
that we need to work not with w.

41
00:02:26,702 --> 00:02:29,122
But with a normalized version of w,

42
00:02:29,122 --> 00:02:33,840
in the sense that we want to think of
w as a vector that has length of 1.

43
00:02:33,840 --> 00:02:38,400
So what this means now is that we will
change the definition of margin slightly.

44
00:02:38,400 --> 00:02:42,260
We are still taking wx plus b times y, but

45
00:02:42,260 --> 00:02:44,980
now we are working with
a normalized version of w,

46
00:02:44,980 --> 00:02:50,478
so we are also dividing by the length,
by the euclidean length of w, in a sense.

47
00:02:50,478 --> 00:02:53,950
And the euclidean length is simply
the sum over all the coordinates,

48
00:02:53,950 --> 00:02:56,790
taking the square of those coordinates,
and then the square root of the sum.

49
00:02:57,940 --> 00:03:00,280
So now, this is the first thing we do,

50
00:03:00,280 --> 00:03:04,360
is write the first changes that we will be
working with a normalized version of w.

51
00:03:04,360 --> 00:03:07,510
And this changes the notion
of the margin a bit.

52
00:03:07,510 --> 00:03:10,590
The other thing that
will also work is not,

53
00:03:10,590 --> 00:03:13,030
now that we will require
support vectors x.

54
00:03:13,030 --> 00:03:18,190
These are these three circled data
points to be defined by the line

55
00:03:18,190 --> 00:03:22,420
w times x plus b equals plus or
minus 1, right?

56
00:03:22,420 --> 00:03:27,480
So, going back to my picture, our
decision boundary is wx plus b equals 0.

57
00:03:27,480 --> 00:03:33,320
So now the, the left support
factors are wx plus b equals

58
00:03:33,320 --> 00:03:38,120
minus 1 and the right support factors
are wx plus b equals plus 1, right?

59
00:03:38,120 --> 00:03:43,160
So we are in some sense requiring
that this here is of unit 1.

60
00:03:43,160 --> 00:03:46,630
So now the question is how can
we put all this together and

61
00:03:46,630 --> 00:03:49,890
find the optimization problem that
will allow us to maximize the margin?

62
00:03:51,340 --> 00:03:54,060
So, the goal is still
to maximize the margin.

63
00:03:54,060 --> 00:03:58,200
Now the question is what is
the relationship between data point x1?

64
00:03:58,200 --> 00:04:01,260
Which kind of is here on
the margin on the other side.

65
00:04:01,260 --> 00:04:05,450
And data point x2 which is
our red data point here.

66
00:04:05,450 --> 00:04:06,930
What do we know is the following.

67
00:04:06,930 --> 00:04:13,390
We know that x, x1, the value of
the data point here is simply x2 plus

68
00:04:13,390 --> 00:04:20,810
twice the margin times the normalized
version of the vector w, right.

69
00:04:20,810 --> 00:04:25,027
So if I have my vector w,
then what's the distance between x and y.

70
00:04:25,027 --> 00:04:29,995
I simply have to take this vector w,
and multiply it by twice the margin.

71
00:04:29,995 --> 00:04:33,234
Because there's one unit
of margin gamma here, and

72
00:04:33,234 --> 00:04:36,290
another unit of margin
gamma at the bottom.

73
00:04:36,290 --> 00:04:39,660
So that's the first kind
of equation that we know.

74
00:04:39,660 --> 00:04:44,260
The second equation that we know is based
on our assumption in the previous slide.

75
00:04:44,260 --> 00:04:49,070
That the left side of the margin is
defined by wx plus b equals minus 1.

76
00:04:49,070 --> 00:04:52,670
While the right hand side of
the margin is over the bottom of,

77
00:04:52,670 --> 00:04:57,340
on the other side of the decision boundary
is defined by wx plus b equals plus 1.

78
00:04:57,340 --> 00:05:01,470
So, I can also go and
write out both of these constraints.

79
00:05:01,470 --> 00:05:05,160
So, what I can do now is I can
take this system of equations and

80
00:05:05,160 --> 00:05:06,760
try to solve it, all right?

81
00:05:06,760 --> 00:05:12,550
So, the, I take, I take the first the
first equation and I enter, instead of,

82
00:05:12,550 --> 00:05:18,860
and I substitute x1 from from the, from
the top equation to obtain the next one.

83
00:05:18,860 --> 00:05:27,660
Now if I go multiply this through, I get
that w times x2 plus b equals twice gamma.

84
00:05:27,660 --> 00:05:31,360
And then I have w times w equals plus 1.

85
00:05:31,360 --> 00:05:36,560
What what we notice now is that I
can use the the last equation and

86
00:05:36,560 --> 00:05:42,250
notice that wx2 plus b equals minus 1,
that's the first thing we notice.

87
00:05:42,250 --> 00:05:48,070
And this already now solves the whole,
the whole, equation for gamma, right?

88
00:05:48,070 --> 00:05:50,410
What we see is that we can solve now for
gamma.

89
00:05:50,410 --> 00:05:57,351
So, we see that gamma equals the length
of w times the w dot product with itself.

90
00:05:57,351 --> 00:06:02,627
What do we note now is that w
times the dot product with itself,

91
00:06:02,627 --> 00:06:06,126
that is simply the square
of the length of w.

92
00:06:06,126 --> 00:06:11,207
So the square root of the length divided
by the square of the length is just 1

93
00:06:11,207 --> 00:06:12,426
over the length.

94
00:06:12,426 --> 00:06:18,710
So what we arrived to is that gamma
our margin is 1 over the length of w.

95
00:06:19,720 --> 00:06:21,660
So to summarize what we know so

96
00:06:21,660 --> 00:06:26,780
far, we started with the first
optimization problem that simply says

97
00:06:26,780 --> 00:06:32,260
we want to find w such that the margin
is maximized and what is the margin?

98
00:06:32,260 --> 00:06:37,460
The margin is the distance of that,
all, all the data points that we have,

99
00:06:37,460 --> 00:06:41,500
have the classification of
the confidence greater than gamma.

100
00:06:41,500 --> 00:06:44,880
So that was our initial
optimization problem.

101
00:06:44,880 --> 00:06:49,010
What we noted then that this initial
optimization problem can trivially be

102
00:06:49,010 --> 00:06:53,770
solved by making w as large as possible or
arbitrarily large.

103
00:06:53,770 --> 00:06:56,990
So there is nothing kind of
useful in solving this problem.

104
00:06:56,990 --> 00:06:59,130
So, what, what we did then was, we said,

105
00:06:59,130 --> 00:07:03,750
okay, let's normalize our
margin by the length of w.

106
00:07:03,750 --> 00:07:07,986
So, we said is maximizing
the margin gamma is

107
00:07:07,986 --> 00:07:12,336
the same as maximizing
1 over the length of w.

108
00:07:12,336 --> 00:07:17,780
Which is the, kind of the same or
equivalent to minimizing the length of w.

109
00:07:17,780 --> 00:07:23,030
Which is the same as minimizing
one-half times the length of w squared.

110
00:07:23,030 --> 00:07:28,122
And just for some technical reasons, at
the end, our goal will be to minimize the,

111
00:07:28,122 --> 00:07:31,900
one-half the length of w squared.

112
00:07:33,270 --> 00:07:37,720
So now that we have transform kind of

113
00:07:37,720 --> 00:07:41,060
maximization of gamma to
the minimization of the length of w.

114
00:07:41,060 --> 00:07:44,520
We can now write down
the support vector machine's

115
00:07:44,520 --> 00:07:47,290
margin maximization optimization problem.

116
00:07:47,290 --> 00:07:49,940
So our goal right now is the following,
and

117
00:07:49,940 --> 00:07:54,720
equivalent to the optimization above
modulo the problems that we resolved.

118
00:07:54,720 --> 00:07:58,050
We want to minimize the length of w, so

119
00:07:58,050 --> 00:08:01,820
we want to find w,
such that it has the smallest length.

120
00:08:01,820 --> 00:08:07,070
While the our classification margin,
our confidence in

121
00:08:07,070 --> 00:08:11,210
classification of all the training
data points is greater than 1.

122
00:08:11,210 --> 00:08:15,638
And this optimization problem that
I wrote down here is called SVM or

123
00:08:15,638 --> 00:08:18,834
support vector machine
with hard constraints.