brunch

You can make anything
by writing

C.S.Lewis

by 라인하트 Nov 13. 2020

앤드류 응의 머신러닝(12-3):SVM 큰 마진인 이유

온라인 강의 플랫폼 코세라의 창립자인 앤드류 응 (Andrew Ng) 교수는 인공지능 업계의 거장입니다. 그가 스탠퍼드 대학에서 머신 러닝 입문자에게 한 강의를 그대로 코세라 온라인 강의 (Coursera.org)에서 무료로 배울 수 있습니다. 이 강의는 머신러닝 입문자들의 필수코스입니다. 인공지능과 머신러닝을 혼자 공부하면서 자연스럽게 만나게 되는 강의입니다.

Support Vector Machines

서포트 벡터 머신

Large Margin Classification (큰 마진 분류)

Mathematics Behind Large Margin Classification

(큰 마진 분류 뒤의 수학)

In this video, I'd like to tell you a bit about the math behind large margin classification. This video is optional, so please feel free to skip it. It may also give you better intuition about how the optimization problem of the support vector machine, how that leads to large margin classifiers.

이번 강의는 서포트 벡터 머신의 최적화 문제가 어떻게 큰 마진으로 이어지는 지를 수학적으로 설명합니다. 이번 강의는 옵션이므로 건너뛰어도 상관없습니다.

In order to get started, let me first remind you of a couple of properties of what vector inner products look like. Let's say I have two vectors U and V, that look like this. So both two dimensional vectors. Then let's see what U transpose V looks like. And U transpose V is also called the inner products between the vectors U and V. Use a two dimensional vector, so I can on plot it on this figure. So let's say that's the vector U. And what I mean by that is if on the horizontal axis that value takes whatever value U1 is and on the vertical axis the height of that is whatever U2 is the second component of the vector U. Now, one quantity that will be nice to have is the norm of the vector U. So, these are, you know, double bars on the left and right that denotes the norm or length of U. So this just means; really the euclidean length of the vector U. And this is Pythagoras theorem is just equal to U1 squared plus U2 squared square root, right? And this is the length of the vector U. That's a real number. Just say you know, what is the length of this, what is the length of this vector down here. What is the length of this arrow that I just drew, is the normal view?

먼저 벡터 내적에 대한 몇 가지 속성을 정리합니다.

여기 2차원 벡터 u와 v가 있습니다. u^Tv는 어떤 모습일까요? u^Tv는 벡터 u와 v의 내적입니다. 2차원 벡터가 의미하는 바를 도식화합니다. 벡터 u를 도식화하면 수평축은 u1, 수직축은 u2라고 할 때 원점에서 시작하는 하나의 직선을 그릴 수 있습니다. 벡터 u의 유클리드 길이는 왼쪽과 오른쪽의 이중 막대로 ||u||표시하고 놈이라고 명명합니다.

벡터 u의 길이 ||u||는 피타코라스의 정리에 따라 √(u1^2 + u2^2)이고 실수입니다. 화살표의 길이는 무엇을 의미할까요?

Now let's go back and look at the vector V because we want to compute the inner product. So V will be some other vector with, you know, some value V1, V2. And so, the vector V will look like that, towards V like so.

이제 다시 돌아가서 벡터 v를 그리고 벡터 v와 벡터 u의 내적을 계산합시다. v1과 v2의 값을 특정하고 벡터 v를 분홍색 화살표로 그립니다.

Now let's go back and look at how to compute the inner product between U and V. Here's how you can do it. Let me take the vector V and project it down onto the vector U. So I'm going to take a orthogonal projection or a 90 degree projection, and project it down onto U like so. And what I'm going to do measure length of this red line that I just drew here. So, I'm going to call the length of that red line P. So, P is the length or is the magnitude of the projection of the vector V onto the vector U. Let me just write that down. So, P is the length of the projection of the vector V onto the vector U. And it is possible to show that unit product U transpose V, that this is going to be equal to P times the norm or the length of the vector U. So, this is one way to compute the inner product. And if you actually do the geometry figure out what P is and figure out what the norm of U is. This should give you the same way, the same answer as the other way of computing unit product. Right. Which is if you take U transpose V then U transposes this U1 U2, its a one by two matrix, 1 times V. And so this should actually give you U1, V1 plus U2, V2. And so the theorem of linear algebra that these two formulas give you the same answer.

And by the way, U transpose V is also equal to V transpose U. So if you were to do the same process in reverse, instead of projecting V onto U, you could project U onto V. Then, you know, do the same process, but with the rows of U and V reversed. And you would actually, you should actually get the same number whatever that number is. And just to clarify what's going on in this equation the norm of U is a real number and P is also a real number. And so U transpose V is the regular multiplication as two real numbers of

the length of P times the normal view.

그리고, 벡터 u와 벡터 v 사이의 내적을 계산합니다. 벡터 v를 벡터 u 위에 사영합니다. 그래서, 직교 사영으로 벡터 u의 화살표 위에 붉은색 선을 그리고 길이를 측정합니다. 붉은색 선의 길이를 p라 하고 벡터 v가 벡터 u에 사영되는 크기입니다. 이것이 벡터 u와 벡터 v의 내적입니다.

u =[u1; u2] 2 X 1차원 행렬을 전치하면 1 X 2 행렬입니다. 실제로 기하학에서 p와 ||u||를 계산하면 벡터 u와 v의 내적과 동일합니다. 선행 대수에서 두 식은 같은 결과를 얻습니다.

u^Tv는 v^Tu와 같습니다. 지금까지 와 반대의 프로세스로 수행합니다. 벡터 v를 벡터 u를 사영하는 대신에 벡터 u를 벡터 v에 사영합니다. 벡터 v를 전치하면 1 X 2 행렬이고 동일한 결과를 얻습니다. 이 방정식에서 ||u||와 p는 실수입니다. u^Tv는 실수 간의 곱셈으로 p의 길이와 ||u||의 길이를 곱한 것입니다.

Just one last detail, which is if you look at the norm of P, P is actually signed so to the right. And it can either be positive or negative. So let me say what I mean by that, if U is a vector that looks like this and V is a vector that looks like this. So if the angle between U and V is greater than ninety degrees. Then if I project V onto U, what I get is a projection it looks like this and so that length P. And in this case, I will still have that U transpose V is equal to P times the norm of U. Except in this example P will be negative. So, you know, in inner products if the angle between U and V is less than ninety degrees, then P is the positive length for that red line whereas if the angle of this angle of here is greater than 90 degrees then P here will be negative of the length of the super line of that little line segment right over there. So the inner product between two vectors can also be negative if the angle between them is greater than 90 degrees. So that's how vector inner products work.

마지막으로 p는 벡터 u에 벡터 v를 직교 사영한 길이입니다. 이것은 양수이거나 음수일 수 있습니다. 왼쪽 하단에 새로운 벡터 u와 벡터 v를 그립니다.

벡터 u와 벡터 v 사이의 각도가 90도 보다 더 크다면 붉은색 선 p는 벡터 u의 화살표에 있지 않고 뒤에 그려집니다. 이때 u^Tv = p·||u|| 같고 p < 0 이므로 음수입니다. 만일 벡터 u와 벡터 v 사이의 각도가 90도 미만이면 p는 빨간색 선에 대한 양수 길이입니다. 만일 벡터 u와 벡터 v 사이의 각도가 90도 이상이면 p는 빨간색 선에 대한 음수 길이입니다. 이것이 벡터의 내적의 동작 원리입니다.

We're going to use these properties of vector inner product to try to understand the support vector machine optimization objective over there. Here is the optimization objective for the support vector machine that we worked out earlier. Just for the purpose of this slide I am going to make one simplification or once just to make the objective easy to analyze and what I'm going to do is ignore the theta 0. So, we'll just ignore theta 0 and set that to be equal to 0. To make things easier to plot, I'm also going to set N the number of features to be equal to 2. So, we have only 2 features, X1 and X2.

Now, let's look at the objective function. The optimization objective of the SVM. What we have only two features. When N is equal to 2. This can be written, one half of theta one squared plus theta two squared. Because we only have two parameters, theta one and thetaa two. What I'm going to do is rewrite this a bit. I'm going to write this as one half of theta one squared plus theta two squared and the square root squared. And the reason I can do that, is because for any number, you know, W, right, the square roots of W and then squared, that's just equal to W. So square roots and squared should give you the same thing.

벡터 내적의 속성을 활용하여 서포트 벡터 머신의 최적화 목표를 정리합니다. 서포트 벡터 머신 최적화 목표를 단순화하기 위해 θ0를 0으로 설정하여 무시합니다. 그리고, 피처의 개수는 n = 2로 제한합니다. 피처는 x1과 x2입니다.

여기서, 파라미터 θ1과 θ2를 제곱근에 대한 제곱의 형태로 변환합니다. 어떤 값 w = (√w)^2 은 같은 값이기 때문입니다. 제곱근의 값을 제곱하면 동일한 값입니다.

What you may notice is that this term inside is that's equal to the norm or the length of the vector theta and what I mean by that is that if we write out the vector theta like this, as you know theta one, theta two. Then this term that I've just underlined in red, that's exactly the length, or the norm, of the vector theta. We are calling the definition of the norm of the vector that we have on the previous line. And in fact this is actually equal to the length of the vector theta, whether you write it as theta zero, theta 1, theta 2. That is, if theta zero is equal to zero, as I assume here. Or just the length of theta 1, theta 2; but for this line I am going to ignore theta 0. So let me just, you know, treat theta as this, let me just write theta, the normal theta as this theta 1, theta 2 only, but the math works out either way, whether we include theta zero here or not. So it's not going to matter for the rest of our derivation. And so finally this means that my optimization objective is equal to one half of the norm of theta squared. So all the support vector machine is doing in the optimization objective is it's minimizing the squared norm of the square length of the parameter vector theta.

눈치 빠른 분들은 알아차렸을 것입니다.

1/2*(√(θ1^2 + θ2^2))^2의 내부인 √(θ1^2 + θ2^2)는 벡터 θ의 길이인 ||θ||와 같습니다. 실제로도 벡터 θ의 길이와 같습니다. 벡터 θ = [ θ0; θ1; θ2]로 쓸 수 있습니다. 이미 θ0 = 0으로 무시할 것입니다. 마지막으로 이것은 최적화 목표가 1/2*||θ||^2와 같습니다. 따라서 모든 서포트 벡터 머신이 최적화 목표에서 수행하는 것은 파라미터 벡터 θ의 제곱의 놈을 최소화하는 것입니다.

Now what I'd like to do is look at these terms, theta transpose X and understand better what they're doing. So given the parameter vector theta and given and example x, what is this is equal to? And on the previous slide, we figured out what U transpose V looks like, with different vectors U and V. And so we're going to take those definitions, you know, with theta and X(i) playing the roles of U and V.

And let's see what that picture looks like. So, let's say I plot. Let's say I look at just a single training example. Let's say I have a positive example the drawing was across there and let's say that is my example X(i), what that really means is plotted on the horizontal axis some value X(i) 1 and on the vertical axis X(i) 2. That's how I plot my training examples. And although we haven't been really thinking of this as a vector, what this really is, this is a

vector from the origin from 0, 0 out to the location of this training example.

벡터의 내적을 바탕으로 θ^Tx^(i)를 정리합니다. 파라미터 벡터 θ와 주어진 예제 x가 있다면 이것은 무엇을 의미하는 걸까요? u^Tv와 마찬가지입니다. θ를 u로 x^(i)를 v로 생각합니다.

그리고, 어떤 모양인지를 알기 위해 도식화합니다. 단 하나의 학습 예제를 본다고 가정합니다. 특정한 점을 x^(i)라고 한다면 수평축에 x1^(i)와 수직축에 x2^(i)입니다. 이것이 학습 예제를 그리는 방법입니다. 이것을 벡터로 생각하지 않지만 실제로 의미하는 바는 원점 (0,0)에서 학습 예제까지의 벡터입니다.

And now let's say we have a parameter vector and I'm going to plot that as vector, as well. What I mean by that is if I plot theta 1 here and theta 2 there so what is the inner product theta transpose X(i). While using our earlier method, the way we compute that is we take my example and project it onto my parameter vector theta. And then I'm going to look at the length of this segment that I'm coloring in, in red. And I'm going to call that P superscript I to denote that this is a projection of the i-th training example onto the parameter vector theta. And so what we have is that theta transpose X(i) is equal to following what we have on the previous slide, this is going to be equal to P times the length of the norm of the vector theta. And this is of course also equal to theta 1 x1 plus theta 2 x2. So each of these is, you know, an equally valid way of computing the inner product between theta and X(i).

여기 파라미터 벡터가 있습니다. 벡터로 도식화합니다. 이것이 의미하는 바는 수평축에 θ1을 수직축에 θ2입니다. 파라미터 벡터 θ에 학습 예제 벡터를 수직 사영합니다. θ^Tx^(i)는 빨간색 선의 길이입니다.

결국, θ^Tx^(i)는 앞에서 배운 u^Tv와 같습니다. 빨간색 선은 p^(i)·||θ|| 와 같습니다. 그리고 이것은 θ1x1^(i) + θ2x2^(i)와 같습니다. 그리고 θ와 x^(i) 사이의 내적을 계산하는 것과 똑같습니다.

Okay. So where does this leave us? What this means is that, this constrains that theta transpose X(i) be greater than or equal to one or less than minus one. What this means is that it can replace the use of constraints that P(i) times X be greater than or equal to one. Because theta transpose X(i) is equal to P(i) times the norm of theta.

P^(i)·||θ|| 가 의미하는 것은 θ^Tx^(i) >= 1 또는 θ^Tx^(i) < 1 조건을 대체할 수 있습니다. 왜냐하면 θ^Tx^(i)는 p^(i)·||θ|| 와 같기 때문입니다.

So writing that into our optimization objective. This is what we get where I have, instead of theta transpose X(i), I now have this P(i) times the norm of theta. And just to remind you we worked out earlier too that this optimization objective can be written as one half times the norm of theta squared.

그래서 최적화 목표에 사용할 수 있습니다. θ^Tx^(i) 대신에 p^(i)·||θ||를 사용합니다. 또한 서포트 벡터 머신의 비용 함수 min 1/2 * Σθj^2 = 1/2*||θ||^2라는 것을 상기합니다.

So, now let's consider the training example that we have at the bottom and for now, continuing to use the simplification that theta 0 is equal to 0. Let's see what decision boundary the support vector machine will choose. Here's one option, let's say the support vector machine were to choose this decision boundary. This is not a very good choice because it has very small margins. This decision boundary comes very close to the training examples. Let's see why the support vector machine will not do this.

이제 하단에 있는 학습 예제를 고려합니다. θ0 = 0이라고 단순화합니다. 서포트 벡터 머신이 어떤 결정 경계를 선택할지 봅시다. 여기에 한 가지 옵션이 있습니다. 서포트 벡터 머신이 결정 경계를 선택한다고 가정합니다. 여백이 매우 적기 때문에 좋은 선택은 아닙니다. 이 결정 경계는 학습 예제와 매우 유사합니다. 서포트 벡터 머신이 이렇게 하지 않는 이유를 살펴보겠습니다.

For this choice of parameters it's possible to show that the parameter vector theta is actually at 90 degrees to the decision boundary. And so, that green decision boundary corresponds to a parameter vector theta that points in that direction. And by the way, the simplification that theta 0 equals 0 that just means that the decision boundary must pass through the origin, (0,0) over there. So now, let's look at what this implies for the optimization objective.

파라미터를 선택하기 위해 파라미터 벡터 θ는 결정 경계와 90도에 있음을 보여줍니다. 녹색 결정 경계는 해당 방향을 가리키는 파라미터 벡터 θ에 해당합니다. θ0 = 0이라는 단순화는 결정 경계가 원점(0,0)을 통과한다는 것을 의미합니다. 이것이 최적화 목표에 무엇을 의미하는 지를 살펴보겠습니다.

Let's say that this example here. Let's say that's my first example, you know, X1. If we look at the projection of this example onto my parameters theta. That's the projection. And so that little red line segment. That is equal to P1. And that is going to be pretty small, right. And similarly, if this example here, if this happens to be X2, that's my second example. Then, if I look at the projection of this this example onto theta. You know. Then, let me draw this one in magenta. This little magenta line segment, that's going to be P2. That's the projection of the second example onto my, onto the direction of my parameter vector theta which goes like this. And so, this little projection line segment is getting pretty small. P2 will actually be a negative number, right so P2 is in the opposite direction. This vector has greater than 90 degree angle with my parameter vector theta, it's going to be less than 0.

여기에 예제가 있습니다. 특정한 예제를 첫 번째 예제 x^(i)으로 가정합니다. 첫 번째 예제의 파라미터 θ에 대한 직교 사영을 살펴봅니다. 여기 작은 빨간 선분은 p^(1)이고 길이는 매우 작을 것입니다. 마찬가지로 두 번째 예제 x^2입니다. 두 번째 예제의 파라미터 θ에 대한 직교 사영을 살펴봅니다. 분홍색 선으로 그립니다. 여기 작은 분홍색 선분은 p^(2)이고 길이는 매우 작을 것입니다. 그래서, 이 작은 사영 선분은 점점 작아지고 있습니다. p^(2)는 실제로 음수이며 반대 방향입니다. 이 벡터는 파라미터 벡터 θ와 90도보다 큰 각도를 가지며 0 보다 작을 것입니다.

And so what we're finding is that these terms P(i) are going to be pretty small numbers. So if we look at the optimization objective and see, well, for positive examples we need P(i) times the norm of theta to be bigger than either one. But if P(i) over here, if P1 over here is pretty small, that means that we need the norm of theta to be pretty large, right? If P1 of theta is small and we want P1 you know times in all of theta to be bigger than either one, well the only way for that to be true for the profit that these two numbers to be large if P1 is small, as we said we want the norm of theta to be large.

그래서 p^(i)는 아주 작은 숫자일 것입니다. 최적화 목표를 살펴보면 파지티브 예제에서 p^(i)·||θ|| >= 1입니다. 그러나 p^(i)가 아주 작다면 ||θ|| 이 매우 커야 한다는 것을 의미합니다. 어느 한쪽의 숫자가 매우 작고 결과값이 커지려면 다른 값이 매우 커야 합니다. p^(1)·||θ|| >= 1에서 ||θ||이 매우 커야 합니다.

And similarly for our negative example, we need P2 times the norm of theta to be less than or equal to minus one. And we saw in this example already that P2 is going pretty small negative number, and so the only way for that to happen as well is for the norm of theta to be large, but what we are doing in the optimization objective is we are trying to find a setting of parameters where the norm of theta is small, and so you know, so this doesn't seem like such a good direction for the parameter vector and theta.

그리고 네거티브 예제도 비슷하게, p^(2)·||θ|| <= -1입니다. 이미 P^(2)가 아주 작은 음수라는 것을 확인하였습니다. 따라서, p^(2)·||θ|| 에서 p^(2)가 아주 작은 값이므로 ||θ||은 커져야 합니다. 그러나 최적화 목표는 ||θ||가 작은 파라미터의 값을 찾는 것입니다. 그래서 이것은 파라미터 벡터 θ에 대한 좋은 값이 아닙니다.

In contrast, just look at a different decision boundary. Here, let's say, this SVM chooses that decision boundary. Now the is going to be very different. If that is the decision boundary, here is the corresponding direction for theta. So, with the direction boundary you know, that vertical line that corresponds to it is possible to show using linear algebra that the way to get that green decision boundary is have the vector of theta be at 90 degrees to it, and now if you look at the projection of your data onto the vector x, lets say its before this example is my example of x1. So when I project this on to x, or onto theta, what I find is that this is P1. That length there is P1. The other example, that example is and I do the same projection and what I find is that this length here is a P2 really that is going to be less than 0. And you notice that now P1 and P2, these lengths of the projections are going to be much bigger, and so if we still need to enforce these constraints that P1 of the norm of theta is phase number one because P1 is so much bigger now. The normal can be smaller. And so, what this means is that by choosing the decision boundary shown on the right instead of on the left, the SVM can make the norm of the parameters theta much smaller. So, if we can make the norm of theta smaller and therefore make the squared norm of theta smaller, which is why the SVM would choose this hypothesis on the right instead.

반대로 우측의 그림과 같은 다른 결정 경계를 봅시다. SVM이 수직축의 녹색 선의 결정 경계를 선택했다면 이에 대응하는 θ는 90도 각도의 수평선을 선택할 것입니다. 데이터를 벡터 x에 사영합니다. 첫 번째 예제 x^(1)을 θ에 사영하면 p^(1)은 붉은색 선분입니다. 두 번째 예제 x^(2)를 θ 직선에 사영하면 p^(2)는 분홍색 선분입니다. p^(2)는 음수입니다. p^(1)과 p^(2)의 길이가 훨씬 더 크기 때문에 ||θ||의 크기는 작아집니다. 즉, SVM은 왼쪽의 결정 경계보다 오른쪽 결정 경계를 선택하여 최적화 목표인 θ의 값을 최소화합니다. 1/2 * ||θ||^2의 값이 더 작습니다. 이것이 SVM이 오른쪽 가설을 선택하는 이유입니다.

And this is how the SVM gives rise to this large margin certification effect. Mainly, if you look at this green line, if you look at this green hypothesis we want the projections of my positive and negative examples onto theta to be large, and the only way for that to hold true this is if surrounding the green line. There's this large margin, there's this large gap that separates positive and negative examples is really the magnitude of this gap. The magnitude of this margin is exactly the values of P1, P2, P3 and so on. And so by making the margin large, by these tyros P1, P2, P3 and so on that's the SVM can end up with a smaller value for the norm of theta which is what it is trying to do in the objective. And this is why this machine ends up with enlarge margin classifiers because itss trying to maximize the norm of these P1 which is the distance from the training examples to the decision boundary.

그리고, SVM이 큰 마진 효과를 일으키는 이유입니다. 녹색 선을 보면 θ에 대한 파지티브 예제와 네거티브 예제의 사이의 길이가 커져야 합니다. 파지티브 예제와 네거티브 예제를 구분하는 가장 큰 차이는 실제로 차이의 크기입니다. 정확히 p^(1), p^(2), p^(3) 등의 값입니다. 그래서 마진을 크게 함으로써 SVM은 최소화 목표를 수행하기 위해 ||θ||의 값을 더 작은 값으로 만듭니다. 알고리즘이 학습 예제에서 결정 경계까지의 거리인 P^(1)·||θ||을 최대화하려고 하기 때문에 마진 분류기라고 부릅니다.

Finally, we did this whole derivation using this simplification that the parameter theta 0 must be equal to 0. The effect of that as I mentioned briefly, is that if theta 0 is equal to 0 what that means is that we are entertaining decision boundaries that pass through the origins of decision boundaries pass through the origin like that, if you allow theta zero to be non 0 then what that means is that you entertain the decision boundaries that did not cross through the origin, like that one I just drew. And I'm not going to do the full derivation that. It turns out that this same large margin proof works in pretty much in exactly the same way.

마지막으로 파라미터 θ0 = 0에 정리합니다. 지금까지 SVM을 이해하기 쉽게 하기 위해 θ0 은 값을 0으로 단순화하였습니다. 그 효과로 결정 경계는 원점 (0,0)을 지납니다. 만약 θ0 가 0이 아닌 값을 사용한다면 결정 경계는 원점을 통과하지 않을 것입니다. 나머지는 동일하게 동작합니다.

And there's a generalization of this argument that we just went through them long ago through that shows that even when theta 0 is non 0, what the SVM is trying to do when you have this optimization objective. Which again corresponds to the case of when C is very large. But it is possible to show that, you know, when theta is not equal to 0 this support vector machine is still finding is really trying to find the large margin separator that between the positive and negative examples. So that explains how this support vector machine is a large margin classifier. In the next video we will start to talk about how to take some of these SVM ideas and start to apply them to build a complex nonlinear classifiers.

θ0 가 0이 아닌 경우에도 최적화 목표를 수행하기 위해 SVM은 상수 C를 사용합니다. 상수 C가 매우 큰 경우 파라미터 θ0가 0이 아닐 때도 서포트 벡터 머신은 파지티브 예제와 네거티브 예제 사이에 큰 마진을 결정 경계로 찾습니다. 지금까지 서포트 벡터 머신이 큰 마진 분류기인 이유를 살펴보았습니다.