나이스트룀 근사

1. 개요[편집]

나이스트룀 근사 Nyström Approximation
이름의 출처	E. J. Nyström (1930) — 적분방정식의 구적법 이산화
기계학습 도입	Williams & Seeger (2001)
근사식	K ≈ C W+ CT (C = K 의 랜드마크 열, W = 그 부분행렬)
계수	최대 m (랜드마크 개수)
비용	O(nm2 + m3), 메모리 O(nm)
정확한 해	O(n3), 메모리 O(n2)
오차의 정체	슈어 보수 — 항상 PSD, 즉 과소추정

커널 행렬 전체를 만들 여유는 없다. 그런데 열 몇 개는 만들 수 있다. 그러면 그 열들로 나머지를 지어 올리면 되지 않나?

나이스트룀 근사는 $n\times n$ 양의 준정부호 커널 행렬 $K$ 를, 그중 $m\ll n$ 개의 열만 실제로 계산해 $K \approx CW^{+}C^{\mathsf T}$ 로 재구성하는 저계수 근사 기법이다. 여기서 $S$ 는 크기 $m$ 의 랜드마크(landmark, 지표점) 집합이고 $C = K_{:,S}\in\mathbb R^{n\times m}$, $W = K_{S,S}\in\mathbb R^{m\times m}$, $W^{+}$ 는 유사역행렬이다.

동기는 커널 트릭이 남긴 청구서 그대로다. 표현자 정리는 해가 $f=\sum_i\alpha_ik(\cdot,x_i)$ 꼴임을 보장하지만 계수를 구하는 비용은 $O(n^3)$ 이고, 그 앞에 $O(n^2)$ 짜리 그람 행렬이 버티고 있다. $n=10^5$ 이면 배정밀도 그람 행렬만 80 GB다. 나이스트룀은 그 행렬을 아예 만들지 않고 $n\times m$ 조각 하나로 대체한다. 커널 값을 $nm$ 번만 평가하므로 커널 평가 자체가 비싼 문제(분자 지문, 그래프 커널)에서 특히 남는 장사다.

이 문서는 왜 이 근사가 정당하고 언제 무너지는가를 다룬다. 커널화 가능한 알고리즘의 목록과 트릭 자체의 논리는 커널 트릭에, 함수공간 쪽 배경은 재생 커널 힐베르트 공간에 있다.

2. 적분방정식에서 온 이름[편집]

이름이 통계학자도 아니고 기계학습 연구자도 아닌 1930년대 핀란드 수치해석자에게서 온 데는 이유가 있다.¹ 에베르트 요하네스 나이스트룀이 다룬 것은 제2종 프레드홀름 적분방정식의 고유값 문제였다.

$$\int_{\mathcal X} k(x,y)\,\phi(y)\,dp(y) \;=\; \lambda\,\phi(x)$$

적분을 수치적분 규칙으로 이산화한다. 절점 $y_1,\dots,y_m$ 과 가중치 $w_j$ 를 잡으면

$$\sum_{j=1}^{m} w_j\, k(x,y_j)\,\phi(y_j) \;\approx\; \lambda\,\phi(x)$$

이고, $x$ 에 절점들을 차례로 대입하면 그냥 $m\times m$ 행렬 고유값 문제가 된다. 여기까지는 평범한 구적법이다. 나이스트룀의 요령은 그다음이다 — 이렇게 얻은 이산 고유벡터를 위 식의 오른쪽에 도로 집어넣으면, 절점이 아닌 임의의 $x$ 에서도 고유함수 값이 나온다.

$$\phi(x) \;\approx\; \frac{1}{\lambda}\sum_{j=1}^{m} w_j\, k(x,y_j)\,\phi(y_j)$$

이것이 나이스트룀 확장(Nyström extension)이고, 저계수 근사라는 이름의 조상이다. 커널 행렬 판본은 이 절차를 문자 그대로 번역한 것이다. 절점 = 랜드마크, 가중치 = 균등하면 $1/m$, 그리고 확장 공식을 $n$ 개 점 전부에 적용해 다시 조립하면 정확히 $CW^{+}C^{\mathsf T}$ 가 나온다. 실제로 $W = U_W\Lambda_WU_W^{\mathsf T}$ 로 두고 확장된 고유벡터를 $\tilde U = CU_W\Lambda_W^{-1}$ 라 하면

$$\tilde U\,\Lambda_W\,\tilde U^{\mathsf T} \;=\; CU_W\Lambda_W^{-1}U_W^{\mathsf T}C^{\mathsf T} \;=\; C\,W^{+}C^{\mathsf T}$$

로 두 서술이 같은 물건임이 한 줄에 확인된다. 여기서 나오는 명시적 특징 사상

$$\tilde{\boldsymbol\varphi}(x) \;=\; W^{-1/2}\,\mathbf k_S(x), \qquad \mathbf k_S(x) = \big[k(x,x_{s_1}),\dots,k(x,x_{s_m})\big]^{\mathsf T}$$

가 실전에서 쓰는 형태다. $\tilde{\boldsymbol\varphi}(x)^{\mathsf T}\tilde{\boldsymbol\varphi}(y) = \mathbf k_S(x)^{\mathsf T}W^{+}\mathbf k_S(y)$ 이므로, 커널 모형이 $m$ 차원 선형 모형으로 내려앉는다. 새 점에 대해서도 그대로 계산되므로 표본 밖 확장(out-of-sample extension)이 공짜인데, 다양체 학습에서 새 점을 기존 임베딩에 얹을 때 쓰는 그 공식이 바로 이것이다.

3. 오차는 슈어 보수다[편집]

근사의 성질이 한 줄로 정리되는 지점이 있다. 랜드마크를 앞으로 보내 블록으로 쓰면

$$K = \begin{pmatrix} W & B^{\mathsf T} \\ B & K_{22}\end{pmatrix}, \qquad C = \begin{pmatrix} W \\ B \end{pmatrix}$$

이고, 곱을 전개하면

$$K - CW^{+}C^{\mathsf T} = \begin{pmatrix} 0 & 0 \\ 0 & K_{22} - BW^{+}B^{\mathsf T}\end{pmatrix}$$

이 된다. 오른쪽 아래 블록이 정확히 $W$ 에 대한 $K$ 의 **슈어 보수**다. 여기서 세 가지가 즉시 따라온다.

• 랜드마크가 걸린 행과 열은 오차가 0이다. 근사는 그 부분에서 정확하고, 남은 오차는 전부 “랜드마크가 아닌 점들끼리의 관계”에 몰려 있다.
• $K$ 가 PSD면 슈어 보수도 PSD다. 따라서 $\tilde K \preceq K$ — 나이스트룀은 항상 과소추정한다. 유사도를 부풀리는 방향의 실패는 구조적으로 불가능하고, 이 성질 덕에 근사 커널을 넣어도 이차형식의 볼록성이 깨지지 않는다.
• $\operatorname{rank}(K)\le m$ 이고 랜드마크가 치역을 다 잡으면 오차가 정확히 0이다. 근사가 근사인 이유는 $K$ 의 계수가 $m$ 보다 크기 때문뿐이다.

$W$ 가 특이하거나 조건이 나쁠 때 역행렬 대신 유사역행렬을 쓰는 이유도 여기서 나온다. RBF 커널의 $W$ 는 이론상 정칙이지만 랜드마크 둘이 가까우면 조건수가 $10^{12}$ 를 넘기는 일이 흔하고, 그대로 $W^{-1}$ 을 계산하면 근사가 노이즈 증폭기로 변한다. 표준 처방은 고유값을 문턱 아래에서 잘라 낸 유사역행렬, 또는 $W+\epsilon I$ 로의 리지 안정화다.

4. 랜드마크 고르기[편집]

나이스트룀의 성능은 사실상 랜드마크 선택이 전부다. 계보상 세 갈래가 있다.

방법	비용	언제 쓰나
균등 무작위 표본	$O(m)$	기본값. 놀랄 만큼 잘 된다
리지 레버리지 점수	근사 계산에 $O(nm^2)$	이론적 보증이 필요할 때
k-평균 군집화 중심	반복당 $O(nmd)$	저차원 조밀 데이터에서 최강
탐욕적 피벗 (불완전 촐레스키 분해)	$O(nm^2)$	목표 오차를 정해 놓고 멈추고 싶을 때

균등 표본이 여전히 기본값인 것은 게으름이 아니다. 커널 행렬의 정보가 넓게 퍼져 있을 때는 무작위 $m$ 개가 스펙트럼의 상위 부분공간을 그럭저럭 덮고, 계산이 $O(m)$ 이라 전처리 비용이 0에 가깝다. 무너지는 조건은 명확하다 — 데이터가 크게 불균형해서 소수 표본이 스펙트럼을 지배하면 균등 표본은 그들을 놓친다.

리지 레버리지 점수는 그 실패를 정면으로 겨냥한다. 정규화 세기 $\lambda$ 에 대해

$$\ell_i(\lambda) \;=\; \big[K(K+n\lambda I)^{-1}\big]_{ii}$$

를 표본 $i$ 의 중요도로 쓰고, 이 값에 비례해 뽑는다. 합 $\sum_i\ell_i(\lambda)$ 가 곧 유효 차원(effective dimension) $d_{\text{eff}}(\lambda)$ 이고,² 이 개수 규모의 랜드마크만 뽑으면 상대 오차 보증이 나온다는 것이 알라위·마호니(2015) 계열의 결과다. 문제는 $\ell_i$ 자체가 $K$ 를 요구한다는 순환인데, 작은 무작위 표본으로 $\ell_i$ 를 근사한 뒤 그것으로 다시 뽑는 재귀적 절차가 표준 우회다.

k-평균 중심(장·창·곽, 2008)은 이론이 아니라 기하로 접근한다. 랜드마크는 데이터 점일 필요가 없으므로 군집 중심을 그대로 써도 되고, 그러면 오차가 군집화의 양자화 오차로 상계된다. 저차원 조밀 데이터에서 같은 $m$ 으로 균등 표본을 크게 이기는 경우가 많다. 대신 전처리에 군집화 한 판이 들어가고, 커널을 임의의 점에서 평가할 수 있어야 하므로 그래프·문자열 커널에는 못 쓴다.

탐욕적 피벗은 촐레스키 분해를 부분적으로만 진행하며 매 단계 잔차 대각이 가장 큰 점을 랜드마크로 뽑는 방식이다. 이것이 불완전 촐레스키와 같은 알고리즘이라는 것, 즉 “나이스트룀의 탐욕적 판본 = 피벗 촐레스키”라는 사실은 두 커뮤니티가 각자 발견한 뒤 한참 뒤에 합쳐졌다.³

5. 오차와 스펙트럼 감쇠[편집]

정확도를 지배하는 것은 알고리즘이 아니라 $K$ 의 고유값이 얼마나 빨리 죽는가다. 슈어 보수 형태에서 이미 예고된 결론이다 — 오차의 크기는 상위 $m$ 개 밖에 남은 스펙트럼 꼬리 $\sum_{i>m}\lambda_i$ 에 묶인다.

균등 표본에 대한 초기 결과(드리네아스·마호니, 2005)는

$$\lVert K - \tilde K\rVert_F \;\le\; \lVert K - K_m\rVert_F \;+\; \varepsilon\sum_{i=1}^{n}K_{ii}$$

꼴의 덧셈형 경계다. $K_m$ 은 최적 계수-$m$ 근사(저랭크 근사 문서의 에카르트-영). 여기서 정직하게 읽어야 할 것은 오른쪽 두 번째 항이다. 규격화된 커널이면 $\sum_iK_{ii}=n$ 이므로 오차 항이 $\varepsilon n$ 으로 표본 수에 비례해 커진다. 즉 이 경계는 큰 $n$ 에서 거의 아무 말도 안 해 준다. 레버리지 점수 표집으로 옮겨 가서야 $(1+\varepsilon)\lVert K-K_m\rVert$ 꼴의 곱셈형 상대 오차가 나오고, 기튼스·마호니(2013) 계열이 그 정리를 정리했다.

실무 감각으로 옮기면 이렇다.

• 스펙트럼이 지수적으로 죽으면(매끄러운 커널 + 저차원 데이터, 예컨대 좁지 않은 RBF) $m$ 을 수백만 잡아도 유효숫자 몇 자리가 맞는다. 고속 다중극자법이 서 있는 것과 같은 지반이다.
• 다항적으로 죽으면(마테른 계열, 고차원) $m$ 을 늘린 만큼만 정직하게 좋아진다. $m$ 을 $n$ 의 상수배로 키워야 하는 상황이면 나이스트룀을 쓸 이유가 없다.
• 거의 안 죽으면 — 고차원에서 좁은 RBF를 쓰면 $K$ 가 거의 단위행렬이 된다 — 저계수 근사가 원리적으로 불가능하다. 이건 근사의 실패가 아니라 커널 폭 선택의 실패이고, 차원의 저주가 그람 행렬에 나타나는 방식이다.

그래서 순서가 있다. $m$ 을 고르기 전에 작은 부분표본으로 그람 행렬의 고유값을 로그 축에 찍어 본다. 감쇠가 안 보이면 랜드마크를 늘릴 게 아니라 커널을 다시 골라야 한다.

6. 근사가 정규화가 되는 지점[편집]

의외의 결과가 하나 있다. 커널 능형회귀에서 랜드마크를 줄이는 것이 정확도를 해치기 전에 정규화로 먼저 작동한다는 것이다(루디·카모리아노·로사스코, 2015). $\tilde K$ 의 계수가 $m$ 이므로 근사 자체가 상위 $m$ 개 고유방향만 남기는 절단이고, 그것은 절단 특이값 분해식 정규화와 같은 효과를 낸다.

정량적 결론이 꽤 세다. 적절한 조건에서 $m = O(\sqrt n\,\log n)$ 규모의 랜드마크만 있어도 정확한 커널 능형회귀와 같은 최적 수렴률이 나온다. 즉 $O(n^3)$ 을 $O(n^2)$ 로 줄이면서 통계적으로 잃는 것이 없다. “근사니까 성능이 조금 떨어지겠지”라는 기본 가정이 여기서는 틀리고, 오히려 $m$ 을 $\lambda$ 와 함께 조율해야 하는 두 번째 정규화 손잡이로 다뤄야 한다. 실제로 $m$ 을 키우면서 $\lambda$ 를 고정하면 검증 오차가 어느 지점부터 다시 나빠지는 것을 관찰할 수 있다.

7. 어디에 쓰이나[편집]

• 커널 능형회귀·SVM. $\tilde{\boldsymbol\varphi}(x)\in\mathbb R^m$ 을 만들어 선형 모형으로 푼다. 학습 $O(nm^2+m^3)$, 예측 1건 $O(m)$ 회 커널 평가. 모형이 랜드마크 $m$ 개만 들고 다니면 되므로 배포 크기가 서포트 벡터 전체를 안고 있는 것보다 훨씬 작다.
• 스펙트럴 군집화. 유사도 행렬의 하위 고유벡터 몇 개만 필요한데 행렬이 $n^2$ 이라는 전형적 상황이다. 파울크스 외(2004)가 영상 분할에 이 조합을 쓴 뒤 표준이 됐다 — 화소 수십만 개의 유사도 행렬을 만들 방법이 애초에 없기 때문이다. 나이스트룀 확장이 “나머지 화소를 고유벡터 위로 보간”하는 역할을 그대로 한다.
• 가우시안 프로세스·크리깅. 유도점(inducing point) 기반 희소 GP의 골격이 나이스트룀이다. 사후평균·분산 계산이 $O(n^3)\to O(nm^2)$ 로 내려온다. 다만 예측 분산까지 그대로 근사하면 불확실성을 과소평가하는 것이 알려져 있고(과소추정 성질이 여기서는 부작용이다),⁴ 그래서 후속 판본들은 대각항을 보정하거나 유도점을 변분적으로 학습한다.
• 다양체 학습·커널 PCA의 표본 밖 확장. 새 점의 좌표를 재계산 없이 얻는다. 정확도는 새 점이 원 표본의 지지집합 안에 있을 때만 믿을 만하다.
• 커널 행렬-벡터 곱. $\tilde Kv = C(W^{+}(C^{\mathsf T}v))$ 를 $O(nm)$ 에 계산할 수 있으므로 켤레기울기법의 전처리기로도 쓴다. 이때는 $\tilde K$ 를 근사해로 쓰는 게 아니라 전처리기로만 쓰는 것이 정직한 용법이다.

8. 무작위 푸리에 특징과의 갈림길[편집]

같은 벽을 때리는 다른 망치가 무작위 푸리에 특징(RFF)이다. 두 방법의 차이는 단 한 줄로 요약된다. RFF는 커널만 보고 나이스트룀은 데이터도 본다.

	RFF	나이스트룀
무엇을 보나	커널의 스펙트럼 측도	실제 표본의 배치
적용 커널	이동불변 연속 커널만 (보흐너 정리)	임의의 PSD 커널
특징 준비	난수 생성 한 줄	랜드마크 선택 + $W^{-1/2}$ 분해
오차	$O(1/\sqrt D)$, 데이터와 무관	스펙트럼 꼬리에 의존, 빠르면 훨씬 좋음
스트리밍	자연스러움	랜드마크 확정 후에만
재현	시드 하나	랜드마크 좌표를 보관해야 함

스펙트럼이 빨리 죽는 실제 데이터에서는 같은 차원의 나이스트룀이 RFF보다 대체로 정확하다(양 외, 2012). 이유는 직관적이다 — 나이스트룀은 데이터가 실제로 놓인 곳에 기저를 배치하고, RFF는 데이터를 안 보고 주파수를 뿌리므로 아무도 살지 않는 영역에도 표현력을 낭비한다. 이론적으로도 RFF는 데이터 분포와 무관한 $1/\sqrt D$ 를 벗어나기 어려운 반면 나이스트룀의 경계는 스펙트럼 감쇠를 그대로 물려받는다.

그렇다고 나이스트룀이 상위호환은 아니다. 문자열·그래프처럼 이동불변이 정의되지 않는 커널에서는 RFF가 아예 못 쓰이므로 나이스트룀이 유일한 선택이고, 반대로 데이터가 도착하기 전에 특징을 확정해 두어야 하는 분산·스트리밍 환경에서는 RFF가 유일한 선택이다. 선택 기준이 정확도가 아니라 워크플로인 경우가 많다. 흥미롭게도 RFF에 레버리지 점수 재가중을 얹는 순간 두 계열의 이론적 간극이 크게 좁혀지는데, 그것은 RFF가 데이터를 보기 시작했다는 뜻이기도 하다.

9. 실무 요령[편집]

• $W$ 의 조건수를 반드시 찍어 본다. 나이스트룀 구현 사고의 대부분이 여기서 난다. 랜드마크에 중복점이나 거의 중복인 점이 섞이면 $W$ 가 특이해지고, inv를 그대로 부른 코드는 조용히 쓰레기를 낸다. pinv + 고유값 절단이 기본값이어야 한다.
• $\tilde K$ 를 명시적으로 조립하지 마라. $CW^{+}C^{\mathsf T}$ 를 곱해 놓는 순간 $O(n^2)$ 메모리가 돌아와서 애초에 근사한 이유가 사라진다. 인수 $C$ 와 $W^{-1/2}$ 형태를 끝까지 유지한다.
• $m$ 은 정규화 손잡이다. 교차검증 격자에 $\lambda$ 만 넣고 $m$ 을 고정하는 것은 절반만 튜닝하는 것이다.
• 랜드마크는 고정하고 기록한다. 무작위 표본을 매번 다시 뽑으면 모형이 재현되지 않는다. RFF가 시드 하나로 끝나는 것과 달리 여기서는 좌표를 보관해야 한다.
• 표준화가 먼저다. 커널 방법 전체에 해당하는 1번 항목이며, 스펙트럼 감쇠 자체가 스케일링에 좌우된다.
• CUR 과의 관계를 알아 두면 문헌 읽기가 쉬워진다. 나이스트룀은 대칭 PSD 행렬에 대한 CUR 분해의 특수 경우이고, 비대칭 일반 행렬로 넘어가면 열과 행을 따로 뽑는 CUR이 된다. 랜덤화 SVD가 행렬을 곱해서 부분공간을 잡는다면 이쪽은 뽑아서 잡는다는 것이 계열의 차이이고, 원소를 해석 가능하게 유지한다는 것이 뽑기 계열의 덤이다.

10. 관련 문서[편집]

• 커널 트릭 · 재생 커널 힐베르트 공간 · 보흐너 정리
• 무작위 푸리에 특징 · 저랭크 근사 · 랜덤화 SVD · 절단 특이값 분해
• 슈어 보수 · 촐레스키 분해 · 조건수 · 고유값 문제
• 가우시안 프로세스 · 크리깅 · 능형회귀 · 티호노프 정규화
• 스펙트럴 군집화 · 커널 PCA · 다양체 학습 · 다차원 척도법
• 수치적분 · 고속 다중극자법 · 전처리기 · 켤레기울기법

11. Footnotes[편집]

1. Nyström, E. J. (1930). “Über die praktische Auflösung von Integralgleichungen mit Anwendungen auf Randwertaufgaben.” Acta Mathematica 54. 경계값 문제를 적분방정식으로 바꿔 손으로 푸는 것이 목적이었고, 커널 기계학습은커녕 컴퓨터도 없던 시절이다. 90년 뒤 GPU 위에서 자기 이름이 불릴 줄은 몰랐을 것이다. 이 바닥에서 “새 알고리즘”의 상당수는 1930년대 수치해석 교과서의 재발견이라는 사실을 잊을 만하면 상기시켜 주는 사례. ↩

2. 유효 차원 $d_{\text{eff}}(\lambda)=\operatorname{tr}(K(K+n\lambda I)^{-1})$ 은 “이 정규화 세기에서 모형이 실제로 쓰는 자유도”라는 해석이 붙는 양이다. $\lambda\to0$ 이면 $\operatorname{rank}(K)$ 로, $\lambda\to\infty$ 면 0으로 간다. 선형회귀의 자유도 $\operatorname{tr}(H)$ 를 커널로 옮긴 것이고, 능형회귀 문서의 “유효 자유도”와 같은 물건이다. 이름만 세 개인 개념이 또 하나 늘었다. ↩

3. 탐욕적 피벗이 곧 불완전 촐레스키라는 것을 알고 나면 랜드마크 선택 논쟁의 절반이 정리된다. 수치선형대수에서 “완전 피벗 촐레스키의 조기 종료”로 30년 전에 분석이 끝난 문제였고, 기계학습 쪽은 그걸 모른 채 “탐욕적 나이스트룀”이라는 이름으로 다시 실험했다. 학제 간 용어 장벽의 비용을 계산하면 아마 논문 수십 편어치는 될 것이다. ↩

4. 과소추정 성질($\tilde K\preceq K$)은 대체로 축복이지만 GP 예측 분산에서는 재앙이다. 사후분산이 $k(x,x) - \mathbf k^{\mathsf T}(K+\sigma^2I)^{-1}\mathbf k$ 꼴인데 $K$ 를 아래로 근사하면 빼는 항이 줄어드는 게 아니라 구조가 뭉개져서, 랜드마크에서 먼 곳의 불확실성이 실제보다 작게 나온다. “모른다고 말해야 할 자리에서 자신 있게 틀린다”는 것이 대리 모델 기반 최적화에서 가장 비싼 실패 모드다. ↩