Archive for the Category » 인공지능 «

Support Vector Machine 소개
Wednesday, November 04th, 2009 | Author: salbang

참고 자료 1: SVM을 활용한 KOSPI 예측
참고 자료 2: Adaptive constraint reduction for training support vector machines

들어가기 전에 말하고 싶은게 하나 있다. 보통 Support Vector Machine(이하 SVM)을 사람들에게 대충 설명해주면 Linear Classifier라고 꼬졌다고 하는데 Linear Classifier지만 Kernel Trick을 사용해서 Nonlinear Classifier로 확장할 수 있다. 그러니 참고 읽어주세요.

Support Vector Machine (SVM)은 통계적 기계학습이라 하는 방법중 하나다. 기계학습이라 함은 말 그대로 학습(공부)하는 기계를 만들어 열라 학습(공부)시켜 뭔가 알아내게 해서 그 녀석을 써먹는 걸 말한다. 아 우리네 인생과 비슷하지 않나? 열심히 공부해서 결국 남 좋은 일 하고 있다. 주주들… 여하간 기계학습에는 크게 두 가지가 있는데 첫째는 Supervised learning(지도학습)이고 둘째는 Unsupervised learning(자가학습)이다. SVM은 이중에서 Supervised learning에 속한다. 그러니 일단 Supervised learning에 대해서 알아보자.

Supervised learning은 누군가로부터 배우는 개념이다. 여기서 누군가는 대체로 사람이 된다. 독버섯과 먹을 수 있는 버섯을 구분하는 방법에 대해 얘기해보자. 갓 모양 및  색깔, 자생 지역 특성 등을 이용하면 독버섯을 구분해 낼 수 있다. 이런 정보를 수치화(-1/1 혹은 연속 적인 값을 할당)한 후에 각 버섯 특성 별로 독버섯인지 아닌지를 버섯 전문가가 분류하여 기계에 주면 기계는 그 둘을 분류해낼 수 있는 판단 기준을 세우게 되는데 이러한 학습법을 Supervised learning이라 한다. 대충 어떤 건지 감 잡았으면 수학적으로 모델링 해보도록 하자.

m개의 버섯에 대한 특징을 모았다고 하자. 각 버섯의 특징을 수치화 한 열 벡터를 \mathbf{x}_i로 표현하도록 하자. i번째 버섯이 독버섯(-1)인지 식용버섯(1)인지를 y_i라고 표현하자. 우리가 원하는 것은 독버섯 벡터들과 식용버섯 벡터들을 나눌 수 있는 Hyperplane \{\mathbf{x} : \langle \mathbf{w}, \mathbf{x} \rangle - \gamma = 0 \}을 찾아내는 것이다. 여기서 \langle \cdot,\cdot\rangle은 내적(inner-product)을 의미한다. 그럼 이 Hyperplane이 두가지 버섯들을 나눈다는 것은 어떻게 표현할 수 있을까?

좀더 쉽게 ^^. 중고등학교 때 많이 다뤘던 2차원 벡터에 대해서 생각해보자. 2차원에서 Hyperplane은 직선이다. 자 그럼 우리 모두 익숙한 \{ (x_1, x_2) : x_1 + x_2 -1 = 0 \}를 한번 그려보자. 그럼 \{(x_1, x_2) : x_1 + x_2 - 1 > 0 \}은 그래프에서 어떤 영역을 나타낼까? 그렇다 바로 직선의 윗부분!

2DExample

그래 바로 주어진 벡터 x_i가 Hyperplane의 위에 있는지 아래에 있는지로 독버섯인지 아닌지 분별하도록 하면 된다. 참 쉽죠~

이를 식으로 표현하면 다음과 같다.

\left\{\begin{array}{ll}</p> <p>\langle\mathbf{w},\mathbf{x_i}\rangle-\gamma>0&\text{if }y_i=1\\</p> <p>\langle\mathbf{w},\mathbf{x_i}\rangle-\gamma<0&\text{if }y_i=-1</p> <p>\end{array}\right.</p> <p>\Leftrightarrow</p> <p>y_i(\langle\mathbf{w},\mathbf{x_i}\rangle-\gamma)>0</p> <p>

좀더 구체적으로 그림으로 한번 볼까?

초평면(Hyperplane)을 이용한 패턴 분류

초평면(Hyperplane)을 이용한 패턴 분류

ManyHyperplanes

패턴을 구분할 수 있는 초평면이 무수히 많다!

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

위 왼쪽 그림에서 보다시피 동그라미들은 초평면 오른쪽 위에 있고 네모들은 아래에 있다. 하지만 저 동그라미들과 네모들을 나눌 수 있는 Hyperplane이 무수히 많다는거! 어떤게 과연 이중 좋은 걸까?

우리가 관찰한 데이터에는 늘상 오류가 있게 마련이다. 즉 공간상에 점으로 표현된 데이터가 그 자리에 있는 데이터란 법이 없다. 뭔 말인고 하니,

빨간선은 별로 안 좋은 분류 Hyperplane

빨간선은 별로 안 좋은 분류 Hyperplane

위 그림에서 동그란 녀석들 중에 점선으로 둘러싸인 녀석이 하나 있는데, 이 놈은 저 점선 안에 어딘가 있었을 놈이란 의미로 점선으로 표시했다. 그럼 빨간선을 사용해서 나중에 구한 데이터를 분류한다고 생각해보자. 재수 없게도 새 데이터가 하필이면 저 점선으로 표시된 부분에서 튀어나올지도 모른다. 그럼 빨간선은 답을 제대로 못 낼지도 모른다. 그럼 이런 상황을 최대한 피하려면 어떻게 해야 할까? 이런 애로사항을 피하기 위해 Vapnik 아저씨가 생각해 낸 것이 바로 Separation Margin(분류여백)이다. 즉 많은 초평면중에서 가장 가까운 점(데이터)까지의 거리를 최대로 하는 평면을 선택하는 것이다. Got it?

이 작업을 하기 위해서 분류 평면 양 옆으로 평행한 보조 평면 두 개를 추가해 사용한다. 그럼 대충 다음과 같은 모양이 나오겠지?

+/- 경계 평면

+/- 경계 평면

1이란 숫자는 그리 중요한 의미를 갖지는 않는다. 하여간 이렇게 셋업해 놓으면 가운데 분류 평면하고 옆에 평행한 평면하고의 거리는 \frac{1}{\||\mathbf{w}\||가 된다. 이 정도는 고등학교 산수니까 알아서들 계산하셈. 그리고 이 거리의 2배 만큼이 분류 여백 되시겠다.

이제 거의 다 왔다. 우리의 목표를 다시 상기해 보자.

1. 패턴을 경계 평면으로 분류한다. 즉 y_i(\langle \mathbf{w}, \mathbf{x} \rangle - \gamma) >= 1.

2. 분류 여백을 최대화 한다. 즉 \max_{\mathbf{w}} \frac{2}{\||\mathbf{w}\||} \Leftrightarrow \min_{\mathbf{w}} \frac{\||\mathbf{w}\||}{2}.

위 두 조건을 하나로 묶으면 다음과 같은 최적화 문제가 나온다.

\begin{align}<br /> &\min_{\mathbf{w}} \frac{\||\mathbf{w}\||}{2}\\<br /> s.t. &y_i(\langle \mathbf{w}, \mathbf{x} \rangle - \gamma) \ge 1,\,i=1,\dots,m.<br /> \end{align}

ㅠㅠ 근데 이게 다가 아니다. 아까도 얘기했지만 우리가 측정한 데이터는 오류, 노이즈 등이 있기 마련. 그래서 딱 잘라 구분할 수 없는 경우가 대부분이다.

어쩌라구? ㅠㅠ
어쩌라규? ㅠㅠ

그렇다 위 그림처럼 데이터는 저렇게 존재한다. ㅠㅠ 왜냐 원래 있어야 할 곳이 아니라 다른 곳에서 관찰 될 수도 있고, 사람이 가공하다 실수했을 수도 있다. 하지만 이런 상황에서도 데이터를 나누고 싶지 않은가? 저 그림만 보더라도 대충 나눠도 되지 않나 싶은 느낌이 들지 않나? 그래 함 나눠 보자. 분류 여백을 최대화 하면서도 잘못 분류하는 걸 줄이는 방향으로 하면 되지 않겠는가?

아싸!

아싸!

분류경계가 잘못 나눈 데이터까지의 거리를 \xi_i라고 하고 이를 목적 함수에서 페널티를 주면 된다. 그럼 이제 이런 문제를 풀면 해결 되는 거다.

\begin{align}<br /> &\min_{\mathbf{w}} \frac{\||\mathbf{w}\||}{2} + \mathbf{\tau}^T\mathbf{\xi}\\<br /> s.t. &y_i(\langle \mathbf{w}, \mathbf{x} \rangle - \gamma) + \xi_i \ge 1,\,i=1,\dots,m,\\<br /> &\mathbf{\xi} \ge \mathbf{0},\,i=1,\dots,m.<br /> \end{align}

진짜 많이 했다. 이제 Nonlinear 평면으로 확장하는 방법에 대해서 얘기하도록 하자. 먼저 Mapping이라는 방법을 쓸 수 있다. 적절한 Mapping \Phi를 사용해서 원래 데이터를 다른 (고)차원으로 이동시켜 버리는 것이다. 3차원에만 있지 말고 4차원으로 가고 싶지 않은가? ㅋㅋ

구체적으로 예를 들자면 다음과 같은 2차 폴리노미얼 Mapping이 있다. (x_1, x_2)^T \mapsto (x_1^2, x_2^2, \sqrt{2}x_1x_2). 이  Mapping을 사용하면 타원형 경계를 만들 수 있다. 즉 다음과 같은 데이터를 분류할 수 있다는 얘기.

우왕 ㅋ 굳 ㅋ. 데이터를 고차원으로 보낼 수 있다규!

우왕 ㅋ 굳 ㅋ. 데이터를 고차원으로 보낼 수 있다규!

그래 데이터를 고차원으로 보내서 거기서 분류 평면을 찾으면 원래 차원에서 희한하게 생긴 분류 곡면이 나온다! 데이터를 4차원으로 보내면 4차원같은 일이 일어난단 말이다! 기쁘지 않은가? 커널 트릭을 사용하면 더 심한 곳으로 옮길 수도 있다. 만쉐이!

근데 매핑으로는 애로사항이 있다. 그건 바로 차원의 저주(Curse of Dimensionality)! 원래 차원이 100차원인데 이를 2차 폴리노미얼 매핑을 실시한다면 _{100}C_2+_{100}C_1 = 5050차원으로 간다. 으헉 ㅠㅠ. 3차원 폴리노미얼 매핑이면 더할텐데. 이건 아니자나 ㅠㅠ. 여기에 우리의 구세주 커널이 있다. 지난 글 Reproducing Kernel Hilbert Space(RKHS)에서 소개한 그 커널 말이다. 이걸 어떻게 이용할 수 있을까? 이걸 이용하려면 데이터간의 Inner-product가 막 일어나는 그런 문제가 필요한데…

여기서 등장하는 구세주는 Duality. 모든 옵티마이제이션 문제에는 Dual Problem(쌍대 문제)가 있다. 어떻게 유도하는지는 생략하고 답만 얘기하자면

<br /> \begin{align*}</p> <p>&\max_{\mathbf{w}} -\frac{1}{2}\mathbf{\alpha}^T\mathbf{K}\mathbf{\alpha} + \mathbf{e}^T\mathbf{\alpha}\\s.t. & \mathbf{y}^T\mathbf{\alpha} = 0\\<br /> & 0 \le \mathbf{\alpha} \le \mathbf{\tau},<br /> \end{align*}<br />

여기서 행렬 \mathbf{K}의 원소 k_{ij} := \langle \mathbf{x_i}, \mathbf{x_j} \rangle이다. 드디어 데이터간에 내적이 나왔다. 여기서 \langle \cdot,\cdot \rangle대신 적당한 커널 k(\cdot,\cdot)을 사용하면 된다. 물론 RKHS를 구성할 수 있는 커널이 필요한데 Symmetric하고 Positive Semi-Definite하면 되겠다.

일단 SVM을 훈련시키는 문제의 정의까지 했다. 다음에는 구체적으로 훈련 시키는 알고리즘에 대해서 다루도록 하겠다.

Category: 금융공학, 인공지능, 통계차익거래  | Tags:  | 4 Comments
Reproducing Kernel Hilbert Space
Thursday, April 16th, 2009 | Author: salbang

(강의 노트)

Hilbert space(힐버트 공간)에는 여러가지가 있지만 하필 reproducing kernel hilbert space (RKHS)에 대해서 설명하려는 것은 이 공간이 support vector machine (SVM)이라는 기계학습(machine learning) 중 한 기법을 nonlinear class로 확장 시키는 데 중요한 역할을 하기 때문이다. 이번엔 우선 Hilbert space가 뭔지 알아보고 그 중에서 reproducing kernel hilbert space가 무엇인지 알아보려고 한다.

간단히 설명해 Hilbert space는 Euclidean space(유클리드 공간)를 inifinite demension(무한차원)까지 확장한 것으로 생각할 수 있다. 우리가 고등학교 때 배운 벡터라 함은 2차원, 3차원, …, n차원 등의 유한 차원 공간에서 어떤 점을 말한다. 즉 예를 들어 4차원 (컬럼) 벡터 v \in \mathbb{R}^4라 함은

v=[5, 2, 4, 8]^T와 같은 녀석을 말한다. 이를 다르게 생각하면 domain(정의역) \Omega={1, 2, 3, 4}에서 정의된 함수

v(i) = \left{\begin{array}{ll} 5, \text{ for }i=1 \\ 2, \text{ for }i=2 \\ 4, \text{ for }i=3\\ 8, \text{ for }i=4\end{array}\right.

로 볼 수도 있다. 즉 유한차원에서의 벡터는 어떤 정수 입력이 들어가면 그에 대응하는 출력이 나오는 함수로 볼 수 있다는 얘기다.

이를 거꾸로 생각하면 어떤 함수 f(x)도 벡터로 생각할 수 있게 된다. 이런 함수들로 구성된 공간이 무한 차원인 것은 f(x)의 정의역인 \Omega에 무한히 많은 원소가 있기 때문이다. 하여간 함수들로 이루어진 대표적인 vector space에는 \mathcal{L}_2 space(Hilbert space이기도 함)가 있다.

다시 Hilbert space로 돌아가서 얘기해보자. Hilbert space \mathcal{H}는 vector space이다. 벡터 스페이스 중에서도 어떤 Norm이 정의될 수 있는 공간을 normed space라 한다. Normed space에서 벡터간 내적 \langle x, y \rangle, \forall x,y \in \mathcal{H}이 정의되면 그 공간은 inner-product space라 한다. inner-product space에서는 Norm ||x||:=\langle x,x\rangle \forall x \in \mathcal{H}이 자연히 존재하며 이 Norm에 대해 Complete한 공간, 즉 모든 Cauchy sequence가 한 점으로 수렴하는 공간을 Hilbert space라고 한다. Hilbert space에서는 두 벡터  x와 y간의 거리 d(x,y)를 d(x,y):=||x-y||=\sqrt{\langle x-y,x-y\rangle}로 정의할 수 있으므로 metric space이기도 하다.

요약 하자면 어떤 Space \mathcal{H}가 Hilbert space라면 \mathcal{H}는

  1. Vector space
  2. Metric space
  3. Normed space
  4. Inner-product space
  5. Complete space

인 것이다.

이제 RKHS로 넘어가자. 이 공간은 symmetric and positive semidefinite(SPSD)한 Kernel에 의해 유도되는 공간이다. 그러니 먼저 SPSD kernel이 무엇인지 부터 알아보자. 일단 kernel이라 함은 어떤 domain \Omega에 속하는 인자를 두개 받는 함수 k : \Omega\times\Omega \rightarrow\mathbb{R}로 정의 할 수 있다. Symmetric하다 함은

k(x,y) = k(y,x) \forall x,y \in \Omega

가 성립됨을 말한다. Positive semidefinite하다는 건 좀 정의하기가 복잡한데 Mercer theorem에 따르면 다음과 같다. 도메인 \Omega에 속한 임의의 점 Sequence x_1,\dots,x_n \in \Omega가 있고 이 점 sequence에 대응하는 Gram matrix K의 각 원소를 k_{ij} := k(x_i, x_j)로 정의한다. 모든 가능한 임의의 n과 임의의 모든 점 조합 x_1,\dots,x_n \in \Omega에 대해 K가 positive semidefinite하면 이 kernel은 positive semidefinite한 kernel이라 한다.

쉽게 얘기하자면 kernel은 Euclidean space에서의 matrix의 Hilbert space 버전으로 생각할 수 있다. (엄밀히 얘기해서 Euclidean space도 Hilbert space에 속한다.)

그럼 일단 RKHS \mathcal{H}의 구성원 들이 어떻게 생겼는지 정의부터 해보자. RKHS를 만드려면 몇가지 재료가 필요하다. 재료부터 알아보자.

  1. 입력공간(Input space) \mathcal{X},
  2. \mathcal{X}의 원소 둘을 실수로 대응시키는 Binary함수이며 SPSD 커널인
    k :\mathcal{X}^2 \mapsto \mathbb{R}.

이 둘이 있으면 RKHS \mathca{H}는 다음과 같이 정의할 수 있다.

\mathcal{H} := \left{f(x) : \sum_{i=1}^m \alpha_i k(x, x_i)\text{ for } x_i \in \mathcal{X},\,\alpha_i\in\mathbb{R},\,i \in {1,\dots,m},\,m \in \mathbb{N}\right}.

말로 풀어 쓰자면 \mathcal{H}에 속하는 함수는 입력공간의 여러점에서의 커널 함수를 계산하는 것을 선형조합(Linear combination)한 것이라 할 수 있다.

f ,g\in \mathcal{H}이면 f + g \in \mathcal{H}, f + g = g + f, \alpha f \in \mathcal{H} 등등등…인 것은 자명하니까 \mathcal{H}가 벡터 공간임은 쉽게 알 수 있다. 다음으로는 inner-product 공간인지 확인해 보자. inner-product 공간임이 확인되면 normed space와 metric space는 자동으로 확인된다. 우선은  inner-product \langle \cdot, \cdot \rangle를 다음과 같이 정의해보자.

\mathcal{H}의 임의의 두 원소 f := \sum_{i=1}^m \alpha_i k(\cdot, x_i)와 g := \sum_{i=1}^{m'} \beta_i k(\cdot, x_i')에 대해

\langle f, g \rangle := \sum_{i=1}^m\sum_{j=1}^{m'}\alpha_i\beta_jk(x_i,x_j').

이제 할 일은 이 연산자가 진정 inner-product의 성질을 갖고 있는지 확인하는 일이다. Inner-product는 다음과 같은 4가지 성질을 만족해야 한다. \mathcal{H}의 원소 f,,g,,h와 임의의 실수 \gamma에 대해서

  1. Associative: \langle\gamma f,g\rangle = \gamma\langle f,g\rangle,
  2. Symmetric: \langle f, g\rangle = \langle g,f \rangle,
  3. Distributive: \langle f, g+h\rangle = \langle f,g \rangle + \langle f, h\rangle, 그리고 마지막으로
  4. Definite: \langle f,f \rangle \ge 0, 단 등호는 f=0일 때만 성립.

위 성질중 1,2,3번을 묶어서 Bilinear하다고 한다. 아무튼 1,2,3번은 입증하기 매우 쉽다. 연습문제로 함 해보도록 *^^*. 4번은 좀 증명하려면 긴데 위에 첨부한 강의 노트를 보도록 하자. 4번을 증명하려면 Cauchy-Schwarz 부등식

\langle f,g \rangle^2 \le \langle f,f\rangle\langle g,g\rangle

이 성립함을 보여야 한다. 이 부등식을 증명하려면 자연스럽게 사용하게 되는 커널의 성질이 있는데 그게 뭔고하니 커널의 Dirac delta function과 비슷한 성질인 Representer of evaluation이라 불리는

\langle f, k(\cdot,x)\rangle =\sum_{i=1}^m\alpha_i k(x_i,x) = f(x)  \forall f\in \mathcal{H}.

그리고 바로 이 스페이스의 이름에 들어가는 Reproducing 성질(property)인

\langle k(\cdot,x),k(\cdot,y)\rangle = k(x,y)

와 같은 성질을 갖고 있다.

Inner-product 공간임이 밝혀 졌으니 natural norm(||f|| = \sqrt{\langle f, f \rangle})이 존재하므로 normed space이면서 norm을 이용한 distance measure가 있으니 metric space임도 저절로 밝혀진다. 이제 Complete space임을 보이면 되는데 사실 위에서 정의한 \mathcal{H}로는 complete space가 될 수 없다.  이를 위해 추가적인 원소를 \mathcal{H}에 더해줘야 하는데 이를 위해서는 다음과 같은 부등식을 이용해야 한다.

|f(x) - g(x)| = |\langle f-g,,k(\cdot,x)\rangle| \le ||k(\cdot,x)||||f-g|| = \sqrt{k(x,x)}||f-g||.

따라서 위에서 정의한 \mathcal{H}내에 있는 모든 가능한 Cauchy sequence의 limit을 \mathcal{H}에 추가해 주면 \mathcal{H}은 complete한 공간이 된다. 따라서 이러한 점들이 추가된 \mathcal{H}는 Hilbert space가 된다.

이 긴 과정을 요약하면 \mathcal{H}는 어떤 kernel로부터 유도 되는 공간으로서 그 kernel은  reproducing 성질을 갖게 되며 그 공간은 Hilbert space이기 때문에 \mathcal{H}는 reproducing kernel hilbert space라고 불린다는 것이다.

Category: 인공지능, 통계차익거래  | Tags: ,  | 2 Comments