[머신러닝] 5. SVM (Support Vector Machine)

1. SVM이란?
2. 결정 경계 찾기
    2.1. 결정 경계와 서포트 벡터 방정식
    2.2. 마진 측정 방법
    2.3. ||w|| 최소화하기
    2.4. 목적함수 설정하기
    2.5. $\alpha$ 최대화하기
    2.6. 정리
3. 커널트릭
4. 장단점
5. SVM 코드 구현
    5.1. scikit-learn에서의 SVM
    5.2. SVC 커널 실험

1. SVM이란?

SVM은 머신러닝에 사용되는 최적의 결정 경계를 찾는 분류 알고리즘입니다.

위 그림과 같이 데이터를 분류할 수 있는 최적의 결정 경계를 찾는 것이 SVM의 목표입니다. 이를 위해선 최적의 서포트 벡터를 찾아야 합니다. 서포트 벡터란, 두 분류 데이터의 경계를 가장 잘 나타낼 수 있는 데이터로, 서로 평행한 2개의 벡터를 선정하게 됩니다.

 

최적의 서포트 벡터를 판단하는 기준은 두 서포트 벡터 사이의 거리인 '마진'이 최대화 되는 서포트 벡터를 찾는 것입니다. 이 마진 내부에는 다른 어떤 데이터도 포함되어서는 안됩니다.

 

결정 경계는 두 서포트 벡터의 가운데 지점으로 결정되며, 이를 기준으로 데이터를 분류할 수 있게 되는 것입니다.

 

즉, SVM은 '마진'을 최대화하는 최적의 서포트 벡터 두 개를 찾는 알고리즘이라고 할 수 있습니다. 그럼 지금부터 SVM의 작동원리에 대해 자세히 알아 보도록 하겠습니다. 내용이 너무 길면 2.6. 정리 부분만 봐도 됩니다.

2. 결정 경계 찾기

2.1. 결정 경계와 서포트 벡터 방정식

결정 경계는 결국엔 선형 함수의 형태로 나타납니다. 따라서 결정 경계는 아래와 같은 선형 함수로 나타낼 수 있습니다.

$$wx+b=0$$

2개의 서포트 벡터는 결정 경계를 기준으로 평행한 2개의 선형 함수로 구성됩니다. 따라서 2개의 서포트 벡터는 아래와 같이 쓸 수 있습니다.

$$wx+b_1=1$$

$$wx+b_2=-1$$

2.2. 마진 측정 방법

한 점 $x$와 결정 경계 $wx+b$ 사이의 거리 $d$는 아래와 같은 공식을 이용해 계산할 수 있습니다.

$$d={|wx+b|\over||w||}$$

따라서 2개의 서포트 벡터 사이의 거리 마진은 아래와 같이 계산할 수 있습니다.

$$margin={\text{support_vector1}-\text{support_vector2}\over||w||}={|1-(-1)|\over||w||}={2\over||w||}$$

그렇다면, 이 마진을 최대화하려면 어떻게 해야할까요? 정답은 분모인 $||w||$를 최소화하는 것입니다. 그럼 지금부터 $||w||$를 최소화하는 방법을 찾아봅시다.

2.3. ||w|| 최소화하기

$||w||$를 최소화하는 서포트 벡터의 파라미터 ($w$, $b_1$, $b_2$)를 찾아야 합니다.

우선 계산의 편의성을 위해 $||w||$ 대신 아래 수식을 최소화할 겁니다.

$$\text{min}_{w,b}{1\over2}||w||^2$$

이유는 $||w||$를 최소화하는 파라미터를 찾기 위해 미분을 활용할 것이기 때문입니다. ${1\over2}||w||^2$을 미분하면 $||w||$가 되기 때문에 최적화 계산이 편리해집니다. 또한 $||w||$와 ${1\over2}||w||^2$는 서로 어차피 비례 관계이기 때문에 저 수식을 최소화하는 것도 $||w||$를 최소화하는 것과 똑같습니다.

 

또한 위 수식을 최소화하면서도, 모든 데이터 $(x_i,y_i)$에 대하여 아래 조건을 만족해야 합니다.

$$y_i(wx_i+b)\geq1$$

즉, 위 조건을 만족하면서 ${1\over2}||w||^2$을 최소화하는 목적함수를 설정하는 것이 필요합니다.

위 조건을 만족해야 하는 이유는 아래 3개의 전제를 보면 알 수 있습니다.

• Case1 : $y_i(wx_i+b)-1<0$
  • 이는 데이터 $x_i$가 마진 내부에 포함된 경우입니다.
  • 마진 내부에는 다른 어떤 데이터도 포함되면 안되기 때문에 $y_i(wx_i+b)-1=0$을 만족하는 다른 데이터를 찾아야 합니다.
  • 따라서 이 경우엔 잘못된 서포트 벡터를 선정한 것이므로 목적함수에 penalty를 적용시켜 이런 데이터가 발생하지 않도록 해야 합니다.
• Case2 : $y_i(wx_i+b)-1>0$
  • 이는 데이터가 마진 내부에 포함되지 않는 경우입니다.
  • 이 데이터는 서포트 벡터에 전혀 관여하지 않기 때문에 목적함수에 포함하지 않도록 합니다.
• Case3 : $y_i(wx_i+b)-1=0$
  • $x_i$가 서포트 벡터인 경우입니다.

최종적으로 모든 데이터 $(x_i,y_i)$에 대하여 Case1을 만족하지 않아야 하고, Case2와 Case3의 경우만 존재해야 하므로 $y_i(wx_i+b)\geq1$을 만족해야 하는 것입니다.

2.4. 목적함수 설정하기

그렇다면 목적함수를 어떻게 설정하는 것이 좋을까요? 저희가 해결해야 하는 것은 '제약 조건이 있는 최적화 문제'를 푸는 것입니다. 이런 경우에 사용할 수 있는 목적함수로는 '라그랑주 함수'가 있습니다.$$L(w,b,\alpha)={1\over2}||w||^2-\sum^n_{i=1}\alpha_i[y_i(wx_i+b)-1]$$앞 항 ${1\over2}||w||^2$은 최소화해야하는 대상이며, 뒷 부분은 제약 조건입니다.

 

위 수식을 최소화하기 위해선 $\alpha_i$를 최대화해야 합니다. $\alpha_i$를 최대화하기 위해 앞서 살펴 본 3가지 케이스를 다시 살펴 보겠습니다.

• Case1 ($y_i(wx_i+b)-1<0$) : 데이터가 마진 내부에 포함된 경우로 더 최적의 서포트 벡터를 찾아야 합니다. 따라서 라그랑주 함수의 값을 더 줄일 수 있도록 $\alpha_i>0$이 되도록 하여 라그랑주 함수가 더 작아질 수 있도록 해야 합니다.
• Case2 ($y_i(wx_i+b)-1>0$) : 데이터가 마진 외부에 있는 경우로 서포트 벡터와 관련이 없는 데이터입니다. 이 경우 $\alpha_i$는 0이 되어 라그랑주 함수에 영향을 미치지 않도록 합니다.
• Case3 ($y_i(wx_i+b)-1=0$) : 서포트 벡터인 경우로 $\alpha_i$의 값과 관계없이 제약 항이 0이 됩니다.

위 3가지 케이스를 종합하면 $\alpha_i\geq0$이 되어야 한다는 것을 알 수 있습니다.

2.5. $\alpha$ 최대화하기

$\alpha$를 최대화하기 위한 방법은 아래와 같은 이중문제(daul problem)로 변환할 수 있다고 합니다.$$\underset{\alpha}{\text{max}}\sum^n_{i=1}\alpha_i-{1\over2}\sum^n_{i=1}\sum^n_{j=1}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)$$뒷 항 ${1\over2}\sum^n_{i=1}\sum^n_{j=1}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)$는 $\alpha$가 너무 커지지 않도록 하여 모델을 안정화하는 역할을 합니다. 또한 이중문제가 최대한 커지려면 이 항이 최대한 작아져야 하기도 합니다.

 

최적의 서포트 벡터를 찾았다면, 모든 데이터는 서포트 벡터이거나, 마진 밖의 데이터가 될 것입니다. 따라서 위 이중문제가 최적화된다면, 대부분의 $\alpha_i$는 0이 되고(마진 밖에 위치한 데이터들을 무시.), 서포트 벡터에 대해서만 $\alpha_i$가 0보다 큰 값을 갖게 될겁니다.

 

위 수식을 최대화하는 방법을 찾는 것은 gradient descent와 같이 미분을 이용할 수 있습니다. 위 이중문제의 $\alpha$에 대한 미분값이 0이라는 것은, 이중문제 함수의 기울기가 0이라는 뜻으로 최댓값에 도달했다는 것을 나타냅니다. 

따라서 이중문제의 $\alpha$에 대한 미분값이 0이 되는 $\alpha$를 찾으면 됩니다.$${\delta\over\delta\alpha_i}(\sum^n_{i=1}\alpha_i-{1\over2}\sum^n_{i=1}\sum^n_{j=1}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j))=1-\sum^n_{j=1}\alpha_jy_iy_j(x_i\cdot x_j)=0$$

 

위 수식을 이용해 최적의 $\alpha$를 계산한 뒤, 파라미터 $w$와 $b$도 $\alpha$를 이용해 계산할 수 있습니다.

• $w$
  $${\delta L(w,b,a)\over \delta w}=w-\sum^n_{i=1}\alpha_iy_ix_i=0$$
  $$\therefore w=\sum^n_{i=1}\alpha_iy_ix_i$$
• $b$
  최적화되었기 때문에 서포트 벡터들만 고려하면 됩니다. 서포트 벡터의 수식을 이용하면,
  $y_i(wx_i+b)=1, wx_i+b={1\over y_i}, b={1\over y_i}-wx_i$
  위와 같이 유도할 수 있습니다. 이 때 $y_i$는 1 또는 -1이므로,
  $b=y_i-wx_i$로 구할 수 있습니다.

이렇게 하여 최종적으로 최적의 결정 경계를 계산할 수 있게 됩니다.

2.6. 정리

내용이 꽤나 길었기 때문에 SVM의 최적화 과정을 간단하게 정리해 보겠습니다.

1. SVM은 최적의 결정 경계를 찾는 방법이다.
2. 최적의 결정 경계를 찾기 위해선 마진을 최대화해야 한다.
   $$\text{margin}={2\over||w||}$$
3. 마진을 최대화하기 위해선 $||w||$를 최소화해야 한다.
4. $||w||$를 최소화하는 동시에, 모든 데이터 $(x_i,y_i)$에 대해 아래 조건도 만족해야 합니다.
   $$y_i(wx_i+b)\geq1$$
   
5. 이를 해결하기 위해 라그랑주 함수를 이용합니다.
   $$L(w,b,\alpha)={1\over2}||w||^2-\sum^n_{i=1}\alpha_i[y_i(wx_i+b)-1]$$
   
6. 라그랑주 함수를 최소화하기 위해선 $\alpha$를 최대화해야 합니다. $\alpha$를 최대화하기 위해 아래와 같은 이중 문제 형태로 변환할 수 있습니다.
   $$\underset{\alpha}{\text{max}}\sum^n_{i=1}\alpha_i-{1\over2}\sum^n_{i=1}\sum^n_{j=1}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)$$
   
7. 위 이중문제의 $\alpha$에 대한 미분값이 0이 될 때, 최적의 $\alpha$를 찾게 되며, 이 경우 대부분의 $\alpha_i$는 0을 갖게 됩니다.(마진 외부의 데이터) $\alpha_i>0$인 경우엔 $x_i$가 서포트 벡터임을 의미합니다.
8. 이렇게 최적의 $\alpha$를 찾으면, 이를 이용해 결정 경계의 파라미터를 계산할 수 있으며, 최종적으로 마진이 최대화되는 이상적인 결정 경계를 찾을 수 있게 됩니다.

3. 커널트릭

SVM은 훌륭한 방법이지만, 한계도 존재합니다. 아래와 같이 SVM이 힘을 발휘하기 힘든 경우가 있기 때문입니다.

1. 데이터의 선형 분리가 어려운 경우
2. 입력 feature의 수가 많아 고차원 공간으로의 매핑이 필요한 경우.

위와 같이 선형적으로 분리하기 어려운 경우엔 데이터를 고차원 공간으로 매핑하여 해결이 가능합니다.

$$x\rightarrow\phi(x)$$

하지만 SVM을 계산하는 과정에 있는 이중문제에서 두 데이터 포인트 간의 내적 계산이 포함되는데, 여기에 고차원 매핑까지 할 경우, 계산량이 크게 늘어난다는 문제가 발생합니다.

$$\underset{\alpha}{\text{max}}\sum^n_{i=1}\alpha_i-{1\over2}\sum^n_{i=1}\sum^n_{j=1}\alpha_i\alpha_jy_iy_j(\phi(x_i)\cdot\phi(x_j))$$

따라서 계산량을 줄이기 위해 '커널 트릭'을 사용합니다. 커널 트릭을 사용하면 "고차원 매핑+내적" 2가지 계산을 한 번의 계산으로 간단히 줄일 수 있게 됩니다.

$$K(x_i,x_j)=\phi(x_i)\cdot\phi(x_j)$$

 

scikit-learn에서 제공하는 kernel 종류들에 대해 간단히 살펴보겠습니다.

 

1. Linear kernel : 데이터가 이미 선형적으로 분리가 가능해 고차원 매핑이 필요없는 경우에 사용됩니다.
   $K(x_i,x_j)=x_i\cdot x_j$
2. Polinomial Kernel : 고차원 다항식으로 매핑하는 커널로 차원 조절이 가능합니다.
   $K(x_i,x_j)=(\gamma x_i\cdot x_j+\gamma)^d$
   $d$ : degree
   $r$ : coef0
3. RBF Kernel : 일반적으로 성능이 가장 잘 나오는 커널입니다.
   $K(x_i,x_j)=\text{exp}(-\gamma||x_i-x_j||^2)$
   $\gamma$ : gamma
4. Sigmoid Kernel : 딥러닝 신경망처럼 작동하는 커널입니다.
   $K(x_i,x_j)=\text{tanh}(\gamma x_i\cdot x_j+r)$
   $r$ : coef0

4. 장단점

장점

• 커널 트릭으로 인해 고차원 데이터에서 강력합니다.
• 선형 문제와 비선형 문제 모두 처리 가능합니다.
• 과적합 위험이 낮습니다.

단점

• 큰 데이터셋에서 학습 속도가 느립니다.
• 커널, 하이퍼파라미터 선택이 까다롭습니다.
• 고차원 데이터에서 해석이 어렵습니다.

5. SVM 코드 구현

5.1. scikit-learn에서의 SVM

scikit-learn에서는 SVM이라는 이름으로 제공하지 않고, 분류 문제에는 SVC를, 회귀 문제에는 SVR을 사용하고 있습니다.

SVC : https://scikit-learn.org/dev/modules/generated/sklearn.svm.SVC.html

SVR : https://scikit-learn.org/1.5/modules/generated/sklearn.svm.SVR.html

from sklearn.svm import SVC, SVR

clf = SVC(
    kernel='rbf',
    gamma='scale',
    coef0=0.0
)

clf.fit(x_train, y_train)

5.2.  SVC 커널 실험

https://colab.research.google.com/drive/1XciV21ts7fnzuUyUaBVrq45G8O72PIgS?usp=sharing

SVC.ipynb

 

아래 4개의 데이터셋에 대해 4개의 커널을 실험해 보도록 하겠습니다.

1. iris : 3개의 꽃잎 특성을 보고 3개의 꽃으로 분류하는 문제. 총 150개의 데이터 샘플.
2. breast cancer : 30개의 신체 특성을 바탕으로 유방암 여부를 판별하는 문제. 총 569개의 데이터 샘플.
3. digits : 8*8 크기의 이미지를 보고 0~9 까지의 숫자 중 하나로 분류하는 문제. 총 1797개의 데이터 샘플.
4. bigdata : make_classification 메소드를 통해 128개의 입력 특성을 갖고, 5개의 클래스로 분류하는 문제를 만듦. 총 20000개의 샘플.

bigdata_x, bigdata_y = make_classification(n_samples=20000, n_features=128, n_informative=30, n_classes=5)

실험 결과는 위와 같이 나타났습니다.

iris, breast cancer, digits 데이터셋에서는 4개의 kernel 모두 대체로 비슷한 성능을 보였습니다. 다만 polynomial kernel과 sigmoid kernel의 성능이 조금 떨어지는 것을 볼 수 있었습니다.

좀 더 고차원의 데이터인 bigdata 에서는 kernel 간의 성능 차이가 확연히 벌어졌습니다. 특히 rbf kernel이 독보적인 성능을 보였으며, 커널 트릭을 사용하지 않는 linear kernel의 경우 성능이 크게 떨어지는 것을 알 수 있었습니다.

 

결과는 coef0나 gamma와 같은 별도의 파라미터를 조정하지 않은 결과로, 파라미터 조정에 따라 결과가 달라질 수 있습니다. 하지만 다른 kernel을 적용하는 것이 모델의 성능에 분명히 영향을 미친다는 것은 확실히 알 수 있으며, 대체로 'rbf kernel'의 성능이 안정적으로 잘 나온다는 것도 알 수 있었습니다.

 

1. KNN : https://all-the-meaning.tistory.com/65
2. Decision Tree : https://all-the-meaning.tistory.com/69
3. Random Forest : https://all-the-meaning.tistory.com/70
4. Linear/Logistic Regression : https://all-the-meaning.tistory.com/71
6. 머신러닝 총정리 : https://all-the-meaning.tistory.com/73