Lecture 7: Kernel Method

---

Non-linearity

 

우리는 linear regression을 할 때 선형적인 함수를 사용한다. 하지만, 모든 변수 간 관계가 선형적인 관계를 가지는 게 아니기 때문에, 때때로는 비선형적인 함수를 사용해야 할 때가 있다. 우리는 데이터를 비선형 함수를 이용해 feature-mapping해서 비선형성을 다룬다.

 

- $h_{\theta}\left ( x \right ) = \theta \times \phi \left ( x \right )$

 

여기서 함수 $h$는 $\theta$와 $\phi$에 대해서는 선형이고, $x$에 대해서는 선형이 아님을 알 수 있다. 그러므로 우리는 $\theta$와 $\phi$에 대해서 Linear regression을 할 수 있다.

 

Linear Regression

 

원소 $x$를 $\phi \left ( x \right )$로 바꾼다면 데이터는 $\left(x^{(i)}, y^{(i)}\right)$에서 $\left(\phi\left(x^{(i)}\right), y^{(i)}\right)$로 데이터를 변환할 수 있다. 이것은 선형 관계를 가지므로, MLE$($최소제곱법$)$를 이용해 Gradient Descent를 수행할 수 있다. 

 

하지만, Gradient Descent를 할 때 $\theta^T \phi \left( x^{(i)} \right)$를 구하는 연산을 수행해야 하는데, $\phi$의 차원이 $p$일 경우 계산의 시간복잡도는 $O\left(np\right)$가 된다. 일반적인 경우에 feature-mapping의 $p, n$이 $p >> n$이므로 계산 비용이 엄청나다. 이것을 적절하게 해결할 방법이 없을까?

 

Kernel Trick

 

우리는 kernel trick이라는 것을 통해 계산 비용을 줄일 수 있다. 핵심적인 관찰은 다음과 같다.

 

- $\theta = \sum_{i=1}^{n} (\beta_{i} \times \phi (x^{(i)})) (\beta_{i} \in \mathbb{R} )$. 즉 $\theta$는 항상 $\phi (x_i)$들의 선형 결합이다.

 

위에 대한 증명은 수학적 귀납법으로 가능하다.

 

iteration 0: $\theta = 0$

iteration 1: $\theta = \theta + \alpha \sum_{i=1}^{n} (y^{(i)} - \theta^T \phi (x_i)) \times \phi (x_i) = \alpha \sum_{i=1}^{n} y^{(i)} \times \phi (x_i) (\theta = 0)$. 즉 반복 전에 위의 명제가 성립하면, 첫 번째 반복 종료 후에도 위의 명제가 성립한다.

...

iteration t: $\theta = \sum \beta_{i} \times \phi (x_i)$

iteration t + 1: $\theta = \sum (\beta_{i} + \alpha (y^{(i)} - \theta^T \phi (x_i))) \times \phi (x_i) \rightarrow \phi (x_i)$ 앞에 있는 $(\beta_{i} + \alpha (y^{(i)} - \theta^T \phi (x_i)))$는 상수이므로 이 값이 새로운 $\beta_{i}$가 된다. 그러므로 t번째 반복 후에 위의 명제가 성립하면, t + 1번째 반복 후에도 위의 명제가 성립한다. 그러므로 위의 명제는 옳다.

 

그래서 어떻게?

 

$\beta$에 집중해서 업데이트해보자.

 

$\beta_{i} \leftarrow \beta_{i} + \alpha(y^{(i)} - \theta^T \phi (x_i))$

$ = \beta_{i} + \alpha (y ^{(i)} - (\sum_{j=1}^{n} \beta_{j} \phi(x_j))^T \phi(x_i))$

$ = \beta_{i} + \alpha (y ^{(i)} - \sum_{j=1}^{n} \beta_{j} <\phi(x_j), \phi(x_i)>)$

 

아직까지는 $O(np)$이다. 이것을 조금 더 개선하기 위해 더 생각해봐야 할 사실이 두 가지 있다.

 

1. $<\phi (x_j), \phi(x_i)>$는 미리 계산될 수 있다. $\leftarrow$ 모든 $i, j$에 대해서 미리 계산하고 저장하면 된다. 
2. $<\phi (x_j), \phi(x_i)>$는 많은 경우에 대해서 $\phi$에 대한 명시적인 평가 없이 계산될 수 있다.

2가 어떤 이야기냐면, 

 

$\phi(x) = [1, x_1, x_2, \cdots, x_n, x_{1}^2, \cdots ]$라 하자.

 

이때 $<\phi(x), \phi(z)>$를 전개해보면 

 

- $1 + \sum_{i}^{n} x_iz_i + \sum_{i, j}^{n} x_ix_jz_iz_j + \cdots$이다.

 

여기서 $\sum_{i}^{n} x_iz_i = <x, z>$인데, $\sum_{i,j}^{n} x_ix_jz_iz_j$ $= \sum_{i}^{n} x_iz_i \times \sum_{j}^{n} x_jz_j = <x, z>^2$처럼 나타낼 수 있다! 즉 위의 식은

 

- $1 + <x, z> + <x, z>^2 + \cdots$

 

처럼 나타낼 수 있고, $\phi(x)$와 $\phi(z)$를 계산하는 데 $O(d)$만 사용했다.

 

이처럼 많은 경우에 $K(x, z) = <\phi(x), \phi(z)>$를 $\phi$를 구하지 않고 계산할 수 있는 함수를 커널 함수라고 한다.

 

Kernel Method

 

- compute Kernel function $K(x^{(i)}, x^{(j)})$

- set $\beta = 0$

- Loop

    - $ \beta_{i} = \beta_{i} + \alpha (y ^{(i)} - \sum_{j=1}^{n} \beta_{j} K(x^{(i)}, x^{(j)}))$

 

workflow

 

- design kernel function

- verify $K$ is valid one by sum or construction $\phi$

- run the algorithm

 

하지만...

 

커널 트릭은 다음과 같은 이유들로 잘 쓰이지 않는다.

 

1. 좋은 커널 함수를 설계해야 하고,
2. $p$ 이전에 데이터의 개수 $n$이 너무 크며,
3. neural network와 다르게 kernel은 feature을 직접 설계해야 하기 때문이다.