비선형 차원 축소법: 커널 PCA

우리는 특정 데이터 포인트를 피쳐 공간으로 매핑시킴으로써 더 나은 차원 축소 기술을 수행할 수 있다. 더 좋은 차원 축소 기술은 축소된 차원에서의 거리와 우리가 믿는 거리 간의 일치를 제공한다.

주어진 비선형 매핑 $\phi$를 이용하면, 비선형 PCA의 목적식은 아래와 같아진다.

$$ minimize \sum_{n=1}^{N} \left| \phi \left( x_n \right) - V V^\top \phi \left( x_n \right) \right|^2 $$

이 목적식은 곧 $ \bar{S} = \frac{1}{N} \sum_{n=1}^{N} \phi \left( x_n \right) \phi \left( x_n \right)^\top $의 고유벡터들을 찾는 것이 되지만, 원래 데이터 차원보다 피쳐 공간의 차원이 커질 수 있기 때문에 이것은 계산이 불가능할 수도 있다. ($S$의 크기가 $\left| D_K \right| \times \left| D_K \right|$이다.)

PCA 복습

PCA를 다시 생각해보면, 평균이 0인 데이터에 대해서 PCA는 데이터 공분산 행렬의 고윳값을 구하게 된다. $S=\frac{1}{N} \sum_{n=1}^{N} x_n x_n^\top$

$$ Su_i = \lambda_i u_i \;\;\; such \; that \;\;\; u_i^\top u_i = 1$$

여기서 내적을 $ \left<x,y \right>$로 표현하게 되면 아래와 같이 표현할 수 있고 이는 가능한 모든 $u_i$가 basis가 $\left\{ x_1, ..., x_n \right\}$인 공간에서 span한 형태로 볼 수 있다.

$$ Su_i = \left( \frac{1}{N} \sum_{n=1}^{N} x_n x_n^\top \right) u_i = \frac{1}{N} \sum_{n=1}^{N} x_n \left< x_n, u_i \right> = \lambda_i u_i $$

즉, 어떤 가능한 $Su_i$는 $x_n$ 방향으로 사영시켰을 때, $u_i$를 $x_n$ 방향으로 사영시킨 결과의 $\lambda_i$배가 된다는 의미가 된다.

$$ \lambda_i \left< x_n, u_i \right> = \left< x_n, Su_i \right> $$

피쳐 공간에서의 PCA와 문제를 바꾸어 생각하기

똑같이, 피쳐 공간에서 PCA를 수행하면 아래와 같은 결과를 얻게 된다.

$$ \lambda \left< \phi \left( x_n \right), v_i \right> = \left< \phi \left( x_n \right), \bar{S} v_i \right> \;\; where \; \bar{S} = \frac{1}{N} \sum_{n=1}^{N} \phi \left( x_n \right) \phi \left( x_n \right)^\top $$

그리고 주어진 피쳐들을 basis로 하는 공간에서 span한 형태로 나타낼 수 있게 된다.

$$ v_i = \sum_{n=1}^{N} \alpha_{in} \phi \left( x_n \right) $$

따라서, 우리는 직접적으로 고유벡터를 구하는 대신 $\left\{ \alpha_{in} \right\}$을 구하는 것으로 문제를 대체할 수 있다.

커널 행렬

우리는 커널 공간에서의 거리를 측정하고 모든 데이터 페어 간의 거리를 저장하는 커널 행렬을 생각해볼 수 있다.

$$ K \in \mathbb{R}^{N \times N} \;\; where \;\; K_{nm} = \left< \phi \left( x_n \right), \phi \left( x_m \right) \right> $$

이제 우리가 구하고자 하는 $\left\{ \alpha_{in} \right\}$의 형태로 나타내기 위해, $v_i$를 풀어서 작성한다.

$$ \frac{1}{N} \left( \sum_{n=1}^{N} \phi \left( x_n \right) \phi \left( x_n \right)^\top \right) \left( \sum_{n=1}^{N} \alpha_{in} \phi \left( x_n \right) \right) = \lambda_i \sum_{n=1}^{N} \alpha_{in} \phi \left( x_n \right) $$

여기서 $\phi \left( x_l \right)^\top$을 양변의 왼쪽에 곱하고 커널 행렬을 이용하면 좌변은 다음과 같이 표현할 수 있다.

$$ \frac{1}{N} \sum_{n=1}^{N} \sum_{m=1}^{N} \alpha_{im} \phi \left( x_l \right)^\top \phi \left( x_n \right) \phi \left( x_n \right)^\top \phi \left( x_m \right) = \frac{1}{N} \sum_{n=1}^{N} \sum_{m=1}^{N} \alpha_{im} K_{ln} K_{nm}$$

마찬가지로 우변도 아래와 같이 표현할 수 있다.

$$ \lambda_i \sum_{n=1}^{N} \alpha_{in} \phi \left( x_l \right)^\top \phi \left( x_n \right) = \lambda_i \sum_{n=1}^{N} \alpha_{in} K_{ln} $$

여기서 $\alpha_i = \left[ \alpha_{i1}, ..., \alpha_{iN} \right]^\top$인 열벡터로 생각하면 아래와 같은 행렬곱으로 표현할 수 있게 된다. (여기서 $l$을 모든 $n$에 대해 행벡터로 깔았다고 생각하면 아래처럼 표현가능하다.)

$$ \frac{1}{N} K^2 \alpha_i = \lambda_i K \alpha_i $$

여기서 우리는 문제를 간단히 만들어 $K$의 고유벡터를 구하는 문제로 만든다. 이 식의 해는 마찬가지로 위 식의 해이기 때문에 문제되지 않는다.

$$ K \alpha_i = \lambda_i N \alpha_i $$

여기서 문제는 $K$의 형태가 $N \times N$이므로 이 행렬의 고유벡터를 구하기 위해서는 $O \left( N^3 \right)$의 시간이 걸리게 된다.

커널 PCA의 정규화기법

우리는 원래 구하고자 하는 벡터 $v_i$에 걸린 제한조건을 $\alpha_i$에 맞게 다듬어야 한다.

$$ 1=v_i^\top v_i = \sum_{n=1}^{N} \sum_{m=1}^{N} \alpha_{in} \alpha_{im} \phi \left( x_n \right)^\top \phi \left( x_m \right) = \alpha_i^\top K \alpha_i = \lambda_i N \alpha_i^\top \alpha_i$$

즉, $\alpha_i$를 위한 최적화 문제의 정의는 아래와 같다.

$$ \lambda_i N \alpha_i = K \alpha_i \;\;\; such \; that \;\; \left| \alpha_i \right|^2 = \frac{1}{\lambda_i N} $$

PCA와 커널 PCA의 축소된 공간 비교

일반 PCA에서는 결국 고유벡터를 구하고 그 고유벡터과의 내적값을 이용하여 축소된 공간에서 데이터를 표현하였다. 즉 축소된 공간의 각각의 값은 아래 내적을 이용하여 구한다.

$$ \left< u_i, x \right> $$

반면, 커널 PCA의 경우, 우리는 고유벡터 $v_i$에 대해서 내적값을 이용하여 구하게 되는데 이는 커널 (피쳐 공간에서의 거리 함수)을 이용하여 표현할 수 있다.

$$ \left< v_i, \phi \left( x \right) \right> = \sum_{n=1}^{N} \alpha_{in} \phi \left( x \right)^\top \phi \left( x_n \right) = \sum_{n=1}^{N} \alpha_{in} k \left( x, x_n \right) $$

피쳐 공간 중심 이동

우리는 피쳐들의 평균이 0이 아닌 경우에 대해서도 간단히 식을 다시 전개할 수 있다.

$$ \tilde{\phi} \left( x_n \right) = \phi \left( x_n \right) - \frac{1}{N} \sum_{l=1}^{N} \phi \left( x_l \right) $$

이를 기반으로 커널 행렬을 구성하면 다음과 같다.

$$ \tilde{K}_{nm} = \left< \tilde{\phi} \left( x_n \right), \tilde{\phi} \left( x_m \right) \right>$$

정의를 이용해서 다시 적으면 다음과 같다.

$$ \left< \tilde{\phi} \left( x_n \right), \tilde{\phi} \left( x_m \right) \right> = \left< \phi \left( x_n \right) - \frac{1}{N} \sum_{l=1}^{N} \phi \left( x_l \right), \phi \left( x_m \right) - \frac{1}{N} \sum_{l=1}^{N} \phi \left( x_l \right) \right> $$

분배법칙을 이용하여 풀어보면 다음과 같다.

$$ K_{nm} - \frac{1}{N} \sum_{l=1}^{N} K_{nl} - \frac{1}{N} \sum_{l=1}^{N} K_{ml} + \frac{1}{N^2} \sum_{l=1}^{N} \sum_{l'=1}^{N} K_{ll'} $$

이를 행렬로 표현하면 다음과 같다.

$$ \tilde{K} = K - 1_N K - K 1_N + 1_N K 1_N $$

여기서 $1_N$은 $N \times N$ 행렬로 모든 원소가 $\frac{1}{N}$인 행렬을 의미한다.

정리

커널 PCA를 수행하기 위해 우리는 먼저 커널 행렬 $K \in \mathbb{R}^{N \times N}$을 계산한다. 만약, 피쳐 공간의 중심이 0이 아니라면 중심 이동된 커널 행렬 $\tilde{K}$를 추가적으로 계산한다. 다음으로, 이 커널 행렬을 이용하여 고유벡터 문제를 푼다. $\lambda_i N \alpha_i = \tilde{K} \alpha_i$ 그리고 $\left| \alpha_i \right|^2 = \frac{1}{N\lambda_i}$가 되게끔 $\alpha_i$를 정규화한다. 새롭게 들어오는 데이터에 대해서 차원을 축소할 때는 구한 $\alpha_i$와 커널 함수 $k$를 이용하여 각 차원에 해당하는 값을 구한다. $\left< v_i, x \right> = \sum_{n=1}^{N} \alpha_{in} k \left( x, x_n \right)$

응용 기법과 한계점

이런 커널 기법들은 모든 데이터 간 피쳐 공간상의 거리를 정의해야 한다는 요구조건이 있다. 이 커널 PCA의 응용 기법으로 isomap이 있다. 이는 먼저 data들 간의 거리를 기반으로 특정 threshold보다 작은 데이터 페어를 그 거리를 weight로 가지는 에지로 연결하여 그래프를 생성한다. 그리고 특정 두 데이터 간의 거리를 그래프 상에서 최단 거리로 정의하여 커널 행렬을 생성한다.