[LGAimers] Support Vector Machine(SVM)

본 내용은 Module 4 이화여자대학교 강제원 교수님의 강의 내용을 요약한 것입니다

Robustness와 SVM

SVM의 필요성

기존의 Linear classification을 보면, 2 Class를 구분하는 hyperplane은 다양하게 나올 수 있다. 

위의 그림을 보면, w1, w2, w3가 모두 가능하다. 

하지만, robust 관점에서 3 solution 중 w2가 가장 좋음은 자명하다. 

우측그림을 보면 w3의 경우 new data에 대해 잘못 판정하는 예시를 보여준다.

Support Vector Machine(SVM)

SVM은 Robustness 관점에서 가장 좋은 Hyperplane을 선택하기 위해 Margine과 Support Vector라는 개념을 도입한다. 

간단히 예기하면 SVM의 목적은 Margin을 최대화 하는 것이다. 

support vector는 가장 sensible한 데이터의 집합으로 Hyperplane과 가장 가까운 element의 집합이다. 각 class 별로 개별로 정의된다. 

Margin:  support vector와 hyperplane간 거리

how to get margin

support vector와 h의 거리 를 Margin이라고 한다.

Margin은 hyperplane의 식을 $h(x) = w^Tx + b$라 하자. 

이때 그러면 +1 Class에 속한 x들에 관해서는 $w^TX + b > 1$

-1 Class에 관해서는 $w^TX + b < -1$ 이라고 할 수 있다(등호 생략)

추가적으로 +1 Class에 속하는 $x^+$와 -1 Class에 속하는 $x^-$와의 관계는 평행이동 관계이다.

즉,  $x^{+}=x^{-}+\lambda w$이다. 

 

이를 이용하면

 

$\lambda$ 구하기 

$$
\begin{aligned}
& w^T x^{+}+b=1 \\
& \Rightarrow w^T\left(x^{-}+\lambda w\right)+b=1 \\
& \Rightarrow w^T x^{-}+b+\lambda w^T w= \\
& w^T x^{-}+b=-1 \\
& \Rightarrow-1+\lambda w^T w=1 \\
& \lambda=\frac{2}{w^T w}
\end{aligned}
$$

 

Margin 식 

$$
\begin{aligned}
& \text { Margin } \\
& =\operatorname{distance}\left(x^{+}, x^{-}\right) \\
& =\left\|x^{+}-x^{-}\right\|_2 \\
& =\left\|x^{-}+\lambda w-x^{-}\right\|_2 \\
& =\|\lambda w\|_2 \\
& =\lambda \sqrt{w^T w} \\
& =\frac{2}{\sqrt{w^T w}} \\
& =\frac{2}{||w||} \\
&
\end{aligned}
$$

 

그럼 우리는 최종적으로 아래의 optimize 문제를 푸는 것과 같다. 

 

이때 quadaratic form의 convexity가 보장됨으로 이를 제곱형태로 변형하여 푼다. 

이때의 optimize문제는 Lagrangian multiplier을 이용한 constrained optimizaiton 문제임으로 아래와 같이 풀 수 있다. 

우선 Lagrangian으로 표현하면

이고 제약조건은 위에 나온 것과 같이 모든 데이터에 관해 거리가 양수이거나 0이 되도록 해야한다(y가 음수인 경우에도 음수끼리의 곱이라 양수다)

 

따라서 우리는 아래의 KKT조건에 대한 문제를 풀면 된다.

Linearly Seprable & Soft Margin

위에서의 문제는 Hard Margin이면서 Linearly Seperable한 문제였다. 즉, 어떠한 Dataset도 Magin 내부에 존재하지 않는 Strict한 조건이었다. 

SoftMargin에서는 직선만으로는 분류하기 어려움으로 약간의 Error를 허용하는 정규화식을 추가한다. 

Nonlinear transform & kernel trick : SVM의 linear하지 않은 영역에 대해서도 풀 수 있rp

NonLienar한 경우에는 kernel을 이용해서 고차원의 sample로 mapping하는 함수를 이용가능한데, 이때 Kernel은 Data를 linearly separable하게 만들어준다. 아래의 대표적인 Kernel들이 존재한다.

 

 

For NonLinear Problem: ANN & DNN

 

추가적으로 선형으로 분해하지 못하는 문제들에 관해서는 Nonlinear하게 Classify하는 것도 가능하다. 

이는 ANN을 이용한다. 

ANN의 경우에는 활성화함수를 비선형으로 사용함으로서 선형으로만 표현되는 식을 비선형으로 표현되게 만들었다. 

흔히 우리가 말하는 DNN문제가 이에 해당한다.