t-SNE

1. 개요[편집]

t-SNE t-distributed Stochastic Neighbor Embedding
발표	판 데어 마턴 & 힌턴, 2008 (JMLR)
조상	SNE — 힌턴 & 로와이스, 2002
고차원 분포	가우시안 조건부 확률 $p_{j|i}$
저차원 분포	자유도 1 스튜던트 $t$(= 코시)
손실	KL 발산 $\mathrm{KL}(P\,\|\,Q)$
주 손잡이	퍼플렉시티(perplexity)
복잡도	원판 $O(N^2)$ → Barnes-Hut $O(N\log N)$

1000차원에 사는 점 5만 개를 A4 한 장에 그려야 한다. 당연히 다 잃는다. 문제는 무엇을 잃을지 고르는 것이다.

t-SNE(t-distributed Stochastic Neighbor Embedding)는 고차원 데이터의 국소 이웃 관계를 확률분포로 바꿔 놓고, 저차원에서 같은 이웃 확률을 최대한 비슷하게 재현하는 점 배치를 경사법으로 찾아내는 비선형 임베딩 기법이다. 판 데어 마턴(Laurens van der Maaten)과 힌턴(Geoffrey Hinton)이 2008년에 발표했고, 이후 십수 년간 단일세포 유전체학부터 신경망 은닉층 시각화까지 “고차원 데이터를 일단 그려 보는” 작업의 사실상 표준이 됐다.¹

주성분 분석이 분산이 큰 방향으로 사영하는 선형 연산이고, 다차원 척도법이 모든 쌍의 거리를 고루 맞추려 애쓴다면, t-SNE는 처음부터 먼 거리를 포기한다고 선언하고 시작한다. 이 포기가 성능의 원천이자 오해의 원천이다. 다양체 학습의 고전 삼총사(Isomap·LLE·라플라시안 고유맵)가 전부 대칭 고유값 문제로 귀결되는 반면, t-SNE는 비볼록 손실을 경사하강법으로 내려가는 완전히 다른 종족이다.

2. 거리를 확률로 바꾸기[편집]

출발점은 조상 격인 SNE(Stochastic Neighbor Embedding, 2002)다. 점 $x_i$ 가 “이웃을 하나 고른다면 $x_j$ 를 고를 확률”을 가우시안 커널로 정의한다.

$$p_{j|i} = \frac{\exp\!\left(-\|x_i-x_j\|^2 / 2\sigma_i^2\right)}{\sum_{k\neq i}\exp\!\left(-\|x_i-x_k\|^2 / 2\sigma_i^2\right)}, \qquad p_{i|i}=0$$

여기서 중요한 것은 대역폭 $\sigma_i$ 에 아래 첨자 $i$ 가 붙어 있다는 점이다. 점마다 다른 대역폭을 쓴다. 조밀한 영역에서는 좁게, 성긴 영역에서는 넓게 — 즉 데이터 밀도의 불균일이 확률로 넘어오지 않도록 각 점의 시야를 개별적으로 맞춘다. 이 한 줄이 실데이터에서 t-SNE가 잘 도는 이유의 절반을 차지한다.

t-SNE는 여기에 대칭화를 추가한다. 조건부 확률을 그대로 쓰면 외톨이 점의 그래디언트가 사실상 사라지는 문제가 있어서, 결합확률로 바꾼다.

$$p_{ij} = \frac{p_{j|i} + p_{i|j}}{2N}$$

이렇게 두면 $\sum_j p_{ij} > 1/(2N)$ 이 모든 $i$ 에 대해 보장되어, 어느 점도 손실함수에서 완전히 무시되지 않는다.

3. 퍼플렉시티 — 대역폭을 정하는 손잡이[편집]

$\sigma_i$ 를 사람이 $N$ 개 지정할 수는 없으니 간접적으로 정한다. 조건부 분포 $P_i$ 의 섀넌 엔트로피에서 유도되는 퍼플렉시티를

$$\mathrm{Perp}(P_i) = 2^{H(P_i)}, \qquad H(P_i) = -\sum_j p_{j|i}\log_2 p_{j|i}$$

로 정의하고, 사용자가 정한 하나의 목표값(보통 5~50)에 맞도록 점마다 $\sigma_i$ 를 이진탐색한다. $H$ 가 $\sigma_i$ 에 대해 단조증가라 이진탐색이 안전하게 수렴한다.

퍼플렉시티는 대략 “각 점이 몇 명을 이웃으로 셈하는가” 로 읽으면 된다. 균등한 $k$ 개 이웃 분포의 퍼플렉시티가 정확히 $k$ 이기 때문이다. 그래서 퍼플렉시티 30은 “이웃 30명짜리 시야”에 가깝다. 이 값이 그림을 통째로 바꾼다는 것이 뒤에 나올 주의사항의 핵심이다.

4. 혼잡 문제와 두꺼운 꼬리[편집]

t-SNE의 이름에 붙은 t가 바로 이 절의 내용이다. 저차원에서도 가우시안을 쓰면(그게 SNE다) 그림이 중앙으로 뭉개진다. 이유는 기하학적이다.

$D$ 차원에서 반지름 $r$ 안의 부피는 $r^D$ 에 비례한다. 고차원 공간에서 어떤 점 주위의 “적당히 떨어진” 점들은 그 부피 때문에 압도적으로 많다. 그런데 이 점들을 2차원 평면에 옮기면 같은 거리 띠에 들어갈 자리가 $r^2$ 만큼밖에 없다. 자리가 모자란 중거리 점들이 전부 안쪽으로 밀려 들어가 덩어리들이 한가운데서 서로 짓눌리는 현상이 혼잡 문제(crowding problem)다.

해법은 저차원 커널의 꼬리를 두껍게 하는 것이다. t-SNE는 자유도 1의 스튜던트 $t$ 분포(= 코시 분포)를 쓴다.

$$q_{ij} = \frac{\left(1+\|y_i-y_j\|^2\right)^{-1}}{\sum_{k\neq l}\left(1+\|y_k-y_l\|^2\right)^{-1}}$$

꼬리가 두꺼우니 같은 확률값을 훨씬 더 먼 거리에서 만들어낼 수 있다. 고차원에서 중간쯤 떨어진 쌍이 저차원에서는 아주 멀리 놓여도 $q_{ij}$ 가 $p_{ij}$ 와 맞아떨어진다. 즉 평면의 공간 부족을 “축척을 늘려” 해결하는 셈이다. 덤으로 $(1+d^2)^{-1}$ 은 지수함수와 달리 계산이 싸고, 서로 아주 먼 쌍에 대해 척력이 $1/d$ 로만 줄어들어 멀리 떨어진 덩어리끼리도 계속 밀어낸다 — 덩어리 사이에 흰 여백이 생기는 그 특유의 그림이 여기서 나온다.

손실은 두 결합분포 사이의 쿨백-라이블러 발산이다.

$$C = \mathrm{KL}(P\,\|\,Q) = \sum_{i \neq j} p_{ij}\log\frac{p_{ij}}{q_{ij}}$$

방향이 forward KL($P$ 가 앞)이라는 점이 결정적이다. $p_{ij}$ 가 큰데 $q_{ij}$ 가 작으면 벌점이 무한대로 커지지만, 반대는 거의 공짜다. 번역하면 “가까운 것을 멀리 놓으면 크게 혼내고, 먼 것을 가까이 놓는 것은 대충 넘어간다.” t-SNE가 국소 구조만 지키고 전역 구조를 버리는 이유는 알고리즘의 실수가 아니라 이 손실함수에 애초부터 적혀 있던 설계다.²

그래디언트는 놀랄 만큼 깔끔하게 떨어진다.

$$\frac{\partial C}{\partial y_i} = 4\sum_{j\neq i}\left(p_{ij}-q_{ij}\right)\left(y_i-y_j\right)\left(1+\|y_i-y_j\|^2\right)^{-1}$$

$p_{ij}$ 에 붙은 항은 인력, $q_{ij}$ 에 붙은 항은 척력이다. 결국 t-SNE는 스프링과 반발력으로 이루어진 $N$ 입자계의 퍼텐셜 최소화이며, 그래서 N체 문제 가속 기법이 그대로 이식된다.

5. 최적화 — 초기 과장과 잔기술[편집]

비볼록 손실이라 지역 최적해가 지천이다. 원 논문이 제시한 처방이 몇 가지 있고, 이게 그냥 “튜닝 팁”이 아니라 결과를 좌우한다.

• 초기 과장(early exaggeration) — 초기 반복 동안 $p_{ij}$ 에 상수(원 논문 4, scikit-learn 기본값 12)를 곱한다. 인력만 인위적으로 키우면 덩어리가 먼저 단단하게 뭉치고, 뭉친 덩어리들은 서로 움직일 빈 공간을 확보한 채 재배치된다. 과장을 끄기 전까지는 그림이 엉망으로 보이는 게 정상이다.
• 모멘텀과 적응 학습률 — 초기 모멘텀 0.5, 이후 0.8. 여기에 그래디언트 부호가 유지되는 방향의 학습률을 키우는 게인 방식을 얹는다.
• 초기값 — 관례적으로 작은 분산의 가우시안 난수였다. 그런데 이 관례가 “t-SNE는 전역 구조를 못 지킨다”는 평판의 상당 부분을 만들었다. 주성분 분석 좌표나 라플라시안 고유맵으로 초기화하면 전역 배치가 눈에 띄게 안정된다.³
• 조기 압축·학습률 — 학습률이 너무 작으면 덩어리들이 초기 과장 단계에서 하나로 뭉친 채 갇힌다. 큰 $N$ 에서는 $\eta \approx N/12$ 정도로 크게 잡는 것이 요즘의 권장값이다.

6. 빠르게 만들기[편집]

원판은 모든 쌍을 계산하니 반복마다 $O(N^2)$ 다. $N=10^5$ 이면 답이 없다. 두 갈래로 가속된다.

Barnes-Hut t-SNE(판 데어 마턴, 2014)는 두 가지를 자른다. 인력 쪽은 $p_{ij}$ 를 최근접 이웃 탐색으로 얻은 $3u$ 개 이웃($u$ 는 퍼플렉시티)만 남기고 나머지를 0으로 희소화한다. 척력 쪽은 쿼드트리를 세워 멀리 있는 점 무리를 질량중심 하나로 묶는다 — 천체역학의 Barnes-Hut 알고리즘을 그대로 가져온 것이고, 판정 기준 $\theta$ 도 같은 역할을 한다. 전체가 $O(N\log N)$ 으로 떨어진다.

FIt-SNE(린더만 외, 2019)는 척력 합을 격자 위 보간과 고속 푸리에 변환으로 계산해 $O(N)$ 까지 내린다. 백만 점 규모의 단일세포 데이터가 노트북에서 도는 것이 이 덕이다.

7. 그림을 읽는 법 — 여기가 진짜 본론[편집]

t-SNE 그림은 정량 지표가 아니라 가설 생성 도구다. 이 경고는 예의상 붙이는 면책 문구가 아니라, 실제로 논문 결론이 뒤집힌 사례가 쌓여 있는 실전 규칙이다.⁴

• 덩어리 사이의 거리에는 의미가 없다. 손실함수가 $p_{ij}$ 가 작은 쌍을 사실상 벌하지 않으므로, 두 덩어리가 화면에서 멀다는 것은 “가깝지 않다”는 뜻일 뿐 “얼마나 먼지”에 대한 정보가 아니다. “A 군집이 B보다 C에 가까우니 계통적으로 가깝다” 류의 주장은 t-SNE 그림만으로는 근거가 없다.
• 덩어리의 크기에도 의미가 없다. 점마다 대역폭을 맞추는 그 설계 때문에 밀도 차이가 의도적으로 지워진다. 성긴 군집과 조밀한 군집이 비슷한 크기의 얼룩으로 나온다.
• 퍼플렉시티 하나로 결론 내지 마라. 값이 작으면 잘게 쪼개진 파편들이, 크면 하나로 합쳐진 덩어리가 나온다. 여러 값에서 재현되는 구조만 믿는다. 퍼플렉시티가 표본 수에 비해 크면 국소 이웃 개념 자체가 무의미해진다.
• 순수 잡음에서도 군집이 나온다. 고차원 가우시안 난수에 퍼플렉시티를 작게 주면 그럴듯한 덩어리들이 만들어진다. 덩어리가 보인다는 것은 군집이 존재한다는 증거가 아니다.
• 실행마다 다르다. 비볼록 + 난수 초기화이므로 시드를 바꾸면 그림이 바뀐다. 회전·반사는 손실이 불변이라 당연하고, 그 이상의 차이도 흔하다. 논문에 쓸 그림이면 시드와 하이퍼파라미터를 전부 적어야 한다.
• 위상 구조는 못 지킨다. 원형·고리형 연속 궤적(세포 분화 궤적 같은 것)은 t-SNE에서 자주 끊어진 조각들로 나타난다. 연속적인 변화를 보고 싶다면 애초에 다른 도구를 써야 한다.

요약하면 t-SNE 좌표를 다음 계산의 입력으로 쓰지 마라. 그 좌표 위에서 k-평균 군집화를 돌리거나 거리를 재서 통계를 내는 것은, 알고리즘이 명시적으로 버린 정보를 되살려 쓰겠다는 얘기다. 군집을 찾을 거면 원 공간(또는 주성분 분석으로 적당히 줄인 공간)에서 계층적 군집화나 DBSCAN을 돌리고, t-SNE 그림은 그 결과에 색을 칠해 보는 용도로 쓰는 것이 올바른 순서다.

8. 실무 파이프라인[편집]

표준 절차는 대체로 이렇게 굳어져 있다.

단계	관행	이유
전처리	주성분 분석으로 30~50차원까지 축소	거리 계산 비용 절감, 잡음 방향 제거
이웃 탐색	근사 kNN	정확한 kNN은 $N$ 이 커지면 불가능
초기화	PCA 첫 두 축(스케일 축소)	전역 배치 안정화, 재현성
퍼플렉시티	여러 값 + 큰 $N$ 에서는 $N/100$ 도 검토	스케일마다 다른 구조
학습률	$\eta \approx N/12$	작으면 한 덩어리로 붕괴

전처리로 PCA를 먼저 거는 것이 “왜 비선형 방법 앞에 선형 방법을 붙이나” 싶겠지만, 실제로는 잡음 차원을 걷어내 kNN 그래프의 품질을 올리는 효과가 커서 거의 항상 이득이다. 차원의 저주가 이웃 개념을 갉아먹기 전에 차원을 줄여 놓는 것이라고 보면 된다.

9. 관련 문서[편집]

• UMAP · 다양체 학습 · 다차원 척도법 · 주성분 분석
• 쿨백-라이블러 발산 · 엔트로피 · 피셔 정보
• 경사하강법 · 확률적 경사하강법 · 지역 최적해
• 최근접 이웃 탐색 · 쿼드트리 · KD-트리 · Barnes-Hut 알고리즘
• k-평균 군집화 · DBSCAN · 계층적 군집화 · 스펙트럴 군집화
• 차원의 저주 · 커널 PCA · 오토인코더 · 단일세포 RNA 시퀀싱

10. Footnotes[편집]

1. 정확한 인용은 van der Maaten & Hinton (2008), Visualizing Data using t-SNE, JMLR 9:2579–2605. 이름의 “Stochastic Neighbor”는 확률적 알고리즘이라는 뜻이 아니라 이웃 관계를 확률로 모형화한다는 뜻이다. 물론 난수 초기화 때문에 결과적으로 확률적이기도 하다. 두 배로 헷갈리게 지은 이름. ↩

2. 반대 방향 KL, 즉 $\mathrm{KL}(Q\,\|\,P)$ 를 최소화하는 변형도 존재하며 이쪽은 모드 하나에 집중하는 성격이 된다. 같은 비대칭 이야기가 변분 추론에서 그대로 반복된다. KL의 방향을 안 보고 “분포 사이 거리”라고 부르는 순간 반쯤 틀린 것이다 — 애초에 거리도 아니다(삼각부등식도 대칭성도 없다). ↩

3. Kobak & Linderman (2021), Nature Biotechnology 39:156–157. 제목이 “Initialization is critical for preserving global data structure in both t-SNE and UMAP”인데, 요지는 “UMAP이 전역 구조를 더 잘 지킨다”는 통설의 상당 부분이 알고리즘 차이가 아니라 기본 초기화 차이였다는 것이다. 벤치마크에서 통제 안 된 변수 하나가 몇 년치 통설을 만든 교과서적 사례. ↩

4. Wattenberg, Viégas & Johnson (2016), How to Use t-SNE Effectively, Distill. 인터랙티브 그림으로 “퍼플렉시티만 바꿔도 결론이 뒤집힌다”를 직접 만져 보게 만든 글이라 한 번쯤 볼 가치가 있다. 이 글 이후로도 논문 심사에서 “t-SNE 그림에서 군집 간 거리가 멀므로”라는 문장이 꾸준히 나온다는 것이, 경고문이 몇 개나 붙어 있든 사람은 예쁜 그림을 믿는다는 증거다. ↩