커널트릭에서 특성공간의 차원문제

김당찬·2022년 2월 22일

Kernel Theory

목록 보기

4/4

무한차원특성공간 vs 유한차원특성공간

커널 트릭에서 살펴보았듯이, 커널을 이용하면 데이터셋을 특성 매핑(feature mapping)을 사용하지 않고도 동일한 연산을 수행할 수 있다. Input Space $\mathbf{X}$ 의 데이터가 벡터 $\mathbf{x_1,\ldots,x_k}$ 로 주어진다고 하자. 특성 매핑(사상) $\phi(\mathbf{x}):\mathbf{X}\to\mathcal{F}$ 은 데이터셋의 각 데이터를 내적공간 $\mathcal{F}$ 로 대응시킨다. 여기서 커널 트릭이라는 것은 $\mathcal{F}$ 에서의 내적 대신 함수 $k:\mathbf{X\times X}\to R$ 을 이용해 내적을 암묵적으로(implicitly) 계산하는 것을 말한다. 이때, 커널의 종류에 따라 특성공간 $\mathcal{F}$ 의 차원이 다르게 나타나는데, 이는 각 커널들의 정의를 통해 보일 수 있다.

유한차원특성공간 - 다항커널

다항커널(Polynominal Kernel)은 특성공간이 유한차원으로 나타나는 대표적인 예시이다.
Input Space가 k차원 유클리드공간 $R^k$ 인 조건에서 각 데이터(벡터) $\mathbf{x,y}\in R^k$ 가 주어진다고 하자. 이때 다항커널 $k$ 는

k(\mathbf{x,y})=(\mathbf{x^\top y}+c)^d

로 주어지며, 여기서 $c,d$ 각각은 음이 아닌, 자연수인 Hyperparameter이다. 계산의 편의를 위해 여기서는 $c=0,d=2$ 로 두고 특성공간을 보이도록 하자. (특별히 $c=0$ 인 경우를 Homogeneous Polynominal Kernel 이라고 한다.)
앞서 말한것과 같이 커널은 특성공간의 내적에 대응하므로

k(\mathbf{x,y})=\langle\phi(\mathbf{x}),\phi(\mathbf{y})\rangle

이 성립한다. 이때 $\mathbf{x}=(x_1,\ldots,x_k)^\top,\mathbf{y}=(y_1,\ldots,y_k)^\top$ 으로 두면 커널은 다음과 같이 표현된다.

k(\mathbf{x,y})=(\mathbf{x^\top y})^2=(x_1y_1+\cdots+x_ky_k)^2 = \sum_i\sum_j x_iy_i\cdot x_jy_j = \mathbf{\phi(x)^\top\phi(y)}

따라서 위의 대응관계가 성립하기 위해 특성공간은

\phi(\mathbf{x}) = (x_1^2,\ldots,x_k^2,\sqrt{2x_1x_2},\ldots,\sqrt{2x_{k-1}x_k})

의 형태로 주어져야 한다. 이때 특성공간 $\phi(\mathbf{x})$ 의 차원은

\binom{k+d-1}{d}=\binom{k+1}{2}

로 주어진다. 이를 통해 다항커널에 대응하는 특성공간이 유한차원임을 알 수 있다.

무한차원특성공간 - RBF 커널

반면, 가우시안 방사함수 커널(Radial Basis Function)의 경우 특성공간이 유한차원으로 주어지지 않는데, 다음과 같은 전개를 통해 확인할 수 있다. 우선 위에서와 마찬가지로, Input Space가 $R^k$ 로 주어진다고 하자. 일반성을 잃지 않고, 가우시안 방사커널의 Hyperparameter $\sigma$ 를 1로 설정하자. 그러면 커널 $k(\mathbf{x,y})=e^{-\Vert \mathbf{x-y}\Vert^2/2}$ 는 테일러 전개를 이용해 다음과 같이 전개된다.

\begin{aligned} e^{-\Vert \mathbf{x-y}\Vert^2/2} &= e^{-\mathbf{\Vert x\Vert^2/2}}e^{-\mathbf{\Vert y\Vert^2/2}}e^{\mathbf{x^\top y}} \\ &=\sum_{j=0}^\infty\frac{(\mathbf{x^\top y}^j)}{j!}e^{-\mathbf{\Vert x\Vert^2/2}}e^{-\mathbf{\Vert y\Vert^2/2}}\\ &=\sum_{j=0}^\infty\Biggl(\frac{e^{-\Vert \mathbf{x}\Vert^2/{2j}}}{\sqrt[2j]{j!}}\frac{e^{-\Vert \mathbf{y}\Vert^2/{2j}}}{\sqrt[2j]{j!}}\mathbf{x^\top y}\Biggr)^j\\ &=\sum_{j=0}^\infty\sum_{\sum_i n_i=j}\exp(-\frac{\Vert \mathbf{x}\Vert^2}{2})\frac{x_1^{n_1}\cdots x_k^{n_k}}{\sqrt{n_1!\cdots n_k!}}\exp(-\frac{\Vert \mathbf{y}\Vert^2}{2})\frac{y_1^{n_1}\cdots y_k^{n_k}}{\sqrt{n_1!\cdots n_k!}} \end{aligned}

이로부터 방사커널의 특성공간이

\phi(\mathbf{x}) = \Biggl(\frac{e^{-\Vert\mathbf{x}\Vert^2/2j}}{(j!)^{1/2j}}\binom{j}{n_1\ldots n_k}^{1/2}x_1^{n_1}\cdots x_k^{n_k}\Biggr)_{j=0\ldots \infty}

로 주어짐을 확인할 수 있다. 이떄, 각 인덱스 $j$ 의 집합이 무한집합이므로, 방사커널의 특성공간은 무한집합임을 알 수 있다.

References

Shashua, Amnon (2009). "Introduction to Machine Learning: Class Notes 67577"

김당찬

블로그 이사했습니다 https://ddangchani.github.io

이전 포스트