# Lecture 12: Shallow Machine Learning - Support Vector Machine (SVM)

[Recording](https://www.youtube.com/watch?v=m-b1q9h_Nnc)

Automatic transcript; technical terms and equations may contain recognition errors.

00:00:00 We'll start with a shallow machine learning model, which is a support vector machine.

00:00:05 So I was asking how much should I talk about it?

00:00:10 So did you have a chance to look at the slides?

00:00:15 So I did talk to other instructors.

00:00:18 I'm sure at least the three of you have just taken support vector machine.

00:00:23 Is that right? 765?

00:00:26 Okay?

00:00:29 So what I will do is that I will still go through this, but some places I will ask you and scheme.

00:00:42 Some places, if it's not that clear to you and I thought maybe it's a complimentary thing, then I put more details into it.

00:00:50 Okay?

00:00:51 Shall we do that?

00:00:53 Okay.

00:00:54 So I want to talk about the following things for support vector machines.

00:00:59 Okay?

00:01:00 I want to talk about what is the intuition behind the support vector machines.

00:01:05 Then how can this be formulated into an optimization problem?

00:01:09 Okay?

00:01:10 So that's why we are using this one as the first example.

00:01:13 Then how can we solve such optimization problem?

00:01:17 Then how can we extend such optimization formulation to address additional considerations like noises or extending from classification to, sorry, binary classification to multi-class classification or from classification to regression.

00:01:39 Okay?

00:01:40 And lastly, the nonlinear support vector machines and kernels will be revisited again.

00:01:47 Okay?

00:01:48 Okay, so what is the intuition of support vector machines?

00:01:57 These are based on the slides that are available here and there's additional references.

00:02:03 Okay, so what is the intuition of support vector machines?

00:02:10 For instance, we have a two-dimensional space.

00:02:12 We have, you know, blue and yellow, I'm sorry, blue and white points.

00:02:17 We want to use a linear classifier to separate them.

00:02:22 So, how would you separate them?

00:02:25 And then how would you tell computers to find a linear classifier?

00:02:29 If it's linear in the two-dimensional space, it's just a line, right?

00:02:34 Okay.

00:02:35 So, if this is an optimization problem, what are the decision variables?

00:02:42 What are the constraints?

00:02:44 And what is the objective function?

00:02:47 Anyone?

00:02:48 What is the decision variable?

00:02:51 The coefficient of this line, right?

00:03:04 Like beta transpose times x, if x is a vector.

00:03:07 Beta is our decision variable, right?

00:03:10 Okay?

00:03:11 So, notice that here in machine learning, we usually have reserved x and y for the input-output.

00:03:16 Okay?

00:03:17 So, usually x is not used for decision variables in optimization.

00:03:21 Okay?

00:03:22 So, that's something you need to pay attention to.

00:03:24 So, in this case, beta is the decision variable.

00:03:26 Okay?

00:03:27 Beta transpose x.

00:03:28 Or w transpose x plus b, where w is slope and b is the intercept.

00:03:38 Okay?

00:03:39 So, those are our decision variables.

00:03:42 Any constraints for w and b?

00:03:49 They are real.

00:03:50 That's it, I guess.

00:03:51 Okay, then what's the objective function?

00:03:54 What's the optimal classifier?

00:03:57 You have learned the support vector machines.

00:03:59 Can anyone help me?

00:04:00 What's the optimal linear classifier?

00:04:04 And where is that?

00:04:06 What's the intuition behind it?

00:04:08 Okay, who have just taken support vector machines this week?

00:04:15 You?

00:04:16 Okay.

00:04:17 Anyone else?

00:04:18 I'm sure it's been covered in other courses as well.

00:04:28 Okay, so.

00:04:29 Okay, anyone want to try?

00:04:31 Don't be shy.

00:04:32 Yes, please.

00:04:33 Doyoung.

00:04:34 smoking last box or minus one we want every data points to be satisfied at inequality.

00:04:49 Ah, okay.

00:04:50 So you're saying that.

00:04:51 Okay, good.

00:04:52 You're talking about the constraints, right?

00:04:54 Because earlier I was saying that one of the constraints about w and b I was saying that.

00:04:59 constraint except that are real, right? Of course that's wrong, right? Because you

00:05:03 need the blue points to be on one side, right? Let's say the plus one class so it

00:05:11 should be bigger than zero, right? And the white points should be on the other

00:05:17 side, so let's say it's a class minus one, then it should be less than zero. When

00:05:22 I say it, I mean w transpose times xi plus b, where xi could be a blue point,

00:05:29 could be a white point, right? So it's on the two sides, right? Your formulation

00:05:35 actually didn't allow any margin. You're saying that, right, all the blue has to be

00:05:39 on one side and you cannot cross, right? And all the white has to be on the other

00:05:45 side and no cross. Good, so our constraints are getting clearer now. What's the

00:05:50 objective function now? So for all such choices that satisfy your constraint,

00:06:04 which one is the best? What's the objective function? The most distant from?

00:06:15 Right. From the closest blue or white. Is that right? So later on we'll know that

00:06:24 they are actually so-called support vectors, right? Okay, so good. Exactly as you said.

00:06:32 The intuition is that to keep the frontier of the blue or white as far away as possible

00:06:41 from the classifier so that you can avoid the, you know, the noises in the data and

00:06:50 have a more robust classifier. For instance, if you have a classifier like this, where

00:06:55 this white point is right at the border. Now imagine that there is some error or noise in

00:07:04 the feature of that white point, right, or the label of the white point, right? Then you see that,

00:07:13 you know, the noise in this single white point is affecting the validity or the optimality of this

00:07:21 classifier so much. So you don't want that to happen. You want some robustness. You want your

00:07:27 decision boundary or this classifier, right, to be as far as possible from both sides, okay?

00:07:34 So that's a goal, okay? So then it's less sensitive to the label or the feature noises, okay?

00:07:46 Okay, so and how do we quantify that? That is called the margin, okay? Okay, do we all know how to

00:07:54 calculate such margin? Do we know how to calculate such margin?

00:08:09 So we can keep W and move B left right until hitting the first blue or white, right?

00:08:21 So we can keep W and move B left right. But that's correct. But then quantitatively,

00:08:26 how do we describe that margin? How do we find out that margin? How do we derive the margin?

00:08:51 Okay, so before that question, I want to also say something, you know, deeper than our intuition,

00:09:04 that maximizing the margin is good in some sense based on our intuition, but it's also good theoretically

00:09:14 based on the Peck theory, okay? Probably approximately correct. And also implies that only the support vectors

00:09:23 are important in defining the borders, right? And empirically, it works, you know, well.

00:09:31 And this is a linear case, okay? So how do we calculate the margin? So as Doyoung said that,

00:09:41 we can't do that, but our goal is to correctly classify the training data if the labels are plus one and minus one, blue and white.

00:09:48 So these are the constraints we have, okay? Now we can rewrite these two types of constraints,

00:09:56 one for blue and one for white, into just one inequality based on yi, right? Right?

00:10:04 Don't get me wrong, you may think, oh, well, I don't want to make a product, then you are ruining the linearity,

00:10:11 and linear programming is easier. But don't forget, our decision variables are w and b.

00:10:19 X and i and yi's are known. These are observed. So our inequality after this formulation is still linear, right?

00:10:31 And then we want to maximize the margin. The margin is actually two divided by the norm of w.

00:10:38 Do we know how to derive that?

00:10:56 Do we know how to do that?

00:10:58 **[Uncertain recognition]** Do we know how to derive that?

00:11:02 **[Uncertain recognition]** All right.

00:11:04 **[Uncertain recognition]** We don't actually provide some intimate realise because there are reasons why one moment

00:11:05 **[Uncertain recognition]** Yeah.

00:11:07 **[Uncertain recognition]** When we pour down these frå야 away.

00:11:10 **[Uncertain recognition]** All right.

00:11:12 **[Uncertain recognition]** Do we know how to derive it?

00:11:14 **[Uncertain recognition]** Do we know how to derive this forma that canfinals happen to each term?

00:11:18 Right? And then you are reaching a blue frontier where a blue point is and you are reaching

00:11:39 a white frontier where a white point is and you know that this is what? What describes this line?

00:12:01 Equals to? And this describes, right? So if you have one point here, let's say x1, you have

00:12:22 another point x2, right? And this is your w, right? So if you have w1 here, w2 here, right?

00:12:36 Then you take the subtraction, you have w transpose times x1 minus x2, the vector pointing toward x2,

00:12:46 right? Right? Equals to? 2. Right? Okay. Are we close to get the margin?

00:13:07 What is the margin? The margin is what? Here I'm assuming that this is a perpendicular, right?

00:13:15 W and x1 minus x2, they're perpendicular. So what's the margin? This is your margin, right?

00:13:26 Right? And x1 minus x2 is exactly this vector. So can you now see why margin is equal to 2 times

00:13:41 **[Uncertain recognition]** x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2 minus x2

00:14:11 instead of maximize the two divided by norm of w,

00:14:16 we can maximize the denominator directly,

00:14:19 or we can maximize the square of the denominator,

00:14:23 okay, which is easier, okay,

00:14:26 because you don't wanna have the square root in it.

00:14:29 So what we end up having is a quadratic optimization problem

00:14:34 with linear constraints.

00:14:35 It's quadratic objective function in w,

00:14:38 and it's a linear in w for the constraints, okay?

00:14:45 And this problem can be solved exactly, analytically, okay?

00:14:51 Don't bother about the convergence, convergence rate.

00:14:56 So this can be solved exactly, okay?

00:15:01 And I can say a little bit more about it,

00:15:04 because so far we don't understand theoretically

00:15:08 what supported vector machines means, right?

00:15:11 So I think you have learned already

00:15:14 at least the weak duality, right?

00:15:18 So here I wanna emphasize this,

00:15:20 because when we talk about linear programming,

00:15:23 we only said the primal formulation, okay?

00:15:27 There's actually a dual, okay?

00:15:30 So the primal formulation is that we're minimizing

00:15:34 this half norm squared, subject to the linear constraints, okay?

00:15:40 So this is a well-known class of problem

00:15:43 with guaranteed exact algorithms, with guaranteed optimum, okay?

00:15:48 And the solution involves constructing a dual problem, okay?

00:15:55 A dual problem, and a Lagrange multiplier alpha i

00:16:03 is the dual variables, okay?

00:16:07 So what you can think of is as a following.

00:16:09 In the primal world, you have constraint

00:16:12 and the decision variables, right?

00:16:15 The primal decision variables, right?

00:16:18 In the dual world, the dual decision variables

00:16:22 are corresponding to each primal constraints, okay?

00:16:26 That's a multiplier, Lagrange multiplier,

00:16:30 associated with every constraint, okay?

00:16:34 So in this case, the dual problem

00:16:37 is finding the optimal dual variables, right?

00:16:41 So that we can rewrite this dual form,

00:16:46 and then we are just maximizing this one,

00:16:51 so that the sum of alpha i, y, i equal to zero,

00:16:55 and alpha is bigger than or equal to zero, okay?

00:16:58 So this is our dual forms, okay?

00:17:01 So for those of you who haven't learned this,

00:17:06 I strongly recommend you look at the duality theory

00:17:11 in linear programming, for instance, okay?

00:17:14 So you need to be familiar with

00:17:17 what duality theory looks like, okay?

00:17:22 And without understanding the dual variables

00:17:26 and Lagrange multipliers,

00:17:27 it's really hard to understand the support vectors, okay?

00:17:32 So as I said that, this alpha i is corresponding to each constraint,

00:17:45 and each constraint in the, each primal constraint

00:17:48 is corresponding to what?

00:17:52 Each primal constraint is corresponding to example i, right?

00:17:57 So that dual variable, alpha i,

00:18:01 is something about each example i, okay?

00:18:06 Well, we'll see what that means.

00:18:08 What exactly is it, okay?

00:18:10 And this alpha i's are non-negative.

00:18:14 So the optimal solution, okay,

00:18:17 the optimal solution has the following form, okay?

00:18:21 It's actually the optimal w is the sum of alpha i times yi,

00:18:27 is already known, times xi, okay?

00:18:29 It's very simple, okay?

00:18:32 And some alpha i are zero,

00:18:39 and some alpha i are non-zero.

00:18:41 So if alpha i equal to zero for a given i,

00:18:44 then that point has no input to the optimal solution, isn't it?

00:18:51 Right?

00:18:53 But if an alpha i is non-zero,

00:18:57 then those points directly determine the classifier.

00:19:02 So those are the support vectors, okay?

00:19:06 The support vectors, okay?

00:19:09 And if you want to learn even more,

00:19:11 you know, when alpha i is non-zero,

00:19:14 anyone recall what?

00:19:16 When alpha i is non-zero.

00:19:21 **[Uncertain recognition]** Mathematically,

00:19:32 Mathematically, what condition does the corresponding constraint have to be satisfied for alpha to be zero or non-zero, based on what you learn from weak duality?

00:20:02 Exactly. Alpha i is strictly positive and non-zero only if the corresponding constraint i for point, for example, i, has an active constraint, meaning that the equality holds.

00:20:23 Okay? That makes sense as we just described, right?

00:20:28 Right? Right? We have seen before that one is plus one and one is minus one right here for the support of vectors, right?

00:20:36 So I hope you get this.

00:20:43 And, okay, this is the first, of course, I skipped a lot of things.

00:20:51 I didn't tell you how to derive the dual variable, and I didn't introduce a weak duality.

00:20:57 So that you can reach the conclusion I was saying.

00:21:00 So, but I understand that those were covered in other courses.

00:21:03 So, I strongly suggest to you, if you don't recall the details right now, after the lectures, please make sure that you review those contents.

00:21:14 Okay?

00:21:16 This is just the first observation from the optimization formulation.

00:21:20 The second observation is the following.

00:21:23 The second observation is the following.

00:21:28 The classifying function, if you plug in the W and B, optimal W and B, what you end up finding is that, actually,

00:21:40 how does each feature, sorry, how does the feature or the input of each example enter the optimal classifier?

00:21:57 We notice that it's the inner product between the example Xi and the test vector X.

00:22:05 Okay?

00:22:06 Does this ring a bell?

00:22:07 Does this ring a bell?

00:22:20 In the dual problem, we saw that, again, the features or the input of the examples enters the formulation through kernels among the examples.

00:22:34 Right?

00:22:35 This is a special kernel, a linear kernel, which is the inner product.

00:22:39 Okay?

00:22:40 So, in other words, we actually don't need the exact Xi or XJ.

00:22:46 Okay?

00:22:47 We actually can solve this, right, based on the kernel representation.

00:22:55 So, this is another concept I want to emphasize that we can learn from the optimization formulation.

00:23:01 Okay?

00:23:02 Okay.

00:23:03 So, now that is done, right?

00:23:06 Now, let's try to extend this formulation.

00:23:09 Okay?

00:23:10 We said previously we want all the blue on one side, all the white on the other side.

00:23:14 What if you cannot achieve that with a linear classifier?

00:23:19 What would you do?

00:23:20 One way is that, well, let's try to make this nonlinear and extremely sophisticated, right?

00:23:26 But, in other words, you use nonlinear or extremely powerful nonlinear kernels.

00:23:35 Okay?

00:23:36 But, you know what's the problem with this, right?

00:23:39 It's overcomplicated model, which can be too sensitive.

00:23:43 In other words, overfitting.

00:23:45 Okay?

00:23:46 What people usually do to address this overfitting issue is the following.

00:23:54 Instead of strictly asking blue and white to be on two sides, opposite two sides, we allow

00:24:01 some blue or white crossing the border to the other side.

00:24:08 And extend the cross border to the other side is described as a new decision variable called

00:24:16 epsilon.

00:24:17 Epsilon 11, epsilon 2, epsilon 7.

00:24:21 This is also called slack variables.

00:24:23 We'll see why it's called slack variables.

00:24:25 Okay?

00:24:26 Then we can first look at the objective function.

00:24:30 The objective function is saying the following.

00:24:33 Let's still try to maximize the margin, but in the meantime, let's try to make sure that the

00:24:39 cumulative violation is as small as possible.

00:24:44 Okay?

00:24:45 So it's like a multi-objective optimization, right?

00:24:48 And you use a C to control the balance between the two objectives.

00:24:53 Okay?

00:24:54 Again, these epsilons are non-negative.

00:24:55 Okay?

00:24:56 Right?

00:24:57 So it's a violation of the border.

00:24:59 Okay?

00:25:00 That's the objective function.

00:25:02 So in the constraint side, all you have to change from the old formulation, right, is now,

00:25:09 instead of asking it to be bigger than or equal to one for yi equal to one, you allowed it to be

00:25:15 one minus epsilon i, where epsilon i is bigger than or equal to zero.

00:25:20 So that's why it's called a slack variable, right?

00:25:23 Intuitively, it's the violation you can cross the border, but the way it enters the formulation

00:25:31 is on the right-hand side of these linear equalities, right?

00:25:35 So it's a slack variable, right?

00:25:37 So this is a very simple optimization problem, again, because it's still quadratic, right?

00:25:45 Right?

00:25:46 It's linear.

00:25:47 The objective function here is linear in epsilon i and quadratic in w, and it's, again, linear

00:25:52 in w and epsilon, right?

00:25:55 So this is a hyperparameter c to control the overfitting, okay?

00:26:02 And this is what we said.

00:26:04 This is a linear support vector machine.

00:26:06 It's a separating hyperplane.

00:26:08 And the most important ones are support vectors, but you understand that this is the corresponding

00:26:15 to the non-zero Lagrangian multiplier or dual variables alpha i corresponding to the active constraint

00:26:26 in the primal form corresponding to training point x i, okay?

00:26:31 And in both dual formulation and in the solution, we found the inner products.

00:26:36 So we see that kernels keep appearing, actually.

00:26:39 This is showing that it's actually a kernel method even before you realize it, okay?

00:26:45 And we know the formulation and the optimal solutions, right?

00:26:49 And last, I want to say how we want to extend sometimes, because sometimes you just cannot have a perfect linear border or separating plane, right?

00:27:06 In that case, you may think about nonlinear.

00:27:10 But how?

00:27:12 Right?

00:27:13 Because I drew that sophisticated border before, and you know that, probably not a good idea, and I don't know how you drew that.

00:27:19 Right?

00:27:20 The question is, is there a principled way?

00:27:22 The principled way is simple.

00:27:24 If you understood that SVM is a kernel method, okay?

00:27:29 So the idea is that let's map the data to a higher dimensional space, so that the plane is linear in that higher dimensional space, okay?

00:27:40 But it's nonlinear in the original space.

00:27:45 For instance, this X, right?

00:27:46 If I introduce X square, additional dimension, then you see that all of a sudden, red and blue can be linearly separated, right?

00:27:55 With, so the question is, how do we do that mapping, right?

00:27:59 How do we do that mapping, right?

00:28:00 So in this case, the general idea is that we map the original X to a higher dimensional phi of X, okay?

00:28:10 Into the higher dimensional phi of X, then how do we do that?

00:28:13 Well, you have different choices, right?

00:28:16 So this is the so-called kernel trick.

00:28:19 Remember, in the optimization formulation and in the optimal solution, all we needed was the kernels, right?

00:28:27 So in that case, the kernels were linear, dot product, right?

00:28:32 So if you want to generalize it, one idea is you replace X with phi.

00:28:39 So in the higher dimensional phi space, you still have a linear kernel, but in the original X space, it's nonlinear, right?

00:28:50 So it's a very powerful way, right?

00:28:52 For instance, this is one example, right?

00:28:56 You have a kernel which is one plus the inner product squared, right?

00:29:02 Then you have to sort of factorize them into phi transpose times phi, right?

00:29:09 Then you can do this and find one example in this case.

00:29:15 We can actually rewrite into one, two, three, four, five, six dimension.

00:29:20 Six dimension phi, okay?

00:29:23 That higher dimensional space, okay?

00:29:25 So I suggest you to look at this again.

00:29:28 I think it's a very simple practice, okay?

00:29:32 But this is just one example.

00:29:34 But in general, what functions can qualify as kernels, right?

00:29:41 There's this .
