1
00:00:00,520 --> 00:00:05,470
So far we implicitly assumed that
our data is linearly separable.

2
00:00:05,470 --> 00:00:08,330
What this means is, we kind of
assumed that it's always possible to

3
00:00:08,330 --> 00:00:14,280
find the line that will perfectly separate
positive and negative training examples.

4
00:00:14,280 --> 00:00:16,720
However most of real data sets,

5
00:00:17,980 --> 00:00:22,040
they are noisy which means that there
is no such sep, separating hyperplane.

6
00:00:22,040 --> 00:00:23,955
So the question is what happens to our,

7
00:00:23,955 --> 00:00:28,440
for, formulation when we have data
that cannot be nicely separated.

8
00:00:28,440 --> 00:00:30,769
For example, imagine my data set here.

9
00:00:30,769 --> 00:00:35,035
Where I have these data points that
are kind of are on the wrong side of the,

10
00:00:35,035 --> 00:00:37,217
of the bound, the decision boundary.

11
00:00:37,217 --> 00:00:41,130
And there is actually no linear decision
boundary here that would allow me.

12
00:00:41,130 --> 00:00:44,640
To, to draw a line and
put all the pluses on one side, and

13
00:00:44,640 --> 00:00:46,520
all the minuses on the other side.

14
00:00:46,520 --> 00:00:49,126
So, when we are dealing with such,
such data.

15
00:00:49,126 --> 00:00:53,210
Where finding nice linear
separator is impossible and

16
00:00:53,210 --> 00:00:56,400
this is basically this happens
in every data part, data set.

17
00:00:56,400 --> 00:01:00,210
What we have to do is, we have to
change our formulation a bit and

18
00:01:00,210 --> 00:01:01,770
introduce a penalty.

19
00:01:01,770 --> 00:01:03,470
So, the idea will be the following.

20
00:01:03,470 --> 00:01:07,040
What we want to do now,
is we still want to maximize the margin.

21
00:01:07,040 --> 00:01:09,510
This is the first part of
our objective function.

22
00:01:09,510 --> 00:01:12,260
But what we want to do is we
want to have some parameter, and

23
00:01:12,260 --> 00:01:16,740
we will call this parameter C,
and plus the number of mistakes.

24
00:01:16,740 --> 00:01:17,410
Right?
So, what we

25
00:01:17,410 --> 00:01:22,570
are doing right now is basically saying,
we want to find w that has good margin,

26
00:01:22,570 --> 00:01:25,930
while also makes a small
number of mistakes.

27
00:01:25,930 --> 00:01:27,090
Right?

28
00:01:27,090 --> 00:01:31,234
So, the idea, in a sense now give,
minimizing w gives us the,

29
00:01:31,234 --> 00:01:33,831
gives us the line that has high margin.

30
00:01:33,831 --> 00:01:38,215
While the second part of
the optimization problem, the,

31
00:01:38,215 --> 00:01:43,650
the one on the right basically wants
to control for the number of mistakes.

32
00:01:43,650 --> 00:01:44,210
Right?

33
00:01:44,210 --> 00:01:49,260
And the idea here is that we will
have the value of C and set it.

34
00:01:49,260 --> 00:01:53,550
And the goal is to find the separating
hyperplane to find the line,

35
00:01:53,550 --> 00:01:57,880
that both has good margin and
makes a small number of mistakes.

36
00:01:57,880 --> 00:02:02,080
And now, of course, the question is,
how do we penalize mistakes?

37
00:02:02,080 --> 00:02:05,320
Because not all mistakes
are of same severity.

38
00:02:05,320 --> 00:02:08,700
And the idea is that not
mistakes are equally bad.

39
00:02:08,700 --> 00:02:13,690
Which means we will be using margin,
in order to penalize them.

40
00:02:13,690 --> 00:02:17,190
So how do we use margin
to penalize mistakes?

41
00:02:17,190 --> 00:02:20,860
We introduce this notion
of slack variables.

42
00:02:20,860 --> 00:02:24,186
And the way we think of slack variables
are basically these additional

43
00:02:24,186 --> 00:02:26,506
constraints, or
these additional penalties.

44
00:02:26,506 --> 00:02:29,890
That we get for
misclassifying a data point.

45
00:02:29,890 --> 00:02:33,410
So the idea is that we
have our separating plane.

46
00:02:33,410 --> 00:02:38,370
And then the, the value of slack variable,
or the value of penalty will simply be

47
00:02:38,370 --> 00:02:44,330
wha, what is the distance from the other
side of the sep, or the margin.

48
00:02:44,330 --> 00:02:46,130
To the, to the data point itself.

49
00:02:46,130 --> 00:02:47,420
Right?
So in this case,

50
00:02:47,420 --> 00:02:49,930
psi the value of psi is this much.

51
00:02:49,930 --> 00:02:54,180
For example for the mis-specification
of this data point plus,

52
00:02:54,180 --> 00:02:58,678
the value of psi is all the way
from the other side right?

53
00:02:58,678 --> 00:03:02,130
This is kind of the,
how much we are mis-classifying.

54
00:03:02,130 --> 00:03:06,750
Because it would require us kind of to
move that data point plus to the other

55
00:03:06,750 --> 00:03:07,610
side of the margin.

56
00:03:07,610 --> 00:03:12,310
If you, if we would want to make
it be classified correctly.

57
00:03:12,310 --> 00:03:17,820
So what this means is, now we are arriving
to our new optimization problem, right?

58
00:03:17,820 --> 00:03:19,670
We still say, okay, what is our goal?

59
00:03:19,670 --> 00:03:21,778
Our goal is to find w and b,

60
00:03:21,778 --> 00:03:26,010
and we want to also find the values
of the slack variables psi.

61
00:03:26,010 --> 00:03:32,400
Such that the norm of w is small,
which means the margin is large.

62
00:03:32,400 --> 00:03:38,330
Plus the, the sum of the span of
this psi is as small as possible.

63
00:03:38,330 --> 00:03:40,600
While what, what we also require,

64
00:03:40,600 --> 00:03:45,540
we also require the confidence in
our classification is at least 1.

65
00:03:45,540 --> 00:03:50,630
And if it's if it's not 1,
then we have to subtract the value of psi.

66
00:03:50,630 --> 00:03:54,660
Right, so this is basically whenever
our correct, example is correct,

67
00:03:54,660 --> 00:03:59,580
correctly classified,
the our confidence will be greater than 1.

68
00:03:59,580 --> 00:04:03,940
And we can, in that case,
will be able to set the value of psi to 0.

69
00:04:03,940 --> 00:04:06,250
Otherwise, if that is not the case,

70
00:04:06,250 --> 00:04:10,450
we will have to set the value
of psi to some nonzero value.

71
00:04:10,450 --> 00:04:15,970
Which means we will occur some
penalty in the optimization problem.

72
00:04:15,970 --> 00:04:22,300
And the idea here is basically that
if we take our data point Xi and

73
00:04:22,300 --> 00:04:24,860
it is on the wrong side of
the classification margin.

74
00:04:24,860 --> 00:04:28,590
Then we incur some penalty for
misclassifying it.

75
00:04:28,590 --> 00:04:31,470
And this data,
this optimization that we set it so

76
00:04:31,470 --> 00:04:35,510
far, this is called the SVM
with soft constraints.

77
00:04:35,510 --> 00:04:36,810
Why soft constraints?

78
00:04:36,810 --> 00:04:41,350
Because now we can also allow for
misclassifications.

79
00:04:41,350 --> 00:04:43,450
So, one more thing that would be good to

80
00:04:44,830 --> 00:04:49,150
get some intuition about is what
is the role of this parameter C?

81
00:04:49,150 --> 00:04:51,950
We call this parameter the slack penalty.

82
00:04:51,950 --> 00:04:53,800
Why do we call it the slack penalty?

83
00:04:53,800 --> 00:04:58,420
Is because it controls between
the size of the cost of the margin.

84
00:04:58,420 --> 00:05:01,480
How much are we wishing to
make the margin big, big?

85
00:05:01,480 --> 00:05:05,900
And how much, are we penalizing
our misclassification mistakes?

86
00:05:05,900 --> 00:05:08,310
So the way we can think
of C is the following.

87
00:05:08,310 --> 00:05:11,410
If we set C to be infinite, right,

88
00:05:11,410 --> 00:05:16,360
what this basically means is that we only
want to find w that separates the data.

89
00:05:16,360 --> 00:05:19,970
So for example, in our case,
if I have a data set here and I would

90
00:05:19,970 --> 00:05:24,890
set C to be very big, then this is the
decision boundary we would find, right.

91
00:05:24,890 --> 00:05:28,140
It's a decision boundary,
that nicely separates the data.

92
00:05:28,140 --> 00:05:32,390
For example,
if you would set C equal 0, right?

93
00:05:32,390 --> 00:05:37,070
Which would basically mean that we don't
really care about misclassifications, but

94
00:05:37,070 --> 00:05:42,740
we just want to make our, our W to be as,
as short as small as possible.

95
00:05:42,740 --> 00:05:46,740
Then, basically, what, what this would do,
it would ignore the data, and the whole

96
00:05:46,740 --> 00:05:49,760
decision morally would just be something
that goes through the coordinate origin.

97
00:05:49,760 --> 00:05:55,380
So, it could be this [INAUDIBLE]
line that I show here.

98
00:05:55,380 --> 00:05:57,880
But, however,
if we choose a good value of C,

99
00:05:57,880 --> 00:06:02,940
then we are nicely trading off between
our line nicely separating the data, so

100
00:06:02,940 --> 00:06:07,440
having large margin,
while also not making too many mistakes.

101
00:06:07,440 --> 00:06:08,290
And for a good or

102
00:06:08,290 --> 00:06:11,060
appropriate value of C, this is
the line we would like to find, right.

103
00:06:11,060 --> 00:06:15,010
We still have a relatively nice
separation between pluses and

104
00:06:15,010 --> 00:06:18,140
minuses, while making one small mistake.

105
00:06:19,300 --> 00:06:22,850
So, having discussed the value of
the slack penalty in the formulation of

106
00:06:22,850 --> 00:06:26,020
the support vector machine,
here is now what we call

107
00:06:26,020 --> 00:06:30,240
the support vector machine optimization
problem in it, in its natural form.

108
00:06:30,240 --> 00:06:32,450
So the way we can think
about it is the following.

109
00:06:32,450 --> 00:06:35,990
Our goal is to solve the following
optimization problem,

110
00:06:35,990 --> 00:06:39,620
where we want to find b and
w, such that the.

111
00:06:40,677 --> 00:06:45,810
1/2 square of the, of the,
of the square of the normal w,

112
00:06:45,810 --> 00:06:51,520
plus the slack penalty times
our misclassification costs.

113
00:06:51,520 --> 00:06:53,830
The whole thing is minimized.

114
00:06:53,830 --> 00:06:57,590
What is, what is this doing, the way we
are thinking about this, we are thinking

115
00:06:57,590 --> 00:07:02,160
of the first part of the optimization
problem as maximizing the margin.

116
00:07:02,160 --> 00:07:02,910
Right, we want.

117
00:07:02,910 --> 00:07:06,090
The length of w to be
as small as possible.

118
00:07:06,090 --> 00:07:09,680
And we think of C as a slack penalty.

119
00:07:09,680 --> 00:07:13,020
Which is something is something we have to
kind of set by hand and it tells us how

120
00:07:13,020 --> 00:07:18,220
much are we trading off between fitting
the data and making the margin large.

121
00:07:18,220 --> 00:07:22,200
And then the the last part is
we call it empirical loss.

122
00:07:22,200 --> 00:07:22,870
Right.
Because this is

123
00:07:22,870 --> 00:07:25,220
saying how well are we fitting the data.

124
00:07:25,220 --> 00:07:27,300
Right.
So the left part of the equation is

125
00:07:27,300 --> 00:07:29,000
trying to maximize the margin.

126
00:07:29,000 --> 00:07:32,230
Find a good separator and
the second part is to,

127
00:07:32,230 --> 00:07:35,720
trying to say let's try to fit
the data as well as possible and

128
00:07:35,720 --> 00:07:40,370
the cost of how well are we fitting
the data is called the loss.

129
00:07:40,370 --> 00:07:43,450
On how we can now think
about machine learning is

130
00:07:43,450 --> 00:07:46,720
that basically machine learning is
trying to trade off between finding a,

131
00:07:46,720 --> 00:07:52,460
a good separation between the two
classes while also miminzing the loss.

132
00:07:52,460 --> 00:07:56,600
And in particular the loss that we have
written here goes under the name of

133
00:07:56,600 --> 00:07:57,810
the hinge loss.

134
00:07:57,810 --> 00:08:02,820
So we can think of support vector machines
to be using or minimizing the hinge loss.

135
00:08:02,820 --> 00:08:05,840
The reason why we call it
the hinge loss is the following.

136
00:08:05,840 --> 00:08:07,920
What we ould really like to do is, is,

137
00:08:07,920 --> 00:08:12,000
the idea is that if we
have our classification.

138
00:08:12,000 --> 00:08:15,220
And on the y axis, we plot the penalty.

139
00:08:15,220 --> 00:08:20,410
The idea would be that if we misclassify,
we obtain a penalty of one,

140
00:08:20,410 --> 00:08:24,750
right, if misclassification means
that we predicted one class, and the,

141
00:08:24,750 --> 00:08:27,380
the true class was,
was, of the other sign.

142
00:08:27,380 --> 00:08:28,080
So the.

143
00:08:28,080 --> 00:08:31,100
Product of the two signs is negative.

144
00:08:31,100 --> 00:08:35,330
While if we made the correct
classification, we would like to obtain 0,

145
00:08:35,330 --> 00:08:37,130
meaning no penalty.

146
00:08:37,130 --> 00:08:43,850
So an ideal 0/1 loss would be,
you obtain penalty of 1 if misclassify,

147
00:08:43,850 --> 00:08:47,530
and obtain penalty of 0
if we classify correctly.

148
00:08:47,530 --> 00:08:50,380
What is the penalty that support
vector machine is using,

149
00:08:50,380 --> 00:08:52,000
is called the hinge loss.

150
00:08:52,000 --> 00:08:56,350
The reason we, we call it the hinge loss
is, because there is this hinge at one.

151
00:08:56,350 --> 00:09:00,320
Which basically means, if we
are classifying the point correctly, and

152
00:09:00,320 --> 00:09:03,920
the point is away from the margin, it's
basically away from the decision boundary

153
00:09:03,920 --> 00:09:10,500
for a least value of 1, then we obtain
the class the the cost for the loss of 0.

154
00:09:10,500 --> 00:09:11,750
However if the mid,

155
00:09:11,750 --> 00:09:16,570
if the point is inside the margin or
inside the classification boundary so

156
00:09:16,570 --> 00:09:20,260
can still be classified correctly but
is too close to the boundary.

157
00:09:20,260 --> 00:09:22,890
Or is actually on the wrong
side of the boundary then we

158
00:09:22,890 --> 00:09:27,180
are incurring the penalty and
its penalty is proportional to how far

159
00:09:27,180 --> 00:09:31,670
away is our point from the from
this decision boundary.

160
00:09:31,670 --> 00:09:37,271
So this is called a Hinge Loss, and
support vector machine is exactly

161
00:09:37,271 --> 00:09:42,499
optimising this hinge loss in the,
in the lost part of the term.