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

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

यह अवलोकन से प्रेरित है कि कर्नेल प्रमुख घटक विश्लेषण (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\,\!$ चोल्स्की अपघटन के माध्यम से प्राप्त किया जा सकता है।

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

इससे यह पता चलता है कि निष्पाद $Y_{i}\,\!$ का $\alpha \,\!$-वाँ तत्व ${\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.

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

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

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