SVM에 대한 이야기를 해보겠다. 강의내용은 되게 러프해서 내가 이전에 정리해둔 글과 같이 조금 자세하게 정리해보겠다.# SVM-BASE

SVM이란 Support Vector Machine의 약자이다.
SVM은 Classification을 위한 ML Algorithm의 하나인데, 여백(Margin)을 이용하여 일반화 능력을 향상시킨다.

왜냐하면 기존의 Classification은 경계선과 데이터간의 관계를 고려하지 않았는데, SVM은 이 두개의 관계를 고려했기 때문이다. SVM에서는 경계선이 Test Data를 잘 구분 해주더라도, 조금 더 학습을 진행시켜 경계선이 Train Data로부터 멀리 떨어지도록 만든다(여백을 증가시킨다).

북한과 남한의 경계를 가를 때 딱 붙여서 갈랐다면 안 좋은 일이 생겼을 것이다. 두 개의 경계를 잘 가르기 위해서는 중간에 DMZ라고 하는 완충지대가 필요하다. DMZ를 SVM에서 말하고 있는 여백이라고 비유해볼 수 있다.

SVM은 비록 DL에 밀려 시들하지만 수학적으로 봤을 때 아름답기 때문에 ML을 공부한다면 알아볼 필요가 있다.

SVM은 NN과 비교했을 때 훨씬 더 다루기 쉽고 우리가 완전히 정복한 이론이다. 이 것을 이해한다면 생각의 폭이 더 넓어질 것이다.

알아야 하는 선형대수 지식

먼저 알아야 하는 선형대수 지식이 있다.
선형대수에서 직선의 방정식을 벡터의 내적형태로 표현할 수 있다.

$w=\begin{bmatrix} a\\b\end{bmatrix},\underline d=\begin{bmatrix}x\\y\end{bmatrix}$

$ax+by=\begin{bmatrix} a&b\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix} =\underline w^{\intercal}\underline d=c$

이렇게 내적의 형태로 표현하면 훨씬 더 간단하게 표현할 수 있다.

그리고 $\underline w^\intercal \underline d = c$는 우리가 $\lVert \underline w\rVert\lVert \underline d\rVert cos\theta=c$ 로 표현할 수 있다.

여기서 식을 변형해 다음과 같이 살펴보자.$\lVert \underline d\rVert cos\theta=\dfrac {c}{\lVert \underline w\rVert}$
여기서 우변을 하나의 상수처럼 취급할 수 있다.
만약에 $\lVert \underline w \rVert$가 1이라고 둔다면 ($\underline w$ 는 법선벡터이므로, 크기는 중요하지 않다. )

$\lVert \underline d\rVert cos\theta= {c}$

이렇게 되는데

이때 $d$의 자취를 그려보면, $w$ 벡터에 정사영 했을 때 그 크기가 $c$ 인 벡터들의 모임이므로,

다음과 같이 빨간 직선이 $\underline d$의 자취로 그려진다. 그리고 이것이 곧 직선의 방정식이 된다.$\lVert \underline d\rVert cos\theta=\dfrac {c}{\lVert \underline w\rVert}$

즉 우리가 이 식의 그래프를 우변을 만족하는 $\underline d$의 자취로도 해석할 수 있다.
만약에 어떤 점이 이 직선보다 위에 있다면 어떨까?

위 식의 $\underline d$ 대신에 그 점을 집어넣으면 된다. 그리고 그렇게 한다면
위 식의 좌변은 우변보다 커지게 될 것이다.

만약 아래에 있다면 좌변은 우변보다 작아지게 될 것이다.

점 A는 직선보다 위에 있고 점 B는 직선보다 아래에 있다.

$\lVert \underline w\rVert$가 1일때
점 A에 해당하는 벡터를 $w$에 정사영 시킨다면 그 값은 $c$ 보다 커지게 된다.

$\lVert \underline \Alpha \rVert cos\theta\ > \dfrac {c}{\lVert \underline w\rVert}=c$
점 B에 해당하는 벡터를 $w$에 정사영 시킨다면 그 값은 $c$ 보다 작아지게 된다.

$\lVert \underline \Beta \rVert cos\theta<\dfrac {c}{\lVert \underline w\rVert}=c$

$\lVert \underline w\rVert$가 1이 아닌 경우로 일반화하고 싶으면 $c$를 $\dfrac c {\lVert \underline w \rVert}$으로 변경하면 된다.

이제 이 그림을 이해해보자, 굵은 빨간 기준 경계선이 있고, 위 아래로 같은 거리에 빨간 점선이 두가지 있다.

위 빨간 점선에 해당하는 식은 다음과 같이 쓸 수 있다. 우리는 $\underline w$의 값을 자유롭게 조정할 수 있으므로, 분자에 어떤 값이 더해지든 큰 상관은 없다. 하지만 편의성을 위해 1을 더한다.

$\lVert \underline d\rVert cos\theta=\dfrac {c+1}{\lVert \underline w\rVert}$

$\lVert \underline d\rVert cos\theta=\dfrac {c}{\lVert \underline w\rVert}$ 보다 $\underline w$ 에 정사영을 내렸을 때 그 값이 더 큰 벡터들의 자취로 볼 수 있다.

아래 빨간 점선에 해댱하는 식은 다음과 같이 쓸 수 있다.

$\lVert \underline d\rVert cos\theta=\dfrac {c-1}{\lVert \underline w\rVert}$

그리고 이 식도 마찬가지로, $\underline w$에 정사영을 내렸을 때 그 값이 더 작은 벡터들의 자취로 볼 수 있다.

굵은 선에 비해 같은 양이 커지고 작아졌으므로, 이 직선들 간의 간격은 같다.

그리고 이 두 점선 사이의 거리는 우변끼리 빼주면 $\dfrac {2}{\lVert \underline w\rVert}$ 다음과 같이 쓸 수 있다.

SVM에서 margin을 말할 때 $\dfrac {2}{\lVert \underline w\rVert}$를 사용하게 된다. 이것을 잘 보자.

SVM LINEAR

선형 분리 가능한 문제에 대해서 먼저 생각해보자.

SVM의 단계는 다음과 같다.

1. 데이터를 오류없이 분류하도록 $\underline w$ 정한다.
2. 정해진 직선의 방향$\underline w$에 대해, 직선으로부터 가장 가까운 샘플까지의
   거리가 같게 되도록 바이어스 $c$를 정한다.

위 그림에서 직선과 가장 가까운 빨간색 샘플까지의 거리와 직선과 가장 가까운 파란색 샘플까지의 거리가 같도록 직선을 결정하면 된다.

여기서 이 초록색 띠의 너비 $(2s)$를 마진이라고 부른다.
SVM은 여기서 이 마진의 크기를 최대로 하는 결정 초평면을 구하는 알고리즘이다.

그리고 이전 시간에 margin을 $\dfrac 2 {\lVert \underline w\rVert}$으로 나타낼 수 있음을 배웠다.

마진을 최대화 하는 것이 우리의 목표이다. 그런데 마진을 최대화 하는 것은

$\lVert \underline w\rVert$를 최소화 하는 것과 같고, 이것을 최소화 하는 것은

$\dfrac 1 2\lVert \underline w\rVert^2$를 최소화 하는 것과 같다. 이렇게 쓰는 이유는 단순히 계산상의 편의 때문이다.

우리는 마진을 최소화 하는 것도 중요하지만, 샘플들이 잘 분류되도록 하는 것도 중요하다.

위 그림에서 왼쪽 점선띠$(c+1)$ 위에 있는 샘플들은 1로 분류하고
오른쪽 점선띠$(c-1)$ 아래에 있는 샘플들은 -1로 분류해야한다.
이 것을 다음 식으로 표현할 수 있다.

훈련 집합을 $\{(\underline x_1,y_1)\cdots(\underline x_n,y_n)\}$ 으로 표현한다면,

$\underline w^\intercal \underline x_i \geq c+1 \ ,\forall y_i=1$ ← $d(\underline x_i) \geq 1\ \forall y_i=1$

$\underline w^\intercal \underline x_i \leq c-1 \ ,\forall y_i=-1$ ← $d(\underline x_i) \leq -1\ \forall y_i=-1$

이 식을 만족시켜야 한다. 이 식의 의미는,
$\underline w^\intercal \underline x_i \geq c+1 \ ,\forall y_i=1$ 를 만족시키는 모든 $\underline x_i$에 대해서,
그에 해당하는 $y_i$를 1로 분류해줘야 한다는 뜻이다.
다른 식도 마찬가지로 해당 식에 대해서 $y_i$를 -1로 분류해주라는 뜻이다.

식을 바꿔주면

$\underline w^\intercal \underline x_i -c -1 \geq 0 \ ,\forall y_i=1$

$\underline w^\intercal \underline x_i -c+1 \leq 0 \ ,\forall y_i=-1$ 로 바꿔줄 수 있다.

이것을 간단하게 바꿔주면 다음과 같은 식으로 쓸 수 있다.

$y_i(\underline w^\intercal \underline x_i -c)$ 는 항상 양수이므로, (음수 곱하기 음수 또는 양수 곱하기 양수 이므로)

$y_i(\underline w^\intercal \underline x_i -c)-1 \geq 0 $ 를 만족시키도록 하면 된다.

즉 우리는 문제를 다음과 같이 쓸 수 있다.

$Minimize: J(w)=\dfrac 1 2 \lVert\underline w\rVert ^2$
$Subject \ to: y_i(\underline w^\intercal \underline x_i -c)-1 \geq 0 , i=1,2,3,4,5,\cdots n$
$or$
$Subject \ to: y_i(c- \underline w^\intercal\underline x_i)+1 \leq 0 , i=1,2,3,4,5,\cdots n$

Meaning of Support Vector

서포트 벡터의 의미가 무엇인가?
그것은 경계선에 있는 점들의 위치벡터를 의미한다.

즉 $y_i(\underline w^\intercal \underline x_i -c)-1 = 0$ 을 만족하는 $\underline x_i$벡터들을 의미한다.

(a.k.a $\underline w^\intercal \underline x_i -c -1 = 0$ 혹은$\underline w^\intercal \underline x_i -c+1 = 0$ 를 만족시키는 Vector $\underline x_i$)

Lagrangian in SVM

위 Problem을 라그랑지안을 통해서 표현할 수 있다.

$f(\underline x)$를 최소화하면서 $\underline g(\underline x)\leq0$ 을 만족하는 문제를 풀 때,

라그랑지안을 $L(\underline x,\underline \lambda)=f(\underline x)+\underline \mu g(\underline x)$ 로 쓸 수 있다.

$f(\underline x)$를 최소화하면서 $\underline g(\underline x)\geq0$ 을 만족하는 문제를 풀 때는

$L(\underline x,\underline \lambda)=f(\underline x)-\underline \mu g(\underline x)$ 이렇게 쓴다. 이번에는 이걸로 아래에 notation 해보겠다.

이를 SVM에 적용하면 ($\mu$ 를 $\alpha$로 표현) ($c$를 $b$로 표현)

$L(\underline w, b, \underline \alpha) = \dfrac 12 \lVert w\rVert^2-\displaystyle\sum_{i=1}^n \alpha_i(y_i(\underline w^\intercal \underline x_i -b)-1)$ 와 같이 쓸 수 있다.

그리고 이 라그랑지안 문제를 풀면 된다.
푸는 첫번째 방식은 KKT를 사용해 그라디언트가 0이 되도록하는 것을 구해서 연립하는 것이다.

$\dfrac {\partial L(\underline w, b, \underline \alpha)} {\partial \underline w}= 0$ $\Rightarrow$$\underline w = \displaystyle\sum_{i=1}^n\alpha_iy_i\underline x_i$

$\dfrac {\partial L(\underline w, b, \underline \alpha)} {\partial b}= 0$$\Rightarrow$$\displaystyle\sum_{i=1}^n\alpha_iy_i = 0$

$\dfrac {\partial L(\underline w, b, \underline \alpha)} {\partial \underline \alpha}= 0$$\Rightarrow$$\displaystyle\sum_{i-1}^n(y_i(\underline w^\intercal \underline x_i -b)-1)=0$

$\alpha_i \geq 0$

두번째 방법은 Dual Problem을 이용하는 것이다.$\nabla_{\underline w,b} L$을 이용하여 $\underset {\underline w,b}{argmin L}$ 을 찾은 후

$\nabla q(\underline \alpha)$를 통해 $\underset {\underline \alpha}{argmax q}$ 를 찾는다.

첫번째를 풀면

$\underline w = \displaystyle\sum_{i=1}^n\alpha_iy_i\underline x_i$

$\displaystyle\sum_{i=1}^n\alpha_iy_i = 0$ 이 두가지 식이 나온다.

그리고 $\underline w = \displaystyle\sum_{i=1}^n\alpha_iy_i\underline x_i$를 원래 식 $L$에 대입하면

$q(\underline \alpha) =\dfrac 12 \lVert \displaystyle\sum_{i=1}^n\alpha_iy_i\underline x_i\rVert^2-\displaystyle\sum_{i=1}^n \alpha_i(y_i(\underline (\displaystyle\sum_{j=1}^n\alpha_jy_j\underline x_j)^\intercal \underline x_j -b)-1)$이 나오고 정리하면

$q(\underline \alpha) =\dfrac 12 \displaystyle\sum_{i=1}^n\sum_{j=1}^na_ia_jy_iy_j\underline x_i^\intercal \underline x_j-\displaystyle\sum_{i=1}^n\sum_{j=1}^na_ia_jy_iy_j\underline x_i^\intercal \underline x_j+\displaystyle\sum_{i=1}^na_iy_ib+\displaystyle\sum_{i=1}^n\alpha_i$ 이다.

여기에 $\displaystyle\sum_{i=1}^n\alpha_iy_i = 0$ 이므로 대입하면 b를 없앨 수 있다.

$q(\underline \alpha) =\displaystyle\sum_{i=1}^n\alpha_i-\dfrac 12 \displaystyle\sum_{i=1}^n\sum_{j=1}^na_ia_jy_iy_j\underline x_i^\intercal \underline x_j$ 이렇게 쓸 수 있다.

여기서 문제를 다음과 같이 간단하게 할 수 있다.

$\displaystyle\sum_{i=1}^n\alpha_iy_i = 0$를 만족하고,

$\alpha_i\geq0 \ i=1,2,3,4,5$ 를만족하면서,

$q(\underline \alpha) =\displaystyle\sum_{i=1}^n\alpha_i-\dfrac 12 \displaystyle\sum_{i=1}^n\sum_{j=1}^na_ia_jy_iy_j\underline x_i^\intercal \underline x_j$ 를 최대화 시켜라.

SVM SOFT MARGIN

지금까지 우리가 배운 SVM은 HARD MARGIN SVM이다.
여백 안에 있는 data에 대해서 오차를 허용해 주지 않는 SVM을 뜻한다.
여기서 다음 데이터를 어떻게 잘 구분할 수 있을까?

기존의 SVM 방법으로는 이 데이터를 잘 구분해주는 결정경계를 만들 수 없다.(a.k.a 선형분리 불가)

이 데이터 상에서 결정경계를 만들어 주기 위해서는, 여백 안에 데이터들이 어느정도 존재하더라도 허용하게 만들어줄 수 있다.
그래서 $\xi$라는 새로운 변수를 도입해, 여백 안에 데이터들이 있더라도 어느정도 허용해주도록 할 수 있다.

이것이 실제로 어떻게 적용될 수 있나 알아보자.

$(\underline w^\intercal \underline x_i -c)$ =0 이것이 결정경계라고 했을 때 (그림에서 직선)
$y_i(\underline w^\intercal \underline x_i -c) =1$ 이것이 support vector에 대한 여백의 경계선이다. (그림에서 점선)

그리고 모든 데이터 샘플에 대하여
$y_i(\underline w^\intercal \underline x_i -c) \ge1$ 이 식이 만족되도록 하면서 마진을 최소화 하는 것이 SVM의 목적이다.

그런데 이 식에 슬랙 변수를 도입해서

$y_i(\underline w^\intercal \underline x_i -c) \ge1-\xi_i$ 이렇게 바꾼다면,

여백에 대해서 데이터에 대한 케이스를 다음과 같이 세가지로 나눌 수 있다.

1) 옳게 분류된 경우 (그림에서 1번 동그라미)

$y_i(\underline w^\intercal \underline x_i -c) \geq 1$ , $\xi_i =0$

2) 옳게 분류됐지만 마진 안에 있는 경우 (그림에서 2번 동그라미)

$0\leq y_i(\underline w^\intercal \underline x_i -c) \leq1$ , $0\lt\xi_i\leq 1$

3) 틀리게 분류된 경우 (마진 안에 있는지는 고려 안함)(틀렸으므로) (그림에서 3번 동그라미)

$y_i(\underline w^\intercal \underline x_i -c) \lt 0$ , $1\lt\xi_i$

1번 케이스의 경우에는 어짜피 잘 분류가 되었으므로 $\xi_i =0$인경우라고 할 수 있다.

2번 케이스의 경우에는 분류가 잘 되었지만 마진 안에 있고 $0\lt\xi_i\leq 1$ 인 경우라고 할 수 있다.

3번 케이스의 경우에는 분류가 잘 안되었고 결정경계의 밖에있는 $1\lt\xi_i$ 인 경우라고 할 수 있다.

$y_i(\underline w^\intercal \underline x_i -c) \ge1-\xi_i$

이상적인 상황은 모든 점들의 슬랙변수가 0인 상황일 것이다. 그러나 위 그림과 같이 데이터가 항상 선형 분리되도록 주어지지는 않기 때문에, 여백 안에 몇개의 불순물들이 있는 것은 허용해 주어야 한다. 이것을 위해 2번 케이스나 3번케이스와 같은 샘플들에 대해서는 슬랙변수를 0보다 크게 만들어 여백 안에 있거나 결정경계를 벗어나는 경우라도 허용해주는 것이다. 그러나 무턱대고 허용해주다 보면 또 분류가 이상하게 잘 안될 수 있다. 그러니 허용을 해주더라도, 그 허용해주는 범위를 최소화 시켜줘야한다.

자 그러면.. 우리의 목표는 $\xi_i$ 을 작게 만드는 것이 된다. 왜냐하면 특정 샘플을 허용해주라도, 그 허용해주는 정도를 최소화 해야하기 때문이다. $\xi_i$ 을 허용해주는 정도로 해석하면 편하다

어떤 데이터 $x_i$ 에 대해서 $\xi_i$의 의미를 생각해보자
만약 $\xi_i$가 1보다 크다는 것은 그 데이터$x_i$ 가 오분류 되더라도 그냥 허용하겠다는 뜻이다.

만약 $\xi_i$가 0보다 크고 1보다 작으면 그 데이터$x_i$ 가 여백안에 있는 것을 허용하겠다는 듯이다.

만약 $\xi_i$가 0이라면 그 데이터$x_i$ 가 여백안에 있는 것도 허용하지 않고, 여백 밖에서 분류되도록 하겠다는 뜻이다.

데이터를 허용해주지 않으면 분류자체를 못하게 되기 때문에 어느정도의 허용은 필수적이라고 할 수 있다.

슬랙을 이해했다면 우리는 문제를 다음과 같이 다시 정의할 수 있다.

$Minimize: J(\underline w,\underline \xi)=\dfrac 1 2 \lVert\underline w\rVert ^2+C\displaystyle\sum_{i=1}^n\xi_i$

여기서 $C$는 Hyper parameter로 Minimize를 할 때 어떤 것에 더 중점을 둘 지에 대한 상수이다.
만약 $C$가 크다면 여백을 최대화 하는 것 보다 $\xi$를 최소화 하는 것(a.k.a 데이터가 여백안에 있거나 오분류 되는 것을 허용해주지 않는 것)이 더 중요할 것이고,
작다면 $\dfrac 1 2 \lVert\underline w\rVert ^2$를 최소화(a.k.a. 여백을 최대화) 하는 것이 $\xi$를 최소화 하는 것 보다 더 중요할 것이다.$S.T:$

$y_i(\underline w^\intercal \underline x_i -b) \ge1-\xi_i\\0\le\xi_i,i=1,2,\dots,n$

위 조건을 만족하면서 최소화 시키면 된다. ($c$를 $b$로 변경)

이를 라그랑주로 바꾸면 다음과 같이 된다.

$L(\underline w,b,\underline \xi,\underline \alpha,\underline \beta)=\bigg(\dfrac 1 2\lVert\underline w\rVert^2+C\displaystyle\sum_{i=1}^n\xi_i\bigg)-\bigg(\displaystyle\sum_{i=1}^n\alpha_i(y_i(\underline w^\intercal \underline x_i +b)-1+\xi_i)+\displaystyle\sum_{i=1}^n\beta_i\xi_i\bigg)$

여기서 $\underline w,b,\underline \xi$는 우리가 구하고자 하는 변수이고, $\underline \alpha,\underline \beta$는 라그랑주 상수이다.

KKT condition을 사용하자. ( $i=1,2,3,\dots,n$ 이라고 가정)

(Stationarity)

$\nabla L =0$

$\dfrac {\partial L}{\partial \underline w}=0 \Rightarrow \underline w = \displaystyle\sum_{i=1}^n\alpha_iy_i\underline x_i$

$\dfrac {\partial L}{\partial b}=0\Rightarrow \displaystyle\sum_{i=1}^na_iy_i=0$

$\dfrac {\partial L}{\partial \xi_i}=0\Rightarrow C=\alpha_i+\beta_i$

(Complementary Slackness)

$\alpha_i(y_i(\underline w^\intercal \underline x_i +b)-1+\xi_i) = 0$

$\beta_i\xi_i$ = 0

(Feasibility)

$\alpha_i \geq 0, \beta_i \geq0$

이렇게 나온다.

이 문제를 쉽게 풀기 위해서 Dual Problem으로 바꿔보자.

라그랑주를 최소화 하는 Primal optimal $\underline w,b,\underline \xi$ 를 찾고
Primal optimal을 대입했을 때의 식을 최대화 시키는 Dual optimal $\underline \alpha,\underline \beta$을 찾으면 된다.

자 해보자!

우선

$\dfrac {\partial L}{\partial \underline w}=0 \Rightarrow \underline w = \displaystyle\sum_{i=1}^n\alpha_iy_i\underline x_i$

$\dfrac {\partial L}{\partial b}=0\Rightarrow \displaystyle\sum_{i=1}^na_iy_i=0$

$\dfrac {\partial L}{\partial \xi_i}=0\Rightarrow C=\alpha_i+\beta_i$ 를

$L(\underline w,b,\underline \xi,\underline \alpha,\underline \beta)=\bigg(\dfrac 1 2\lVert\underline w\rVert^2+C\displaystyle\sum_{i=1}^n\xi_i\bigg)-\bigg(\displaystyle\sum_{i=1}^n\alpha_i(y_i(\underline w^\intercal \underline x_i +b)-1+\xi_i)+\displaystyle\sum_{i=1}^n\beta_i\xi_i\bigg)$ 여기에 대입해서 정리하면

다음과 같이 바뀐다.

$Maximize:q(\underline \alpha) =\displaystyle\sum_{i=1}^n\alpha_i-\dfrac 12 \displaystyle\sum_{i=1}^n\sum_{j=1}^na_ia_jy_iy_j\underline x_i^\intercal \underline x_j$
$S.T.:\displaystyle\sum_{i=1}^na_iy_i=0,\ 0\le\alpha_i\leq C$