어제 저는 t-SNE를 밑바닥부터 직접 구현해 보았고, 6차원의 덩어리들이 깔끔한 2D 그림으로 풀려나가는 것을 지켜보았습니다. 제대로 작동하며, 그려내는 클러스터(cluster)들은 매우 아름다웠습니다. 하지만 두 가지가 마음에 걸렸습니다. 속도가 느렸다는 점입니다. 매 반복(iteration)마다 $N^2$개의 모든 점 쌍을 건드려야 했습니다. 그리고 전체적인 그림을 놓치고 있었습니다. t-SNE 플롯에서 두 클러스터 사이의 거리는 아무런 의미가 없었습니다. 그래서 오늘은 그 후계자인 UMAP을 구현했습니다. UMAP은 선명한 국소 클러스터(local clusters)를 유지하면서도 이 두 가지 문제를 모두 해결합니다.

사고의 전환: 확률에서 그래프로

t-SNE는 확률(probabilities)로 생각합니다. 모든 점의 쌍에 대해 "당신을 이웃으로 선택할 확률이 얼마나 되는가"를 계산하고, 그 숫자들로 조밀한 행렬(dense matrix)을 만든 다음, 두 번째 행렬이 첫 번째 행렬과 일치할 때까지 2D 점들을 이리저리 움직입니다.

UMAP은 위상수학(topology)으로 생각합니다. 데이터가 어떤 곡면, 즉 매니폴드(manifold) 위에 놓여 있다고 가정하고, 그래프(graph)를 통해 그 표면을 근사합니다. 각 점을 $k$개의 최근접 이웃(k nearest neighbours)과 연결합니다. 그리고 모든 연결에 두 점이 얼마나 강하게 함께 속해 있는지를 나타내는 0과 1 사이의 가중치(weight)를 부여합니다. 이 가중치가 부여된 그래프가 모델의 전부입니다. UMAP의 역할은 연결된 점들은 가까이 유지되고 나머지 것들은 멀어지도록 동일한 그래프를 2D에 그리는 것입니다.

이러한 재정의가 바로 속도가 나오는 지점입니다. 점당 $k$개의 이웃을 가진 그래프는 희소(sparse)합니다. 거대한 조밀한 행렬을 아예 만들 필요가 없습니다.

고차원 그래프 구축하기

세 가지 아이디어가 핵심적인 역할을 수행하며, 저는 각각을 순수 JavaScript로 코딩했습니다.

첫째, 국소 연결성(local connectivity)입니다. 가공되지 않은 이웃 간의 거리는 불공평합니다. 붐비는 지역의 점은 이웃이 가깝고, 희소한 지역의 점은 이웃이 멉니다. 따라서 UMAP은 각 점에 대해 단 하나의 최근접 이웃까지의 거리인 $
ho$(rho)를 뺍니다. 이는 모든 점이 적어도 하나의 다른 점과 완전히 연결되도록 보장하며, 어떤 점도 고립되지 않게 합니다.

둘째, 점별 대역폭(per-point bandwidth) $\sigma$(sigma)입니다. 각 행의 매끄러운 멤버십 값(membership values)의 합이 $\log_2(\text{n_neighbors})$가 되도록 $\sigma$를 이진 탐색(binary-search)합니다. 이는 t-SNE가 목표 퍼플렉시티(perplexity)를 맞추기 위해 가우시안 너비(Gaussian width)를 조정하는 방식과 정확히 일치하게, 그래프를 국소 밀도(local density)에 적응시킵니다.

셋째, 대칭화(symmetrise)입니다. 점 $i$가 생각하는 $j$에 대한 의견은 $j$가 생각하는 $i$에 대한 의견과 일치하는 경우가 드뭅니다. UMAP은 퍼지 합집합(fuzzy union) $a + b - a \cdot b$를 사용하여 두 방향성 가중치(directed weights)를 융합합니다. 이를 통해 에지(edge)당 하나의 대칭적인 강도(symmetric strength)를 부여하며, 완성된 가중치 그래프(weighted graph)가 UMAP의 고차원 타겟(high-dimensional target)이 됩니다.

중요한 두 가지 조절 노브 (knobs)

n_neighbors는 국소(local) 대 전역(global)을 조절하는 다이얼입니다. 작은 값(예: 5)은 UMAP이 가장 가까운 점들만 믿게 만들어 미세한 디테일은 포착하지만 전체적인 형태를 파편화합니다. 큰 값(예: 50)은 각 점이 매니폴드(manifold)를 가로질러 멀리까지 볼 수 있게 하여 더 많은 전역 구조(global structure)를 보존합니다. 이는 t-SNE의 퍼플렉시티(perplexity)와 직접적으로 대응되는 개념입니다.

min_dist는 클러스터(cluster)가 얼마나 조밀하게 모일지를 제어합니다. 2D에서 UMAP은 $1/(1 + a \cdot d^{2b})$ 곡선으로 유사도를 측정하며, 거리가 min_dist에 도달할 때까지 곡선이 평평하게 유지되다가 그 이후에 감소하도록 $a$와 $b$를 최소제곱법(least-squares)으로 피팅합니다. 작은 min_dist는 이웃들이 서로 거의 겹쳐지며 밀집된 덩어리를 형성하게 하고, 큰 min_dist는 각 클러스터를 넓게 퍼뜨려 더 읽기 쉬운 플롯을 만듭니다. 제 데모에서는 두 슬라이더를 드래그하며 레이아웃이 실시간으로 재조정되는 것을 볼 수 있습니다.

그리기: 인력, 척력, 감쇠 (attract, repel, decay)

레이아웃은 고차원(high-D) 그래프와 저차원(low-D) 그래프 사이의 교차 엔트로피(cross-entropy)에 대해 확률적 경사 하강법(stochastic gradient descent, SGD)으로 훈련된 힘 지향 그래프 완화(force-directed graph relaxation)입니다. 각 에포크(epoch)마다 다음 과정을 수행합니다:

• 에지(edge)를 샘플링합니다. — 더 강한 에지가 더 자주 발생하며 — — 두 끝점을 서로 끌어당깁니다(pull).
• 각 인력(pull)에 대해, 몇 번의 부정 샘플링(negative samples)을 수행합니다: 무작위 점들을 잡아 서로 밀어냅니다(push).
• 레이아웃이 고정되도록 학습률(learning rate)을 0을 향해 감쇠(decay)시킵니다.

실제 에지를 따라 인력(attract)을 가하고, 무작위 쌍에 대해 척력(repel)을 가합니다. 이것이 최적화 도구(optimiser)의 전부이며, 밀집 행렬(dense matrix) 대신 샘플링을 통한 희소 그래프(sparse graph)에서 작동하기 때문에, t-SNE가 단계당 이차적(quadratically)으로 확장되었던 것에 비해 대략 선형적(linearly)으로 확장됩니다.

고정된 시드(fixed seed)를 사용하여 Node에서의 인터랙티브 데모를 검증했습니다. 클러스터 간/클러스터 내 분리 점수(between-cluster / within-cluster separation score)가 약 0.34(하나의 혼합된 덩어리)에서 500 에포크(epochs) 이후 25 이상으로 상승합니다. 네 개의 실제 클러스터가 진정으로 분리된 섬 형태로 빠르게 자리 잡습니다.

이것이 알려주는 것과 알려주지 않는 것

UMAP은 국소적 이웃(local neighbourhoods)을 아름답게 보존하며 t-SNE보다 전역적 구조(global structure)를 더 잘 유지하므로, 클러스터의 배치는 실제 신호(signal)를 담고 있습니다. 하지만 이것은 여전히 메트릭 임베딩(metric embedding)은 아닙니다. 정확한 거리, 클러스터 크기, 간격 크기는 근사치일 뿐이며, 두 개의 조절 노브(knobs)에 따라 변합니다. 이를