半正定値埋め込み

最大分散展開（MVU）は半正定値埋め込み（SDE）とも呼ばれ、半正定値計画法を使用して高次元ベクトル入力データの非線形次元削減を実行するコンピュータサイエンスのアルゴリズムです。^{[1] [2] [3]}

これは、カーネル主成分分析（kPCA）がカーネルトリックを活用して元のデータを内積空間に非線形にマッピングするため、データの次元を削減しないという観察に基づいています^[4]。

MVUは、次の手順で高次元の入力ベクトルから低次元のユークリッドベクトル空間へのマッピングを作成します。^[5]

1. 近傍グラフが作成されます。各入力は、その k 近傍入力ベクトル (ユークリッド距離メトリックに従って) に接続され、すべての k 近傍は互いに接続されます。データが十分にサンプリングされている場合、結果のグラフは、基礎となる多様体の離散近似になります。
2. 近傍グラフは、半正定値計画法の助けを借りて「展開」されます。半正定値計画法は、出力ベクトルを直接学習する代わりに、近傍グラフで接続されていない任意の 2 つの入力間のペアワイズ距離を最大化し、最近傍距離を維持する内積行列を見つけることを目指します。
3. 最終的に、学習された内積行列に多次元スケーリングを適用することで、低次元の埋め込みが得られます。

半正定値計画法を適用し、その後に線形次元削減ステップを実行して低次元の埋め込みをユークリッド空間に復元する手順は、Linial、London、Rabinovichによって最初に提案されました。^[6]

を元の入力とし、を埋め込みとする。2つの隣接点がある場合、満たすべき局所等長制約は次の通りである: ^{[7] [8] [9]}${\displaystyle X\,\!}$${\displaystyle Y\,\!}$${\displaystyle i,j\,\!}$

${\displaystyle |X_{i}-X_{j}|^{2}=|Y_{i}-Y_{j}|^{2}\,\!}$

を とのグラム行列とする（すなわち）。すべての近傍点に対する上記の制約は の項で表現できる：^{[10] [11]}${\displaystyle G,K\,\!}$${\displaystyle X\,\!}$${\displaystyle Y\,\!}$${\displaystyle G_{ij}=X_{i}\cdot X_{j},K_{ij}=Y_{i}\cdot Y_{j}\,\!}$${\displaystyle i,j\,\!}$${\displaystyle G,K\,\!}$

${\displaystyle G_{ii}+G_{jj}-G_{ij}-G_{ji}=K_{ii}+K_{jj}-K_{ij}-K_{ji}\,\!}$

さらに、埋め込みの中心を原点に制約することも必要です。^{[12] [13] [14]}${\displaystyle Y\,\!}$

${\displaystyle 0=|\sum _{i}Y_{i}|^{2}\Leftrightarrow (\sum _{i}Y_{i})\cdot (\sum _{i}Y_{i})\Leftrightarrow \sum _{i,j}Y_{i}\cdot Y_{j}\Leftrightarrow \sum _{i,j}K_{ij}}$

上で述べたように、近傍点間の距離が保存されることを除いて、アルゴリズムは各点のペア間の距離を最大化することを目指します。最大化すべき目的関数は^{[15] [16] [17]です。}

${\displaystyle T(Y)={\dfrac {1}{2N}}\sum _{i,j}|Y_{i}-Y_{j}|^{2}}$

直感的に、上記の関数を最大化することは、点を可能な限り互いに引き離すことと同等であり、したがって多様体を「展開」する。局所等長制約^[18]

どこに ${\displaystyle \tau =max\{\eta _{ij}|Y_{i}-Y_{j}|^{2}\}\,\!}$${\displaystyle \eta _{ij}:={\begin{cases}1&{\mbox{if}}\ i{\mbox{ は }}j\\0&{\mbox{otherwise}}\end{cases}}}$

目的関数が発散する（無限大になる）のを防ぎます。

グラフにはN点あるので、任意の2点間の距離は となる。目的関数は次のように制限できる。^{[19] [20]}${\displaystyle |Y_{i}-Y_{j}|^{2}\leq N\tau \,\!}$

${\displaystyle T(Y)={\dfrac {1}{2N}}\sum _{i,j}|Y_{i}-Y_{j}|^{2}\leq {\dfrac {1}{ 2N}}\sum _{i,j}(N\tau )^{2}={\dfrac {N^{3}\tau ^{2}}{2}}\,\!}$

目的関数は、純粋にグラム行列の形で書き直すことができる: ^{[21] [22] [23]}

${\displaystyle {\begin{aligned}T(Y)&{}={\dfrac {1}{2N}}\sum _{i,j}|Y_{i}-Y_{j}|^{2}\\&{}={\dfrac {1}{2N}}\sum _{i,j}(Y_{i}^{2}+Y_{j}^{2}-Y_{i}\cdot Y_{j}-Y_{j}\cdot Y_{i})\\&{}={\dfrac {1}{2N}}(\sum _{i,j}Y_{i}^{2}+\sum _{i,j}Y_{j}^{2}-\sum _{i,j}Y_{i}\cdot Y_{j}-\sum _{i,j}Y_{j}\cdot Y_{i})\\&{}={\dfrac {1}{2N}}(\sum _{i,j}Y_{i}^{2}+\sum _{i,j}Y_{j}^{2}-0-0)\\&{}={\dfrac {1}{N}}(\sum _{i}Y_{i}^{2})={\dfrac {1}{N}}(Tr(K))\\\end{整列}}\,\!}$

最終的に、最適化は次のように定式化される。^{[24] [25] [26]}

${\displaystyle {\begin{aligned}&{\text{Maximize}}&&Tr(\mathbf {K} )\\&{\text{subject to}}&&\mathbf {K} \succeq 0,\sum _{ij}\mathbf {K} _{ij}=0\\&{\text{and}}&&G_{ii}+G_{jj}-G_{ij}-G_{ji}=K_{ii}+K_{jj}-K_{ij}-K_{ji},\forall i,j{\mbox{ where }}\eta _{ij}=1,\end{aligned}}}$

グラム行列を半正定値計画法で学習した後、コレスキー分解によって出力を得ることができます。 ${\displaystyle K\,\!}$${\displaystyle Y\,\!}$

特に、グラム行列は次のように表すことができます。ここで、は固有値 の固有ベクトルのi番目の要素です。^{[27] [28]}${\displaystyle K_{ij}=\sum _{\alpha =1}^{N}(\lambda _{\alpha }V_{\alpha i}V_{\alpha j})\,\!}$${\displaystyle V_{\alpha i}\,\!}$${\displaystyle V_{\alpha }\,\!}$${\displaystyle \lambda _{\alpha }\,\!}$

したがって、出力の-番目の要素はである。^{[29] [30]}${\displaystyle \alpha \,\!}$${\displaystyle Y_{i}\,\!}$${\displaystyle {\sqrt {\lambda _{\alpha }}}V_{\alpha i}\,\!}$

• 局所線形埋め込み
• 等長法（曖昧さ回避）
• ローカル接線空間アライメント
• リーマン多様体
• エネルギー最小化

• Linial, London および Rabinovich, Nathan, Eranおよび Yuri (1995)。「グラフの幾何学とそのアルゴリズム的応用のいくつか」。Combinatorica。15 ( 2 ) : 215–245。doi :10.1007/BF01200757。S2CID 5071936  。{{cite journal}}: CS1 maint: multiple names: authors list (link)
• Weinberger, Sha、Saul, Kilian Q.、Fei、Lawrence K. (2004 年 7 月 4 日)。非線形次元削減のためのカーネル マトリックスの学習。第 21 回国際機械学習会議 (ICML 2004) の議事録。カナダ、アルバータ州バンフ。{{cite conference}}: CS1 maint: multiple names: authors list (link)
• Weinberger および Saul、Kilian Q.、Lawrence K. (2004 年 6 月 27 日 b)。半正定値計画法による画像多様体の教師なし学習。2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition。第 2 巻。
• Weinberger および Saul、Kilian Q.、Lawrence K. (2006 年 5 月 1 日)。「半正定値計画法による画像多様体の教師なし学習」(PDF)。International Journal of Computer Vision。70 : 77–90。doi : 10.1007 /s11263-005-4939-z。S2CID 291166  。
• Lawrence, Neil D (2012)。「スペクトル次元削減のための統一的な確率的視点: 洞察と新しいモデル」。Journal of Machine Learning Research。13 ( 5 月): 1612。arXiv : 1010.4830。Bibcode : 2010arXiv1010.4830L 。

• Kilian Q. Weinberger の MVU Matlab コード