[PRML] 1.4. The Curse of Dimensionality (차원의 저주)

1. 개요

 다차함수 커브 피팅 예제에서는 우리는 x가 1개의 입력변수로 이루어진 것을 예로 들었다. 하지만, 패턴인식의 실제 상황에서는 많은 입력 변수들로 이루어진 고차원 입력값을 다뤄야 한다. 이것은 몇몇 심각한 문제를 가지고 있으며 패턴인식 기법의 설계에서 영향을 끼치는 주요한 요소이다.

 

2. 내용

• 그림 1.19는 기름, 물, 그리고 가스로 이루어진 데이터에서 100개의 데이터 포인트를 뽑은 것이다. 이것들은 3가지의 지질학적인 상태로 이루어져 있다. 그 상태들은 homogenous, annular, 그리고 laminar이다. 그리고 3가지 상태에서 3가지 물질들의 구성비율 역시 다양하다. 각 데이터 포인트는 12개의 차원으로 이루어져 있다. 이중에서 x6와 x7만을 시각화 목적을 위해 사용한다.

그림 1.19

• 어떻게 학습알고리즘에게 빨간색과 파란색 그리고 초록색을 구분시키게 할 것인가? 먼저 가장 쉬운 방식은 그림 1.20과 같이 공간을 나눠주는 것이다. 새로운 테스트 포인트가 들어왔을 때 훈련 포인트들이 찍혔던 공간 중 어디에 찍히는지 확인하고 가장 많이 훈련데이터가 있는 클래스로 집어넣어주는 것이다. (동일한 값의 경우에는 랜덤하게 나눠줌).

그림 1.20

• 그러나, 위와 같은 순진한 방식의 경우는 문제가 많다. 특히, 입력변수가 많은 고차원 데이터의 경우 이 문제는 분명해진다. 그림 1.21에 묘사되듯이 우리가 일정한 규격으로 공간을 나눈다면 영역의 숫자는 지수적으로 증가하게 된다.  이렇게 되면 훈련데이터가 매우 많아야 샘플이 없는 영역이 없게 만들 수 있다. 분명히, 변수가 적은 경우가 아니고서는 이것을 적용할 수는 없다. 좀 더 세련된 접근방법이 필요하다.

그림 1.21

• 고차원 공간의 문제에 대한 더 깊은 통찰을 얻을 수 있는 방법 중 하나는 다항식 곡선 피팅의 예제로 돌아가서 입력 변수가 여러 개인 경우에 이 접근을 어떻게 확장할지를 고려하는 것입니다. 만일 우리가 D개의 입력 변수가 있고 3차까지의 계수를 갖는 일반적인 다항삼수를 고려한다면 수식 1.74와 같이 나타난다.

수식 1.74

• D가 증가하게 되면 독립적인 계수들의 숫자들 또한 D**3에 비례한만큼 증가하게 된다. M차항의 다항함수의 경우 파라미터의 숫자는 D**M으로 증가하게 된다.
• 3차원 그림으로는 표기하기 어려우므로 D차원 내에서 반지름이 r=1인 구체 (sphere)를 예로 들겠다. 그 후, r = 1-e와 r=1 사이의 구체의 부피의 비율을 고려해보겠다. 이것을 D차원 내에 있는 구체에 대한 부피는 수식 1.75와 같이 나타낼 수 있다. 여기서 K_D는 D에만 의존하는 상수이다. 따라서, 비율은 수식 1.76과 같이 나타낼 수 있다.

수식 1.75

수식 1.76

• 수식 1.76은 값이 큰 D에 대해 e가 작더라도 1로 수렴해가는 것을 그림 1.22를 통해 볼 수 있다.

그림 1.22. x축은 e값

• 패턴 인식과 직접적으로 관련된 더 나은 예로 가우시안 분포의 고차원 공간에서의 행동을 고려해 봅시다. 만약 우리가 직교 좌표에서 극좌표로 변환하고 (from Cartesian to polar coordinates), 그 후에 방향 변수들을 적분해 버리면, 우리는 원점으로부터의 반경 r에 대한 밀도 p(r)의 표현을 얻을 수 있습니다. 따라서 p(r)δr은 반경 r에 위치한 얇은 쉘의 두께가 δr인 내부의 확률 질량입니다. 이 분포는 D의 다양한 값에 대해 그림 1.23에 플로팅되어 있으며, 우리는 큰 D에 대해서 가우시안의 확률 질량이 얇은 쉘에 집중되어 있는 것을 볼 수 있습니다.

그림 1.23

• 차원의 저주는 패턴인식 응용에서 중요한 문제들을 낳지만, 이것이 고차원에 대해 적용할만한 효과적인 기법들을 개발하는 것을 막지는 못한다. 이러한 이유는 2가지인데, 첫째로는 실제 데이터는 저차원 공간에 국한된 공간에서 존재하는 경우가 많다. 이 때문에 중요한 분산은 좁은 영역에 대해서만 고려해도 될 수 있다. 둘 째로, 실제 데이터는 적어도 국소적이라도 몇 가지 부드러운 특징이 있다. 이 때문에 입력변수들의 조그마한 변화들은 목표변수의 작은 변화를 제공한다. 이러한 국소 보간법과 같은 기법 (local interpolation-like techinique)를 활용해서 새로운 입력변수에 대한 목표 변수를 예측할 수 있게된다. 
  보간법 : 쉽게 예를 들면 알고 있는 두 지점 사이의 중간값을 모르면 예측해서 채워주는 기법
• 성공적인 패턴인식 기법은 적어도 이 중 한가지를 사용하는 것이다. 예를들어, 컨베이어 벨트위의 동일한 평면 물체를 사진을 찍고 그것들의 방향이 무엇인지 결정하는 문제가 있다고 해보자. 각 이미지는 픽셀로 이루어진 고차원 공간에 있으며 그것의 차원성은 픽셀의 숫자로 결정된다. 물체는 제한된 이미지와 방향 내에서 다른 위치에서 나타날 수 있기 때문에 이미지들 간에는 3개 차원의 자유도가 나타나며 이미지 집합은 3차원의 공간 내 (three dimensional manifold)에 위치 (embedded)된다. 물체의 위치 혹은 방향과 픽셀의 강도 간에는 복잡한 관계로 이루어 져있다. 이 때문에, 이 다양체 (manifold)는 굉장히 비선형적이다. 만일, 우리의 모델이 입력이미지에 대해 물체가 어떤 방향을 향하는지 위치와 상관없이 예측하는 것이라면, 한 가지 자유도 (one degree of freedom of variability)만이 해당 다양체에서 중요할 것이다.