SVM(support vector machine)

서포트 벡터 머신

퍼셉트론에서는 영역을 구분하는 판별경계선(decision hyperplane)이 한 문제에도 다양하게 존재할 수 있었다.

서포트 벡터머신(SVM: Support Vector machine)은 퍼셉트론 기반 모형에 가장 안정적인 하나의 판별 경계선을 찾기 위한 제한조건을 추가한 모형이다.

• 서포트: 판별경계선을 하나로 정해줄 수 있는 근거가 되는
• 벡터: 데이터
• 음의 서포트 벡터(o)와 양의 서포트 벡터(x) 사이의 거리 : 마진

서포트와 마진

다음과 같이 N개의 학습용 데이터가 있을 때,

$$(x_1,y_1),(x_2,y_2),\cdots,(x_i,y_i),\cdots,(x_N,y_N)$$

판별함수모형에서 $y$ 는 +1 혹은 -1 의 값을 갖는다.

$$y = \begin{cases} +1\\-1 \end{cases}$$

판별함수모형에서 판별함수를 정의하기 전에 다음 수식들을 복습삼아 짚고 넘어가자.

• $w^Tx - w_0 = 0$ : 벡터 w에 수직인 x의 직선방정식

• $\dfrac{|w^Tx - w_0|}{||w||}$ : 점과 직선의 거리

이제 판별함수 모형에서 직선인 판별함수 $f(x)$ 는 다음과 같은 수식으로 나타낼 수 있다.

$$f(x) = w^Tx - w_0$$

데이터 중에서 $y$값이 +1인 데이터를 $x_+$, $y$값이 -1인 데이터를 $x_-$라고 하면, 판별함수 정의에 따라 $x_+$에 대한 판별함수 값은 양수가 되고, $x_-$에 대한 판별함수 값은 음수가 된다.

$$f(x^+) = w^Tx^+ - w_0> 0\\ f(x^-) = w^Tx^- - w_0<0$$

$x_+ $중에서 판별 함수의 값이 가장 작은 데이터를 $x^+$라고 하고 $x_- $중에서 판별함수의 값이 가장 큰 데이터를 $x^-$라고 하자. 이 데이터들은 각각의 클래스에 속한 데이터 중에서 가장 경계선에 가까이 붙어있는 최전방(most front)의 데이터들이다. 즉, 마이너스 값을 갖는 데이터 중에서 가장 큰 데이터와 플러스값을 갖는 데이터 중에서 가장 작은 데이터에 해당하는 애들을 서포트(support) 혹은 서포트 벡터(support vector)라고 한다.

그런데 조건을 지키는 내에서 100프로 동일한 성능을 갖는 판별함수가 다양하게 존재할 수 있다. 따라서 하나의 판별함수를 구하기 위해 $f(x^+)=1, f(x^-)=-1$ 이 되도록 normalizing한 판별함수를 구한다.

$$f(x^+) = w^Tx^+ - w_0 = +1\\ f(x^-) = w^Tx^- - w_0 = -1$$

그렇게 되면 판별경계선 $f(x)$ 와 두 점 $x^+, x^-$ 사이의 거리는 아래와 같이 계산할 수 있다.

$$\frac{w^Tx^+ - w_0}{||w||} = \frac{1}{||w||}\\ - \frac{w^Tx^- - w_0}{||w||}=\frac{1}{||w||}$$

이 거리의 합을 마진(margin)이라 하며, 마진값이 클수록 경계선이 안정적이라고 할 수 있다. 위 두 식을 더하면 마진은 $\dfrac{2}{||w||}$ 가 되므로, 마진값이 최대가 되는 경우는 $||w||$ 이 최소가 되는 경우가 된다. 계산의 편의를 위해 제곱을 취해주면 $||w||^2$ 를 최소화하는 문제가 되므로 quadratic optimization 이 된다.

결국 마진을 최대화하는 것은 다음과 같은 목적함수를 최소화하는 것과 같다.

$$L = \frac{1}{2} ||w||^2 = \frac{1}{2}w^Tw$$

또한 모든 표본데이터에 대해 다음 부등식제한조건을 만족해야 한다.

$$y_i\cdot (w^Tx_i - w_0) - 1 \geq 0\,\,\,\,\, (i=1,\cdots ,N)$$

그렇게 되면 라그랑주 승수법을 통해 목적함수 $L$을 다음과 같이 고칠 수 있다.

$$L = \frac{1}{2}w^Tw - \sum^N_{i=1}a_i\{y_i\cdot(w^Tx_i-w_0)-1\}$$

여기서 $a_i$ 는 각각의 부등식에 대한 라그랑주 승수이다. 이 최적화문제를 풀어 $w, w_0, a$ 를 구하면 판별함수를 얻을 수 있다.

듀얼 형식(Dual Form)

최적화를 위해서는 일단 목적함수를 $w, w_0$으로 미분한 값이 0이 되어야 한다.

$$\frac{\partial L}{\partial w} = 0 \\ \frac{\partial L}{\partial w_0} = 0$$

이 식을 풀어서 정리하면 다음과 같아진다.

$$\begin{eqnarray} \frac{\partial L}{\partial w} &=& \frac{\partial}{\partial w}\left(\frac{1}{2} w^Tw\right) - \frac{\partial}{\partial w} \sum^N_{i=1}(a_iy_iw^Tx_i - a_iy_iw_0 - a_i)\\ &=& w - \sum^N_{i=1}a_iy_ix_i\\ &=& 0 \end{eqnarray}$$ $$\begin{eqnarray} \frac{\partial L}{\partial w_0} &=& \frac{\partial}{\partial w_0}\left(\frac{1}{2} w^Tw\right) - \frac{\partial}{\partial w_0} \sum^N_{i=1}(a_iy_iw^Tx_i - a_iy_iw_0 - a_i)\\ &=& \sum^N_{i=1}a_iy_i\\ &=& 0 \end{eqnarray}$$

여기서 $a_i$, $y_i$, $w^Tx$ 는 모두 스칼라이고, 정리하면 아래와 같은 식이 나온다.

$$w = \sum^N_{i=1}a_iy_ix_i$$ $$0 = \sum^N_{i=1}a_iy_i$$

이 두 식을 원래의 목적함수에 대입하여 $w, w_0$을 없애면 다음과 같다.

$$\begin{eqnarray} L &=& \frac{1}{2}w^Tw - \sum^N_{i=1}a_i\{y_i\cdot(w^Tx_i - w_0) -1\}\\ &=& \frac{1}{2}\left(\sum^N_{i=1}a_iy_ix_i\right)^T \left(\sum^N_{j=1}a_jy_jx_j\right) - \sum^N_{i=1}a_i\left\{y_i\cdot \left(\left(\sum^N_{j=1}a_jy_jx_j\right)^T x_i-w_0\right)-1\right\}\\ &=& \frac{1}{2}\sum^N_{i=1}\sum^N_{j=1}a_ia_jy_iy_jx_i^Tx_j - \sum^N_{i=1}\sum^N_{j=1}a_ia_jy_iy_jx^T_ix_j + w_o\sum^N_{i=1}a_iy_i + \sum^N_{i=1}a_i\\ &=& \sum^N_{i=1} a_i - \frac{1}{2}\sum^N_{i=1}\sum^N_{j=1}a_ia_jy_iy_jx^T_ix_j \end{eqnarray}$$

즉,

$$L = \sum^N_{i=1}a_i - \frac{1}{2}\sum^N_{i=1}\sum^N_{j=1}a_ia_jy_iy_jx^T_ix_j$$

이 때 $a$는 다음조건을 만족한다.

$$\sum^N_{i=1}a_iy_i = 0\\ a_i \geq 0\,\,\,\,\,(i = 1, \cdots , N)$$

이제 이 문제는 𝑤를 구하는 문제가 아니라 𝑎만을 구하는 문제로 바뀌었으므로 듀얼 형식(dual form)이라고 한다. 듀얼형식으로 바꾸면 수치적으로 QP(Quadratic Programming)문제가 되므로 원래의 문제보다 효율적으로 풀 수 있게 된다.

QP문제를 풀어서 구한 $a$ 값을 식에 대입하면 $w$ 값을 찾을 수 있다.

우선 $L$을 최소화하는 a 값을 구하면 예측모형을 다음과 같이 쓸 수 있다.

$$f(x) = w^Tx - w_0 = \sum^N_{i=1}a_iy_ix_i^Tx - w_0$$

$w_0$ 은

$$w_0 = w^Tx^+ - 1\\ \text{또는}\\ w_0 = w^Tx^- + 1\\ \text{또는}\\ w_0 = \frac{1}{2}w^T(x^+ + x^-)$$

로 구한다.

$a_i=0$ 일 경우 해당 데이터는 $w$ 계산에 아무런 기여를 하지 않으므로 위 식은 사실상 다음과 같다.

$$f(x) = a^+x^Tx^+ - a^-x^Tx^- - w_0$$

여기서 $x^Tx^+$ 는 $x$ 와 $x^+$ 사이의 코사인유사도, $x^Tx^-$ 는 $x$ 와 $x^- $ 사이의 코사인유사도이므로, 결국 두 서포트벡터 중 코사인유사도가 큰 쪽으로 판별하게 된다. 이렇게 계산하는 것은 실제 판별경계선으로부터 데이터의 거리를 계산하는 것과 똑같다.

Scikit-Learn 의 서포트 벡터 머신

scikit-learn의 svm 서브패키지는 서포트벡터 머신 모형인 SVC (Support Vector Classifier) 클래스를 제공한다.

SVC 클래스는 커널(kernel)을 선택하는 인수 kernel 과 슬랙변수 가중치(slack variable weight)를 선택하는 인수 C 를 받는데 지금까지 공부한 서포트벡터 머신을 사용하려면 인수를 다음처럼 넣어준다.

from sklearn.svm import SVC
model = SVC(kernel='linear', C=1e10).fit(X, y)

위와 같은 학습용 데이터를 SVM 모델로 예측하면 아래와 같은 결과가 나온다.

xmin = X[:, 0].min()
xmax = X[:, 0].max()
ymin = X[:, 1].min()
ymax = X[:, 1].max()
xx = np.linspace(xmin, xmax, 10)
yy = np.linspace(ymin, ymax, 10)
X1, X2 = np.meshgrid(xx, yy)

Z = np.empty(X1.shape)
for (i, j), val in np.ndenumerate(X1):
    x1 = val
    x2 = X2[i, j]
    p = model.decision_function([[x1, x2]])
    Z[i, j] = p[0]
levels = [-1, 0, 1]
linestyles = ['dashed', 'solid', 'dashed']
plt.scatter(X[y == -1, 0], X[y == -1, 1], marker='o', label="-1 클래스")
plt.scatter(X[y == +1, 0], X[y == +1, 1], marker='x', label="+1 클래스")
plt.contour(X1, X2, Z, levels, colors='k', linestyles=linestyles)
plt.scatter(model.support_vectors_[:, 0], model.support_vectors_[:, 1], s=300, alpha=0.3)

x_new = [10, 2]
plt.scatter(x_new[0], x_new[1], marker='^', s=100)
plt.text(x_new[0] + 0.03, x_new[1] + 0.08, "테스트 데이터")

plt.xlabel("x1")
plt.ylabel("x2")
plt.legend()
plt.title("SVM 예측 결과")

plt.show()

슬랙 변수

데이터들의 클래스가 겹쳐있어서 직선인 경계선으로 나누어지지 않는, 즉 선형분리 할 수 없는 경우에 분류를 위해 오차를 허용해야 하는데, 이 때 사용하는 개념이 슬랙변수이다. 슬랙변수는 개별 데이터에 대해 주어지며 항상 0 또는 양수이고, $\xi$ (크사이)로 표현한다.

$$\xi \geq 0 \,\,\,\,\,\,\,\,(i=1,\cdots, N)$$

선형분리할 수 없는 분류데이터에 대해서 원래의 판별함수 조건을 그대로 적용하게 되면 아예 학습이 잘 되지 않거나 오버피팅이 일어날 확률이 높다. 슬랙변수를 사용하면 원래의 판별함수 부등식조건을 데이터 하나하나에 대해 완화해서 적용함으로써 개별적인 오차를 허용할 수 있게 된다.

원래 판별함수 값은 클래스가 +1 인 영역의 샘플 $x_+$ , 클래스가 -1인 영역의 샘플 $x_-$ 에 대해 각각

$$w^Tx_+ - w_0 \geq 1\\ w^Tx_- - w_0 \leq -1$$

의 부등식 조건을 만족해야 했다.

그런데 슬랙변수를 사용하면 아래와 같이 조건을 완화할 수 있게 된다.

$$w^Tx_+ - w_0 \geq 1 - \xi_i\\ w^Tx_- - w_0 \leq -1 + \xi_i$$

즉,

$$y(w^Tx_- - w_0) \leq -1 + \xi_i\\$$

이 된다.

하지만 슬랙변수를 사용하더라도 어쨌든 없던 값을 추가해주는 것이기 때문에 최대한 적게 주고, 작은값으로 주어야 한다.

그러면 최적화목적함수는 다음과 같아진다.

$$L = \dfrac{1}{2}||w||^2 - \sum^N_{i=1}a_i(y_i \cdot (w^Tx_i - w_0) -1 + \xi_i) - \sum^N_{i=1} \mu_i\xi_i+C\sum^N_{i=1}\xi_i$$

• $\mu_i$ : 위 부등식 제한조건에 대한 라그랑주 멀티플라이어.

• C : 슬랙변수의 합이 너무 커지지 않도록 제한하는 변수.

이 식에서 C를 ‘regularization parameter’라고 부르는데, 모델이 학습데이터에만 너무 특화되어 새로운 데이터가 들어왔을 때 예측이 잘못되는 것을 막기 위한 일반화 목적으로 들어가는 일종의 penalty값이라고 생각하면 된다. C값을 크게 주면 슬랙변수 합의 크기가 제한되어 마진이 작아지고, 작게 주면 반대로 마진이 커진다.

C값에 따른 판별함수 경계선을 시각화하면 아래와 같이 달라지는 것을 알 수 있다.