표현자 정리 증명 📂머신러닝

표현자 정리 증명

정리

인풋 집합^{input set} $X \ne \emptyset$ 과 양정부호 커널 $k: X \times X \to \mathbb{R}$ 이 주어져 있다고 하자. 학습데이터셋^{training Dataset}을 $$ D := \left\{ \left( x_{i} , y_{i} \right) \right\}_{i=1}^{m} \subset X \times \mathbb{R} $$ 라 하고, 재생 커널 힐베르트 공간 $H_{k}$ 의 클래스 $$ \mathcal{F} := \left\{ f \in \mathbb{R}^{X} : f \left( \cdot \right) = \sum_{i=1}^{\infty} \beta_{i} k \left( \cdot , z_{i} \right) \land \beta_{i} \in \mathbb{R} \land z_{i} \in X \land \left\| f \right\| < \infty \right\} \subset H_{k} $$ 를 위와 같이 둔다. 임의의 목적 함수 $c : \left( D \times \mathbb{R} \right) ^{m} \to \overline{\mathbb{R}}$ 과 단조증가함수인 레귤라이저^regulizer $g : \mathbb{R} \to [0,\infty)$ 에 대해 다음과 같이 정칙화된 대상 범함수^{regulized Objective Functional} $L : \mathcal{F} \to \overline{\mathbb{R}}$ 이 정의되어 있다고 하자. $$ L (f) := c \left( \left( x_{1}, y_{1}, f \left( x_{1} \right) \right), \cdots , \left( x_{m}, y_{m}, f \left( x_{m} \right) \right) \right) + g \left( \left\| f \right\| \right) $$ 여기서 $H_{k}$ 의 놈 $\left\| \cdot \right\|$ 은 $k$ 의 양정부호성^{positive Definiteness}에 따라 다음과 같이 주어진다. $$ \left\| \sum_{i=1}^{\infty} \beta_{i} k \left( \cdot , z_{i} \right) \right\|^{2} := \sum_{i=1}^{\infty} \sum_{j=1}^{\infty} \beta_{i} \beta_{j} k \left( z_{i} , z_{j} \right) \ge 0 $$

$\mathbb{R}$ 은 실수의 집합이고, $\overline{\mathbb{R}}$ 은 무한대 $\infty$ 를 포함하는 확장 실수다.
$\mathbb{R}^{X}$ 는 정의역이 $X$ 고 공역이 $\mathbb{R}$ 인 함수를 모아놓은 함수공간이다.
레귤라이저란 데이터에 대한 오버피팅을 방지하기 위한 페널티^penalty 함수다.
범함수란 엄밀하지 않게 대충 말하자면 함수 자체를 인풋으로 받아들이는 함수다.

비모수^{nonparametric}

$L (f)$ 를 최소화하는 함수 $f \in \mathcal{F}$ 는 어떤 $\left\{ \alpha_{i} \right\}_{i=1}^{m} \subset \mathbb{R}$ 에 대해 다음과 같은 꼴로 나타난다. $$ f (\cdot) = \sum_{i=1}^{m} \alpha_{i} k \left( \cdot , x_{i} \right) $$

반모수^{semiparametric}

$X$ 에서 정의된 $M$ 개의 실함수의 집합을 $\left\{ \psi_{p} : X \to \mathbb{R} \right\}_{p=1}^{M}$ 에 대해 행렬 $\left( \psi_{p} \left( x_{i} \right) \right)_{ip}$ 의 랭크가 $M$ 이라고 하자. 그러면 $f \in \mathcal{F}$ 와 $h \in \span \left\{ \psi_{p} \right\}$ 에 대해 $$ c \left( \left( x_{1}, y_{1}, \tilde{f} \left( x_{1} \right) \right) , \cdots , \left( x_{m}, y_{m}, \tilde{f} \left( x_{m} \right) \right) \right) + g \left( \left\| f \right\| \right) $$ 를 최소화하는 $\tilde{f} = f + h$ 는 어떤 $\left\{ \alpha_{i} \right\}_{i=1}^{m}, \left\{ \beta_{p} \right\}_{p=1}^{M} \subset \mathbb{R}$ 에 대해 다음과 같은 꼴로 나타난다. $$ \tilde{f} (\cdot) = \sum_{i=1}^{m} \alpha_{i} k \left( \cdot , x_{i} \right) + \sum_{p=1}^{M} \beta_{p} \psi_{p} (\cdot) $$

설명

가능하다면 다음 두 포스트를 먼저 읽어보는 것을 추천한다:

표현자

표현자 정리^{representer theorem}은 고전적 머신러닝, 특히 서포트벡터머신의 맥락에서 가장 중요한 정리 중 하나로써 주어진 데이터에 대해 우리가 근사시키고 싶은 목적 함수 $f$ 가 적절한 커널 $k$ 에 대해 $$ f (\cdot) = \sum_{i=1}^{m} \alpha_{i} k \left( \cdot , x_{i} \right) $$ 와 같은 꼴로 나타난다고 하는 강력한 정리다. 여기서 커널의 인풋 중 하나가 $x_{i}$ 로 픽스된 함수 $$ k \left( \cdot , x_{i} \right) = \phi \left( x_{i} \right) (\cdot)\in H_{k} $$ 을 표현자^representer라 부른다. 이에 따르면 표현자 정리는 ‘재생 커널 힐베르트 공간에서 학습데이터에 적합한^fitted 임의의 함수는 표현자들의 유한한 선형결합으로 나타낼 수 있다’고 요약할 수 있겠다. 특히 비선형회귀를 위한 서포트벡터 머신의 커널 트릭은 이에 정확히 부합한다.

이는 딥러닝과 시벤코 정리의 관계와 유사하다.

데이터 과학의 맥락에서 표현자 $\phi \left( x_{i} \right) (\cdot)$ 는 피쳐 맵^{feature map}이라고도 불리는데, 임의의 데이터 $X$ 를 우리가 그 특징^feature을 알 수 있는 힐베르트공간으로 옮기고 그 유한한 합으로 우리가 원하는 함수를 표현할 수 있다는 말은 그동안 우리가 배워온 많은 머신러닝 기법들이 왜 작동해왔는지를 정당화한다. 물론 수학적 보장이 없더라도 그 기법들은 기법 그 자체로써 유효하지만, 표현자 정리가 있음으로써 그 기법들이 이론적 기반을 다지게 된다는 점에서 아주 중요하다.

목적 함수와 레귤라이저

정리의 스테이트먼트에서는 목적 함수 $c$ 와 레귤라이저 $g$ 를 아주 일반적으로 정의했지만, 실질적으로 많은 경우에 $c$ 는 데이터와 $f$ 의 적합도를 측정하는 평균잔차제곱, 즉 $$ c = {{ 1 } \over { m }} \sum_{i=1}^{n} \left( y_{i} - f \left( x_{i} \right) \right)^{2} $$ 로 보고 $g$ 는 제곱 세미 놈 페널티 $g \left( \left\| f \right\| \right) = \lambda \left\| f \right\|^{2}$ 로 보아도 무방하다¹.

주의해야할 점은 이 수식의 모양이나 단어의 의미만 보고 목적 함수와 레귤라이저를 구분해서는 안 된다는 것이다. 표현자 정리의 가장 대표적인 응용이 서포트 벡터 머신인데, 마진에 느슨한 허용을 주는 소프트 마진 SVM에서 다루는 최소화 문제는 다음과 같다. $$ \begin{matrix} \text{Minimize} & {{ 1 } \over { 2 }} \left\| \mathbf{w} \right\|_{2}^{2} + \lambda \sum_{k=1}^{n} \xi_{k} \\ \text{subject to} & \left| f \left( \mathbf{x}_{k} \right) \right| \ge 1 - \xi_{k} \\ & \xi_{k} \ge 0 \end{matrix} \\ k = 1, \cdots , n $$

여기서 최적화 그 자체만 생각했을 때 목적 함수는 상수 $\lambda \ne 0$ 에 대해 사실 $$ {{ 1 } \over { 2 \lambda }} \left\| \mathbf{w} \right\|_{2}^{2} + \sum_{k=1}^{n} \xi_{k} $$ 과 다름 없으며, 이 때는 데이터와의 괴리를 생각하는 $\sum_{k=1}^{n} \xi_{k}$ 가 $c$ 고 서포트 벡터 머신의 초평면 $f (\mathbf{x}) = \mathbf{w}^{T} + b$ 에서 유도되는 ${{ 1 } \over { 2 \lambda }} \left\| \mathbf{w} \right\|_{2}^{2}$ 가 $g$ 로 읽혀야한다. 이 최적화의 의미를 수학에 두느냐 머신러닝에 두느냐에 따라 헷갈릴 수 있는데,

수학의 색이 더 강한 사람은 SVM을 ‘일단 선형회귀를 끝낸 뒤 예외를 두는 것’으로 보기 때문에 $\left\| \mathbf{w} \right\|_{2}^{2}$ 를 먼저 최소화하려 하고
데이터과학의 색이 더 강한 사람은 SVM을 ‘우선 데이터를 잘 분류하는데에 성공하고, 그 중에서 가장 마진이 큰 초평면을 찾는 것’으로 보기 때문에 $\sum_{k=1}^{n} \xi_{k}$ 을 먼저 최소화하려고 하기 때문이다.

양쪽 다 충분히 공감할 수 있는 관점이고, 표현자 정리의 응용이 SVM 하나만 있는 것도 아니니 여기서는 뇌새김 암기법 같은 것을 찾으려 하지 말고 문제에 따라 능동적으로 사고하고 받아들여야한다.

증명 ²

참고문헌에 있는대로 비모수적 표현자 정리만 증명한다.

Part 1. $f = \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) + v$

재생커널의 정의: 함수 $k : X \times X \to \mathbb{C}$ 가 다음 두 조건을 만족하면 $H$ 의 재생 커널^{reproducing Kernel}이라 한다.
(i): 표현자^representer: 모든 $x \in X$ 에 대해 $$ k \left( \cdot , x \right) \in H $$
(ii) 재생 성질^{reproducing Property}: 모든 $x \in X$ 과 모든 $f \in H$ 에 대해 $$ \left< f , k \left( \cdot , x \right) \right> = f(x) = \delta_{x} (f) $$ 특히 모든 $x_{1} , x_{2} \in X$ 에 대해 다음이 성립한다. $$ k \left( x_{1} , x_{2} \right) = \left< k \left( \cdot , x_{2} \right), k \left( \cdot , x_{1} \right) \right> $$

재생커널 $k : X \times X \to \mathbb{R}$ 에 대해 $x \mapsto k (\cdot ,x)$ 인 (표현자) 함수 $\phi : X \to \mathbb{R}^{X}$ 를 정의하자. $k$ 는 재생커널이므로, $x' \in X$ 에서 함수 $\left( \phi (x) \right) (\cdot)$ 의 함수값은 모든 $x, x' \in X$ 에 대해 $$ \left( \phi (x) \right) (x ') = k \left( x' , x \right) = \left< \phi \left( x ' \right) , \phi (x) \right> $$ 이다. 여기서 $\left< \cdot , \cdot \right>$ 는 $H_{k}$ 의 내적이다. 주어진 $\left\{ x_{i} \right\}_{i=1}^{m}$ 에 대해 임의의 함수 $f \in \mathcal{F}$ 는 $\span \left\{ \phi \left( x_{i} \right) \right\}_{i=1}^{m}$ 의 부분과 그에 직교해서 모든 $j$ 에 대해 $$ \left< v , \phi \left( x_{j} \right) \right> = 0 $$ 를 만족하는 $v \in \mathcal{F}$ 와 어떤 $\left( \alpha_{1} , \cdots , \alpha_{m} \right) \subset \mathbb{R}^{m}$ 에 대해 다음과 같이 나타낼 수 있다. $$ f = \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) + v $$ 우리는 이제 $$ \begin{align*} L (f) :=& c \left( \left( x_{1}, y_{1}, f \left( x_{1} \right) \right), \cdots , \left( x_{m}, y_{m}, f \left( x_{m} \right) \right) \right) + g \left( \left\| f \right\| \right) \\ =& c + g \end{align*} $$ 에서 $c$ 는 $v$ 에 독립이며, $v = 0$ 일 때 $f$ 가 $L(f)$ 를 최소화함을 논할 것이다.

Part 2. $c$ 와 $v$ 는 독립이다

함수 $f = f(\cdot)$ 와 재생 커널 $k \left( \cdot , x_{j} \right)$ 의 내적은 재생 성질에 따라 $$ \begin{align*} =& \left< f , k \left( \cdot , x_{j} \right) \right> \\ f \left( x_{j} \right) =& \left< \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) + v , \phi \left( x_{j} \right) \right> \\ =& \sum_{i=1}^{m} \alpha_{i} \left< \phi \left( x_{i} \right) , \phi \left( x_{j} \right) \right> + 0 \end{align*} $$ 이다. 이는 $v$ 에 독립이므로, $L (f) = c + g$ 에서 학습데이터 $D$ 와 $f$ 에만 종속된 $$ c = c \left( \left( x_{1}, y_{1}, f \left( x_{1} \right) \right), \cdots , \left( x_{m}, y_{m}, f \left( x_{m} \right) \right) \right) $$ 역시 $v$ 에 독립임을 알 수 있다.

Part 3. $g$ 는 $v = 0$ 일 때 최소화된다

(1): $v$ 는 $\sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right)$ 에 직교하고
(2): $g$ 가 단조함수로 가정했으므로

$$ \begin{align*} & g \left( \left\| f \right\| \right) \\ =& g \left( \left\| \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) + v \right\| \right) \\ =& g \left( \sqrt{\left\| \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) + v \right\|^{2} + \left\| v \right\|^{2}} \right) & \because (1) \\ \ge& g \left( \left\| \sum_{i=1}^{m} \alpha_{i} \phi \left( x_{i} \right) \right\| \right) & \because (2) \end{align*} $$ 를 얻는다. 보다시피 $v = 0$ 일 때 등식이 성립하며, $g$ 가 최소화되려면 $v=0$ 이어야 한다. 한편 Part 2에서 $v$ 는 $c$ 에 영향을 끼칠 수 없음을 확인했으므로 $v = 0$ 으로 두어도 무방하고, $L = c + g$ 를 최소화하는 함수 $f$ 는 다음과 같은 꼴로 나타날 수 있게 된다. $$ f (\cdot) = \sum_{i=1}^{m} \alpha_{i} k \left( \cdot , x_{i} \right) $$

■

Wahba. (2019). Representer Theorem. https://pages.stat.wisc.edu/~wahba/ftp1/wahba.wang.2019submit.pdf ↩︎
Schölkopf. (2001). A Generalized Representer Theorem. https://link.springer.com/chapter/10.1007/3-540-44581-1_27 ↩︎