데이터와 학습(Data and learning)

차원의 저주(Curse of dimensionality)

차원이 높아지면 공간이 기하급수적으로 넓어져 데이터가 텅 빈 듯 흩어지고, 거의 모든 점⁠(almost everywhere)⁠ 사이 거리가 비슷해져 '가깝다'는 말이 힘을 잃는 현상.

\frac{\max D - \min D}{\min D} \xrightarrow{\,d\to\infty\,} 0, \qquad \frac{V_d}{2^d} = \frac{\pi^{d/2}}{2^d\,\Gamma(d/2+1)} \xrightarrow{\,d\to\infty\,} 0

먼저 보면 좋은 개념벡터 큰 수의 법칙

한 변이 1인 d차원 정육면체 안에 점 64개를 무작위로 뿌리고, 두 점씩 짝지은 2016쌍의 거리를 모두 재 봅니다. 차원 $d =$ . 아래는 그 거리들을 평균⁠(mean)⁠ 거리로 나눠 그린 히스토그램입니다.

가로축은 (거리 ÷ 평균 거리). 청록 선이 가장 가까운 쌍, 분홍 선이 가장 먼 쌍입니다.

d = 1이나 2에서는 거리가 0 근처부터 평균의 두세 배까지 넓게 퍼져 있습니다. d를 키우면 히스토그램⁠(histogram)⁠이 1 근처로 좁게 몰립니다. 지금 가장 가까운 쌍은 , 가장 먼 쌍은 , 둘의 차이를 가장 가까운 거리로 나눈 비는 입니다. d = 1000이면 가장 가까운 쌍과 가장 먼 쌍의 차이가 겨우 13%쯤입니다. 모두가 모두에게서 비슷하게 멀면, '가장 가까운 이웃'을 찾는 최근접 이웃 분류⁠(k-nearest neighbors classification)⁠나 가까운 점끼리 묶는 k-평균 군집⁠(k-means clustering)⁠은 기댈 곳을 잃습니다.

까닭은 큰 수의 법칙⁠(law of large numbers)⁠입니다. 유클리드 거리⁠(Euclidean distance)⁠의 제곱은 좌표마다의 차이 제곱을 d개 더한 합이고, 0과 1 사이 두 균등 난수의 차이 제곱은 기댓값⁠(expected value)⁠이 1/6입니다. 그러니 거리 제곱 ÷ d는 1/6로 모이고, d가 크면 거리는 거의 $\sqrt{d/6}$ 입니다(지금 평균 , $\sqrt{d/6} =$ ). 흔들림은 중심극한정리⁠(central limit theorem)⁠대로 d와 상관없이 약 0.24에 머물러서, 평균에 대한 상대적인 폭은 $1/\sqrt d$ 로 줄어듭니다. 같은 이유로, 정육면체의 한가운데를 원점으로 옮겨 놓고 보면 무작위로 고른 두 점의 방향은 거의 직각이어서 코사인 유사도⁠(cosine similarity)⁠가 0 근처에 몰립니다. 한 꼭짓점⁠(vertex)⁠을 원점으로 두면 모든 좌표가 양수라서 이렇게 되지 않습니다.

공간이 텅 비는 것도 봅시다. 정육면체 $[-1,1]^d$ 에 꼭 맞게 들어간 반지름 1인 공은 d = 2에서 넓이⁠(area)⁠의 π/4 ≈ 79%를 차지하고(무작위 점으로 π를 구하는 몬테카를로 방법⁠(Monte Carlo method)⁠의 그 비율), d = 3에서 52%, d = 10에서 0.25%입니다. d = 이면 입니다. 부피는 거의 모두 모서리 쪽에 있습니다. 또 부피는 표면 가까이에 몰립니다. 반지름 1인 공에서 두께가 $\varepsilon =$ 인 바깥 껍질이 차지하는 몫은, 안쪽 공의 부피가 $(1-\varepsilon)^d$ 배이므로 $1-(1-\varepsilon)^d$ 로, 지금 입니다.

그래서 공간을 촘촘히 덮으려면 필요한 점의 개수가 차원에 따라 기하급수로 늘어납니다. 축마다 10칸으로 나누면 $10^d$ 칸이 필요합니다. 미국의 응용수학자 리처드 벨먼이 동적 계획법⁠(dynamic programming)⁠을 다루며 이 어려움을 '차원의 저주'라고 불렀고, 흔히 1957년 책 《동적 계획법》이 처음으로 꼽힙니다. 고차원 적분⁠(integral)⁠에 격자 대신 몬테카를로 방법을 쓰는 까닭도 여기 있습니다. 무작위 점 n개의 오차는 차원과 상관없이 $1/\sqrt n$ 에 비례해 줄어듭니다.

이어지는 곳. 반지름 1인 d차원 공의 부피 공식 $\pi^{d/2}/\Gamma(d/2+1)$ (Γ는 계승⁠(factorial)⁠을 정수⁠(integer)⁠가 아닌 수로 넓힌 감마 함수⁠(gamma function)⁠로, $\Gamma(n+1) = n!$ )은 가우스 적분⁠(Gaussian integral)⁠을 d번 곱하는 요령으로 얻고, 그것이 얼마나 빨리 0으로 가는지는 스털링 공식⁠(Stirling's formula)⁠이 알려 줍니다. d차원 표준 정규분포⁠(normal distribution)⁠에서 뽑은 점들은 밀도가 가장 높은 중심 근처가 아니라 반지름 $\sqrt d$ 근처의 껍질에 몰립니다. 반지름의 표준편차⁠(standard deviation)⁠는 d가 커져도 약 0.7에 머물러서, 껍질은 반지름에 비하면 점점 얇아집니다. 다행히 실제 데이터는 고차원 공간 속 낮은 차원의 곡면 근처에 놓인 경우가 많아서, 주성분 분석⁠(principal component analysis)⁠이나 그것을 비선형으로 넓힌 오토인코더⁠(autoencoder)⁠ 같은 차원 축소가 저주를 누그러뜨립니다. 마할라노비스 거리⁠(Mahalanobis distance)⁠처럼 공분산⁠(covariance)⁠을 추정해야 하는 방법은 차원이 높을수록 자료가 훨씬 많이 필요합니다. 자료에 비해 변수가 많으면 모형이 우연한 무늬까지 맞추기 쉬워 과적합⁠(overfitting)⁠의 위험도 커집니다.

관련 인물리처드 벨먼 요슈아 벤지오

이 개념이 나오는 큰 생각근사와 오차

이 개념이 나오는 긴 글

거리와 유사도 까마귀와 택시 까마귀는 곧장 날고 택시는 블록을 돌아간다. '얼마나 먼가'에는 답이 하나가 아니고, 어떤 거리를 고르느냐가 통계와 기계 학습의 답을 바꾼다. 계산언어학 말을 세는 기계 문법은 규칙일까, 확률일까? 파니니의 문법에서 촘스키의 위계, 섀넌의 영어 엔트로피, 오늘날의 언어 모델까지. 통신과 잡음 잡음 너머로 대서양 바닥의 케이블은 왜 신호를 뭉갰을까? 잡음이 있어도 오류 없이 보낼 수 있다는 섀넌의 정리와, 그 한계를 50년 동안 쫓은 부호들. 신경망과 기계 학습 배우는 기계 예를 보여 주면 규칙을 스스로 찾는 기계. 1958년의 퍼셉트론에서 오늘의 심층 신경망까지, 그 밑바닥에는 미분과 연쇄법칙이 있다. 언어 모델 다음 단어를 맞히는 기계 다음 낱말을 짐작하는 일만으로 어디까지 갈 수 있을까? 마르코프의 글자 세기에서 섀넌의 추측 게임, 트랜스포머와 규모의 법칙, 사람의 선호까지. 밑바닥에는 확률의 곱셈 규칙과 로그 하나가 있고, 그 수학은 모델이 왜 그럴듯하게 틀리는지도 말해 준다. 반환과 동적 계획법 같은 계산, 다른 덧셈 가장 짧은 길, 길의 가짓수, 가장 그럴듯한 해석, 갈 수 있는지 없는지. 따로 태어난 알고리즘들이 사실은 한 계산이고, 달라지는 것은 더하기와 곱하기 자리에 무엇을 넣느냐뿐이다. 그렇게 바꿔 넣어도 되는 까닭은 분배법칙 하나다.

이 개념을 언급하는 페이지

리만 합
… 막대를 격자처럼 세우는 대신 무작위로 점을 뿌려 넓이를 재는 방법이 몬테카를로 방법이고, 변수가 많은고차원에서는 이쪽이 낫습니다. 격자는 한 축을 10조각 내면 d차원에서 10^d 칸이 필요하지만, 무작위 점 …
큰 수의 법칙
… 어느 두 점을 골라도 거리가 거의 같아 보입니다. '가까운 점'과 '먼 점'의 구별이 흐려지는 이 현상이차원의 저주입니다. 언어 모델에게 같은 문제를 여러 번 풀게 해 가장 많이 나온 답을 고를 때도 이 법칙이 결론을 …
몬테카를로 방법
… 개가 필요합니다. 무작위 점의 오차가 1/\sqrt N 에 비례해 줄어드는 빠르기는 차원과 무관해서,고차원적분에서는 몬테카를로가 이깁니다. 바늘을 던져 π를 구하는 뷔퐁의 바늘도 같은 발상입니다. 계산에 …
마할라노비스 거리
… d(d−1)/2개, 모두 d(d+1)/2개의 수를 자료에서 추정해야 해서, 차원이 높고 자료가 적으면차원의 저주에 걸립니다.
코사인 유사도
… 뽑은 두 벡터는 거의 언제나 직각에 가까워서(코사인 ≈ 0, 차이는 대략 1/\sqrt d 크기), 이것이차원의 저주의 또 다른 얼굴입니다. 함수도 적분으로 내적을 정하면 사이각을 잴 수 있는데, 푸리에 급수의 …
최근접 이웃 분류
… 이어지는 곳. 차원이 높아지면 거의 모든 점이 비슷하게 멀어져 '가장 가까운 이웃'이 뜻을 잃습니다(차원의 저주). 이름이 비슷한 k-평균 군집은 이름표 없이 무리를 찾는 전혀 다른 방법입니다. 지금까지 찾은 가장 …
거리 함수
… 아주 높아질수록 모든 점 사이의 거리가 평균 거리 둘레로 몰려 '가장 가깝다'가 힘을 잃습니다. 이것이차원의 저주입니다.
유클리드 거리
… 가장 가까운 점과 가장 먼 점의 거리 차이가 거리 자체에 비해 작아져 유클리드 거리마저 구별력을 잃습니다(차원의 저주). 모든 벡터를 길이 1로 맞추면 \lVert q - d\rVert^2 = 2 - 2\cos(q, d) …
Lp 노름
… 공이 정육면체 부피에서 차지하는 몫이 0으로 줄어듭니다. 부피 대부분이 모서리 쪽에 몰린다는 뜻이고,차원의 저주의 한 얼굴입니다. L2의 공(원)을 방향마다 다르게 늘이고 돌려 타원으로 만든 것이 ⟦마할라노비스 …
n-그램 언어 모델
… 개로, V진법 n자리 수만큼 늘어나지만(자릿값 기수법), 말뭉치는 그 가운데 극히 일부만 담습니다.차원의 저주와 닮은 현상이고, 지프의 법칙의 긴 꼬리 때문에 말뭉치를 늘려도 쉽게 사라지지 않습니다. 한 번도 못 …
단어 임베딩
… 그림 속 거리와 실제 코사인 순위가 어긋날 수 있습니다. 차원이 높을수록 이런 어긋남은 피할 수 없고(차원의 저주), 실제 임베딩을 볼 때도 주성분 분석 같은 방법으로 차원을 줄여 그림을 그립니다. 유추가 되는 …
과적합
… 됩니다. 특성의 수가 자료의 수에 가까워지면 우연히 맞아떨어지는 규칙을 찾기 쉬워지는데, 이것도차원의 저주의 한 얼굴입니다. 이어지는 곳. '같은 것을 설명한다면 더 단순한 설명을 고르라'는 원칙을 14세기 …
오류 정정 부호
… 읽는 것은 부호어들로 나눈 보로노이 영역 가운데 어디에 떨어졌는지 보는 것이고, 좋은 부호를 찾는 일은고차원공간에 공을 빽빽이 채우는 문제와 닮았습니다. 오류를 t개까지 고치려면 부호어마다 해밍 거리 t 이내의 …
통로 부호화 정리
… 정리⟧가 되고, 부호어의 잡음 구름을 고차원 공간에 겹치지 않게 채우는 그림은 보로노이 영역과차원의 저주로 이어집니다. 약간의 왜곡을 허용할 때의 한계는 율–왜곡 이론이 다룹니다. 잡음 구름의 크기 …
섀넌–하틀리 정리
… = BT\log_2(1+S/N) 비트입니다. 고차원에서는 공의 부피가 거의 모두 껍질에 몰린다는차원의 저주가 여기서는 축복이 됩니다. 이진 통로의 잡음 구름 세기(통로 부호화 정리)를 유클리드 거리의 세계로 …
기계 학습
… 하강법⟧과 역전파, 일반화의 함정은 과적합, 편향–분산 분해, 정규화, 교차 검증,차원의 저주에서 다룹니다. 거리로 배우는 방법은 최근접 이웃 분류, k-평균 군집, 코사인 유사도, …
서포트 벡터 머신과 커널
… 마진입니다). 퍼셉트론이 고치는 횟수의 상한 (R/\gamma)^2 과 같은 양입니다. 마진이 넓으면차원의 저주를 어느 정도 피할 수 있다는 뜻입니다. 최적의 경계 초평면은 1960년대 바프니크와 체르보넨키스가 …
인공지능
… 볼록 최적화, 조건을 지키며 최적을 찾는 라그랑주 승수법, 차원이 높아지면 자료가 듬성듬성해지는차원의 저주. 신경망의 기초. 가장 단순한 학습 기계 퍼셉트론에서 여러 층의 신경망으로, 그것을 학습시키는 …
오토인코더와 잠재 공간
… 분해⟧에 있습니다. 복원이 정사영이라는 사실은 정사영과 내적에서, 고차원 자료를 왜 줄여야 하는지는차원의 저주에서 이어집니다. VAE의 벌점은 쿨백–라이블러 발산, 그 벌점이 끌어당기는 모양은 정규분포이고, …
검색 증강 생성
… 거리들이 서로 비슷해져서 공간을 반씩 나누는 k-d 트리 같은 정확한 색인이 거의 전수 조사가 되는데(차원의 저주), 근사 방법이 필요한 까닭입니다. 2017년 공개된 FAISS 같은 라이브러리가 이런 방법들을 담고 …

이 페이지가 가리키는 개념

최근접 이웃 분류 k-평균 군집 유클리드 거리 기댓값 중심극한정리 코사인 유사도 몬테카를로 방법 리처드 벨먼 동적 계획법 가우스 적분 스털링 공식 정규분포 주성분 분석 오토인코더와 잠재 공간 마할라노비스 거리 과적합