Completeness for Probabilistic Boolean Tapes

तकनीकी सारांश: संभाव्य बूलियन टेप्स के लिए पूर्णता (Completeness for Probabilistic Boolean Tapes)

समस्या विवरण
यह शोध पत्र संभाव्य बूलियन सर्किट (probabilistic Boolean circuits) के अर्थशास्त्र (semantics) के लिए एक पूर्ण समीकरणिक स्वयंसिद्धीकरण (equational axiomatization) प्रदान करने की चुनौती को संबोधित करता है। यद्यपि संभाव्य बूलियन सर्किट को परिमित संभाव्य प्रोग्रामिंग (finite probabilistic programming) के लिए एक स्ट्रिंग-डायग्राममैटिक आधार के रूप में प्रस्तावित किया गया है, पूर्ववर्ती स्वयंसिद्धीकरण प्रयास (विशेष रूप से [59] में) अपूर्ण थे। पूर्ववर्ती कार्य में प्रेरित तुल्यता (equivalence) अर्थपूर्ण समानता (semantic equality) की तुलना में काफी व्यापक थी; इसने आरेख $c$ और $d$ को तब समान माना जब उनके अर्थ समानुपाती ($\langle\langle c \rangle\rangle \propto \langle\langle d \rangle\rangle$) थे, न कि पूर्णतः समान। फलस्वरूप, पिछले कार्यों के कुछ स्वंसिद्ध (axioms) मानक अर्थशास्त्र (मार्कोव कर्नेल/सब-डिस्ट्रीब्यूशन पर आधारित) के प्रति असुरक्षित (unsound) थे। इसके अतिरिक्त, यह शोध पत्र नोट करता है कि आंशिक बूलियन सर्किट (वे सर्किट जो आउटपुट देने में विफल हो सकते हैं) का पहले स्वयंसिद्धीकरण नहीं किया गया था।

कार्यप्रणाली (Methodology)
लेखक एक चरणबद्ध दृष्टिकोण अपनाते हैं, जो सरल संरचनाओं से पूर्ण संभाव्य भाषा की ओर बढ़ता है, और स्ट्रिंग डायग्राम और श्रेणी सिद्धांत (category theory) के सिद्धांतों का लाभ उठाता है:

1. बूलियन सर्किट ($Diag_B$): लेखक सबसे पहले बूलियन सर्किट के मानक स्ट्रिंग-डायग्राममैटिक प्रतिनिधित्व को याद करते हैं, जिन्हें सेट और फंक्शन के वर्ग (category of sets and functions) में मोर्फिज्म के रूप में व्याख्यायित किया जाता है। वे इस खंड के लिए ज्ञात बूलियन बीजगणित की पूर्णता पर भरोसा करते हैं।
2. आंशिक बूलियन सर्किट ($Diag_{PB}$): लेखक हस्ताक्षर (signature) का विस्तार एक "को-कॉपी" जनरेटर (जिसे $\cap$ द्वारा दर्शाया गया है) को शामिल करने के लिए करते हैं, जो "कॉपी" जनरेटर का द्वैत (dual) है। यह जनरेटर दो इनपुट्स की तुलना करता है और केवल तभी आउटपुट देता है जब वे सहमत हों; अन्यथा, यह कोई आउटपुट नहीं देता (अपरिभाषित)। यह आंशिक फलनों (partial functions) को मॉडल करता है। लेखक एक नया मोनॉइडल सिद्धांत $PB$ परिभाषित करते हैं जो आंशिकता (partiality) को नियंत्रित करने वाले स्वंसिद्धों (associativity, commutativity, idempotence, और Frobenius laws) के साथ बूलियन बीजगणित का विस्तार करता है।
3. संभाव्य बूलियन टेप्स ($T(Diag_{PB})$): पूर्ण संभाव्य सर्किट भाषा ($Diag_{PrB}$) को सीधे स्वयंसिद्ध करने के बजाय, लेखक "संभाव्य बूलियन टेप्स" पेश करते हैं। यह औपचारिकता आंशिक बूलियन सर्किट की श्रेणी में 'कॉन्वेक्स बाइप्रोडक्ट्स' (convex biproducts) को स्वतंत्र रूप से जोड़कर निर्मित की गई है। टेप्स दो मोनॉइडल संरचनाओं का समर्थन करते हैं: टेंसर उत्पाद ($\otimes$) और कॉन्वेक्स सम ($\oplus$)। बाद वाला संरचना, संभाव्य नियंत्रण (जैसे, संभाव्य ब्रांचिंग) को मॉडल करने की अनुमति देता है जिसे केवल टेंसर उत्पाद अकेले नहीं कर सकता।
4. श्रेणीगत ढांचा (Categorical Framework): अर्थशास्त्र की व्याख्या $KL(D_\le)$ में की जाती है, जो सब-डिस्ट्रीब्यूशन मोनाड (subdistribution monad) की क्लेस्की श्रेणी (Kleisli category) है। लेखक [6] के परिणामों का उपयोग करते हैं जो टेप डायग्राम्स को PCA-समृद्ध श्रेणी $C^+$ (जिसे $St^Mat(C^+)$ कहा जाता है) पर स्टोकैस्टिक मैट्रिसेस के रूप में लक्षणबद्ध करते हैं। विशेष रूप से, वे इस तथ्य पर निर्भर करते हैं कि टेप की श्रेणी $T(C)$, $St^Mat(C^+)$ के आइसोमोर्फिक है।

मुख्य योगदान

1. आंशिक बूलियन सर्किट का पूर्ण स्वयंसिद्धीकरण:
   शोध पत्र आंशिक बूलियन सर्किट ($Diag_{PB}$) के लिए स्वंसिद्धों का एक पूर्ण सेट प्रस्तुत करता है। ये स्वंसिद्ध मानक बूलियन बीजगणित को "को-कॉपी" जनरेटर (चित्र 3) को नियंत्रित करने वाले नियमों के साथ विस्तारित करते हैं। लेखक किसी भी आंशिक सर्किट को एक "डोमेन" सर्किट (जो निर्धारित करता है कि फलन कहाँ परिभाषित है) और एक "टोटल" सर्किट (जो आउटपुट मान निर्धारित करता है) में विघटित करके पूर्णता (प्रमेय 9) सिद्ध करते हैं, जिससे समस्या बूलियन सर्किट की ज्ञात पूर्णता में बदल जाती है।

2. संभाव्य बूलियन टेप्स का पूर्ण स्वयंसिद्धीकरण:
   लेखक संभाव्य बूलियन टेप्स के लिए एक पूर्ण स्वयंसिद्धीकरण प्रदान करते हैं (चित्र 4 और 5)। इस प्रणाली में शामिल हैं:

   • टेप निर्माण के लिए स्वंसिद्ध (प्राकृतिक और सुसंगत मोनॉइड्स, को-पॉइंटेड कॉन्वेक्स अल्जेब्रा)।
   • आंशिकता के लिए विशिष्ट स्वंसिद्ध (जैसे, एक विफल गणना को शून्य वितरण के समान मानना)।
   • एक महत्वपूर्ण निहितार्थ स्वयंसिद्ध (T3) जो कैनसेलिटिविटी (cancellativity) को व्यक्त करता है, जो बीजगणितीय संरचनाओं में एक मानक तर्क सिद्धांत है।
     पूर्णता प्रमाण (अनुवर्ती 29) टेप्स और स्टोकैस्टिक मैट्रिसेस के बीच आइसोमोर्फिज्म पर निर्भर करता, यह दिखाते हुए कि $KL(D_\le)$ में अर्थपूर्ण समानता ठीक से परिभाषित स्वंसिद्धों के सापेक्ष टेप कैलकुलस में समानता के अनुरूप है।

3. सर्किट समानता को टेप समानता में बदलना:
   संभाव्य बूलियन सर्किट से संभाव्य बूलियन टेप्स तक एक एनकोडिंग $E(-)$ का उपयोग करके (जैसा कि [8] में स्थापित किया गया है), लेखक यह प्रदर्शित करते हैं कि सर्किट की अर्थपूर्ण समानता की जाँच करना उनके टेप एनकोडिंग की समानता की जाँच करने में बदल जाता है (अनुवर्ती 30)।

परिणाम

• सुदृढ़ता और पूर्णता (Soundness and Completeness): शोध पत्र सिद्ध करता है कि प्रस्तावित स्वंसिद्ध प्रणाली $KL(D_\le)$ में अर्थशास्त्र के संबंध में सुदृढ़ और पूर्ण दोनों है।
• पूर्ववर्ती कार्य का सुधार: लेखक दिखाते हैं कि उनकी प्रणाली द्वारा प्रेरित तुल्यता [59] की तुलना में काफी सूक्ष्म (finer) है। विशेष रूप से, वे प्रदर्शित करते हैं कि पिछले सिस्टम के स्वंसिद्ध F2 और F7 असुरक्षित (unsound) हैं, जबकि उनका स्वयंसिद्ध F8 (जो [59] से है) उनके सिस्टम के भीतर व्युत्पन्न योग्य (derivable) है।
• टेप्स की अभिव्यक्ति (Expressivity): लेख दर्शाते हैं कि टेप्स, केवल $\otimes$ पर निर्भर सर्किटों की तुलना में संभाव्य नियंत्रण को अधिक स्वाभाविक रूप से मॉडल कर सकते हैं। उदाहरण के लिए, एक टेप एक वैध गणना और एक विफलता (शून्य व्यवहार) के बीच संभाव्य चयन को मॉडल कर सकता है, बिना पूरे संयोजन को शून्य बनाए, जो केवल मोनॉइडल उत्पाद का उपयोग करने वाले दृष्टिकोणों की एक सीमा है।

महत्व
शोध पत्र दावा करता है कि यह आंशिक बूलियन सर्किट के लिए पहला पूर्ण स्वयंसिद्धीकरण और संभाव्य बूलियन टेप्स के लिए पूर्ण स्वयंसिद्धीकरण प्रदान करके महत्वपूर्ण है। इन परिणामों को स्थापित करके, लेखक संभाव्य प्रोग्रामिंग के लिए डायग्राम के स्तर पर सीधे समीकरणिक तर्क (equational reasoning) को सक्षम करते हैं। टेप्स की ओर बदलाव एक ऐसा संरचनात्मक रूप से पारदर्शी स्वयंसिद्धीकरण प्रदान करता है जो संभाव्य नियंत्रण और आंशिकता को समान रूप से संभालता है। लेखक नोट करते हैं कि हालांकि वर्तमान कार्य सीमित संभाव्य प्रोग्रामिंग पर केंद्रित है, टेप का ढांचा (विशेष रूप से $\oplus$ के साथ ट्रेसेस का उपयोग) संभाव्य प्रोग्राम लॉजिक और संभाव्य नियमित अभिव्यक्तियों के प्रतिनिधित्व के लिए बीजगणितीय आधार प्रदान करने की क्षमता रख सकता है, हालांकि इन्हें वर्तमान परिणाम के बजाय भविष्य की दिशाओं के रूप में पहचाना गया है। यह कार्य "स्ट्रिंग-डायग्राममैटिक" दृष्टिकोण पर आधारित है जहाँ डेटा को एक भौतिक संसाधन के रूप में माना जाता है, जो मुक्त प्रतिलिपि बनाने या त्यागने को रोकता है, जो संभाव्य और क्वांटम कंप्यूटिंग संदर्भों में केंद्रीय है।