非線形次元削減

サモンのマッピングは、NLDR（非線形データ解析）技術の中でも最初期に開発された、最も普及している手法の一つである。

自己組織化マップ（SOM、コホーネンマップとも呼ばれる）とその確率的変種である生成地形図（GTM）は、埋め込み空間の点表現を使用して、埋め込み空間から高次元空間への非線形マッピングに基づく潜在変数モデルを形成します。 ^{[ 6 ]}これらの技術は、同じ確率モデルに基づいている密度ネットワークに関する研究に関連しています。

次元削減に最も広く使われているアルゴリズムはカーネルPCAである。^{[ 7 ]} PCAは、まず共分散行列を計算することから始まる。${\displaystyle m\times n}$マトリックス${\displaystyle \mathbf {X} }$

${\displaystyle C={\frac {1}{m}}\sum _{i=1}^{m}{\mathbf {x} _{i}\mathbf {x} _{i}^{\mathsf {T}}}.}$

次に、そのデータをその行列の最初のk 個の固有ベクトルに投影します。これに対し、KPCA は、データをより高次元の空間に変換した後、その共分散行列を計算することから始まります。

${\displaystyle C={\frac {1}{m}}\sum _{i=1}^{m}{\Phi (\mathbf {x} _{i})\Phi (\mathbf {x} _{i})^{\mathsf {T}}}.}$

次に、PCAと同様に、変換されたデータをその行列の最初のk 個の固有ベクトルに投影します。カーネルトリックを使用して計算の大部分を因数分解するため、実際の計算を行わずにプロセス全体を実行できます。${\displaystyle \Phi (\mathbf {x} )}$。 もちろん${\displaystyle \Phi }$は、対応するカーネルが既知であるように選択する必要があります。残念ながら、与えられた問題に対して適切なカーネルを見つけることは容易ではないため、標準カーネルを使用した場合、KPCA は一部の問題で良好な結果を得られません。たとえば、スイスロール多様体では、これらのカーネルでは性能が低いことが知られています。ただし、このような設定で良好な性能を発揮する他のいくつかの方法 (たとえば、ラプラシアン固有マップ、LLE) は、データ依存カーネル行列を構築することにより、カーネル PCA の特殊なケースと見なすことができます。^{[ 8 ]}

KPCAは内部モデルを備えているため、トレーニング時に利用できなかった点を埋め込みにマッピングするために使用できます。

主曲線と多様体は、非線形次元削減のための自然な幾何学的枠組みを提供し、埋め込み多様体を明示的に構築し、多様体への標準的な幾何学的投影を使用してエンコードすることにより、PCA の幾何学的解釈を拡張します。このアプローチは、もともとTrevor Hastieが1984 年の論文^{[ 11 ]}で提案し、 1989 年に正式に発表しました^{[ 12 ]}。このアイデアは、多くの著者によってさらに検討されています^{[ 13 ]} 。 多様体の「単純さ」をどのように定義するかは問題に依存しますが、一般的には、多様体の固有の次元および/または滑らかさによって測定されます。通常、主多様体は最適化問題の解として定義されます。目的関数には、データ近似の品質と、多様体の曲がりに対するいくつかのペナルティ項が含まれます。一般的な初期近似は、線形 PCA と Kohonen の SOM によって生成されます。

ラプラシアン固有マップは、スペクトル技術を使用して次元削減を実行します。^{[ 14 ]}この技術は、データが高次元空間内の低次元多様体にあるという基本的な仮定に基づいています。^{[ 15 ]} このアルゴリズムはサンプル外の点を埋め込むことはできませんが、再生核ヒルベルト空間正則化に基づく技術により、この機能を追加できます。^{[ 16 ]} このような技術は、他の非線形次元削減アルゴリズムにも適用できます。

主成分分析などの従来の手法では、データの固有の幾何学的構造は考慮されません。ラプラシアン固有マップは、データセットの近傍情報からグラフを構築します。各データポイントはグラフ上のノードとして機能し、ノード間の接続性は近傍点の近接度によって決定されます（例えば、k近傍法アルゴリズムを使用）。このようにして生成されたグラフは、高次元空間における低次元多様体の離散近似とみなすことができます。グラフに基づくコスト関数の最小化により、多様体上で互いに近い点が、局所的な距離を保持したまま、低次元空間でも互いに近い位置にマッピングされることが保証されます。多様体上のラプラス・ベルトラミ演算子の固有関数は埋め込み次元として機能します。これは、緩やかな条件下で、この演算子が多様体上の二乗可積分関数の基底となる可算スペクトルを持つためです（単位円多様体上のフーリエ級数と比較してください）。ラプラシアン固有写像を確固たる理論的基盤の上に置こうとする試みは、ある程度の成功を収めており、特定の非制限的な仮定の下では、点の数が無限大に近づくにつれて、グラフ・ラプラシアン行列がラプラス・ベルトラミ演算子に収束することが示されている。^{[ 15 ]}

Isomap ^{[ 17 ]}は、 Floyd–Warshall アルゴリズムと古典的な多次元尺度構成法 (MDS)を組み合わせたものです。古典的な MDS は、すべての点間のペアワイズ距離のマトリックスを受け取り、各点の位置を計算します。Isomap は、ペアワイズ距離は隣接する点間でのみ既知であると仮定し、Floyd–Warshall アルゴリズムを使用して他のすべての点間のペアワイズ距離を計算します。これにより、すべての点間のペアワイズ測地距離の完全なマトリックスが効果的に推定されます。次に、Isomap は古典的な MDS を使用して、すべての点の次元削減された位置を計算します。Landmark-Isomap は、ランドマークを使用して速度を向上させるこのアルゴリズムの変種ですが、精度が多少犠牲になります。

多様体学習では、入力データは、より高次元のベクトル空間内に埋め込まれた低次元多様体からサンプリングされたものと想定されます。MVUの主な考え方は、多様体の局所的な線形性を活用し、基となる多様体のあらゆる点において局所的な近傍を保持するマッピングを作成することです。

局所線形埋め込み(LLE) は、Isomap とほぼ同時期に発表されました。^{[ 18 ]} LLE は、疎行列アルゴリズムを活用するように実装すると最適化が速くなることや、多くの問題でより良い結果が得られることなど、Isomap に比べていくつかの利点があります。LLE もまた、各点の最近傍点のセットを見つけることから始まります。次に、各点をその近傍点の線形結合として最もよく表す重みのセットを計算します。最後に、固有ベクトルベースの最適化手法を使用して、各点が依然としてその近傍点の同じ線形結合で表されるように、点の低次元埋め込みを見つけます。LLE は、さまざまな領域のサンプル密度が異なるため重みがドリフトするのを防ぐ固定単位がないため、不均一なサンプル密度をうまく処理できない傾向があります。LLE には内部モデルがありません。

元のデータポイント${\displaystyle X_{i}\in \mathbb {R} ^{D}}$LLEの目標は各点を埋め込むことである${\displaystyle X_{i}}$低次元の点へ$\displaystyle Y_{i}\in \mathbb {R} ^{d}}$、 どこ${\displaystyle d\ll D}$。

LLEは2つのステップから構成されます。最初のステップでは、各点X _iについて、その近傍点X _jの重心座標に基づいてX _iの最適な近似値を計算します。元の点は、重み行列W _ijで与えられる近傍点の線形結合によって近似的に再構成されます。再構成誤差は次のとおりです。

${\displaystyle E(W)=\sum _{i}\left|\mathbf {X} _{i}-\sum _{j}{\mathbf {W} _{ij}\mathbf {X} _{j}}\right|^{2}}$

重みW _{ij は}、点X _iを再構築する際に点X _jが果たす貢献度を表します。コスト関数は、次の 2 つの制約の下で最小化されます。

• 各データポイントX _{i は}、その近傍のデータポイントからのみ再構築されます。つまり、${\displaystyle W_{ij}=0}$点X _{j が}点X _iの隣接点ではない場合。
• 重み行列の各行の合計は 1 に等しくなります。つまり、${\displaystyle \sum _{j}{\mathbf {W} _{ij}}=1}$。

これら2つの制約により、${\displaystyle W}$回転や平行移動の影響を受けない。

2番目のステップでは、重みに基づいて近隣領域を保持するマップが作成されます。各ポイント${\displaystyle X_{i}\in \mathbb {R} ^{D}}$点にマッピングされる$\displaystyle Y_{i}\in \mathbb {R} ^{d}}$別のコストを最小限に抑えることによって：

${\displaystyle C(Y)=\sum _{i}\left|\mathbf {Y} _{i}-\sum _{j}{\mathbf {W} _{ij}\mathbf {Y} _{j}}\right|^{2}}$

以前のコスト関数とは異なり、重み W _ijは固定され、座標を最適化するために点 Y _{i上で最小化が行われます。この最小化問題は、疎な}N × N固有値問題( Nはデータ点の数) を解くことで解決でき、その下位d個の非ゼロ固有ベクトルが直交座標セットを提供します。

このアルゴリズムにおける唯一のハイパーパラメータは、ある点の「近傍」とみなす要素です。一般的に、データ点はユークリッド距離で測定したK個の最近傍点から再構築されます。この場合、アルゴリズムには整数値のハイパーパラメータKが1つだけ存在し、これは交差検証によって選択できます。

LTSA ^{[ 22 ]}は、多様体が正しく展開されると、多様体へのすべての接超平面が整列するという直感に基づいています。まず、すべての点のk近傍を計算します。各局所近傍でd番目に大きい主成分を計算することで、すべての点の接空間を計算します。次に、接空間を整列させる埋め込みを見つけるように最適化します。

最大分散展開、Isomap、および局所線形埋め込みは、多様体が適切に展開されると点の分散が最大化されるという考え方に依拠した共通の直感を共有しています。Isomapや局所線形埋め込みと同様に、最初のステップは、すべての点のk近傍点を見つけることです。次に、隣接点間の距離が維持されるように制約された、すべての非隣接点間の距離を最大化する問題を解こうとします。このアルゴリズムの主な貢献は、この問題を半正定値計画問題として定式化する手法です。残念ながら、半正定値計画ソルバーは計算コストが高いです。局所線形埋め込みと同様に、内部モデルはありません。

オートエンコーダーは、恒等関数を近似するように学習されたフィードフォワードニューラルネットワークです。つまり、値のベクトルから同じベクトルにマッピングするように学習されます。次元削減目的で使用される場合、ネットワークの隠れ層の 1 つは、少数のネットワークユニットのみを含むように制限されます。したがって、ネットワークは、ベクトルを少数の次元にエンコードし、それを元の空間にデコードするように学習する必要があります。したがって、ネットワークの前半は高次元空間から低次元空間にマッピングするモデルであり、後半は低次元空間から高次元空間にマッピングします。オートエンコーダーのアイデアはかなり古いものですが、^{[ 23 ]}ディープオートエンコーダーのトレーニングは、制限付きボルツマンマシンとスタック型ノイズ除去オートエンコーダーの使用により、ごく最近になって可能になりました。オートエンコーダーに関連するものには、多次元尺度構成法とサモンマッピング(上記参照)に触発されたストレス関数を使用して、高次元から埋め込み空間への非線形マッピングを学習する NeuroScale アルゴリズムがあります。 NeuroScaleにおけるマッピングは、放射基底関数ネットワークに基づいている。

ガウス過程潜在変数モデル(GPLVM) ^{[ 24 ]}は、ガウス過程 (GP) を使用して高次元データの低次元非線形埋め込みを見つける確率的次元削減手法です。これは、PCA の確率的定式化の拡張です。モデルは確率的に定義され、潜在変数は周辺化され、尤度を最大化することによってパラメータが得られます。カーネル PCA と同様に、カーネル関数を使用して非線形マッピング (ガウス過程の形式) を形成します。ただし、GPLVM ではマッピングは埋め込み (潜在) 空間からデータ空間 (密度ネットワークや GTM と同様) への方向であるのに対し、カーネル PCA では逆方向です。元々は高次元データの可視化のために提案されましたが、2 つの観測空間間で共有多様体モデルを構築するために拡張されました。 GPLVMとその多くの派生モデルは、特に人間の動作モデリングのために提案されており、例えば、バックコンストレイントGPLVM、GPダイナミックモデル（GPDM）、バランスGPDM（B-GPDM）、トポロジー制約GPDMなどがあります。歩行分析における姿勢と歩行多様体の結合効果を捉えるために、多層ジョイント歩行姿勢多様体が提案されました。^{[ 25 ]}

関係性透視図法は、多次元尺度構成法のアルゴリズムです。このアルゴリズムは、閉じた多様体上で多粒子動的システムをシミュレートすることにより、多様体上のデータ点の配置を見つけ出します。このシステムでは、データ点が粒子にマッピングされ、データ点間の距離（または非類似度）が反発力として表されます。多様体のサイズが徐々に大きくなるにつれて、多粒子システムは徐々に冷却され、データ点間の距離情報を反映した配置に収束します。

関係性パースペクティブマップは、正電荷を帯びた粒子が球体の表面を自由に移動する物理モデルから着想を得ています。粒子間のクーロン力によって導かれる粒子の最小エネルギー配置は、粒子間の反発力の強さを反映します。

関係透視図法は^{[ 26 ]}で導入されました。 このアルゴリズムは当初、画像多様体として平面トーラスを使用していましたが、その後、（ソフトウェアVisuMapで）球、射影空間、クラインの壺などの他のタイプの閉じた多様体を画像多様体として使用できるように拡張されました。

感染マップは、ネットワーク上の複数の感染を利用してノードを点群としてマッピングします。^{[ 27 ]}グローバルカスケードモデルの場合、拡散速度は閾値パラメータで調整できます。${\displaystyle t\in [0,1]}$。 のために${\displaystyle t=0}$感染マップはIsomapアルゴリズムと同等である。

曲線成分分析（CCA）は、出力空間内の小さな距離に焦点を当てながら、元の距離をできるだけ保持するような出力空間内の点の配置を探します（元の空間内の小さな距離に焦点を当てるSammonのマッピングとは逆です）。 ^{[ 28 ]}

注目すべきは、CCAは反復学習アルゴリズムとして、実際には（Sammonアルゴリズムのように）大きな距離に焦点を当てることから始まり、徐々に小さな距離へと焦点を移していく点である。両者の間で妥協点を見出す必要がある場合、小さな距離の情報が大きな距離の情報を上書きする。

CCAのストレス関数は右ブレグマン発散の合計に関連している。^{[ 29 ]}

CDA ^{[ 28 ]}は、自己組織化ニューラルネットワークを訓練して多様体に適合させ、その埋め込みにおける測地距離を保持しようとします。これは曲線成分分析（Sammon のマッピングを拡張したもの）に基づいていますが、測地距離を使用します。

微分同相次元削減またはDiffeomap ^{[ 30 ]}は、データをより低次元の線形部分空間に転送する滑らかな微分同相写像を学習します。この手法は、データ点から始まるフィールドに沿った流れがより低次元の線形部分空間で終了するような、滑らかな時間インデックス付きベクトル場を解き、順方向および逆方向の写像の下でペアワイズ差を保持しようとします。

多様体アライメントは、類似の生成プロセスによって生成された異なるデータセットが、類似した基底多様体表現を共有するという仮定を利用します。各元の空間から共有多様体への射影を学習することで、対応関係が復元され、あるドメインの知識を別のドメインに転送できます。ほとんどの多様体アライメント手法は2つのデータセットのみを考慮しますが、この概念は任意の数の初期データセットに拡張できます。^{[ 31 ]}

拡散マップは、熱拡散とランダムウォーク（マルコフ連鎖）の関係を利用します。多様体上の拡散演算子と、多様体からサンプリングされたノードを持つグラフ上で定義された関数に作用するマルコフ遷移行列との間に類似性が見られます。^{[ 32 ]}特に、データセットを次のように表します。$\displaystyle \mathbf {X} =[x_{1},x_{2},\ldots ,x_{n}]\in \Omega \subset \mathbf {R^{D}} }$拡散マップの基本的な仮定は、高次元データが次元の低次元多様体上に存在するというものである。${\displaystyle \mathbf {d} }$Xをデータセットとし、${\displaystyle \mu }$X上のデータ点の分布を表す。さらに、X内の点の類似性を表すカーネルを定義する。カーネル${\displaystyle {\mathit {k}}}$以下の特性を持つ^{[ 33 ]}

${\displaystyle k(x,y)=k(y,x),}$

kは対称である

${\displaystyle k(x,y)\geq 0\qquad \forall x,y,k}$

kは正値性を保持する

したがって、個々のデータポイントをグラフのノード、カーネルkをそのグラフ上の何らかのアフィニティを定義するものと考えることができます。カーネルが対称であるため、グラフも構成上対称です。ここで、タプル ( X , k ) から可逆マルコフ連鎖を構築できることが容易にわかります。この手法はさまざまな分野で共通しており、グラフ・ラプラシアンとして知られています。

例えば、グラフK = ( X , E ) はガウスカーネルを用いて構築することができる。

${\displaystyle K_{ij}={\begin{cases}e^{-\|x_{i}-x_{j}\|_{2}^{2}/\sigma ^{2}}&{\text{if }}x_{i}\sim x_{j}\\0&{\text{otherwise}}\end{cases}}}$

上記の式において、${\displaystyle x_{i}\sim x_{j}}$は、${\displaystyle x_{i}}$は、${\displaystyle x_{j}}$本来、多様体上の距離を実際に測定するには測地距離を用いるべきである。多様体の正確な構造は不明であるため、最近傍点については測地距離をユークリッド距離で近似する。${\displaystyle \sigma }$近接性の概念を調整するという意味で、${\displaystyle \|x_{i}-x_{j}\|_{2}\gg \sigma }$それから${\displaystyle K_{ij}=0}$そしてもし${\displaystyle \|x_{i}-x_{j}\|_{2}\ll \sigma }$それから${\displaystyle K_{ij}=1}$前者は拡散がほとんど起こっていないことを意味し、後者は拡散プロセスがほぼ完了していることを意味します。選択するためのさまざまな戦略${\displaystyle \sigma }$^{[ 34 ]}に記載されている。

マルコフ行列を忠実に表現するために、${\displaystyle K}$対応する次数行列で正規化する必要がある${\displaystyle D}$:

${\displaystyle P=D^{-1}K.}$

${\displaystyle P}$これはマルコフ連鎖を表す。${\displaystyle P(x_{i},x_{j})}$からへの遷移の確率は${\displaystyle x_{i}}$に${\displaystyle x_{j}}$1つの時間ステップで。同様に、からへの遷移の確率は${\displaystyle x_{i}}$に${\displaystyle x_{j}}$tタイムステップでは、次のように与えられます。${\displaystyle P^{t}(x_{i},x_{j})}$。 ここ${\displaystyle P^{t}}$行列は${\displaystyle P}$t回自身を掛け合わせる。

マルコフ行列${\displaystyle P}$これは、データセットXの局所的な幾何学的構造に関する何らかの概念を構成します。拡散マップと主成分分析の主な違いは、拡散マップではデータセット全体の相関関係を考慮するのに対し、データの局所的な特徴のみが考慮される点です。

${\displaystyle K}$これはデータセット上のランダムウォークを定義しており、カーネルがデータセットの局所的な形状を捉えていることを意味します。マルコフ連鎖は、カーネル値を通して伝播する速い方向と遅い方向を定義します。ウォークが時間とともに前進するにつれて、局所的な形状情報は、動的システムの局所的な遷移（微分方程式で定義される）と同じように集約されます。^{[ 33 ]}拡散のメタファーは、ファミリー拡散距離の定義から生じます。${\displaystyle \{D_{t}\}_{t\in N}}$

${\displaystyle D_{t}^{2}(x,y)=\|p_{t}(x,\cdot )-p_{t}(y,\cdot )\|^{2}}$

tが固定されている場合、${\displaystyle D_{t}}$パス接続性に基づいてデータセットの任意の 2 ポイント間の距離を定義します。${\displaystyle D_{t}(x,y)}$xとyを結ぶ経路の数が多いほど、またその逆も同様に、小さくなります。なぜなら、その量は${\displaystyle D_{t}(x,y)}$長さ t のすべての経路の合計を含みます。${\displaystyle D_{t}}$測地距離よりもデータ中のノイズに対してはるかに頑健である。${\displaystyle D_{t}}$距離を計算する際に、点xと点y間のすべての関係を考慮に入れ、ユークリッド距離や測地距離よりも優れた近接性の概念を提供する。

局所多次元尺度構成法は、局所領域で多次元尺度構成法を実行し、凸最適化を使用してすべての要素を適合させます。^{[ 35 ]}

非線形主成分分析（NLPCA）は、バックプロパゲーションを使用して、多様体に適合する多層パーセプトロン（MLP）をトレーニングします。^{[ 36 ]}重みのみを更新する一般的なMLPトレーニングとは異なり、NLPCAは重みと入力の両方を更新します。つまり、重みと入力の両方が潜在値として扱われます。トレーニング後、潜在入力は観測ベクトルの低次元表現となり、MLPはその低次元表現から高次元の観測空間にマッピングします。

データ駆動型高次元尺度構成法（DD-HDS）^{[ 37 ]}は、 (1)元の空間と出力空間の両方で小さな距離に焦点を当てることで偽の近傍と裂け目を同時に罰し、(2)距離分布に合わせて重み関数を調整することで尺度の集中現象を考慮するという点を除いて、Sammonのマッピングと曲線成分分析に密接に関連しています。

Manifold Sculpting ^{[ 38 ]}は、段階的最適化を使用して埋め込みを見つけます。他のアルゴリズムと同様に、k近傍を計算し、局所的な近傍の関係性を維持する埋め込みを探します。高次元の分散をゆっくりとスケーリングアウトしながら、同時に低次元の点を調整してそれらの関係性を維持します。スケーリング率が小さい場合、非常に正確な埋め込みを見つけることができます。いくつかの問題を抱える他のアルゴリズムよりも高い経験的精度を誇ります。また、他の多様体学習アルゴリズムの結果を改善するためにも使用できます。ただし、非常に遅いスケーリング率を使用しない限り、一部の多様体を展開するのに苦労します。モデルはありません。

RankVisu ^{[ 39 ]}は、距離ではなく近傍のランクを保持するように設計されています。RankVisu は、困難なタスク (距離の保持が満足に達成できない場合) で特に役立ちます。実際、近傍のランクは距離よりも情報量が少なく (ランクは距離から推測できますが、距離はランクから推測できません)、そのためランクの保持は容易です。

トポロジー制約付き等長埋め込み(TCIE) ^{[ 40 ]}は、ユークリッド距離と矛盾する測地線をフィルタリングした後、測地距離を近似するアルゴリズムです。本質的に非凸なデータをマッピングするために Isomap を使用したときに発生する歪みを修正することを目的として、TCIE は重み付き最小二乗 MDS を使用して、より正確なマッピングを取得します。TCIE アルゴリズムは、まずデータ内の境界点を検出し、測地線の長さを計算する際に矛盾する測地線をマークし、後続の重み付きストレス優位化で小さな重みを与えます。

t分布確率的近傍埋め込み（t-SNE）^{[ 41 ]}は広く用いられている。これは確率的近傍埋め込み手法のファミリーの一つである。このアルゴリズムは、高次元空間におけるデータ点のペアが関連している確率を計算し、類似した分布を生成する低次元埋め込みを選択する。

ユニフォーム多様体近似射影（UMAP）は、非線形次元削減手法です。^{[ 42 ]} t-SNE ^{[ 43 ] [ 44 ]}と同様の方法で動作しますが、主な違いは、遠く離れた点を互いに遠ざけるための反発項が含まれていることです。