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

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

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

Main article: आयामीता में कमी

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

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

विधि

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

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