एल्गोरिथम संभाव्यता

एल्गोरिथम संभाव्यता के माध्यम से प्रेक्षक अवस्थाओं से भौतिकी तक

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

गणितीय औपचारिकता में उपयोग किए गए अवलोकनों में परिमित बाइनरी स्ट्रिंग्स का रूप होता है जिन्हें ट्यूरिंग मशीनों के आउटपुट के रूप में देखा जाता है, और सार्वभौमिक पूर्व प्रोग्रामों (अर्थात्, एक सार्वभौमिक ट्यूरिंग मशीन के लिए इनपुट)) पर संभाव्यता वितरण से गणना की गई परिमित बाइनरी स्ट्रिंग्स के सेट पर एक संभाव्यता वितरण है। ट्यूरिंग-कम्प्यूटेबिलिटी अर्थ में पूर्व सार्वभौमिक है, अर्थात् किसी भी स्ट्रिंग की शून्य संभावना नहीं है। यह गणना योग्य नहीं है किन्तु इसका अनुमान लगाया जा सकता है।

अवलोकन

एल्गोरिथम संभाव्यता सोलोमनॉफ़ के आगमनात्मक अनुमान के सिद्धांत का मुख्य घटक है, जो अवलोकनों पर आधारित भविष्यवाणी का सिद्धांत हैं; इसका आविष्कार मशीन लर्निंग के लिए उपयोग करने के लक्ष्य से किया गया था; प्रतीकों का क्रम दिया गया है, कि अगला कौन सा आएगा? सोलोमोनॉफ़ का सिद्धांत उत्तर प्रदान करता है जो एक निश्चित अर्थ में इष्टतम है, चूंकि यह गणना योग्य नहीं है। उदाहरण के लिए, कार्ल पॉपर के अनौपचारिक आगमनात्मक अनुमान सिद्धांत सोलोमोनॉफ़ गणितीय रूप से कठोर है।

सोलोमोनोव की एल्गोरिथम संभाव्यता के लिए चार प्रमुख प्रेरणाएँ थीं: ओकाम का रेजर, एपिकुरस का कई स्पष्टीकरणों का सिद्धांत, आधुनिक कंप्यूटिंग सिद्धांत (उदाहरण के लिए सार्वभौमिक ट्यूरिंग मशीन का उपयोग) और भविष्यवाणी के लिए बेयस का नियम।

ओकाम का रेजर और एपिकुरस का सिद्धांत अनिवार्य रूप से सार्वभौमिक पूर्व के दो अलग-अलग गैर-गणितीय अनुमान हैं।

• ओकाम का उस्तरा: उन सिद्धांतों में से जो देखी गई घटनाओं के अनुरूप हैं, सबसे सरल सिद्धांत का चयन करना चाहिए।
• एपिकुरस का अनेक स्पष्टीकरणों का सिद्धांत: यदि से अधिक सिद्धांत अवलोकनों के अनुरूप हैं, तो ऐसे सभी सिद्धांतों को रखें।

यूनिवर्सल प्रायर के केंद्र में कंप्यूटर का अमूर्त मॉडल है, जैसे यूनिवर्सल ट्यूरिंग मशीन। कोई भी अमूर्त कंप्यूटर तब तक काम करेगा, जब तक वह ट्यूरिंग-पूर्ण है, अर्थात् प्रत्येक गणना योग्य फ़ंक्शन में कम से कम प्रोग्राम होता है जो अमूर्त कंप्यूटर पर उसके एप्लिकेशन की गणना करेगा।

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

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

सोलोमनॉफ़ का गणनीय माप एक निश्चित शक्तिशाली अर्थ में सार्वभौमिकता (दर्शन) है, किन्तु गणना का समय अनंत हो सकता है। इस समस्या से निपटने की एक विधि लियोनिद लेविन के खोज एल्गोरिदम का प्रकार है, जो छोटे प्रोग्रामों के साथ अधिक समय दिए जाने पर संभावित प्रोग्रामों की सफलता की गणना करने में लगने वाले समय को सीमित करता है। जब इसे लंबे समय तक और लंबे समय तक चलाया जाता है, तो यह अनुमानों का क्रम उत्पन्न करेगा जो सार्वभौमिक संभाव्यता वितरण में परिवर्तित हो जाता है। इस समस्या से निपटने के अन्य विधियों में प्रशिक्षण अनुक्रमों को सम्मिलित करके खोज स्थान को सीमित करना सम्मिलित है।

सोलोमोनोव ने इस वितरण को स्थिर कारक (जिसे कोलमोगोरोव जटिलता अपरिवर्तन प्रमेय कहा जाता है) के अन्दर मशीन-अपरिवर्तनीय सिद्ध किया।

मौलिक प्रमेय

I. कोलमोगोरोव का अपरिवर्तनीय प्रमेय

कोलमोगोरोव का अपरिवर्तनीय प्रमेय स्पष्ट करता है कि डेटासेट की कोलमोगोरोव जटिलता, या न्यूनतम विवरण लंबाई, यूनिवर्सल ट्यूरिंग मशीन का अनुकरण करने के लिए उपयोग की जाने वाली ट्यूरिंग-पूर्ण भाषा की पसंद के लिए अपरिवर्तनीय है:

$\forall x\in \{0,1\}^{*},|K_{U}(x)-K_{U'}(x)|\leq {\mathcal {O}}(1)$

जहाँ $K_{U}(x)=\min _{p}\{|p|:U(p)=x\}$ है।

व्याख्या

न्यूनतम विवरण $p$ इस प्रकार है कि $U\circ p=x$ ट्यूरिंग-पूर्ण भाषा $U$ के सापेक्ष स्ट्रिंग $x$ के प्राकृतिक प्रतिनिधित्व के रूप में कार्य करता है। इसके अतिरिक्त, चूँकि $x$ को आगे संपीड़ित नहीं किया जा सकता है इसलिए $p$ एक असंपीड्य और इसलिए अगणनीय स्ट्रिंग है। यह वैज्ञानिकों की यादृच्छिकता की धारणा से मेल खाता है और इस कारण को स्पष्ट करता है कि कोलमोगोरोव जटिलता गणना योग्य क्यों नहीं है।

इसका तात्पर्य यह है कि डेटा के किसी भी भाग में यादृच्छिक स्ट्रिंग के संदर्भ में आवश्यक और पर्याप्त प्रतिनिधित्व होता है।

प्रमाण

निम्नलिखित से लिया गया है

संकलक के सिद्धांत से, यह ज्ञात है कि किन्हीं दो ट्यूरिंग-कम्प्लीट भाषाओं $U_{1}$ और $U_{2}$ के लिए, $U_{1}$ में व्यक्त एक कंपाइलर $\Lambda _{1}$ उपस्थित है जो $U_{2}$ में व्यक्त प्रोग्रामों को $U_{1}$ में व्यक्त कार्यात्मक-समतुल्य प्रोग्रामों में अनुवाद करता है।

यह इस प्रकार है कि यदि हम $p$ को सबसे छोटा प्रोग्राम मानते हैं जो किसी दिए गए स्ट्रिंग $x$ को प्रिंट करता है:

$K_{U_{1}}(x)\leq |\Lambda _{1}|+|p|\leq K_{U_{2}}(x)+{\mathcal {O}}(1)$

जहाँ $|\Lambda _{1}|={\mathcal {O}}(1)$, और समरूपता से हम विपरीत असमानता प्राप्त करते हैं।

द्वितीय. लेविन का सार्वभौमिक वितरण

यह देखते हुए कि कोई भी विशिष्ट-डिकोडेबल कोड क्राफ्ट-मैकमिलन असमानता उपसर्ग-मुक्त कोलमोगोरोव जटिलता को संतुष्ट करता है, हमें सार्वभौमिक वितरण प्राप्त करने की अनुमति देता है:

$P(x)=\sum _{U\circ P=x}P(U\circ p=x)=\sum _{U\circ p=x}2^{-K_{U}(p)}\leq 1$

जहां तथ्य यह है कि $U$ एक उपसर्ग-मुक्त यूटीएम का अनुकरण कर सकता है, इसका तात्पर्य यह है कि दो अलग-अलग विवरणों $p$ और $p'$ के लिए, $p$ '$p'$ का एक सबस्ट्रिंग नहीं है और $p'$, $p$ का एक सबस्ट्रिंग नहीं है।

व्याख्या

संगणनीय यूनिवर्स में, एक भौतिक प्रक्रिया द्वारा उत्पन्न एन्कोडिंग $x\in \{0,1\}^{*}$ के साथ एक घटना को देखते हुए उस घटना की संभावना अच्छी तरह से परिभाषित होती है और विशिष्ट और स्वतंत्र कारणों की संभावनाओं के योग के बराबर होती है। उपसर्ग-मुक्त मानदंड वास्तव में कारणात्मक स्वतंत्रता की गारंटी देता है।

प्रमाण

यह क्राफ्ट-मैकमिलन असमानता का तात्कालिक परिणाम है।

क्राफ्ट की असमानता बताती है कि स्ट्रिंग $\{x_{i}\}_{i=1}^{n}$ के अनुक्रम को देखते हुए कोडवर्ड $\{\sigma _{i}\}_{i=1}^{n}$ के साथ एक उपसर्ग कोड उपस्थित है जहां $\forall i,|\sigma _{i}|=k_{i}$ यदि और केवल यदि:

$\sum _{i=1}^{n}s^{-k_{i}}\leq 1$

जहाँ $s$ वर्णमाला $S$ का आकार है।

व्यापकता की हानि के बिना, मान लीजिए कि हम $k_{i}$ को इस प्रकार आदेश दे सकते हैं कि:

$k_{1}\leq k_{2}\leq ...\leq k_{n}$

अब, एक उपसर्ग कोड उपस्थित है यदि और केवल तभी जब प्रत्येक चरण $j$ में चुनने के लिए कम से कम एक कोडवर्ड हो जिसमें उपसर्ग के रूप में पिछले $j-1$ कोडवर्ड में से कोई भी सम्मिलित न हो। पिछले चरण में कोडवर्ड के अस्तित्व के कारण $i<j,s^{k_{j}-k_{i}}$ कोडवर्ड निषिद्ध हैं क्योंकि उनमें उपसर्ग के रूप में $\sigma _{i}$ सम्मिलित होता है। इसका तात्पर्य यह है कि सामान्यतः एक उपसर्ग कोड उपस्थित होता है यदि और केवल यदि

$\forall j\geq 2,s^{k_{j}}>\sum _{i=1}^{j-1}s^{k_{j}-k_{i}}$

दोनों पक्षों को $s^{k_{j}}$ से विभाजित करने पर, हम पाते हैं:

$\sum _{i=1}^{n}s^{-k_{i}}\leq 1$

इति सिद्धम्

इतिहास

सोलोमनॉफ़ ने 1960 के आसपास इससे संबंधित अपरिवर्तनीय प्रमेय के साथ एल्गोरिथम संभाव्यता की अवधारणा का आविष्कार किया, इस पर रिपोर्ट प्रकाशित की: आगमनात्मक अनुमान के सामान्य सिद्धांत पर प्रारंभिक रिपोर्ट। उन्होंने 1964 में ए फॉर्मल थ्योरी ऑफ़ इंडक्टिव इंफ़रेंस, भाग I और भाग II के साथ इन विचारों को पूरी तरह से स्पष्ट किया ।

उदाहरण

इन विचारों को विशिष्ट बनाया जा सकता है.

प्रमुख लोग

• रे सोलोमोफ़
• एंड्री कोलमोगोरोव
• लियोनिद लेविन

यह भी देखें

• सोलोमनॉफ का आगमनात्मक अनुमान का सिद्धांत
• एल्गोरिथम सूचना सिद्धांत
• बायेसियन अनुमान
• आगमनात्मक अनुमान
• आगमनात्मक संभाव्यता
• कोलमोगोरोव जटिलता
• यूनिवर्सल ट्यूरिंग मशीन
• सूचना-आधारित जटिलता

स्रोत

• ली, एम. और विटानी, पी., एन इंट्रोडक्शन टू कोलमोगोरोव कॉम्प्लेक्सिटी एंड इट्स एप्लीकेशन्स, तीसरा संस्करण, स्प्रिंगर साइंस एंड बिजनेस मीडिया, एन.वाई., 2008

अग्रिम पठन

• Rathmanner, S and Hutter, M., "A Philosophical Treatise of Universal Induction" in Entropy 2011, 13, 1076-1136: A very clear philosophical and mathematical analysis of Solomonoff's Theory of Inductive Inference

बाहरी संबंध

• Algorithmic Probability at Scholarpedia
• Solomonoff's publications