Semidefinite inbäddning

Maximum Variance Unfolding (MVU) , även känd som Semidefinite Embedding (SDE), är en algoritm inom datavetenskap som använder semidefinite programmering för att utföra icke-linjär dimensionalitetsreduktion av högdimensionell vektoriell indata.

Det motiveras av observationen att kärnans principal komponentanalys (kPCA) inte minskar datadimensionaliteten, eftersom den utnyttjar Kernel-tricket för att icke-linjärt mappa originaldata till ett inre produktutrymme .

Algoritm

MVU skapar en mappning från de högdimensionella ingångsvektorerna till något lågdimensionellt euklidiskt vektorutrymme i följande steg:

En grannskapsgraf skapas. Varje ingång är ansluten med sina k-närmaste ingångsvektorer (enligt euklidisk avståndsmetrik) och alla k-närmaste grannar är anslutna till varandra. Om data samplas tillräckligt bra, är den resulterande grafen en diskret approximation av det underliggande grenröret.
Grannskapsgrafen "viks upp" med hjälp av semidefinite programmering. Istället för att lära sig utgångsvektorerna direkt, syftar den semidefinita programmeringen till att hitta en inre produktmatris som maximerar de parvisa avstånden mellan två valfria ingångar som inte är anslutna i grannskapsgrafen samtidigt som de närmaste grannarnas avstånd bevaras.
Den lågdimensionella inbäddningen erhålls slutligen genom applicering av flerdimensionell skalning på den inlärda inre produktmatrisen.

Stegen att tillämpa semidefinite programmering följt av ett steg för att reducera linjär dimensionalitet för att återställa en lågdimensionell inbäddning i ett euklidiskt rum föreslogs först av Linial , London och Rabinovich.

Optimeringsformulering

Låt $X\,\!$ vara den ursprungliga ingången och $Y\,\!$ vara inbäddningen. Om $i,j\,\!$ är två grannar, då är den lokala isometrirestriktionen som måste uppfyllas:

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

Låt $G,K\,\!$ vara grammatriserna för $X\,\!$ och $Y\,\!$ (dvs: $G_{ij}=X_{i}\cdot X_{j},K_{ij}=Y_{i}\cdot Y_{j}\,\ !$ ). Vi kan uttrycka ovanstående begränsning för varje grannpunkt $i,j\,\!$ i termer av $G,K\,\!$ :

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

Dessutom vill vi också begränsa inbäddningen $Y\,\!$ att centrera vid origo:

$0=|\summa _{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}$

Som beskrivits ovan, förutom att avstånden för närliggande punkter bevaras, syftar algoritmen till att maximera det parvisa avståndet för varje par av punkter. Den objektiva funktionen som ska maximeras är:

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

Intuitivt är maximering av funktionen ovan likvärdigt med att dra punkterna så långt bort från varandra som möjligt och därför "vika ut" grenröret. Den lokala isometri-restriktionen

Låt ${\displaystyle \tau =max\{\eta _{ij}|Y_{i}-Y_{j}|^{2}\}\,\!} där$ η $\eta _{ij}:={\begin{cases}1&{\mbox{if}}\ i{\mbox{ är en granne till }}j\\0&{\mbox{annars}}.\ slut{cases}}$

förhindrar att objektivfunktionen divergerar (går till oändligheten).

Eftersom grafen har N punkter, är avståndet mellan två valfria punkter $|Y_{i}-Y_{j}|^{2}\leq N\tau \,\!$ . Vi kan sedan binda den objektiva funktionen enligt följande:

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

Den objektiva funktionen kan skrivas om rent i form av grammatrisen:

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

Slutligen kan optimeringen formuleras som:

${\begin{aligned}&{\text{Maximize}}&&Tr(\mathbf {K} )\\&{\text{med förbehåll för}}&&\ 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{ där }}\eta _{ij}=1,\end{aligned }}$

Efter att grammatrisen $K\,\!$ har lärts in genom semidefinite programmering, kan utgången $Y\,\!$ erhållas via Cholesky-dekomponering .

I synnerhet kan grammatrisen skrivas som $K_{ij}=\sum _{\alpha =1}^{N} (\lambda _{\alpha }V_{\alpha i}V_{\alpha j})\,\!$ där $V_{\alpha i}\,\!$ är det i:te elementet av egenvektor $V_{\alpha }\,\!$ av egenvärdet $\lambda _{\alpha }\,\!$ .