Eigenfunctions and Kernel Methods

IntroductionPermalink

이번 글에서는 eigenfunctions^고유함수와 이를 기반으로 하는 커널 방법론들의 해석에 대해 다루어보도록 하겠습니다. 고유함수의 개념은 데이터를 분석하는 과정에서는 요구되지 않을 수 있습니다. 다만, 많은 머신러닝 방법론, 그 중에서도 Gaussian Process 기반 방법론들의 이해에 중요한 부분을 차지한다고 생각합니다.

기본적인 아이디어는 행렬의 고유값과 고유벡터를 생각해보면 이해가 쉽습니다. 행렬 $A$ 에 대해 $A v = λ v$ 를 만족하는 $v$ 를 고유벡터^eigenvector, $λ$ 를 고유값^eigenvalue이라고 합니다. 이러한 고유벡터와 고유값은 행렬의 성질을 분석하는 데 중요한 역할을 합니다. 마찬가지로, 함수에 대해서도 고유함수와 고유값을 정의할 수 있습니다.

EigenfunctionsPermalink

KernelPermalink

고유함수를 이해하기 위해서는 먼저 커널^kernel에 대한 이해가 필요합니다. 커널에 대한 부가적인 내용은 Kernel Methods에서 다루었으니, 해당 글을 참고하시기 바랍니다. 커널을 간단히 정의하자면, 두 입력 벡터 $x, x^{'} \in X$ 에 대해 실수값을 반환하는 함수 $k : X \times X \to R$ 를 말합니다. 이때, 커널은 대칭성^symmetric과 양의 정부호성^{positive definiteness}을 만족해야 합니다.

대칭성: $k (x, x^{'}) = k (x^{'}, x)$
양의 정부호성: 모든 $L_{2}$ 공간의 함수 $f \in L_{2} (X, μ)$ 에 대해 다음이 성립합니다.
$\int \int k (x, x^{'}) f (x) f (x^{'}) d μ (x) d μ (x^{'}) \geq 0$

Remark. 커널 함수와 공분산 함수^{covariance function}는 밀접한 관련이 있습니다. Gaussian process의 경우, 공분산 함수는 다음과 같이 정의됩니다.
$k (x, x^{'}) = Cov (f (x), f (x^{'}))$
본래 공분산 함수는 확률과정^{stoachastic process} 혹은 랜덤필드^{random field}의 공분산을 정의합니다. 커널 함수는 반드시 두 입력값에 대한 유사도를 반환하는 것은 아니므로, 두 정의가 완전히 동일하다고 할 수는 없습니다. 다만, Gaussian process의 경우, 커널 함수가 공분산 함수의 역할을 한다고 생각할 수 있습니다. (명칭의 차이도 존재 : e.g. Gaussian RBF kernel vs Squared Exponential covariance function)

DefinitionPermalink

커널함수에 대한 고유함수^{eigenfunction}은 다음과 같이 정의됩니다.

\int k (x, x^{'}) ϕ (x^{'}) d μ = λ ϕ (x^{'})

여기서 $μ$ 는 $X$ 에서 정의되는 적절한 측도^measure이며, $λ$ 는 고유값^eigenvalue입니다. 이때, $ϕ$ 를 고유함수라고 부릅니다. 이는 행렬의 고유값과 고유벡터의 정의와 유사합니다.

행렬에서는 고유값과 고유벡터가 행렬의 크기만큼 존재하는 것과 달리, 커널 함수의 경우 무한개의 고유함수가 존재합니다. (함수공간을 무한차원의 벡터공간으로 볼 수 있기 때문임을 생각하면 좋습니다.)

ExamplePermalink

확률측도 $μ$ 가 밀도함수 $p (x) = N (0, σ^{2})$ 를 가질 때, Gaussian RBF 커널

k (x, x^{'}) = \exp (- \frac{∥ x - x^{'} ∥^{2}}{2 ℓ^{2}})

에 대한 고유함수와 고유값은 다음과 같습니다.

\begin{aligned} λ_{k} & = \sqrt{\frac{2 a}{A}} B^{k}, \\ ϕ_{k} (x) & = \exp (- (c - a) x^{2}) H_{k} (\sqrt{2 c} x) \end{aligned}

여기서 $a = 1 / 4 σ^{2}$ , $b = (2 ℓ^{2})^{- 1}$ , $c = \sqrt{a^{2} + 2 a b}$ , $A = a + b + c$ , $B = b / A$ 이고, $H_{k}$ 는 아래와 같이 정의되는 에르미트 다항식^{Hermite polynomial}입니다.

H_{k} (x) = (- 1)^{k} e^{x^{2}} \frac{d^{k}}{d x^{k}} e^{- x^{2}}

Mercer’s TheoremPermalink

Mercer의 정리는, 임의의 커널 함수 $k$ 를 고유값과 고유함수들로 나타낼 수 있다는 정리입니다. 먼저, 커널 함수 $k$ 에 대해, 다음과 같이 적분 연산자 $T_{k}$ 를 정의하도록 합시다.

T_{k} f (x) = \int_{X} k (x, x^{'}) f (x^{'}) d μ

이때 Mercer의 정리는 다음과 같습니다.

Mercer’s Theorem. 측도 공간 $(X, μ)$ 에서 정의된 커널 함수 $k$ 에 대해 $T_{k} : L_{2} (X, μ) \to L_{2} (X, μ)$ 가 양의 정부호인 경우, $μ^{2}$ 에 대해 거의 모든^{almost everywhere} $x, x^{'} \in X$ 에 대해 다음 표현이 성립합니다.
$k (x, x^{'}) = \sum_{i = 1}^{\infty} λ_{i} ϕ_{i} (x) ϕ_{i}^{*} (x^{'})$

여기서 $λ_{i}$ 는 양의 실수이고, $ϕ_{i}$ 는 정규화된^normalized 고유함수입니다. 정규화된 고유함수는 행렬의 고유벡터와 유사하게, 함수공간의 정규직교^orthonormal 기저를 형성합니다.

Nyström MethodPermalink

Mercer의 정리는 커널 함수를 고유함수들로 나타낼 수 있다는 것을 보여줍니다. 확률측도 $μ$ 가 밀도함수 $p (x) d x$ 를 가질 때, 고유함수 분해는 다음과 같이 근사될 수 있습니다.

\begin{aligned} λ_{i} ϕ_{i} (x) & = \int k (x, x^{'}) p (x) ϕ_{i} (x) d x \\ ≃ \frac{1}{n} \sum_{j = 1}^{n} k (x_{j}, x^{'}) ϕ_{i} (x_{j}) \end{aligned}

이때, $x_{1}, \dots, x_{n}$ 은 샘플링된 데이터 포인트들입니다. 이때, 위 식에 $x^{'} = x_{j}$ 들을 대입하면 ( $j = 1, \dots, n$ ), 이는 다음과 같은 행렬식으로 나타낼 수 있습니다.

\begin{matrix} (1) & [\begin{matrix} λ_{i} ϕ_{i} (x_{1}) \\ ⋮ \\ λ_{i} ϕ_{i} (x_{n}) \end{matrix}] = \frac{1}{n} [\begin{matrix} k (x_{1}, x_{1}) & \dots & k (x_{1}, x_{n}) \\ ⋮ & ⋱ & ⋮ \\ k (x_{n}, x_{1}) & \dots & k (x_{n}, x_{n}) \end{matrix}] [\begin{matrix} ϕ_{i} (x_{1}) \\ ⋮ \\ ϕ_{i} (x_{n}) \end{matrix}] \end{matrix}

여기서 식 (1) 우변의 행렬은 $n \times n$ 크기의 행렬이며, 이를 Gram matrix 라고 부릅니다. 이는 커널 함수에 데이터 포인트들을 대입하여 계산한 행렬로 이해할 수 있습니다. 이때, $K$ 의 고유값분해는 다음과 같이 나타낼 수 있습니다.

\begin{matrix} (2) & λ_{i}^{mat} u_{i} = K u_{i} \end{matrix}

$λ_{i}^{mat}, u_{i}$ 는 각각 Gram matrix $K$ 의 고유값과 고유벡터입니다. 그러면, 식 (1)과 식 (2)의 관계로부터 $λ_{i} = λ_{i}^{mat} / n$ 임을 알 수 있습니다. 즉, 커널함수의 고유값을 Gram matrix의 고유값으로 추정할 수 있습니다.

나아가, 고유함수 $ϕ_{i}$ 역시 다음과 같이 근사할 수 있습니다.

ϕ_{i} (x) ≃ \frac{\sqrt{n}}{λ_{i}^{mat}} k (x^{'})^{⊤} u_{i}

이때, $k (x^{'})$ 는 $x^{'}$ 에 대한 커널 벡터^{kernel vector}로, 다음과 같이 정의됩니다.

k (x^{'}) = [\begin{matrix} k (x_{1}, x^{'}) \\ ⋮ \\ k (x_{n}, x^{'}) \end{matrix}]

특히, 데이터 샘플 $x_{j}$ 에 대해서는 $ϕ_{i} (x_{j}) = \sqrt{n} (u_{i})_{j}$ 임을 알 수 있습니다. 이는 고유벡터의 $j$ 번째 원소에 $\sqrt{n}$ 을 곱한 것과 같습니다.

이러한 방법론을 Nyström method라고 부릅니다. 요약하자면, Nyström method는 데이터 샘플을 이용하여 Gram matrix의 고유값과 고유벡터를 구하고, 이를 이용하여 고유함수를 추정합니다.

Reproducing Kernel Hilbert SpacePermalink

이전에 커널 트릭을 설명하기 위해 RKHS^{Reproducing Kernel Hilbert Space}와 representer theorem에 대해 다룬 바 있습니다. 해당 포스트에서는 reproducing kernel map construction 을 통해 RKHS를 정의하였습니다. 여기서는 고유함수를 이용해 RKHS를 정의하는 방법에 대해 다루어보도록 하겠습니다.

RKHSPermalink

실함수 $f$ 들로 구성된 힐베르트 공간(완비내적공간) $H$ 의 내적이 $⟨ \cdot, \cdot ⟩_{H}$ 이고, 함수 $k : X \times X \to R$ 이 존재하여 다음 두 조건을 만족하는 경우,

모든 $x \in X$ 에 대해 $k (x, \cdot) \in H$
Reproducing property : 모든 $x \in X$ 와 $f \in H$ 에 대해 다음이 성립합니다.
$f (x) = ⟨ f, k (x, \cdot) ⟩_{H}$

$H$ 를 RKHS^{재생커널힐베르트공간}라고 부릅니다. 또한, $k$ 를 재생커널^{reproducing kernel}이라고 부릅니다.

Moore-Aronszajn TheoremPermalink

RKHS $H$ 이 존재하면, 이에 대응하는 커널 함수 $k$ 가 유일하게 존재합니다. 또한, 커널 함수 $k$ 가 존재하면, 이에 대응하는 RKHS $H$ 가 유일하게 존재합니다. 이를 Moore-Aronszajn theorem이라고 부릅니다.

RKHS using EigenfunctionsPermalink

이제 고유함수를 바탕으로 RKHS를 다시 살펴보도록 하겠습니다. 우선, 임의의 커널 함수 $k$ 는 다음과 같이 표현될 수 있습니다. (여기서는 유한개의 고유함수를 가정합니다)

k (x, x^{'}) = \sum_{i = 1}^{N} λ_{i} ϕ_{i} (x) ϕ_{i} (x^{'})

이때, 고유함수 $ϕ_{i}$ 들은 함수공간의 정규직교 기저를 형성합니다. 즉, 다음이 성립합니다.

⟨ ϕ_{i}, ϕ_{j} ⟩_{H} =: \int ϕ_{i} (x) ϕ_{j} (x) d μ = δ_{i j}

그렇다면, $ϕ_{i}$ 들을 기저로 하여, 이들의 선형결합으로 힐베르트공간 $H$ 을 구성할 수 있습니다.

f (x) = \sum_{i = 1}^{N} f_{i} ϕ_{i} (x), \sum_{i} f_{i}^{2} / λ_{i} < \infty

이때, $H$ 의 원소 $f, g$ 에 대해 내적을 다음과 같이 정의할 수 있습니다. (내적의 성질을 만족합니다)

⟨ f, g ⟩_{H} = \sum_{i = 1}^{N} \frac{f_{i} g_{i}}{λ_{i}}

이렇게 정의한 힐베르트공간 $H$ 는, reproducing property를 만족합니다.

⟨ f, k (x, \cdot) ⟩_{H} = \sum_{i = 1}^{N} \frac{f_{i} λ_{i} ϕ_{i} (x)}{λ_{i}} = f (x)

마찬가지로,

⟨ k (x, \cdot), k (x^{'}, \cdot) ⟩_{H} = k (x, x^{'})

역시 성립합니다. 이러한 관계로부터, 고유함수를 기저로 하는 힐베르트공간 $H$ 이 RKHS임을 알 수 있습니다.

ReferencesPermalink

Williams, C. K., & Rasmussen, C. E. (2006). Gaussian processes for machine learning (Vol. 2, No. 3, p. 4). Cambridge, MA: MIT press.