あなたはUMAPを知っていますか？
わたしは知っています。

聞いたことあるけど知らない人は、この記事でなんとなく理解しましょう。

UMAPとは

t-SNEよりも高速・高性能に次元削減・可視化する手法である。よく使われる t-SNE と比較してみよう。以下の図は Fashion MNIST の可視化である。

t-SNE に比べて、UMAP ではクラスタが明確に分かれているように見える。また似たカテゴリどうしは近くに、似ていないカテゴリどうしは遠くに配置されている。（Understanding UMAPの解説に可視化の例が豊富にあるので詳しくはそちらを見てほしい。上の3Dの図をぐりぐり回して見れるので）

UMAPは埋め込み次元数によらず、実行時間がほとんど一定である。t-SNE のように埋め込み次元が増えても指数関数的に実行時間が増えることはないので、可視化だけでなく次元削減にも使える。また FIt-SNE という t-SNE を C++ で高速に実装したものよりも、Python で書かれた UMAP の方が速い。

そして新規サンプルの埋め込みに対応している。t-SNEの場合、低次元空間に新しいデータを追加するのが難しく、全体を再度実行する必要があった。これに対しUMAPでは差分の計算だけで済み、自然に埋め込むことができる。

ツールとして使いたいだけなら、とてもカンタンだ。 (コードは公式ドキュメントより)

!pip install umap-learn

import numpy as np
from sklearn.datasets import load_digits
import matplotlib.pyplot as plt
import umap

# Digitsで試す
digits = load_digits()

# umapで2次元に削減
reducer = umap.UMAP(random_state=42)
reducer.fit(digits.data)
embedding = reducer.transform(digits.data)

# plot
plt.scatter(embedding[:, 0], embedding[:, 1], c=digits.target, cmap='Spectral', s=5)
plt.gca().set_aspect('equal', 'datalim')
plt.colorbar(boundaries=np.arange(11)-0.5).set_ticks(np.arange(10))
plt.title('UMAP projection of the Digits dataset', fontsize=24);

また非常に高次元で大量のデータに対しても、現実的な時間で実行できる。以下の図は3000万個の整数を素因数分解したバイナリベクトルを入力として可視化したもの。（意味がある可視化かは知らないがイケてる）

これで満足な方はここで終わり。ツールとして便利に使ってください。

既存手法

UMAPの説明に入る前に既存手法をざっと確認しておく。

これまで多くの次元削減手法が提案されてきた。データの持つグローバル構造とローカル構造を保持できることが求められる。そして最近ではある程度の計算速度も求められている。

線形的な手法（PCAなど）

人工データにはうまく機能するが、高次元実データでの性能が低い。Swiss-rollとかうまくいかない。

非線形な手法

UMAPはこちらに属する。

Isomap
LLE
Laplacian Eignmap
t-SNE
LargeVis

中でもt-SNEはグローバル構造もローカル構造もよく保持できる手法として、よく使用されている。ただし実行時間に課題があり、それを解決するために LargeVis などが提案されていた。この記事ではUMAPの工学的な解説を試みるが、Isomapやt-SNEなどをある程度知っていると理解しやすいと思う。既存手法にあげた論文は参考文献にまとめている。

文字の定義

今後のためにいくつか定義しておく。

データ数 $N$
$n$次元　高次元データ集合$X$
- $X = \{x_1, x_2, ..., x_N\}, ; x_i \in \mathbb{R}^n$
$m$次元　低次元データ集合$Y$ ($m << n$)
- $Y = \{y_1, y_2, ..., y_N\}, ; y_i \in \mathbb{R}^m$

以降これらの文字は特に断りなく使用する。

UMAPの工学的理解

まずUMAPの目的を再確認しておこう。

高次元データ$X$を低次元データ$Y$に変換すること。ただし$X$の局所構造と大域構造は保持したまま変換する。

UMAPの論文は数学の知識がないと真に理解することはできない。しかし論文には数学の知識を持たない人のための説明が書かれている。高度な数学に基づいたUMAPだが、実は UMAPはグラフの作成とグラフ上の操作とみなすことができる。これはUMAPがIsomapやt-SNE、LargeVisなどととても近い発想に基づいているからだ。

手法の流れは以下の2ステップである。

重み付きk近傍グラフをつくる
グラフを低次元に配置する

図はLargeVis論文より

ステップ1では、データの局所構造に注目している。そして局所構造に基づいて構築したグラフを、ステップ2で大域構造を表すように配置していく、（というイメージ）。多様体において測地点距離が局所的にはユークリッド距離とみなせるので、近傍ブラフもユークリッド距離を使用するイメージでいい。（実際には距離に限らず、非類似度のようなものでも使用できる。）

順に見ていこう。

1.重み付きk近傍グラフをつくる

①k近傍グラフをつくる

まず重みをつけずに近傍グラフをつくろう。近傍を求めるために距離（metrics）$d$を定義しておく（ユークリッド距離などをイメージするといい）。

そして$x_i$のメトリクス$d$でのk個の近傍を以下のように表記する。
$\{x_{i_1}, ..., x_{i_k}\}$

近傍探索は通常のk近傍法を用いてもいいが、UMAPでは近似手法を用いる。通常のk近傍法では $O(N^2)$ かかってしまうが、近似手法では $O(N^{1.14})$ まで早くなる。詳しくは参考文献近似最近傍探索の最前線を見てほしい。

近傍探索が終わったら、近傍どうしを辺でむずんで k近傍グラフを作成する。つまり辺集合$E$、頂点集合$V$を以下のように定める。

$E = \{(x_i, x_{i_j}) ; | ; 0\leq i \leq N, , 0\leq j \leq k \}$
$V$は、データの各点に対応。

こうして重みなしで有向なk近傍グラフ$G_1$ができた。$G_1=(V, E)$

ちょっとまとめると、
「①k近傍グラフをつくる」では、高次元データ$X$の各$x_i$に対して k個の近傍を探して、重みなし有向k近傍グラフ$G_1$をつくった。

➁重み付きk近傍グラフをつくる

重みをつけるために、まず重み関数$w$を定義する。右辺は$\rho_i$と$\sigma_i$で正規化されている。

$w((x_i, x_{i_j})) = \exp(\dfrac{-\max(0, , d(x_i, x_{i_j})-\rho_i)}{\sigma_i})$

ここで$\rho_i$は最近傍との距離である。
$\rho_i = \min\{d(x_i, x_{i_j}) ; |; 1\leq j \leq k \}$

また$\sigma_i$は以下の式を満たすように二部探索で求める。
$\Sigma_j w((x_i, x_{i_j})) = \log_2 (k)$
右辺の $\log_2(k)$ は経験的に得られたものである。

（この$log_2{k}$ってなんやねんですが、分散を二部探索で求めているため t-SNE の perplexity 的な意味合いだと思う。）

先ほどの重み関数を用いて、有向重みつきグラフ$G_2$を作成する。
$G_2 = (V, E, w)$

しかしこの$G_2$をそのまま使用することはしない。以下の変換によって無向グラフ$G$を作成する。
$A$：$G_2$の隣接行列
$B = A+A^T-A\circ A^T, \circ : アダマール積$

$B$の要素を見てみると、対象化を行っているのがわかる。
$B_{i,l} = w((x_i, x_l)) + w((x_l, x_i)) - w((x_i, x_l))*w((x_l, x_i)) \ = B_{l. i}$

（これはt-SNEでSNEの条件付確率を対称化したのと同様の働きだと思う。コスト関数が扱いやすくなる。）

こうしてできた$B$を隣接行列としてグラフ$G$をつくる。このグラフ$G$をステップ➂で低次元に配置していく。

ちょっとまとめると、
「➁重み付きk近傍グラフをつくる」では重みありで無向なk近傍グラフ$G$を作成した。

2.低次元に配置する

隣接行列が得られたので、これを低次元空間に配置したい。しかし実は隣接行列からグラフを描画する方法は一意ではない。下の二つの図を見てほしい。

どちらも同じグラフを可視化したもの（画像はこちらのもの）。きれいに配置するために力学モデルを使用する。説明が長くなるので力学モデルの説明は Qiita別記事（グラフ描画アルゴリズムとNetworkxの裏側）で書いた。力学モデルでは以下のようなアルゴリズムで頂点を良い感じに配置する。

各頂点間に働く引力／斥力を計算
1で計算した力をもとに頂点を動かす。動かす変位の大きさは温度パラメータ $t$ 以下
温度パラメータを下げる
1～3を一定回数繰り返す

力学モデルでは引力と斥力が定義する必要があるので、以下のように定義する。なぜこの式なのかは後で少しだけ説明するので、いったん受け入れて先に進むことにする。

$f_a(y_i, y_j) = \dfrac{-2ab|y_i - y_j|^{2(b-1)}} {1+|y_i - y_j|^2} w((x_i, x_j))(y_i - y_j)$

$f_r(y_i, y_j) = \dfrac{b} {(\epsilon + |y_i - y_j|^2)(1 + |y_i - y_j|^2)} (1 - w((x_i, x_j))) (y_i - y_j)$

$a, b$：ハイパーパラメータ
$\epsilon$：ゼロ除算を避けるための小さい値

ただしUMAPでは斥力の計算を効率化している。ある頂点$x_i$について考えると、

引力は、近傍のk個に働く
斥力は、近傍以外のN-k個に働く

一般に $k<<N$ なので、斥力の計算がボトルネックになる。UMAPではネガティブサンプリングを使用して、計算量を落としている。辺で接続されていない頂点どうしは、ネガティブエッジで接続されているとみなす。

そしてこのネガティブエッジを良い感じにサンプリングして、暫定的に更新していく。UMAPでは以下のような頂点サンプリング分布 $P$ を使用する。これは十分大きなデータセットにおいて一様分布に近似できる。（この辺わからないので教えてほしいです。）

$P(x_i) = \dfrac{ \sum_{{a \in A | d_0(a) = x_i}}{1 - \mu(a)} }{ \sum_{{b\in A | d_0(b) \neq x_i }}{1 - \mu(b)} }$

$\mu$：メンバーシップ関数（$\mu:A\rightarrow [0, 1]$、$A$に属している度合い）
$A$：Fuzzy topological expression (らしい)

配置を更新する際はネガティブエッジをすべて使用する代わりに、いくつかサンプリングして更新する。つまり以下のようなアルゴリズムになる。

各頂点間に働く引力を計算。斥力は分布$P$でサンプリングして計算。
1で計算した力をもとに頂点を動かす。動かす変位の大きさは温度パラメータ $t$ 以下
温度パラメータを下げる
1～3を一定回数繰り返す

収束性が保証されているかわからないが、経験的にはきちんと収束するようだ。

この理解は本来の流れと全然違う？？

「UMAPの論文は本来めちゃくちゃ数学的なのに、今の説明あってるん？」

「どのようにFuzzy topology やリーマン多様体と関係してるん？」

と思う方のために本来の流れとの関連性を書く。そのためにはまず本来の数学的な流れを知る必要がある…。

本来のUMAPの流れ

数学の知識のある方はこの流れで理解したらいい。

定式化
コスト関数の導出
コスト関数を最小化して低次元に埋め込む

それぞれ簡単に見ていこう。

1.定式化

概要をつかむためにUMAP 論文を読む Qiitaから一部引用しとく。

UMAPでは以下の概念が導入される。（ほえー）

fuzzy set

ファジーな集合

simplicial set

複体のこと

fuzzy simplicial set

1 と 2 の組み合わせ

FinReal

単体を EPMet に変換する

FinSing

EPMet を fuzzy simplicial set に変換する

そして点列を Fuzzy topological expression に変形する操作を定義。

まず1章ではデータ点列からリーマン多様体を推定する方法を述べた.
といっても本当に多様体そのものの形を推定したのではなくて, 有限空間の上の距離 (FinEPMet) を推定してやった.

3章では複体を fuzzy にしたような fuzzy simplicial set を定義し, FinSing という FinEPMet を fuzzy simplicial set に変換するための操作を定義した.

引用だけしてもよくわからんが、数学屋さんが言ってるから多分そうだと思う（理解を放棄）。この辺知りたい方は以下の記事が参考になる。英語に抵抗がないなら論文読むのが正確。

2.コスト関数の導出

二つの Fuzzy topological expression のクロスエントロピーを以下のように定義。

$C((A, \mu), (A, \nu)) \rightarrow \sum_{a \in A}{( \mu(a)\log(\nu(a)) + (1 - \mu(a)) \log(1-\nu(a)) )}$

$\mu, \nu$：メンバーシップ関数（$\mu:A\rightarrow [0, 1]$、$A$に属している度合い）
$A$：Fuzzy topological expression

等号にしていないのは、右辺が最小化の際に関係しない部分を省いたあとの式だから。（詳しくは論文を見てほしい。）

3.コスト関数を最小化して低次元に埋め込む

高次元データを fuzzy topological expression $X$ に変換
低次元データ（埋め込み先）も同様に fuzzy topological expression $Y$ に変換

この Fuzzy topological expression 間のクロスエントロピーが最小になるように、低次元データ$Y$を勾配法に従って変化させていく。こうしてできた $Y$ が可視化結果だったり、次元削減結果になる。

ここまで大雑把にまとめると、

数学屋さんが導出したコスト関数がある。
これを最小化すれば、数学に基づいた低次元埋め込みができる。

先ほどまでの工学的理解とのつながり

「さっきのk近傍グラフとか力学モデルの説明は何だったんだよ！？」
となっているあなた、お待たせしました。力学モデルの引力／斥力の定義がコスト関数とつながっている。

コスト関数は以下のように書けた。

$C((A, \mu), (A, \nu)) \rightarrow \sum_{a \in A}{( \mu(a)\log(\nu(a)) + (1 - \mu(a)) \log(1-\nu(a)) )}$

$\mu, \nu$：メンバーシップ関数（$\mu:A\rightarrow [0, 1]$、$A$に属している度合い）
$A$：Fuzzy topological expression

式をよく見てみると、力学モデルとの関係性が見えてくる。$\mu$は高次元データのほうのメンバーシップ関数なので、$\mu(a)$は$A$に属している度合い、$(1-\mu(a))$は$A$に属していない度合い。つまり、$\sum$の第１項は近傍に作用する項、第２項は近傍以外に作用する項ととらえることができる。

先ほどの引力と斥力はコスト関数から逆算されたものっぽい（論文に明記されていないが、既存手法のLargeVisでもコスト関数を導出したあと、斥力に対応する項をネガティブサンプリングによって効率的に計算している）。

結局先ほどの引力／斥力の定義の真相に迫るには数学の知識が必要になる。しかし、「よくわからないコスト関数を最小化する」という理解より、「グラフをつくって、力に従って埋め込んでいく」理解のほうが一歩進んだ感じがする。

最後に

数学的に難しいUMAPが、（やや技巧的ではあるものの）単純な力学モデルで定式化できるのはおもしろいですね。数学のバックグラウンドがない人（私）にとっての最大限の理解はここまでです。解説できているかわからない部分もあるので、この記事を鵜呑みにせず論文をあたって間違いを指摘してもらえると助かります。

参考文献

UMAP:UniformManifold ApproximationandProjectionfor DimensionReduction,arXiv
：ここにすべてがある

UMAP 論文を読む Qiita
UMAP解説記事
：この二つは数式を追って理解しようとしてる記事

Understanding UMAP
：豊富な図があり、わかりやすい。見るだけでおもしろいので見てほしい。

UMAP ドキュメント
HowToUseUMAP
：ツールとして使うならここを見たらいい

Dimensionality reduction with t-SNE(Rtsne) and UMAP(uwot) using R packages.
：t-SNEとUMAPの概要がつかめる。実用＞理論

グラフ描画アルゴリズムとNetworkxの裏側
：代表的な力学モデルアルゴリズムの解説。（わたしの記事）

近似最近傍探索の最前線
：木による空間分割、ハッシュ、「近傍の近傍もまた近傍」という仮説を立てるなどおもしろい

また以下の論文を読むと理解が深まる。