Support Vector Machine; SVM

Support Vector Machine

    - 고차원 데이터 분류에 좋은 성능을 보인다.

    - 퍼셉트론의 확장

    - 최적화 대상은 margin을 최대화하는 것

margin : 클래스를 구분하는 결정 경계와 결정 경계와 가장 가까운 sample사이의 거리로 정의
            이때 해당 sample을 support vector라고 부름

출처 : https://en.wikipedia.org/wiki/Support-vector_machine

선형 SVM

1) 개요

    - 클래스가 다른 데이터들을 large margin으로 분리하는 경계를 찾는 것이다.

    - 즉, 클래스 간의 거리가 최대가 될 수 있도록 하는 것이다.

 

2) 수학적 이해 - w, b를 찾아야한다.

    - 목적식

$$w^{T}x_{pos} + b = 1 \;\;vector\;on\;plus\;plane$$

$$w^{T}(x_{neg}+\lambda w) + b = 1 \;\; (x_{pos} = x_{neg}+\lambda w)$$

$$w^{T}x_{neg} + b + \lambda w^{T}w=1$$

$$-1 + \lambda w^{T}w=1 \;\; (w^{T}x_{neg}+b = -1)$$

$$\lambda = \frac{2}{w^{T}w}$$

$$Margin = distance(x_{pos}, x_{neg})$$

$$=||x_{pos}-x_{neg}||_{2}$$

$$=||(x_{neg}+\lambda w) - x_{neg}||_{2}$$

$$=||\lambda w||_{2}=\lambda \sqrt{w^{T}w}$$

$$=\frac{2}{w^{T}w}\cdot \sqrt{w^{T}w}= \frac{2}{\sqrt{w^{T}w}}$$

$$=\frac{2}{||w||_{2}}$$

L2 norm
$$||W||_{2}=(\sum_{i} |w_{i}|^{2})^{\frac{1}{2}} = \sqrt{w_{1}^{2}+w_{2}^{2} + \cdots +w_{n}^{2}} = \sqrt{W^{T}W}$$

$$max\;Margin = max\frac{2}{||w||_{2}} \Leftrightarrow min\frac{1}{2}||w||_{2}$$

    - 계산의 편의를 위해 제곱을 해준다.

$$\boldsymbol{\frac{1}{2}||w||_{2}^{2}}$$

    - 제약식

    - 아래 제약을 통해 margin이 최소 1 이상인 값을 구한다.

$$w_{0}+w^{T}x^{(i)}\geq 1\;\;y^{(i)}=1\;일\;때$$

$$w_{0}+w^{T}x^{(i)}\leq -1\;\;y^{(i)}=-1\;일\;때$$

$$\boldsymbol{y_{i}(w_{0}+w^{T}x_{i})\geq 1}\;\; \forall i$$

Quadratic programming
- 목적함수는 제곱을 했기 때문에 2차식이고 제약식은 선형이기 때문에 이를 quadratic programming이라 부른다.
- 이는 convex optimization이기 때문에 globally optimal solution이 존재한다.

다음 공식을 적용하여 L2 norm을 사용한 것을 알 수 있다.
$$Ax+By+c=0,\;(x_{0}, y_{0})\;\;d=\frac{Ax_{0}+By_{0}+c=0}{\sqrt{A^{2}+B^{2}}}$$

 

선형 SVM 이상치 처리 (linearly non-separable data)

1) Outlier (이상치 처리)

    - 실전에서 모델을 설계할 때, 모든 데이터가 정확하게 나뉘어 있는 경우는 드물다.

    - 선형 SVM에서는 parameter cost를 조정하여 얼마나 다른 클래스로 분류될 허용치를 결정한다.

    - C의 크기가 작을 수록 많이 허용하고 클수록 적게 허용한다.

    - C가 없으면 hard-margin SVM (separable), 있으면 soft-margin SVM (non-separable)으로 나뉜다.

2) Slack variable

    - 선형 제약 조건을 완화

    - 제약식

$$w_{0}+w^{T}x^{(i)}\geq 1-\xi\;\;y^{(i)}=1\;일\;때$$

$$w_{0}+w^{T}x^{(i)}\leq -1+\xi\;\;y^{(i)}=-1\;일\;때$$

    - 목적식

$$\frac{1}{2}||w||^{2}+C(\sum_{i}\xi^{(i)})$$

 

3) 코드 예시

from sklearn.svm import SVC
svm = SVC(kernel='linear', C=10.0, random_state = 1)
svm.fit(X_train_std, y_train)

 

비선형 SVM

1) 개요

    - 비선형 데이터를 매핑 함수(phi function)를 사용하여 선형적으로 구분되는 고차원 공간에 투영한다.

    - SVM을 고차원의 투영된 공간에서 학습을 진행한다.

 

 

2) 수학적 이해

$$\Phi : x \rightarrow z = \Phi(x)$$

    - SVM Lagrangian dual formulation에서 x를 내적하는 부분이 있는데 이를 아래와 같이 변환한다.

$$x_{i}^{T}x_{j} \rightarrow \Phi(x_{i})^{T}\Phi(x_{j})$$

    - 내적에 사용되는 높은 비용 절감을 위해 커널함수로 정의

$$K(x^{(i)},x^{(j)})=\phi(x^{(i)})^{T}\phi(x^{(j)})$$

kernel function을 사용하면 phi function을 사용했을 때와 동일한 결과지만 계산과정은 더 간단하다.

 

3) Kernel function

    - kernel을 결정하는 뚜렷한 기준이 없어서 데이터 특성에 맞게 선택하는 것이 중요하다.

 

4) RBF; Radial Basis function (방사기저함수, Gaussian kernel)

    - 가장 널리 사용되는 커널 함수 중 하나

    - 매개변수 C와 gamma를 조정해야 하는데 gamma는 가우시안 구의 크기를 제한하는 매개변수이다.

    - gamma가 클수록 support vector의 영향력이 줄어들어 결정경계는 구불구불해진다.

 

5) 코드 예시

svm = SVC(kernel='rbf', random_state = 1, gamma=0.10, C=10.0)
svm.fit(X_xor, y_xor)

 

Logistic vs. SVM

    - Logistic은 SVM보다 이상치에 민감하다. SVM은 결정 경계에 가까운 support vector에 관심을 둔다.

    - Logistic은 간단하고 구현이 쉬우며 업데이트가 용이하다.

from sklearn.linear_model import SGDClassifier
ppn = SGDClassifier(loss = 'perceptron') # perceptron
lr = SGDClassifier(loss = 'log')         # logistic regression
svm = SGDClassifier(loss = 'hinge')		 # SVM

 

---

참고

머신러닝 교과서 with 파이썬, 사이킷런, 텐서플로 (길벗)

비스카이비전 블로그 bskyvision.com/163

고려대 김성범 교수님 유튜브 www.youtube.com/channel/UCueLU1pCvFlM8Y8sth7a6RQ/videos