Kernel Method는 어디서 Neural Network와 만나는가

Kernel method는 오랫동안 deep learning과 별개의 세계로 여겨졌다. 하나는 볼록 최적화와 RKHS 이론에, 다른 하나는 확률적 경사법과 표현 학습에 뿌리를 두고 있다. 그런데 이 시리즈의 네 챕터 — MKL, Random Features, Deep Kernel Learning, NTK — 를 나란히 놓으면 하나의 흐름이 보인다. kernel이 점점 데이터로부터 학습되고, 마침내 무한폭 NN과 정확히 동치가 된다. 이 수렴은 우연인가, 아니면 같은 원리의 다른 표현인가?

Kernel 선택을 데이터에 맡기다 — MKL

Multiple Kernel Learning (MKL)의 출발점은 단순하다. 후보 kernel $\{k_1, \ldots, k_L\}$이 각각 PD이면, 볼록 결합

$k_\beta(x, y) = \sum_{l=1}^L \beta_l k_l(x, y), \quad \beta_l \geq 0, \sum_l \beta_l = 1$

도 PD다. $\beta$를 데이터로부터 학습하면 “어떤 kernel을 써야 하는가”라는 질문이 최적화 문제로 바뀐다.

실용적 알고리즘인 SimpleMKL은 이 구조를 활용한다. $\beta$ 고정 → 표준 SVM 풀기 → dual objective의 $\beta$-gradient로 simplex 위 투영 → 수렴까지 반복. 복잡도는 $O(n^2 L T)$로 원래 SDP formulation의 $O(n^6)$보다 실용적이다.

$\ell_p$-norm 변형 ($\sum \beta_l^p = 1$)은 sparsity를 제어한다. $p=1$이면 Lasso처럼 irrelevant kernel을 0으로 밀어내고, $p=2$이면 모든 kernel을 고르게 사용한다.

$O(n^3)$를 피하는 Fourier 우회로 — Random Features

Kernel method의 근본 병목은 $n \times n$ gram matrix다. $n = 10^6$이면 $O(n^3)$은 불가능하다. Rahimi & Recht (2007)의 Random Features는 이 병목을 Bochner 정리로 우회한다.

shift-invariant kernel $\kappa(z) = \kappa(x - y)$가 PD이면, Bochner 정리에 의해

$\kappa(z) = \int_{\mathbb{R}^d} e^{i\omega^\top z} \, d\mu(\omega)$

를 만족하는 양의 유한 측도 $\mu$가 존재한다. 이것은 $\kappa(x-y) = \mathbb{E}_{\omega \sim \mu}[e^{i\omega^\top x} e^{-i\omega^\top y}]$를 의미하므로, Monte Carlo 근사가 가능하다.

$\phi_{\text{RFF}}(x) = \sqrt{2/D}\,(\cos(\omega_j^\top x + b_j))_{j=1}^D, \quad \omega_j \sim \tilde{\mu},\; b_j \sim U[0, 2\pi]$

실용적 함의는 명확하다. $\Phi = [\phi(x_1); \ldots; \phi(x_n)] \in \mathbb{R}^{n \times D}$를 구성하면 KRR은 $O(nD^2 + D^3)$으로 풀린다. $D = 1000$, $n = 10^6$에서 $O(n^3) = 10^{18}$이 $O(nD^2) = 10^{12}$로 줄어든다. RBF kernel의 경우 $\omega_j \sim \mathcal{N}(0, I/\sigma^2)$로 샘플링하면 된다.

GP의 불확실성 + NN의 표현 학습 — Deep Kernel Learning

MKL은 fixed candidate kernel들을 결합한다. Random Features는 무한 차원 feature space를 Monte Carlo로 근사한다. Deep Kernel Learning (Wilson et al. 2016)은 다른 방향을 택한다. NN이 feature를 직접 학습하게 하고, 그 위에 GP를 얹는다.

$k_\theta(x, y) := k_0(\phi_\theta(x), \phi_\theta(y))$

composition $k_\theta$는 $\phi_\theta$가 임의의 NN이어도 PD다 (composition 정리). 학습 목표는 marginal likelihood의 최대화다.

$\mathcal{L}(\theta, \ell, \sigma_n) = -\frac{1}{2} y^\top (K_\theta + \sigma_n^2 I)^{-1} y - \frac{1}{2} \log|K_\theta + \sigma_n^2 I| - \frac{n}{2}\log 2\pi$

$\theta$ (NN weights), $\ell$ (base kernel length-scale), $\sigma_n$ (noise)를 backprop으로 공동 학습한다. 핵심은 자동 정규화다. NN이 overfit하려 하면 feature들이 너무 독특해져 $\log|K_\theta|$가 커지고 objective가 떨어진다. “데이터를 설명하는 가장 단순한 feature”가 Bayesian Occam’s razor로 선택된다.

대규모 데이터에서는 SVDKL이 필요하다. feature space의 inducing point $Z \in \mathbb{R}^{m \times D}$와 VFE ELBO로 mini-batch stochastic gradient를 가능하게 하면 복잡도가 $O(Bm^2)$로 줄어 $n = 10^6$ 이상으로 scaling된다.

무한폭에서 NN = Kernel Method — NTK

Deep Kernel Learning은 “NN을 kernel에 사용”하는 방향이었다. NTK는 역방향을 증명한다. “NN 자체가 kernel method다”.

$\Theta_\theta(x, y) := \nabla_\theta f_\theta(x)^\top \nabla_\theta f_\theta(y)$

이 Neural Tangent Kernel은 feature map $\phi_\theta(x) = \nabla_\theta f_\theta(x)$의 내적이므로 자동으로 PD다.

NTK의 eigendecomposition은 학습 동력학을 직접 설명한다. 큰 고유값 방향(smooth function)은 training 초기에 빠르게 fit되고, 작은 고유값 방향(high-frequency)은 느리게 혹은 전혀 fit되지 않는다. Early stopping은 이 관점에서 자연스러운 정규화다.

정리

네 챕터를 관통하는 흐름은 하나다 — “kernel을 고정에서 학습으로”.

• MKL: fixed candidate kernel들의 볼록 결합을 학습한다. global optimum 보장, $O(n^2 L T)$.
• Random Features: shift-invariant kernel의 Fourier 구조를 Monte Carlo로 근사해 $O(n^3) \to O(nD^2)$로 scaling한다.
• Deep Kernel Learning: NN feature를 marginal likelihood로 공동 학습해 GP의 불확실성과 NN의 표현력을 통합한다.
• NTK: 무한폭 NN gradient flow가 kernel regression과 정확히 동치임을 증명한다.

kernel theory와 deep learning은 서로 다른 언어로 같은 문제를 말하고 있었다.