커널 방법과 최근접 이웃

최근접 이웃

정의. kNN 회귀는 새 입력 $\mathbf{x}$에서 가장 가까운 학습 점 $k$개의 집합 $\mathcal{N}_k(\mathbf{x})$를 찾아 그 출력의 평균을 예측으로 쓴다.

분류에서는 다수결을 쓴다. 학습 단계에서 하는 일이 없고(데이터를 저장할 뿐이다), 가정은 하나뿐이다. 입력 공간에서 가까운 점은 출력도 비슷하다. $k$는 유연성을 정한다. $k = 1$이면 학습 데이터를 그대로 외우고, $k = N$이면 16.1장의 평균 baseline이 된다. 그 사이의 $k$는 교차검증으로 고른다.

거리와 스케일. "가깝다"는 거리로 정의되고, 보통의 Euclid 거리 $\lVert\mathbf{x} - \mathbf{x}'\rVert = \sqrt{\sum_j (x_j - x'_j)^2}$는 모든 특징을 같은 무게로 더한다. 그런데 특징의 단위가 다르면 숫자의 크기가 다르고, 숫자가 큰 특징이 거리를 지배한다. 반응 속도를 농도(0.01–0.2 mol/L)와 온도(280–360 K)로 예측하는 문제에서 확인한다. 속도는 농도의 제곱에 비례하고 온도에는 Arrhenius 식처럼 지수적으로 의존한다.

import numpy as np
from sklearn.neighbors import KNeighborsRegressor
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

rng = np.random.default_rng(0)
n = 600
conc_mol_l = rng.uniform(0.01, 0.2, n)                     # 농도 [mol/L]
temp_k = rng.uniform(280, 360, n)                          # 온도 [K]
rate = 50 * conc_mol_l**2 * np.exp(-2000 * (1 / temp_k - 1 / 320))   # 반응 속도 (2차 반응 + Arrhenius)
rate += rng.normal(0, 0.02, n)                             # 측정 잡음
X = np.column_stack([conc_mol_l, temp_k])                  # (600, 2)
tr, te = slice(0, 400), slice(400, None)
for label, model in [("표준화 없이", KNeighborsRegressor(10)),
                     ("표준화 후", make_pipeline(StandardScaler(), KNeighborsRegressor(10)))]:
    model.fit(X[tr], rate[tr])
    print(f"{label}: 시험 R² {model.score(X[te], rate[te]):.3f}")

표준화 없이: 시험 R² 0.176
표준화 후: 시험 R² 0.991

표준화 없이 계산한 거리에서 농도 차이는 최대 0.19, 온도 차이는 최대 80이다. 거리는 사실상 온도만 보고, 가장 중요한 특징인 농도는 무시된다. 표준화하면 두 특징이 같은 척도에 놓여 $R^2$가 0.176에서 0.991로 오른다. 16.2장에서 정규화 벌점이 단위를 탔던 것과 같은 문제다. 거리 기반 방법은 표준화를 pipeline에 넣고, 학습 데이터의 통계량으로만 표준화한다.

표준화는 "모든 특징이 같은 정도로 중요하다"는 가정이기도 하다. 중요하지 않은 특징도 거리에 같은 무게로 들어간다. 이것이 다음 문제로 이어진다.

차원의 저주. 입력 차원이 높아지면 "가까운 이웃"이라는 개념 자체가 무너진다. 단위 초입방체 $[0, 1]^d$에 데이터가 고르게 퍼져 있을 때, 데이터의 비율 $r$을 담는 작은 초입방체의 한 변 길이는 $r^{1/d}$이다. 데이터의 1%를 이웃으로 모으려면 $d = 2$에서는 한 변이 0.1이면 되지만, $d = 10$에서는 $0.01^{1/10} \approx 0.63$, 즉 각 축 범위의 63%를 덮어야 한다. 이웃이 더 이상 국소적이지 않다. 또한 차원이 높으면 한 점에서 가장 가까운 점과 가장 먼 점까지의 거리가 비슷해진다(Beyer 외, 1999). 출력이 앞의 두 특징에만 의존하고 나머지는 무관한 잡음 특징인 데이터에서, 잡음 특징을 늘려 가며 kNN과 선형 모델을 비교한다.

from sklearn.linear_model import RidgeCV

def task(n, d_noise, rng):                                 # 출력은 앞의 두 특징에만 의존
    X = rng.uniform(-1, 1, (n, 2 + d_noise))               # (n, 2 + d_noise)
    y = np.sin(3 * X[:, 0]) + X[:, 1] ** 2 + rng.normal(0, 0.1, n)
    return X, y

for d_noise in (0, 4, 16, 64):
    r = np.random.default_rng(1)
    Xa, ya = task(500, d_noise, r)
    Xb, yb = task(500, d_noise, r)
    knn = KNeighborsRegressor(10, algorithm="kd_tree").fit(Xa, ya).score(Xb, yb)
    lin = RidgeCV().fit(Xa, ya).score(Xb, yb)
    d = np.linalg.norm(Xb[:1] - Xa, axis=1)                # 시험점 하나에서 학습점까지 거리, (500,)
    print(f"차원 {2 + d_noise:2d}: 최근접/최원 거리 비 {d.min() / d.max():.2f}  kNN R² {knn:.2f}  선형 R² {lin:.2f}")

차원  2: 최근접/최원 거리 비 0.06  kNN R² 0.96  선형 R² 0.56
차원  6: 최근접/최원 거리 비 0.21  kNN R² 0.76  선형 R² 0.54
차원 18: 최근접/최원 거리 비 0.42  kNN R² 0.41  선형 R² 0.57
차원 66: 최근접/최원 거리 비 0.69  kNN R² 0.19  선형 R² 0.50

잡음 특징이 0개일 때 kNN의 $R^2$는 0.96으로, 비선형 관계를 표현하지 못하는 선형 모델(0.56)보다 훨씬 낫다. 잡음 특징이 늘면 최근접/최원 거리 비가 0.06에서 0.69로 커지고, kNN은 0.19까지 떨어져 선형 모델보다 나빠진다. 선형 모델은 무관한 특징의 계수를 0 근처로 두면 되므로 거의 영향을 받지 않는다. 데이터 수가 같다면, 무관한 차원이 늘수록 국소적인 방법이 먼저 무너진다.

연구에서의 의미. kNN은 입력이 저차원이고 의미 있는 거리가 있을 때 강한 baseline이다. 차원이 높으면 특징 선택, 도메인 지식으로 만든 저차원 표현, 또는 학습된 표현(embedding) 위의 거리를 쓴다. 표현 학습 뒤 최근접 이웃 검색은 큰 데이터셋에서 지금도 표준 도구다.

SVM

왜 필요한가. 두 클래스를 가르는 초평면은 데이터가 분리 가능하면 무수히 많다. 로지스틱 회귀(16.2장)는 확률의 우도로 하나를 고른다. 서포트 벡터 머신(support vector machine, SVM)은 다른 기준을 쓴다. 두 클래스에서 가장 멀리 떨어진 초평면, 즉 마진(margin)이 가장 큰 초평면을 고른다(Cortes & Vapnik, 1995).

정의. 라벨을 $y_i \in \{-1, +1\}$로 두고 결정 함수를 $f(\mathbf{x}) = \mathbf{w}^\top\mathbf{x} + b$라 하자. 경계 $f = 0$에서 $f = \pm 1$인 두 평행 초평면까지의 거리를 합한 마진 폭은 $2/\lVert\mathbf{w}\rVert$이다. 마진을 최대화하는 것은 $\lVert\mathbf{w}\rVert$를 최소화하는 것이고, 마진 안으로 들어오거나 반대편에 놓이는 점은 슬랙 변수 $\xi_i \ge 0$으로 허용한다.

최적에서 $\xi_i = \max(0, 1 - y_i f(\mathbf{x}_i))$이므로, 이 문제는

와 같다. 첫 항이 hinge loss다. 올바른 쪽에 마진 이상 떨어진 점($y_i f(\mathbf{x}_i) \ge 1$)은 손실이 정확히 0이다. 둘째 항은 16.2장의 L2 정규화다. 즉 SVM은 "hinge loss + Ridge 벌점"인 선형 분류기이고, $C$가 클수록 정규화가 약하다. 로지스틱 회귀의 cross-entropy와 비교하면, cross-entropy는 확실히 맞힌 점에도 작은 손실을 계속 주지만 hinge loss는 마진 밖의 점을 완전히 무시한다.

쌍대 문제와 서포트 벡터. 위 문제의 Lagrange 쌍대(10.2장)는

이고, 해에서 $\mathbf{w} = \sum_i \alpha_i y_i \mathbf{x}_i$다. 상보 여유 조건 때문에 마진 밖에 있는 점은 $\alpha_i = 0$이다. $\alpha_i > 0$인 점, 즉 마진 위나 안쪽에 있는 점만 해에 기여하고, 이들을 서포트 벡터라 한다. 나머지 점은 지워도 해가 바뀌지 않는다.

from sklearn.svm import SVC

rng = np.random.default_rng(2)
Xs = np.vstack([rng.normal([-1.5, 0], 0.7, (100, 2)), rng.normal([1.5, 0], 0.7, (100, 2))])   # (200, 2)
ys = np.repeat([0, 1], 100)
for C in (0.01, 1.0, 100.0):
    svm = SVC(kernel="linear", C=C).fit(Xs, ys)
    w = svm.coef_[0]
    print(f"C = {C:6.2f}: 서포트 벡터 {svm.n_support_.sum():3d}개, 마진 폭 2/||w|| = {2 / np.linalg.norm(w):.2f}, 학습 정확도 {svm.score(Xs, ys):.3f}")
svm = SVC(kernel="linear", C=1.0, tol=1e-6).fit(Xs, ys)    # 해를 정밀하게 구한다
keep = np.ones(200, bool)
keep[np.setdiff1d(np.arange(200), svm.support_)[:50]] = False   # 서포트 벡터가 아닌 점 50개 제거
svm2 = SVC(kernel="linear", C=1.0, tol=1e-6).fit(Xs[keep], ys[keep])
same = np.allclose(svm.coef_, svm2.coef_, atol=1e-4) and np.allclose(svm.intercept_, svm2.intercept_, atol=1e-4)
print("서포트 벡터가 아닌 점 50개를 지워도 경계가 같은가:", same)

C =   0.01: 서포트 벡터  88개, 마진 폭 2/||w|| = 2.68, 학습 정확도 0.990
C =   1.00: 서포트 벡터  14개, 마진 폭 2/||w|| = 0.91, 학습 정확도 0.985
C = 100.00: 서포트 벡터   7개, 마진 폭 2/||w|| = 0.34, 학습 정확도 0.990
서포트 벡터가 아닌 점 50개를 지워도 경계가 같은가: True

$C$가 작으면(정규화가 강하면) 마진이 넓어지고(2.68) 마진 안에 들어오는 점이 많아져 서포트 벡터가 88개다. $C$를 키우면 마진이 좁아지고(0.34) 서포트 벡터가 7개로 준다. 서포트 벡터가 아닌 점 50개를 지우고 다시 학습해도 경계가 같다. 해가 소수의 경계 근처 점으로 정해진다는 것은 SVM의 장점(예측이 서포트 벡터 수에만 비례)이자 약점(경계 근처의 라벨 오류에 민감)이다.

쌍대 문제에서 입력은 내적 $\mathbf{x}_i^\top\mathbf{x}_j$로만 나타난다. 이를 커널 $k(\mathbf{x}_i, \mathbf{x}_j)$로 바꾸면 SVM은 커널이 정한 특징 공간에서 마진을 최대화하는 비선형 분류기가 된다. 이것이 다음 절의 커널 트릭이다. SVM의 출력은 확률이 아니라 부호 있는 점수 $f(\mathbf{x})$라는 점도 기억한다. 확률이 필요하면 별도의 보정 단계가 필요하다.

커널 방법

커널 트릭. 양의 정부호 커널 $k(\mathbf{x}, \mathbf{x}') = \langle\boldsymbol\phi(\mathbf{x}), \boldsymbol\phi(\mathbf{x}')\rangle$는 특징 사상 $\boldsymbol\phi$를 계산하지 않고 특징 공간의 내적을 준다. 내적만 쓰는 알고리즘은 모두 커널화할 수 있다. 자주 쓰는 커널은 다음과 같다.

커널 릿지 회귀. 표현자 정리(representer theorem, 7.9장)에 따라, RKHS에서 정규화된 최소제곱의 해는 $f(\mathbf{x}) = \sum_i \alpha_i k(\mathbf{x}, \mathbf{x}_i)$이고 계수는

로 구한다. $\mathbf{K}$는 학습 점들의 $N \times N$ Gram 행렬, $\mathbf{k}(\mathbf{x}) = (k(\mathbf{x}, \mathbf{x}_1), \dots, k(\mathbf{x}, \mathbf{x}_N))^\top$이다. 이것이 커널 릿지 회귀(kernel ridge regression, KRR)다. 선형 커널이면 16.2장의 Ridge와 같은 예측을 낸다.

GP와의 관계. Gaussian process 회귀는 함수 $f$ 자체에 사전분포를 둔다. 평균 0, 공분산 함수 $k$인 GP 사전분포와 분산 $\sigma^2$인 가우시안 관측 잡음을 가정하면, 관측 $\mathbf{y}$가 주어졌을 때 $f(\mathbf{x})$의 사후분포는 가우시안이고

이다(유도는 13.7장). 사후평균은 $\lambda = \sigma^2$인 KRR의 예측과 같은 식이다. 16.2장에서 Ridge가 가우시안 사전분포의 MAP였던 것과 같은 관계가 함수공간에서 성립한다. 차이는 GP가 사후분산, 즉 예측의 불확실성을 함께 준다는 것이다. 사후분산은 학습 점 근처에서 작고, 멀어지면 사전분산 $k(\mathbf{x}, \mathbf{x})$로 돌아간다.

from sklearn.gaussian_process import GaussianProcessRegressor
from sklearn.gaussian_process.kernels import RBF
from sklearn.kernel_ridge import KernelRidge

rng = np.random.default_rng(3)
x_tr = np.sort(rng.uniform(0, 10, 30))[:, None]            # 측정 위치, (30, 1)
y_tr = np.sin(x_tr[:, 0]) + rng.normal(0, 0.1, 30)
x_te = np.linspace(-2, 12, 141)[:, None]                   # 학습 범위 밖 포함, (141, 1)
ell, noise_var = 1.0, 0.1**2
krr = KernelRidge(kernel="rbf", gamma=1 / (2 * ell**2), alpha=noise_var).fit(x_tr, y_tr)
gp = GaussianProcessRegressor(RBF(ell), alpha=noise_var, optimizer=None).fit(x_tr, y_tr)
mean, std = gp.predict(x_te, return_std=True)              # (141,), (141,)
print("KRR 예측 = GP 사후평균:", np.allclose(krr.predict(x_te), mean, atol=1e-8))
for x0 in (5.0, 11.0, 12.0):
    i = np.argmin(np.abs(x_te[:, 0] - x0))
    print(f"x = {x0:4.1f}: 사후평균 {mean[i]:+.2f}, 사후표준편차 {std[i]:.2f}, 참값 {np.sin(x0):+.2f}")
for ell_try in (0.1, 1.0, 10.0):
    m = KernelRidge(kernel="rbf", gamma=1 / (2 * ell_try**2), alpha=noise_var).fit(x_tr, y_tr)
    rmse = np.sqrt(np.mean((m.predict(x_te[20:121]) - np.sin(x_te[20:121, 0])) ** 2))
    print(f"길이 척도 {ell_try:4.1f}: 학습 범위 안 RMSE {rmse:.3f}")

KRR 예측 = GP 사후평균: True
x =  5.0: 사후평균 -0.90, 사후표준편차 0.06, 참값 -0.96
x = 11.0: 사후평균 -0.27, 사후표준편차 0.80, 참값 -1.00
x = 12.0: 사후평균 -0.08, 사후표준편차 0.99, 참값 -0.54
길이 척도  0.1: 학습 범위 안 RMSE 0.421
길이 척도  1.0: 학습 범위 안 RMSE 0.100
길이 척도 10.0: 학습 범위 안 RMSE 0.595

같은 커널과 $\lambda = \sigma^2$에서 KRR 예측과 GP 사후평균이 일치한다. 학습 범위 $[0, 10]$ 안의 $x = 5$에서 사후표준편차는 0.06으로 작다. 범위를 벗어난 $x = 11, 12$에서는 사후평균이 0(사전평균)으로 돌아가고 사후표준편차가 사전표준편차 1에 다가간다. RBF 커널의 예측은 데이터에서 멀어지면 "모른다"로 돌아가고, GP는 그것을 불확실성으로 정직하게 보고한다. KRR은 같은 예측을 하면서 그 사실을 알려 주지 않는다.

커널 선택의 의미. 커널은 "어떤 함수가 그럴듯한가"에 대한 사전 가정이다. 길이 척도를 바꾼 마지막 세 줄이 그 효과를 보여 준다. $\ell = 0.1$은 측정 간격(평균 약 0.33)보다 짧아 학습 점 사이에서 예측이 0으로 꺼지고(RMSE 0.421), $\ell = 10$은 사인 곡선의 주기보다 길어 곡선을 펴 버린다(0.595). $\ell = 1$이 데이터의 실제 변동 척도와 맞는다(0.100). 커널 선택의 실무 원칙은 다음과 같다.

• 입력을 표준화하거나 특징마다 길이 척도를 둔다. RBF 커널도 거리의 함수이므로 kNN과 같은 스케일 문제가 있다. RBF 커널의 길이 척도는 하나뿐이라, 단위가 서로 다른 특징 모두에 맞는 값을 고를 수 없다. 아래 위젯의 농도·온도 자료에서 표준화 없이도 길이 척도를 크게 잡으면 시험 $R^2$가 0.95 가까이 오르는데, 농도 방향으로 거의 평평해진 커널이 매끄러운 저차 함수만 표현하고 참 함수가 마침 농도의 2차식이기 때문이다. 스케일과 길이 척도가 우연히 맞은 결과이므로 이것에 기대지 않는다. 특징마다 다른 길이 척도를 두는 ARD(automatic relevance determination) 커널은 무관한 특징의 길이 척도를 길게 만들어 그 특징을 사실상 무시한다.
• 하이퍼파라미터는 데이터로 고른다. KRR에서는 교차검증으로, GP에서는 주변우도(marginal likelihood)를 최대화해 길이 척도와 잡음 분산을 함께 고른다(13.7장).
• 알고 있는 구조를 커널로 넣는다. 주기성(일·연 주기), 매끄러움의 정도(Matérn), 추세(선형 커널과의 합)는 커널의 합과 곱으로 표현한다. 커널의 합은 성분 함수들의 합을, 곱은 상호작용을 뜻한다.

확장성

문제. 정확한 KRR과 GP는 $N \times N$ Gram 행렬을 만들고 $(\mathbf{K} + \lambda\mathbf{I})$의 선형계를 푼다. 메모리는 $O(N^2)$, 시간은 Cholesky 분해에 $O(N^3)$이다. $N = 10^4$이면 Gram 행렬만 float64로 800 MB이고, $N$이 두 배가 되면 시간은 약 8배가 된다. 예측도 학습 점 전체와의 커널 계산이 필요해 $O(N)$이다. kNN은 학습이 없지만 예측마다 이웃을 찾아야 하고, 고차원에서는 트리 기반 검색이 효율을 잃는다.

저랭크 근사. 해결책은 Gram 행렬을 랭크 $m \ll N$인 행렬로 근사하는 것이다. 그러면 $N \times m$ 특징 행렬 위의 Ridge 회귀가 되어 시간은 $O(Nm^2)$, 메모리는 $O(Nm)$이다.

• Nyström 근사는 학습 점 중 $m$개를 기준점(landmark)으로 골라 $\mathbf{K} \approx \mathbf{K}_{Nm}\mathbf{K}_{mm}^{-1}\mathbf{K}_{mN}$으로 근사한다(Williams & Seeger, 2001). 7.6장의 저랭크 근사를 열 일부만으로 하는 셈이다.
• Random features는 shift-invariant 커널이 어떤 분포의 Fourier 변환이라는 사실(Bochner 정리)을 쓴다. RBF 커널이면 $\boldsymbol\omega_j \sim \mathcal{N}(\mathbf{0}, \ell^{-2}\mathbf{I})$, $b_j \sim \mathrm{U}(0, 2\pi)$를 뽑아 $z_j(\mathbf{x}) = \sqrt{2/m}\cos(\boldsymbol\omega_j^\top\mathbf{x} + b_j)$를 만들면 $\mathbf{z}(\mathbf{x})^\top\mathbf{z}(\mathbf{x}') \approx k(\mathbf{x}, \mathbf{x}')$이다(Rahimi & Recht, 2007). 데이터와 무관하게 특징을 만든다.

from sklearn.kernel_approximation import Nystroem, RBFSampler
from sklearn.linear_model import Ridge

rng = np.random.default_rng(4)
Xl = rng.uniform(-3, 3, (2500, 2))                         # (2500, 2)
yl = np.sin(Xl[:, 0]) * np.cos(Xl[:, 1]) + rng.normal(0, 0.1, 2500)
Xa, ya, Xb, yb = Xl[:1500], yl[:1500], Xl[1500:], yl[1500:]
exact = KernelRidge(kernel="rbf", gamma=0.5, alpha=0.01).fit(Xa, ya)
print(f"정확한 KRR (1500×1500 Gram 행렬): 시험 R² {exact.score(Xb, yb):.3f}")
for m in (10, 50, 200):
    for name, feat in [("Nyström", Nystroem(gamma=0.5, n_components=m, random_state=0)),
                       ("random features", RBFSampler(gamma=0.5, n_components=m, random_state=0))]:
        model = make_pipeline(feat, Ridge(alpha=0.01)).fit(Xa, ya)
        print(f"m = {m:3d} {name:15s}: 시험 R² {model.score(Xb, yb):.3f}")

정확한 KRR (1500×1500 Gram 행렬): 시험 R² 0.961
m =  10 Nyström        : 시험 R² 0.805
m =  10 random features: 시험 R² 0.254
m =  50 Nyström        : 시험 R² 0.961
m =  50 random features: 시험 R² 0.957
m = 200 Nyström        : 시험 R² 0.961
m = 200 random features: 시험 R² 0.962

특징 10개로는 두 근사 모두 정확한 KRR에 못 미친다. 데이터에 맞춰 기준점을 고르는 Nyström(0.805)이 데이터와 무관한 random features(0.254)보다 훨씬 낫다. 특징 50개에서 두 방법 모두 정확한 KRR(0.961)에 거의 도달하고, 200개면 차이가 없다. 이 문제는 입력이 2차원이고 함수가 매끄러워 적은 특징으로 충분하다. 입력 차원이 높고 함수가 복잡하면 필요한 $m$이 커진다. $m$은 정확도와 비용 사이의 하이퍼파라미터이므로, $m$을 늘려 가며 검증 성능이 포화하는 지점을 찾는다.

연구에서의 의미. 데이터가 수천 개 이하이면 정확한 KRR·GP가 현실적이고, 불확실성이 필요하면 GP가 기본 선택이다. 수만 개 이상이면 Nyström·random features 같은 근사나, 16.4장의 트리 앙상블, 17장 이후의 신경망이 후보가 된다. random features 위의 선형 모델은 은닉층의 가중치를 고정한 2층 신경망과 같은 꼴이라, 커널 방법과 신경망을 잇는 다리 역할도 한다.

참고 문헌

• Cortes, Vapnik (1995). Support-vector networks. Machine Learning, 20(3), 273–297. — soft margin SVM과 커널을 이용한 비선형 분류
• Beyer, Goldstein, Ramakrishnan, Shaft (1999). When is "nearest neighbor" meaningful? Database Theory — ICDT'99, LNCS 1540, 217–235. — 차원이 높아질 때 최근접·최원 거리의 비가 1에 가까워지는 조건
• Williams, Seeger (2001). Using the Nyström method to speed up kernel machines. Advances in Neural Information Processing Systems 13, 682–688. — Gram 행렬의 Nyström 저랭크 근사
• Rahimi, Recht (2007). Random features for large-scale kernel machines. Advances in Neural Information Processing Systems 20, 1177–1184. — shift-invariant 커널의 random Fourier features 근사