6.1. Dual Representations

Linear regression (with $L_2$ regularization) 의 loss function은 흔히 다음과 같이 표현된다.

$\mathcal{L}(w) = {1 \over 2} \displaystyle\sum_{n=1}^N{\{w^T \phi(x_n) - t_n\}^2} + {\lambda \over 2} w^T w$, where $\lambda \geq 0$

 

여기서 중요한 부분은 $\phi(x_n)$, 즉 어떠한 mapping으로 $x_n$을 표현할 것인가?이다. 예를 들어, $\phi(x_n) = [1, x, x^2]^T$로 두면, 우리의 model은 $w^T \phi(x_n) = w_0 + w_1 x_n + w_2 x_n^2$이 되어 우리는 2차 함수로의 regression을 하고자 하는 것이다.

 

한편, $\phi(x_n)$에는 한계가 있다. 바로 급수와 같은 "무한"의 개념을 다룰 수 없다는 것이다.

 

Dual representation과 kernel trick의 목표는 loss가 minimum일 때의 $\phi(x_n)$를 잘 변형해서 더 다양한 함수(급수를 포함하여)를 다루는 것이다.

 

다시 regression으로 돌아와서, regression의 목표는 loss function을 최소화하는 것이므로, ${{d\mathcal{L}(w)} \over dw}=0$을 푼 결과가 우리가 원하는 $w$값이 될 것이다.

${{d\mathcal{L}(w)} \over dw} = \displaystyle\sum_{n=1}^N{\{w^T \phi(x_n) - t_n\}\phi(x_n)} + \lambda w = 0$

$\therefore w = - {1 \over \lambda} \displaystyle \sum_{n=1}^N {\{w^T \phi(x_n) - t_n\}\phi(x_n)}$

 

식을 단순한 형태로 바꾸면, $w = \Phi^T a$, where $\Phi^T = [\phi(x_1) \cdots \phi(x_N)]$, $a = (a_1 ,\cdots, a_N)^T$, with $a_n = -{1 \over \lambda} \{w^T \phi(x_n ) - t_n \}$이 된다.

 

우리는 $w=$argmin$_w \mathcal{L}(w)$를 $\Phi$와 새로운 parameter $a$를 이용해서 표현할 수 있게 되었다. 그 결과, $w$를 $\Phi a$로 치환하게 되면, $\mathcal{L}$의 minimum value는

$\mathcal{L}(a) = {1\over2} \displaystyle\sum_{n=1}^N {\{ a^T \Phi \phi(x_n) - t_n\}^2} + {\lambda \over 2} a^T \Phi \Phi^T a$

        $={1\over2}a^T \Phi \Phi^T \Phi \Phi^T a - a^T \Phi \Phi^T t + {1 \over 2} t^T t + {\lambda \over 2} a^T \Phi \Phi^T a$이 된다. ($t = (t_1, \cdots , t_N)^T$)

 

잘 살펴보면, optimization이 된 $\mathcal{L}(a)$는 $\Phi \Phi^T$, $a$, $t$로 구성된 것을 볼 수 있다.

여기서 정의를 하나 하게 된다.

 

Def. Gram matrix $K$ is the $N\times N$ symmetric matrix with $[K]_{i,j} = \phi(x_i)^T \phi(x_j)$

 

이렇게 하면, loss function을 $\mathcal{L}(a) = {1 \over 2} a^T KK a - a^T K t + {1 \over 2} t^T t + {\lambda \over 2} a^T K a$로 표현할 수 있게 된다.

 

$a$ 또한 K를 이용해서 표현할 수 있다.

$a = -{1 \over \lambda} \{w^T \Phi^T - t\} = -{1\over \lambda} \{a^T \Phi \Phi^T - t\} = -{1 \over \lambda}\{a^T K - t\}$

$\Rightarrow$ $(I_N + {1 \over \lambda}K)a = {1 \over \lambda} t$

$\Rightarrow$ $a = (K + \lambda I_N)^{-1} t$

 

단순히 치환만 해보면, Gram matrix의 중요성이 잘 보이지 않는다. 그러나 Gram matrix의 element를 $\phi(x_i)^T \phi(x_j)$가 아닌 $k(x_i, x_j)$라는 kernel function(이후 다루게 될 내용)으로 정의하게 되면, $k(x_i, x_j)$를 어떻게 정의하느냐에 따라 우리가 관심가지고 있는 $\phi(x)$의 값이 다를 것이다. 즉, 우리는 $\phi(x)$ 대신 kernel function을 이용할 수 있게 되었다.