अर्ध निश्चित एम्बेडिंग

मैक्सिमम वेरिएंस अनफोल्डिंग (एमवीयू), जिसे सेमिडेफिनिट एंबेडिंग (एसडीई) के रूप में भी जाना जाता है, कंप्यूटर विज्ञान में एक कलन विधि है जो उच्च-आयामी समन्वित वेक्टरियल इनपुट डेटा की गैर-रैखिक आयामीता में कमी करने के लिए अर्ध निश्चित प्रोग्रामिंग का उपयोग करता है। यह अवलोकन से प्रेरित है कि कर्नेल प्रमुख घटक विश्लेषण (kPCA) डेटा डायमेंशनलिटी को कम नहीं करता है, क्योंकि यह मूल डेटा को आंतरिक-उत्पाद स्थान में गैर-रैखिक रूप से मैप करने के लिए कर्नेल चाल का लाभ उठाता है।

एल्गोरिथम

एमवीयू निम्न चरणों में उच्च आयामी इनपुट वैक्टर से कुछ निम्न आयामी यूक्लिडियन वेक्टर स्पेस में मैपिंग बनाता है:

1. एक पड़ोस (टोपोलॉजी) ग्राफ बनाया गया है। प्रत्येक इनपुट अपने k-निकटतम इनपुट वैक्टर (यूक्लिडियन दूरी मीट्रिक के अनुसार) से जुड़ा होता है और सभी k-निकटतम पड़ोसी एक दूसरे से जुड़े होते हैं। यदि डेटा को पर्याप्त रूप से नमूना लिया गया है, तो परिणामी ग्राफ अंतर्निहित कई गुना का असतत सन्निकटन है।
2. पड़ोस का ग्राफ अर्ध-निश्चित प्रोग्रामिंग की मदद से सामने आया है। आउटपुट वैक्टर को सीधे सीखने के बजाय, अर्ध-निश्चित प्रोग्रामिंग का उद्देश्य एक आंतरिक उत्पाद मैट्रिक्स को खोजना है जो निकटतम पड़ोसियों की दूरी को संरक्षित करते हुए पड़ोस के ग्राफ में जुड़े हुए किसी भी दो इनपुट के बीच जोड़ीदार दूरी को अधिकतम करता है।
3. निम्न-आयामी एम्बेडिंग अंततः सीखे हुए आंतरिक उत्पाद मैट्रिक्स पर बहुआयामी स्केलिंग के अनुप्रयोग द्वारा प्राप्त की जाती है।

यूक्लिडियन अंतरिक्ष में एक कम-आयामी एम्बेडिंग को पुनर्प्राप्त करने के लिए एक रैखिक आयामी कमी कदम के बाद अर्ध-निश्चित प्रोग्रामिंग को लागू करने के कदम पहले नाथन रैखिक, लंदन और राबिनोविच द्वारा प्रस्तावित किए गए थे।

अनुकूलन फॉर्मूलेशन

होने देना $X\,\!$ मूल इनपुट हो और $Y\,\!$ एम्बेडिंग हो। अगर $i,j\,\!$ दो पड़ोसी हैं, तो स्थानीय आइसोमेट्री बाधा जिसे संतुष्ट करने की आवश्यकता है:

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

होने देना $G,K\,\!$ का ग्रामियन मैट्रिक्स हो $X\,\!$ और $Y\,\!$ (अर्थात: $G_{ij}=X_{i}\cdot X_{j},K_{ij}=Y_{i}\cdot Y_{j}\,\!$). उपरोक्त बाधा को हम प्रत्येक पड़ोसी बिंदु के लिए व्यक्त कर सकते हैं $i,j\,\!$ की अवधि में $G,K\,\!$:

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

इसके अलावा, हम एम्बेडिंग को भी बाधित करना चाहते हैं $Y\,\!$ मूल पर केन्द्रित करने के लिए:

$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}$ जैसा कि ऊपर वर्णित है, पड़ोसी बिंदुओं की दूरियों को संरक्षित करने के अलावा, एल्गोरिथ्म का उद्देश्य प्रत्येक जोड़ी बिंदुओं की जोड़ीदार दूरी को अधिकतम करना है। अधिकतम किया जाने वाला उद्देश्य कार्य है:

$T(Y)={\dfrac {1}{2N}}\sum _{i,j}|Y_{i}-Y_{j}|^{2}$ सहजता से, ऊपर दिए गए फ़ंक्शन को अधिकतम करना बिंदुओं को एक दूसरे से जितना संभव हो उतना दूर खींचने के बराबर है और इसलिए कई गुना प्रकट होता है। स्थानीय आइसोमेट्री बाधा होने देना $\tau =max\{\eta _{ij}|Y_{i}-Y_{j}|^{2}\}\,\!$ कहाँ

$\eta _{ij}:={\begin{cases}1&{\mbox{if}}\ i{\mbox{ is a neighbour of }}j\\0&{\mbox{otherwise}}.\end{cases}}$

उद्देश्य फलन को अपसरण (अनंत में जाने) से रोकता है।

चूँकि ग्राफ में N बिंदु हैं, किन्हीं दो बिंदुओं के बीच की दूरी $|Y_{i}-Y_{j}|^{2}\leq N\tau \,\!$. इसके बाद हम उद्देश्य समारोह को निम्नानुसार बाध्य कर सकते हैं:

$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}}\,\!$

उद्देश्य फ़ंक्शन को ग्राम मैट्रिक्स के रूप में विशुद्ध रूप से फिर से लिखा जा सकता है:

${\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{aligned}}\,\!$

अंत में, अनुकूलन को इस प्रकार तैयार किया जा सकता है:

${\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}}$ ग्राम मैट्रिक्स के बाद $K\,\!$ सेमीडिफिनिट प्रोग्रामिंग, आउटपुट द्वारा सीखा जाता है $Y\,\!$ Cholesky अपघटन के माध्यम से प्राप्त किया जा सकता है।

विशेष रूप से, ग्राम मैट्रिक्स को इस रूप में लिखा जा सकता है $K_{ij}=\sum _{\alpha =1}^{N}(\lambda _{\alpha }V_{\alpha i}V_{\alpha j})\,\!$ कहाँ $V_{\alpha i}\,\!$ ईजेनवेक्टर का i-वाँ तत्व है $V_{\alpha }\,\!$ आइगेनवैल्यू का $\lambda _{\alpha }\,\!$. इससे यह पता चलता है कि $\alpha \,\!$आउटपुट का -वाँ तत्व $Y_{i}\,\!$ है ${\sqrt {\lambda _{\alpha }}}V_{\alpha i}\,\!$.

यह भी देखें

• स्थानीय रूप से रैखिक एम्बेडिंग
• आइसोमेट्री (गणित) (बहुविकल्पी) | आइसोमेट्री (गणित)
• स्थानीय स्पर्शरेखा अंतरिक्ष संरेखण
• रीमैनियन कई गुना
• ऊर्जा न्यूनीकरण

संदर्भ

• 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.{{cite journal}}: CS1 maint: multiple names: authors list (link)
• 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.{{cite conference}}: CS1 maint: multiple names: authors list (link)
• 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.

अतिरिक्त सामग्री

• किलियन क्यू. वेनबर्गर का एमवीयू मैटलैब कोड

श्रेणी:कम्प्यूटेशनल सांख्यिकी श्रेणी:आयाम में कमी श्रेणी:अनुकूलन एल्गोरिद्म और विधियां