Archive for » April, 2009 «

초보자를 위한 NVIDIA CUDA 단계별 학습 프로그램
Friday, April 17th, 2009 | Author: salbang

NVIDIA에서 GPU 프로그래밍을 위한 교육을 실시한다. 열라 기대된다. ^^; 이러면서 살짝 내 논문 링크

Implementing an interior point method for linear programs on a CPU-GPU system

행렬 연산을 GPU를 이용해 하는 건데 CUDA가 없을 때 Cg라는 녀석과 OpenGL을 같이 써서 열라 개고생 해서 만들었다 ㅠㅠ.

교육 안내는 아래 링크 참조.

http://www.nvidiaevent.co.kr/cuda_200904/#d

세계 유일의 C언어 기반 GPU 개발 도구인 NVIDIA® CUDA™ 기술은 범용 병렬 컴퓨팅 아키텍처로써 GPU가 복잡한 컴퓨터 문제를
해결하도록 하며, 이미 수많은 CUDA 구현 GPU와 무료 CUDA 소프트웨어 툴을 사용해 비디오 및 오디오 인코딩에서부터
석유 및 가스 탐사, 제품 설계, 의학 이미지 및 과학 연구 등 다양한 분야에서 어플리케이션을 가속화하고 있습니다.

엔비디아 코리아에서는 병렬 컴퓨팅과 CUDA 프로그래밍에 관심이 있지만 쉽게 시작하고 있지 못한 분들을 위해
NVIDIA® CUDA™ 단계별 학습 프로그램을 진행합니다.

기초부터 고급 과정까지 차근차근 단계별로 배울 수 있는 좋은 기회가 될 이번 프로그램에 여러분들의 많은 참여와 관심 부탁드립니다.

Category: 잡설  | Tags: ,  | 2 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
초보들이 행렬 연산할 때 자주 하는 실수들
Monday, April 06th, 2009 | Author: salbang

초보들이 보통 개념없이 프로그램 혹은 엑셀 쉬트를 작성하면서 행렬 연산을 하다보면 극악 무도한 행동을 좀 한다 (내가 자주 목격했다!!!). 그게 뭔고 하니 Nonsingular인 n \times n Linear System \mathbf{A}\mathbf{x} = \mathbf{b}를 푸는데

\mathbf{x} = \mathbf{A}^{-1}\mathbf{b}

를 한다는 것이다!!!

“도대체 이게 뭐가 문제지?”하고 생각했다면 당신 x잡고 반성해라. 혹시 당신 수학자거나 과학자 혹은 퀀트라면 이거 정말 심각하다. 이게 얼마나 극악 무도한 짓인지 알려주겠다.

일단 정상적으로 리니어 시스템을 풀려면 어떻게 하는지 알아둘 필요가 있다. 물론 아까도 얘기했듯이 Nonsingular인 경우다. Nonsingular가 무슨 말이냐면 n\times n 매트릭스 \mathbf{A}가 Full rank이다는 말이고 이 말은 다시 \mathbf{A}의 역행렬이 존재한다는 얘기다. 그럼 도대체 어떻게 푸는 것이 좋은 건지 빨리 알고 싶다고? 행렬 분해를 해서 풀어야 한다. A가 Symmetric Postiive Definite이 아니라면 LU 분해를 사용하게 된다. LU 분해가 뭔고 하니
\mathbf{L}\mathbf{U} = \mathbf{A}가 되는 Lower triangular matrix \mathbf{L}과 Upper triangular matrix \mathbf{U}를 찾는 것이다. 왜 이런 짓을 하냐고? 이런 행렬을 찾아내면 \mathbf{x}를 찾아내기가 쉬워서 그렇다. 자세한 과정은 수치해석 교재나 Wikipedia를 참조하자. 아무튼 이렇게 찾아냈으면 forward-substitution 즉

\mathbf{Ly} = \mathbf{b},

를 풀어 \mathbf{y}를 찾고 또 backward-substitution 즉
\mathbf{Ux} = \mathbf{y}

를 풀어 \mathbf{x}를 찾아낸다. 아 참 귀찮다고?
혹시 MATLAB을 사용한다면
\mathbf{x} = \mathbf{A} \backslash \mathbf{b}

를 하면 바로 위 과정을 알아서 해준다.

이제 역행렬을 구해서 푸는 게 뭐가 문젠지 알아보자. 첫째는 계산 시간 문제다. 역행렬을 구하기 위해 어떤 작업을 하는지 알아둘 필요가 있다.
역행렬을 찾아내는 것은 위에 매틀랩식 식으로 나타내면

\mathbf{X} = \mathbf{A} \backslash \mathbf{I},

인데 여기서 \mathbf{I}는 Identity 행렬로 행렬의 대각은 1로 채워져 있고 나머지 원소들은 0인 행렬이다. 이 문제는
\mathbf{x}_i = \mathbf{A} \backslash \mathbf{e}_i,

를 i = 1,...,n에 대해 푸는 것과 같은데 \mathbf{x}_i와 \mathbf{e}_i는 각각 행렬 \mathbf{X}와 \mathbf{I}의 i번째 열이다.

자 왜 시간이 오래 걸리는지 알겠지?

시간만 문제가 되는게 아니다. 계산 오류도 커진다. 특히 Matrix \mathbf{A}가 singular에 가까우면 더 심각해진다. 사실 이 때는 LU분해도 문제긴 하다. 그래도 LU분해가 좀 낫긴 하다. 이 경우 \mathbf{x}를 구한 다음에 \mathbf{Ax}를 해보면 \mathbf{b}와 상당히 동떨어진 결과를 내 놓는다.

이 때는 Rank revealing QR 분해나 SVD 분해를 사용해서 최대한 근사치를 구하는 방식을 쓴다. \mathbf{A}가 full rank가 아닐 때와 같은 방식으로 푼다는 얘기다. \mathbf{A}의 rank가 거의 r이라고 하면 Ax의 레인지(Range)가 n차원 공간에서 거의 r차원의 subspace에 걸친다는 얘긴다. 이 때는 A의 Rank revealing QR알고리즘을 써서 QR 팩터를 구하고 Q(:,1:r)와 R(1:r,:)를 곱해 A의 근사 매트릭스 B를 만든다음 ||\mathbf{b} - \mathbf{Bx}||_2를 최소로 하는 \mathbf{x}를 찾으면 된다.

그런데 이런 모든 것을 MATLAB의 \ 연산자가 알아서 처리해준다. 그러니까 MATLAB 사용자라면 x = inv(A)*b대신에 x = A\b를 써라.

Category: 수치해석  | Leave a Comment
« Previous Entries