UMAP

1. 개요[편집]

UMAP Uniform Manifold Approximation and Projection
발표	매키니스 · 힐리 · 멜빌, 2018 (arXiv 1802.03426)
이론적 포장	퍼지 단체 집합(fuzzy simplicial set)
실제 1단계	근사 kNN 그래프 + 국소 연결성 보정
실제 2단계	음성 표집 SGD로 교차엔트로피 최소화
주 손잡이	n_neighbors · min_dist
초기화	스펙트럴(그래프 라플라시안 고유벡터)
t-SNE 대비	빠름 · transform 가능 · 해석 함정은 동일

논문은 단체 집합과 수반 함자로 시작하는데, 코드는 kNN 그래프에 스프링 달고 흔드는 것이다. 둘 다 사실이다.

UMAP(Uniform Manifold Approximation and Projection)은 고차원 데이터에서 만든 가중 최근접 이웃 탐색 그래프를 저차원 좌표로 옮기되, 그래프의 간선 존재 확률을 저차원에서 재현하도록 교차엔트로피를 확률적 경사법으로 최소화하는 비선형 차원축소 기법이다. 매키니스(Leland McInnes), 힐리(John Healy), 멜빌(James Melville)이 2018년에 발표했고, t-SNE가 십 년 가까이 독점하던 고차원 시각화 판을 몇 년 만에 절반 이상 가져갔다.

빠르게 퍼진 이유는 세 가지로 정리된다 — 속도(수백만 점이 현실적인 시간에 돈다), transform(학습된 임베딩에 새 점을 찍을 수 있다), 그리고 전역 구조를 더 잘 지킨다는 평판이다. 셋 중 앞의 둘은 구조적으로 사실이고, 마지막 하나는 뒤에서 보듯 상당 부분 초기화 차이였다는 후속 연구가 있다. 다양체 학습의 고전 삼총사와 달리 고유값 문제를 풀지 않는다는 점에서 t-SNE와 같은 종족이다.

2. 이론적 포장과 실제 계산[편집]

원 논문의 유도는 리만 기하와 위상 데이터 분석 쪽 언어로 되어 있다. 요지만 옮기면 이렇다 — 데이터가 어떤 리만 다양체에서 균일하게 뽑혔다고 가정하고, 그 다양체 위에서 각 점 주위의 거리를 재정의한 뒤, 그 국소 정보들을 퍼지 단체 집합으로 붙여 하나의 위상적 표현을 만든다. 저차원에서도 같은 방식으로 표현을 만들고, 두 표현 사이의 퍼지 집합 교차엔트로피를 최소화한다.

“균일하게 뽑혔다”는 가정은 명백히 거짓인데, UMAP은 이 가정을 거리를 점마다 다시 스케일해서 억지로 참으로 만드는 방식으로 쓴다. 즉 “데이터가 균일하지 않다”를 “다양체의 계량이 점마다 다르다”로 바꿔 읽는다. 실무적으로는 t-SNE가 점마다 $\sigma_i$ 를 따로 이진탐색하는 것과 같은 일이며, 동기만 다르게 설명한 것이라고 보면 크게 틀리지 않는다.¹

중요한 것은 이 이론이 알고리즘의 성능을 보장하지 않는다는 점이다. 유도에서 실제 구현으로 넘어오는 지점마다 근사와 편의가 들어가 있고, 특히 최적화 단계의 음성 표집은 이론이 예측하지 않는 동작을 한다(아래 참조). 논문의 수학이 인상적이라는 이유로 결과를 더 믿을 근거는 없다.

3. 1단계 — 그래프 만들기[편집]

여기까지는 전부 결정론적이고, 여기서 그림의 골격이 결정된다.

근사 kNN. 각 점의 n_neighbors 개 이웃을 찾는다. 정확한 kNN은 $N$ 이 커지면 감당이 안 되므로 NN-Descent(동·차리카·리, 2011)를 쓴다. “내 이웃의 이웃은 내 이웃일 가능성이 높다”는 관찰로 후보 목록을 반복 갱신하는 알고리즘이고, 임의의 거리 척도에 대해 작동한다는 것이 KD-트리류 대비 장점이다. 정확한 k-최근접 이웃을 포기한 이 결정이 UMAP 속도의 절반이다.

국소 연결성 보정. 점 $i$ 에서 가장 가까운 이웃까지의 거리를 $\rho_i$ 라 하고, 간선 가중치를

$$w_{i\to j} = \exp\!\left(-\frac{\max\left(0,\ d(x_i,x_j)-\rho_i\right)}{\sigma_i}\right)$$

로 둔다. $\rho_i$ 를 빼는 것이 핵심이다. 모든 점은 최근접 이웃과 가중치 1로 연결된다 — 즉 어떤 점도 고립되지 않는다는 것이 보장된다. 차원의 저주 때문에 고차원에서는 모든 거리가 비슷하게 커지는데, 이 뺄셈이 “절대 거리”가 아니라 “가장 가까운 것보다 얼마나 더 먼가”로 척도를 바꿔 그 문제를 피해 간다.

대역폭 $\sigma_i$ 는

$$\sum_{j=1}^{k} \exp\!\left(-\frac{\max(0,\ d_{ij}-\rho_i)}{\sigma_i}\right) = \log_2 k$$

가 되도록 이진탐색한다. t-SNE의 퍼플렉시티 이진탐색과 판박이다.

대칭화. $w_{i\to j}$ 와 $w_{j\to i}$ 가 다르므로 퍼지 합집합(확률적 t-여합)으로 합친다.

$$w_{ij} = w_{i\to j} + w_{j\to i} - w_{i\to j}\,w_{j\to i}$$

t-SNE가 산술평균으로 대칭화하는 자리에 UMAP은 합집합을 쓴다. 합집합은 둘 중 하나만 강해도 간선을 살린다 — 밀도가 다른 두 영역을 잇는 간선이 더 잘 살아남는 쪽이다.

4. 2단계 — 저차원 최적화[편집]

저차원 유사도는 t-SNE의 코시 커널을 일반화한 형태다.

$$\psi(y_i,y_j) = \left(1 + a\,\|y_i-y_j\|^{2b}\right)^{-1}$$

$a,b$ 는 사용자가 정하지 않고, min_dist와 spread로 정의되는 목표 곡선에 최소제곱으로 수치 적합해서 얻는다. min_dist = 0, spread = 1 이면 $a=b=1$ 이 되어 정확히 t-SNE의 커널로 되돌아간다.

손실은 퍼지 집합 교차엔트로피다.

$$C = \sum_{ij}\left[\ w_{ij}\log\frac{w_{ij}}{\psi_{ij}} \ +\ (1-w_{ij})\log\frac{1-w_{ij}}{1-\psi_{ij}}\ \right]$$

앞항은 인력, 뒷항이 척력이다. t-SNE의 KL에는 이 뒷항이 없고 대신 $Q$ 의 정규화 상수가 척력 역할을 한다. 이 차이가 계산에서 결정적이다 — UMAP의 손실에는 분배함수(모든 쌍에 대한 합)가 없어서, 쌍 하나만 뽑아 그래디언트를 계산해도 편향이 없다.

그래서 최적화가 확률적 경사하강법이 된다. 매 스텝마다 가중치 $w_{ij}$ 에 비례하는 확률로 간선 하나를 뽑아 두 점을 당기고, 그 점에 대해 무작위로 고른 negative_sample_rate(기본 5)개 점을 밀어낸다. 단어 임베딩 학습(word2vec)이 쓴 음성 표집과 같은 발상이고, $O(N^2)$ 도 쿼드트리도 필요 없다. t-SNE가 Barnes-Hut 알고리즘으로 척력 합을 근사해야 하는 자리를 UMAP은 아예 우회한다.

다만 이 편의에는 대가가 있다. 음성 표집은 무작위로 뽑은 점을 밀어내므로, 실제로 최적화되는 목적함수는 위에 적은 교차엔트로피가 아니다. 표집 분포가 척력 항에 곱해져 유효 손실을 바꾸고, negative_sample_rate를 바꾸면 최소점 자체가 이동한다. 이를 명시적으로 분석한 후속 연구가 있다.²

5. t-SNE와 무엇이 실제로 다른가[편집]

항목	t-SNE	UMAP
고차원 유사도	가우시안, 퍼플렉시티로 대역폭	지수, $\rho_i$ 보정 + n_neighbors
대칭화	산술평균	퍼지 합집합
저차원 커널	코시 (고정)	$a,b$ 적합 (min_dist)
손실	forward KL	퍼지 교차엔트로피
척력	분배함수 (BH·FFT 근사 필요)	음성 표집
초기화	관례적으로 난수	스펙트럴 (기본값)
새 점	불가 (전체 재계산)	transform 가능
출력 차원	실질적으로 2~3	임의

“UMAP이 전역 구조를 더 잘 보존한다”는 통설이 이 표의 어느 줄에서 나오는가가 핵심 쟁점이었다. 코박과 린더만(2021)은 두 방법의 초기화를 통제해 비교했고, t-SNE를 주성분 분석으로 초기화하고 UMAP을 난수로 초기화하면 전역 구조 보존의 우열이 뒤집힌다는 것을 보였다. 즉 알고리즘의 공로로 발표된 것이 상당 부분 기본 초기화 설정의 공로였다.³

남은 차이도 있다. 뵘·베렌스·코박(2022)은 여러 이웃 임베딩 기법이 인력-척력 비율이라는 하나의 축 위에 놓인다는 것을 보였다. 이 관점에서 UMAP은 대략 “인력을 더 세게 준 t-SNE”에 해당하고, 그래서 덩어리가 더 단단하고 간격이 더 벌어진 그림이 나온다. 음성 표집·min_dist·초기 과장이 전부 이 하나의 손잡이를 다른 방식으로 돌리는 장치다.

6. 손잡이 두 개[편집]

• n_neighbors — 각 점이 보는 이웃 수. 작으면(215) 국소 구조가 살고 그림이 잘게 쪼개진다. 크면(50200) 전역 배치가 안정되는 대신 작은 구조가 뭉개진다. 의미가 “해상도”이지 “군집 개수”가 아니라는 점을 놓치면 안 된다. t-SNE의 퍼플렉시티와 역할이 거의 같다.
• min_dist — 저차원에서 점들이 얼마나 붙어도 되는가의 하한. 순수하게 미학적 파라미터다. 0에 가까우면 덩어리가 조밀한 점 뭉치로 압축되어 군집 구분이 선명해지고, 크면(0.5~0.99) 고르게 퍼져 내부 분포가 보인다. 이 값을 줄여 군집이 또렷해진 것을 두고 “군집이 더 잘 분리됐다”고 말하는 것은 그림의 물리적 크기를 키워 놓고 신호가 커졌다고 말하는 것과 같다.

7. transform — 새 점 찍기[편집]

UMAP이 t-SNE 대비 가진 구조적 이점 하나가 여기 있다. 학습이 끝난 뒤 새 점 $x_{\text{new}}$ 가 오면, 기존 데이터에서 그 점의 kNN을 찾아 같은 방식으로 간선 가중치를 만들고, 기존 좌표는 고정한 채 새 점만 몇 번의 SGD 스텝으로 배치한다. 그래서 UMAP은 훈련/테스트 분리가 있는 파이프라인에 들어갈 수 있고, 전처리 단계로 모델에 끼워 넣는 것도 가능하다.

다양체 학습의 고유값 계열이 나이스트룀 확장으로 푸는 아웃오브샘플 문제를, UMAP은 최적화 문제를 부분적으로 다시 푸는 방식으로 해결하는 셈이다. 물론 새 점이 원래 데이터의 지지집합 밖이면 답은 무의미하다는 한계는 똑같다. 감독형 UMAP(레이블을 거리 척도에 섞는 변형)과 교차검증 누수 문제도 같은 맥락에서 조심해야 한다 — 레이블을 넣고 만든 임베딩에서 그 레이블을 예측하는 성능을 재면 당연히 잘 나온다.

8. 해석 주의사항[편집]

t-SNE 문서에 적은 해석 주의사항이 UMAP에도 그대로 적용된다. 군집 사이 거리·군집 크기에 의미가 없다는 것, 하이퍼파라미터 하나로 그림이 통째로 바뀐다는 것, 순수 잡음에서도 그럴듯한 덩어리가 나온다는 것, 좌표를 다음 계산의 입력으로 쓰면 안 된다는 것 — 전부 같다. 여기서 중복해 적지 않으니 그쪽을 읽으면 된다.

UMAP 고유의 함정만 덧붙이면 이렇다.

• min_dist가 만드는 선명함은 증거가 아니다. 기본값 0.1은 군집이 또렷해 보이도록 고른 시각적 기본값이지 데이터의 성질이 아니다.
• 스펙트럴 초기화 덕에 실행 간 변동이 작아 보인다. 재현성이 좋다는 것은 좋은 성질이지만, “여러 번 돌려도 같은 그림이 나오니 진짜 구조다”라는 추론은 성립하지 않는다. 같은 초기값에서 출발했으니 같은 데로 가는 것이다.
• 2차원 임베딩 자체의 한계가 있다. 단일세포 유전체학 쪽에서는 2차원 임베딩이 원 데이터의 이웃 관계를 얼마나 왜곡하는지를 정량화하고, 임베딩 그림에 근거한 결론 전반에 문제를 제기한 비판이 나와 있다.⁴ 도구를 바꾼다고 해결되는 문제가 아니라 고차원을 2차원에 넣는다는 행위 자체의 한계다.
• 밀도 정보는 여전히 지워진다. $\rho_i$ 보정과 점별 대역폭이 밀도를 의도적으로 균일화하기 때문이다. 밀도를 보고 싶으면 밀도 보존 변형(densMAP 계열)을 따로 써야 한다.

9. 관련 문서[편집]

• t-SNE · 다양체 학습 · 주성분 분석 · 다차원 척도법
• 최근접 이웃 탐색 · KD-트리 · 국소 민감 해싱 · HNSW
• 확률적 경사하강법 · 경사하강법 · 쿨백-라이블러 발산
• 스펙트럴 군집화 · 고유값 문제 · 희소행렬
• DBSCAN · HDBSCAN · k-평균 군집화
• 차원의 저주 · 오토인코더 · 위상 데이터 분석 · 단일세포 RNA 시퀀싱

10. Footnotes[편집]

1. HDBSCAN의 저자이기도 한 매키니스가 만든 도구라, UMAP과 HDBSCAN을 이어 붙이는 파이프라인이 널리 쓰인다. 다만 “UMAP 좌표에서 HDBSCAN을 돌린다”는 것은 t-SNE 문서가 하지 말라고 적은 바로 그 행위다. 저자가 만든 조합이라고 해서 방법론적으로 안전해지는 것은 아니다. ↩

2. Damrich & Hamprecht (2021), On UMAP’s True Loss Function, NeurIPS. 결론을 거칠게 요약하면 “UMAP은 논문에 적힌 손실을 최소화하지 않지만, 그럼에도 잘 돈다”이다. 공학에서는 흔한 일이고, 이론 유도가 결과를 보증하지 않는다는 앞 절의 이야기와 정확히 같은 지점이다. ↩

3. Kobak & Linderman (2021), Nature Biotechnology 39:156–157. 이 논문 이후 scikit-learn의 t-SNE 기본 초기화가 난수에서 PCA로 바뀌었다. 몇 년치 통설이 기본값 한 줄에 걸려 있었던 셈인데, 이 바닥에서 “기본값은 저자의 취향이지 진리가 아니다”의 가장 비싼 사례로 꼽을 만하다. ↩

4. Chari & Pachter (2023), The specious art of single-cell genomics, PLOS Computational Biology. 제목의 “specious”는 “그럴듯해 보이지만 틀린”이라는 뜻이다. 제목부터 싸움을 걸고 시작하는 논문이고, 실제로 활발한 반론이 이어졌다. 다만 “2차원 그림 위에서 거리를 읽지 마라”는 핵심 주장 자체는 반론 쪽도 대체로 동의한다. ↩