यादृच्छिक प्रक्षेपण

गणित और सांख्यिकी में, यादृच्छिक प्रक्षेपण एक ऐसी तकनीक है जिसका उपयोग यूक्लिडियन अंतरिक्ष में स्थित बिंदुओं के एक सेट के आयाम में कमी के लिए किया जाता है। अन्य विधियों की तुलना में यादृच्छिक प्रक्षेपण विधियों को उनकी शक्ति, सरलता और कम त्रुटि दर के लिए जाना जाता है. प्रायोगिक परिणामों के अनुसार, यादृच्छिक प्रक्षेपण दूरियों को अच्छी तरह से संरक्षित करता है, लेकिन अनुभवजन्य परिणाम विरल हैं। उन्हें यादृच्छिक अनुक्रमण नाम के तहत कई प्राकृतिक भाषा कार्यों में लागू किया गया है।

आयामीता में कमी

Main article: Dimensionality reduction

आयाम में कमी, जैसा कि नाम से पता चलता है, सांख्यिकी और मशीन सीखने से विभिन्न गणितीय विधियों का उपयोग करके यादृच्छिक चर की संख्या को कम कर रहा है। बड़े डेटा सेट के प्रबंधन और हेरफेर की समस्या को कम करने के लिए अक्सर आयाम में कमी का उपयोग किया जाता है। आयामीता में कमी की तकनीक आम तौर पर कई गुना की आंतरिक आयामीता को निर्धारित करने के साथ-साथ इसके प्रमुख दिशाओं को निकालने में रैखिक परिवर्तनों का उपयोग करती है। इस उद्देश्य के लिए विभिन्न संबंधित तकनीकें हैं, जिनमें शामिल हैं: प्रमुख घटक विश्लेषण, रैखिक विभेदक विश्लेषण, विहित सहसंबंध विश्लेषण, असतत कोसाइन परिवर्तन, यादृच्छिक प्रक्षेपण, आदि।

यादृच्छिक प्रक्षेपण तेजी से प्रसंस्करण समय और छोटे मॉडल आकारों के लिए त्रुटि की नियंत्रित मात्रा का व्यापार करके डेटा के आयाम को कम करने का एक सरल और कम्प्यूटेशनल रूप से कुशल तरीका है। यादृच्छिक प्रोजेक्शन मैट्रिसेस के आयाम और वितरण को नियंत्रित किया जाता है ताकि डेटासेट के किसी भी दो नमूनों के बीच जोड़ीदार दूरी को लगभग संरक्षित किया जा सके।

विधि

यादृच्छिक प्रक्षेपण के पीछे मुख्य विचार जॉनसन-लिंडनस्ट्रॉस लेम्मा में दिया गया है, जिसमें कहा गया है कि यदि सदिश स्थान में बिंदु पर्याप्त रूप से उच्च आयाम के हैं, तो उन्हें उपयुक्त निम्न-आयामी स्थान में इस तरह प्रक्षेपित किया जा सकता है जो बिंदुओं के बीच की दूरी को लगभग संरक्षित करता है।

यादृच्छिक प्रक्षेपण में, मूल डी-डायमेंशनल डेटा को एक के-डायमेंशनल (के << डी) सबस्पेस में एक यादृच्छिक का उपयोग करके प्रक्षेपित किया जाता है $k\times d$ - आयामी मैट्रिक्स जिसके स्तंभों की इकाई लंबाई है। मैट्रिक्स नोटेशन का उपयोग करना: यदि $X_{d\times N}$ एन डी-आयामी अवलोकनों का मूल सेट है, फिर $X_{k\times N}^{RP}=R_{k\times d}X_{d\times N}$ निम्न k-आयामी उप-स्थान पर डेटा का प्रक्षेपण है। रैंडम प्रोजेक्शन कम्प्यूटेशनल रूप से सरल है: रैंडम मैट्रिक्स R बनाएं और प्रोजेक्ट करें $d\times N$ ऑर्डर के K आयामों पर डेटा मैट्रिक्स X $O(dkN)$. यदि डेटा मैट्रिक्स X विरल है और प्रति स्तंभ लगभग c गैर-शून्य प्रविष्टियाँ हैं, तो इस ऑपरेशन की जटिलता क्रम की है $O(ckN)$.

गाऊसी यादृच्छिक प्रक्षेपण

गाऊसी वितरण का उपयोग करके यादृच्छिक मैट्रिक्स आर उत्पन्न किया जा सकता है। पहली पंक्ति एक यादृच्छिक इकाई वेक्टर है जिसे समान रूप से चुना गया है $S^{d-1}$. दूसरी पंक्ति अंतरिक्ष ऑर्थोगोनल से पहली पंक्ति तक एक यादृच्छिक इकाई वेक्टर है, तीसरी पंक्ति अंतरिक्ष ऑर्थोगोनल से पहली दो पंक्तियों तक एक यादृच्छिक इकाई वेक्टर है, और इसी तरह। इस प्रकार R को चुनने पर निम्नलिखित गुण संतुष्ट होते हैं:

• गोलाकार समरूपता: किसी भी ओर्थोगोनल मैट्रिक्स के लिए $A\in O(d)$, RA और R का वितरण समान है।
• लम्बवत: R की पंक्तियाँ एक दूसरे के लम्बवत हैं।
• सामान्यता: R की पंक्तियाँ इकाई-लंबाई वाले वैक्टर हैं।

अधिक कम्प्यूटेशनल रूप से कुशल यादृच्छिक अनुमान

अचलोपता ने दिखाया है कि गॉसियन वितरण को बहुत सरल वितरण द्वारा प्रतिस्थापित किया जा सकता है जैसे कि

$R_{i,j}={\sqrt {3}}\times {\begin{cases}+1&{\text{with probability }}{\frac {1}{6}}\\0&{\text{with probability }}{\frac {2}{3}}\\-1&{\text{with probability }}{\frac {1}{6}}\end{cases}}$

यह डेटाबेस अनुप्रयोगों के लिए कुशल है क्योंकि पूर्णांक अंकगणितीय का उपयोग करके संगणना की जा सकती है। में अधिक संबंधित अध्ययन किया जाता है। यह बाद में दिखाया गया कि स्पार्स जेएल ट्रांसफॉर्म पर काम में, वितरण को और भी विरल बनाते हुए पूर्णांक अंकगणित का उपयोग कैसे किया जाए, जिसमें प्रति स्तंभ बहुत कम गैर शून्य हैं। यह फायदेमंद है क्योंकि एक विरल एम्बेडिंग मैट्रिक्स का मतलब डेटा को कम आयाम में और भी तेज़ी से प्रोजेक्ट करने में सक्षम होना है।

परिमाणीकरण के साथ यादृच्छिक प्रक्षेपण

रैंडम प्रोजेक्शन को 1-बिट (साइन रैंडम प्रोजेक्शन) या मल्टी-बिट्स के साथ परिमाणीकरण (विवेकीकरण) द्वारा आगे बढ़ाया जा सकता है। यह सिमहैश का निर्माण खंड है, आरपी पेड़, और अन्य स्मृति कुशल आकलन और सीखने के तरीके।

बड़ा क्वासियोर्थोगोनल आधार (रैखिक बीजगणित)

जॉनसन-लिंडनस्ट्रॉस लेम्मा|जॉनसन-लिंडनस्ट्रॉस लेम्मा कहता है कि एक उच्च-आयामी अंतरिक्ष में वैक्टर के बड़े सेट को दूरी के अनुमानित संरक्षण के साथ बहुत कम (लेकिन अभी भी उच्च) आयाम n के स्थान में रैखिक रूप से मैप किया जा सकता है। इस आशय की व्याख्याओं में से एक एन-आयामी यूक्लिडियन अंतरिक्ष का घातीय रूप से उच्च क्वासियोर्थोगोनल आयाम है। एन-आयामी यूक्लिडियन अंतरिक्ष में लगभग ओर्थोगोनालिटी वैक्टर (आंतरिक उत्पाद स्थान के छोटे मूल्य के साथ) के घातीय रूप से बड़े (आयाम एन में) सेट हैं। यह अवलोकन उच्च-आयामी डेटा के डाटाबेस इंडेक्स में उपयोगी है। मशीन सीखने में यादृच्छिक सन्निकटन के तरीकों के लिए बड़े यादृच्छिक सेटों की क्वासियोर्थोगोनलिटी महत्वपूर्ण है। उच्च आयामों में, एक गोले पर (और कई अन्य वितरणों से) समवितरण से बेतरतीब ढंग से और स्वतंत्र रूप से चुने गए सदिशों की घातीय रूप से बड़ी संख्या एक के करीब संभावना के साथ लगभग ओर्थोगोनल हैं। इसका तात्पर्य यह है कि यादृच्छिक और स्वतंत्र रूप से चुने गए वैक्टरों के रैखिक संयोजनों द्वारा इस तरह के उच्च-आयामी स्थान के एक तत्व का प्रतिनिधित्व करने के लिए, यदि हम रैखिक संयोजनों में परिबद्ध गुणांक का उपयोग करते हैं, तो अक्सर घातीय रूप से बड़ी लंबाई के नमूने उत्पन्न करना आवश्यक हो सकता है। दूसरी ओर, यदि मनमाने ढंग से बड़े मूल्यों वाले गुणांकों की अनुमति है, तो यादृच्छिक रूप से उत्पन्न तत्वों की संख्या जो सन्निकटन के लिए पर्याप्त हैं, डेटा स्थान के आयाम से भी कम है।

कार्यान्वयन

• RandPro - यादृच्छिक प्रक्षेपण के लिए एक आर पैकेज
• [http://scikit-learn.org/stable/modules/random_projection.html sklearn.random_projection] - स्किकिट-लर्न पाइथन लाइब्रेरी से रैंडम प्रोजेक्शन के लिए एक मॉड्यूल
• वीका कार्यान्वयन [1]

यह भी देखें

• स्थानीयता-संवेदनशील हैशिंग
• रैंडम मैपिंग
• जॉनसन-लिंडनस्ट्रॉस लेम्मा

अग्रिम पठन

• Fodor, Imola K (2002). A survey of dimension reduction techniques (Report). CiteSeerX 10.1.1.8.5098.
• Menon, Aditya Krishna (2007). Random projections and applications to dimensionality reduction (Thesis). CiteSeerX 10.1.1.164.640.
• Ramdas, Aditya. A Random Introduction To Random Projections (Report). CiteSeerX 10.1.1.377.2593.