Curse of Dimensionality

Curse of dimensionality

최근의 Graph Theory paradingm 에서는  node 와 edge들을 low dimensional vector space에 encode하여

vector로 표현하는 방법이 지배적이고 많이 쓰이고 있다.

 

특히 large-scale Graph를 input 으로 받는 경우 vector들은 high dimensional space에 embed 되고 

이는 curse of dimensionality 문제를 직면하게 된다.

 

Curse of dimensionality는 Bellman에 의해 처음 정의 되었고,
high dimensional space에서 일어나는 vector 간의 proximity 측정의 오류 현상을 의미한다.

 

예를 들어 고차원의 벡터 공간에 embed된 node n_1, n_2, n_9가 있다고 가정하자.

실제 dataset에서는 n_1, n_2가 가까이 이웃해있고 n_9는 아주 멀리 떨어져있는 노드라고 가정했을때

high dimensional space에서는 노드 간의 거리를 측정했을때 

n_1과 n_2의 사이의 거리보다 n_9와의 거리가 가깝게 측정되는 경우가 허다하다.

 

또한  "distance concentration" 도 curse of dimensionality에서 자주 언급되는 문제인데,

고차원에서는 벡터들 사이의 거리의 차이가 희미해 진다는 이론이다.

 

Manifold

이러한 문제를 해결하기 위한 한가지 방법 중에 Manifold learning 이 있다.

Manifold Learning 는 고차원의 vector들을 저차원의 subspace 공간(manifold)에 mapping함으로써 데이터의 차원을 줄일 수 있다.

 

여기서 주목해야할 점은, 데이터들을 pattern을 잘 아우르는 주요 feature들을 잘 extract하는 것이다.

 

Embedding들의 주요 feature들을 잘 추출하여 나타내는 manifold에서는 

고차원에서는 discriminative하게 구별할 수 없거나 왜곡 되었던 embedding들 간의 거리를 

더 효율적이고 뚜렷하게 explicit하게 measure할 수 있다.

 

최적의 manifold를 찾는 것은 Unsupervised Learning 에서 매우 중요한 역할을 한다.

labeled data없이 대량의 데이터에서 스스로 데이터들의 feature를 찾아내야하는 unsupervised learning의 경우에는

데이터들의 dominant 한 feature들을 잘 나타내는 manifold를 automatic 하게 high dimensional space에서 찾는 것이 매우 중요하다.