for textmining

Kernel-SVM

|

이번 글에서는 서포트 벡터 머신(SVM)의 변형인 Kernel-SVM에 대해 살펴보도록 하겠습니다. 이 글 역시 고려대 강필성 교수님과 역시 같은 대학의 김성범 교수님 강의를 정리했음을 먼저 밝힙니다. SVM의 일반적인 내용에 대해서는 이곳을, C-SVM에 대해서는 이곳을 참고하시기 바랍니다. 그럼 시작하겠습니다.

Kernel-SVM의 목적의식

SVM은 두 범주를 잘 분류하면서 마진(margin)이 최대화된 초평면(hyperplane)을 찾는 기법입니다. 기본적으로 선형분류를 한다는 것이죠. 하지만 어떤 직선을 그어도 두 범주를 완벽하게 분류하기 어려운 경우도 많습니다. Kernel-SVM은 이 문제를 해결하기 위해 제안됐습니다. 먼저 아래 그림을 보겠습니다.

그림에서도 알 수 있듯 Kernel-SVM의 핵심 아이디어는 이것입니다.

원공간(Input Space)의 데이터를 선형분류가 가능한 고차원 공간(Feature Space)으로 매핑한 뒤 두 범주를 분류하는 초평면을 찾는다.

mapping function

여기에서 가장 중요한 것은 Input Space와 Featuer Space 사이를 매핑해주는 함수 $Φ$입니다. 예를 들어 $Φ$가 아래와 같이 정의돼 있다고 칩시다.

$Φ$는 $R^2$에 속한 입력을 받아서 그보다 고차원인 $R^6$으로 변환해 줍니다. 이렇게 되면 원래는 선형분리가 불가능했던 XOR문제가 선형분리가 가능한 데이터로 바뀌게 됩니다. 아래와 같습니다.

그러면 SVM에 $Φ$를 어떻게 적용하는지 살펴보겠습니다. Hard-margin SVM과 Soft-Margin SVM의 라그랑지안 Dual 식은 동일하며 다음과 같습니다. ($L_D$ 제약식은 생략)

Kernel-SVM은 $Φ$로 변환된 고차원 공간에서 두 범주를 분류하는 초평면을 만들기 때문에 $x_i^T$와 $x_j$에 $Φ$를 적용해 주어야 합니다. 식은 다음과 같이 쓸 수 있습니다.

Kernel Trick!

그런데 커널을 도입하게 되면 연산량이 폭증하게 됩니다. 그도 그럴 것이 모든 관측치에 대해 고차원으로 매핑하고 이를 다시 내적(inner product)해야 하기 때문입니다. 고차원 매핑과 내적을 한방에 할 수는 없을까요? 이를 위해 도입된 것이 바로 커널(Kernel)입니다. 커널 $K$는 다음과 같이 정의됩니다.

매핑함수 $Φ$는 선형변환(Linear Transformation)이고 그에 해당하는 표준행렬(standard matrix)을 $A$라고 두면 다음과 같이 쓸 수 있습니다.

그러면 $K$는 다음과 같이 다시 쓸 수 있습니다.

여기에서 $Φ$를 $m$차원에서 $n$차원으로 매핑해주는 함수라고 가정해 봅시다. 그러면 각각의 차원수는 다음과 같습니다.

(1) $x_i^T$ : (1 x m)

(2) $A^T$ : (m x n)

(3) $A$ : (n x m)

(4) $x_j$ : (m x 1)

따라서 $K$의 결과는 스칼라가 됩니다. 그런데 $K(x_i, x_i)$인 경우 항상 0 이상의 값을 지녀야 할 겁니다. 또 $K(x_i, x_j)=K(x_j, x_i)$을 만족해야 할 겁니다. 이러한 맥락에서 $K(x_i,x_j)$로 구성된 행렬은 positive semi-definite matrix여야 하며 대칭행렬(symetric matrix)이어야 합니다.

이와 관련된 Mercer’s Theorem은 다음과 같습니다.

위 조건을 만족하는 임의의 함수는 모두 커널 함수로 쓸 수 있습니다. 그 종류는 다음과 같습니다.

Gaussian Kernel

polynomial 커널을 쓰는 경우 사용자가 지정한 $d$가 Feature space의 차원이 됩니다. 그러면 가우시안 커널은 어떨까요? $2σ^2=1$이어서 분모가 생략된 간단한 형태를 보겠습니다.

테일러급수 정리에 의해 $exp(2x_ix_2)$를 다음과 같이 쓸 수 있습니다.

따라서 가우시안 커널은 Input Space가 몇 차원이 됐든 무한대 차원의 Feature Space로 매핑한다는 얘기입니다.

Kernel의 효과

기존 SVM에 해당하는 Linear 커널은 선형 분류경계면을 만들어냅니다. Polynomial 등 이 글에서 소개하는 커널은 비선형 경계면이 만들어집니다. 다음과 같습니다.

이번엔 가우시안 커널을 보겠습니다. gamma는 지수의 분모에 해당하는 하이퍼 파라메터인데요. 작을수록 마진이 넓어지는 걸 확인할 수 있습니다.

Comments