An Introduction to Kernel Methods (3) - Infinite Dimensional Feature Space

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

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

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

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

k (x, y) = (x^{⊤} y + c)^{d}

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

k (x, y) = ⟨ ϕ (x), ϕ (y) ⟩

이 성립한다. 이때 $x = (x_{1}, \dots, x_{k})^{⊤}, y = (y_{1}, \dots, y_{k})^{⊤}$ 으로 두면 커널은 다음과 같이 표현된다.

k (x, y) = (x^{⊤} y)^{2} = (x_{1} y_{1} + \dots + x_{k} y_{k})^{2} = \sum_{i} \sum_{j} x_{i} y_{i} \cdot x_{j} y_{j} = ϕ (x)^{⊤} ϕ (y)

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

ϕ (x) = (x_{1}^{2}, \dots, x_{k}^{2}, \sqrt{2 x_{1} x_{2}}, \dots, \sqrt{2 x_{k - 1} x_{k}})

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

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

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

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

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

\begin{aligned} e^{- ‖ x - y ‖^{2} / 2} & = e^{- ‖ x ‖^{2} / 2} e^{- ‖ y ‖^{2} / 2} e^{x^{⊤} y} \\ = \sum_{j = 0}^{\infty} \frac{({x^{⊤} y}^{j})}{j!} e^{- ‖ x ‖^{2} / 2} e^{- ‖ y ‖^{2} / 2} \\ = \sum_{j = 0}^{\infty} (\frac{e^{- ‖ x ‖^{2} / 2 j}}{\sqrt[2 j]{j!}} \frac{e^{- ‖ y ‖^{2} / 2 j}}{\sqrt[2 j]{j!}} x^{⊤} y)^{j} \\ = \sum_{j = 0}^{\infty} \sum_{\sum_{i} n_{i} = j} \exp (- \frac{‖ x ‖^{2}}{2}) \frac{x_{1}^{n_{1}} \dots x_{k}^{n_{k}}}{\sqrt{n_{1}! \dots n_{k}!}} \exp (- \frac{‖ y ‖^{2}}{2}) \frac{y_{1}^{n_{1}} \dots y_{k}^{n_{k}}}{\sqrt{n_{1}! \dots n_{k}!}} \end{aligned}

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

ϕ (x) = (\frac{e^{- ‖ x ‖^{2} / 2 j}}{(j!)^{1 / 2 j}} {(\binom{j}{n_{1} \dots n_{k}})}^{1 / 2} x_{1}^{n_{1}} \dots x_{k}^{n_{k}})_{j = 0 \dots \infty}

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

ReferencesPermalink

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

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

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

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

ReferencesPermalink

Leave a comment