Introduction

• Linear SVM에서 dual problem은 오직 input 벡터의 내적(inner product)에만 의존한다.
• Linear SVM은 feature map과 kernel의 개념을 도입하여 Nonlinear SVM으로 확장된다.
• However, this extension lacks of theoretical foundation.
• Why?
  1. Dual problem은 유한차원의 문제(finite dimensional problem)에서만 정의된다. 하지만 흔히 알려진 커널(e.g. gaussian kernel, neural network kernel)들은 feature space의 차원이 무한하고, 따라서 dual problem이 잘 정의되지 않는다.
  2. Hinge loss 외의 다른 손실함수에 대해서는 커널 트릭을 어떻게 적용해야하는지가 불분명하다.
  3. It is not clear what the class of function space is used.
• 그리고 Reproducing Kernel Hilbert Space (RKHS) 이론은 커널 트릭에 대한 견고한 이론적 기반을 마련해준다!

Idea
함수의 모양이 점점 복잡해질수록, 함수를 추정하기 위해 알아야 하는 데이터의 수가 많아진다. 간단한 선형 함수를 예로 들면 직선위의 두 점만 알아도 함수를 추정할 수 있다. 함수가 smooth할수록 함수를 추정하기가 쉬워지는 것이다. 이는 가능한 함수의 공간이 크지 않기 때문이기도 하다. 하지만 함수의 모양이 복잡해지면, 즉 가능한 함수의 공간(abstract space)이 점점 커지면, 유한한 데이터로는 추정할 수 없게 되는 문제가 발생한다. 따라서 복잡한 함수를 추정할 때에는 충분히 다양한 함수를 포함하면서도 finite sample로 추정할 수 있는 함수의 공간이 필요하다. (여기서 어떻게 RKHS로 이어지는지는 나도 아직 설명할 수 있을만큼 이해를 하지는 못했다.. 이해하면 추가해서 올리는 걸로..!)

Review of Hilbert space

Hilbert space

힐버트 공간은 1. complete 2. inner product 3. linear 의 세 조건을 충족하는 공간이다. 완비성을 갖춘 내적이 정의된 벡터 공간이라는 것이다.

각 조건을 하나씩 살펴보자.

1. Linear space
   조건 : $\mathcal{H}$에 속하는 임의의 두 원소 $\mathbf{x}$, $\mathbf{y}$에 대해 다음이 성립한다.
   \(\alpha\mathbf{x} + \beta\mathbf{y} \in \mathcal{H}, (\alpha, \beta :{ scalar})\)
   다시 말해 선형 공간이라는 것은, 임의의 두 원소의 선형 결합도 원소로 가지고 있어야 한다는 것이다.
2. Inner product
   힐버트 공간에서는 내적으로 metric을 정의한다.¹
   조건 : 내적 $<\mathbf{x},\mathbf{y}>$는 $\mathcal{H} \times \mathcal{H}$ 에서 $\mathbb{R}$ 로의 bilinear positive definite kernel 이다.
   • bilinear : $\mathbf{x}$, $\mathbf{y}$ 둘중 하나를 고정하면 다른 하나에 대한 linear 함수.
   • positive definite
     • \(\sum_{i=1}^n {\sum_{j_1}^n{c_ic_jK(x_i, x_j)}} \geq 0\)
       $\text{for any } n \in \mathbb{N}$
       $x_1, \cdots, x_n \in \mathcal{H}$
       $c_1, \cdots , c_n \in \mathbb{R}$

3. Complete
   조건 : $\mathcal{H}$ 내의 어떠한 Cauchy sequence도 $\mathcal{H}$ 내의 원소로 수렴한다.

   참고

   • Complete metric space (완비 거리 공간)
     • 그 안이나 경계에 빠진 점이 없는 공간
     • 거리 위상을 갖춘 벡터 공간에서 극한을 제약없이 활용하려면 완비성 조건이 필요하다고 한다.
   • Cauchy sequence
     • 점들 사이의 거이가 점점 가까워지는 점렬
     • 처음의 유한개의 점들을 제외하면, 남은 점들 사이의 거리가 점점 작아져야한다.
   • Cauchy sequence처럼 수렴하는 것처럼 보이는 점렬들이 실제로 수렴하는 값을 가지는 거리 공간을 Complete하다고 표현한다.
   • Complete metric space에서는 ‘수렴’의 조건이 오직 수열의 값에만 의존하게 된다. (the criterion for convergence depends only on the terms of the sequence itself)²

예) 유클리드 공간, $L_2$ 공간

Reproducing kernel Hilbert space

• Let $k : \mathcal{X} \times \mathcal{X} \to R$ be a given Mercer kernel.
• $\mathcal{F}_k$ : $k$로부터 생성된 RKHS (Reproducing kernel Hilbert space)
• $\mathcal{F}_k$는 ${k(\mathbf{x}, \cdot) : \mathbf{x} \in \mathcal{X} }$의 linear span space이다.
• 이때 내적은 아래와 같이 정의 된다.

Reproducing property

For any $f\in\mathcal{F}_k$,

Proof
Let $f(\cdot) = k(\mathbf{x}, \cdot)$ Then $f(\cdot) = \sum_{i=1}^r{\alpha_ik(\mathbf{x}_i, \cdot)}$

\[\begin{align} \ &<f, k(\mathbf{x}, \cdot)> \\ \ &= <\sum_{i=1}^r{\alpha_ik(\mathbf{x}_i, \cdot)}, k(\mathbf{x}, \cdot)> \\ \ &= \sum_{i=1}^r{\alpha_ik(\mathbf{x}_i, \mathbf{x})} \\ \ &= f(\mathbf{x}) \end{align}\]

참고 자료

• 고급 데이터마이닝 방법 및 실습 (김용대 교수님) 강의 자료
• Brain’s Pick : 단어 간 유사도 파악 방법
• Hilbert space - Wikipedia
• Wasserstein GAN 수학 이해하기 I