Dimension Reduction - t-SNE (2)

Dimension Reduction - t-SNE (1)

---

t-SNE 는 고차원 데이터를 효율적으로 저차원으로 매핑하는 차원축소 방법으로 머신러닝의 다양한 분야에서 2/3 차원으로 데이터를 시각화할 떄 많이 사용하는 방법입니다. Scikit-learn 에도 구현되어 있어 쉽게 사용할 수 있습니다만, t-SNE 를 훈련시킬 때의 파라미터와 데이터 구조에 따라 그 결과가 데이터 분석 상의 잘못된 오해를 불러일으킬 수 있습니다. 

특히, t-SNE 에는 데이터의 지역적 (local) / 전역적 (global) 구조를 고려하는 "perplexity" 라는 파라미터가 있습니다. Perplexity 는 $2^{entropy}$로 정의되는 파라미터로 분포가 uniform 분포에 가까워 불확실해 entropy가 높다면 perplexity가 높아지게 됩니다. t-SNE 에서는 각 데이터 $x_i$마다 이웃과의 거리 분포를 정의하는 $\sigma_i$를 파라미터로 주어진 perplexity 값에 따라 이진탐색을 통하여 각각 다른 값을 사용합니다.

Perplexity 가 작을수록 $p_i$ 분포로 정의되는 엔트로피가 낮아야 되기 때문에 $\sigma_i$가 작아집니다. 즉, 가장 가까운 점들의 확률은 높아지는 대신 나머지 점들의 확률은 매우 낮아지게 됩니다. 따라서 작은 $\sigma$는 지역적인 구조를 강조합니다. 반대로 큰 $\sigma$는 전역적인 구조를 강조하여 모든 점들이 가질 수 있는 확률값을 비슷하게 만듭니다. 이러한 방식으로 t-SNE 는 지역 / 전역적인 구조를 모두 고려하게 되는데 실제로는 시간 복잡도를 줄이기 위해 Barnes-hut tree 알고리즘을 사용하기도 하고 ($O(n^2) \rightarrow O(nlogn)$) 매우 작은 $p_{ij}$는 고려하지 않습니다. 실질적으로 locality 만 적용하게 되는 셈인데 그것을 어떠한 값으로 딱 정하는 것이 아닌 확률적으로 정하는 것이죠. (soft-boundary)

결과적으로 주어진 perplexity 에 따라 각 데이터 별로 주어진 perplexity 를 만족하기 위한 $\sigma$가 개별적으로 정해지고 원 데이터의 거리 분포에 상관없이 비슷한 모양의 $p_{ij}$를 만들게 됩니다. 이번 포스트에서는 perplexity 에 따라 t-SNE의 결과가 어떻게 달라지는지 살펴보도록 하겠습니다.

Perplexity

Scikit-learn 에 구현된 t-SNE 와 저자인 Matten & Hitton 또한 perplexity 를 5에서 50까지의 값을 추천합니다. Figure 1과 같이 perplexity 에 따른 t-SNE의 결과는 매우 상이한데요. Perplexity가 100으로 매우 높은 경우 데이터셋의 모든 점을 거의 균일하게 취급하게 때문에 원래의 군집 구조가 오히려 무너진 것을 볼 수 있습니다.

Figure 1

Cluster size

두 개의 cluster 사이즈가 다를 경우는 어떨까요? (원 데이터를 생성할 때 표준오차의 크기를 다르게 합니다.) Figure 2를 보면 t-SNE 상에서는 군집의 크기가 상대적으로 매우 비슷해진 것을 볼 수 있습니다. 이는 t-SNE가 각 데이터 별로 perplexity를 만족하기 위한 $\sigma$를 개별적으로 구하므로 원 데이터상의 밀집된 구조는 상대적으로 확장하고 희박한 (sparse) 구조는 줄이는 효과를 가지게됩니다. 따라서 t-SNE 결과만으로 군집이 되었다 하더라도 그 군집의 크기를 판단할 수 없다는 것이죠.

Figure 2

Distance between clusters

여러 개의 군집이 있을 때 군집 간의 거리가 다르다면 어떻게 될까요? Figure 3에서 perplexity 50일 때를 보면 원 데이터의 구조를 잘 유지하고 있는 것처럼 보입니다. 그렇다면 perplexity 50이 항상 정답일까요? Figure 4에서는 Figure 3과 달리 군집의 밀도를 조금 더 높인 이후의 결과입니다. 군집의 밀도를 높이니 주어진 perplexity 안에서는 원 데이터의 구조를 잘 유지하지 않습니다.

Figure 3

Figure 4

결과적으로 특정한 최적의 perplexity 값을 존재하지 않습니다. 데이터 마다 여러 개의 군집이 각기 다른 밀도로 존재하므로 perplexity 값을 조절하는 fine-tuning 이 필수적으로 필요하게 됩니다. 또한 t-SNE 결과 상에서의 군집 간의 거리는 아무것도 의미하지 않습니다.

Random noise

100차원의 표준정규분포에서 500개의 데이터를 샘플링한 이후에 t-SNE를 적용하면 놀랍게도 perplexity 에 따라 어떠한 군집을 형성할 떄도 있습니다. Figure 5의 perplexity 2인 경우를 보면 애매한 모양의 군집이 형성된 것을 볼 수가 있죠. 하지만 우리는 원 데이터가 랜덤한 것을 알기 때문에 이러한 군집이 전혀 의미가 없다는 것을 알고 있습니다.

Figure 5

Some shape

물론 t-SNE 결과의 모양이 항상 의마가 없는 것은 아닙니다. Figure 6을 보면 특정한 perplexity 범위에서 원 데이터의 구조를 잘 유지하는 것을 볼 수 있습니다. 이때 각 라인의 끝자락이 살짝 휘어진 것을 볼 수 있는데 t-SNE 의 군집된 부분을 확장하는 알고리즘 성향때문인 것으로 추측됩니다.

Figure 6

 

Conclusion

따라서 t-SNE를 통해 데이터의 구조를 파악하기 위해서는 다양한 perplexity 에 대한 plotting 이 필수적입니다. Figure 7은 같은 중심을 가지고 표준오차가 다른 두 개의 분포를 가진 원 데이터에 대해 t-SNE 를 적용한 결과입니다. Perplexity 30을 보면 원 데이터의 구조를 (topology) 어느 정도 잘 유지하는 것을 볼 수 있으나 원 데이터의 파란색 점을 지나치게 확장한 모습을 보입니다. Perplexity 가 커질수록 원 데이터의 구조를 유지하나 주황색 데이터가 원의 형태를 그리는 것을 볼 수 있습니다. 이는 perplexity 가 커지다보니 각 주황색 점들이 안쪽 파란색 점들과 같은 거리 정보를 가지는 것을 표현하도록 동작하기 때문입니다. 따라서 이러한 경우에는 t-SNE 결과가 원 데이터의 구조를 왜곡한 것으로 볼 수 있겟죠. 

Figure 7

그래도 다행인 점은 LLE (Local Linear Embedding), ISOMAP 등과 같은 다른 시각화 알고리즘에 비해 t-SNE 가 그나마 이러한 파라미터에 더 robust 하다는 점입니다. 하지만 지금까지 살펴봤듯이 perplexity 와 원 데이터 구조에 따라 결과가 매우 상이하기 때문에 다양한 경우에 대해 조정하는 과정을 거쳐야 합니다.

일바적으로 데이터의 수가 적으면 perplexity 를 낮게, 수가 많을수록 perlexity 를 크게 잡습니다. 예를 들어 데이터의 수가 적은 대신에 perplexity 가 크다면 적은 데이터를 기반으로 perplexity 를 맞추기 위해 $\sigma$ 가 과하게 커지는 경향이 있어 원래의 군집 구조가 사라질 수 있기 때문입니다. 또한, bag-of-words 와 같이 sparse vector 에 대해 계산할 때에는 일반적인 euclidean 거리 대신 cosine 거리를 사용할 수 있습니다 (metric='cosine')

 

참조

• https://distill.pub/2016/misread-tsne/#perplexity=10&epsilon=5&demo=13&demoParams=50
• https://lovit.github.io/nlp/representation/2018/09/28/tsne/