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

技術要約：アフィニティ行列の平滑化がt-SNEの近傍保存に与える影響

問題提起
t-分布型確率的近傍埋め込み（t-SNE）は、局所的な近傍構造を保存することで知られる広く用いられている次元削減手法である。しかし、その普及にもかかわらず、t-SNEの埋め込みは絶対的な近傍保存スコアが低くなることが多く、誤差も不均一に分布する傾向がある。これまでの研究の多くは、t-SNEのグローバルな構造保存の改善や、最適化プロセス（初期化、学習率など）の最適化に焦点を当ててきたが、高次元のアフィニティ行列自体を修正することによって、t-SNEの局所的な構造保存を改善できるかという点についての明示的な調査はほとんど行われてこなかった。

著者らは、標準的なt-SNEにおいて、条件付き確率分布（アフィニティの行）が非常に「鋭い（sharp）」、つまり少数の近傍が確率質量を支配していることが多いことを指摘している。さらに、これらの分布の鋭さはデータポイントごとに異なっている。本論文では、このアフィニティ分布の「鋭さ」が異なるスケールにおける近傍保存にどのように影響するか、また、この鋭さを修正することが標準的なt-SNEや代替のマルチスケール手法よりも優れた埋め込みをもたらすかどうかを調査している。

手法
本研究では、標準的なt-SNEのアフィニティ構築に対して、制御された摂動として、条件付き確率 $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$) を再スケーリングすることと数学的に等価であることを証明している。具体的には、新しい実効帯域幅は $\tilde{\sigma}_i = \sigma_i / \sqrt{\gamma}$ となる。
   • 決定的な点として、グローバルなパープレキシティ・パラメータ $\rho$ を変更する場合（これはすべての点に対して同じ実効的な近傍数を強制する）とは異なり、固定された $\gamma$ を適用すると、点依存の実効パープレキシティが生じる。実効パープレキシティは、各点における元の分布の形状に基づいて変化する。

3. 実験設定:

   • 本手法は openTSNE 内に実装され、MNIST、UCI Adult、および Mouse Cortex データセットを用いて評価された。
   • 評価の主要な指標は、高次元の $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$ による平滑化は、「ミドル・ローカル」の範囲（$k \approx 25–90$）において標準的なt-SNEやマルチスケール手法を上回った。
  • 平滑化は、高いパープレキシティにおける距離のSpearmanランク相関によって測定されるグローバルな構造保存も改善した。
• グローバル・パープレキシティ調整との比較: 標準的なt-SNEにおいてグローバルなパープレキシティ $\rho$ を単に増やすだけでは、平滑化による恩恵を再現することはできない。平滑化は、各点に対して不均一な実効近傍サイズの分布を生み出すが、$\rho$ を上げることはすべての点に対して一様にスケールをシフトさせる。その結果、平滑化されたt-SNEは、一致またはより高いパープレキシティを持つ標準的なt-SNEよりも、特定のミドルレンジの $k$ 値において高いNO@kスコアを達成した。
• 他手法との比較: ミドル・ローカルの範囲において、平滑化されたバリアント（$\gamma=0.7$）は、複数の帯域幅スケールを取り入れた Multiscale Mixture および Multiscale 手法よりも優れた性能を示した。鋭利化されたバリアント（$\gamma=1.5$）は非常に小さな $k$ で優位となり、一様分布（$\gamma=0$）は非常に大きな $k$ で優位となった。

意義と主張
本論文は、**アフィニティの鋭さ（affinity sharpness）**が、t-SNEの挙動における意味のある、かつこれまで十分に探求されてこなかった軸であることを主張している。主な貢献は以下の通りである：

1. 近傍サイズと分布の分離: 本研究は、近傍の数（パープレキシティによって制御される）と、それらの間の確率質量の分布（$\gamma$ によって制御される）が、異なる要因であることを示している。
2. 軽量なチューニング: パラメータ $\gamma$ は、実践者が埋め込みの焦点をシフトさせるための、シンプルで軽量なメカニズムを提供する：
   • 極めて近い近傍に対する高い忠実度を目的とする場合は、鋭いアフィニティ（$\gamma > 1$）を使用する。
   • より広い局所構造やグローバルなトポロジーの保存を改善することを目的とする場合は、滑らかなアフィニティ（$\gamma < 1$）を使用する。
3. 限界: 著者らは、改善は一貫しているものの、絶対的な観点からは控えめなものであると謙虚に述べている。本研究は単一の品質指標（NO@k）に焦点を当てており、これらの指標の改善が特定のドメインの洞察にどのように具体的に変換されるかは、依然として未解決の課題である。また、特定の $k$ 値に対する最適なハイパーパラメータ（$\rho, \gamma$）の網羅的な最適化は、本研究では行われていない。

結論として、本論文は、標準的なt-SNEは確率質量を最初の数個の近傍に集中させすぎる傾向があり、それがより広い局所構造を保存する能力を制限している可能性があると論じている。アフィニティ行列を平滑化することで、この質量を中位のランクの近傍へと再分配することができ、最適化プロセスや計算のスケーラビリティを変更することなく、クラスターのサブ構造やグローバルなレイアウトの信頼性を高めることができる。