How smoothing the affinity matrix affects neighborhood preservation in t-SNE

기술 요약: 어피니티 행렬(Affinity Matrix)의 평활화가 t-SNE의 이웃 보존에 미치는 영향

문제 정의
t-분포 기반 확률적 근접 이웃 임베딩(t-SNE)은 국소적 이웃 구조를 보존하는 것으로 알려진 널리 사용되는 차원 축소 기법이다. 그러나 그 인기에도 불구하고, t-SNE 임베딩은 종종 낮은 절대적 이웃 보존 점수를 보이며, 오류가 불균일하게 분포되는 경우가 빈번하다. 많은 연구가 t-SNE의 전역 구조 보존을 개선하거나 최적화 과정(예: 초기화, 학습률)을 최적화하는 데 집중해 왔으나, **국소 구조 보존(local structure preservation)**을 개선하기 위해 고차원 어피니티 행렬 자체를 수정하는 것에 대한 명시적인 조사는 제한적이었다.

저자들은 표준 t-SNE에서 조건부 확률 분포(어피니티 행/row)가 매우 "날카로운(sharp)" 경향이 있으며, 즉 소수의 최근접 이웃이 확률 질량(probability mass)을 지배한다는 점을 관찰했다. 또한 이러한 분포의 날카로움은 데이터 포인트마다 다르게 나타난다. 본 논문은 이러한 어피니티 분포의 "날카로움"이 다양한 스케일에서 이웃 보존에 어떤 영향을 미치는지, 그리고 이 날카로움을 수정하는 것이 표준 t-SNE나 대안적인 멀티스케일 방법보다 더 나은 임베딩을 제공할 수 있는지 조사한다.

방법론
본 연구는 표준 t-SNE의 어피니티 구성에 제어된 섭동(perturbation)을 도입한다: 즉, 조건부 확률 $p_{j|i}$에 적용되는 **행 단위 거듭제곱 변환(row-wise power transform)**이다.

1. 변환식: 주어진 점 $i$에 대하여, 조건부 확률은 다음과 같이 $\gamma \geq 0$ 파라미터를 사용하여 변환된다:
   $$\tilde{p}_{j|i} = \frac{p_{j|i}^\gamma}{\sum_{m \neq i} p_{m|i}^\gamma}$$

   • $\gamma = 1$: 표준 t-SNE를 복구함.
   • $\gamma < 1$ (평활화, Smoothing): 큰 확률을 상대적으로 작은 확률에 비해 감소시켜, 낮은 확률을 가진 이웃으로 질량을 재분배함.
   • $\gamma > 1$ (날카롭게 하기, Sharpening): 가장 큰 확률들에 질량을 더욱 집중시킴.
   • $\gamma = 0$: 이웃들에 대해 균등한 분포를 생성함 (순위 구조를 무시함).

2. 이론적 특성:

   • 저자들은 이 거듭제곱 변환이 원래 커널의 **가우시안 대역폭(Gaussian bandwidth, $\sigma_i$)을 재조정(rescaling)**하는 것과 수학적으로 동일함을 증명한다. 구체적으로, 새로운 유효 대역폭은 $\tilde{\sigma}_i = \sigma_i / \sqrt{\gamma}$가 된다.
   • 결정적으로, 모든 점이 동일한 유효 이웃 수를 갖도록 강제하는 전역 퍼플렉시티(perplexity) 파라미터 $\rho$를 변경하는 것과 달리, 고정된 $\gamma$를 적용하면 **점 의존적인 유효 퍼플렉시티(point-dependent effective perplexities)**가 발생한다. 유효 퍼플렉시티는 각 특정 점의 원래 분포 형태에 따라 달라진다.

3. 실험 설정:

   • 본 방법은 openTSNE 내에 구현되었으며 MNIST, UCI Adult, Mouse Cortex 데이터셋에서 평가되었다.
   • 평가를 위한 주요 지표는 고차원 $k$-최근접 이웃이 임베딩에서 보존되는 비율을 측정하는 **$k$에서의 이웃 중첩도(Neighborhood Overlap at $k$, NO@k)**이다.
   • 표준 t-SNE, 변화하는 전역 퍼플렉시티, 그리고 대안적인 어피니티 구성(Multiscale, Fixed Sigma, Uniform, tt-SNE)과 비교하였다.

주요 결과
실험은 $\gamma$에 의해 제어되는 명확한 스케일 의존적 트레이드오프를 보여준다:

• 날카롭게 하기 ($\gamma > 1$): 매우 가까운 이웃(작은 $k$)의 보존을 개선한다. 그러나 $k$가 증가함에 따라 성능이 급격히 저하된다.
• 평활화 ($\gamma < 1$): 더 넓은 국소 이웃(중간 범위의 $k$) 및 전역 구조의 보존을 개선한다.
  • 특히 $\gamma \approx 0.7$인 평활화는 "중간-국소(mid-local)" 범위($k \approx 25–90$)에서 표준 t-SNE 및 멀티스케일 방법보다 우수한 성능을 보였다.
  • 평활화는 높은 퍼플렉시티에서 전역 구조 보존(거리의 Spearman 순위 상관관계로 측정) 또한 개선하였다.
• 전역 퍼플렉시티 튜닝과의 비교: 표준 t-SNE에서 전역 퍼플렉시티 $\rho$를 단순히 높이는 것은 평활화의 이점을 재현하지 못한다. 평활화는 점들에 대해 이질적인 유효 이웃 크기 분포를 생성하는 반면, $\rho$를 높이는 것은 모든 점에 대해 스케일을 균일하게 이동시킨다. 결과적으로, 평활화된 t-SNE는 일치하거나 더 높은 퍼플렉시티를 가진 표준 t-SNE보다 특정 중간 범위 $k$ 값에서 더 높은 NO@k 점수를 달성했다.
• 타 방법론과의 비교: 중간-국소 범위에서, 여러 대역폭 스케일을 포함하는 Multiscale Mixture 및 Multiscale 방법보다 평활화된 변형 모델($\gamma=0.7$)이 더 우수했다. 날카로운 변형 모델($\gamma=1.5$)은 매우 작은 $k$에서 우위를 점했고, 균등 분포($\gamma=0$)는 매우 큰 $k$에서 우위를 점했다.

의의 및 주장
본 논문은 **어피니티의 날카로움(affinity sharpness)**이 t-SNE 동작의 의미 있고 이전에 탐구되지 않은 축임을 주장한다. 주요 기여는 다음과 같다:

1. 이웃 크기와 분포의 분리: 본 연구는 이웃의 수(퍼플렉시티에 의해 제어됨)와 그들 사이의 확률 질량 분포($\gamma$에 의해 제어됨)가 서로 다른 요소임을 입증한다.
2. 경량 튜닝: $\gamma$ 파라미터는 실무자가 임베딩의 초점을 전환할 수 있는 간단하고 가벼운 메커니즘을 제공한다:
   • 매우 가까운 이웃에 대한 높은 충실도를 목표로 한다면 더 날카로운 어피니티($\gamma > 1$)를 사용한다.
   • 더 넓은 국소 구조와 전역 위상(topology)의 보존을 개선하고자 한다면 더 부드러운 어피니티($\gamma < 1$)를 사용한다.
3. 한계점: 저자들은 개선 사항이 일관되기는 하지만 절대적인 수치 면에서는 완만하다는 점을 겸허히 언급한다. 본 연구는 단일 품질 지표(NO@k)에 집중하고 있으며, 이러한 지표의 개선이 특정 도메인 통찰력으로 어떻게 번역되는지는 여전히 열린 과제로 남아 있다. 또한, 특정 $k$ 값에 대한 최적의 하이퍼파라미터($\rho, \gamma$)가 본 연구에서 완전히 최적화되지는 않았다.

결론적으로, 본 논문은 표준 t-SNE가 확률 질량을 처음 몇 개의 이웃에 너무 과도하게 집중시켜 더 넓은 국소 구조를 보존하는 능력을 제한할 수 있다고 주장한다. 어피티 행렬을 평활화함으로써, 최적화 절차나 계산 확장성을 변경하지 않고도 중간 순위의 이웃들에게 질량을 재분배하여 클러스터의 하위 구조와 전역 레이아웃의 신뢰성을 높일 수 있다.