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

From Vigyanwiki
Revision as of 08:49, 15 June 2023 by Manidh (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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

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

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

विधि

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

यादृच्छिक प्रक्षेपण में, मूल d-आयामी डेटा को एक k-आयामी (k << d) उप-स्थान पर प्रक्षेपित किया जाता है, एक यादृच्छिक - आयामी आव्यूह R का उपयोग करके जिसके स्तंभों की इकाई लंबाई होती है। आव्यूह संकेतन का उपयोग करना: यदि N d-आयामी प्रेक्षणों का मूल सेट है तो निम्न k-आयामी उप-स्थान पर डेटा का प्रक्षेपण है। यादृच्छिक प्रक्षेपण कम्प्यूटेशनल रूप से सरल है: यादृच्छिक आव्यूह "R" बनाएं और डेटा आव्यूह X को क्रम के K आयामों पर प्रोजेक्ट करें। यदि डेटा आव्यूह X विरल है और प्रति स्तंभ लगभग c अशून्य प्रविष्टियों के साथ है, तो इस ऑपरेशन की जटिलता क्रम की है।[3]

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

गाऊसी वितरण का उपयोग करके यादृच्छिक आव्यूह आर उत्पन्न किया जा सकता है। पहली पंक्ति एक यादृच्छिक इकाई सदिश है जिसे समान रूप से चुना गया है दूसरी पंक्ति स्थान ऑर्थोगोनल से पहली पंक्ति तक एक यादृच्छिक इकाई सदिश है तीसरी पंक्ति स्थान ऑर्थोगोनल से पहली दो पंक्तियों तक एक यादृच्छिक इकाई सदिश है और इसी तरह। इस प्रकार R को चुनने पर निम्नलिखित गुण संतुष्ट होते हैं:

  • गोलाकार समरूपता: किसी भी ओर्थोगोनल आव्यूह के लिए , RA और R का वितरण समान है।
  • लम्बवत: R की पंक्तियाँ एक दूसरे के लम्बवत हैं।
  • सामान्यता: R की पंक्तियाँ इकाई-लंबाई वाले सदिश हैं।

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

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

यह डेटाबेस अनुप्रयोगों के लिए कुशल है क्योंकि पूर्णांक अंकगणितीय का उपयोग करके संगणना की जा सकती है। में अधिक संबंधित अध्ययन किया जाता है।[5]

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

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

रैंडम प्रक्षेपण को 1-बिट (साइन यादृच्छिक प्रक्षेपण) या मल्टी-बिट्स के साथ परिमाणीकरण (विवेकीकरण) द्वारा आगे बढ़ाया जा सकता है।[7] [8] यह सिमहैश आरपी ट्री और अन्य मेमोरी कुशल आकलन और सीखने के विधि का निर्माण खंड है।[9][10]

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

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

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

कार्यान्वयन

  • RandPro - यादृच्छिक प्रक्षेपण के लिए एक आर पैकेज [14][15]
  • एसकेलर्न .यादृच्छिक प्रक्षेपण - स्किकिट-लर्न पाइथन लाइब्रेरी से रैंडम प्रोजेक्शन के लिए एक मॉड्यूल
  • वीका कार्यान्वयन [1]

यह भी देखें

संदर्भ

  1. Ella, Bingham; Heikki, Mannila (2001). "Random projection in dimensionality reduction: Applications to image and text data". KDD-2001: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: Association for Computing Machinery. pp. 245–250. CiteSeerX 10.1.1.24.5135. doi:10.1145/502512.502546.
  2. Johnson, William B.; Lindenstrauss, Joram (1984). "Extensions of Lipschitz mappings into a Hilbert space". Conference in Modern Analysis and Probability (New Haven, Conn., 1982). Contemporary Mathematics. Vol. 26. Providence, RI: American Mathematical Society. pp. 189–206. doi:10.1090/conm/026/737400. ISBN 9780821850305. MR 0737400. S2CID 117819162..
  3. Bingham, Ella; Mannila, Heikki (May 6, 2014). "Random projection in dimensionality reduction: Applications to image and text data" (PDF).
  4. Achlioptas, Dimitris (2001). "Database-friendly random projections". डेटाबेस सिस्टम के सिद्धांतों पर बीसवीं ACM SIGMOD-SIGACT-SIGART संगोष्ठी की कार्यवाही - PODS '01. pp. 274–281. CiteSeerX 10.1.1.28.6652. doi:10.1145/375551.375608. ISBN 978-1581133615. S2CID 2640788.
  5. Li, Ping; Hastie, Trevor; Church, Kenneth (2006). "Very sparse random projections". 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (1): 287–296. doi:10.1145/1150402.1150436. ISBN 1595933395. S2CID 7995734.
  6. Kane, Daniel M.; Nelson, Jelani (2014). "Sparser Johnson-Lindenstrauss Transforms". Journal of the ACM. 61 (1): 1–23. arXiv:1012.1577. doi:10.1145/2559902. MR 3167920. S2CID 7821848.
  7. Charikar, Moses (2002). "Similarity estimation techniques from rounding algorithms". 34-th Annual ACM Symposium on Theory of Computing. 1 (1): 380–388. doi:10.1145/509907.509965. ISBN 1581134959. S2CID 4229473.
  8. Freund, Yoav; Dasgupta, Sanjoy; Kabra, Mayank; Verma, Nakul (2007). "Learning the structure of manifolds using random projections". 20th International Conference on Neural Information Processing Systems. 1 (1): 473–480.
  9. Boufounos, Petros; Baraniuk, Richard (2008). "1-bit Compressive Sensing". 42nd Annual Conference on Information Sciences and Systems. 1 (1): 16–21. doi:10.1109/CISS.2008.4558487. S2CID 206563812.
  10. Li, Xiaoyun; Li, Ping (2019). "Generalization error analysis of quantized compressive learning". 33rd International Conference on Neural Information Processing Systems. 1: 15150–15160.
  11. Kainen, Paul C.; Kůrková, Věra (1993), "Quasiorthogonal dimension of Euclidean spaces", Applied Mathematics Letters, 6 (3): 7–10, doi:10.1016/0893-9659(93)90023-G, MR 1347278
  12. Hecht-Nielsen, R. (1994). "Context vectors: General-purpose approximate meaning representations self-organized from raw data". In Zurada, Jacek M.; Marks, Robert Jackson; Robinson, Charles J. (eds.). Computational Intelligence: Imitating Life. IEEE. pp. 43–56. ISBN 978-0-7803-1104-6.
  13. Gorban, Alexander N.; Tyukin, Ivan Y.; Prokhorov, Danil V.; Sofeikov, Konstantin I. (2016). "Approximation with Random Bases: Pro et Contra". Information Sciences. 364–365: 129–145. arXiv:1506.04631. doi:10.1016/j.ins.2015.09.021. S2CID 2239376.
  14. Ravindran, Siddharth (2020). "के-निकटतम पड़ोसी (के-एनएन) का उपयोग करके बड़े डेटा वर्गीकरण में आयाम में कमी के लिए डेटा-स्वतंत्र पुन: प्रयोज्य प्रक्षेपण (डीआईआरपी) तकनीक". National Academy Science Letters. 43: 13–21. doi:10.1007/s40009-018-0771-6. S2CID 91946077.
  15. Siddharth, R.; Aghila, G. (July 2020). "RandPro- आर में उच्च आयामी बहुभिन्नरूपी डेटा विश्लेषण के लिए यादृच्छिक प्रक्षेपण-आधारित सुविधा निष्कर्षण का एक व्यावहारिक कार्यान्वयन". SoftwareX. 12: 100629. Bibcode:2020SoftX..1200629S. doi:10.1016/j.softx.2020.100629.


अग्रिम पठन