차원의 저주

 

오차 최소화 측면에서의 곡선 피팅

오차 최소화 측면에서의 곡선 피팅

확률적 측면에서의 곡선 피팅

확률적 측면에서의 곡선 피팅

앞서 소개한 다항식 곡선 피팅에서는 입력 변수가 오직 x 하나였다. 하지만, 패턴 인식의 실제 사례에서는 많은 종류의 입력 변수로 구성된 고차원 공간을 다뤄야만 한다. 고차원 공간의 입력 변수를 다뤄야 한다는 사실은 패턴 인식 문제를 푸는 데 있어서 심각히 고려되어야 할 중요한 사안이다.

 

차원의 저주1: 차원이 늘어남에 따른 계산량의 기하급수적 증가

오일 흐름 데이터 산포도. 빨간점은 '균질', 녹색점은 '환형', 파란점은 '층상'을 나타낸다.

위의 그래프를 통해 고차원 공간의 입력 변수를 다루는 문제를 살펴보자. 그림에서 x점을 추정하기 위해 어떤 알고리즘을 사용할 수 있을까? 가장 간단하게 전체를 균일한 영역으로 나누고 각각의 영역에서 가장 많은 수를 나타내는 label 값을 그 영역의 label로 결정하는 것이다.

직관적으로 생각할 수 있는 분류 방법

언뜻 보면 꽤나 타당한 분류 방법인 것 같으나 이 분류법의 문제는 입력 공간이 커짐에 따라 발생한다. 현재는 두 개의 입력공간 x6, x7을 바탕으로 산포도를 표현하였지만 사실 이 예시에는 x1, x2, x3 등 더 많은 입력공간이 존재한다. 위의 산포도에서는 단지 다른 입력공간을 모두 생략하고 x6, x7만 고려하여 나타낸 것이다. 여기서 만약 차원이 하나 더 추가된다면 어떻게 될까?

위의 그림을 보면 입력 공간이 하나씩 추가될 때 마다 나눠야 하는 영역의 개수를 보여준다. 입력 공간이 하나일 경우 총 3개의 영역으로 나누었다. 만약 입력 공간이 하나 추가되면 영역은 9개로 늘어난다. 즉, N차원에서는 3^N개의 영역으로 나누어야 한다는 것이다. 이는 입력 변수가 추가될 때마다, 생성해야 하는 영역의 수가 늘어나는 속도가 너무 빠르다. 조금민 고차원으로 올라도 기하급수적으로 증가하는 것이다. 그리고 영역이 늘어남에 따라 각 영역을 채우는 데이터 포인트의 수도 비례하여 늘어나야 한다. 따라서 이러한 접근법은 고차원에서 타당하지 않음을 알 수 있다.

 

여기 하나 더 예시가 있다. 다항식 곡선 피팅 문제를 하나의 변수가 아닌 D개의 변수가 있다고 가정 하자. 

3차 계수까지 고려한다 했을 때 위의 식과 같이 필요한 매개변수는 기하급수적으로 늘어난다. 앞의 예시와 마찬가지의 결과이다.

 

차원의 저주2: 변수에 대한 기하학적 직관이 차원에 따라 다름

 

우리가 3차원 세계에 살면서 얻게 된 기하학적 직관은 고차원에서 매우 다르게 작용할 수 있다. 간단한 예로 D차원의 반지름 r=1인 구체를 고려해 보자. 만약 반지름 r = 1−e에서 r=1 사이에 존재하는 부피의 비율을 계산한다면 어떻게 될까? D차원에서 반지름 r을 가지 ㄴ구체의 부피는 r^D에 비례하여 증가한다. 따라서 다음과 같이 적을 수 있다.

이를 통해 다음과 같은 그래프를 그릴 수 있다.

다음 그림을 보면 차원이 높아짐에 따라 구의 얇은 겉면(e)에 해당하는 부분이 전체 부피의 비율중 아주 높은 비율을 차지하게 된다. 

 

이렇게 고차원에서 발생할 수 있는 심각한 문제를 차원의 저주(curse of dimensionality)라고 부른다. 여기서 중요한 것은 저차원 공간에서 발전시킨 아이디어들이 고차원에서 반드시 적용되지는 않는다는 것이다. 

 

따라서 차원의 저주로 인해, 머신러닝 문제 해결에서는 원하는 문제를 풀기 위한 입력 변수의 개수를 최대한 줄이는 것이 중요한 문제가 된다.