Linear Regression
linear regression은 데이터의 선형 관계를 추론하는 linear model이다. 입력 \(x \in \mathbb{R}^d\)와, 출력 \(y \in \mathbb{R}\)에 대한 linear model \(h_\theta\)는 아래와 같이 표현할 수 있다.
$$ h_\theta(x) = \theta_0 + \theta_1 x_1 + \dots + \theta_dx_d $$
\(\theta_i\)는 학습 시 업데이트되는 파라미터(or weights)이다. vector notation을 사용하면 아래와 같이 쓸 수 있다.
$$ h_\theta (x) = \sum_{j=0}^d {\theta_jx_j} = \theta^{\intercal} x $$
이때 파라미터 \(\theta\)의 cost function은 다음과 같다.
$$ J(\theta) = \frac{1}{2} \sum_{i=1}^n {(h_\theta (x^{(i)}) - y^{(i)})^2} $$
\(\frac{1}{2}\)을 곱하는 이유는 미분 계산의 편의를 위해서다. 위 cost function을 최적화하는 다양한 방법이 있지만 우린 Gradient Descent algorithm을 활용한 최적화 방법을 알아볼 것이다.
$$ \frac{\partial J}{\partial \theta} = \sum_{i=1}^n(h_\theta(x^{(i)}) - y^{(i)}) \ x^{(i)} $$
따라서 \(\theta\)를 업데이트하는 수식은 아래와 같다.
$$ \theta \leftarrow \theta - \alpha \sum_{i=1}^n(h_\theta(x^{(i)}) - y^{(i)}) \ x^{(i)} $$
Basis Functions
위의 linear model은 선형 관계만 표현할 수 있다. 모델에 비선형성을 주기 위해 basis function(\(\phi_l\))을 사용한다: \(\{ \phi_l \in \mathbb{R}^d \rightarrow \mathbb{R} | l=1, \dots, L \}\)
$$ h_\theta (x) = \sum_{l=0}^{L}\theta_l\phi_l(x) = \theta^\intercal \phi(x) $$
여기서 \(x\)는 vector임에 유의해야 한다. 기존 linear model에서는 \(h_\theta (x) = \theta^{\intercal} x\)로 표현되던 것에서, \(x\)가 basis functions를 거치도록 바뀌었다. \(\phi_l\)은 하나의 basis function을 의미하고, \(\phi\)는 모든 basis function을 vector 형태로 나열한 vector function이다. 즉, \(\phi \in \mathbb{R}^d \rightarrow \mathbb{R}^L\)이다.
\(\phi\)는 \(x\)를 비선형으로 변환하는 함수이다. 대표적으로 polynomial basis functions가 있다:
$$ \phi(x) = [1;x_1;x_2;\dots;x_1^2;x_1x_2;\dots;x_1^3;x_1^2x_2;\dots] $$
위 수식처럼 polynomial basis functions는 vector \(x\)의 각 element를 곱하여 \(L\)개의 항을 만든다. 모든 항을 선형 결합하면 \(h_\theta\)가 되고, 선형을 벗어나 더 높은 차원의 표현력을 갖게 된다.
이제 업데이트 수식을 구해보자. 역시 Gradeint Descent를 사용한다.
$$ J(\theta) = \frac{1}{2} \sum_{i=1}^n {(h_\theta (x^{(i)}) - y^{(i)})^2} $$
$$ \begin{align} \frac{\partial J}{\partial \theta} & = \sum_{i=1}^n{(h_\theta(x^{(i)}) - y^{(i)}) \ \phi(x^{(i)})} \nonumber \\ & = \sum_{i=1}^n{(\theta^\intercal \phi(x^{(i)}) - y^{(i)}) \ \phi(x^{(i)})} \nonumber \end{align} $$
따라서
$$ \theta \leftarrow \theta - \alpha \sum_{i=1}^n{(\theta^\intercal \phi(x^{(i)}) - y^{(i)}) \ \phi(x^{(i)})} $$
Kernel Trick
위 업데이트 식을 다른 시각에서 바라보자. simplicity를 위해 \(\theta\)의 초깃값은 \(0\)으로 가정해보자. 그렇다면 결국 \(\theta\)는 \(\phi(x^{(1)}), \dots, \phi(x^{(N)})\)의 선형 결합으로 표현할 수 있게 된다. 이 선형 결합의 계수를 \(\beta_i\)로 표현한다면 \(\theta\)를 아래 수식처럼 표현할 수 있다.
$$ \theta = \sum^N_{i=1}{\beta_i \cdot \phi(x^{(i)})} $$
그렇다면 업데이트 식은 이렇게 된다:
$$ \begin{align} \theta \leftarrow & \ \theta - \alpha \sum_{i=1}^n{(\theta^\intercal \phi(x^{(i)}) - y^{(i)}) \ \phi(x^{(i)})} \nonumber \\ = & \ \sum^N_{i=1}{\beta_i \cdot \phi(x^{(i)})} - \alpha \sum_{i=1}^n{(\theta^\intercal \phi(x^{(i)}) - y^{(i)}) \ \phi(x^{(i)})} \nonumber \\ = & \ \sum^N_{i=1}{(\beta_i - \alpha (\theta^\intercal \phi(x^{(i)}) - y^{(i)})) \ \phi(x^{(i)})} \nonumber \end{align} $$
\(\theta\)의 업데이트 결과가 또다시 \(\phi(x^{(1)}), \dots, \phi(x^{(N)})\)의 선형 결합으로 표현된다. 그리고 이때의 선형결합 계수(\(\beta_i - \alpha (\theta^\intercal \phi(x^{(i)}) - y^{(i)})\))는 새로운 \(\beta_i\)가 된다. 따라서 아래 수식으로 \(\beta_i\)를 업데이트할 수있다.
$$ \begin{align} \beta_i \leftarrow & \ \beta_i - \alpha (\theta^\intercal \phi(x^{(i)}) - y^{(i)}) \nonumber \\ = & \ \beta_i - \alpha (\Sigma^N_{j=1}{\beta_j \phi(x^{(j)})^\intercal} \phi(x^{(i)}) - y^{(i)}) \nonumber \end{align} $$
사실 난 개인적으로 이 부분에서 놀랐다. GD 업데이트 식을 선형결합으로 해석하고, 나아가 선형결합 계수의 업데이트 식을 유도해내는 아이디어가 정말 대단하다. 나도 언젠가 이런 아이디어를 스스로 생각해낼 수 있게 되길 바라며.. 계속하겠다.
위 업데이트 수식에 새로운 함수 \(K(x, z) = \phi(x)^\intercal \phi(z)\)를 도입하여 대입하면:
$$ \beta_i \leftarrow \beta_i - \alpha (\Sigma^N_{j=1}{\beta_j K(x^{(j)}, x^{(i)})} - y^{(i)}) $$
이렇게 \(K\)를 도입하면 계산량을 줄일 수 있다. 모든 \(K(x^{(j)}, x^{(i)})\)의 값을 한번만 구해두면 \(\beta_i\)를 업데이트할 때마다 사용할 수 있다. 다시 \(K\)를 구할 필요가 없으므로 중복 계산을 피할 수 있게 된다. 이 함수 \(K\)를 Kernel이라고 부른다.
Generalizing
조금 더 생각해보자. kernel function(\(K\))을 도입하면 학습(파라미터 업데이트) 시 \(\phi\) 함수를 직접적으로 사용할 일이 없어진다. 미리 구해둔 \(K\) 값을 사용하면 되기 때문이다. \(\beta_i\)를 업데이트할 때도 마찬가지다. 추론 시에도 아래 수식처럼 입력 \(x'\)에 대해 \(\beta_i\)와 \(K\) 값만으로 \(y\)를 추론할 수 있다.
$$ h_\theta (x') = \theta^\intercal \phi(x') = \sum^N_{i=1}{\beta_i \cdot \phi(x^{(i)})^\intercal \phi(x')} = \sum^N_{i=1}{\beta_i \cdot K(x^{(i)}, x')} $$
그렇다면 \(\phi\) 함수는 \(K\) 값을 미리 구해둘 때만 필요하다. 우리는 여기서 \(K\)를 구할 때마저도 \(\phi\) 함수의 역할을 제외시킬 것이다. 아래 예시를 보자.
$$ \phi(x) = [x_1x_1; x_1x_2; \dots; x_1x_d; x_2x_1;x_2x_2; \dots; x_dx_1; \dots x_dx_d] $$
위와같은 polynomial basis functions를 정의한다. 일반적으로 \(x,z \in \mathbb{R}^d\)일 때 \(K(x, z)\) 값을 구하려면, \(\phi(x)\)와 \(\phi(z)\)를 각각 구하고 이 둘을 내적해야 한다. 하지만 아래 수식처럼 \(K(x,z)\)의 값을 바로 구할 수도 있다.
$$ \begin{align} K(x,y) & = \phi(x)^\intercal\phi(z) \nonumber \\ & = \sum_{i=1}^d \sum_{j=1}^d {x_ix_jz_iz_j} \nonumber \\ & = \sum_{i=1}^d \sum_{j=1}^d {(x_ix_j)(z_iz_j)} \nonumber \end{align} $$
이렇게 \(\phi\)를 거치지 않고 \(K(x, z)\) 값을 바로 구할 수 있다. 이제 \(\phi \) 함수는 신경쓰지 않아도 된다. 오로지 \(K\)만으로 모든 계산이 가능해지게 되었다.
조금 주제를 돌려, \(K\) 함수의 역할을 조금 더 생각해보자. \(K(x, z)=\phi(x)^\intercal\phi(z)\)에서 \(K\)는 \(\phi(x)\)와 \(\phi(z)\)의 유사도를 나타내는 함수(similarity metric)로도 해석할 수 있다. 여기서 힌트를 얻어 새로운 \(K\) 함수식을 만들어낼 수 있다. 이전 예시에서는 basis functions(\(\phi\))를 먼저 정하고 kernel function(\(K\)) 함수식을 유도했다면, 이번에는 유사도를 나타내는 함수라는 힌트를 바탕으로 \(K\) 함수식을 먼저 정할 것이다.
이런 방식으로 구한 대표적인 커널 중 하나는 Gaussian kernel이다.
$$ K(x, z) = \exp(-\frac{\Vert x-z\Vert^2}{2\sigma^2}) $$
위 커널의 basis functions(\(\phi\))는 무엇일까? 그 전 예시에서는 basis functions로부터 \(K\)를 유도했기에 그 과정이 쉬웠다. 그러나 역으로 \(K\) 함수식으로부터 \(\phi\)를 구하는 것은 쉽지 않다. Gaussian kernel의 경우 Taylor series expansion을 통해 \(\phi\)를 구할 수 있다.
$$ \begin{align} K(x, z) & = \exp(-\frac{\Vert x-z \Vert ^2}{2\sigma^2}) \nonumber \\ & = \prod_{i=1}^d{\exp(-\frac{(x_i-z_i)^2}{2\sigma^2})} \nonumber \\ & = \prod_{i=1}^d{\exp(-\frac{x_i^2-2x_iz_i+z_i^2}{2\sigma^2})} \nonumber \\ & = \prod_{i=1}^d{\left(\exp(-\frac{x_i^2+z_i^2}{2\sigma^2}) \cdot \left(1 + \frac{1}{1!}\frac{x_iz_i}{\sigma^2} + \frac{1}{2!}\left(\frac{x_iz_i}{\sigma^2}\right)^2 + \frac{1}{3!}\left(\frac{x_iz_i}{\sigma^2} \right) ^3 + \cdots \right)\right)} \nonumber \\ & = \prod_{i=1}^d{\left(\exp(-\frac{x_i^2+z_i^2}{2\sigma^2}) \cdot \left(1 + \sqrt{\frac{1}{1! \sigma^2}}x_i \cdot \sqrt{\frac{1}{1! \sigma^2}}z_i + \sqrt{\frac{1}{2! \sigma^4}}x_i^2 \cdot \sqrt{\frac{1}{2! \sigma^4}}z_i^2 + \sqrt{\frac{1}{3! \sigma^6}}x_i^3 \cdot \sqrt{\frac{1}{3! \sigma^6}}z_i^3 + \cdots \right)\right)} \nonumber \\ & = \prod_{i=1}^d{\left(\exp(-\frac{x_i^2+z_i^2}{2\sigma^2}) \cdot \sum_{n=0}^\infty{\sqrt{\frac{1}{n! \sigma^2n}}x_i^n \cdot \sqrt{\frac{1}{n! \sigma^2n}}z_i^n} \right)} \nonumber \\ & = \prod_{i=1}^d{\left(\sum_{n=0}^\infty{\exp(-\frac{x_i^2}{2\sigma^2}) \cdot \sqrt{\frac{1}{n! \sigma^{2n}}}x_i^n \cdot \exp(-\frac{z_i^2}{2\sigma^2}) \cdot \sqrt{\frac{1}{n! \sigma^{2n}}}z_i^n} \right) } \nonumber \\ & = \sum_{n=0}^\infty{\prod_{i=1}^d{\left(\exp(-\frac{x_i^2}{2\sigma^2}) \cdot \sqrt{\frac{1}{n! \sigma^{2n}}}x_i^n \right) } \cdot \prod_{i=1}^d{\left(\exp(-\frac{z_i^2}{2\sigma^2}) \cdot \sqrt{\frac{1}{n! \sigma^{2n}}}z_i^n \right) }} \nonumber \end{align} $$
따라서,
$$ \begin{align} \phi_l(x) & = \prod_{i=1}^d{\left(\exp(-\frac{x_i^2}{2\sigma^2}) \cdot \sqrt{\frac{1}{l! \sigma^{2l}}}x_i^l \right)} \ \ \ \forall l \in \{1, 2, \dots\} \nonumber \\ \nonumber \\ \phi(x_i) & = [\phi_1(x); \phi_2(x); \phi_3(x); \dots] \nonumber \end{align} $$
이는 basis functions \(\phi\)가 입력 \(x\)를 무한한 차원의 벡터로 매핑한다는 뜻이다.
세상에는 Gaussian kernel 외에도 참 많은 커널 함수들이 있다. 이 모든 함수의 basis functions를 구할 수 있을까? 일반적으로 매우 어렵거나 불가능하다. 그리고 애초에 구할 필요가 없다. basis functions를 몰라도 \(K\) 함수 만으로 충분히 학습과 추론을 할 수 있기 때문이다.
Kernel의 조건과 추가적인 해석은 2편에서 다루도록 하겠다.