Technical NotebookDDangchani's DataLog

Machine Learning

t-Stochastic Neighbor Embedding

t-distributed Stochastic Neighbor Embedding Stochastic Neighbor Embedding Stochastic Neighbor Embedding이란 고차원 공간에서 각 데이터들의 유사성(similarity)을 조건부 확률로 나타내는 차원축소 내지 클러스터링 기법을 의미한다. 가까운 데이터들에 대해서 조건부 확률을 크게 설정한다. 이를 수식으로 다...

2023. 7. 28.3 min read

t-distributed Stochastic Neighbor Embedding

Stochastic Neighbor Embedding

Stochastic Neighbor Embedding이란 고차원 공간에서 각 데이터들의 유사성(similarity)을 조건부 확률로 나타내는 차원축소 내지 클러스터링 기법을 의미한다. 가까운 데이터들에 대해서 조건부 확률을 크게 설정한다. 이를 수식으로 다음과 같이 정의하는데, 이 과정에서 정규분포를 이용한다.

pj∣i=exp⁡(−∥xi−xj∥2/2σi2)∑k≠iexp⁡(−∥xi−xk∥2/2σi2) p_{j\vert i} = \frac{\exp(-\Vert x_{i}-x_{j}\Vert^2/2\sigma_{i}^{2})}{\sum_{k\neq i}\exp(-\Vert x_{i}-x_{k}\Vert^{2}/2\sigma_{i}^{2})}

이때 variance σi2\sigma_{i}^{2}는 데이터 xix_{i} 를 중심으로 하는 정규분포의 분산을 의미한다. 반면, 앞선 고차원 데이터 xi,xjx_i,x_{j}를 저차원으로 매핑한 데이터 yi,yjy_i,y_j 에 대해서도 다음과 같이 유사성 측도를 정의할 수 있다.

qj∣i=exp⁡(−∥yi−yj∥2)∑k≠iexp⁡(−∥yi−yk∥2) q_{j\vert i} = \frac{\exp(-\Vert y_{i}-y_{j}\Vert^2)}{\sum_{k\neq i}\exp(-\Vert y_{i}-y_{k}\Vert^{2})}

만일 저차원 매핑 데이터 yi,yjy_i,y_j가 고차원에서의 유사성을 완벽하게 재현한다면, 두 조건부 확률 pj∣i,qj∣ip_{j\vert i},q_{j\vert i} 의 값이 동일할 것이다. 즉, 이로부터 차원 축소가 잘 이루어진 yi,yjy_i,y_j 는 두 조건부확률분포의 차이를 최소화한다는 아이디어를 얻을 수 있고, 확률분포의 차이를 다음과 같이 Kullback-Leibler divergence로 나타내면 다음과 같은 비용함수(cost function)를 얻을 수 있다.

C=∑iKL(Pi∥Qi)=∑i∑jpj∣ilog⁡pj∣iqj∣i C=\sum_{i}KL(P_{i}\Vert Q_{i})=\sum_{i}\sum_{j}p_{j\vert i}\log\frac{p_{j\vert i}}{q_{j\vert i}}

이 비용함수를 최소화하기 위해서 일반적으로 gradient descent 알고리즘을 사용하게 된다.

t-distributed Stochastic Neighbor Embedding

Symmetric SNE

KL divergence를 앞서 정의한 것처럼 조건부 확률분포들에 대해서 최소화할 수 있지만, 결합확률분포에 대해서도 최소화하는 방법을 생각할 수 있다. 이 경우 저차원 공간(yi,yjy_i,y_j에 대해)에서 비용함수는 다음과 같이 주어진다.

C=KL(P∥Q)=∑i∑jpijlog⁡pijqij C=KL(P\Vert Q)=\sum_i\sum_{j} p_{ij}\log\frac{p_{ij}}{q_{ij}}

이때 joint distribution에 대해서는 pij=pji,qij=qjip_{ij}=p_{ji}, q_{ij}=q_{ji} 가 성립하기 때문에, 이러한 SNE를 symmetric SNE 라고 정의한다. 또한, 저차원 공간에서의 유사성 측도 qijq_{ij}는 다음과 같이 주어지고

qij=exp⁡(−∥yi−yj∥2)∑k≠lexp⁡(−∥yk−yl∥2) q_{ij} = \frac{\exp(-\Vert y_{i}-y_{j}\Vert^2)}{\sum_{k\neq l}\exp(-\Vert y_{k}-y_{l}\Vert^{2})}

고차원 데이터 공간에서의 측도는

pij=exp⁡(−∥xi−xj∥2/2σ2)∑k≠lexp⁡(−∥xk−xl∥2/2σ2) p_{ij} = \frac{\exp(-\Vert x_{i}-x_{j}\Vert^2/2\sigma^{2})}{\sum_{k\neq l}\exp(-\Vert x_{k}-x_{l}\Vert^{2}/2\sigma^{2})}

으로 주어진다. 그런데, 이 경우 고차원 공간에서 어떤 데이터 xix_i 가 이상치인 경우 문제가 발생하게 된다. ii번째 데이터가 이상치인 경우 pijp_{ij}가 모든 jj에 대해 극단적으로 작아지는 문제가 발생하기 때문이다. 따라서 이를 극복하기 위해 symmetrized conditional probability를 다음과 같이 정의한다.

pij=pj∣i+pi∣j2n p_{ij}=\frac{p_{j\vert i}+p_{i\vert j}}{2n}

Crowding Problem

일반적인 SNE, symmetric SNE는 Crowding problem이라고 하는 문제가 발생한다. 일반적으로 시각화 과정은 2차원 평면에 이루어지므로, 우선 주어진 고차원 데이터 X⊂Rd\mathbf{X}\subset\mathbb{R}^d 가 2차원 manifold M\mathcal{M} 위에 나타난다고 가정하자. 이러한 경우를 M\mathcal{M} 이 Rd\mathbb{R}^d 에 embedding 되어있다고 한다(manifold embedded in high dimensional space). 그런데, 만일 M\mathcal{M} 이 높은 차원의 intrinsic dimension을 가진다면 문제가 발생하게 된다. 여기서 intrinsic dimension이란, 데이터를 표현하기 위한 최소한의 변수의 수(차원)를 의미한다. 예를 들어 ten-intrinsic dimensional manifold라면, 11개의 서로 다른 data point xi,i=1,…,11x_{i}, i=1,\ldots,11 이 있고 각각의 거리가 모두 같을 때(equidistant: ∥xi−xj∥\Vert x_{i}-x_{j}\Vert가 모두 동일할 때), 이들을 2차원 manifold에 매핑하는 것은 불가능하다. 직관적인 예제가 있어 이 글을 참고하면 좋을 것 같다.

t-SNE

t-SNE는 앞서 말한 Crowding Problem을 극복하기 위해 저차원 공간에서 유사성 측도를 heavy-tailed distribution으로 사용한다. Student t-distribution을 사용하며(cauchy distribution이기도 함), 다음과 같다.

qij=(1+∥yi−yj∥2)−1∑k≠l(1+∥yk−yl∥2)−1 q_{ij}=\frac{(1+\Vert y_{i}-y_{j}\Vert^{2})^{-1}}{\sum_{k\neq l}(1+\Vert y_{k}-y_{l}\Vert^2)^{-1}}

Cost function의 그래디언트는 다음과 같이 계산된다.

∂C∂yi=4∑j(pij−qij)(yi−yj)(1+∥yi−yj∥2)−1 \frac{\partial C}{\partial y_i}=4\sum_{j}(p_{ij}-q_{ij})(y_{i}-y_{j})(1+\Vert y_{i}-y_{j}\Vert^{2})^{-1}

Perplexity

SNE에는 cost-function parameter(tuning parameter)로 사용하는 perplexity가 존재하는데, 다음과 같이 정의된다(HH는 Shannon entropy).

Perp(Pi):=2H(Pi)H(Pi)=−∑jpj∣ilog⁡2pj∣i \begin{aligned} &\textrm{Perp}(P_{i}):=2^{H(P_{i})} \\ &H(P_{i})=-\sum_{j}p_{j\vert i}\log_{2}p_{j\vert i} \end{aligned}

SNE 수행 과정에서 고차원 결합확률분포의 분산은 주어지는 것이 아니라 최적의 값으로 계산되는데, 이때 위와 같이 정의되는 perplexity가 smooth measure of the effective number of neighbors, 즉 적합한 σ2\sigma^{2} 값을 찾기 위한 탐색 과정에서의 parameter로서 작동한다.

Example. MNIST Data

Sklearn 패키지에는 TSNE 모듈로 t-SNE를 간단하게 실행할 수 있게 되어있다. 이를 이용해 MNIST 데이터를 2차원 평면에 매핑한 결과 다음과 같다.

  • 코드
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns

# MNIST dataset
from tensorflow.keras.datasets import mnist

# Load Data
from tensorflow.keras.datasets import mnist
(X_train, y_train), (X_test, y_test) = mnist.load_data()

# Select a subset of the data
target_indices = []
for i in range(10):
    target_indices.extend(np.where(y_train == i)[0][:1000])
X_train = X_train[target_indices]
y_train = y_train[target_indices]

# Flatten X
X_train = X_train.reshape(X_train.shape[0], -1)

from sklearn.manifold import TSNE

# tSNE
tSNE = TSNE(n_components=2, perplexity=30, random_state=0)
tSNE.fit_transform(X_train)

# Plot with legend
df = pd.DataFrame()
df['x'] = tSNE.embedding_[:,0]
df['y'] = tSNE.embedding_[:,1]
df['label'] = y_train

plt.figure(figsize=(10,10))
for i in range(10):
    plt.scatter(df[df['label']==i]['x'], df[df['label']==i]['y'], label=i)
plt.legend(fontsize = 12)
plt.title('tSNE with MNIST', fontsize=30)
plt.tight_layout()
plt.savefig('tSNE.png', facecolor='white')

References

  • van der Maaten et al. - Visualizing Data using t-SNE (2008)