Upgrade to Pro — share decks privately, control downloads, hide ads and more …

UMAPをざっくりと理解 / Overview of UMAP

UMAPをざっくりと理解 / Overview of UMAP

UMAPをざっくりと理解

kaityo256

May 01, 2025
Tweet

More Decks by kaityo256

Other Decks in Programming

Transcript

  1. 1 25 慶應義塾大学理工学部物理情報工学科 渡辺宙志 2025年5月1日 研究室ミーティング UMAPをざっくりと理解 UMAP: Uniform Manifold

    Approximation and Projection for Dimension Reduction Leland McInnes, John Healy, James Melville, arXiv:1802.0326
  2. 2 25 UMAPとは? Uniform Manifold Approximation and Projection for Dimension

    Reduction 次元削減手法の一つ 𝑓( Ԧ 𝑥) = Ԧ 𝑦 入力データ 高次元ベクトル 出力データ 低次元ベクトル (D=2 or 3) 広く使われている次元削減手法であるt-SNEに比べてクラスタ間の 分離に強く、計算負荷が小さい
  3. 4 25 なぜ次元削減をするのか? • ノイズの影響を強くうけてしまう • 高次元空間のデータのままでは処理が重い • クラスタリングできたとしても、解釈が難しい データ点の関係をなるべく保存したまま次元削減を行うことで

    • ノイズの影響を回避しつつ • 計算コストを抑えながら • 解釈しやすい データを抽出できる t-SNE UMAP 高次元データをそのままクラスタリングすると 次元削減 クラスタリング k-means (H)DBSCAN クラスタリングの前処理のため
  4. 5 25 次元削減の例(MNIST) 𝑥𝑖 = (0.0, 0.0, ... 0.4, 0.8,

    ..., 0.0) 784次元ベクトル 各手書き数字データは784次元空間上の点 これが7万点ある 784次元から2次元へ埋め込み 𝑦𝑖 = (0.2, 0.8) Ԧ 𝑦 = 𝑓( Ԧ 𝑥) UMAPには「数字が10種類ある」と教えていないのに10個の クラスタに分離できた 元のデータは784次元空間上の点 2次元ベクトル
  5. 6 25 次元削減でしたいこと 元の空間で近い点は、変換後の空間でも近くしたい | Ԧ 𝑥𝑖 − Ԧ 𝑥𝑗

    |が小さいなら | Ԧ 𝑦𝑖 − Ԧ 𝑦𝑗 |も小さくしたい 𝑓( Ԧ 𝑥) = Ԧ 𝑦
  6. 7 25 UMAPのアルゴリズム 1. 通常のユークリッド距離でk個の隣接データ点を探す 2. k個の隣接データ点から距離のスケールパラメータを決める 3. 元の空間各点の接続重みを計算する 4.

    接続重みを対称化する 5. 削減後の空間の接続重みを定義する 6. 元の空間と次元削減後の空間の接続重みの交差エントロ ピーを最小化するように低次元埋め込みを行う
  7. 11 25 スケールパラメータの決定 𝐷𝑌 :埋め込み次元 𝑟𝑖𝑗 :点𝑖, 𝑗間の距離 𝜌𝑖 :点𝑖の最近接点への距離

    Ω𝑖 :点𝑖の近傍の集合 以上の情報から、点𝑖のスケールパラメータ𝜎𝑖 を以下のように定める ෍ 𝑗∈Ω𝑖 exp − (𝑟𝑖𝑗 − 𝜌𝑖 ) 𝜎𝑖 = log2 𝐷𝑌 実際には二分探索で𝜎𝑖 を求める
  8. 13 25 重みの対称化 近傍の数をk=3とした場合 i j iにとってjはk近傍(𝑝 𝑗 𝑖 ≠

    0)だが jにとってiはk近傍ではない(𝑝 𝑗 𝑖 = 0) i j iから見たjは近いが jから見たiは遠い 𝑝 𝑗 𝑖 = exp − (𝑟𝑖𝑗 − 𝜌𝑖 ) 𝜎𝑖 点𝑖から点𝑗へ接続する確率 𝑝 𝑗 𝑖 ≠ 𝑝 𝑖 𝑗 一般に 𝑝 𝑗 𝑖 > 𝑝(𝑖|𝑗) 𝑖にとっての単位長さ 𝑗にとっての単位長さ
  9. 14 25 重みの対称化 𝑝𝑖𝑗 = 1 − (1 − 𝑝

    𝑗 𝑖 )(1 − 𝑝 𝑖 𝑗 ) 「少なくともどちらか一方は接続する確率」により対称化 iからjに 接続しない jからiに 接続しない かつ 𝑖 𝑗 𝑝 𝑗 𝑖 𝑝 𝑖 𝑗 = 𝑝 𝑗 𝑖 + 𝑝 𝑖 𝑗 − 𝑝 𝑖 𝑗 𝑝 𝑖 𝑗
  10. 16 25 低次元埋め込み 𝑓( Ԧ 𝑥) = Ԧ 𝑦 高次元空間

    低次元空間 各エッジの重みが同じようになるように低次元に埋め込む (低次元で対応するデータ点の位置を決める)
  11. 17 25 距離のスムージング クラスター内で点の距離が近くなりすぎるのを防ぐため「最低距離」を 定め、それを用いて距離のスムージングを行う 𝑦𝑖𝑗 :次元削減後の点𝑖, 𝑗間のユークリッド距離 𝑙0 :最低距離(ハイパーパラメータ)

    𝑎, 𝑏: 𝑙0 から決まるパラメータ 𝑞𝑖𝑗 = 1 1 + 𝑎𝑦𝑖𝑗 2𝑏 上記を用いて ただし𝑎, 𝑏は𝜙 𝑑 = 1 + 𝑎𝑑2𝑏 −1 が以下の関数に最も近くなるように フィッティングで決める 𝜓 𝑑 = ቊ = 1 𝑑 < 𝑙0 = exp(−(𝑑2−𝑙0 )) otherwise
  12. 18 25 距離のスムージング 𝑞𝑖𝑗 = 1 1 + 𝑎𝑦𝑖𝑗 2𝑏

    以下を次元削減後の空間の点𝑖, 𝑗間の重みとする • 0 < 𝑞𝑖𝑗 ≤ 1を満たす • 距離𝑦𝑖𝑗 が小さいほど重み𝑞𝑖𝑗 が大きくなる • 𝑎 = 𝑏 = 1の場合、Studentのt分布に帰着 • 𝑙0 より小さい場合の重みの変化を無視する 次元削減前の重み𝑝𝑖𝑗 と、次元削減後の重み𝑞𝑖𝑗 をなるべく近づける最適化を行う
  13. 19 25 コスト関数 Ƹ 𝑝𝑖𝑗 :元の空間で𝑖, 𝑗が接続しているか 1:接続、0:接続していない ො 𝑞𝑖,𝑗

    :次元削減後の空間でエッジ𝑖が接続しているか 𝐻 = ෍ 𝑖,𝑗 𝑃 Ƹ 𝑝𝑖𝑗 = 1 log 𝑃 Ƹ 𝑝𝑖𝑗 = 1 𝑃(𝑞𝑖𝑗 = 1) + 𝑃 Ƹ 𝑝𝑖𝑗 = 0 log 𝑃 Ƹ 𝑝𝑖𝑗 = 0 𝑃(ො 𝑞𝑖𝑗 = 0) この量を最小化するように低次元配置を決める = ෍ 𝑖 𝑝𝑖𝑗 log 𝑝𝑖𝑗 𝑞𝑖𝑗 + (1 − 𝑝𝑖𝑗 ) log (1 − 𝑝𝑖𝑗 ) (1 − 𝑞𝑖𝑗 ) ※ 数式上はKLダイバージェンスに見えるが、論文には交差エントロピーと書いてある
  14. 20 25 コスト関数 元の空間で距離が近い(𝑝𝑖𝑗 が大き い)と、次元削減後のエッジの重み 𝑞𝑖𝑗 も大きくしようとする→距離が 近づく→引力相互作用 元の空間で距離が遠い(𝑝𝑖𝑗

    が小さ い)と、次元削減後のエッジの重み 𝑞𝑖𝑗 も小さくしようとする→距離が 遠ざかる→斥力相互作用 この量を確率的勾配降下法(stochastic gradient descent method)で最適化 引力項は真面目に計算するが、斥力項はNegative Samplingにより評価 𝐻 = ෍ 𝑖 𝑝𝑖𝑗 log 𝑝𝑖𝑗 𝑞𝑖𝑗 + (1 − 𝑝𝑖𝑗 ) log (1 − 𝑝𝑖𝑗 ) (1 − 𝑞𝑖𝑗 ) 𝑝𝑖𝑗 :高次元空間でのグラフの重み 𝑞𝑖𝑗 :低次元空間でのグラフの重み
  15. 21 25 ハイパーパラメタの影響 少ない ← 近傍点数k → 大きい 最低距離 短い

    長い ↑ ↓ 近傍点数が大きすぎる→小さな構造を取りこぼす 最低距離が長すぎる→クラスタを分離できない 異なるクラスタが 重なっている クラスタが 接近しすぎている
  16. 24 25 t-SNEとの比較 t-SNE UMAP 高次元空間の重み exp(− Ԧ 𝑥𝑖 −

    Ԧ 𝑥𝑗 2 /2𝜎𝑖 2) ガウス型 exp(−(𝑟𝑖𝑗 − 𝜌𝑖 )/𝜎𝑖 ) 指数関数型 低次元空間の重み t分布 𝑞𝑖𝑗 ∝ 1 + Ԧ 𝑦𝑖 − Ԧ 𝑦𝑗 2 −1 修正t分布 𝑞𝑖𝑗 ∝ 1 + 𝑎 Ԧ 𝑦𝑖 − Ԧ 𝑦𝑗 2𝑏 −1 𝑝𝑖𝑗 の構築 全データ点ペア 𝑝𝑖𝑗 の意味 点𝑖が近傍として 点𝑗を選ぶ確率 点𝑖, 𝑗間を結ぶエッジが 存在する確率 k個の近傍点についてのみ 対称化 𝑝𝑖𝑗 = 𝑝 𝑗 𝑖 + 𝑝(𝑖|𝑗) 2𝑁 幾何平均 𝑝𝑖𝑗 = 𝑝 𝑗 𝑖 + 𝑝 𝑖 𝑗 − 𝑝 𝑖 𝑗 𝑝 𝑖 𝑗 T-conorm
  17. 25 25 まとめ • UMAPはファジートポロジカル構造に着目することで次元削減する アルゴリズム • 最初にk個の近傍点を探し、その近傍点の重みのみを考えるため、 計算が軽い •

    重要なハイパーパラメタは近傍点数kと最低距離min_dist 近傍点数: 注目したい領域のサイズを決める 小さすぎるとノイズに埋もれ、大きすぎると小さい構造を取りこぼす 最低距離: 引力が働く距離の下限。これより小さいと引力が抑制される 大きすぎるとクラスターがつぶれ、小さすぎるとクラスターが分離できない