Dimension Reduction, Curse Of High Dimensionality

고차원의 저주 (Curse Of High Dimensionality) : 고차원에서는 다음과 같은 현상이 일어나 기계학습에서 여러 문제가 발생한다.

1) 차원이 무한으로 갈 수록 임의의 두 점간의 거리가 무한대로 발산한다. 그러므로 당연히 임의의 두점에 대한 거리의 비가 1로 수렴한다.(즉 임의의 점 4개를 뽑고, 2점들 간의 거리의 비가 1로 수렴한다)
2) 데이터의 instance가 고차원의 공간에서는 보다 희소(Sparse)해진다. 따라서 특정한 차원(Feature)를 충분히 설명할 수 없어지고, 부족한 데이터는 곧 모델의 Generalization Ability를 약화시켜 Overfitting이 일어난다.

차원 축소 (Dimension Reduction) :

차원 축소는 고차원의 저주를 비롯해 여러가지 고차원에서 일어나는 문제를 해결할 수 있는 도구이다.
차원이 너무 많으면 오버피팅이 쉽게 일어나고, 학습에 필요한 데이터가 굉장히 많아지게된다. 학습 시간이 길어지는 것 또한 당연하다.

차원 축소는 크게 5가지 방법으로 나뉜다.

1) 전통적인 선형 방법(PCA 등)
각 데이터들을 분리해낼 수 있는 아이겐 벡터 즉, 어떤 각도로 데이터를 정사영시켜 바라볼 때 가장 잘 분리되는 가를 찾는 방법이다.

2) 전역 비선형 방법
각 데이터들간의 거리를 최대한 유지(Global Properties를 보존)하면서 저차원으로 매핑시키고자하는 방법이다.

3) 지역 비선형 방법
전체적인 데이터들의 속성을 유지하는게 아니라, 오직 지역적인 데이터들간의 거리만을 유지하려는 방법이다. 이 방법의 아이디어에는 지역적인 속성을 유지하면 결국 전역적인 속성도 유지될 것이라는 가정이 깔려있다.

4) 지역 비선형 방법의 확장 및 변형
지역 비선형방법에서 Approximation이나 각도를 유지하는 방법 등을 추가 사용한 것.

5) 선형모델의 전역 정렬 방법
2번과 3번을 동시에 수행하는 모델이라고한다. 지역 선형 모델들을 전역적으로 정렬해서 두가지 속성을 모두 유지하는 방법.

t-SNE : stochastic(실행할 때 마다 결과가 다름) 한 차원 축소 알고리즘. Objective Function 이 Convex가 아니기 때문에 학습에는 적절하지 않고, 2차원 또는 3차원으로 표현된 데이터를 시각적으로 확인할 때에 매우 유용하다.

그이외에도 2006년 힌튼의 딥러닝 논문은 뉴럴넷을 이용한 차원축소, 매니폴드 탐색이 키워드였다.

고차원의 관측데이터가 샘플링되는 확률분포가 사실은 저차원에 공간에 그려지는 어떠한 구조에서 유래하는 데, 이때의 구조를 매니폴드라고한다.

또한 여기서의 저차원을 데이터의 인트린직 디맨젼이라 부른다.

그래서 차원축소는 곧 매니폴드를 찾으려는 시도이며, 매니폴드를 완벽히게 찾았다는 것은 데이터의 언더라잉 프로버빌리티 댄시티를 알아냈다는 것으로, 그 데이터에 대한 리제너레이션과 클래시피케이션 등을 베이즈 에러로 할수있음을 의미한다.

dim_reduction_toolbox_Introduction.pdf

http://blog.naver.com/nlboman/21817010

http://en.wikipedia.org/wiki/Locally_linear_embedding#Locally-linear_embedding