SVM

SVM(support vector machine)

Introduction

간단하게 SVM이란, 클래스를 분류하기 위한 가장 좋은 hyper-plane 을 찾는 것이라고 할 수 있다.

여기서 Hyper-Plane 이란 N차원의 벡터 공간에서 N-1차원의 부분 공간을 의미하는데, 여기서 이 Hyper-Plane 은 벡터 공간에서 1차원 선을 법선으로 갖는 초평면 이라고 해석할 수 있다.

쉽게 생각해서 3차원 공간이 있다고 할 때 우리는 보통 2차원 평면을 그린 후 해당 평면을 1차원의 법선 벡터로 정의하게 되는데, 아무리 이 차원 공간이 커진다고 하더라도 Hyper-Plane은 1차원 법선 벡터를 갖는 N-1차원의 부분 공간이라고 생각하면 편하다.

그림 1. SVM의 개요

지금 보이는 그림에서 각 직선을 우리는 Hyper-plane이라고 할 수 있다.

여기서 우리의 문제 정의는 무엇일까?

우리의 문제는 -.+ 두가지 class를 올바르게 분리할 뿐만 아니라 해당 분리 과정에서 선을 긋는데, 그 선은 두 Class간의 거리를 최소화 하여 긋게 하는 것이다.

즉, 나누는 Hyper-Plane은 많지만 여기서 가장 적은 error(각 plane 에서 class간의 거리)를 최소화 하는 plane 을 찾고자 하는 것이다.

위 그림에서 $\vec{w}$ 는 dased line 의 법선벡터라고 할 수 있으며, $\vec{u}$는 임의의 data라고 해보자.

해당 그림에서 저 Line의 방정식을 $\vec{w}$를 이용하여 $\vec{w} x +b$($b$는 고정 상수)라고 정의할 수 있는데, 위 그림의 $\vec{u}$를 대입하게 되면 $\vec{w} \vec{u} + b$의 방정식을 얻게 되며 위 방정식은 0보다 작은 값을 갖게 될 것이다.

그렇다면 Idea가 생길 수 있다.

우리가 어떤 클래스를 분류할 때, Hyperplane 을 임의로 만들고, 그 Hyper plane을 기준으로 분류하고자 하는 데이터들의 부호가 반대로 되도록 만들 수 있다면, 또 그 값들의 absolute value 가 작다면, 우리는 최적의 Hyper Plane을 찾을 수 있게 되는 것이 아닐까?

이러한 문제에서 SVM은 출발하게 된다.

어떻게 Error를 구하는가?

우선 서포트 벡터 머신은 margin이라는 값을 사용한다. 이 margin은 단순히 각 class의 가장 가까운 관측치 간의 거리이다.

예를 들어 직선이 있고 이 직선(hyper plane)을 중심으로 -,+ 로 나눈다고 할 때 - 진영에서 직선과 가장 가까운 관측치 간의 거리와 +진영에서 직선과 가장 가까운 관측치 간의 거리를 margin이라고 한다.

아래 그림에서 노랑 영역의 폭이 margin이라고 할 수 있다.

그림 2. SVM margin

이 margin은 동일한 데이터에 대해 모델이 어떻게 분류하느냐에 따라 달라질 수 있다.

예를 들어 동일한 데이터에 대해 A라는 모델은 매우 좁은 값의 margin을 갖고 B라는 모델은 상대적으로 큰 값의 margin을 갖는다고 할 때 어떤 모델이 좋은 모델일까?

B의 모델이 새로운 데이터가 들어왔을 때 좀 더 Robust 할 것이기 때문에 우리는 B모델을 좀 더 선호할 것이다.

따라서 우리는 N차원의 벡터 공간에 무수히 많은 데이터들을 두 클래스로 분류하기 위해 Margin이 최댓값을 갖는 N-1차원의 Hyper plane을 설계하는 것이 목적이다.

Training Set up

앞서 모델을 학습시키는 과정에서 어떤 목적을 갖고 학습을 진행할 것인지에 대해서 살펴보았다.

Training을 위해 또 한 가지 준비 할 것은 두 데이터 포인트이다.

이 두 데이터 포인트는 임의의 hyper plane과 가장 거리가 가까운 각 Class의 한 점이다.

그림1에서 위쪽 실선 위의 점을 $x^+$ 라고 하고 아랫쪽 실선위의 한 점을 $x^-$라고 하자.

그렇다면 $w x^+ + b =1$ 을 위쪽 실선의 식이라고 해보자.

여기서 위쪽 실선의 식을 해당 식과 같이 정의 한 이유는 우리가 margin에 대해서 이야기 할 때 우리가 정의한 hyper-plane(dashed line) 을 평행 이동 시켜 각 class 에서 가장 거리가 짧은 값을 포함시킬 수 있도록 평면을 두개 만들게 되는데 그림 1의 실선의 두 직선이 그 직선이다.

물론 $\delta$ 만큼 떨어져있어 우리가 모르는 미지의 수이지만, 모든 계수는 결정되지 않았기 때문에 계산 편의상 1로 놓아도 무방하다.

그럼 아래쪽 실선에서의 데이터 포인트 또한 $w x^- +b = -1$이라고 표현할 수 있겠다.

여기서 $x^+ $ 는 $x^-$ 에서 $\lambda w$ 만큼 평행이동 한 point 라고 하자.

또한 위쪽 실선의 윗부분, 아래쪽 실선의 아래 부분의 데이터 포인트들은 모두 각 $+$와 $-$ 클래스로 할당되게 되기 때문에

$wx^+ + b \geq 1$ , $w x^- +b \leq -1$ 의 두가지 수식으로 구분될 수 있다는 것을 알 수 있다.

또한 우리는 $y_i$ 라는 변수를 데이터가 $x^+$ 라면 1, $x^-$라면 -1 로 표현되는 변수라고 설정을 해보자. (해당 설정은 이후 제약식을 통한 최적화 문제에서 사용된다.)

그렇다면 두 클래스가 +인지 -인지 구분할 수 있는 수식을 $y_i(w^T x_i +1) \geq 1$ 로 한번에 표현할 수 있다.

우선 변수에 대한 set up 은 이렇게만 진행하고, 이후에 어떻게 이 변수를 통해 최소 margin을 갖는 hyper-plane을 찾는지 살펴보자.

최적화 문제

우리가 앞서 가정한 대로 식을 한번 짜보자.

$w x^+ +b =1 $ 에서 $x^+$ 는 $x^-$ 에서 평행이동 한 값이므로 $w x^+ b =1 $ 은 $w(x^- + \lambda w^T) + b =1 $ 이라고 표현할 수 있다.

또 위 식을 풀어쓰면 $w x^- + b + \lambda w w^T = 1$ 은 $-1 + \lambda w w^T =1$ 이 되며 해당 식을 이항하면 $\lambda = \frac{2}{W^TW}$ 가 된다.

또한 $x^+ , x^- $ 는 평행이동 한 점이므로 우리가 구하고자 하는 margin은 $\vert \vert x^+ - x^- \vert \vert$ 이며 해당 식을 풀어 쓰면 $\vert \vert x^- + \lambda w^T - x^- \vert \vert$ = $\vert \vert \lambda w^T \vert \vert $ 가 된다.

해당 식을 다시 쓰면 $\lambda (w w^T)^{1/2}$ 가 되는데, 앞서 $\lambda$ 의 정의에 의해 해당 식은 $\frac{2}{w^Tw} \cdot (ww^T)^{1/2} = \frac{2}{\vert \vert w \vert \vert}$ 가 된다.

따라서 margin 은 $\frac{2}{\vert \vert w \vert \vert}$ 가 된다.

우리의 목적은 해당 maring을 최대화 하는 것인데 해당 값을 최대화 하는 것은 $1/2 \vert \vert w \vert \vert_2$ 를 최소화 하는 것과 같다.

라그랑주 승수 법 사용

따라서 우리의 목적 함수는 $\frac{1}{2} \vert \vert w \vert \vert_2$ 이며 우리가 처한 조건은 $y_i(w^T x_i +b) \geq 1$ 이다.

또한 Hyper plane을 설계하기 위한 파라미터는 $w$ 와 $b$ 이고 $y_i$ 는 임의적으로 우리가 만든 변수이다.

따라서 라그랑주 승수법을 사용하기 위해 보조 방정식을 $L = \frac{1}{2}\vert \vert w \vert \vert_2 - \sum_i \alpha_i [y_i(w^T x_i + b)]$ 로 정의할 수 있다.

우리는 위 식이 최솟값을 갖는 지점을 찾아 볼 것이다.

이제 해당 식의 최솟값을 찾기 위해 파라미터 편미분을 통해 0이되는 지점을 찾아보자.

$\frac{\part L}{\part w} = w - \sum_i \alpha_i y_i x_i =0$ 이 되며 $w = \sum_i \alpha_i y_i x_i$ 가 되었다.

우리가 원하는 $w$ 를 찾기 위해서는 라그랑주 승수법의 파라미터인 $\alpha$ 들을 찾아야 하는 것이다.

$\frac{\part L}{\part b} = \sum_i \alpha_i y_i x_i = 0$ 의 식이 나온다.

따라서 위 두 가지 식을 원 식 $L$ 에 넣게 된다면 우리가 원하는 최솟값을 구할 수 있을 것이다.

$L$ 에 두가지 조건 식을 넣게 된다면 ($w = \sum_i \alpha_i y_i x_i$, $\sum_i \alpha_i y_i x_i = 0$ )

$\sum_i \alpha_i - \frac{1}{2}\sum_i \sum_j \alpha_i \alpha_j y_i y_j x_i x_j$ 라는 식을 얻을 수 있게 된다.

따라서 우리는 위 식을 최소화 하게 되면, 적절한 Hyper plane을 찾을 수 있게 된다.

Kernel Trick

위 식에서 우리가 파악할 수 있는 것은 $x_i \cdot x_j$ 라는 부분이다.

표기 편의 상 해당 변수를 상수취급 하였지만 실질적으로 각 변수는 vector인데, 저 두 벡터의 내적 값이 클 수록 $L$ 의 값은 작아지게 된다.

따라서 해당 변수들을 적절히 변환시킨다면(벡터의 차원을 옮김) 서포트 벡터 머신의 성능을 좀 더 높일 수 있을 것이다.

그림 3. SVM kernel trick

해당 그림은 이러한 kernel trick을 쉽게 나타낸 것인데, 단순히 2차원의 data를 3차원으로 kernel 함수를 통한 변환을 시켜주어 $L$ 값을 줄인 것이다.

Support Vector

이제 해당 머신의 이름에 대해서 살펴보자.

해당 머신은 Support 하는 Vector를 구해서 최적값을 찾는 머신이다.

여기서 Support 하는 벡터란 우리가 앞서 계산했던 식들에서 $w x^- +b = -1$ $w x^+ +b = 1$ 를 만족하는 수식들 즉 그림 1의 실선 위의 점 들이다.

해당 점들을 기반으로 우리는 $L$ 을 구하게 되었는데, SVM 에서 실선 직선 위에 없는 데이터 포인터들이 갖는 $\alpha$ 값은 모두 0 에 해당하므로 outlier 에 영향을 잘 받지 않는 robust한 모델이다.

또한 해당 모델은 완벽하게 분류할 수 없는 데이터에 대해서는 계산이 불가능 할 수 있다.

따라서 Soft margin SVM 이란 모델이 생겨나게 되었는데 해당 모델은 $e$ 의 에러를 허용하는 모델로 동일하게 라그랑주 승수법을 통한 최적화가 이뤄지지만, Ridge, Lasso와 같은 $C$ 를 파라미터로 두어 margin 과 error 간의 trade-off를 결정하게 한다.

해당 $C$값은 에러에 가중치를 주는 것이므로 데이터의 클래스 경계가 불분명하고 $C$ 값이 높다면 오버피팅을 발생시킬 수 있다.

그림 4. SVM Soft Margin

Loss

SVM은 다중 분류 문제에서 익숙한 cross entropy loss를 사용하는 것이 아니고 다른 loss 값을 사용한다.

우선 앞서 정의한 $w$ 는 $\alpha,y,x$ 의 summation으로 변환하여 최솟값을 구하게 되는데, $w x_n + b \geq 1$ 이 되는 어떤 data point $x_n$ 이 있다고 하고 해당 $x_n$ 을 모델이 positive class 라고 판단했다고 해보자.

만약 실제 $x_n$ 이 negative sample이라면, 해당 모델은 이 판단을 고쳐 적절한 $w$를 다시 세팅해야 한다.

여기서 쓰이는 지표 (얼마나 분류를 잘 못 했는지)가 loss이며 해당 loss 값을 토대로 $w$ 값을 갱신하게 되는데, SVM의 경우는 이 loss 값으로 hinge loss 를 사용하게 된다.

힌지 로스의 수식은 생각보다 간단하게 아래와 같이 나타난다. $L_i = \sum_{i ~ \neq y_i} max(0,s_i - s_{y_i} +1)$

여기서 $y_i$ 는 정답 라벨이라고 할 때 해당 Loss 는 $s_i$ (잘 못 분류한 클래스를 확신하는 정도) 에 $s_{y_i}$ (정답 클래스를 확신하는 정도) 를 뺀 후 1을 더한 식으로 값을 계산한다.

위 식에서 보듯 해당 loss 값은 클래스를 잘 못 분류했다고 해서 극단적으로 loss 가 높아지진 않는다.

예를 들어 croos entropy의 경우에는 오답을 완벽하게 확신하면 Loss 값이 무한대로 발산하지만 hinge loss 값은 그렇지 않다는 특징을 갖고 있다.

SVM with python

from sklearn.svm import SVC
from sklearn import datasets

iris = datasets.load_iris()
# 훈련 세트
X = iris["data"][:, (2, 3)] # # 꽃잎 길이, 꽃잎 너비
y = (iris["target"] == 2).astype(np.float64).reshape(-1, 1) # Iris virginica

from sklearn.base import BaseEstimator

class MyLinearSVC(BaseEstimator):
    def __init__(self, C=1, eta0=1, eta_d=10000, n_epochs=1000, random_state=None):
        self.C = C
        self.eta0 = eta0
        self.n_epochs = n_epochs
        self.random_state = random_state
        self.eta_d = eta_d

    def eta(self, epoch):
        return self.eta0 / (epoch + self.eta_d)
        
    def fit(self, X, y):
        # Random initialization
        if self.random_state:
            np.random.seed(self.random_state)
        w = np.random.randn(X.shape[1], 1) # n feature weights
        b = 0

        m = len(X)
        t = y * 2 - 1  # -1 if y==0, +1 if y==1 class 변환 함수 
        X_t = X * t # class 변환 
        self.Js=[]

        # Training
        for epoch in range(self.n_epochs):
            support_vectors_idx = (X_t.dot(w) + t * b < 1).ravel() # 인덱스 분류
            X_t_sv = X_t[support_vectors_idx] # data point 가 들어간 함수 
            t_sv = t[support_vectors_idx]

            J = 1/2 * np.sum(w * w) + self.C * (np.sum(1 - X_t_sv.dot(w)) - b * np.sum(t_sv)) # soft margin 에서의 비용함수 정의 
            # 해당 함수가 최소화된 지점을 반환
            self.Js.append(J)

            w_gradient_vector = w - self.C * np.sum(X_t_sv, axis=0).reshape(-1, 1)
            # w의 기울기 벡터를 기존 w 에서 계속해서 갱신한다. 
            b_derivative = -self.C * np.sum(t_sv)
                
            w = w - self.eta(epoch) * w_gradient_vector
            b = b - self.eta(epoch) * b_derivative
            

        self.intercept_ = np.array([b])
        self.coef_ = np.array([w])
        support_vectors_idx = (X_t.dot(w) + t * b < 1).ravel()
        self.support_vectors_ = X[support_vectors_idx] 
        # w 갱신 
        return self 

    def decision_function(self, X):
        return X.dot(self.coef_[0]) + self.intercept_[0]

    def predict(self, X):
        return (self.decision_function(X) >= 0).astype(np.float64)

C=2
svm_clf = MyLinearSVC(C=C, eta0 = 10, eta_d = 1000, n_epochs=60000, random_state=2)
svm_clf.fit(X, y)
svm_clf.predict(np.array([[5, 2], [4, 1]]))

plt.plot(range(svm_clf.n_epochs), svm_clf.Js) plt.axis([0, svm_clf.n_epochs, 0, 100])

해당 수식으로 비용함수의 변화를 확인할 수 있다.

그림 5. SVM Loss