커널 트릭

Kernel trick; 커널 트릭
고차원 특징 공간으로 데이터를 옮기는 계산을 하지 않고, 그 공간에서의 내적만 커널 함수로 바로 구해 선형 알고리즘을 비선형으로 확장하는 기법

커널 트릭(kernel trick)은 내적만으로 쓸 수 있는 선형 알고리즘에서 내적 $⟨ x, x^{'} ⟩$ 을 커널 함수 $k (x, x^{'})$ 로 바꿔, 데이터를 고차원(때로는 무한 차원) 특징 공간으로 옮긴 효과를 내는 방법이다. 특징 벡터 $φ (x)$ 를 실제로 만들지 않으므로 계산량은 원래 입력 차원 수준에 머문다.

서포트 벡터 머신(SVM)의 비선형 분류가 대표적인 쓰임새이고, 커널 PCA, 커널 릿지 회귀, 가우시안 프로세스도 같은 원리에 기대고 있다. 이런 알고리즘을 묶어 커널 방법(kernel method)이라 한다. 상위 개념은 기계 학습 문서의 "커널 방법" 항목 참고.

원리

내적만 쓰는 알고리즘

SVM의 쌍대 문제는 훈련 데이터가 내적 $x_{i}^{⊤} x_{j}$ 로만 나타나는 형태다.

$\max_{α} \sum_{i} α_{i} - \frac{1}{2} \sum_{i, j} α_{i} α_{j} y_{i} y_{j} x_{i}^{⊤} x_{j} s.t. 0 \leq α_{i} \leq C, \sum_{i} α_{i} y_{i} = 0$

예측도 $f (x) = \sum_{i} α_{i} y_{i} x_{i}^{⊤} x + b$ 로 내적만 쓴다. 여기서 $x_{i}^{⊤} x_{j}$ 를 $φ (x_{i})^{⊤} φ (x_{j})$ 로 바꾸면 특징 공간에서 선형 SVM을 푼 것이 되고, 원래 입력 공간에서는 비선형 경계가 된다. 이 내적을 한 번에 계산해 주는 함수가 커널이다.

$k (x, x^{'}) = ⟨ φ (x), φ (x^{'}) ⟩$

예: 2차 다항 커널

2차원 입력 $x = (x_{1}, x_{2})$ 에 다항 커널 $k (x, z) = (x^{⊤} z + 1)^{2}$ 을 쓰면, 이 값은 6차원 특징 사상

$φ (x) = (x_{1}^{2}, x_{2}^{2}, \sqrt{2} x_{1} x_{2}, \sqrt{2} x_{1}, \sqrt{2} x_{2}, 1)$

의 내적과 정확히 같다. 입력이 $d$ 차원이고 차수가 $p$ 이면 특징 공간의 차원은 $(\binom{d + p}{p})$ 로 늘지만, 커널 계산은 내적 한 번과 거듭제곱 한 번이면 된다. 가우스(RBF) 커널은 테일러 전개하면 모든 차수의 다항 항을 포함하므로 특징 공간이 무한 차원이다.

그람 행렬

훈련 데이터 $n$ 개에 대해 $K_{i j} = k (x_{i}, x_{j})$ 로 만든 $n \times n$ 행렬을 그람 행렬(Gram matrix) 또는 커널 행렬이라 한다. 커널 알고리즘은 입력 차원 대신 이 행렬을 다루므로, 메모리는 $O (n^{2})$ , 행렬 분해가 필요한 경우 계산은 $O (n^{3})$ 이 된다. 데이터가 수만 개를 넘으면 이것이 커널 방법의 가장 큰 병목이다.

어떤 함수가 커널이 될 수 있나

양의 준정부호 조건

함수 $k$ 가 어떤 특징 공간의 내적으로 표현되려면, 대칭이고 임의의 점 집합 $x_{1}, \dots, x_{n}$ 과 실수 $c_{1}, \dots, c_{n}$ 에 대해

$\sum_{i = 1}^{n} \sum_{j = 1}^{n} c_{i} c_{j} k (x_{i}, x_{j}) \geq 0$

이어야 한다. 즉 어떤 데이터로 만들어도 그람 행렬이 양의 준정부호(positive semi-definite)여야 한다. 이 조건을 만족하는 함수를 양의 정부호 커널(positive definite kernel) 또는 머서 커널이라 부른다.

머서 정리

머서 정리(Mercer's theorem)는 1909년 제임스 머서가 적분 방정식 연구에서 증명한 결과다.^[1] 콤팩트 정의역에서 연속이고 대칭이며 양의 준정부호인 커널은 고유함수 $e_{i}$ 와 음이 아닌 고윳값 $λ_{i}$ 로

$k (x, x^{'}) = \sum_{i = 1}^{\infty} λ_{i} e_{i} (x) e_{i} (x^{'})$

처럼 전개된다. $φ (x) = (\sqrt{λ_{1}} e_{1} (x), \sqrt{λ_{2}} e_{2} (x), \dots)$ 로 두면 커널이 곧 이 특징 사상의 내적이므로, 양의 준정부호 조건만 확인하면 특징 공간이 존재한다는 보장이 생긴다. 더 일반적으로는 모든 양의 정부호 커널에 대응하는 재생 커널 힐베르트 공간(RKHS)이 하나씩 존재한다(Moore-Aronszajn 정리).^[2]

커널을 새로 만드는 규칙

커널 $k_{1}, k_{2}$ 가 있으면 다음도 커널이다. 그래서 복잡한 커널을 간단한 것들의 조합으로 설계한다(가우시안 프로세스의 커널 설계도 이 규칙을 쓴다).

합: $k_{1} + k_{2}$
곱: $k_{1} \cdot k_{2}$
양의 상수배: $c k_{1}$ ( $c > 0$ )
지수: $\exp (k_{1})$
특징 함수 앞뒤 곱: $f (x) k_{1} (x, x^{'}) f (x^{'})$

표현자 정리

표현자 정리(representer theorem)는 RKHS에서 "손실 + 노름 제곱 규제"를 최소화하는 해가 언제나 훈련 점에서의 커널 합 $f (x) = \sum_{i} α_{i} k (x_{i}, x)$ 꼴임을 보인다. 김멜도르프와 와바가 1971년 스플라인 문제에서 처음 보였다.^[3] 무한 차원 공간의 최적화가 계수 $n$ 개를 찾는 문제로 바뀌므로, 커널 트릭이 실제 알고리즘이 될 수 있는 근거가 된다.

주요 커널

커널	식	특징 공간	하이퍼파라미터	쓰임
선형	$x^{⊤} x^{'}$	입력 공간 그대로	없음	특징이 많은 텍스트 분류. 대개 커널 SVM보다 LinearSVC가 빠르다
다항	$(γ x^{⊤} x^{'} + r)^{d}$	차수 $d$ 이하 단항식	$γ, r, d$	특징 사이 상호작용이 중요할 때. 차수가 크면 수치가 불안정하다
가우스(RBF)	$\exp (- γ ‖ x - x^{'} ‖^{2})$	무한 차원	$γ$ (= $1 / 2 ℓ^{2}$ )	사전 지식이 없을 때의 기본값. scikit-learn SVC의 기본 커널
라플라스	$\exp (- γ ‖ x - x^{'} ‖_{1})$	무한 차원	$γ$	RBF보다 덜 매끄러운 함수
시그모이드	$\tanh (γ x^{⊤} x^{'} + r)$	매개변수에 따라 커널이 아님	$γ, r$	신경망과의 유사성 때문에 쓰이나, 일부 매개변수에서 양의 준정부호가 아니다
문자열·그래프 커널	공통 부분열, 경로 수 등	구조에 따라 다름	다양	생물 서열, 화합물 그래프처럼 벡터가 아닌 데이터

RBF 커널의 $γ$ 는 한 훈련 점이 영향을 미치는 범위의 역수다. $γ$ 가 크면 각 점 주변만 보는 복잡한 경계가 되어 과적합되기 쉽고, 작으면 경계가 선형에 가까워진다. SVM의 규제 상수 $C$ 와 함께 격자 탐색이나 베이지안 최적화로 고른다. scikit-learn의 gamma="scale"은 $1 / (n_{features} \cdot V a r (X))$ 이다.^[4]

커널 트릭을 쓰는 알고리즘

서포트 벡터 머신: 보저, 기용, 바프니크가 1992년 최대 마진 분류기에 커널을 결합했고,^[5] 1995년 코르테스와 바프니크가 소프트 마진을 더해 현재 형태가 되었다.^[6]
커널 PCA: 특징 공간에서 주성분 분석을 한다. 공분산 행렬 대신 중심화한 그람 행렬의 고유벡터를 구한다. 1998년 숄코프, 스몰라, 뮐러가 발표했다.^[7]
커널 릿지 회귀: L2 규제를 건 선형 회귀의 커널판. 해는 $α = (K + λ I)^{- 1} y$ 로 닫힌 형태다.
가우시안 프로세스 회귀: 사후 평균이 커널 릿지 회귀의 해와 같은 꼴이고, 여기에 불확실성(사후 분산)을 더해 준다.
그 밖에 커널 k-평균, 스펙트럼 군집, 커널 밀도 추정(이름은 같지만 "커널"이 평활 함수를 뜻하는 다른 개념), 커널 2표본 검정(MMD) 등이 있다.

코드 예시

아래는 scikit-learn 1.7에서 실행해 확인한 예시다. 다항 커널이 명시적 특징 사상의 내적과 같음을 보이고, 같은 SVM에 커널만 바꿔 비교한다.

import numpy as np
from sklearn.datasets import make_moons, make_circles
from sklearn.svm import SVC
from sklearn.decomposition import KernelPCA, PCA
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import cross_val_score

# 1) (x.z + 1)^2 = phi(x).phi(z)
def phi(x):
    x1, x2 = x
    return np.array([x1**2, x2**2, np.sqrt(2)*x1*x2, np.sqrt(2)*x1, np.sqrt(2)*x2, 1.0])
x, z = np.array([1.0, 2.0]), np.array([3.0, -1.0])
print(phi(x) @ phi(z), (x @ z + 1) ** 2)            # 4.0 4.0

# 2) 같은 SVM, 다른 커널 (5겹 교차 검증 정확도)
X, y = make_moons(n_samples=500, noise=0.2, random_state=0)
for k in ["linear", "poly", "rbf"]:
    print(k, cross_val_score(SVC(kernel=k), X, y, cv=5).mean())
# linear 0.868 / poly 0.912 / rbf 0.958

# 3) 그람 행렬을 직접 넘기기
def rbf(A, B, gamma=1.0):
    d2 = (A**2).sum(1)[:, None] + (B**2).sum(1)[None, :] - 2 * A @ B.T
    return np.exp(-gamma * d2)
K = rbf(X, X)
clf = SVC(kernel="precomputed").fit(K[:400, :400], y[:400])
print(clf.score(K[400:, :400], y[400:]))           # 시험 행 x 훈련 열

# 4) 동심원 데이터: PCA로는 직선 분리 불가, 커널 PCA로는 가능
Xc, yc = make_circles(n_samples=400, factor=0.3, noise=0.05, random_state=0)
for m in [PCA(n_components=2), KernelPCA(n_components=2, kernel="rbf", gamma=10)]:
    Z = m.fit_transform(Xc)
    print(type(m).__name__, LogisticRegression().fit(Z, yc).score(Z, yc))
# PCA 0.5 / KernelPCA 1.0

kernel="precomputed"를 쓰면 예측 때 시험 데이터와 훈련 데이터 사이의 커널 값(시험 개수 × 훈련 개수 행렬)을 넘겨야 한다.

대규모 데이터: 커널 근사

그람 행렬의 $O (n^{2})$ 메모리와 $O (n^{3})$ 계산을 피하려고, 유한 차원 특징 $z (x)$ 를 만들어 $k (x, x^{'}) \approx z (x)^{⊤} z (x^{'})$ 로 근사한 뒤 선형 모델을 쓴다.

방법	아이디어	scikit-learn	비고
니스트룀 근사	훈련 점 일부( $m$ 개)로 그람 행렬의 저랭크 근사를 만든다	`Nystroem`	데이터에 맞춘 근사라 같은 차원에서 대체로 정확하다
무작위 푸리에 특징	이동 불변 커널의 푸리에 변환에서 주파수를 표본추출해 $\cos (w^{⊤} x + b)$ 특징을 만든다	`RBFSampler`	2007년 라히미와 레흐트 제안^[8]
다항 커널 스케치	텐서 스케치로 다항 특징을 압축	`PolynomialCountSketch`	다항 커널 전용

scikit-learn 문서는 표본이 수만 개를 넘으면 SVC 대신 이런 근사 뒤에 LinearSVC나 SGDClassifier를 쓰라고 권한다.^[4]^[9]

딥 러닝과의 관계

고정 특징 대 학습 특징: 커널 방법은 특징 공간을 커널로 미리 정하고 계수만 배운다. 딥 러닝은 특징 사상 자체를 데이터로 배운다. 2010년대 이후 이미지·언어 같은 큰 데이터에서는 학습 특징이 앞서면서 커널 SVM의 비중이 줄었다.
신경 탄젠트 커널(NTK): 폭이 무한대로 커지는 신경망의 경사 하강 학습은 특정 커널을 쓴 커널 회귀와 같아진다는 결과다(자코 등, 2018).^[10] 신경망 이론 분석의 도구로 쓰인다.
어텐션과 커널: 트랜스포머의 어텐션은 쿼리와 키 사이의 유사도 $\exp (q^{⊤} k / \sqrt{d})$ 를 가중치로 값을 평균 내는 커널 평활기로 볼 수 있다.^[11] 퍼포머(Performer)는 이 소프트맥스 커널을 무작위 특징으로 근사해 어텐션 비용을 시퀀스 길이에 선형으로 줄였다.^[12] 자세한 내용은 선형 어텐션 문서 참고.

한계와 실무 선택

데이터 크기: 수천~수만 개까지는 커널 SVM·가우시안 프로세스가 잘 맞고, 그 이상은 커널 근사나 다른 모델(트리 앙상블, 신경망)을 쓴다.
커널 선택: 결과가 커널과 하이퍼파라미터에 민감하다. RBF로 시작하고 $C$ , $γ$ 를 로그 척도로 탐색하는 것이 일반적인 출발점이다. 입력은 표준화해야 한다(거리 기반이므로 척도가 큰 특징이 지배한다).
해석: 특징 공간이 암묵적이어서 어떤 특징이 중요한지 직접 읽기 어렵다.
표 형태 데이터: 특징이 수십 개이고 표본이 많으면 그래디언트 부스팅이 대개 더 실용적이다.

같이 보기

각주

↑ James Mercer, 〈Functions of positive and negative type, and their connection with the theory of integral equations〉, Philosophical Transactions of the Royal Society A 209, 415~446, 1909. doi:10.1098/rsta.1909.0016
↑ N. Aronszajn, 〈Theory of reproducing kernels〉, Transactions of the American Mathematical Society 68, 337~404, 1950. doi:10.1090/S0002-9947-1950-0051437-7
↑ George Kimeldorf, Grace Wahba, 〈Some results on Tchebycheffian spline functions〉, Journal of Mathematical Analysis and Applications 33, 82~95, 1971. doi:10.1016/0022-247X(71)90184-3
↑ ^4.0 ^4.1 scikit-learn 1.9 문서, sklearn.svm.SVC
↑ Bernhard E. Boser, Isabelle M. Guyon, Vladimir N. Vapnik, 〈A training algorithm for optimal margin classifiers〉, COLT '92, 144~152, 1992. doi:10.1145/130385.130401
↑ Corinna Cortes, Vladimir Vapnik, 〈Support-vector networks〉, Machine Learning 20(3), 273~297, 1995. doi:10.1007/BF00994018
↑ Bernhard Schölkopf, Alexander Smola, Klaus-Robert Müller, 〈Nonlinear Component Analysis as a Kernel Eigenvalue Problem〉, Neural Computation 10(5), 1299~1319, 1998. doi:10.1162/089976698300017467
↑ Ali Rahimi, Benjamin Recht, 〈Random Features for Large-Scale Kernel Machines〉, NIPS 2007. NeurIPS
↑ scikit-learn 문서, Kernel Approximation
↑ Arthur Jacot, Franck Gabriel, Clément Hongler, 〈Neural Tangent Kernel: Convergence and Generalization in Neural Networks〉, NeurIPS 2018. arXiv:1806.07572
↑ Yao-Hung Hubert Tsai 외, 〈Transformer Dissection: A Unified Understanding of Transformer's Attention via the Lens of Kernel〉, EMNLP 2019. arXiv:1908.11775
↑ Krzysztof Choromanski 외, 〈Rethinking Attention with Performers〉, ICLR 2021. arXiv:2009.14794

참고 문헌

Bernhard Schölkopf, Alexander J. Smola, 《Learning with Kernels》, MIT Press, 2002.
Christopher M. Bishop, 《Pattern Recognition and Machine Learning》, Springer, 2006, 6장 "Kernel Methods". 마이크로소프트 리서치 공개본
scikit-learn 문서, Support Vector Machines

[mercer-1] James Mercer, 〈Functions of positive and negative type, and their connection with the theory of integral equations〉, Philosophical Transactions of the Royal Society A 209, 415~446, 1909. doi:10.1098/rsta.1909.0016

[aronszajn-2] N. Aronszajn, 〈Theory of reproducing kernels〉, Transactions of the American Mathematical Society 68, 337~404, 1950. doi:10.1090/S0002-9947-1950-0051437-7

[kimeldorf-3] George Kimeldorf, Grace Wahba, 〈Some results on Tchebycheffian spline functions〉, Journal of Mathematical Analysis and Applications 33, 82~95, 1971. doi:10.1016/0022-247X(71)90184-3

[sksvc-4] 4.0 ^4.1 scikit-learn 1.9 문서, sklearn.svm.SVC

[boser-5] Bernhard E. Boser, Isabelle M. Guyon, Vladimir N. Vapnik, 〈A training algorithm for optimal margin classifiers〉, COLT '92, 144~152, 1992. doi:10.1145/130385.130401

[cortes-6] Corinna Cortes, Vladimir Vapnik, 〈Support-vector networks〉, Machine Learning 20(3), 273~297, 1995. doi:10.1007/BF00994018

[kpca-7] Bernhard Schölkopf, Alexander Smola, Klaus-Robert Müller, 〈Nonlinear Component Analysis as a Kernel Eigenvalue Problem〉, Neural Computation 10(5), 1299~1319, 1998. doi:10.1162/089976698300017467

[rff-8] Ali Rahimi, Benjamin Recht, 〈Random Features for Large-Scale Kernel Machines〉, NIPS 2007. NeurIPS

[skapprox-9] scikit-learn 문서, Kernel Approximation

[ntk-10] Arthur Jacot, Franck Gabriel, Clément Hongler, 〈Neural Tangent Kernel: Convergence and Generalization in Neural Networks〉, NeurIPS 2018. arXiv:1806.07572

[tsai-11] Yao-Hung Hubert Tsai 외, 〈Transformer Dissection: A Unified Understanding of Transformer's Attention via the Lens of Kernel〉, EMNLP 2019. arXiv:1908.11775

[performer-12] Krzysztof Choromanski 외, 〈Rethinking Attention with Performers〉, ICLR 2021. arXiv:2009.14794

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]