Kernel-SVM
30 May 2017 | Support Vector Machine
이번 글에서는 서포트 벡터 머신(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 사이를 매핑해주는 함수 $Φ$입니다. 예를 들어 $Φ$가 아래와 같이 정의돼 있다고 칩시다.
\[\Phi :({ x }_{ 1 },{ x }_{ 2 })\rightarrow ({ x }_{ 1 }^{ 2 },{ x }_{ 2 }^{ 2 },\sqrt { 2 } { x }_{ 1 },\sqrt { 2 } { x }_{ 2 },\sqrt { 2 } { x }_{ 1 }{ x }_{ 2 },1)\]
$Φ$는 $R^2$에 속한 입력을 받아서 그보다 고차원인 $R^6$으로 변환해 줍니다. 이렇게 되면 원래는 선형분리가 불가능했던 XOR문제가 선형분리가 가능한 데이터로 바뀌게 됩니다. 아래와 같습니다.
그러면 SVM에 $Φ$를 어떻게 적용하는지 살펴보겠습니다. Hard-margin SVM과 Soft-Margin SVM의 라그랑지안 Dual 식은 동일하며 다음과 같습니다. ($L_D$ 제약식은 생략)
\[\max { { L }_{ D }({ \alpha }_{ i }) } =\sum _{ i=1 }^{ n }{ { \alpha }_{ i } } -\frac { 1 }{ 2 } \sum _{ i=1 }^{ n }{ \sum _{ j=1 }^{ n }{ { \alpha }_{ i }{ { \alpha }_{ j }y }_{ i }{ y }_{ j }{ x }_{ i }^{ T }{ x }_{ j } } }\]
Kernel-SVM은 $Φ$로 변환된 고차원 공간에서 두 범주를 분류하는 초평면을 만들기 때문에 $x_i^T$와 $x_j$에 $Φ$를 적용해 주어야 합니다. 식은 다음과 같이 쓸 수 있습니다.
\[\max { { L }_{ D }({ \alpha }_{ i }) } =\sum _{ i=1 }^{ n }{ { \alpha }_{ i } } -\frac { 1 }{ 2 } \sum _{ i=1 }^{ n }{ \sum _{ j=1 }^{ n }{ { \alpha }_{ i }{ { \alpha }_{ j }y }_{ i }{ y }_{ j }{ \Phi ({ x }_{ i }) }^{ T }{ \Phi ({ x }_{ j }) } } }\]
Kernel Trick!
그런데 커널을 도입하게 되면 연산량이 폭증하게 됩니다. 그도 그럴 것이 모든 관측치에 대해 고차원으로 매핑하고 이를 다시 내적(inner product)해야 하기 때문입니다. 고차원 매핑과 내적을 한방에 할 수는 없을까요? 이를 위해 도입된 것이 바로 커널(Kernel)입니다. 커널 $K$는 다음과 같이 정의됩니다.
\(K({ x }_{ i },{ x }_{ j })={ \Phi ({ x }_{ i }) }^{ T }{ \Phi ({ x }_{ j }) }\)
매핑함수 $Φ$는 선형변환(Linear Transformation)이고 그에 해당하는 표준행렬(standard matrix)을 $A$라고 두면 다음과 같이 쓸 수 있습니다.
\[{ \Phi (x) }=Ax\]
그러면 $K$는 다음과 같이 다시 쓸 수 있습니다.
\[K({ x }_{ i },{ x }_{ j })={ \Phi ({ x }_{ i }) }^{ T }{ \Phi ({ x }_{ j }) }={ x }_{ i }^{ T }{ A }^{ T }A{ x }_{ j }\]
여기에서 $Φ$를 $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은 다음과 같습니다.
위 조건을 만족하는 임의의 함수는 모두 커널 함수로 쓸 수 있습니다. 그 종류는 다음과 같습니다.
\[\begin{align*}
linear\quad &:\quad K({ x }_{ 1 },{ x }_{ 2 })={ x }_{ 1 }^{ T }{ x }_{ 2 }\\ polynomial\quad &:\quad K({ x }_{ 1 },{ x }_{ 2 })={ ({ x }_{ 1 }^{ T }{ x }_{ 2 }+c) }^{ d },\quad c>0\\ sigmoid\quad &:\quad K({ x }_{ 1 },{ x }_{ 2 })=\tanh { \left\{ a({ x }_{ 1 }^{ T }{ x }_{ 2 })+b \right\} } ,\quad a,b\ge 0\\ gaussian\quad &:\quad K({ x }_{ 1 },{ x }_{ 2 })=exp\left\{ -\frac { { \left\| { x }_{ 1 }-{ x }_{ 2 } \right\| }_{ 2 }^{ 2 } }{ 2{ \sigma }^{ 2 } } \right\} ,\quad \sigma \neq 0
\end{align*}\]
Gaussian Kernel
polynomial 커널을 쓰는 경우 사용자가 지정한 $d$가 Feature space의 차원이 됩니다. 그러면 가우시안 커널은 어떨까요? $2σ^2=1$이어서 분모가 생략된 간단한 형태를 보겠습니다.
\(\begin{align*}\\ K({ x }_{ 1 },{ x }_{ 2 })&=exp\left\{ -{ ({ x }_{ 1 }-{ x }_{ 2 }) }^{ 2 } \right\} \\ &=exp(-{ x }_{ 1 })exp(-{ x }_{ 2 })exp(2{ x }_{ 1 }{ x }_{ 2 })\end{align*}\)
테일러급수 정리에 의해 $exp(2x_ix_2)$를 다음과 같이 쓸 수 있습니다.
\[exp(2{ x }_{ 1 }{ x }_{ 2 })=\sum _{ k=0 }^{ \infty }{ \frac { { 2 }^{ k }{ x }_{ 1 }^{ k }{ x }_{ 2 }^{ k } }{ k! } }\]
따라서 가우시안 커널은 Input Space가 몇 차원이 됐든 무한대 차원의 Feature Space로 매핑한다는 얘기입니다.
Kernel의 효과
기존 SVM에 해당하는 Linear 커널은 선형 분류경계면을 만들어냅니다. Polynomial 등 이 글에서 소개하는 커널은 비선형 경계면이 만들어집니다. 다음과 같습니다.
이번엔 가우시안 커널을 보겠습니다. gamma는 지수의 분모에 해당하는 하이퍼 파라메터인데요. 작을수록 마진이 넓어지는 걸 확인할 수 있습니다.
이번 글에서는 서포트 벡터 머신(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 사이를 매핑해주는 함수 $Φ$입니다. 예를 들어 $Φ$가 아래와 같이 정의돼 있다고 칩시다.
\[\Phi :({ x }_{ 1 },{ x }_{ 2 })\rightarrow ({ x }_{ 1 }^{ 2 },{ x }_{ 2 }^{ 2 },\sqrt { 2 } { x }_{ 1 },\sqrt { 2 } { x }_{ 2 },\sqrt { 2 } { x }_{ 1 }{ x }_{ 2 },1)\]$Φ$는 $R^2$에 속한 입력을 받아서 그보다 고차원인 $R^6$으로 변환해 줍니다. 이렇게 되면 원래는 선형분리가 불가능했던 XOR문제가 선형분리가 가능한 데이터로 바뀌게 됩니다. 아래와 같습니다.
그러면 SVM에 $Φ$를 어떻게 적용하는지 살펴보겠습니다. Hard-margin SVM과 Soft-Margin SVM의 라그랑지안 Dual 식은 동일하며 다음과 같습니다. ($L_D$ 제약식은 생략)
\[\max { { L }_{ D }({ \alpha }_{ i }) } =\sum _{ i=1 }^{ n }{ { \alpha }_{ i } } -\frac { 1 }{ 2 } \sum _{ i=1 }^{ n }{ \sum _{ j=1 }^{ n }{ { \alpha }_{ i }{ { \alpha }_{ j }y }_{ i }{ y }_{ j }{ x }_{ i }^{ T }{ x }_{ j } } }\]Kernel-SVM은 $Φ$로 변환된 고차원 공간에서 두 범주를 분류하는 초평면을 만들기 때문에 $x_i^T$와 $x_j$에 $Φ$를 적용해 주어야 합니다. 식은 다음과 같이 쓸 수 있습니다.
\[\max { { L }_{ D }({ \alpha }_{ i }) } =\sum _{ i=1 }^{ n }{ { \alpha }_{ i } } -\frac { 1 }{ 2 } \sum _{ i=1 }^{ n }{ \sum _{ j=1 }^{ n }{ { \alpha }_{ i }{ { \alpha }_{ j }y }_{ i }{ y }_{ j }{ \Phi ({ x }_{ i }) }^{ T }{ \Phi ({ x }_{ j }) } } }\]Kernel Trick!
그런데 커널을 도입하게 되면 연산량이 폭증하게 됩니다. 그도 그럴 것이 모든 관측치에 대해 고차원으로 매핑하고 이를 다시 내적(inner product)해야 하기 때문입니다. 고차원 매핑과 내적을 한방에 할 수는 없을까요? 이를 위해 도입된 것이 바로 커널(Kernel)입니다. 커널 $K$는 다음과 같이 정의됩니다.
\(K({ x }_{ i },{ x }_{ j })={ \Phi ({ x }_{ i }) }^{ T }{ \Phi ({ x }_{ j }) }\) 매핑함수 $Φ$는 선형변환(Linear Transformation)이고 그에 해당하는 표준행렬(standard matrix)을 $A$라고 두면 다음과 같이 쓸 수 있습니다.
\[{ \Phi (x) }=Ax\]그러면 $K$는 다음과 같이 다시 쓸 수 있습니다.
\[K({ x }_{ i },{ x }_{ j })={ \Phi ({ x }_{ i }) }^{ T }{ \Phi ({ x }_{ j }) }={ x }_{ i }^{ T }{ A }^{ T }A{ x }_{ j }\]여기에서 $Φ$를 $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은 다음과 같습니다.
위 조건을 만족하는 임의의 함수는 모두 커널 함수로 쓸 수 있습니다. 그 종류는 다음과 같습니다.
\[\begin{align*} linear\quad &:\quad K({ x }_{ 1 },{ x }_{ 2 })={ x }_{ 1 }^{ T }{ x }_{ 2 }\\ polynomial\quad &:\quad K({ x }_{ 1 },{ x }_{ 2 })={ ({ x }_{ 1 }^{ T }{ x }_{ 2 }+c) }^{ d },\quad c>0\\ sigmoid\quad &:\quad K({ x }_{ 1 },{ x }_{ 2 })=\tanh { \left\{ a({ x }_{ 1 }^{ T }{ x }_{ 2 })+b \right\} } ,\quad a,b\ge 0\\ gaussian\quad &:\quad K({ x }_{ 1 },{ x }_{ 2 })=exp\left\{ -\frac { { \left\| { x }_{ 1 }-{ x }_{ 2 } \right\| }_{ 2 }^{ 2 } }{ 2{ \sigma }^{ 2 } } \right\} ,\quad \sigma \neq 0 \end{align*}\]Gaussian Kernel
polynomial 커널을 쓰는 경우 사용자가 지정한 $d$가 Feature space의 차원이 됩니다. 그러면 가우시안 커널은 어떨까요? $2σ^2=1$이어서 분모가 생략된 간단한 형태를 보겠습니다. \(\begin{align*}\\ K({ x }_{ 1 },{ x }_{ 2 })&=exp\left\{ -{ ({ x }_{ 1 }-{ x }_{ 2 }) }^{ 2 } \right\} \\ &=exp(-{ x }_{ 1 })exp(-{ x }_{ 2 })exp(2{ x }_{ 1 }{ x }_{ 2 })\end{align*}\)
테일러급수 정리에 의해 $exp(2x_ix_2)$를 다음과 같이 쓸 수 있습니다.
\[exp(2{ x }_{ 1 }{ x }_{ 2 })=\sum _{ k=0 }^{ \infty }{ \frac { { 2 }^{ k }{ x }_{ 1 }^{ k }{ x }_{ 2 }^{ k } }{ k! } }\]따라서 가우시안 커널은 Input Space가 몇 차원이 됐든 무한대 차원의 Feature Space로 매핑한다는 얘기입니다.
Kernel의 효과
기존 SVM에 해당하는 Linear 커널은 선형 분류경계면을 만들어냅니다. Polynomial 등 이 글에서 소개하는 커널은 비선형 경계면이 만들어집니다. 다음과 같습니다.
이번엔 가우시안 커널을 보겠습니다. gamma는 지수의 분모에 해당하는 하이퍼 파라메터인데요. 작을수록 마진이 넓어지는 걸 확인할 수 있습니다.
Comments