차원의 저주
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
차원의 저주는 고차원 공간에서 데이터 분석 및 모델링이 어려워지는 현상으로, 수치 해석에서 계산 시간 증가 및 수치 오차 발생 형태로 나타난다. 조합 폭발, 데이터 희소성, 거리 측정의 부정확성 등이 주요 원인이며, 기계 학습, 데이터 마이닝, 패턴 인식, 정보 검색 등 다양한 분야에서 문제로 작용한다. 차원 축소, 특징 선택, 규제 등의 해결 방안이 있으며, 경우에 따라 차원의 축복으로 인해 성능이 향상될 수도 있다. 한국 사회에서는 정부의 정책 지원과 기업의 데이터 분석 활용을 통해 영향을 미치고 있다.
더 읽어볼만한 페이지
- 동적 계획법 - 배낭 문제
배낭 문제는 주어진 배낭 용량 내에서 물건들의 가치 합을 최대화하는 조합 최적화 문제로, 물건을 쪼갤 수 있는지, 개수 제한이 있는지에 따라 다양한 변형이 있으며, 동적 계획법, 탐욕 알고리즘 등으로 해결하고, NP-완전 문제에 속하며 자원 할당 문제 등에 응용된다. - 동적 계획법 - 비터비 알고리즘
비터비 알고리즘은 잡음이 있는 통신 링크 상에서 길쌈 부호 해독에 사용되며, 확률과 관련된 극대화 문제에 동적 계획법을 적용하는 표준 용어로, 상태 기계를 기반으로 은닉 마르코프 모델에서 가장 가능성 높은 상태 시퀀스를 찾는 데 활용되어 통신, 자연어 처리, 생물정보학 등 다양한 분야에 적용되고 개선 방법이 연구되고 있다. - 차원 - 크룰 차원
크룰 차원은 환 내의 소수 아이디얼 체인의 길이를 이용하여 정의되며, 환론 및 대수기하학에서 중요한 역할을 하고 다양한 개념으로 확장되어 사용된다. - 차원 - 데카르트 좌표계
데카르트 좌표계는 르네 데카르트가 고안한 좌표계로, 다양한 차원의 공간에서 점의 위치를 나타내며, 2차원에서는 x축과 y축, 3차원에서는 직교하는 세 평면으로 확장되고, 고차원에서는 실수 튜플을 사용한다. - 수치해석학 - 수학적 최적화
수학적 최적화는 주어진 집합에서 실수 또는 정수 변수를 갖는 함수의 최댓값이나 최솟값을 찾는 문제로, 변수 종류, 제약 조건, 목적 함수 개수에 따라 다양한 분야로 나뉘며 여러 학문 분야에서 활용된다. - 수치해석학 - 선형대수학
선형대수학은 벡터, 벡터 공간, 행렬 등의 개념으로 선형 방정식과 선형 변환을 연구하는 수학 분야로, 선형성을 활용해 행렬로 표현 및 계산하며, 연립일차방정식 해법, 고유값/고유벡터를 통한 행렬 분석, 벡터 공간의 기저와 차원 등을 다루고 물리학, 공학, 컴퓨터 과학 등 다양한 분야에 응용된다.
| 차원의 저주 | |
|---|---|
| 차원의 저주 | |
| 유형 | 문제 |
| 분야 | 머신러닝 데이터 마이닝 데이터베이스 |
| 설명 | 고차원 공간에서 데이터 분석 및 모델링 시 발생하는 문제점 |
| 관련 개념 | 샘플 크기 희소성 모델 복잡도 과적합 |
| 해결 방법 | 차원 축소 (주성분 분석, 선형 판별 분석, 자동 인코더) 특성 선택 규제화 비모수적 방법 앙상블 방법 |
| 원인 | |
| 데이터 희소성 | 고차원 공간에서는 데이터 포인트들이 희소하게 분포하게 되어, 모델 학습에 필요한 충분한 정보를 얻기 어려움. |
| 계산 복잡도 증가 | 차원이 증가함에 따라 계산량이 기하급수적으로 증가하여, 모델 학습 및 예측에 많은 시간과 자원이 소모됨. |
| 과적합 위험 증가 | 고차원 공간에서는 모델이 훈련 데이터에 지나치게 적합되어, 새로운 데이터에 대한 예측 성능이 저하될 가능성이 높음. |
| 영향 | |
| 모델 성능 저하 | 분류, 회귀 등 다양한 머신러닝 모델의 성능이 저하될 수 있음. |
| 해석력 감소 | 모델이 복잡해짐에 따라 모델의 예측 결과를 해석하기 어려워짐. |
| 자원 낭비 | 불필요한 계산량 증가로 인해 시간, 메모리, 저장 공간 등 자원 낭비가 발생할 수 있음. |
| 해결 전략 | |
| 차원 축소 (Dimensionality Reduction) | 고차원 데이터를 저차원 공간으로 변환하여 데이터의 중요한 특징을 유지하면서도 차원을 줄이는 방법. |
| 특성 선택 (Feature Selection) | 모델 학습에 유용한 특성만 선택하고 나머지 특성을 제거하는 방법. |
| 규제화 (Regularization) | 모델의 복잡도를 제한하여 과적합을 방지하는 방법. |
| 비모수적 방법 (Non-parametric Methods) | 데이터 분포에 대한 가정을 최소화하여 차원의 영향을 줄이는 방법. |
| 앙상블 방법 (Ensemble Methods) | 여러 모델을 결합하여 예측 성능을 향상시키는 방법. |
| 역사 | |
| 최초 언급 | 리처드 벨먼 (1957년) |
2. 정의
수치 해석에서 차원의 저주는 계산 시간과 수치 오차가 증가하는 현상으로, 다음과 같은 예가 있다.
하지만, "선형" 연립 방정식의 근사해를 구하는 계산은 계수 행렬의 차수 ''N''의 세제곱에 비례하는 정도 이하이며, "단변수" 수치 계수 고차 방정식의 모든 근을 근사하여 구하는 계산 역시 방정식의 차수 ''D''의 세제곱에 비례하는 정도 이하이므로, "차원의 저주"에 해당하지 않는다. 일반적으로 "차원의 저주"는 문제의 공간 차원이나 변수의 수가 증가함에 따라 계산에 필요한 자원(주로 연산량)이 저차 다항식적으로 증가하지 않고 지수 함수적으로 증가하여 계산이 어려워지는 문제를 의미한다.
차원의 저주는 상태 변수의 차원이 큰 동적 최적화 문제를 수치적 후진 귀납법으로 풀 때 심각한 문제가 된다. 또한 기계 학습 문제에서도 고차원 특징 공간과 고차원 공간에서의 최근접 이웃 탐색에서 유한 개의 표본으로부터 상태를 학습할 때 차원의 저주로 인해 문제가 복잡해진다.
3. 발생 원인
차원의 저주는 여러 가지 원인으로 발생한다. 우선, 변수의 수가 증가함에 따라 고려해야 할 값의 조합이 기하급수적으로 늘어나는 조합 폭발 문제가 있다. 예를 들어, 각 변수가 두 가지 값을 가질 수 있는 경우, 변수가 개라면 가능한 조합의 수는 개가 된다.[30]
또한, 차원이 증가할수록 데이터가 차지하는 공간의 부피가 기하급수적으로 커지는 현상이 발생한다. 예를 들어, 1차원 단위 구간을 0.01 간격으로 표본 추출하려면 100개의 점이 필요하지만, 10차원 단위 초정육면체를 같은 간격으로 표본 추출하려면 1020개의 점이 필요하다. 이는 고차원 공간에서 데이터가 매우 희소하게 분포하게 됨을 의미한다.[31][32]
수치 해석에서 차원의 저주는 계산 시간과 수치 오차를 증대시킨다. 예를 들어, 다음과 같은 경우가 있다.
마지막으로, 고차원 공간에서는 유클리드 거리와 같은 거리 척도가 점들 사이의 상대적인 거리를 제대로 반영하지 못하는 문제가 발생한다. 고차원 공간에서는 대부분의 점들이 서로 비슷한 거리에 위치하게 되어, 거리 기반의 분석 방법이 효과를 잃게 된다.
3. 1. 조합 폭발
어떤 문제에서는 각 변수가 여러 개의 이산적인 값을 가질 수 있거나, 가능한 값의 범위가 유한한 수의 가능성을 갖도록 나뉜다. 변수를 함께 고려하면, 엄청난 수의 값 조합을 고려해야 한다. 이러한 현상은 조합 폭발이라고도 한다. 가장 간단한 경우인 개의 이진 변수에서도 가능한 조합의 수는 으로, 차원에 대해 지수적으로 증가한다. 각 추가 차원은 모든 조합을 시도하는 데 필요한 노력을 두 배로 늘린다.3. 2. 희소성 문제
어떤 문제에서는 각 변수가 여러 개의 이산적인 값을 가질 수 있거나, 가능한 값의 범위가 유한한 수의 가능성을 갖도록 나뉜다. 변수를 함께 고려하면, 엄청난 수의 값 조합을 고려해야 한다. 이러한 현상은 조합 폭발이라고도 한다. 가장 간단한 경우인 개의 이진 변수에서도 가능한 조합의 수는 이며, 차원에 대해 지수적으로 증가한다. 단순하게, 각 추가 차원은 모든 조합을 시도하는 데 필요한 노력을 두 배로 늘린다.수학적 공간에 추가 차원을 더하면 부피가 기하급수적으로 증가한다. 예를 들어, 102 = 100개의 균등하게 배치된 표본점만으로도 단위 구간( "1차원" 정육면체를 시각화해보라)을 점 사이의 거리가 10−2 = 0.01을 넘지 않도록 표본 추출할 수 있다. 인접한 점 사이의 간격이 10−2 = 0.01인 격자를 가진 10차원 단위 초정육면체의 동등한 표본 추출에는 1020 = [(102)10]개의 표본점이 필요하다. 일반적으로 간격 거리가 10−''n''이면, 10차원 초정육면체는 단위 구간인 1차원 초정육면체보다 10''n''(10−1) = [(10''n'')10/(10''n'')] "더 크게" 보인다. 위의 예에서 ''n'' = 2이다. 즉, 0.01의 표본 추출 거리를 사용할 때 10차원 초정육면체는 단위 구간보다 1018 "더 크게" 보인다. 이러한 효과는 위에 설명된 조합론적 문제와 아래 설명된 거리 함수 문제의 결합이다.
3. 3. 거리 측정의 부정확성
고차원 공간에서 유클리드 거리와 같은 거리 척도를 사용하여 점들 사이의 거리를 정의할 때, 서로 다른 점 쌍 사이의 거리 차이가 거의 없게 되는 현상이 발생한다.고차원 유클리드 공간의 "광대함"은 내접 초구와 초입방체의 부피 비율을 비교하여 설명할 수 있다. 반지름이 이고 차원이 인 초구의 부피는 (여기서 는 감마 함수)이고, 모서리 길이가 인 초입방체의 부피는 이다. 차원 가 증가함에 따라 초구의 부피는 초입방체에 비해 무시할 수 있을 정도로 작아진다. 이는 차원이 무한대로 갈 때 두 부피의 비율이 0으로 수렴하는 것을 통해 알 수 있다.[13]
: as .
또한, 중심과 모서리 사이의 거리는 로, 고정된 에 대해 차원이 증가함에 따라 무한대로 커진다.
이러한 현상은 카이제곱 분포를 통해서도 설명할 수 있다. 실제로, 구간 [-1, 1]에서 무작위 점과 관련된 (비중심) 카이제곱 분포는 ''d''-입방체에서 무작위 점의 길이 제곱 분포와 같다. 대수의 법칙에 따라, 이 분포는 원래 유도의 표준 편차 제곱(σ2)의 ''d''배 주변의 좁은 범위에 집중된다. 이는 카이제곱 분포를 통해 ''d''-입방체의 대부분의 부피가 반경 인 구의 경계 근처에 집중된다는 것을 보여준다.
실수에 대한 고정된 임의 분포는 의 점에 대한 곱 분포를 유도한다. 고정된 ''n''에 대해, 임의의 기준점 ''Q''와 ''n''개의 임의의 데이터 점 ''P''1,...,''P''''n'' 목록 사이의 최소 및 최대 거리의 차이는 최소 거리에 비해 구별할 수 없게 된다.[14]
:.
이는 고차원에서 거리 함수가 유용성을 잃는다는 것을 의미한다. 그러나 최근 연구에 따르면 이는 일차원 분포 이 독립적이고 동일하게 분포된 확률 변수일 때만 성립하며, 속성이 상관 관계가 있는 경우 데이터가 더 높은 거리 대비를 제공하고 신호 대 잡음비가 중요한 역할을 하여 특징 선택을 사용해야 한다고 알려져 있다.[23]
최근에는 대비 손실이 고차원에서 문제를 발생시킨다는 주장에 개념적 결함이 있을 수 있다는 제안이 있다. 만약 여러 생성 과정을 고려하면 대비 손실이 오히려 긍정적인 역할을 할 수 있으며, 고차원 거리를 의미 있게 만들 수 있다는 연구 결과도 제시되었다.[15]
4. 문제점
차원의 저주는 데이터 분석 및 모델링에 여러 가지 문제를 야기한다.
기계 학습에서 '차원의 저주'는 '피킹 현상' 또는 '휴즈 현상'이라고도 불리며,[5][6] 고정된 수의 훈련 샘플에서 차원(특징) 수가 증가하면 예측력이 처음에는 증가하지만, 특정 차원을 넘어서면 오히려 감소하는 현상을 의미한다.[7][8][9] 또한, 차원이 증가할수록 정확한 일반화를 위해 필요한 데이터 양이 기하급수적으로 늘어난다.[4]
데이터 마이닝에서 차원의 저주는 특징이 너무 많은 데이터 세트를 의미하며, 가능한 매개변수 값의 공간이 기하급수적으로 증가하여 계산 시간과 공간에 큰 영향을 미친다. 특징 수가 증가하면 잘못된 예측이나 분류가 늘어나 오류 양성 및 오류 음성이 발생할 수 있다.
수치 해석에서 차원의 저주는 계산 시간과 수치 오차를 증가시킨다. 예를 들어 다차원 연립 방정식을 풀거나,[30] 고차 대수 방정식의 근을 찾거나,[30] 다차원 수치 적분을 수행하는 경우[31][32]가 있다.
고차원 공간에서 유클리드 거리와 같은 척도를 사용하면 점들 사이의 거리에 차이가 거의 없게 되어 거리 기반 알고리즘의 성능을 저하시킨다. 고차원 데이터에서 이상치를 검색할 때 점수 및 거리 집중, 관련 없는 속성, 기준 집합 정의의 어려움, 비교 불가능한 점수, 점수 해석의 어려움, 지수적 검색 공간, 데이터 스누핑 편향, 허브니스(Hubness) 등의 문제가 발생한다.[23]
4. 1. 과적합
기계 학습에서 예측 성능과 관련하여 '차원의 저주'는 '피킹 현상'과 상호 교환적으로 사용되며,[5] 이는 '휴즈 현상'이라고도 알려져 있다.[6] 이 현상은 고정된 수의 훈련 샘플에서 분류기나 회귀자의 평균(예상) 예측력이 사용되는 차원 또는 특징의 수가 증가함에 따라 먼저 증가하지만, 특정 차원을 넘어서면 꾸준히 개선되는 대신 악화되기 시작한다는 것을 의미한다.[7][8][9]특징이나 차원의 수가 증가함에 따라 정확하게 일반화하기 위해 필요한 데이터의 양은 기하급수적으로 증가한다.[4] 일반적인 경험 법칙은 표현의 각 차원당 최소 5개의 훈련 예제가 있어야 한다는 것이다.[5]
4. 2. 계산 복잡성 증가
동적 최적화 문제를 수치적 후진 귀납법으로 풀 때, 목적 함수는 각 값의 조합에 대해 계산되어야 한다. 이는 "상태 변수"의 차원이 클 때 상당한 장애가 된다.[3] 데이터 마이닝에서 차원의 저주는 특징이 너무 많은 데이터 세트를 의미한다.다음은 개인 데이터 세트의 유전자 변이를 나타내는 표이다.
| 개인 이름 | 유전자 1 | 유전자 2 | ... | 유전자 2000 |
|---|---|---|---|---|
| 개인 1 | 1 | 0 | ... | 1 |
| ... | ... | ... | ... | ... |
| 개인 200 | 0 | 1 | ... | 1 |
200명의 개인과 2000개의 유전자(특징)를 나타내며, 여기서 1 또는 0은 해당 유전자에 유전자 변이가 있는지 여부를 나타낸다. 이 데이터 세트에 대한 데이터 마이닝 응용 프로그램은 특정 유전자 변이 간의 상관 관계를 찾아내고, 개인이 암에 걸렸는지 여부를 결정하기 위해 의사 결정 트리와 같은 분류 알고리즘을 만드는 것일 수 있다.
데이터 마이닝의 일반적인 관행은 암 발병으로 이어지는 유전자 변이 간의 연관 규칙을 만드는 것이다. 이를 위해서는 각 개인의 각 유전자 변이를 반복하고 원하는 임계값 이상으로 발생하는 다른 유전자 변이를 찾아 쌍을 만들어야 한다. 2개, 3개, 4개로 시작하여 쌍 집합이 비어있게 될 때까지 진행한다. 이 알고리즘의 복잡성으로 인해 각 개인 또는 행에 대한 모든 유전자 쌍의 순열을 계산해야 할 수 있다. n개의 항목과 r개의 그룹 크기를 갖는 순열을 계산하는 공식은 $$\frac{n!}{(n - r)!}$$이므로, 어떤 개인의 3개 쌍 순열의 수를 계산하면 각 개인에 대해 평가해야 할 7988004000개의 서로 다른 유전자 쌍이 생성된다. 쌍의 크기가 증가함에 따라 생성되는 쌍의 수는 팩토리얼의 순서로 증가한다.
다음 표는 쌍 크기가 커짐에 따라 연관 쌍 순열이 증가하는 것을 보여준다.
| 쌍 의 수 | 순열 계산 | 각 행에 대해 계산된 순열 의 수 |
|---|---|---|
| 2 | $2000!/(2000-2)!$ | 3998000 |
| 3 | $2000!/(2000-3)!$ | 7988004000 |
| 4 | $2000!/(2000-4)!$ | 15952043988000 |
| 5 | $2000!/(2000-5)!$ | 31840279800048000 |
데이터 세트의 특징 수가 증가함에 따라 가능한 매개변수 값의 공간이 기하급수적으로 또는 팩토리얼적으로 증가한다. 이 문제는 연관성을 찾거나 고려해야 할 최적의 특징을 검색할 때 계산 시간과 공간 모두에 심각한 영향을 미친다.
데이터 마이너가 너무 많은 특징을 다룰 때 직면할 수 있는 또 다른 문제는 데이터 세트의 특징 수가 증가함에 따라 잘못된 예측 또는 분류 수가 증가하는 경향이 있다는 것이다. 모든 데이터 포인트를 유지하면 모델에서 더 많은 오류 양성 및 오류 음성이 발생할 수 있다.
각 개인의 모든 유전자 변이를 나타내는 위의 유전자 변이 표를 보면, 각 유전자 변이는 암과 상관 관계가 있는지 여부에 관계없이 알고리즘의 의사 결정 프로세스를 안내하는 모델에서 일부 입력 또는 가중치를 갖게 된다. 이상치이거나 암과 실제로 상관 관계가 없을 때 유전자 변이의 전반적인 분포를 지배하는 변이가 있을 수 있다. 이러한 특징은 모델에 반하여 작동하여 최적의 결과를 얻는 것을 더 어렵게 만들 수 있다.
이 문제는 데이터 마이너가 해결해야 하며 보편적인 해결책은 없다. 데이터 마이너가 취해야 할 첫 번째 단계는 문제를 해결하는 데 어떻게 사용할 수 있는지 이해하기 위해 데이터를 탐색하는 것이다. 그런 다음 데이터 세트에서 샘플이나 특징을 제거해야 할 필요가 있다고 판단되면 특징 선택 또는 차원 축소 알고리즘을 생성하거나 사용할 수 있다.
수치 해석에서의 차원의 저주는 계산 시간, 수치 오차의 증대를 의미하며, 다음과 같은 예가 있다.
차원의 저주는 상태 변수의 차원이 큰 동적 최적화 문제를 수치적 후진 귀납법으로 풀 때 심각한 장애가 된다. 또한 기계 학습 문제에서도 고차원 특징 공간과 고차원 공간에서의 최근접 이웃 탐색에서, 유한 개의 표본으로부터 상태를 학습할 때 차원의 저주로 인해 문제가 복잡해진다.
4. 3. 모델 성능 저하
기계 학습에서 예측 성능과 관련하여 '차원의 저주'는 '피킹 현상' 또는 '휴즈 현상'이라고도 불린다.[5][6] 이 현상은 훈련 샘플 수가 고정되어 있을 때, 분류기나 회귀자에서 사용되는 차원(특징)의 수가 증가함에 따라 처음에는 평균 예측력이 증가하지만, 특정 차원을 넘어서면 오히려 예측력이 감소하는 현상을 의미한다.[7][8][9]평균 예측력의 감소 또는 증가는 추가되는 특징의 크기와 상대적인 누적 차별 효과에 따라 결정된다.[10]
5. 해결 방안
차원의 저주를 해결하기 위한 방법에는 여러 가지가 있다. 수치 해석에서는 계산 시간과 수치 오차를 줄이기 위해 노력한다. 예를 들어, 다차원 연립 방정식을 풀거나[30], 근 찾기 알고리즘을 사용하여 고차 대수 방정식을 풀거나[30], 다중 적분을 계산할 때[31][32] 차원의 저주가 발생할 수 있다.
하지만, "선형" 연립 방정식의 근사해를 구하는 계산은 계수 행렬의 차수에 대해 세제곱에 비례하는 정도 이하로 증가하고, "단변수" 수치 계수 고차 방정식의 모든 근을 구하는 계산도 방정식 차수에 대해 세제곱에 비례하는 정도 이하로 증가하므로, 엄밀히 말해 "차원의 저주"에 해당하지는 않는다. 일반적으로 "차원의 저주"는 문제의 공간 차원이나 변수의 수가 늘어날 때 계산에 필요한 자원이 지수 함수적으로 증가하여 계산이 어려워지는 문제를 의미한다.
차원의 저주는 상태 변수의 차원이 큰 동적 최적화 문제를 수치적 후진 귀납법으로 풀 때나 기계 학습에서 고차원 특징 공간과 고차원 공간에서의 최근접 이웃 탐색을 할 때, 그리고 유한한 표본으로 상태를 학습할 때 심각한 문제가 된다. 이러한 문제를 해결하기 위해 차원 축소, 특징 선택, 규제 등의 기법을 활용할 수 있다.
5. 1. 차원 축소 (Dimension Reduction)
수치 해석에서 차원의 저주는 계산 시간과 수치 오차를 증대시킨다. 예를 들어, 다차원 연립 방정식 풀이[30], 근 찾기 알고리즘을 사용한 고차 대수 방정식 풀이[30], 수치 다중 적분[31][32] 등이 있다.일반적으로 "차원의 저주"는 문제의 공간 차원이나 변수의 수에 대해 계산 자원(주로 연산량)이 저차 다항식적으로 증가하는 것이 아니라 지수 함수적으로 증가하여 계산이 어려운 문제를 의미한다. "선형" 연립 방정식의 근사해 계산은 계수 행렬 차수 ''N''의 세제곱에 비례하는 정도 이하이며, "단변수" 수치 계수 고차 방정식의 모든 근을 근사하여 구하는 계산 역시 방정식 차수 ''D''의 세제곱에 비례하는 정도 이하이므로, 이는 "차원의 저주"에 해당하지 않는다.
차원의 저주는 상태 변수의 차원이 큰 동적 최적화 문제를 수치적 후진 귀납법으로 풀 때, 그리고 기계 학습 문제에서 고차원 특징 공간과 고차원 공간에서의 최근접 이웃 탐색에서 유한 개의 표본으로 상태를 학습할 때 심각한 문제가 된다.
5. 2. 특징 선택 (Feature Selection)
모델에 중요하다고 판단되는 특징만 선택하여 차원을 줄이는 기법을 특징 선택이라고 한다. 데이터 마이너가 너무 많은 특징을 다룰 때, 데이터 세트의 특징 수가 증가함에 따라 가능한 매개변수 값의 공간이 기하급수적으로 또는 팩토리얼적으로 증가하여 계산 시간과 공간에 심각한 영향을 미치는 문제가 발생할 수 있다. 또한, 데이터 세트의 특징 수가 증가함에 따라 잘못된 예측 또는 분류 수가 증가하는 경향이 있다. 이는 각 특징이 모델에서 일부 입력 또는 가중치를 가지게 되는데, 이상치이거나 실제로는 상관 관계가 없는 특징이 모델에 반하여 작동하여 최적의 결과를 얻는 것을 더 어렵게 만들기 때문이다.이러한 문제를 해결하기 위해 특징 선택 알고리즘을 생성하거나 사용할 수 있다. 예를 들어, 특징 또는 발생의 표준 편차를 계산하여 데이터 세트의 이상치를 제거하는 데 사용되는 사분위 범위 방법이 있다.
5. 3. 규제 (Regularization)
기계 학습 문제에서 고차원 특징 공간과 고차원 공간에서의 최근접 이웃 탐색을 할 때, 유한 개의 표본으로부터 상태를 학습하면 차원의 저주로 인해 문제가 복잡해진다.[30]6. 활용 분야
차원의 저주는 다양한 분야에서 문제를 일으킨다.
- 수치 해석:
- 다차원 연립 방정식 풀이[30]
- 고차 대수 방정식의 근 찾기 알고리즘[30]
- 수치 다중 적분 (다차원 수치 적분)[31][32]
- 상태 변수의 차원이 큰 동적 최적화 문제를 수치적 후진 귀납법으로 풀 때
- 기계 학습: 고차원 특징 공간과 고차원 공간에서의 최근접 이웃 탐색에서 유한 개의 표본으로부터 상태를 학습할 때 문제가 복잡해진다.[30]
- 데이터 마이닝: 특징(feature)이 너무 많은 데이터 세트를 다룰 때 발생한다. 예를 들어, 유전자 데이터에서 특정 유전자 변이 간의 상관관계를 찾거나, 의사 결정 트리와 같은 분류 알고리즘을 통해 질병 예측을 할 때 계산량이 기하급수적으로 증가하고, 오류 예측 및 분류 또한 증가하는 경향이 있다.
- 정보 검색: 고차원 문서 벡터 공간에서 검색을 효율적으로 수행하기 어렵게 만든다.
이러한 문제를 해결하기 위해 데이터 마이닝에서는 데이터를 탐색하고 필요에 따라 특징 선택 또는 차원 축소 알고리즘을 사용하며, 정보 검색에서는 차원 축소 및 인덱싱 기법이 사용된다.
6. 1. 기계 학습 (Machine Learning)
기계 학습 문제에서 각 특징은 다양한 값을 가질 수 있는 고차원 특징 공간을 가진다. 유한한 수의 데이터 샘플로부터 "자연 상태"를 학습하는 경우, 각 값의 조합에 대해 여러 샘플이 존재하도록 하기 위해 일반적으로 엄청난 양의 훈련 데이터가 필요하다. 추상적인 의미에서 특징이나 차원의 수가 증가함에 따라 정확하게 일반화하기 위해 필요한 데이터의 양은 기하급수적으로 증가한다.[4]일반적인 경험 법칙은 표현의 각 차원당 최소 5개의 훈련 예제가 있어야 한다는 것이다.[5] 기계 학습에서 예측 성능과 관련하여 ''차원의 저주''는 ''피킹 현상''과 상호 교환적으로 사용되며,[5] 이는 ''휴즈 현상''이라고도 알려져 있다.[6] 이 현상은 고정된 수의 훈련 샘플에서 분류기 또는 회귀자의 평균(예상) 예측력이 사용되는 차원 또는 특징의 수가 증가함에 따라 먼저 증가하지만, 특정 차원을 넘어서면 꾸준히 개선되는 대신 악화되기 시작한다고 말한다.[7][8][9]
그럼에도 불구하고, ''단순한'' 분류기(예: 공통의 알려진 공분산 행렬을 가정하는 다변량 가우시안 모델에서 선형 판별 분석)의 맥락에서, 추가 특징 집합의 상대적 누적 효능이 (이미 분류기의 일부인 특징과 관련하여) 이 추가 특징 집합의 크기보다 크거나 작은 경우, 이러한 추가 특징을 사용하여 구성된 분류기의 예상 오류가 이를 사용하지 않고 구성된 분류기의 예상 오류보다 작거나 크다는 것을 분석적, 경험적으로 보여주었다. 즉, 평균 예측력의 감소 또는 증가는 추가 특징의 크기와 (상대적) 누적 차별 효과 모두에서 중요하다.[10]
메트릭 학습에서, 더 높은 차원은 때때로 모델이 더 나은 성능을 달성하도록 할 수 있다. 임베딩을 초구 표면으로 정규화한 후, FaceNet은 한 소거 연구에서 64, 256 또는 512 차원 대신 128 차원을 사용하여 최고의 성능을 달성한다.[11] 단어 임베딩 간의 단일 불변성 차이에 대한 손실 함수는 고차원에서 최소화되는 것으로 나타났다.[12]
차원의 저주는 고차원 공간에서 최근접 이웃 탐색을 복잡하게 만든다. 모든 차원을 기반으로 하는 거리의 하한으로 한 좌표의 차이를 사용하여 후보를 빠르게 기각하는 것이 불가능하다.[16][17]
그러나, 최근에 단순히 차원의 수가 반드시 어려움을 초래하지 않는다는 점이 관찰되었다.[18] 왜냐하면, ''관련 있는'' 추가 차원도 대비를 증가시킬 수 있기 때문이다. 또한, 결과 순위에서 가깝고 먼 이웃을 구별하는 것이 여전히 유용하다. 그러나 관련 없는("노이즈") 차원은 위에서 설명한 방식대로 대비를 감소시킨다. 데이터가 본질적으로 고차원인 시계열 분석에서는, 신호 대 잡음비가 충분히 높다면 거리 함수도 안정적으로 작동한다.[19]
6. 2. 데이터 마이닝 (Data Mining)
의 수계산
의 수