A Behavioural Theory of Probabilistic Algorithms Using Probabilistic Abstract State Machines
यह शोध पत्र चार स्वयंसिद्ध अभिधारणाओं (axiomatic postulates) का प्रस्ताव करके और यह सिद्ध करके कि संभाव्य एब्स्ट्रैक्ट स्टेट मशीन्स (pASMs) व्यवहारिक तुल्यता के साथ इन अभिधारणाओं को संतुष्ट करने वाले किसी भी एल्गोरिदम का अनुकरण कर सकते हैं, संभाव्य एल्गोरिदम का एक व्यवहारिक सिद्धांत स्थापित करता है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
कल्पना कीजिए कि आप एक कंप्यूटर प्रोग्राम के काम करने के तरीके का वर्णन करने की कोशिश कर रहे हैं, लेकिन यह प्रोग्राम केवल एक सख्त, सीधी रेखा वाले पथ का अनुसरण नहीं कर रहा है। इसके बजाय, हर मोड़ पर, यह तय करने के लिए कि आगे कहाँ जाना है, एक सिक्का उछालता है (या पासा फेंकता है)। यह एक प्रायिकता एल्गोरिदम (Probabilistic Algorithm) है। ये कंप्यूटर जगत के "जुआरी" हैं, जिनका उपयोग सॉर्टिंग से लेकर कोड तोड़ने तक सब कुछ करने के लिए किया जाता है, क्योंकि कभी-कभी हर एक संभावना की जांच करने की तुलना में एक रैंडम अनुमान लगाना तेज़ या अधिक स्मार्ट होता है।
यह शोध पत्र एक बड़ा सवाल पूछता है: क्या हम एक सार्वभौमिक "नियम पुस्तिका" लिख सकते हैं जो सटीक रूप से इन रैंडमाइजिंग प्रोग्रामों का वर्णन करे, बिना उन्हें किसी विशिष्ट कंप्यूटर भाषा या हार्डवेयर से बांधे?
लेखक, फ्लेवियो फेरारोटी और क्लाउस-डिएटर शेवे कहते हैं, "हाँ।" वे इन एल्गोरिदम के लिए एक नई थ्योरी बनाते हैं जिसे व्यवहार संबंधी सिद्धांत (Behavioural Theory) कहा जाता है। यहाँ उनके कार्य का सरल उपमाओं (analogies) का उपयोग करके विवरण दिया गया है।
1. चार स्वर्णिम नियम (The Postulates)
यह परिभाषित करने के लिए कि क्या एक "प्रायिकता एल्गोरिदम" माना जाए, लेखक चार सख्त नियम प्रस्तावित करते हैं। इन्हें इन रैंडम प्रोग्रामों के लिए भौतिकी के नियमों के रूप में समझें:
नियम 1: रास्ते का विभाजन (Random Branching Time)।
एक सामान्य प्रोग्राम में, यदि आप एक चौराहे पर हैं, तो आगे जाने के लिए केवल एक ही रास्ता होता है। एक प्रायिकता प्रोग्राम में, कई रास्ते होते हैं। नियम कहता है: "प्रत्येक चरण में, प्रोग्राम के पास अगले चरणों की एक सूची होनी चाहिए, और प्रत्येक पथ के साथ एक विशिष्ट प्रायिकता जुड़ी होनी चाहिए (जैसे बाएं जाने की 30% संभावना, दाएं जाने की 70% संभावना)।"- उपमा: एक 'चूज़-योर-ओन-एडवेंचर' (अपनी पसंद का रोमांच चुनें) पुस्तक की कल्पना करें जहाँ, आपके द्वारा पेज चुनने के बजाय, एक जादुई पासा यह तय करता है कि आपको अगले पेज पर कौन सा पेज पलटना है। किताब को हर पेज के लिए संभावनाओं को स्पष्ट रूप से सूचीबद्ध करना चाहिए।
नियम 2: आकार बदलने वाला दर्पण (Abstract States)।
प्रोग्राम की "अवस्था" (उसकी वर्तमान मेमोरी और डेटा) बाहर से अलग दिख सकती है, लेकिन यदि अंतर्निहित संरचना समान है, तो प्रोग्राम एक ही तरह से व्यवहार करना चाहिए।- उपमा: कल्पना करें कि दो समान घर हैं, लेकिन एक नीला है और दूसरा लाल। यदि आप फर्नीचर को इस तरह से बदलते हैं कि लेआउट बिल्कुल समान रहता है, तो कहानी के उद्देश्य के लिए वह घर अभी भी वही "घर" है। यह नियम सुनिश्चित करता है कि यदि आप चीजों का नाम बदलते हैं (जैसे कोड में "जॉन" को "जेन" में बदलना), तो अगले चरणों की संभावनाएँ बिल्कुल समान रहती हैं।
नियम 3: टूलबॉक्स (Background)।
प्रोग्राम को गणित करने के लिए उपकरणों के एक मानक सेट की आवश्यकता होती है, जिसमें 0 और 1 के बीच की संख्याओं को संभालने के लिए विशेष उपकरणों का एक सेट भी शामिल है।- उपमा: आप आटा और अंडे के बिना केक नहीं बना सकते। इसी तरह, इन एल्गोरिदमों को एक पहले से लोड किए गए "टूलबॉक्स" की आवश्यकता होती है जिसमें लॉजिक (True/False), सूचियाँ, और एक विशेष "प्रायिकता कैलकुलेटर" शामिल है जो संभावनाओं को जोड़ने और गुणा करने को जानता है ताकि नंबर बहुत बड़े या अजीब न हो जाएं।
नियम 4: स्थानीय दृश्य (Probabilistic Bounded Exploration)।
यह सबसे महत्वपूर्ण और कठिन नियम है। यह कहता है कि प्रोग्राम को अगला कदम उठाने के लिए पूरे ब्रह्मांड को देखने की आवश्यकता नहीं है। उसे केवल अपनी वर्तमान अवस्था के एक छोटे, सीमित "स्नैपशॉट" को देखने की आवश्यकता है।- ट्विस्ट: लेखक "स्लाइसिंग" (Slicing) नामक एक अवधारणा पेश करते हैं। कल्पना करें कि आपके पास 100 सामग्रियों वाली एक जटिल रेसिपी है। यदि आप केवल शीर्ष 10 सामग्रियों का उपयोग करने का निर्णय लेते हैं (सूची को स्लाइस करना), तो रेसिपी अभी भी काम करती है, लेकिन यह कम संभावित परिणाम उत्पन्न करती है। नियम कहता है: "यदि आप विकल्पों को सीमित करते हैं (सूची को स्लाइस करते हैं), तो प्रोग्राम शेष विकल्पों के लिए संभावनाओं की पुनर्गणना करता है ताकि वे 100% तक जुड़ सकें।" यह परिवर्तनों की संरचना को विकल्पों की संभावना से अलग करता है।
2. मशीन मॉडल: pASMs
लेखक फिर एक विशिष्ट प्रकार की मशीन पेश करते हैं जिसे प्रायिकता अमूर्त अवस्था मशीन (Probabilistic Abstract State Machine - pASM) कहा जाता है।
- एक pASM को ऊपर दिए गए चार नियमों का पालन करने वाले रोबोट के रूप में सोचें।
- इसमें एक विशेष कमांड है जिसे
choose ... with weight ...कहा जाता है। यह ऐसा है जैसे रोबोट कह रहा हो, "मैं तीन दरवाजे देख रहा हूँ। दरवाजे A का भार 1 है, दरवाजे B का भार 2 है, और दरवाजे C का भार 3 है। मैं एक 6-तरफा पासे को फेंककर एक को चुनूँगा, जहाँ दरवाजा C चुनने की संभावना दरवाजा A की तुलना में दोगुनी है।"
3. बड़ी सिद्धि (The Capture Theorem)
शोध पत्र की मुख्य उपलब्धि यह सिद्ध करना है कि ये दोनों चीजें वास्तव में एक ही हैं:
- सिद्धांत (The Theory): कोई भी प्रोग्राम जो चार स्वर्णिम नियमों का पालन करता है।
- मशीन (The Machine): कोई भी pASM रोबोट जो
chooseकमांड के साथ बनाया गया है।
परिणाम: लेखक सिद्ध करते हैं कि प्रत्येक प्रायिकता एल्गोरिदम जो उनके नियमों का पालन करता है, उसे एक pASM रोबोट द्वारा चरण-दर-चरण सिम्युलेट (अनुकरण) किया जा सकता है।
- उपमा: कल्पना करें कि आपके पास एक मानव द्वारा किया जाने वाला अराजक, रैंडम नृत्य है (एल्गोरिदम)। लेखक सिद्ध करते हैं कि आप एक ऐसा रोबोट (pASM) बना सकते हैं जो उस नृत्य की हुबहू नकल कर सके, चरण-दर-चरण, बिल्कुल उसी रैंडम मूव्स और संभावनाओं के साथ। मानव का नृत्य चाहे कितना भी जटिल क्यों न हो, यदि वह नियमों का पालन करता है, तो रोबोट भी उसे कर सकता है।
4. वे क्या कवर नहीं करते
शोध पत्र बहुत विशिष्ट है कि वह क्या छोड़ देता है:
- क्वांटम कंप्यूटर: वे स्पष्ट रूप से कहते हैं कि उनका सिद्धांत क्वांटम एल्गोरिदम को कवर नहीं करता है। क्वांटम कंप्यूटिंग में, "अवस्था" (state) स्वयं रैंडम होती है (जैसे एक घूमता हुआ सिक्का जो एक ही समय में हेड्स और टेल्स दोनों है)। इस पेपर में, रैंडमनेस केवल तब होती है जब प्रोग्राम अपने अगले कदम को चुनता है, न कि डेटा की अवस्था में।
- अनंत विकल्प: वे मानते हैं कि अगले चरणों की संभावित सूची हमेशा परिमित (finite) होती है (आप एक ही चरण में चुनने के लिए अनंत दरवाजों की सूची नहीं रख सकते)।
सारांश
संक्षेप में, यह शोध पत्र रैंडम कंप्यूटर प्रोग्रामों को समझने के लिए एक ठोस गणितीय आधार बनाता है। यह चार स्पष्ट नियमों का उपयोग करके उन्हें परिभाषित करता है और सिद्ध करता है कि pASM नामक एक विशिष्ट प्रकार की मशीन किसी भी ऐसे प्रोग्राम को पूरी तरह से सिम्युलेट करने के लिए पर्याप्त शक्तिशाली है। यह प्रायिकता कंप्यूटिंग के लिए "संविधान" लिखने जैसा है, यह सुनिश्चित करते हुए कि चाहे आप कोड कैसे भी लिखें, यदि वह संविधान का पालन करता है, तो वह एक अनुमानित और विश्लेषण योग्य तरीके से व्यवहार करेगा।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।