t-SNE

t-distributed stochastic neighbor embedding; t-SNE; t-분포 확률적 이웃 임베딩
고차원 데이터의 이웃 관계를 확률 분포로 바꾸고, 저차원(보통 2차원)에서 같은 이웃 분포가 나오도록 점을 배치하는 비선형 시각화 기법

t-SNE(t-distributed stochastic neighbor embedding)는 2008년 판 데르 마턴과 힌턴이 발표한 비선형 차원 축소 기법이다.^[1] 가까운 점은 가깝게 두는 국소 구조 보존에 집중해, 이미지·문서·단일 세포 유전자 발현·신경망 임베딩처럼 수십~수천 차원인 데이터를 2~3차원 산점도로 그리는 데 쓴다. 한국어로는 'T-분포 확률적 임베딩'이라는 번역도 있지만, 실제로는 약어 t-SNE를 그대로 쓰는 경우가 대부분이다.

시각화 전용이라는 점이 중요하다. 군집 크기, 군집 사이 거리, 축의 값은 원래 공간의 양을 그대로 반영하지 않으므로, 그림을 읽을 때 주의할 점이 많다. 상위 개념은 비지도 학습 문서의 "차원 축소" 항목 참고.

배경

SNE(2002): 힌턴과 로위스가 제안한 확률적 이웃 임베딩(stochastic neighbor embedding). 고차원과 저차원 모두에서 가우스 분포로 이웃 확률을 정의하고 두 분포의 쿨백-라이블러 발산을 줄인다.^[2] 최적화가 어렵고 점들이 가운데로 뭉치는 문제가 있었다.
t-SNE(2008): 대칭 확률을 쓰고, 저차원 쪽 분포를 꼬리가 두꺼운 스튜던트 t 분포로 바꿔 두 문제를 줄였다.^[1]
바른스-헛 t-SNE(2014): 쌍별 계산을 공간 분할 트리로 근사해 $O (N^{2})$ 을 $O (N \log N)$ 으로 줄였다.^[3] scikit-learn의 기본 방식이다.
FIt-SNE(2019): 보간과 고속 푸리에 변환으로 척력 계산을 가속해, 대규모 단일 세포 RNA 시퀀싱 데이터 시각화에 맞췄다.^[4]

알고리즘

1. 고차원 이웃 확률

점 $x_{i}$ 가 $x_{j}$ 를 이웃으로 고를 조건부 확률을, $x_{i}$ 를 중심으로 한 가우스 분포로 정의한다.

$p_{j | i} = \frac{\exp (- ‖ x_{i} - x_{j} ‖^{2} / 2 σ_{i}^{2})}{\sum_{k \neq i} \exp (- ‖ x_{i} - x_{k} ‖^{2} / 2 σ_{i}^{2})}, p_{i | i} = 0$

점마다 폭 $σ_{i}$ 가 다르다. 밀집 지역에서는 좁게, 희박한 지역에서는 넓게 잡아야 이웃 수가 비슷해지기 때문이다. $σ_{i}$ 는 사용자가 정한 퍼플렉시티(perplexity)에 맞도록 이진 탐색으로 찾는다(아래 절 참고). 그다음 대칭화한다.

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

$N$ 으로 나눠 전체 합이 1이 되고, 이상치 $x_{i}$ 도 $\sum_{j} p_{i j} > 1 / (2 N)$ 을 보장받아 그림에서 제자리를 갖는다.

2. 저차원 이웃 확률

저차원 점 $y_{i}$ 들 사이에는 자유도 1인 스튜던트 t 분포(코시 분포)를 쓴다.

$q_{i j} = \frac{{(1 + ‖ y_{i} - y_{j} ‖^{2})}^{- 1}}{\sum_{k \neq l} {(1 + ‖ y_{k} - y_{l} ‖^{2})}^{- 1}}$

3. 목적 함수와 기울기

두 분포의 KL 발산을 최소화한다.

$C = K L (P ‖ Q) = \sum_{i \neq j} p_{i j} \log \frac{p_{i j}}{q_{i j}}$

$\frac{\partial C}{\partial y_{i}} = 4 \sum_{j} (p_{i j} - q_{i j}) (y_{i} - y_{j}) {(1 + ‖ y_{i} - y_{j} ‖^{2})}^{- 1}$

$p_{i j} > q_{i j}$ 이면(원래 가까운데 그림에서 멀면) 두 점을 끌어당기고, 반대면 밀어낸다. KL 발산은 비대칭이라 "가까운 점을 멀리 둔 것"에는 큰 벌점을, "먼 점을 가깝게 둔 것"에는 작은 벌점을 준다. 그래서 국소 구조는 잘 보존되지만 전역 거리는 보존되지 않는다.

왜 t 분포인가: 혼잡 문제

고차원에서는 한 점으로부터 중간 거리에 있는 점이 아주 많다. 이것을 2차원 원판에 같은 비율로 담을 공간이 없어서, 가우스 분포를 쓰면 중간 거리 점들이 가운데로 뭉개진다. 원 논문은 이를 혼잡 문제(crowding problem)라 불렀다.^[1] 꼬리가 두꺼운 t 분포를 저차원에 쓰면, 고차원의 중간 거리를 저차원의 더 먼 거리로 대응시킬 수 있어 군집 사이에 빈 공간이 생긴다. t-SNE 그림에서 군집이 뚜렷하게 갈라져 보이는 이유이자, 군집 간 거리가 과장되는 이유다.

4. 최적화

경사 하강에 모멘텀을 더해 반복한다. 원 논문은 1000번 반복하고, 처음 50번은 $p_{i j}$ 에 4를 곱하는 초기 과장(early exaggeration)을 썼다.^[1] 초기 과장은 군집들이 초반에 서로 멀리 떨어져 자리를 잡도록 돕는다. 목적 함수가 볼록하지 않아 초기화와 난수 시드에 따라 결과가 달라진다.

퍼플렉시티

퍼플렉시티는 점 $i$ 의 이웃 분포 $P_{i}$ 의 엔트로피로 정의한다.

$P e r p (P_{i}) = 2^{H (P_{i})}, H (P_{i}) = - \sum_{j} p_{j | i} \log_{2} p_{j | i}$

"유효 이웃 수"로 읽으면 된다. 원 논문은 결과가 퍼플렉시티 변화에 비교적 강하고 일반적인 값은 5~50이라고 적었다.^[1] $H$ 는 $σ_{i}$ 에 대해 단조 증가하므로 이진 탐색으로 맞춘다.

import numpy as np

def conditional_p(D2_i, target_perp, tol=1e-5, iters=100):
    """점 i에서 다른 점들까지의 제곱 거리(자기 자신 제외)로 p_{j|i}를 구한다."""
    lo, hi, beta = 0.0, np.inf, 1.0             # beta = 1 / (2 sigma_i^2)
    for _ in range(iters):
        p = np.exp(-(D2_i - D2_i.min()) * beta)  # 최솟값을 빼서 언더플로 방지
        p /= p.sum()
        H = -np.sum(p * np.log2(p + 1e-12))
        if abs(2**H - target_perp) < tol:
            break
        if 2**H > target_perp:                   # 이웃이 너무 많다: sigma를 줄인다
            lo = beta
            beta = beta * 2 if hi == np.inf else (beta + hi) / 2
        else:
            hi = beta
            beta = (beta + lo) / 2
    return p

고르는 요령은 다음과 같다.

퍼플렉시티는 점 개수보다 작아야 한다. scikit-learn도 이를 요구하고, 데이터가 클수록 큰 값을 권한다.^[5]
작은 값은 아주 가까운 이웃만 보아 국소 구조가 잘게 쪼개지고, 순수한 잡음에서도 가짜 덩어리가 보일 수 있다. 큰 값은 더 넓은 구조를 반영하지만 세부가 뭉개지고 계산이 늘어난다.
하나의 값으로 결론 내지 말고 여러 값(예: 5, 30, 50, 100)으로 그려서 공통으로 나타나는 구조만 믿는다.^[6]

scikit-learn 사용법

from sklearn.datasets import load_digits
from sklearn.decomposition import PCA
from sklearn.manifold import TSNE, trustworthiness

X, y = load_digits(return_X_y=True)                  # 1797 x 64
X50 = PCA(n_components=50, random_state=0).fit_transform(X)   # 먼저 PCA로 줄인다

for perp in [5, 30, 50]:
    tsne = TSNE(n_components=2, perplexity=perp, init="pca",
                learning_rate="auto", random_state=0)
    Y = tsne.fit_transform(X50)                       # (1797, 2)
    print(perp, tsne.kl_divergence_, trustworthiness(X, Y, n_neighbors=10))
# 5 0.945 0.992 / 30 0.753 0.993 / 50 0.678 0.992  (scikit-learn 1.7)

trustworthiness는 저차원 이웃이 원래 공간에서도 이웃이었는지를 0~1로 잰다. kl_divergence_는 퍼플렉시티마다 $P$ 자체가 달라지므로 퍼플렉시티끼리 비교하는 기준이 될 수 없다.

매개변수	기본값(1.9)	설명
`perplexity`	30.0	유효 이웃 수. 5~50 사이를 고려하라고 안내한다
`early_exaggeration`	12.0	초기 과장 배수. 원 논문의 4보다 크다
`learning_rate`	"auto"	$\max (N / e a r l y_e x a g g e r a t i o n / 4, 50)$ . 1.2부터 기본값. 다른 구현(bhtsne, openTSNE 등)보다 정의가 4배 크다
`max_iter`	1000	1.5에서 `n_iter`에서 이름이 바뀌었다. 250 이상이어야 한다
`init`	"pca"	1.2부터 기본값. 무작위 초기화보다 전역 배치가 안정적이다
`method`	"barnes_hut"	$O (N \log N)$ 근사. "exact"는 $O (N^{2})$
`angle`	0.5	바른스-헛 근사의 정확도와 속도 절충(0.2~0.8에서 둔감)

scikit-learn은 특징이 매우 많으면 PCA(조밀 데이터)나 TruncatedSVD(희소 데이터)로 먼저 50차원 정도로 줄이라고 권한다. 잡음을 줄이고 거리 계산을 빠르게 하기 위해서다.^[5] TSNE에는 transform 메서드가 없어, 새 데이터를 기존 그림에 추가할 수 없다.

해석할 때 주의할 점

디스틸(Distill)의 해설 글은 t-SNE 그림을 잘못 읽는 대표적인 경우를 정리했다.^[6]

하이퍼파라미터가 결과를 크게 바꾼다. 퍼플렉시티와 반복 횟수를 바꿔 보고, 모양이 안정될 때까지 반복해야 한다. 너무 일찍 멈춘 그림은 점들이 눌린 모양이 된다.
군집 크기는 의미가 없다. t-SNE는 밀집한 군집을 늘리고 희박한 군집을 줄이는 경향이 있어, 그림에서 큰 군집이 실제로 퍼진 군집이라는 보장이 없다.
군집 사이 거리는 의미가 없을 수 있다. 멀리 떨어진 두 군집이 더 가까운 두 군집보다 실제로 더 다르다고 말할 수 없다.
무작위 잡음도 무작위로 보이지 않을 수 있다. 작은 퍼플렉시티에서는 아무 구조 없는 가우스 잡음에서도 덩어리가 보인다.
모양은 때때로만 보인다. 선이나 고리 같은 형태가 드러나기도 하지만 왜곡이 섞인다.
위상 구조를 보려면 그림 하나로는 부족하다. 여러 퍼플렉시티의 그림을 비교한다.

그 밖에 실무에서 지킬 점은 다음과 같다.

t-SNE 좌표를 군집 분석이나 분류의 입력 특징으로 쓰지 않는다. 거리와 밀도가 왜곡된 좌표이기 때문이다. 군집은 원래 공간이나 PCA 공간에서 구한 뒤 색으로 표시한다.
축과 좌표값에는 단위나 의미가 없다. 회전·반전해도 같은 결과다.
시드를 고정하고, 결론을 내리기 전에 시드를 바꿔 여러 번 돌린다.

UMAP과의 비교

UMAP(Uniform Manifold Approximation and Projection)은 2018년 매키네스 등이 발표한 기법으로, 리만 기하학과 대수 위상수학에 기반한 이론에서 출발한다.^[7] 실제 계산은 t-SNE와 비슷하게 k-최근접 이웃 그래프를 만들고, 고차원 그래프와 저차원 그래프가 비슷해지도록 점을 배치한다.

항목	t-SNE	UMAP
고차원 유사도	가우스 커널, 퍼플렉시티로 폭 조정, 전체 정규화	k-최근접 이웃 그래프, 점마다 거리 척도 조정, 정규화 없음
저차원 유사도	스튜던트 t 분포(자유도 1)	$(1 + a d^{2 b})^{- 1}$ 꼴 곡선(`min_dist`로 $a, b$ 결정)
목적 함수	KL 발산	퍼지 집합의 교차 엔트로피(인력 + 척력 항)
주요 매개변수	`perplexity`(기본 30)	`n_neighbors`(기본 15), `min_dist`(기본 0.1)^[8]
속도	바른스-헛 $O (N \log N)$ . 큰 데이터에서 느린 편	근사 최근접 이웃 + 음성 표본추출로 대체로 더 빠르다
새 데이터 변환	scikit-learn 구현에는 없음	`transform` 지원
출력 차원	2~3차원 시각화 위주	더 높은 차원으로도 써서 전처리에 쓸 수 있다
전역 구조	잘 보존하지 못한다	더 잘 보존한다는 주장이 있으나 초기화 영향이 크다(아래)
라이브러리	scikit-learn `TSNE`, openTSNE, FIt-SNE	`umap-learn`(scikit-learn에는 없음)

UMAP 논문은 시각화 품질이 t-SNE와 대등하고 전역 구조를 더 잘 보존한다고 주장했다.^[7] 그러나 코박과 린더만은 이 차이가 알고리즘이 아니라 초기화에서 온다고 반박했다. 기존 비교는 t-SNE를 무작위로, UMAP을 라플라스 고유맵(스펙트럼 임베딩)으로 초기화했는데, 둘 다 무작위로 초기화하면 전역 구조 보존이 똑같이 나쁘고, 둘 다 PCA 같은 정보 있는 초기화를 쓰면 똑같이 좋았다.^[9] scikit-learn도 1.2부터 t-SNE의 기본 초기화를 PCA로 바꾸었다.^[5]

선택 기준은 대략 다음과 같다.

수십만 점 이상이거나 새 데이터를 같은 좌표계에 계속 넣어야 하면 UMAP.
그림을 2차원 시각화로만 쓰고 국소 군집 구조가 관심사면 둘 다 괜찮다. 해석 주의점(군집 크기·거리)은 UMAP에도 그대로 적용된다.
전역 구조(군집 사이 관계)가 중요하면 둘 중 무엇이든 PCA 초기화를 쓰고, PCA 그림도 같이 본다.

다른 차원 축소와 비교

방법	선형성	보존하는 것	새 데이터	주 용도
주성분 분석	선형	전역 분산	가능	전처리, 압축, 1차 시각화
다차원 척도법	비선형(거리 기반)	쌍별 거리 전체	어려움	거리 행렬 시각화
커널 PCA	비선형	특징 공간의 분산	가능	비선형 특징 추출. 커널 트릭 참고
t-SNE	비선형	국소 이웃	불가(기본 구현)	2~3차원 시각화
UMAP	비선형	국소 이웃 + 일부 전역	가능	시각화, 전처리

언어 모델 시대에는 문장 임베딩이나 워드 임베딩의 분포를 들여다보는 데 t-SNE와 UMAP이 쓰인다. 이때도 같은 해석 주의점이 적용된다.

같이 보기

각주

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 Laurens van der Maaten, Geoffrey Hinton, 〈Visualizing Data using t-SNE〉, Journal of Machine Learning Research 9, 2579~2605, 2008. JMLR
↑ Geoffrey Hinton, Sam Roweis, 〈Stochastic Neighbor Embedding〉, NIPS 2002. NeurIPS
↑ Laurens van der Maaten, 〈Accelerating t-SNE using Tree-Based Algorithms〉, Journal of Machine Learning Research 15, 3221~3245, 2014. JMLR
↑ George C. Linderman 외, 〈Fast interpolation-based t-SNE for improved visualization of single-cell RNA-seq data〉, Nature Methods 16, 243~245, 2019. doi:10.1038/s41592-018-0308-4
↑ ^5.0 ^5.1 ^5.2 scikit-learn 1.9 문서, sklearn.manifold.TSNE
↑ ^6.0 ^6.1 Martin Wattenberg, Fernanda Viégas, Ian Johnson, 〈How to Use t-SNE Effectively〉, Distill, 2016. doi:10.23915/distill.00002
↑ ^7.0 ^7.1 Leland McInnes, John Healy, James Melville, 〈UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction〉, 2018. arXiv:1802.03426
↑ umap-learn 문서, Basic UMAP Parameters
↑ Dmitry Kobak, George C. Linderman, 〈Initialization is critical for preserving global data structure in both t-SNE and UMAP〉, Nature Biotechnology 39, 156~157, 2021. doi:10.1038/s41587-020-00809-z

참고 문헌

[tsne-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 Laurens van der Maaten, Geoffrey Hinton, 〈Visualizing Data using t-SNE〉, Journal of Machine Learning Research 9, 2579~2605, 2008. JMLR

[sne-2] Geoffrey Hinton, Sam Roweis, 〈Stochastic Neighbor Embedding〉, NIPS 2002. NeurIPS

[bhtsne-3] Laurens van der Maaten, 〈Accelerating t-SNE using Tree-Based Algorithms〉, Journal of Machine Learning Research 15, 3221~3245, 2014. JMLR

[fitsne-4] George C. Linderman 외, 〈Fast interpolation-based t-SNE for improved visualization of single-cell RNA-seq data〉, Nature Methods 16, 243~245, 2019. doi:10.1038/s41592-018-0308-4

[sktsne-5] 5.0 ^5.1 ^5.2 scikit-learn 1.9 문서, sklearn.manifold.TSNE

[distill-6] 6.0 ^6.1 Martin Wattenberg, Fernanda Viégas, Ian Johnson, 〈How to Use t-SNE Effectively〉, Distill, 2016. doi:10.23915/distill.00002

[umap-7] 7.0 ^7.1 Leland McInnes, John Healy, James Melville, 〈UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction〉, 2018. arXiv:1802.03426

[umapdoc-8] umap-learn 문서, Basic UMAP Parameters

[kobak-9] Dmitry Kobak, George C. Linderman, 〈Initialization is critical for preserving global data structure in both t-SNE and UMAP〉, Nature Biotechnology 39, 156~157, 2021. doi:10.1038/s41587-020-00809-z

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]