kntty.hateblo.jp

ここに何か書く。

UMAPの仕組み ── 低次元化の理屈を理解してみる

1. はじめに

  • 非線形の高次元データを低次元化して可視化する道具として、t-SNEに代わってUMAPが主流になってきている。
    • McInnes L, Healy J, Melville J. UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction. 2018.
  • UMAPの仕組みを論文から理解するには数学脳不足で挫折していたが、先人達の解説記事のお蔭でやっと直感的な理解できた気がするので、ここにまとめたい。
  • t-SNEと比べた説明もしているので、t-SNEを把握しているとより理解が早いかも。
  • あくまで直感的、厳密な説明でないことをご容赦いただきたい。

(2021.3.26追記:コメントで指摘を頂いた、表の間違いを修正。)
(2021.7.3追記:近さ曲線の図を修正。)

2. 次元削減の方針

UMAPでやろうとしている大きな方針は、

  • 高次元で「近い」点同士を、低次元上でも「近く」に配置したい

である。手順を大雑把に書くと、次のように表せる。

  • Step 1. 高次元における、全ての2点の組合せに対しての「近さ$v _ {ij}$」を、数値化する。
  • Step 2. 低次元における、全ての2点の組合せに対しての「近さ$w _ {ij}$」を、数値化する。
    近さの組$(w _ {ij})$と$(v _ {ij})$とが整合するように、点配置(マッピング先)を繰り返し更新する。

ここで「近さ」は、点付近の密度に応じた値としている。つまり、点が密集する周辺では距離を厳しく、点が疎なところでは距離を緩く評価する。 (非線形データに対応するため。)

実は、ここまで書いた方針は、従来のt-SNEとほとんど同じである。考え方としては、近さの定義と、2つの「全ペアの近さ」の比べ方、その2点が違うだけ、と解釈できる。

  • UMAPでは、近さを「近傍に属する強さ」、近さの組をファジー集合と見なして、ファジー集合の塊同士を交差エントロピーで比べる(この辺の言葉が難しい...)。
  • t-SNEでは、近さを確率と見なして、総和が1となる近さの組をKL情報量で比べる。

f:id:kntty:20201230171903p:plain
UMAPとt-SNEの考え方

ちなみに、「近さ」に距離そのものを使わない理由としては、

  • 非線形に対応するため
  • Crowding Problemに対応するため(後日の記事で追記済み)

が挙げられる。

3. 高次元における近さの定義

高次元側の具体的な「近さ」を、次の流れで定義する。

  • 高次元のある点$\bm x _ i$に対して、他の点$\bm x _ j$の近さ$v _ {j|i}$を考える。非対称($v _ {j|i} \neq v _ {i|j}$)であることに注意。
  • $v _ {j|i}$と$v _ {i|j}$から、対称化した近さ$v _ {ij}$を得る。

(ちなみに、参照先に倣って、縦棒|表記を、非対称であることを示すために使っている。)

3.1. 準備

点$\bm x _ i$に対して、$k$近傍の集合(すなわち、$k$番目に距離の小さい点までを集めた集合)を、$K _ i$と表すことにする。 (ただし、正の整数 $k$はパラメータとして与える。)

このとき、他のある点$\bm x _ j$が集合$K _ i$に属すか否かは、$\{0,1\}$の2値で表現可能である。

UMAPでは、この2値を、0以上1以下の実数に拡張した、ファジー集合(fuzzy set)として扱う。つまり、要素が集合に属すか否かを、実数で曖昧に表そう、ということである。

  • なお、厳密には、「fuzzy simplicial set」らしい。この辺の理論はちゃんと理解していない。

これらをイメージするなら、次の図の(a)と(b)のような近傍グラフとなる(ちなみに、後ほど、(c)のように対称化することになる)。

f:id:kntty:20201230154257p:plain
近傍グラフによるイメージ

3.2. 定義

さて、「点$\bm x _ i$の近傍」という集合に、他の点$\bm x _ j (j\neq i)$が属する強さ(近さ)を$v _ {j|i}$で表し、UMAPでは次のように定義する。

v_{j|i} = \exp\left(\frac{-(r_{ij} - ρ_i)}{σ_i}\right) \quad (\bm x_j \in K_i) \quad ...(1)

ここで、

  • $r _ {ij}$: 点$\bm x _ i$と$\bm x _ j$の(通常の意味での)距離。一般にはユークリッド距離。
  • $ρ _ i$ : 最近傍との距離。$ρ _ i = \min _ {j\in K _ i}\{r _ {ij}\}$
  • $σ _ i$ : 点の疎密に対応するための割り算。後述。

なお、k近傍に含まれていなければ、

v _ {j|i} = 0 \qquad (x _ j \notin K _ i)

と考える。

式(1)において、$σ _ i$は、点が密集しているところでは小さく(狭く)、疎なところでは大きく(広く)設定したい変数である。
この$σ _ i$は、$\sum _ j v _ {j|i} = \log _ 2 k$となるように、二部探索で決められる。 ($\log _ 2 k$は経験的に定められたものらしい。)

また、$ρ _ i$が特徴的で、これによって、$\bm x _ i$の最近傍な点との近さは、必ず 1 となる。

f:id:kntty:20210703223820p:plain
高次元の近さ曲線

3.3. 対称化

近さが非対称だと計算が煩雑になるので、対称化して定義し直す。

(集合における和集合を、fuzzyに考えて得られたものと思われる。)

v _ {ij} = (v _ {j|i} + v _ {i|j}) - v _ {j|i}v _ {i|j}
  • 数式をよく眺めてみると、少なくとも一方から見て最近傍であれば、対称化しようが必ず$v _ {ij} = 1$である。なかなかの最近傍重視。

4. 低次元における近さの定義

低次元の点$\bm y _ i$に対しても、同様の当てはめを試みる。ただし、

  • 高次元の$σ$に当たる値は、一定値(=1)としたい(疎密の度合を均一化)。
  • 高次元の$ρ$に当たる値は、最近傍を表す近さであるため、これも一定の値を与えたい。

ということを考慮に入れると、次のような式が出来上がる。

w _ {j|i} = \exp\left({-\max\{0,d _ {ij} - ρ'\}}\right) = \tilde w _ {ij}

この時点で、既に$i$と$j$に関する対称性を満たしていることに注意。 $ρ'$は、パラメータmin_distに対応する。

実装上は、これを更に、t-分布ライクな分布関数で近似している。

w _ {ij} = \frac{1}{1 + a \cdot d _ {ij}^{2\cdot b} }

$a, b$には、 $w_{ij}$を$\tilde w _ {ij}$にフィッティングして得られた固定値を使う。

f:id:kntty:20201230153700p:plain
低次元の近さ曲線フィッティング([4] How UMAP Exactly Works より図を引用)

  • t-分布ライクになっているのは、t-SNEの恩恵を預かることを意識していそう。
  • なお、デフォルトのmin_distの設定値の場合、$a\simeq 1.929, b\simeq 0.7915$程になるらしい。

5.最適化

高次元での近さの組$(v _ {ij})$と、低次元での近さの組$(w _ {ij})$が、数値化できるようになった。

あとは、対応する近さが一致するように、低次元の点を配置していけば良い。

UMAPのコスト関数は、2つのfuzzy setに対する交差エントロピーで定義する。すなわち、

L = \sum_{i,j}\left[v_{ij}\log\frac{v_{ij}}{w_{ij}} +     (1-v_{ij})\log\frac{1-v_{ij}}{1-w_{ij}}\right]

確率的勾配法(SGD)で$\bm y _ i$を更新するために、$L$を微分すると、 第1項と第2項が、それぞれ引力と斥力になって現れる。

\frac{∂L^+}{∂\bm{y}_i} = \frac{∂L^+}{∂d^2}\frac{∂d^2}{∂\bm{y}_i} = \underbrace{ \frac{-2abd_{ij}^{2(b-1)}}{1+ad_{ij}^{2b}} }_{f^+}     v_{ij} (\bm{y}_i - \bm{y}_j) = v_{ij} f^+ (\bm y_i - \bm y_j)
\frac{∂L^-}{∂\bm{y}_i} = \frac{∂L^-}{∂d^2}\frac{∂d^2}{∂\bm{y}_i} = \underbrace{ \frac{2b}{(ε+ad_{ij})(1+ad_{ij})} }_{f^-}     (1 - v_{ij}) (\bm{y}_i - \bm{y}_j)

となる。

ここで更に、実装を簡単にするために、サンプリングを導入する。

SGDの更新の時に、全ての近傍点に対して重み付けして毎回更新するのと、重みに基づく割合でサンプリングした点だけを定数倍で更新するのとで、(反復を増やせば) 同じ意味になることを利用する。

結局、UMAPは、次の繰り返しで$(\bm y _ i)$の配置を更新することで、次元削減を実現している手法、ということになる。

  • k近傍の点を$v _ {ij}$に重み付けされた割合でサンプリングして、$f ^ +$に基づいて$\bm y _ i$と$\bm y _ j$を引っ張る。
  • 全ての点に対して、一様サンプリングでランダムに点を拾ってきて、$f ^ -$に基づいて$\bm y _ i$と$\bm y _ j$を引き離す。
    (本来は$1 - v _ {ij}$で重み付けすべきはずだが、ほどんどの点で$1 - v _ {ij} = 1$になることから、強引に1と見なしているようである。)

6. t-SNEとの相違

次の表のようにまとめられる。

f:id:kntty:20210326233840p:plain
UMAPとt-SNEの関係

影響が大きい点は、次の2点。

a. 正規化不要 → 計算コスト削減

  • t-SNEでは、近さを確率と見なすために正規化を要するため、1組の近さを計算するのに、常に$N-1$ のペアに対する計算操作が必要となる。 
  • UMAPでは、$k (\ll N)$ のペアに対する計算だけで済む。

特に、低次元側は、反復の度に近さを数値化し直す必要があるため、正規化不要なUMAPに計算量の大きなアドバンテージがある。 (特に$N$が大きい場合。厳密には、t-SNEでも重複計算を削るとか、多少工夫できるとはいえ、なお差は大きいと思う。)

b. Laplacian Eigenmapによる初期化 → 結果の安定化

  • UMAPでは、Laplacian Eigenmap($k$近傍グラフを行列で表して主成分分析しているようなもの?)を使って、$\bm y _ i$の初期配置を、決定的に決めている。
  • t-SNEの非決定的なランダム配置で初期化するよりも、結果が安定しやすいようである。

参考

解説記事様々。大変に参考になりました。