세미데피니트 임베딩

Semidefinite 임베딩(SDE)이라고도 하는 MVU(Maximum Discovery Expanding, MVU)는 Semidefinite 프로그래밍을 사용하여 고차원 벡터럴 입력 데이터의 비선형 치수 감소를 수행하는 컴퓨터 과학의 알고리즘이다.^[1][2][3]

커널 주성분 분석(kPCA)은 커널 트릭을 활용해 원본 데이터를 내부 제품 공간에 비선형적으로 매핑하기 ^[4]때문에 데이터 차원성을 줄이지 않는다는 관측에 동기부여가 된다.

알고리즘.

MVU는 다음 단계에 따라 고차원 입력 벡터에서 일부 저차원 유클리드 벡터 공간에 대한 매핑을 생성한다.^[5]

1. 이웃 그래프가 생성된다.각 입력은 k-가장 가까운 입력 벡터(유클리드 거리 측정기준에 따라)와 연결되며 모든 k-가장 가까운 이웃이 서로 연결된다.데이터가 충분히 샘플링되는 경우, 결과 그래프는 기저 다지관의 이산형 근사치가 된다.
2. 이웃 그래프는 세미더파인 프로그래밍의 도움으로 "접히지 않은" 것이다.반피니트 프로그래밍은 출력 벡터를 직접 학습하는 대신 가장 가까운 인접 거리를 보존하면서 인접 그래프로 연결되지 않은 두 입력 사이의 쌍방향 거리를 최대화하는 내부 제품 매트릭스를 찾는 것을 목표로 한다.
3. 학습된 내부 제품 매트릭스에 다차원 스케일링을 적용함으로써 저차원 임베딩이 최종적으로 얻어진다.

유클리드 공간에 저차원적으로 내장되는 것을 복구하기 위해 세미데피나이트 프로그래밍을 적용하는 단계와 선형 차원성 감소 단계가 먼저 리니얼, 런던, 라비노비치에 의해 제안되었다.^[6]

최적화 공식

$X{\displaystyle }$ $displaystyle X\,\!}$을(를) 원래 입력으로$$ 하고 $Y{\displaystyle }$ $displaystyle Y\,\!}$을(를) 임베딩으로 한다$$.$i{\displaystyle }$, ${\displaystyle j}$ $displaystyle i,j\,\!}$이(가) 두 이웃이라면$$, 만족해야 할 국부 등위계량 제약조건은 다음과 같다.^[7][8][9]

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

$G{\displaystyle }$, ${\displaystyle K}$ $displaystyle G,K\,\!}$을(를) $X{\displaystyle }$ $displaystyle X\,\}$ 및 $Y{\displaystyle }$ $displaystyle Y\,\!}$의 Gram 행렬로 두십시오$$($$예:$displaystyle G_{ij}=X_{i}\cdot X_{j},K_{ij}=$$Y_{i}\cdot Y_{j}\,\!}$ ).$$$우리$는 G${\displaystyle }$,${\displaystyle }$${\displaystyle K}$, K , K , K , K , K ,$K$$\$ $,\$의 용어로$$ 모든 인접 $포인트$에 대해 위의 제약조건을 표현할 수 있다$.$^[10][11]

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

또한 $내장형{\displaystyle }$ Y${\displaystyle }${\$displaystyle Y\,\!}$을(를) 오리진 중앙에 배치하도록$$ 제한하고자 한다.^[12][13][14]

${\displaystyle 0= \sum _{i}Y_{i} ^{2}\왼쪽 화살표(\sum _{i})Y_{i}\cdot(\sum _{i})Y_{i}}\좌우경로 \sum _{i}Y_{i}\cdot Y_{j}\좌우경로 \sum _{i,j}K_{ij}}}}}$

위에서 설명한 것처럼, 인접 점의 거리를 제외하고, 알고리즘은 모든 점 쌍의 쌍별 거리를 최대화하는 것을 목표로 한다.최대화할 목표 함수는 다음과 같다.^[15][16][17]

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

직관적으로 위의 기능을 최대화하는 것은 가능한 한 서로 멀리 떨어져 있는 점을 잡아당겨 다지관을 "풀어내"는 것과 같다.국부 등계 구속조건

$\tau {\displaystyle }$= m ${\displaystyle a}$ ${\displaystyle x}$ {${\displaystyle i_{}}$ i ${\displaystyle y_{}}$ ${\displaystyle i{}_{}{}_{}}$- ${\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\displaystyle {}^{}{}_{}{}^{\mathrm{}}\}}$ {\$displaystyle \tau =max\{\eta_{i}-Y_{j}$^{$2}\}\,\}$서 i: 이 j 이면 .$style \eta _{j:$$={\package{case}1&{\mbox{if}\i{\mbox{{}}}는 }j\\\0&{\mbox{mbox}}$$의 이웃이다.$$\end{case}}}$

객관적 기능이 (무한으로) 이탈하는 것을 방지한다.

그래프에 N개의 점이 있기 때문에, 두 점 ${\displaystyle Y{}_{}}$i - ${\displaystyle Y_{}}$ ${\displaystyle {}^{}{}_{}{}^{\mathrm{}}}$ 2${\displaystyle {}^{}n}$ N ${\displaystyle \tau }${\$displaystyle Y_{i}-Y_{j}$^{$2}\leq$N\$tau \,\}.$ 그러면 다음과 같이 목표 함수를 바인딩할 수 있다$.$^[19][20]

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

객관적 함수는 순전히 Gram 행렬의 형태로 다시 쓸 수 있다.^[21][22][23]

${\displaystyle {\begin}T(Y)&}={\dfrac {1}{2N}\sum _{i,j} Y_{i}-Y_{j} ^{2}\\&}={\dfrac {1}{2}N}\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{arged}\,\!}$

마지막으로 최적화는 다음과 같이 공식화할 수 있다.^[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_{j}-G_{ij}-G_{ji}-{ji}+K_{j}-K_{ij}-K_{ji}-K_{ji},\j{mbox{where }\}\{ij}=1,\ended}}}}}}에 대한 자세한 내용은 다음과 같다.$

그램 매트릭스 $K{\displaystyle }$ $displaystyle K\,\!}$을(를) 세미더파인 프로그래밍으로 학습한$$ 후, 출력 $Y{\displaystyle }$ $displaystyle Y\,\!}$을(를) 슐레스키 분해를 통해 얻을$$ 수 있다.

In particular, the Gram matrix can be written as ${\displaystyle K_{ij}=\sum _{\alpha =1}^{N}(\lambda _{\alpha }V_{\alpha i}V_{\alpha j})\,\!}$ where ${\displaystyle V_{\alpha i}\,\!}$ is the i-th element of eigenvector ${\displaystyle V_{\alpha }\,$고유값 ${\displaystyle {\alpha }_{}}$ $displaystyle \displayda _{\property }\,\!}$의 $\backslash !\}.$^[27][28]

이어서 $출력{\displaystyle {}_{}}$ ${\displaystyle {Yi}_{}}$의 $\alpha {\displaystyle }${\$displaystyle$$$\$alpha$$$$\,\!}$ -th번째$$ $요소$는 ${\displaystyle \sqrt{{}_{}}{}_{}}$ V ${\displaystyle {\alpha }_{}}$ i $displaystyle${\$sqrt${\\$lambda _}{\\lapa$ }$V_{\alpha$ i$\},\backslash !\}$^[29][30]이다.

참고 항목

• 로컬 선형 내장
• 등위법(동음이의)
• 로컬 접선 공간 정렬
• 리만 다양체
• 에너지 최소화

메모들

참조

• Linial, London and Rabinovich, Nathan, Eran and Yuri (1995). "The geometry of graphs and some of its algorithmic applications". Combinatorica. 15 (2): 215–245. doi:10.1007/BF01200757. S2CID 5071936.
• Weinberger, Sha and Saul, Kilian Q., Fei and Lawrence K. (4 July 2004a). Learning a kernel matrix for nonlinear dimensionality reduction. Proceedings of the Twenty First International Conference on Machine Learning (ICML 2004). Banff, Alberta, Canada.
• Weinberger and Saul, Kilian Q. and Lawrence K. (27 June 2004b). Unsupervised learning of image manifolds by semidefinite programming. 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Vol. 2.
• Weinberger and Saul, Kilian Q. and Lawrence K. (1 May 2006). "Unsupervised learning of image manifolds by semidefinite programming" (PDF). International Journal of Computer Vision. 70: 77–90. doi:10.1007/s11263-005-4939-z. S2CID 291166.
• Lawrence, Neil D (2012). "A unifying probabilistic perspective for spectral dimensionality reduction: insights and new models". Journal of Machine Learning Research. 13 (May): 1612. arXiv:1010.4830. Bibcode:2010arXiv1010.4830L.

추가재료

• 킬리안 Q.와인버거 MVU 매트랩 코드