Home Machine Learning 15. Kernel Methods

[기계학습] 15. Kernel Methods

Post Date

Modified Date

Category

열다섯 번째 챕터는 Kernel Method를 배우게 됩니다. 지난 시간에 배웠던 Support Vector Machine에서 이어지는 내용입니다.

챕터는 크게 두 주제로 나뉘어 있습니다. 비선형 변환을 처리하기 위한 Kernel Trick이 무엇인지를 먼저 배우고, SVM의 방법 중 하나인 Soft-margin SVM을 배우게 됩니다. 두 주제가 서로 연관이 되어있지는 않지만, 두 주제 모두 비선형 문제를 해결하기 위한 시도라고 생각하시면 됩니다.

The Kernel Trick

지금까지 비선형 문제를 풀기 위해서는 비선형 문제를 선형 문제로 변환시키기 위해 \mathcal{Z} 공간으로 데이터를 Transform 시키는 방법을 사용하였습니다. 그러나 일반적으로 적당한 Transform Function \Phi를 찾는 것은 쉽지 않기 때문에 Transform을 시키지 않은 채로 비선형 문제를 해결하는 방법이 필요합니다. Kernel의 아이디어는 바로 거기서부터 시작합니다.

먼저 지금까지 \mathcal{Z} 공간에서 어떤 일을 했었는지를 떠올려봅시다. 지난 시간에 배웠던 라그랑지안 \mathcal{L} 식에서 맨 뒷부분을 보시면, 보라색으로 표시된 \mathbf{z}^{\sf T}_{n}\mathbf{z}_m의 내적 부분이 바로 유일하게 \mathcal{Z} 공간이 사용되는 부분입니다. 라그랑지안에서의 Constraints 부분은 \mathcal{Z} 공간과 관련이 없습니다.

라그랑지안을 풀고 찾은 가설 g에도 \mathbf{z}가 쓰입니다. 그런데 g에서의 Weight인 \mathbf{z}가 쓰이므로, 결과적으로 가설 g에는 \mathbf{z} 자체보다는 \mathbf{z}_n\mathbf{z}의 내적만이 필요합니다. b 또한 식을 살펴보면 \mathbf{z}_n\mathbf{z}_m의 내적만 알고 있다면 구할 수 있습니다.

이로써 알 수 있는 것은 라그랑지안을 통해 \mathcal{Z} 공간에서 가설 g를 구하기 위해서는 \mathbf{z}를 직접 구할 필요 없이 \mathbf{z} 간의 내적만 알 수 있으면 된다는 것입니다. 만약에 \mathcal{Z} 공간까지 가지 않더라도 \mathbf{z} 간의 내적을 구할 수 있다면, 굳이 힘들게 데이터들을 \mathcal{Z} 공간으로 Transform 시키는 수고를 하지 않아도 될 것입니다.

주어진 데이터는 \mathcal{X} 공간에 있는 임의의 두 점 \mathbf{x}\mathbf{x}'이라고 가정합시다. 이 두 점을 \mathcal{Z} 공간으로 Transform 시킨 점을 \mathbf{z}\mathbf{z}'이라고 하면, 우리가 원하는 것은 주어진 데이터만으로 \mathbf{z}\mathbf{z}'의 내적을 구하는 것입니다. 이 내적을 K(\mathbf{x}, \mathbf{x}')으로 표현하고, Kernel이라 부르도록 하겠습니다.

이해를 돕기 위해 주어진 데이터가 \mathbf{x} = (x_1, x_2)라고 가정합시다. 만약 Transform Function \Phi이 2차 다항식으로 주어진다면 Transform을 한 결과는 \mathbf{z} = (1, x_1, x_2, x_1^2, x_2^2, x_1 x_2)가 됩니다. 이 경우 K(\mathbf{x}, \mathbf{x}')를 구한다면 아래와 같습니다.

K(\mathbf{x}, \mathbf{x}') = \mathbf{z}^{\sf T} \mathbf{z}'

=(1, x_1, x_2, x_1^2, x_2^2, x_1 x_2) \cdot (1, {x'}_1, {x'}_2, {x'}_1^2, {x'}_2^2, {x'}_1 {x'}_2)

=1 + x_1 {x'}_1 + x_2 {x'}_2 + x_1^2 {x'}_1^2 + x_2^2 {x'}_2^2 + x_1 {x'}_1 x_2 {x'}_2

그렇다면 두 점 \mathbf{x}\mathbf{x}'을 Transform을 하지 않고 K(\mathbf{x}, \mathbf{x}')를 구하는 방법을 알아봅시다.

또 다른 예로 K(\mathbf{x}, \mathbf{x}') = (1 + \mathbf{x}^{\sf T} \mathbf{x}')^2를 가정해봅시다. 이를 풀어쓰면 1 + x_1^2 {x'}_1^2 + x_2^2 {x'}_2^2 + 2 x_1 {x'}_1 + 2 x_2 {x'}_2 + 2 x_1 {x'}_1 x_2 {x'}_2이 되는데, 이 식을 잘 살펴보면 두 벡터 (1, x_1^2, x_2^2, \sqrt{2} x_1, \sqrt{2} x_2, \sqrt{2} x_1 x_2)(1, {x'}_1^2, {x'}_2^2, \sqrt{2} {x'}_1, \sqrt{2} {x'}_2, \sqrt{2} {x'}_1 {x'}_2)의 내적을 수행한 결과라는 것을 알 수 있습니다.

이런 식으로 (1 + \mathbf{x}^{\sf T} \mathbf{x}')의 제곱의 형태인 Kernel을 Polynomial Kernel (다항식 커널)이라고 부릅니다.

일반적인 상황을 고려하기 위해 d차원의 주어진 데이터를 Q차 다항식으로 Transform을 하게 된다면, 이와 동등한 Kernel은 K(\mathbf{x}, \mathbf{x}') = (1 + \mathbf{x}^{\sf T} \mathbf{x}')^Q로 표현할 수 있습니다.

그런데 문제는 만약 dQ가 커지게 되면 K(\mathbf{x}, \mathbf{x}')를 구하기가 너무 어렵다는 것입니다. 슬라이드에 나온대로 d=10, Q=100인 상황만 가정하더라도 10차 다항식을 100제곱 하는 결과를 구해야 하는데, 계산량이 너무 많아 전개하는 것이 거의 불가능합니다.

그렇기 때문에 Polynomial Kernel에서는 \mathbf{x}^{\sf T} \mathbf{x}'를 전개하지 않고 a \mathbf{x}^{\sf T} \mathbf{x}' + b 의 형태로 만들어 이항정리를 사용해 \mathbf{x}^{\sf T} \mathbf{x}'의 계수만을 구하게 됩니다.

Kernel이 두 점 \mathbf{x}\mathbf{x}'의 내적으로 정의된 문제는 해결되었으나, 그 외에 상황을 고려할 필요가 있습니다. 이번 예제에 나온 Kernel은 \mathbf{x}\mathbf{x}'의 내적으로 표현되지 않고 Euclide Norm으로 표현되고 있습니다. 이런 식의 Kernel이 \mathcal{Z} 공간에 존재하는 지를 보여야 합니다.

결론부터 말하면 이 Kernel은 무한차원의 \mathcal{Z} 공간에 존재합니다. 간단한 예를 들면 주어진 점 \mathbf{x}를 1차원이라 가정합니다. 그렇다면 \mathbf{x}\mathbf{x}'는 모두 스칼라로 표현이 되므로 xx'으로 대체합니다. 그리고 \gamma를 간단하게 1로 놓습니다.

그런 후에 이 식을 Taylor Series로 표현한다면 좀 더 복잡한 식이 되긴 합니다. 하지만 보기 쉽게 xx'를 갖고 있는 것을 각각 분리한다면 두 무한 차원의 벡터의 내적으로 이루어진 식임을 알 수 있습니다.

참고로 이런 Kernel을 Radial Basis Function Kernel이라고 합니다. 다음 챕터에서 이를 더 자세하게 다룰 예정입니다.

이제 Kernel을 실제 비선형 문제에서 적용하는 방법을 살펴봅시다. 주어진 \mathcal{X} 공간의 데이터들을 무한 차원인 \mathcal{Z} 공간에 Transform 할 필요 없이, 이전 슬라이드에서 배운 Kernel만을 사용할 것입니다. Kernel을 Quadratic Programming에 입력하면 알아서 Support Vector가 구해지기 때문에 직접적인 계산은 필요가 없습니다.

그림이 작아서 잘 보이진 않지만, 파란색의 점과 빨간색의 점이 양쪽의 Support Vector입니다. 그리고 그 Support Vector를 따라 그린 검은색 곡선이 학습 결과가 됩니다. Support Vector인데 왜 Margin이 크지 않는지 궁금해하실 수도 있는데, 이 검은색 곡선은 \mathcal{Z} 공간에서 Margin이 최대인 직선으로 그린 것이기 때문에 지금 보는 \mathcal{X} 공간과는 관련이 없습니다.

Support Vector Machine을 계산할 때, 위와 비슷한 Quadratic Programming 문제를 풀었던 것을 기억하실 겁니다. 그 당시에는 \mathcal{X} 공간의 문제를 풀었기 때문에 저 자리에 \mathbf{x}\mathbf{x}'의 내적이 들어가 있었습니다. 비선형 문제를 풀기 위해서는 저 자리에 \mathbf{z}\mathbf{z}'의 내적이 있어야 하지만, 그것이 싫어 K(\mathbf{x}, \mathbf{x}')로 대체한 것이 지금까지 한 내용입니다.

이제 Kernel에서 Final Hypothesis를 어떻게 구하는지를 알아봅시다.

이전에도 보았듯이, Hypothesis를 \mathcal{Z} 공간에서 구했기 때문에 g\mathbf{z}가 포함된 식으로 표현이 가능했습니다. 하지만 지금까지 우리는 \mathbf{z}를 배제해왔으니, 이것 대신 Kernel K( - , - )로 표현할 수 있도록 식을 바꾸어봅시다.

이번 챕터 앞부분에서 했던 것처럼 \mathbf{w}를 풀어서 전개하면 \mathbf{z} 간의 내적으로 표현할 수 있게 되고, 그 부분을 K(\mathbf{x}_n, \mathbf{x})로 대체할 수 있습니다. 시그마가 포함된 앞부분은 더이상 정리할 수 없지만, b는 또다시 Kernel로 표현할 수 있습니다.

지금까지 배운 Kernel의 유일한 문제, 스스로 만든 임의의 Kernel이 유효한지를 알 수 없다는 것입니다. 다시 말해, 우리가 제시한 Kernel이 어떤 \mathcal{Z} 공간에서 나온 Kernel임을 보여야 한다는 것입니다.

크게 3가지 접근방법이 있는데, 첫 번째는 Polynomial Kernel과 같이 개념적인 방법으로 접근하여 Kernel을 만드는 방법입니다. 두 번째는 다음 슬라이드에서 설명할 Kernel의 수학적인 특성을 이용하는 것입니다. 세 번째는 저자분이 선호하는 방법이라고 하는데 신경 쓰지 않는 방법이라고 합니다….

이전 슬라이드에서 말한 Kernel의 수학적인 특성을 이용해 Kernel을 디자인해봅시다. 임의의 Kernel이 유효하기 위한 필요충분조건은 첫째로 Symmetric 해야 한다는 조건이 있습니다. 이것은 \mathbf{x}\mathbf{x}'의 위치를 서로 바꿔도 원래의 식과 동일해야 한다는 것입니다.

두번째는 모든 데이터 점을 사용해 만든 Kernel Matrix가 Positive Semi-Definite여야 합니다. Matrix가 Positive Semi-Definite라는 것은 해당 Matrix의 모든 Eigenvalue가 음수가 아니라는 것인데, 일반적으로는 영벡터가 아닌 x에 대해 x^{\sf T} M x \ge 0이라면 Matrix M이 Positive Semi-Definite라고 부릅니다.

이 수학적 특성을 Mercer’s Condition이라고 부르는데, 보시다시피 두 번째 조건은 데이터의 많은 경우 계산이 어렵기 때문에 실제로 이를 보이는 것은 쉽지 않습니다.

Soft-Margin SVM

Kernel에 대한 이야기는 끝났고, 다음으로는 Soft-margin SVM에 대해 알아봅시다.

이전과 마찬가지로 비선형 문제를 다룰 것이지만, 비선형 문제도 두 가지 종류로 나눌 수 있습니다. 하나는 왼쪽 그림처럼 몇 개의 데이터만 무시한다면 선형으로 나눌 수 있는 경우고, 다른 하나는 오른쪽 그림처럼 아예 선형 분류를 시도조차 할 수 없는 경우입니다.

오른쪽 그림과 같은 경우는 Kernel로 처리하면 되지만, 왼쪽 그림과 같은 경우는 Kernel보다 더 나은 방법이 있을 것 같습니다. 이제 배울 Soft-Margin SVM으로 이런 경우를 처리할 것입니다.

Support Vector Machine의 Error Measure를 다시 한번 살펴보겠습니다. 현재 문제가 되는 것은 Support Vector 사이에 있는 Margin 영역에 Violation (침범)하는 데이터입니다. 이 Violation 데이터 때문에 Support Vector를 구하는 식인 y_n (\mathbf{w}^{\sf T} \mathbf{x}_n + b) \ge 1가 성립하지 않습니다.

이 문제를 해결하기 위해 Violation 데이터를 정량화할 필요가 있고, 원래의 최적화 식을 변형해야 합니다. 오른쪽 항에 0보다 큰 \xi_n를 빼주는데, \xi_n의 총 합이 Violation이 일어나는 총 합이 됩니다.

Support Vector를 구하는 식을 바꾸었으니 원래의 최적화 식 또한 변경할 필요가 있습니다. 원래의 최적화 식에 \xi_n의 총 합과 그 가중치를 나타내는 상수 C를 곱한 값을 빼주어야 합니다. Augment Error의 개념과 비슷하다고 생각하시면 됩니다. 최적화 식의 조건은 이전 슬라이드에서 변경했던 식이 그대로 들어왔습니다.

최적화 식이 바뀌었으니, 그것을 계산하는 라그랑지안 또한 바뀔 것임을 쉽게 알 수 있습니다. 라그랑지안에서는 최적화 식과 조건을 하나의 식으로 만들어주므로 대부분의 항은 크게 문제 될 것이 없습니다. 마지막 항을 보시면 \beta_n \xi_n의 합을 빼는 항이 추가된 것이 보이는데, 이것은 \xi_n이 0보다 크다는 조건을 라그랑지안으로 표현한 것입니다.

라그랑지안에서 변수 \xi_n가 추가되었으니 라그랑지안을 \xi_n에 대해 편미분한 식을 구해야 합니다. 라그랑지안이 복잡해 보이지만, 자세히 보시면 라그랑지안이 \xi_n에 대해 죄다 1차식으로만 이루어졌다는 것을 알 수 있습니다. 따라서 남는 계수는 C\alpha_n, 그리고 \beta_n 뿐입니다. 식은 간단하지만 의외로 이 편미분의 결과가 의미하는 바는 큰데, \alpha_nC보다 절때 클 수 없다는 것입니다. 만약에 \alpha_nC 보다 크다면 편미분 식을 만족하는 \beta_n값이 없어지기 때문입니다. 게다가 이제 \beta_n\alpha_nC로 표현할 수 있으니, 추가된 새로운 변수인 \beta_n을 소거할 수 있습니다.

최종적으로 라그랑지안을 살펴보면 당연히 \beta_n는 이제 없어지고, \alpha_nC보다 크지 않다는 조건이 추가되었습니다.

이제 Support Vector의 종류를 살펴보도록 하겠습니다. 이제 이전과 달리 모든 Support Vector가 Magin을 나타내는 것이 아닙니다. 변경된 Support Vector를 구하는 식에서 \xi_n가 0인 경우에는 이전과 마찬가지로 Margin의 경계선에 위치하는 Support Vector가 나오지만, 그렇지 않은 경우에는 Support Vector가 전혀 엉뚱한 위치에 있을 수 있기 때문입니다.

마지막으로 두 가지 기술적 관점을 살펴보겠습니다. 원래의 Support Vector Machine은 데이터가 선형으로 분리가 가능한 경우를 가정해서 Hard Margin을 계산하는 것이었습니다. 그러나 데이터가 선형 분리가 되지 않을 때는 다른 방법을 찾아야 하는데, 쉬운 방법으로는 방금과 같이 Soft Margin을 구하는 것입니다. 이때 변수가 \alpha 하나에서 \beta가 추가되었기 때문에 Dual Problem으로 바뀌게 됩니다.

두 번째로는 \mathcal{Z} 공간에서의 문제입니다. 기존에 Threshold를 의미하는 w_0이 있었다는 것을 기억하실 겁니다. 그런데 SVM에서는 이에 대한 언급이 없고, 이와 비슷한 기능을 하는 b가 있었습니다. 같은 역할을 하는 서로 다른 변수가 있기 때문에 개념이 꼬일 수 있지만, 결과적으로 이 둘이 전부 0으로 수렴하기 때문에 실제 계산에서는 신경 쓸 필요가 없습니다.

이번 챕터는 여기까지입니다. 읽어주셔서 감사합니다.

댓글 남기기

Please enter your comment!
Please enter your name here

Duvelix

학부에서는 수학을, 대학원에서는 컴퓨터공학을 전공했습니다. 현재는 컴퓨터공학과 박사과정을 수료하고 보이지 않는 졸업과 싸우는 중입니다.

Popular posts

[KATC] 전문연구요원 훈련소 후기 – 프롤로그

훈련소를 수료하고 돌아온지도 거의 열흘이 지났습니다. 그 동안 밀려있던 일들을 처리하기도 하고 오랜만에(?) 느낀 사회의 자유를 즐기느라 포스트를 작성하지 못했습니다. 당분간은 정기적으로 작성해던 포스트의...

[Tip] New 닌텐도 3DS XL vs New 닌텐도 2DS XL

안녕하세요, 오늘 포스트는 New 닌텐도 3DS XL과 New 닌텐도 2DS XL의 차이점을 소개하려고 합니다. 저는 New 닌텐도 2DS XL로 시작을 했고 최근에 New 닌텐도 3DS...

[기계학습] 7. VC Dimension

일곱 번째 챕터에서는 지난 챕터 마지막에 나온 Vapnic-Chervonenkis (VC) Dimension에 대해 배우게 됩니다. 이번 챕터는 4개의 소주제로 나뉘어 있습니다. 먼저 VC Dimension의 정의를 배우고, Perceptron에서의...

[Life Hack] OBS Studio로 녹화하기

게임을 할 때나, 컴퓨터로 복잡한 작업을 할 때는 기록을 위해 녹화를 하고 싶은 경우가 있습니다. 컴퓨터 화면을 녹화할 수 있는 프로그램은 Fraps, 반디캠, 오캠...

[Life Hack] 구글 애드센스 시작하기

구글 애드센스는 구글에서 컨텐츠 제공자들이 수익을 얻을 수 있게 만드는 광고 게제 서비스입니다. 구글 계정을 통해 가입하여, 제공 받은 광고 태그를 블로그나 유튜브에 삽입하면...

Recent comments