5주차, Support Vector Machine

빨간 점들과 파란 선들을 어떻게하면 가장 잘 classifcation하는 decision bounary를 잡을 수 있을까?

⇒ 경계에서 가장 가까운 점들을 관통하는 두 직선에서 가장 멀리 떨어져있는 점(Margin 최대화)

이를 위해서 3개의 점(2빨간, 1파란)을 찾는다고 하자. 어떻게 찾을 수 있을까?

decision boundary를 $$wx+b$$로 정의할 때,

$$wx+b>0$$이면 positive, $$wx+b<0$$이면 negative로 놓을 수 있다.(위 그림에서는 빨간색이 positive, 파란색이 negative)

이때, positive를 +1, negative를 -1이라고 모델링하면(이게 yj)

Confidence level = $$(w \cdot w_j+b)y_j$$이다. (j는 각각에 대해서라는뜻)

이때, confidence level은 항상 양수이므로($y_j$때문에), 이를 최대화하면 margin을 최대화 할수 있다.

한 점 x를 wx+b에 projection한 걸 xp라고 하면, 두 점 사이의 거리는 $$\cfrac{f(x)}{||w||}$$가 된다.

이 거리(margin)을 최대화 하는것이 좋은 decision bondary다.

이를 최적화 문제로 풀 수 있는데,

이 때, a=f(x)=wx+b 이고, 2r인 이유는 both side(positive, negative)를 고려해야 하기 때문이다.

또한, a는 임의의 값(arbitary number)이므로 normalize할 수 있고, a=1이라고 생각하면 위의 식을 다음과 같이 바꿀 수 있다.

이는 quadratic optimization(이차 계획법)으로 풀 수 있는 문제다.

optimization을 공부 안해서 이차 계획법은 잘모르지만, 대충 찾아본걸 정리하면

1. 목적함수(뭔가를 최소화 시키는것. $$ {1\over2}X^TQx+c^Tx$$같은 꼴이다)
2. 등식 제한조건(Ax=b)
3. 부호 제한조건($$x \ge0)$$

같은게 있고, 이때 모든 조건을 만족하는 x를 찾는 거임.

그런데, 아래처럼 우리가 설계한 decision boundary로 구분할 수 없는 값들(한 선으로 구분이 안감)이 들어오면 w를 찾을 수 없다.

이럴때 두 가지 방법을 쓸 수 있는데

1. error를 허용하는 방법인 soft margin SVM(우리가 앞에서 한건 hard margin이다)
2. decision boundary를 비 선형으로 만드는 kernel trick

Sotf margin

앞의 식에 뒤에다가 error term + C X #error 만큼의 페널티를 줄 수있다.

그런데, 이 방식으로 했을때의 loss를 생각해보면,

위 그림에서 0-1 Loss의 모양을 갖게 된다. (decision bondary에서 올라감)

이건 멀리 떨어진거나 가까이 있는거나 동일한 페널티를 주는건데, 사실 별로 좋지 않다. quadratic programming으로도 잘 안된다. 그래서, hinge loss를 사용한다.

문제는 어떻게이다. C값이 아니라, slack variable이라는 걸 사용해서 멀어질수록 페널티가 커지게 한다.

slack은, 보다시피 합으로 정의된다.

slack의 값 $$\xi_j = (1-(wx_j+b)y_j)_+$$ 는, 잘못 분류되었을때 1을 넘고, support line과 decision boundary사이에서 0~1사이이며, support line 안에 있는거는 =0이다.

(밑첨자 +는 양수면 그대로, 음수면 0 출력한다는 뜻)

추가로, Hinge Loss를 Logistic Regression의 Loss(Log-loss)와 비교해보자.

파란게 log-loss이다.

이게 그 수식인데, 밑의 식에서 $$Y_iX_i\theta-log(1+e^{X_i\theta)}$$가 hinge loss의$$ \xi_j = (1-(wx_j+b)y_j)$$와 비슷하지 않은가? 그래서 hinge loss의 식을 log loss로 만들면

위와 같이 나타낼 수 있다.

log loss와 hinge loss의 차이는 decision boundary근처의 구간인데, hinge는 이때 loss가 0이지만, log는 0이 아니다. 사용하기 나름이고, 뭐가 더 좋다는 없다.

C에 따른 decision boundary이다. C가 작으면 페널티가 작은거니까, 일단 크게 잡고 시작하는게 좋다라는 말이 전해진다고 한다.

Kernel Trick

왼쪽이 리니어, 오른쪽이 논리니어. 오른쪽이 더 나아보이지 않냐.

어떻게 non-linear로 만들까? 사실 우리는 이미 해봤어

$$\varphi(<x_1, x_2>) = <x_1, x_2, x_1^2, x_2^2, x_1x_2....>$$이런 식으로 결합하거나 곱해서 차원을 늘리는거지(Interaction Term). 이걸 무한대까지 늘려보자.

그러기 위해서는 Classification 문제인 SVM을 Contrained Quadratic Programming으로 바꾼다.

아래의 꼴로 말이다. 이게 Primal 꼴이고, 이를 Dual로 바꿔주면, 커널을 더 잘 쓸수 있다는데, Optimization공부가 부족하므로 대충 아래같은 차이가 있다는것만 알고 넘어가자.

그럼 어떻게 dual로 바꿀까? Lagrange Method를 사용할거다.

그걸 쓰면 두 조건$$g(x)\le0, h(x)=0$$을 목적함수에 가져다가 붙일 수 있게 된다.

g(x), h(x)를 Lagrange Multiplier $\alpha, \beta$를 사용해서 목적함수 식에다가 붙일 수 있다.

이를 Lagrange Dual function으로 바꿔서 식을 만들고,

(여기서 사실 optimization 관련 지식이 좀 필요했다. duality, lower bound, constraint function, concave... 일단 미뤄놓고 생각하자)

Lagrange Dual problem은 양수의 Lagrange Multiplier를 사용하여 object function에 constraint를 추가한 다음, 기존의 object function을 최소화하는 primal variable을 구하여 최소화시키는 Lagrangian을 형성하는 것 (= Lagrange dual Function) 이다.

이때 이 문제를 풀기 위한 솔루션은 Lagrange multiplier의 기능을 하는 primal variable을 제공하기 때문에(이를 dual variable이라고 한다), 이때 dual variable에 대한 derived constraint (non-negativity constraint, 즉 라그랑지 승수는 양수여야 한다는 조건) 에서 dual variable에 대한 object function을 최대화하는 문제로 바뀌게 된다.

라고 한다...

여튼 이 식을 이용하면 특정 optimization문제가 f(x)와 동일하게 동작하게 된다고 한다.

그 내용이 4번째 줄이다(feasible)

하여튼, 이 문제를 잘 풀기 위해서는 Strong Duality를 만족해야한다.

Strong duality는 dual function에서 나온 답(d*)과 primal function의 답(p*)이 같은 해를 가진다는거고, 이걸 만족하게 해주는 조건이 KKT condition이다.

아래와 같은 5가지 조건이 있는데, 나중에 보자.

그래서 어떻게 Dual 꼴로 만들어주는가?

앞에서 구한 Hard Margin의 식에서 1을 좌변으로 넘기고, 그거를 라그랑주 승수(멀티플라이어)에 대해 변형하고, 모든 것들(j)에 대해 구하기 위해서 summation하면 아래와 같은 식이 나온다.

여기서 max와 min을 바꾸면, \alpha에 대한 최적화 문제로 바뀌게 된다.

이 식에 KKT condition을 적용해서 식을 정리하면

위와 같은 식으로 바뀐다. 이러면 라그랑주 승수인 알파에 대한 최적화 값으로 바뀌게 된다.(x랑 y는 이미 데이터로써 우리가 들고 있으니까 알고있지).

Quadratic Programming으로 다시 바뀐거야.(왜냐면 알파텀이 최대 2승이니까)

 

일단 매핑에 대해 다시 알아보고 가자

이렇게 다른 차원으로 보내서 classification 할 수 있게 되는거야. 그런데 이게 feature space가 늘어나면(차원이 늘어나면)힘들잖아. 이걸 최적화 하는게 Kernel Trick이다.

일단 커널은 다른 차원에 있는 두 벡터의 내적으로 표현돼

커널의 종류중에 Polynomial이 있는데

위와 같이 그냥 내적하고 제곱, 세제곱한거랑 다를게 없네?

⇒ mapping하고 내적한 거나, 내적하고 mapping한거나 다를게 없다!!

⇒당연히 지금 있는 space(작음)에서 내적하고 mapping하면 편하다

 

이제 \varphi를 써서 차원을 늘려보자. 아까 정리했던

식의 x를 mapping하면

위와 같은 식이 나오고, 이를 커널 형태로 나타내면

이렇게 고칠 수 있다. 커널은 뭐 아무거나 고른다고 해보자.

 

W, b도 이렇게 식으로 나타낼 수 있다.

그런데, b는 $\varphi$가 2개라서 커널로 바꿀 수 있는데, w는 하나라서 커널 식으로 바꿀수가 없다.

근데 w가 왜필요하지? 이걸 이용해서 classification을 하기 위해서지? 그럼 그냥 분류해볼까?

이렇게 식으로 정의해보자. (sign은 positive면 양수, negative면 음수)

이 식을 전개하면

이렇게 되고, 중간에 varphi 2개가 커널이 되어서 

이렇게 식이 바뀐다.

여기 있는 $$\alpha, y, Kernel, x$$는 우리가 이미 아는 값(커널은 정하는값)이므로 값을 구할 수 있다.

실제로 4차, RBF 커널로 해봤을 때 non-linear 한 decision boundary를 갖는걸 볼 수 있다.