【알고리즘】 7-2강. UMAP(uniform manifold approximation and projection)

7-2강. UMAP(uniform manifold approximation and projection)

 

추천글 : 【알고리즘】 7강. 차원 축소 알고리즘 

---

1. 개요 [본문]

2. 1단계.  k-simplex 정의 [본문]

3. 2단계.  k-simplex 정의 최적화 [본문]

4. 3단계. graph layout problem solving [본문]

5.  레퍼런스 [본문]

---

 

1. 개요 [목차]

⑴ tSNE와 함께 많이 사용되는 차원 축소 알고리즘

⑵ 리만 기하학(Riemannian geometry)에 기반한 위상 개념을 이용

⑶ 각 점들 간의 연결관계가 아니라 점들이 형성하려는 위상을 포착하려는 이유

① 수학적 이론이 뒷받침 : Nerve theorem 참고

② 위상이 있다는 게 전제가 돼 있으면 여러 알려진 최적화 알고리즘을 쓸 수 있기 때문

 

 

2. 1단계. k-simplex 정의 [목차]

⑴ k-simplex

① 정의 : k 차원의 물체를 만들기 위해 k+1개의 점을 이용한 가장 단순한 형태 

② 0-simplex : 점

③ 1-simplex : 선분 (face는 점)

④ 2-simplex : 삼각형 (face는 선분)

⑤ 3-simplex : 정사면체 (face는 삼각형)

⑵ simplicial complex K 

① 정의 : face끼리 맞닿게 하여 붙인 simplex들의 집합

⑶ 방법 1. Čech complex : 유한한 점들의 집합에서 k-simplex를 정의하는 방법을 제공

① 1^st. 각 점 주위로 일정한 크기의 원을 그림

② 2^nd. 0-simplex의 정의 : 모든 점이 제각각 0-complex가 될 수 있음

③ 3^rd. 1-simplex의 정의 : 만약 어떤 두 점 주위의 원이 모두 겹치는 공간이 있으면 그 두 점은 1-simplex를 형성

④ 4^th. 2-simplex의 정의 : 만약 어떤 세 점 주위의 원이 모두 겹치는 공간이 있으면 그 세 점은 2-simplex를 형성

⑷ 방법 2. Vietoris-Rips complex : Čech complex에서 k-simplex를 정의하는 방식을 0-, 1-simplex에 대해서만 한 것

① 실제 데이터에서 2-simplex 혹은 그 이상의 simplex는 드물다는 사실을 이용함

 

 

3. 2단계. k-simplex 정의 최적화 [목차]

⑴ 원의 반경이 상수값인 경우

① 데이터 포인트가 균질하게 퍼져있는 경우

○ 원의 반경이 너무 작은 경우를 제외하면 위 알고리즘이 잘 작동함

② 데이터 포인트가 비균질하게 퍼져있는 경우

○ 원의 반경이 작은 경우 : 멀리 있는 점들은 차원축소 결과 isolated island로 나타남

○ 원의 반경이 큰 경우 : 가까이 있는 점들 간의 위상 정보를 제대로 캐치하지 못함

○ 원의 반경이 큰지 작은지는 데이터셋에 의존하는 상대적인 개념

⑵ 해결방안 : 데이터 포인트의 sparsity를 고려하여 원의 radius를 정의

① 더 구체적으로는, k-th nearest point에 도달할 만큼 radius를 정의 

 

 

4. 3단계. graph layout problem solving [목차]

⑴ 정의 : 1단계에서 고차원 데이터에 대해 얻은 위상 개념이 보존되도록 저차원 데이터를 재구성하는 것

⑵ 예 1. Laplacian eigenmaps

⑶ 예 2. Diffusion maps

⑷ 예 3. MDS

⑸ 예 4. Sammon mapping

⑹ 예 5. stochastic gradient descent

 

 

5. 레퍼런스 [목차]

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

How UMAP Works — umap 0.5 documentation

⑵ https://arxiv.org/pdf/1802.03426.pdf

 

입력 : 2022.05.19 00:54