[ML][Classification] Support Vector Machine(SVM, SVD)

이번 글에서는Binary Classification에서 주로 활용되는 Support Vector Machine에 대해 공부해보고자합니다

 

SVM에 들어가기에 앞서 먼저 알아두고 가야할 것들에 대해 설명하고 시작하도록 하겠습니다 !

 

※ Hyperplane(초평면)

Affine Space(어핀 공간) : 벡터 공간에서의 원점이 없는 공

Vector Space(벡터 공간) : 임의의 점을 잡아도 원점에서 해당 점을 잇는 벡터로 바라보고 있는 벡터를 정의할 수 있는 공간

 

즉, 벡터공간에서는 벡터가 어디에 위치해 있든 크기와 방향만 같다면 모두 같은 벡터로 취급하지만 어핀 공간에서는 벡터에 위치표현을 추가하여 해단 벡터의 크기, 방향 뿐만 아니라 위치까지도 표현할 수 있는 공간이 된다

 

그렇다면 Hyperplane이란?

 

Hyperplane(초평면)이란 p차원의 공간에서 p-1 차원의 평평한 Afifine Space이다

 

예를 들면 3차원 공간에서의 2차원 평면, 2차원 공간에서의 1차원 평면(즉, 선)이라고 할 수 있습니다

 

p차원 공간에서의 Hyperplane은 아래와 같이 정의합니다

$$b + w_1 X_1 + w_2 X_2 + \cdots + w_p X_p = b + <w, X> = 0$$

 

이때 $w = (w_1, w_2, \cdots, w_p)$의 Normal Vector는 Hyperplane에 수직인(Orthogonal) 방향을 의미합니다

 

Seperating Hyperplane(분리초평면)

 

$f(X) = b + w_1 X_1 + w_2 X_2 + \cdots + w_p X_p$에서 $f(X) >0$인 점들과 $f(X)>0$인 점들을 분류합니다

여기서 $y_i$를 labeling하여 $y_i \cdot f(x_i) >0, \; for all i$로 만든다

이 때, $f(X)=0$은 분리초평면을 의미한다

---

그럼 이제 Supprot Vector Machine(SVM)에 대해 알아보도록 하겠습니다

Support Vector Machine(SVM)

SVM은 분류를 위한 기준선을 정의하는 모델입니다

즉, 새로운 데이터가 들어 왔을때 결정 경계를 기준으로 경계의 어느쪽에 속하는지 분류하는 모델입니다

 

일반적으로 Loss Function을 통해 최적의 분류를 하는 다른 Classification Model과 달리 SVM은 Margin이라고 하는 거리를 최대화하는 과정(Maximal Margin Classifier)에서 최적의 분류를 하게 됩니다

분류 과정에서 Margin의 크기를 최대화해야하는데,outlier에 민감하게 반응할 수 있으므로 outlier를 잘 처리하는 것이 중요한 Model입니다.

 

이 때, Outlier를 허용하지 않는 것을 Hard Margin, 어느 정도의 Outlier들을 Margin 안에 포함되는 것을 허용한다면 Sort Margin이라고 합니다

 

SVM의 알고리즘을 알아보기 전 용어 설명 먼저 하도록 하겠습니다

 

결정경계(또는 Hyperplane)

앞서 설명했던 Hyperplane과 같습니다

SVM 목표는 이 Hyperplane을 찾는 것이 목표입니다

그림에서 녹색선으로 표기되어 있습니다

 

Margin

Margin은 결정경계와 데이터 포인트 사이의 거리(그림에서 $M_i$)입니다

SVM이 Margin의 크기를 최대로 하는 결정경계를 찾는 것이 목표입니다

그림에서 Margin(gap)으로 표기해두었습니다

 

Support Vector

하지만 Margin을 계산할 때 모든 데이터 포인트에 대해서 계산하지 않습니다

이 때 임의의 결정경계에 대해 Margin을 계산할 때 영향을 미치는 데이터들만을 Support Vector라고 합니다

그림에 표기해두었습니다

 

정리하자면 SVM은 임의의 결정경계에 대해 Support Vector들을 통해 Margin을 계산하고 이를 최대로 하는

결정경계를 찾아가는 모델입니다

---

알고리즘

그럼 이제 본격적으로 결정경계를 찾아가는 알고리즘을 살펴보도록 하겠습니다

그전에 라그랑주 승수법에 대해 모르시는 분들은 아래 글을 보고 와주시면 됩니다

[ML]라그랑주 승수법(Lagrange Multiplier Method)

 

$$
{\normalsize
\begin{align}
&\underset{b, w_1, \cdots, w_p}{\max}M \tag{1}\\
&subject\;to\; M_i \ge M \; for\;all\;i=1,\;\cdots,\;N\tag{2}\\
&subject\;to\; \frac{y_i(b + w_1x_{i1} + \cdots + w_p x_{ip})}{||w||} \ge M \; for\;all\;i=1,\;\cdots,\;N\tag{3}\\
&subject\;to\; y_i(b + w_1x_{i1} + \cdots + w_p x_{ip}) \ge \hat{M} = M||w|| \; for\;all\;i=1,\;\cdots,\;N\tag{4}\\
\end{align}
}
$$

식 (2)에서 식 (3)은 거리 공식을 통해 구한 $M_i$를 대입하여 도출합니다
식 (3)에서 식 (4)는 $||w||$를 넘겨주어 식을 변환합니다 
이 때, $y_i$는 1 또는 -1 이므로 $y_i(b + w_1x_{i1} + \cdots + w_p x_{ip})$ 이부분에서 절댓값을 없애주어도 양수가 되기때문에 절대값을 제거하여 사용합니다

$$
{\normalsize
\begin{aligned}
&\underset{w, b}{\max} \frac{\hat{M}}{||w||}\\
&subject\;to\; y_i(b + w_1x_{i1} + \cdots + w_p x_{ip}) \ge \hat{M} = M||w|| \; for\;all\;i=1,\;\cdots,\;N\\
\end{aligned}
}
$$

여기서 $\hat{M}$의 크기는 중요하지 않기 때문에 1로 치환하여 식을 바꿔줍니다
왜냐하면 $||w||$의 크기가 상수배로 커지면 그에 따라 $\hat{M}$의 크기도 같은 상수배만큼 커지기 때문입니다

$$
{\normalsize
\begin{aligned}
&\underset{w, b}{\max} \frac{1}{||w||}\\
&subject\;to\; y_i(b + w_1x_{i1} + \cdots + w_p x_{ip}) \ge 1 \; for\;all\;i=1,\;\cdots,\;N\\
\end{aligned}
}
$$

우리는 여태까지 최소화 문제에 대해 풀어왔습니다
따라서, 최대화 문제를 최소화 문제로 변환하고 라그랑주 승수법을 이용해 최적의 해를 찾을것입니다
(분모에 2를 나눠준 것은 나중에 미분을 할 때 계산을 편리하게 하기 위함입니다)

$$
{\normalsize
\begin{aligned}
&\underset{w, b}{\min} \frac{{||w||}^2}{2}\\
&subject\;to\; y_i(b + w_1x_{i1} + \cdots + w_p x_{ip}) \ge 1 \; for\;all\;i=1,\;\cdots,\;N\\
\end{aligned}
}
$$

---

그럼 이제 저희가 풀어야할 문제가 나왔습니다.
이제 이를 라그랑주 승수법을 이용하여 풀어보도록 하겠습니다

$$
{\normalsize
\begin{aligned}
&\underset{w, b}{\min} \frac{{||w||}^2}{2}\\
&subject\;to\; y_i(b + w_1x_{i1} + \cdots + w_p x_{ip}) \ge 1 \; for\;all\;i=1,\;\cdots,\;N\\
\end{aligned}
}$$

 

Primal Problem : $\underset{w, b}{\min} \frac{{||w||}^2}{2}$

Constraint : $subject\;to\; y_i(b + w_1x_{i1} + \cdots + w_p x_{ip}) \ge 1 \; for\;all\;i=1,\;\cdots,\;N$

 

Dual Form : $${\normalsize
\begin{aligned}
&\underset{\lambda}{\max} \underset{w, b}{\min} L(w, b, \lambda _i) = \underset{\lambda}{\max} \Big\{ \underset{w, b}{\min}\frac{||w||^2}{2} - \sum \limits_{i=1}^{N} \lambda_i\{y_i(w \cdot x_i + b) -1\} \Big\}\\
&subject\;to\; \lambda_i \ge 0, \; i=1,\;\cdots\;N
\end{aligned}
}$$

이 때 Stationary Condition에 따라 Primal Problem의 parameter에 대한 편미분 값이 0이 됩니다

$$\frac{\partial L(w,b,\lambda_i)}{\partial w}=0, \quad \frac{\partial L(w, b, \lambda_i)}{\partial b}$$

따라서 식을 정리해보면 아래와 같습니다

$$
\begin{aligned}
&\frac{\partial L(w,b,\lambda_i)}{\partial w} = w_1 + w_2 + \cdots + w_p - \sum \limits_{i=1}^{N} \lambda_i \cdot y_i \cdot x_i = 0 \Rightarrow w = \sum \limits_{i=1}^{N} \lambda_i \cdot y_i \cdot x_i \\
&\frac{\partial L(w, b, \lambda_i)}{\partial b} = - \sum \limits_{i=1}^{N} \lambda_i \cdot y_i = 0 \Rightarrow  \sum \limits_{i=1}^{N} \lambda_i \cdot y_i = 0
\end{aligned}
$$

---

여기서부터 듀얼 문제에 대한 해결입니다

$$
\begin{aligned}
&\underset{\lambda}{\max}\frac{\sum \limits_{i=1}^{N}\lambda_i y_i x_i \cdot \sum \limits_{j=1}^{N}\lambda_j y_j x_j}{2} - \sum \limits_{i=1}^{N} \lambda_i\Big\{y_i(x_i \cdot (\sum \limits_{j=1}^{N} \lambda_j y_j x_j) + b) -1 \Big\}\\
&\Rightarrow \underset{\lambda}{\max} \sum \limits_{i=1}^{N} \lambda_i - \frac{1}{2}\sum \limits_{i=1}^{N} \sum \limits_{j=1}^{N}\lambda_i \lambda_j y_i y_j {x_i}^T x_j\\
&subject\;to\; \lambda_i \ge 0,\; \sum \limits_{i=1}^{N}\lambda_i y_i = 0\quad for\;i = 1,\cdots, N
\end{aligned}
$$

 

여기서 KKT Condition(Complementary Slackness Condtiion)에 따라 아래의 식이 만족되어야 합니다

$$\lambda_i\{y_i(w^T x_i + b) - 1\} = 0, \quad for\; all\; i$$

따라서 $\lambda_i$ 또는 $y_i(w^T x_i +b) - 1$ 둘 중 하나는 반드시 0이어야 합니다

즉, 결정경계에 영향을 미치는 관측치들은 오로지 Support Vector 뿐이라는 결론을 얻게 됩니다(Support Vector라면 $y_i(w^T x_i +b) - 1$가 0, 그렇지 않은 데이터들이라면 라그랑주 승수를 0으로 만든다)

 

$$
\begin{aligned}
&\underset{\lambda}{\max} \sum \limits_{i=1}^{N} \lambda_i - \frac{1}{2}\sum \limits_{i=1}^{N} \sum \limits_{j=1}^{N}\lambda_i \lambda_j y_i y_j {x_i}^T x_j\\
&subject\;to\; \lambda_i \ge 0,\; \sum \limits_{i=1}^{N}\lambda_i y_i = 0\quad for\;i = 1,\cdots, N
\end{aligned}
$$

 

위의 식은 2차 계획법(Quadratic Programming)으로 해결합니다

$\lambda_i$를 통해 w, b를 계산하면 아래와 같은 결과를 얻을 수 있습니다

$$w = \sum \limits_{i=1}^{N} \lambda_i y_i x_i$, $b = \frac{1}{N_{SV}} \sum \limits_{i=1}^{N_{SV}} (y_i - w^T x_i)$$

 

그럼 다음 글에서는 Soft Margin Machine과 Nonlinear SVM에서 다루어보도록 하겠습니다 !