커널 PCA

1. 개요[편집]

커널 PCA Kernel Principal Component Analysis
제안	Schölkopf · Smola · Müller (1998)
푸는 것	중심화된 커널 행렬 K̃ 의 대칭 고유값 문제
안 하는 것	특징사상 φ 를 명시적으로 계산하는 일
비용	시간 O(N³) · 메모리 O(N²) — 표본 수가 지배
고질병	사전이미지(pre-image) 문제 · RBF 폭 σ 민감성

선형 PCA는 데이터가 평면 위에 있다고 믿는다. 커널 PCA는 그 믿음을 100차원짜리 공간으로 미뤄 놓는다.

커널 PCA(kernel PCA, KPCA)는 입력을 고차원 특징공간으로 보내는 사상 $\varphi$ 를 한 번도 계산하지 않은 채, 내적만 돌려주는 커널 함수 $k(x,y)=\langle\varphi(x),\varphi(y)\rangle$ 로 이루어진 $N\times N$ 행렬의 고유분해만으로 그 특징공간에서의 주성분 분석을 수행하는 비선형 차원 축소 기법이다. 쇤코프·스몰라·뮐러가 1998년 Neural Computation 논문 「Nonlinear component analysis as a kernel eigenvalue problem」에서 제안했다.

핵심 관찰은 한 줄이다. PCA의 모든 계산은 내적으로만 쓸 수 있다. 공분산의 고유벡터는 항상 데이터점들의 선형결합이고, 새 점의 사영값도 결국 내적의 합이다. 그러면 내적을 다른 것으로 바꿔치기해도 알고리즘 전체가 그대로 돌아간다. 이 바꿔치기가 커널 트릭이고, 커널 PCA는 그 트릭을 가장 순수한 형태로 보여 주는 예제다. 대가는 명확하다 — 변수 수 $p$ 가 아니라 표본 수 $N$ 이 비용을 결정하게 되고, 얻어낸 성분을 원래 공간으로 되돌리는 길이 막힌다.

2. 왜 $\varphi$ 를 안 써도 되는가[편집]

특징공간에서 데이터가 중심화되어 있다고 잠시 가정하자. 공분산 연산자는

$$C = \frac{1}{N}\sum_{i=1}^{N} \varphi(x_i)\,\varphi(x_i)^{\mathsf T}$$

이고 고유방정식은 $C\mathbf v = \lambda \mathbf v$ 다. 여기서 $\lambda>0$ 이면 $\mathbf v = C\mathbf v/\lambda$ 이므로 $\mathbf v$ 는 반드시 $\varphi(x_i)$ 들의 선형결합이다. 즉

$$\mathbf v = \sum_{i=1}^{N}\alpha_i\,\varphi(x_i)$$

로 쓸 수 있다. 이걸 원 방정식에 넣고 양변에 $\varphi(x_l)$ 을 내적하면 $\varphi$ 가 전부 커널값으로 흡수되어

$$K\boldsymbol\alpha = N\lambda\,\boldsymbol\alpha, \qquad K_{ij}=k(x_i,x_j)$$

만 남는다. $p$ 차원(어쩌면 무한차원) 고유값 문제가 $N\times N$ 고유값 문제로 바뀌었다. 이 유도에서 차원이 사라지는 자리가 커널 방법의 전부다.

3. 중심화 — 평균을 뺄 수 없을 때 평균을 빼는 법[편집]

앞의 가정 “특징공간에서 중심화되어 있다”는 공짜가 아니다. $\varphi$ 를 모르니 $\bar\varphi = \frac1N\sum\varphi(x_i)$ 를 계산할 수도, 빼줄 수도 없다. 다행히 중심화된 내적은 원래 커널값들로 표현된다. $\tilde\varphi(x)=\varphi(x)-\bar\varphi$ 를 대입해 전개하면 행렬 형태로

$$\tilde K = K - \mathbf 1_N K - K \mathbf 1_N + \mathbf 1_N K \mathbf 1_N, \qquad (\mathbf 1_N)_{ij} = \tfrac{1}{N}$$

이 나온다. 항이 네 개인 이유는 $\langle \varphi_i-\bar\varphi,\ \varphi_j-\bar\varphi\rangle$ 를 전개하면 항이 네 개이기 때문이지 그 이상의 사연은 없다. 실무에서 커널 PCA가 조용히 틀리는 첫 번째 원인이 이 중심화를 빼먹는 것이고, 두 번째 원인은 중심화를 학습 데이터에만 하고 새 점에는 안 하는 것이다.¹

4. 고유분해와 정규화[편집]

이제 $\tilde K \boldsymbol\alpha_k = \lambda_k \boldsymbol\alpha_k$ 를 푼다(여기서 $\lambda_k$ 는 커널 행렬의 고유값이고, 특징공간 공분산의 고유값은 $\lambda_k/N$ 이다 — 문헌마다 $N$ 이 어디 붙는지가 달라서 코드 비교할 때 늘 헷갈리는 지점이다). $\tilde K$ 가 대칭 양반정치이므로 고유값은 실수이고 음수가 나오면 반올림 오차다.

정규화가 이 알고리즘의 가장 안 예쁜 부분이다. 우리가 원하는 것은 특징공간 고유벡터의 단위 노름 $\lVert \mathbf v_k\rVert = 1$ 인데, $\mathbf v_k = \sum_i \alpha_{ki}\tilde\varphi(x_i)$ 이므로

$$\lVert \mathbf v_k\rVert^2 = \boldsymbol\alpha_k^{\mathsf T}\tilde K \boldsymbol\alpha_k = \lambda_k\,\boldsymbol\alpha_k^{\mathsf T}\boldsymbol\alpha_k = 1$$

이 되어야 한다. 즉 고유벡터 루틴이 돌려준 정규직교 $\boldsymbol\alpha_k$ 를 $1/\sqrt{\lambda_k}$ 로 다시 스케일해야 한다. 이 스케일을 빠뜨리면 성분들의 상대적 크기가 전부 틀어지고, $\lambda_k$ 가 작은 꼬리 성분에서는 스케일이 폭발한다. 사실상 조건수 문제라서, 작은 고유값 성분은 애초에 버리는 게 맞다.

$k$ 번째 성분 위로의 사영은 새 점 $x$ 에 대해

$$\beta_k(x) = \langle \mathbf v_k,\ \tilde\varphi(x)\rangle = \sum_{i=1}^{N}\alpha_{ki}\,\tilde k(x_i, x)$$

이고, $\tilde k(x_i,x)$ 는 위 중심화 공식의 벡터 버전이다. 결과적으로 새 점 하나를 사영하려면 학습 데이터 전부와 커널을 계산해야 한다. 학습이 끝나면 데이터를 버릴 수 있는 선형 PCA와 결정적으로 다른 점이고, 커널 방법 전반이 공유하는 짐이다.

성분 개수에도 반전이 있다. 선형 PCA의 성분은 최대 $\min(N-1,\,p)$ 개지만, 커널 PCA는 $N-1$ 개까지 나온다. 입력이 2차원이어도 성분 50개를 뽑을 수 있다. “차원 축소”라는 이름을 달고 차원을 늘리는 것이 가능한 이유이며, 실제로 SVM 앞단 전처리로 쓸 때는 늘리는 쪽이 목적인 경우도 있다.

5. RBF 폭 σ — 손잡이 하나가 결과를 다 정한다[편집]

가장 흔한 선택인 가우시안(RBF) 커널 $k(x,y)=\exp(-\lVert x-y\rVert^2/2\sigma^2)$ 를 쓰면 결과는 사실상 $\sigma$ 하나가 정한다. 양 끝을 보면 왜 그런지 분명해진다.

• $\sigma \to 0$: 대각만 1이고 나머지가 0인 $K \to I$. 중심화하면 고유값이 거의 전부 같아져서 모든 점이 자기만의 성분이 된다. 스펙트럼이 평평하다는 것은 데이터에서 아무것도 못 배웠다는 뜻이다.
• $\sigma \to \infty$: $\exp(-r^2/2\sigma^2)\approx 1 - r^2/2\sigma^2$ 이고, 상수항은 중심화가 지워 버린다. 남는 것은 $-\lVert x_i-x_j\rVert^2/2$ 를 이중 중심화한 행렬인데, 이것이 정확히 중심화된 그람 행렬이다(고전적 다차원 척도법의 핵심 항등식). 따라서 큰 $\sigma$ 에서 커널 PCA는 선형 PCA로 수렴한다.

즉 $\sigma$ 는 “선형 PCA”와 “쓸모없는 항등행렬” 사이를 잇는 연속 손잡이이고, 쓸 만한 구간은 그 사이 어딘가에 좁게 있다. 비지도 기법이라 교차검증할 목적함수가 없다는 것이 진짜 문제다. 실무 처방은 대개 휴리스틱이다 — 쌍거리의 중앙값을 $\sigma$ 로 쓰는 median heuristic, 고유값 스펙트럼이 급락하는 지점을 보는 눈대중, 후단 작업(분류·군집)이 있다면 그 성능으로 고르기. 마지막 방법이 제일 정직하지만, 그러면 이미 비지도가 아니다.²

6. 사전이미지 문제 — 돌아오는 길이 없다[편집]

선형 PCA에서는 성분 몇 개로 자른 뒤 $\hat x = W W^{\mathsf T} x$ 로 원래 공간에 복원하면 그만이다. 커널 PCA에서는 이 마지막 단계가 일반적으로 풀리지 않는다.

이유는 기하다. 특징공간에서 $\varphi$ 의 상(image) $\{\varphi(x): x\in\mathcal X\}$ 는 선형 부분공간이 아니라 휘어진 다양체다. 상위 성분들로의 사영 $P\varphi(x)$ 는 그 다양체 위에 있을 이유가 전혀 없고, 따라서 $\varphi(z)=P\varphi(x)$ 를 만족하는 $z$ 는 존재하지 않는 것이 보통이다. 그래서 문제를 최소화로 바꿔 푼다.

$$z^\star = \arg\min_z \big\lVert \varphi(z) - P\varphi(x)\big\rVert^2$$

RBF 커널이면 이 목적함수의 정류점 조건이 예쁜 고정점 반복으로 정리된다(미카 외, 1999).

$$z \;\leftarrow\; \frac{\sum_i \gamma_i \exp\!\big(-\lVert z-x_i\rVert^2/2\sigma^2\big)\,x_i}{\sum_i \gamma_i \exp\!\big(-\lVert z-x_i\rVert^2/2\sigma^2\big)}$$

즉 가중 평균을 반복해서 갱신하는 형태다. 문제는 이 반복이 (1) 비볼록이라 국소최소에 걸리고, (2) 초기값에 민감하며, (3) 분모가 0에 가까워지면 발산한다는 것. 대안으로 곽·창(2004)은 특징공간 거리와 입력공간 거리의 관계를 이용해 사전이미지를 다차원 척도법 문제로 바꿔 닫힌 형태로 푸는 방법을 냈고, 안정성이 훨씬 낫다. 어느 쪽이든 답은 근사이며, “커널 PCA로 잡음 제거를 했다”는 그림들은 전부 이 근사의 산물이다.

7. 비용과 우회로[편집]

정직하게 구현하면 커널 행렬 저장에 $O(N^2)$, 고유분해에 $O(N^3)$ 이다. $N=10^5$ 이면 배정밀도 커널 행렬만 80 GB이므로 표본 십만 개에서 이미 못 돌린다. 우회로는 셋이다.

우회로	아이디어	비용
상위 몇 개만	$\tilde K$ 를 곱하기만 하는 반복법(란초스 알고리즘, 랜덤화 SVD)	행렬-벡터 곱 $O(N^2)$ × 반복
나이스트룀	열 $m\ll N$ 개만 뽑아 $\tilde K \approx C W^{+} C^{\mathsf T}$ 로 저랭크 근사	$O(Nm^2)$
무작위 특징	커널을 근사하는 명시적 특징 $z(x)\in\mathbb R^{D}$ 를 만들고 선형 PCA	$O(ND^2)$, 사전이미지 부담도 줄어듦

세 번째가 무작위 푸리에 특징(라히미·레흐트, 2007)이다. 이동불변 커널의 푸리에 변환이 확률측도라는 보흐너 정리를 이용해 무작위 주파수를 뽑고, $z(x)=\sqrt{2/D}\,\cos(\omega_j^{\mathsf T}x+b_j)$ 로 근사한다. 이 지점에서 커널 PCA는 무작위 사영 계열과 직접 만난다 — 어느 쪽도 데이터를 다 보지 않고 근사 내적을 만든다는 점에서 같은 정신이다. 나이스트룀 확장은 새 점을 기존 고유함수 위로 보간하는 데도 그대로 쓰이며, 그 용법은 다양체 학습 문서가 다룬다.

8. 친척들과의 관계[편집]

커널 PCA의 진짜 지위는 “PCA의 비선형 확장” 하나가 아니라 여러 스펙트럴 기법을 한 틀로 묶는 언어라는 데 있다. 어떤 대칭 양반정치 행렬을 만들어 그 상위 고유벡터를 좌표로 쓰느냐만 다르다.

• 고전적 다차원 척도법은 거리 행렬을 이중 중심화한 것의 커널 PCA다. 위 $\sigma\to\infty$ 논의가 정확히 그 사실이다.
• 스펙트럴 군집화 는 그래프 라플라시안의 하위 고유벡터를 쓴다. 부호를 뒤집으면 커널 PCA의 상위 고유벡터와 같은 계산이고, 차이는 그 좌표를 군집으로 자르느냐 그대로 쓰느냐다.
• 확산 지도는 랜덤워크 전이행렬에 시간 $t$ 를 손잡이로 붙인 커널을 쓴다.
• 가우시안 프로세스 는 같은 커널 행렬을 회귀의 사전분포로 쓴다. 커널 PCA가 $\tilde K$ 의 고유구조를 보는 것이라면 GP 회귀는 $(K+\sigma_n^2 I)^{-1}$ 을 푸는 것이라, 같은 행렬의 서로 다른 얼굴이다.

이 통일이 실무적으로 주는 것: 코드의 대부분이 공유되고, 병목이 전부 “대칭 행렬의 극단 고유쌍 몇 개”로 환원되어 수치해석 도구를 그대로 재활용할 수 있다.

9. 쓸 때 알아야 할 것[편집]

• 먼저 선형 PCA를 돌려 봐라. 스크리 도표가 이미 급락한다면 비선형성은 문제가 아니었던 것이다. 커널 PCA는 비용도 해석 난이도도 한 자릿수 올라간다.
• 표준화는 여전히 필요하다. RBF 커널의 $\lVert x-y\rVert$ 안에서 단위가 큰 변수가 거리를 독점한다. 선형 PCA에서 하던 실수가 커널 안에 숨어서 반복될 뿐이다.
• 이상치에 더 약하다. 이상치 하나가 다른 모든 점과의 커널값을 0 근처로 만들면, 그 점만을 위한 고유벡터가 상위에 등장한다. 뒤집어 말하면 이 성질을 이상치 탐지에 쓸 수도 있고, 실제로 특징공간 재구성 오차를 이상 점수로 쓰는 방법이 있다. 거리 기반 이상 판정 전반은 마할라노비스 거리 쪽이 표준이다.
• 성분에 이름을 붙이지 마라. 선형 PCA의 로딩은 그래도 “0.34×온도 −0.51×압력”이라고 읽을 수라도 있지만, 커널 PCA의 성분은 $\alpha$ 계수 $N$ 개일 뿐이라 물리적 해석이 사실상 불가능하다. 보고서에 넣을 그림이 필요한 것이라면 다른 도구를 찾는 게 낫다.³

10. 관련 문서[편집]

• 주성분 분석 · 다양체 학습 · 스펙트럴 군집화
• 고유값 문제 · 특이값 분해 · 란초스 알고리즘 · 랜덤화 SVD
• 저랭크 근사 · 조건수 · 레일리 몫
• 가우시안 프로세스 · 차원의 저주
• 마할라노비스 거리 · 무작위 사영 · 자카드 유사도
• 축소차수모델 · 능동 형상 모형

11. Footnotes[편집]

1. 새 점을 사영할 때 쓰는 중심화는 학습 데이터의 평균으로 해야 한다. 새 점들끼리 다시 평균을 내서 빼면 배치 크기에 따라 결과가 달라지는, 재현 불가능한 파이프라인이 완성된다. scikit-learn 같은 라이브러리가 이걸 알아서 해 주기 때문에 직접 구현할 때 처음으로 데는 곳이기도 하다. ↩

2. 그래서 커널 PCA 그림이 논문에 실릴 때는 대개 $\sigma$ 를 몇 개 훑어 제일 예쁜 것이 실린다. 비지도 기법에 하이퍼파라미터가 붙으면 “결과가 아니라 취향”이 되기 쉽다는 오래된 불평이고, t-SNE의 퍼플렉시티, UMAP의 이웃 수도 전부 같은 병을 앓는다. ↩

3. 실무에서 커널 PCA가 가장 자주 쓰이는 자리는 사실 “그림”이 아니라 다른 알고리즘의 앞단이다. 비선형으로 펼친 좌표 몇십 개를 선형 분류기에 먹이는 용도. 이때는 성분에 의미가 없어도 아무 문제가 없고, 그래서 잘 쓰인다. ↩