On the Pseudo-Mixing of Kac's Walk

उच्च-आयामी गणित की दुनिया में, एक मौलिक चुनौती है: सैकड़ों या हजारों दिशाओं वाले स्थान में वास्तव में एक यादृच्छिक (random) रोटेशन कैसे उत्पन्न किया जाए। कल्पना कीजिए कि आप एक हज़ार दीवारों वाले कमरे में एक दिशा चुनने की कोशिश कर रहे हैं; एक "यादृच्छिक" चुनाव का अर्थ है कि प्रत्येक दिशा समान रूप से संभावित है, जिसमें किसी भी कोने की ओर कोई छिपा हुआ झुकाव नहीं है। कंप्यूटर विज्ञान और सांख्यिकी में, इस अवधारणा को 'हाार माप' (Haar measure) के रूप में औपचारिक रूप दिया गया है, जो रोटेशन का एक आदर्श, समान वितरण है। दशकों से, शोधकर्ता डेटा संपीड़न (data compression), क्रिप्टोग्राफी और मशीन लर्निंग के लिए एल्गोरिदम बनाने के लिए इसी आदर्श यादृच्छिकता पर भरोसा करते आए हैं। हालाँकि, इस वितरण का सटीक रूप से पालन करने वाला मैट्रिक्स बनाना कम्प्यूटेशनल रूप से महंगा है, जिसमें अक्सर इतना समय और मेमोरी लगता है कि यह बड़े पैमाने की समस्याओं के लिए अव्यवहारिक हो जाता है।

इस समस्या को हल करने के लिए, वैज्ञानिक लंबे समय से 'कैक्स वॉक' (Kac's walk) नामक एक चतुर शॉर्टकट का उपयोग करते आए हैं। एक पूर्ण यादृच्छिक रोटेशन को शून्य से बनाने के बजाय, यह विधि एक निश्चित आकार से शुरू होती है और इसके आयामों के जोड़ों पर बार-बार छोटे, यादृच्छिक घुमाव (twists) लागू करती है। इसे एक कठोर वस्तु को लेने और एक बार में दो आयामों में उसे बार-बार यादृच्छिक रूप से घुमाने के रूप में सोचें। आशा हमेशा यह रही है कि इन छोटे घुमावों के बाद, वस्तु एक पूर्ण रूप से यादृच्छिक वस्तु के समान दिखाई देगी, भले ही वह सख्त गणितीय अर्थों में तकनीकी रूप से उस स्थिति तक न पहुँची हो। यह विचार व्यवहार में इतना सफल रहा है कि इंजीनियर गणनाओं को कई गुना तेज करने के लिए इन "कैक्स मैट्रिसेस" का उपयोग कर रहे हैं, यह विश्वास करते हुए कि यह शॉर्टकट वास्तविक दुनिया के अनुप्रयोगों के लिए पर्याप्त रूप से काम करता है। लेकिन लंबे समय तक, गणितज्ञ यह सिद्ध नहीं कर सके कि यह शॉर्टकट क्यों सुरक्षित है; वे केवल यह जानते थे कि इस प्रक्रिया को पारंपरिक अर्थों में वास्तव में यादृच्छिक होने में बहुत लंबा समय लगता है, जिससे प्रयोगशाला में जो काम करता था और कागज पर जो सिद्ध किया जा सकता था, उसके बीच एक अंतर बना रहा।

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

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

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

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

तत्काल एल्गोरिथम सुधारों से परे, यह कार्य हमें जटिल प्रणालियों में यादृच्छिकता को समझने के बारे में एक नया दृष्टिकोण प्रदान करता है। यह सुझाव देता है कि कई उपयोगी कार्यों के लिए, "कम्प्यूटेशनल" मिक्सिंग समय—वह समय जब एक प्रणाली कंप्यूटर के लिए यादृच्छिक दिखने लगती है—"पारंपरिक" मिक्सिंग समय से बहुत कम होता है, जो प्रणाली को गणितीय रूप से पूर्ण होने के लिए आवश्यक है। यह घटना, जो सिद्धांत में संभव मानी जाती है, ऐसे मौलिक और उपयोगी प्रक्रिया के लिए शायद ही कभी प्रदर्शित की गई हो। शोधकर्ताओं के निष्कर्ष imply करते हैं कि कई व्यावहारिक परिदृश्यों में, हमें पूर्ण संतुलन की स्थिति तक पहुँचने का इंतजार करने की आवश्यकता नहीं है; हमें केवल तब तक प्रतीक्षा करने की आवश्यकता है जब तक कि यह उन उपकरणों के लिए पर्याप्त यादृच्छिक न हो जाता है जिनका हम उपयोग करते हैं। यह अंतर्दृष्टि वैज्ञानिकों को यादृच्छिक एल्गोरिदम के डिजाइन के प्रति अपने दृष्टिकोण को बदलने के लिए प्रोत्साहित कर सकती है, जिससे उन्हें उन अन्य क्षेत्रों में इन कम्प्यूटेशनल रूप से कुशल शॉर्टकटों को खोजने के लिए प्रेरित किया जा सके जहाँ पारंपरिक मिक्सिंग समय अत्यधिक धीमा होता है।

यह अध्ययन क्रिप्टोग्राफी के क्षेत्र को भी छूता है, जहाँ ऐसे मैट्रिक्स उत्पन्न करने की क्षमता जो यादृच्छिक दिखते हैं लेकिन गणना के लिए आसान हैं, अत्यंत मूल्यवान है। लेखक उल्लेख करते हैं कि उनके परिणाम "ट्रैपडोर" (trapdoored) मैट्रिसेस के निर्माण का समर्थन करते हैं, जो किसी भी पर्यवेक्षक के लिए यादृच्छिक प्रतीत होते हैं लेकिन उनमें एक गुप्त कुंजी होती है जो तेज़ गणना की अनुमति देती है। हालांकि उन्होंने एक नया क्रिप्टोग्राफिक सिस्टम नहीं बनाया, लेकिन उनके प्रमाण ने कि सैक्स मैट्रिसेस यादृच्छिक होने से अविभेदनीय हैं, ऐसे निर्माणों के सैद्धांतिक आधार को मजबूत किया है। यह संबंध शुद्ध गणित, कंप्यूटर विज्ञान और सुरक्षा के बीच गहरे अंतर्संबंध को उजागर करता है, जो यह दिखाता है कि एक ज्यामितिक आकार पर यादृच्छिक वॉक की बेहतर समझ का सूचना को सुरक्षित करने और संसाधित करने के तरीके पर दूरगामी परिणाम हो सकते हैं।

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