Uniform Manifold Approximation and Projectionの日本語訳.

はじめに

この記事はUMAPの論文のキーワードを紹介と解説するのもであり(ごめんなさい現時点ではただの翻訳です.),筆者の数学のレベルが著しく低レベルであるため,おかしな点があるかもしれません.ご容赦ください.またコメントにてそのおかしな点をご指摘いただけるとありがたいです.また理論の説明は数学的な内容が含まれているため原著に任せます.

Githubの訳

「Uniform Manifold Approximation and Projection」は,
日本語に直すと「一様多様体近似と投影」となります.

t-SNEと同様に視覚的な次元圧縮に使用できますが,UMAPは一般的な非線形次元圧縮に使われます.

このアルゴリズムはデータに対して3つの仮定があります.

1.データはリーマン多様体上に一様に分布している.
2.リーマン計量は局所定数である.(または近似できます)
3.多様体は局所連結である。

これらの仮定から多様体をファジー位相構造でモデル化することが可能である。
埋め込みは、可能な限り同等のファジー位相構造を有するデータの低次元投影を探索することによって見出される。

論文の訳

アブストラクト

UMAP(Uniform Manifold Approximation and Projection)は、次元削減のための新しい学習手法です. UMAPは、リーマン幾何学と代数的位相幾何学に基づく理論的枠組みから構築されています.結果は実世界のデータに適用される実用的なスケーラブルなアルゴリズムです.UMAPアルゴリズムは視覚化のクオリティはt-SNEに劣らず,またランタイムパフォーマンスも優秀である.さらに、UMAPは、埋め込み寸法に関する計算上の制限がなく、機械学習のための一般的な次元削減技法として実行可能である。

イントロダクション

次元削減は、関連する構造(アプリケーションに依存する関連性)を保持する高次元データの低次元表現を生成することを目指しています.次元削減は、データサイエンスのための視覚化と機械学習における前処理ステップの両方において重要な問題である.

次元削減はますます増加するデータセットの視覚化と前処理の基本テクニックである.したがって、大量のデータに対して柔軟であり、利用可能なデータの多様性に対処することができるアルゴリズムを有することが望ましい.次元削減アルゴリズムは2つのカテゴリに分類される傾向があります.

.データ内の距離構造を保存しようとするもの.
.またはグローバル距離上のローカル距離の保存に有利なもの.
PCA [8]などのアルゴリズム, MDS[9], と Sammon mapping [20]とt-SNEは前者のカテゴリに分類され[15][26], Isomap [24], LargeVis [22], Laplacian eigenmaps [1] [2], di‚usion maps [4],
NeRV [28], とJSE [12] はすべて後者のアルゴリズムに属します.

UMAP(Uniform Manifold Approximation and Projection)は、t-SNEに似た結果を提供することを目指していますが、ラプラシアン固有写像上のBelkinとNiyogiの研究に関連する数学的基礎に基づいています.
特に、リーマン幾何学とDavid Spivak [21]の研究を組み合わせることにより、多様体上の一様分布の問題に対処し、ファジー単純集合の幾何学的実現へのカテゴリー理論アプローチに取り組んでいる.

本論文では次元削減のための新しい多様体学習手法を紹介する.実際の世界のデータに適用される実用的でかつ柔軟なアルゴリズムとテクニックを念頭に置いた健全な数学理論を提供します. t-SNEは、視覚化のための次元削減のための最新技術です.

我々のアルゴリズムは、視覚化の質においてt-SNEと競合し、ランタイムパフォーマンスの優れたグローバルな構造をより多く保持していると言えます。さらに、UMAPのトポロジー基盤は、t-SNEで実現可能なデータ・サイズよりも大きなデータ・セット・サイズに大規模に拡張することを可能にします.最後に、UMAPには埋め込みディメンションに関する計算上の制限がなく、機械学習の汎用次元削減テクニックとして実行可能になります.

第2節では、アルゴリズムの根底にある理論について説明します。第3節では、実世界のデータセットに関する実用的な結果を提供します.

2 UMAPアルゴリズム

概要として、UMAPはlocal多様体近似を用いて、それらのlocalファジー単純集合表現をパッチする。(すいませんここのちゃんとした訳が分かりませんでした.)高次元データのトポロジー表現を構築する.
データの低次元表現が与えられると、同様のプロセスを使用して同等のトポロジカル表現を構成することができる.
次に、UMAPは、低次元空間におけるデータ表現のレイアウトを最適化し、2つの位相表現間のクロスエントロピーを最小化する.

ファジィトポロジー表現の構築は、2つの問題、すなわち、データが存在すると想定される多様体を近似すること、近似された多様体のファジィ単純集合表現を構成する.
このアルゴリズムを説明するにあたっては、ソースデータの多様体を近似する方法について議論する。次に、多様体近似からファジー単純集合構造を構築する方法について説明する。次に、低次元表現(多様体は単に \mathbb{R}^d である)に関連するファジー単純集合の構成と表現を最適化する方法について議論する。最後に、いくつかの実装の問題について説明します.

2.1 多様体上のデータの一様分布と測地線近似

我々のアルゴリズムの最初のステップは、データがあると仮定した多様体の推定値を求めることです.
原著の方を見てください.

2.2 ファジィトポロジカル表現

原著の方をみてください.

2.3 低次元表現の最適化

原著の方を見てください.

2.4 実装

このアルゴリズムの実用的な実装には、確率的な勾配降下によるk-最近傍計算および効率の最適化が必要である。
効率的な近似k-最近傍計算は、Dong et al。のNearest-Neighbor-Descentアルゴリズムによって達成することができる。 [5]。エラー本来のそのような近似は、これらの目的には十分すぎることを意味する。
提供された目的関数の下での埋め込みを最適化する際には、Tangらの研究[22]。確率的エッジサンプリングを利用し、ネガティブサンプリング[17]。これは、非常に確率的な近似確率正規化要件がないため、勾配降下アルゴリズムを使用します。
さらに、入力データのファジィグラフ表現の正規化されたラプラシアンは、多様体のラプラス – ベトトラミ演算子の離散近似であるので([1]と[2]を参照)、確率的勾配降下正規化されたラプラシアンの固有ベクトルを使用します。
これらの手法を組み合わせることで、非常に効率的な埋め込みが行われます。
これについては、次のセクションで説明します。

実装は次の場所にあります。
https://github.com/lmcinnes/umap

実験結果

UMAPの強力な数学的基盤はその発展の動機であったが、最終的にその実効性によって判断されなければならない. このセクションでは、UMAPにおける複数の多様な実世界データセットの低次元埋め込みの忠実度とパフォーマンスを検証します. 以下のデータセットが考慮された.

3.1 定性分析

視覚化のための次元削減のための現在の技術水準は、HintonおよびVan der Maatenのt-SNEアルゴリズム(およびその変形)である。
PCA [8]、多次元スケーリング[9]、Isomap [23]を含む従来の手法と比較して、t-SNEはデータの局所構造の発見と保存において劇的な改善を提供する。 これにより、t-SNEがベンチマークとなります.
これに対して、あらゆる寸法削減技術を比較しなければならない.
私たちは、UMAPによって生成される埋め込みの品質は、2次元または3次元に縮小するときにt-SNEに匹敵すると主張している。 例えば、図1は、COIL20、MNIST、ファッションMNIST、およびGoogleニュースのデータセットのUMAPとt-SNE埋め込みの両方を示しています。 正確な埋め込みは異なるが、UMAPはt-SNEと同じ構造を区別する.

UMAPは、t-SNEよりもデータセットのグローバルおよびトポロジの構造の多くを獲得したと主張することができます.
COIL20データセットのループの多くは、絡み合ったループを含め、元のままです.
同様に、MNIST数字データセットの異なる桁間のグローバルな関係は、埋め込みスペースの隅に1(赤)と0(暗い赤)、4,7,9(黄色、海緑色、紫色) )と3,5,8(オレンジ色、チャートトゥーズ、青色)は、同様の桁の明確な塊として分離されています.

ファッションMNISTのデータセットでは、衣類(ダークレッド、イエロー、オレンジ、バーミルン)とフットウェア(シャトー、シーグリーン、バイオレット)の区別がより明確になっています.

最後に、t-SNEとUMAPの両方が同様の単語ベクトルのグループを捕捉しているが、UMAP埋め込みは様々な単語クラスタ間でより明確なグローバル構造を示していると思われる.


図1:多数の実世界データセットのUMAPとt-SNE埋め込みの比較.COIL20データセットのループの多くは、UMAPによる絡み合ったループを含め、元のままです.同様に、MNIST数字データセットの異なる桁間のグローバルな関係は、埋め込みスペースの隅に1(赤)と0(暗い赤)、4,7,9(黄色、海緑色、紫色) )と3,5,8(オレンジ色、黄緑色、青色)は、同様の桁の明確な塊として分離されています.

3.2 パフォーマンスとスケーリング

性能比較のために、MulticoreTSNE [25]と比較することを選択しました。現時点でt-SNEの中で最も速く現存する実装であると考えており、シングルコアモードで実行しても MulticoreTSNEは以下のとおりです.MulticoreTSNEは、Van der Maatenのbhtsne [26]コードに基づいてC++で書かれた非常に最適化された実装であることに注意してください。
対照的に、私たちのUMAP実装はPythonで書かれていました.(パフォーマンスのためにnumba [10]ライブラリを使用しています)。
MulticoreTSNEはシングルスレッドモードで実行され、シングルスレッドUMAP実装との公正な比較が行われました.
さまざまな現実世界のデータセットに対するベンチマークは、3.1GHzのIntel Core i7と8GBのRAMを搭載したMacBook Proで実行されました.Googleニュースのデータセットのスケーリング基準は、フルサイズのデータセットを読み込む際のメモリの制約のため、Intel Xeon E5-2697v4プロセッサと512GB RAMのサーバで実行されました.


表1からわかるように、t-SNEは、データセットサイズとデータセット次元の両方でスケーリングされます.
対照的に、UMAP実装のスケーリングは、主にデータセットのサイズによって支配されます。 Barnes-Hut t-SNEは、低次元埋め込み空間のクワッド・ツリーやオクタ・ツリーに頼っているが、UMAP実装にはそのような制限がないため、埋め込みディメンションに関して容易に拡張できることにも注目する価値がある.


図2:完全なGoogle Newsデータセットの様々なサイズのサブサンプルでのt-SNEとUMAPのランタイムパフォーマンススケーリング より低いt-SNEラインは、8コアを使用するマルチコアt-SNEのウォールクロックランタイムです。

これにより、UMAPは、単に視覚化技術としてではなく、汎用の次元削減技術として使用できます。
ランタイムスケーリングのパフォーマンスとデータセットサイズを直接的に比較すると、GoogleNewsデータセットはさまざまなデータセットサイズでサブサンプリングされました.
図2に示すように、UMAPは優れた漸近的スケーリング性能を示し、大きなデータでは複数のコアでもt-SNEより約1桁速いスピードで実行されます.
図3に示す300万語の完全なGoogleNewsデータセットのUMAP埋め込みは、複数のコアを使用する場合でも、t-SNEに必要な数日間と比較して約200分で完了しました.


図3:UMAPによって埋め込まれたGoogleNewsデータセットからの300万語のベクトルの視覚化.

4 結論

私たちは、強力な数学的基礎に基づいた一般的な次元削減技術を開発しました.アルゴリズムは明らかにt-SNEよりも高速でスケーリングが優れています.これにより、以前は不可能だった,より大きなデータセットの高品質埋め込みを生成することができます。

リファレンスは英語の論文を参照してください.
原著

コメントを残す

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください