차원의 저주

통계 수치해석 마지막 수정: 2026-08-20 04:48:51

1. 개요[편집]

차원의 저주(curse of dimensionality)는 차원 $d$ 가 커질수록 공간의 부피·표본·계산량이 지수적으로 폭발하고, 저차원의 기하학적 직관이 통째로 무너지는 현상 전반을 가리키는 말이다. 리처드 벨먼이 1957년 동적계획법 책에서 상태공간을 격자로 훑는 비용을 두고 처음 쓴 표현인데¹, 이후 수치해석·통계·머신러닝·최적화 어디서든 “고차원에서 안 되는 이유”를 뭉뚱그려 부르는 이름이 됐다.

저주의 정체는 하나가 아니라 세 겹이다. (1) 격자 표본이 $N^d$ 로 터진다 — 축마다 점 10개면 10차원에서 이미 $10^{10}$ 개다. (2) 부피가 껍질과 구석으로 도망간다 — 고차원 공은 속이 비고 큐브는 모서리만 남는다. (3) 거리가 무의미해진다 — 모든 점이 서로 엇비슷하게 멀어져 “가까운 이웃”이라는 개념 자체가 힘을 잃는다. 이 셋이 맞물려 kNN·커널 밀도 추정·수치적분·과적합까지 광범위하게 발현된다. 재미있는 반전은, 바로 이 저주 때문에 차원과 무관한 몬테카를로 방법이 고차원에서 유일한 탈출구가 된다는 점이다.

2. 부피는 껍질로 도망간다[편집]

반지름 1인 $d$ 차원 공에서, 반지름 $1-\varepsilon$ 안쪽에 든 부피의 비율은

\frac{V(1-\varepsilon)}{V(1)} = (1-\varepsilon)^d \xrightarrow{d\to\infty} 0

이다. $d$ 가 크면 이 값이 0으로 가니, 부피의 거의 전부가 두께 $\varepsilon$ 짜리 바깥 껍질에 몰린다. $\varepsilon=0.01$ 이라도 $d=1000$ 이면 안쪽 99% 반지름 공이 전체 부피의 $0.99^{1000}\approx 4\times10^{-5}$ 밖에 안 된다. 고차원 오렌지는 과육 없이 껍질만 있는 셈이다.

큐브 쪽은 반대로 구석으로 도망간다. 변의 길이 1인 $d$ 차원 큐브에 내접하는 공의 부피는

V_{\text{ball}} = \frac{\pi^{d/2}}{2^d\,\Gamma\!\left(\tfrac{d}{2}+1\right)} \xrightarrow{d\to\infty} 0

이라, 큐브 부피의 거의 전부가 내접구 바깥, 즉 모서리 근처에 있다. $d=10$ 이면 내접구가 큐브의 0.25%뿐이다. “정육면체 한가운데 공이 꽉 찼다”는 3차원 그림은 고차원에서 완전히 틀린다.

가우스 분포에서도 같은 일이 벌어진다. 표준정규 $\mathbf{x}\sim\mathcal N(0,I_d)$ 에서 원점은 밀도가 가장 높은 점이지만, 대부분의 표본은 원점이 아니라 반지름 $\sqrt d$ 짜리 얇은 껍질에 놓인다. $\|\mathbf{x}\|^2$ 이 자유도 $d$ 인 카이제곱을 따라 평균 $d$ , 표준편차 $\sqrt{2d}$ 이므로, 상대 폭 $\sqrt{2d}/d = \sqrt{2/d}\to 0$ 으로 껍질이 갈수록 얇아진다. 고차원 가우스는 종 모양 덩어리가 아니라 비눗방울이다. 이것이 측도 집중(concentration of measure) 현상의 한 얼굴이다.

3. 근접이웃이 무의미해진다[편집]

데이터가 고차원이면 “가장 가까운 점”과 “가장 먼 점”의 거리가 서로 비슷해진다. 베이어 등(1999)의 결과를 거칠게 옮기면, 꽤 일반적인 분포에서

\frac{d_{\max} - d_{\min}}{d_{\min}} \xrightarrow{d\to\infty} 0

이 성립한다 — 최근접과 최원접의 상대 격차가 사라진다. 원인은 거리 집중이다. 각 좌표가 독립이면 제곱거리 $\sum_{i=1}^d (x_i - y_i)^2$ 는 $d$ 개 항의 합이라 큰 수의 법칙으로 평균 근방에 몰리고, 상대 변동이 $1/\sqrt d$ 로 줄어든다. 모든 쌍의 거리가 거의 같아지니 “이웃”이라는 순위가 잡음에 묻힌다.

여기에 각도까지 붙는다. 고차원에서 무작위로 뽑은 두 벡터는 거의 확실히 직교에 가깝다 — 내적이 0 근방에 집중한다. 저차원에서 벡터들이 방향을 공유하던 직관은 사라지고, 모두가 서로 수직인 “고슴도치” 공간이 된다. kNN 분류가 고차원에서 급격히 무너지고, 커널 밀도 추정의 대역폭 선택이 절망적으로 어려워지는 근본 원인이 이 거리·각도 집중이다.

4. 격자는 지수로, 몬테카를로는 차원 독립으로[편집]

수치적분에서 저주가 가장 정량적으로 드러난다. $d$ 차원 적분을 축마다 $n$ 점 격자로 수치적분하면 점의 개수는 $N = n^d$ 다. 정칙 격자 규칙(사다리꼴·심프슨·가우스 구적)의 오차는 1차원에서 $O(n^{-p})$ 로 좋지만, 총 점수 $N$ 으로 바꿔 쓰면

\text{error} \sim n^{-p} = N^{-p/d}

이라 차원이 오를수록 수렴 지수가 $1/d$ 로 깎인다. $d=20$ 에서 4차 정확도 규칙조차 $N^{-1/5}$ — 사실상 개점휴업이다. 이것이 벨먼의 원래 저주다.

몬테카를로 방법은 이 벽을 우회한다. $N$ 개 난수 표본의 평균으로 적분을 추정하면 중심극한정리로 오차가

\text{error} \sim \frac{\sigma}{\sqrt N}

인데, 이 $1/\sqrt N$ 에는 $d$ 가 들어 있지 않다. 차원은 상수 $\sigma$ (피적분함수의 분산)에만 스며들 뿐 수렴 지수를 건드리지 않는다. 저차원( $d\lesssim 4$ )에서는 격자 구적이 몬테카를로를 압도하지만, 어느 차원을 넘으면 $N^{-p/d}$ 가 $N^{-1/2}$ 보다 나빠져 몬테카를로가 역전한다 — 고차원 적분·금융공학·통계물리에서 몬테카를로가 사실상 유일한 선택인 이유다. 준몬테카를로는 저불일치 수열로 $\sigma$ 앞의 로그 인자까지 다듬어 $\approx N^{-1}$ 에 근접시키지만, 유효 차원이 낮을 때만 효과가 좋다는 단서가 붙는다.

한편 피적분함수가 충분히 매끄러우면 스몰략 격자(sparse grid)가 절충안이 된다. 완전 텐서곱 격자에서 “고차 교차항”에 해당하는 점을 솎아내 점수를 $N^d$ 에서 $N(\log N)^{d-1}$ 규모로 줄이면서도, 혼합 매끄러움 가정 아래 정확도를 상당 부분 지킨다. 저주를 완전히 없애진 못하고 지수를 로그로 완화할 뿐이지만, 중간 차원( $d\sim 10\text{–}50$ )에서 실전 가치가 크다.

5. 그런데 왜 머신러닝은 작동하는가[편집]

이 정도면 고차원에서 아무것도 안 될 것 같은데, 실제로는 수백만 차원 신경망이 잘만 돌아간다. 저주와 현실의 이 간극을 메우는 개념이 매니폴드 가설(manifold hypothesis)이다 — 자연 데이터(이미지·음성·문장)는 형식적으로는 고차원 벡터지만, 실제로는 훨씬 낮은 내재 차원(intrinsic dimension)의 곡면 위에 몰려 있다는 것이다. 저주가 매기는 값은 명목 차원 $d$ 가 아니라 이 내재 차원이라, 표본이 얇은 매니폴드에 집중되면 유효 저주가 완화된다.

그럼에도 저주는 과적합의 형태로 반드시 청구서를 내민다. 특징(feature) 수가 표본 수에 견줘 커지면 모델이 잡음까지 외워 버리고, 고차원 공간에서는 아무 데이터나 선형 분리가 가능해져(커버의 정리) 일반화가 무너진다. “차원을 늘리면 표현력이 는다”와 “차원을 늘리면 표본이 지수로 더 필요하다”는 언제나 같이 온다. 정규화, 차원 축소(PCA·오토인코더), 특징 선택은 전부 이 저주에 물리는 세금을 깎으려는 장치다. 경사하강법이 고차원에서 의외로 잘 되는 것도 저주의 다른 얼굴 덕이다 — 고차원에서는 나쁜 국소최소점보다 안장점이 압도적으로 많고, 안장점은 빠져나갈 방향이 늘 있어 최적화가 갇히지 않는다.

6. 관련 문서[편집]

몬테카를로 방법 · 준몬테카를로 · 수치적분
스몰략 격자 · 과적합 · 경사하강법
kNN · 커널 밀도 추정
통계 · 수치해석

벨먼의 원문은 동적계획법에서 상태 변수가 열 몇 개만 돼도 표를 채우는 비용이 감당 불가가 된다는 맥락이었다. “curse”라는 극적인 단어가 학계에 이렇게 오래 박제될 줄은 본인도 몰랐을 것이다. 참고로 “동적계획법(dynamic programming)“이라는 이름도 벨먼이 예산 심사관에게 수학 냄새를 숨기려 일부러 지은 작명이라는 회고가 있다. ↩