Semidefinite embedding とは

Semidefinite embedding(SDE)またはMVD(maximum variance unfolding)は、高次元のベクトル入力データの非線形次元削減を行うために半正定値プログラミングを使用するコンピュータサイエンスのアルゴリズムです。 MVUは、主成分分析の非線形一般化と見ることができます。
非線形次元削減アルゴリズムは、高次元データを低次元ユークリッドベクトル空間にマッピングしようと試みる。最大分散アンフォールディングは、多様な学習ファミリーのメンバーであり、アイソマップや局所的な線形埋め込みなどのアルゴリズムも含まれています。マニフォルド学習では、入力データは、より高次元のベクトル空間の内部に埋め込まれた低次元マニホールドからサンプリングされると仮定される。 MVUの背後にある主な直感は、多様体の局所的線形性を利用し、その基礎となる多様体のあらゆる点で局所近傍を保存するマッピングを作成することです。
MVUは、高次元入力ベクトルからいくつかの低次元ユークリッドベクトル空間へのマッピングを以下のステップで作成する。
近傍グラフが作成されます。各入力は、k個の最も近い入力ベクトル(ユークリッド距離メトリックに従う)に接続され、すべてのk最近傍点は互いに接続される。データが十分にサンプリングされた場合、得られるグラフは、基礎となるマニホールドの離散近似である。
近傍グラフは、半正定値プログラミングの助けを借りて展開されます。出力ベクトルを直接学習する代わりに、半正定値プログラミングは、近傍グラフに接続されていない任意の2つの入力間のペアワイズ距離を最大にする内積マトリックスを見つけ、最近接距離を保持することを目指しています。
最後に、学習された内積行列に多次元スケーリングを適用することにより、低次元埋め込みが得られる。
ユークリッド空間への低次元埋め込みを回復するための線形次元削減ステップの後に続く準決定的プログラミングを適用するステップは、Linial、London、およびRabinovichによって最初に提案された。