SVM-KERNEL

앞서서 선형분리 가능한 문제에 대한 SVM을 배웠고,
선형분리 불가능한 문제에 대한 SVM Soft margin을 배웠다.
그러나 soft margin은 어느정도 선형분리 가능한 꼴 에서 몇 개의 데이터를 허용해주는 정도이기 때문에, 모든 선형분리 불가능한 문제에는 적용할 수 없다.

예를들어 다음과 같은 데이터가 있다.

다음과 같은 데이터는 선형분리가 불가능하다. Soft Margin을 사용하더라도 분류할 수 없다.
이러한 비선형 데이터에 대해서는 어떻게 접근해야 할 것인가?

다음과 같은 방법이 있다.
위 그림의 2차원 데이터를 3차원으로 변경하는 것이다.

기존의 데이터가 $\underline x = \begin{bmatrix} x_1\\x_2\end{bmatrix}$였다면, 여기서 x_3에 대한 것을 임의로 추가시켜 $(x_3= x_1^2+x_2^2)$

$\underline x = \begin{bmatrix} x_1\\x_2\\x_1^2+x_2^2\end{bmatrix}$ 와 같은 3차원 데이터로 만든다면 그림이 다음과 같이 그려진다.

그리고 데이터를 다음과 같이 노란색 초평면으로 선형분리 할 수 있게 된다.
여기서 우리가 알 수 있는 것은
선형분리 불가능한 문제를 해결하는 방법은 차원을 증가시키면 된다는 것이다.

이 과정을 다음과 같은 식으로 쓸 수 있다.

$\underline \Phi(\underline x)=\underline \Phi((x_1,x_2,\cdots,x_d)^\intercal) = (\phi_1(\underline x),\phi_2(\underline x),\cdots,\phi_q(\underline x))^\intercal$
d 차원의 data를 변환함수 $\Phi$에 넣으면, q차원의 data로 변한다.

근데 여기서 어려운 점은 차원을 증가시키는건 알겠는데, 어떤 변환을 통해서 차원을 증가시켜야 하는지에 대한 문제다. 위 그림에서는 $(x_3= x_1^2+x_2^2)$ 을 통해서 차원을 증가시켰지만, 다른 방법 예를들어 $x_3=x_1$과 같은 방법으로 변환시킨다면 선형분리시킬 수 없다.

그럼 이 상황을 어떻게 해결할 수 있을까?

이 상황을 해결하기 위해서 만들어진 것이 커널 트릭이다.
커널 함수의 정의부터 살펴보자

원래 특징 공간 $L$에서 정의된 두 특징 벡터 $\underline x$ 와 $\underline z$ 에 대해 $K(\underline x, \underline z)=\Phi(\underline x)\cdot\Phi(\underline z)$ 인 변환함수 $\Phi$가 존재하면 $K(\underline x, \underline z)$를 커널함수라고 부른다.

다음 상황을 보자.

특징 공간 $L$ 에 있는$\begin{bmatrix}x\\\end{bmatrix}$를 다음과 같이 변환시키는 함수를 생각해보자.

$\Phi(\begin{bmatrix}x\\\end{bmatrix}) = \begin{bmatrix}x^2\\ \sqrt 2 x\\1\end{bmatrix}$

이렇게 되면 특징 공간에 있는 데이터 $\alpha=[x_1],\beta=[x_2]$ 가 다음과 같이 변화한다.

$\Phi(\underline \alpha)=\Phi(\begin{bmatrix}x_1\\\end{bmatrix}) = \begin{bmatrix}x_1^2\\ \sqrt 2 x_1\\1\end{bmatrix}$$\Phi(\underline \beta)=\Phi(\begin{bmatrix}x_2\\\end{bmatrix}) = \begin{bmatrix}x_2^2\\ \sqrt 2 x_2\\1\end{bmatrix}$

그리고 변환된 데이터 둘을 내적해주면 다음과 같이 된다.

$\Phi_1 (\underline \alpha)^\intercal \Phi_2(\underline \beta)=x_1^2x_2^2+2x_1x_2+1=(1+x_1x_2)^2=K(\underline \alpha,\underline \beta)$

변환 전에 함수는 1차원 데이터였다. 그리고 변환을 통해 3차원 데이터로 바뀌었다.
그런데, 이 3차원 데이터를 내적한 값은 1차원데이터로 표현이 가능했다.
그리고 이 함수(표현)을 커널함수라고 부른다.

여기서 우리가 머리를 굴려서 Trick을 쓰게 되는데, 그것은 우리가 변환된 데이터의 내적값을 알고 싶을 때, 구지 변환을 시키지 않더라도 원래 데이터를 커널함수에 집어넣는 것만을 통해서 그 내적값을 알 수 있다는 것이다.

즉 위에서 우리가 커널함수가 $K(\underline \alpha,\underline \beta)=(1+\underline \alpha \underline \beta)^2$라는 것을 미리 알고있다면,
$\Phi(\begin{bmatrix}x\\\end{bmatrix}) = \begin{bmatrix}x^2\\ \sqrt 2 x\\1\end{bmatrix}$ 이렇게 변환되는 것을 모르더라도,

$\Phi_1 (\underline x_1)^\intercal \Phi_2(\underline x_2)$이 어떤 값인지$K(\underline \alpha,\underline \beta)=(1+\underline \alpha \underline \beta)^2$에 대입함으로써 바로 알 수 있다는 것이다.
이것이 커널트릭이다.

이것은 엄청난 편리함을 가져다주고 우리에게 있는 차원의 저주를 풀어줄 수 있는 하나의 Key가 된다. SVM에서도 이러한 방법을 통해서 비선형 문제를 푼다.

그렇다면 Kernel Function에 어떤 것들이 있는지 알아보자.
널리쓰이는 커널 세가지가 있다.

Polynomial Kernel: $K(\underline x,\underline z) = (\underline x \cdot \underline z+1)^p$
$p$는 차수를 지정하는 하이퍼 매개변수이다.

RBF(Gaussian) Kernel: $K(\underline x,\underline z) = exp\bigg (\dfrac {-\lVert \underline x - \underline z\rVert ^2} {2\sigma^2} \bigg )$
$\sigma$는 가우시안의 퍼짐 정도를 나타내는 하이퍼 매개변수이다.

Sigmoid Kernel: $K(\underline x,\underline z)=tanh(a\underline x\cdot\underline z + \beta)$
시그모이드 커널은 $\alpha$ 와 $\beta$ 중 특정 조합만 성립한다. 주로 $\alpha =2 , \beta =1$을 주로 사용한다.

Kernel 의 의미를 한 번 생각해보자, Kernel은 알맹이,핵심,중심,중요한 것 이라는 뜻이다.
우리가 집중해야 할 부분은 내적의 결과이지, 그 이전의 데이터가 어떤 모양이였고 어떻게 변환되었는지는 중요하지 않다는 것이다.

더 높은 차원에서의 내적결과를 낮은 차원에서의 커널함수의 계산으로 대치하는 것, 그것이
Kernel Trick이다.

그러면 실제로 SVM에서 이를 어떻게 적용하는지를 알아보자

SVM-KERNEL(2)

SVM에서 커널함수를 어떻게 사용할까?
이전에 소프트마진에서 사용했던 식을 다시한번 가져와보자.

$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$

만약에 비선형 문제라면 우리는 $\underline x$를 더 높은 차원으로 변환시킨 다음 문제를 풀어야한다.
그리고 더 높은 차원에서의 내적을 풀어야 한다. ($\underline x_i^\intercal \underline x_j$ 이므로)

$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 \Phi(\underline x_i)^\intercal \Phi(\underline x_j)$
$S.T.:\displaystyle\sum_{i=1}^na_iy_i=0,\ 0\le\alpha_i\leq C$

여기서 Kernel Trick을 사용한다. 더 높은 차원에서의 내적을 풀 때, 변환을 하지 않고 원래 있는 데이터를 커널함수에 대입시켜서 더 높은 차원에서의 내적값을 계산한다.

만약 RBF 커널을 사용한다면 식을 다음과 같이 바꿀 수 있다.

$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 \exp\bigg (\dfrac {-\lVert \underline x_1 - \underline x_2 \rVert ^2} {2\sigma^2} \bigg )$
$S.T.:\displaystyle\sum_{i=1}^na_iy_i=0,\ 0\le\alpha_i\leq C$

이렇게 식을 바꾼다면 더 높은 차원의 데이터에 대해서도 SVM을 적용할 수 있게 된다!

이 식을 이제 잘 풀기만 하면 된다.
$n$이 작은 경우에는 우리가 해석적으로 풀 수 있지만,
$n$이 커지는 경우에는 우리가 알고리즘으로 풀어야한다.

이러한 알고리즘에는 여러가지 종류가 있다.

SMO 알고리즘, plane cutting 알고리즘, coordinate descent알고리즘 등이 있다. 이러한 알고리즘에 대해서는 나중에 다시 다뤄보겠다.

만약 알고리즘을 통해서 라그랑주 승수를 다 구했다고 가정해보자.(학습이 끝났을 때)

그러면 새로운 샘플 $\underline x$가 들어왔을 때 $\underline x$의 레이블을 예측해야한다.

이에 대해서 알아보자.

SVM-PREDICTION

선형분리한 경우에 대해서 생각해보자

선형 분리 가능한 경우:

선형 SVM 예측: 새로운 샘플 $\underline x$에 대하여
$d(\underline x)>0$ 이면 1, 그렇지 않으면 -1으로 분류.
$d(\underline x) = \underline w^\intercal\underline x+b$

우리는 알고리즘을 통해 라그랑주 승수를 구했으므로

$\dfrac {\partial L}{\partial \underline w}=0 \Rightarrow \underline w = \displaystyle\sum_{i=1}^n\alpha_iy_i\underline x_i$를 통해서 가중치를 구할 수 있다.

여기서 $\alpha_i =0$인 것들은 제외할 수 있다. 왜냐하면 곱하더라도 0이기 때문이다.
즉 서포트 벡터에 해당하는 값들을 통해서 $\underline w$를 구하겠다는 것이다.

그러면 식이 다음과 같이 바뀐다.

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

이 식을 통해 가중치를 구한 후에

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

에 대입해서 b(bias)를 구할 수 있다. 하나의 서포트 벡터만 대입해서 구해도 이론적으로는 괜찮지만,
수치적 정확도를 위해서 모든 서포트 벡터를 대입한 다음 평균을 취한다.
(왜냐하면 알고리즘으로 구하는 값은 근사값일 수 밖에 없으므로)

이렇게 우리가 $\underline x,b$에 대해서 알게 되었으면,
새로운 샘플 $\underline x$가 들어왔을 때
$d(\underline x)$에 대입하고 부호를 통해서 분류하면 된다.

선형 분리 불가능한 경우:

비선형 SVM 예측: 새로운 샘플 $\underline x$에 대하여
$d(\underline x)>0$ 이면 1, 그렇지 않으면 -1으로 분류.
$d(\underline x) =\displaystyle\sum_{a_k \not = 0}\alpha_iy_iK(\underline x_k\underline x) +b$

비선형 문제인 경우에는 내적 계산을 사용하므로 상황이 달라진다. 비선형 공간에서는 학습과정에서 공간을 변환시켰으므로, 예측할 때도 공간을 변환시켜야한다. 왜냐하면 우리가 구한 함수는 변환된 공간에서의 함수이기 때문에, 새로운 샘플을 이 함수에 대입시키기 위해서는 이 샘플의 차원 또한 변환시켜야한다.

그러나 우리는 매핑 함수를 모른다. 우리는 변환된 공간에서의 내적값을 이용하는 (Kernel Trick)을 사용했다. 그러니 우리는 예측할 때도 Kernel Trick을 사용해서 내적으로 예측값을 구해야한다. 즉 내적의 형태가 나오도록 유도해야한다.

$d(\underline x)=\underline w^\intercal\Phi(\underline x) +b$
(데이터에 대해서 공간변화)
$\underline w =\displaystyle\sum_{a_k \not = 0}\alpha_ky_k\Phi(\underline x_k)$ 이므로 대입하면
$d(\underline w)=\bigg (\displaystyle\sum_{a_k \not = 0}\alpha_ky_k\Phi(\underline x_k)\bigg)^\intercal\Phi(\underline x) +b$
이다. 다행히 내적의 형태로 표현할 수 있다.

$d(\underline w)=\displaystyle\sum_{a_k \not = 0}\alpha_ky_k\Phi(\underline x_k)^\intercal\Phi(\underline x) +b$
이므로 커널 함수를 적용하면,
$d(\underline w)=\displaystyle\sum_{a_k \not = 0}\alpha_ky_kK(\underline x_k,\underline x)+b$ 로 표현할 수 있다.

여기서 주목할 점은 우리가 $K(\underline x_k,\underline x)$ 를 미리 계산할 수 없다는 것이다.
새로운 샘플 $\underline x$가 들어오면 그때 이 함수를 계산할 수 있다.

즉 새로운 샘플이 들어오기 전까지는 $\underline x_k$들을 저장해 두어야 한다. 하지만 다행인 점은
서포트벡터만 저장해도 된다는 것이다. $a_k \not = 0$ 인 데이터들로만 가중치를 계산하기 때문이다.

즉 비선형 SVM은 메모리 기반 방법이다. 메모리에 데이터들을 저장해두고 예측해야한다.
따라서 서포트 벡터가 많아질 수록 모델의 크기도 커지고 예측시간도 길어진다.