UMAP은 어떻게 작동할까? (Uniform Manifold Approximation and Projection) - 2

https://data-newbie.tistory.com/169

UMAP은 어떻게 작동할까? (Uniform Manifold Approximation and Projection) - 1

 

이번에는 실제 어떻게 적용이 되는지에 대한 내용이 있어서 확인을 해보려고 합니다.

 

Adapting to Real World Data

앞에서는 설명된 접근 방식은 왜 근방 그래프 기반 접근 방식이 차원 축소를 수행할 때 매니 폴드 구조를 캡처해야 하는지에 대한 훌륭한 이론을 제공합니다.

하지만 실제로 접목시킬 때는 문제가 생긴다고 하는데요.

1. 일단 각 데이터 별로 open cover를 만드는 적절한 Radius를 선택하는 것이 어렵습니다.
   1. 너무 작은 것을 선택하면 결과로 나타나는 단순한 복합체가 여러 연결된 구성 요소로 나뉩니다.
   2. 너무 큰 것을 선택하면 단순한 복합체가 몇 개의 매우 높은 차원의 단순화 (및 그 얼굴 등)로 바뀌고 매니 폴드 구조를 더 이상 캡처하지 못합니다.

이러한 딜레마는 topology를 포착하는 정당성을 제공하는 Nerve theorem에 기인하게 됩니다.

이 정리에서는 simplicial complex는 덮개의 결합과 동등하게 (homotopically)있을 것이라고 말한다.

 

하지만 실제 유한한 데이터에서는 특정 반경을 본인들이 상상했던 manifold를 커버하지 못한다고 합니다.

마찬가지로, 포인트가 너무 많아지면 커버가 "너무 많이"다루어지고 우리는 이상적으로 생각했던 것보다 높은 차원의 단순화로 끝납니다.

데이터가 매니 폴드 전반에 걸쳐 균일하게 분포 된 경우(uniformly distributed) 적합한 반지름을 쉽게 선택할 수 있습니다.

포인트들간에 평균 거리는 잘 작동할 것입니다!

그래서  uniform distribution을 사용하게 되면, 전체 Cover 가 no gaps , no unnecessarily disconnected components

되면서 전체 Manifold를 포 관할 것을 보장받게 됩니다.

즉 먼가 끊김이 발생하지 않고 gap도 안 생겨서 전체 manifold를 구성할 수 있게 된다는 말 같습니다.

 

그래서 불필요한 높은 차원의 Simplices에서 발생하는 Bunching effect가 생기지 않게 해 준다고 하네요!

이렇게 있으면 gap이 생기고 disconnected components가 생긴다고 하는 것 같습니다.

 

데이터가 균등하게 퍼져 있기 때문에 우리는 실제로 기본 매니 폴드를 커버하고 응집으로 끝나지 않습니다.

다른 말로하면,이 모든 이론은 데이터가 다양체 위에 균일하게 분포되었다고 가정할 때 잘 작동합니다.

분명히 우리가 매니 폴드에 포인트를 균일하게 분배했다면, 이것은 훨씬 더 잘 작동할 것입니다.

그러나 실제 데이터는 그렇지 않은 것을 모두 알고 있고, 그러면 이것을 어떻게 해결을 해야 할까요?!

 

문제를 앞으로 돌아가면,

데이터가 매니 폴드에 균일하게 분포되어 있다고 가정하고 매니 폴드 자체에 대한 정보를 묻습니다.

 

 If the data looks like it isn’t uniformly distributed that must simply be because the notion of distance is varying across the manifold – space itself is warping: stretching or shrinking according to where the data appear sparser or denser.
거리의 개념이 다양체 전체에서 다양하기 때문에 단순히 데이터를 균일하게 분포시키지 않은 것처럼 보이는 경우 - 공간 자체가 왜곡됩니다. 즉 데이터가 더 고밀도 또는 고밀도로 나타나는 위치에 따라 늘어나거나 줄어듭니다.

 

 

일단 수학적인 방법으로는 모든 데이터가 균 인하게 분포되어 있는 경우 각각의 거리 계산 방식은 Riemannian geometry를 사용할 수 있지만,

실용적인 관점에서 결국 한 포인트에서 가까운 K개의 이웃점에 대한 것으로 하면 된다고 하고.

여기서 k는 로컬 거리감을 근사화하기 위해 사용하는 표본 크기입니다.

 

그래서 결국 각각의 점들은 자신들만의 고유한 거리 함수를 가지게 됩니다! 

지역석 거리 함수에 관하여 반지름 볼들을 선택할 수 있게 됩니다!

 

결국 이런 방식이 Nerve theorem과 Simplicial Complex관점에서 왜 작동되는지 설명할 거라고 하네요...

수학 + 영어를 못하니... 너무 어렵네요 머라는 건지................ㅠ

동시에 모든 것을 위상적으로 해석하면 k에 대한 의미 있는 해석이 가능해진다.

k의 선택은 Riemann 메트릭을 어떻게 국부적으로 추정할 것인지를 결정합니다.

• K를 작게 선택하면, 매우 지역적 해석을 원하는 것을 의미하게 된다(더 정확하게 큰 변동을 포착하는 그런~~)
• K를 크게 선택하게 되면, 넓은 범위를 기반으로 해서 하겠다는 것이고 넓은 관점에서 볼 수 있다는 머 그런 말 같다.

 

그래도 결국 이런 방식은 또 높은 차원에서 데이터가 고립되는 형태가 나올 수 있기 때문에 

이것을 해결하기 위해 Local Connectivity 아이디어를 더 추가했다고 한다.

 

차원이 높다 보면, 샘플은 기하급수적으로 필요하게 되는, Curse of dimensionality 가 있는데,

Local Connectivity constraint는 절대적인 거리보다는 이웃 간의 거리에 초점을 맞추는 것을 확보할 수 있다.

 

중간에 fuzzy 이런 게 나오는데... 그냥 모르겠다..

 

how do we go about converting that into a low dimensional representation?

그럼 다음 장에는 이것을 어떠한 낮은 차원으로 표현하는지에 대해서 보도록 하겠습니다 ㅠ

 

https://umap-learn.readthedocs.io/en/latest/how_umap_works.html

How UMAP Works — umap 0.3 documentation