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

From Vigyanwiki
(Created page with "File:From observer states to physics via algorithmic probability.png|thumb|एल्गोरिथम संभाव्यता के माध्यम से प्र...")
 
No edit summary
Line 1: Line 1:
[[File:From observer states to physics via algorithmic probability.png|thumb|एल्गोरिथम संभाव्यता के माध्यम से प्रेक्षक अवस्थाओं से भौतिकी तक<ref>Markus Müller. Law without Law: from observer states to physics via algorithmic information theory. Quantum: the open journal for quantum science. 06 June 2020. </ref>]][[एल्गोरिथम सूचना सिद्धांत]] में, एल्गोरिथम संभाव्यता, जिसे सोलोमनॉफ़ [[संभावना]] के रूप में भी जाना जाता है, किसी दिए गए अवलोकन के लिए पूर्व संभाव्यता निर्दिष्ट करने की एक गणितीय विधि है। इसका आविष्कार 1960 के दशक में [[रे सोलोमनॉफ़]] ने किया था।<ref>Solomonoff, R., "[http://world.std.com/~rjs/z138.pdf A Preliminary Report on a General Theory of Inductive Inference]", Report V-131, Zator Co., Cambridge, Ma. (Nov. 1960 revision of the Feb. 4, 1960 report).</ref> इसका उपयोग आगमनात्मक अनुमान सिद्धांत और एल्गोरिदम के विश्लेषण में किया जाता है। अपने सोलोमनॉफ के आगमनात्मक अनुमान के सिद्धांत में, सोलोमनॉफ एल्गोरिदम के भविष्य के आउटपुट के लिए भविष्यवाणी की संभावनाओं को प्राप्त करने के लिए बेयस नियम के साथ विधि का उपयोग करता है।<ref>Li, M. and Vitanyi, P., ''An Introduction to Kolmogorov Complexity and Its Applications'', 3rd Edition, Springer Science and Business Media, N.Y., 2008</ref>
[[File:From observer states to physics via algorithmic probability.png|thumb|एल्गोरिथम संभाव्यता के माध्यम से प्रेक्षक अवस्थाओं से भौतिकी तक<ref>Markus Müller. Law without Law: from observer states to physics via algorithmic information theory. Quantum: the open journal for quantum science. 06 June 2020. </ref>]][[एल्गोरिथम सूचना सिद्धांत]] में, एल्गोरिथम संभाव्यता, जिसे सोलोमनॉफ़ [[संभावना]] के रूप में भी जाना जाता है, किसी दिए गए अवलोकन के लिए पूर्व संभाव्यता निर्दिष्ट करने की गणितीय विधि है। इसका आविष्कार 1960 के दशक में [[रे सोलोमनॉफ़]] ने किया था।<ref>Solomonoff, R., "[http://world.std.com/~rjs/z138.pdf A Preliminary Report on a General Theory of Inductive Inference]", Report V-131, Zator Co., Cambridge, Ma. (Nov. 1960 revision of the Feb. 4, 1960 report).</ref> इसका उपयोग आगमनात्मक अनुमान सिद्धांत और एल्गोरिदम के विश्लेषण में किया जाता है। अपने सोलोमनॉफ के आगमनात्मक अनुमान के सिद्धांत में, सोलोमनॉफ एल्गोरिदम के भविष्य के आउटपुट के लिए भविष्यवाणी की संभावनाओं को प्राप्त करने के लिए बेयस नियम के साथ विधि का उपयोग करता है।<ref>Li, M. and Vitanyi, P., ''An Introduction to Kolmogorov Complexity and Its Applications'', 3rd Edition, Springer Science and Business Media, N.Y., 2008</ref>
उपयोग की जाने वाली गणितीय औपचारिकता में, अवलोकनों में [[ट्यूरिंग मशीन]]ों के आउटपुट के रूप में देखी जाने वाली परिमित बाइनरी स्ट्रिंग्स का रूप होता है, और सार्वभौमिक पूर्व कार्यक्रमों पर संभाव्यता वितरण से गणना की गई परिमित बाइनरी स्ट्रिंग्स के सेट पर एक संभाव्यता वितरण है (यानी, इनपुट) एक सार्वभौमिक ट्यूरिंग मशीन)। पूर्व में सार्वभौमिक है
उपयोग की जाने वाली गणितीय औपचारिकता में, अवलोकनों में [[ट्यूरिंग मशीन]]ों के आउटपुट के रूप में देखी जाने वाली परिमित बाइनरी स्ट्रिंग्स का रूप होता है, और सार्वभौमिक पूर्व कार्यक्रमों पर संभाव्यता वितरण से गणना की गई परिमित बाइनरी स्ट्रिंग्स के सेट पर संभाव्यता वितरण है (यानी, इनपुट) सार्वभौमिक ट्यूरिंग मशीन)। पूर्व में सार्वभौमिक है
ट्यूरिंग-कम्प्यूटेबिलिटी सेंस, यानी किसी भी स्ट्रिंग की शून्य संभावना नहीं है। यह गणना योग्य नहीं है, लेकिन इसका अनुमान लगाया जा सकता है।<ref>Hutter, M., Legg, S., and Vitanyi, P., [http://www.scholarpedia.org/article/Algorithmic_probability "Algorithmic Probability"], Scholarpedia, 2(8):2572, 2007.</ref>
ट्यूरिंग-कम्प्यूटेबिलिटी सेंस, यानी किसी भी स्ट्रिंग की शून्य संभावना नहीं है। यह गणना योग्य नहीं है, लेकिन इसका अनुमान लगाया जा सकता है।<ref>Hutter, M., Legg, S., and Vitanyi, P., [http://www.scholarpedia.org/article/Algorithmic_probability "Algorithmic Probability"], Scholarpedia, 2(8):2572, 2007.</ref>


Line 6: Line 6:
==अवलोकन==
==अवलोकन==


एल्गोरिथम संभाव्यता सोलोमनॉफ़ के आगमनात्मक अनुमान के सिद्धांत का मुख्य घटक है, अवलोकनों पर आधारित भविष्यवाणी का सिद्धांत; इसका आविष्कार मशीन लर्निंग के लिए उपयोग करने के लक्ष्य से किया गया था; प्रतीकों का एक क्रम दिया गया है, कौन सा अगला आएगा? सोलोमोनॉफ़ का सिद्धांत एक उत्तर प्रदान करता है जो एक निश्चित अर्थ में इष्टतम है, हालांकि यह गणना योग्य नहीं है। उदाहरण के लिए, [[कार्ल पॉपर]] के अनौपचारिक आगमनात्मक अनुमान सिद्धांत के विपरीत,{{clarify|reason=According to his wikipedia article, 'Popper is known for his rejection of the classical inductivist views on the scientific method'. Consequently, he didn't give an 'inductive inference theory'.|date=September 2015}}सोलोमोनॉफ़ गणितीय रूप से कठोर है।
एल्गोरिथम संभाव्यता सोलोमनॉफ़ के आगमनात्मक अनुमान के सिद्धांत का मुख्य घटक है, अवलोकनों पर आधारित भविष्यवाणी का सिद्धांत; इसका आविष्कार मशीन लर्निंग के लिए उपयोग करने के लक्ष्य से किया गया था; प्रतीकों का क्रम दिया गया है, कौन सा अगला आएगा? सोलोमोनॉफ़ का सिद्धांत उत्तर प्रदान करता है जो निश्चित अर्थ में इष्टतम है, हालांकि यह गणना योग्य नहीं है। उदाहरण के लिए, [[कार्ल पॉपर]] के अनौपचारिक आगमनात्मक अनुमान सिद्धांत के विपरीत,{{clarify|reason=According to his wikipedia article, 'Popper is known for his rejection of the classical inductivist views on the scientific method'. Consequently, he didn't give an 'inductive inference theory'.|date=September 2015}}सोलोमोनॉफ़ गणितीय रूप से कठोर है।


सोलोमोनोव की एल्गोरिथम संभाव्यता के लिए चार प्रमुख प्रेरणाएँ थीं: ओकाम का रेजर, एपिकुरस#एपिस्टेमोलॉजी|एपिकुरस का कई स्पष्टीकरणों का सिद्धांत, आधुनिक कंप्यूटिंग सिद्धांत (उदाहरण के लिए एक सार्वभौमिक ट्यूरिंग मशीन का उपयोग) और भविष्यवाणी के लिए बेयस का नियम।<ref>Li and Vitanyi, 2008, p. 347</ref>
सोलोमोनोव की एल्गोरिथम संभाव्यता के लिए चार प्रमुख प्रेरणाएँ थीं: ओकाम का रेजर, एपिकुरस#एपिस्टेमोलॉजी|एपिकुरस का कई स्पष्टीकरणों का सिद्धांत, आधुनिक कंप्यूटिंग सिद्धांत (उदाहरण के लिए सार्वभौमिक ट्यूरिंग मशीन का उपयोग) और भविष्यवाणी के लिए बेयस का नियम।<ref>Li and Vitanyi, 2008, p. 347</ref>
ओकाम का रेजर और एपिकुरस का सिद्धांत अनिवार्य रूप से [[सार्वभौमिक पूर्व]] के दो अलग-अलग गैर-गणितीय अनुमान हैं।
ओकाम का रेजर और एपिकुरस का सिद्धांत अनिवार्य रूप से [[सार्वभौमिक पूर्व]] के दो अलग-अलग गैर-गणितीय अनुमान हैं।


* ओकाम का उस्तरा: उन सिद्धांतों में से जो देखी गई घटनाओं के अनुरूप हैं, सबसे सरल सिद्धांत का चयन करना चाहिए।<ref>Li and Vitanyi, 2008, p. 341</ref>
* ओकाम का उस्तरा: उन सिद्धांतों में से जो देखी गई घटनाओं के अनुरूप हैं, सबसे सरल सिद्धांत का चयन करना चाहिए।<ref>Li and Vitanyi, 2008, p. 341</ref>
* एपिकुरस का अनेक स्पष्टीकरणों का सिद्धांत: यदि एक से अधिक सिद्धांत अवलोकनों के अनुरूप हैं, तो ऐसे सभी सिद्धांतों को रखें।<ref>Li and Vitanyi, 2008, p. 339.</ref>
* एपिकुरस का अनेक स्पष्टीकरणों का सिद्धांत: यदि से अधिक सिद्धांत अवलोकनों के अनुरूप हैं, तो ऐसे सभी सिद्धांतों को रखें।<ref>Li and Vitanyi, 2008, p. 339.</ref>
यूनिवर्सल प्रायर के केंद्र में कंप्यूटर का एक अमूर्त मॉडल है, जैसे यूनिवर्सल ट्यूरिंग मशीन।<ref>Hutter, M., [http://www.scholarpedia.org/article/Algorithmic_information_theory "Algorithmic Information Theory"], Scholarpedia, 2(3):2519.</ref> कोई भी अमूर्त कंप्यूटर तब तक काम करेगा, जब तक वह ट्यूरिंग-पूर्ण है, यानी प्रत्येक गणना योग्य फ़ंक्शन में कम से कम एक प्रोग्राम होता है जो अमूर्त कंप्यूटर पर उसके एप्लिकेशन की गणना करेगा।
यूनिवर्सल प्रायर के केंद्र में कंप्यूटर का अमूर्त मॉडल है, जैसे यूनिवर्सल ट्यूरिंग मशीन।<ref>Hutter, M., [http://www.scholarpedia.org/article/Algorithmic_information_theory "Algorithmic Information Theory"], Scholarpedia, 2(3):2519.</ref> कोई भी अमूर्त कंप्यूटर तब तक काम करेगा, जब तक वह ट्यूरिंग-पूर्ण है, यानी प्रत्येक गणना योग्य फ़ंक्शन में कम से कम प्रोग्राम होता है जो अमूर्त कंप्यूटर पर उसके एप्लिकेशन की गणना करेगा।


अमूर्त कंप्यूटर का उपयोग वाक्यांश सरल व्याख्या को सटीक अर्थ देने के लिए किया जाता है। प्रयुक्त औपचारिकता में, स्पष्टीकरण, या घटना के सिद्धांत, कंप्यूटर प्रोग्राम हैं जो अमूर्त कंप्यूटर पर चलने पर अवलोकन स्ट्रिंग उत्पन्न करते हैं। प्रत्येक कंप्यूटर प्रोग्राम को उसकी लंबाई के अनुरूप वजन दिया जाता है। सार्वभौमिक संभाव्यता वितरण यादृच्छिक इनपुट के साथ सभी संभावित आउटपुट स्ट्रिंग्स पर संभाव्यता वितरण है, जो प्रत्येक परिमित आउटपुट उपसर्ग q के लिए उन प्रोग्रामों की संभावनाओं का योग निर्दिष्ट करता है जो q से शुरू होने वाली किसी चीज़ की गणना करते हैं।<ref>Solomonoff, R., "[http://world.std.com/~rjs/kollect.pdf The Kolmogorov Lecture: The Universal Distribution and Machine Learning]" ''The Computer Journal'', Vol 46, No. 6 p 598, 2003.</ref> इस प्रकार, एक सरल व्याख्या एक लघु कंप्यूटर प्रोग्राम है। एक जटिल व्याख्या एक लंबा कंप्यूटर प्रोग्राम है। सरल स्पष्टीकरण अधिक संभावित हैं, इसलिए एक उच्च-संभावना अवलोकन स्ट्रिंग एक छोटे कंप्यूटर प्रोग्राम द्वारा उत्पन्न होती है, या शायद बड़ी संख्या में थोड़े लंबे कंप्यूटर प्रोग्रामों में से किसी एक द्वारा उत्पन्न होती है। कम-संभावना अवलोकन स्ट्रिंग वह है जिसे केवल एक लंबे कंप्यूटर प्रोग्राम द्वारा ही उत्पन्न किया जा सकता है।
अमूर्त कंप्यूटर का उपयोग वाक्यांश सरल व्याख्या को सटीक अर्थ देने के लिए किया जाता है। प्रयुक्त औपचारिकता में, स्पष्टीकरण, या घटना के सिद्धांत, कंप्यूटर प्रोग्राम हैं जो अमूर्त कंप्यूटर पर चलने पर अवलोकन स्ट्रिंग उत्पन्न करते हैं। प्रत्येक कंप्यूटर प्रोग्राम को उसकी लंबाई के अनुरूप वजन दिया जाता है। सार्वभौमिक संभाव्यता वितरण यादृच्छिक इनपुट के साथ सभी संभावित आउटपुट स्ट्रिंग्स पर संभाव्यता वितरण है, जो प्रत्येक परिमित आउटपुट उपसर्ग q के लिए उन प्रोग्रामों की संभावनाओं का योग निर्दिष्ट करता है जो q से शुरू होने वाली किसी चीज़ की गणना करते हैं।<ref>Solomonoff, R., "[http://world.std.com/~rjs/kollect.pdf The Kolmogorov Lecture: The Universal Distribution and Machine Learning]" ''The Computer Journal'', Vol 46, No. 6 p 598, 2003.</ref> इस प्रकार, सरल व्याख्या लघु कंप्यूटर प्रोग्राम है। जटिल व्याख्या लंबा कंप्यूटर प्रोग्राम है। सरल स्पष्टीकरण अधिक संभावित हैं, इसलिए उच्च-संभावना अवलोकन स्ट्रिंग छोटे कंप्यूटर प्रोग्राम द्वारा उत्पन्न होती है, या शायद बड़ी संख्या में थोड़े लंबे कंप्यूटर प्रोग्रामों में से किसी द्वारा उत्पन्न होती है। कम-संभावना अवलोकन स्ट्रिंग वह है जिसे केवल लंबे कंप्यूटर प्रोग्राम द्वारा ही उत्पन्न किया जा सकता है।


एल्गोरिथम संभाव्यता [[कोलमोगोरोव जटिलता]] की अवधारणा से निकटता से संबंधित है। कोलमोगोरोव की जटिलता का परिचय सूचना सिद्धांत और यादृच्छिकता में समस्याओं से प्रेरित था, जबकि सोलोमोनोव ने एक अलग कारण से एल्गोरिदम जटिलता पेश की: आगमनात्मक तर्क। एक एकल सार्वभौमिक पूर्व संभाव्यता जिसे बेयस नियम में प्रत्येक वास्तविक पूर्व संभाव्यता के लिए प्रतिस्थापित किया जा सकता है, का आविष्कार सोलोमोफ़ द्वारा कोलमोगोरोव जटिलता के साथ एक साइड उत्पाद के रूप में किया गया था।<ref>Gács, P. and Vitányi, P., "In Memoriam Raymond J. Solomonoff", ''IEEE Information Theory Society Newsletter'', Vol. 61, No. 1, March 2011, p 11.</ref> यह उस अवलोकन की सबसे संभावित निरंतरता की भविष्यवाणी करता है, और यह माप प्रदान करता है कि यह निरंतरता कितनी संभावित होगी।{{Citation needed|date=September 2017}}
एल्गोरिथम संभाव्यता [[कोलमोगोरोव जटिलता]] की अवधारणा से निकटता से संबंधित है। कोलमोगोरोव की जटिलता का परिचय सूचना सिद्धांत और यादृच्छिकता में समस्याओं से प्रेरित था, जबकि सोलोमोनोव ने अलग कारण से एल्गोरिदम जटिलता पेश की: आगमनात्मक तर्क। एकल सार्वभौमिक पूर्व संभाव्यता जिसे बेयस नियम में प्रत्येक वास्तविक पूर्व संभाव्यता के लिए प्रतिस्थापित किया जा सकता है, का आविष्कार सोलोमोफ़ द्वारा कोलमोगोरोव जटिलता के साथ साइड उत्पाद के रूप में किया गया था।<ref>Gács, P. and Vitányi, P., "In Memoriam Raymond J. Solomonoff", ''IEEE Information Theory Society Newsletter'', Vol. 61, No. 1, March 2011, p 11.</ref> यह उस अवलोकन की सबसे संभावित निरंतरता की भविष्यवाणी करता है, और यह माप प्रदान करता है कि यह निरंतरता कितनी संभावित होगी।{{Citation needed|date=September 2017}}


सोलोमोनोव का असंख्य माप एक निश्चित शक्तिशाली अर्थ में [[सार्वभौमिकता (दर्शन)]] है, लेकिन गणना का समय अनंत हो सकता है। इस समस्या से निपटने का एक तरीका लियोनिद लेविन के खोज एल्गोरिदम का एक प्रकार है,<ref>Levin, L.A., "Universal Search Problems", in Problemy Peredaci Informacii 9, pp. 115–116, 1973</ref> जो संभावित कार्यक्रमों की सफलता की गणना करने में लगने वाले समय को सीमित करता है, छोटे कार्यक्रमों को अधिक समय दिया जाता है। जब लंबे समय तक और लंबे समय तक चलाया जाता है, तो यह अनुमानों का एक क्रम उत्पन्न करेगा जो सार्वभौमिक संभाव्यता वितरण में परिवर्तित हो जाता है। समस्या से निपटने के अन्य तरीकों में प्रशिक्षण अनुक्रमों को शामिल करके खोज स्थान को सीमित करना शामिल है।
सोलोमोनोव का असंख्य माप निश्चित शक्तिशाली अर्थ में [[सार्वभौमिकता (दर्शन)]] है, लेकिन गणना का समय अनंत हो सकता है। इस समस्या से निपटने का तरीका लियोनिद लेविन के खोज एल्गोरिदम का प्रकार है,<ref>Levin, L.A., "Universal Search Problems", in Problemy Peredaci Informacii 9, pp. 115–116, 1973</ref> जो संभावित कार्यक्रमों की सफलता की गणना करने में लगने वाले समय को सीमित करता है, छोटे कार्यक्रमों को अधिक समय दिया जाता है। जब लंबे समय तक और लंबे समय तक चलाया जाता है, तो यह अनुमानों का क्रम उत्पन्न करेगा जो सार्वभौमिक संभाव्यता वितरण में परिवर्तित हो जाता है। समस्या से निपटने के अन्य तरीकों में प्रशिक्षण अनुक्रमों को शामिल करके खोज स्थान को सीमित करना शामिल है।


सोलोमोनोव ने इस वितरण को एक स्थिर कारक के भीतर मशीन-अपरिवर्तनीय साबित किया (जिसे कोलमोगोरोव जटिलता#इनवेरिएंस प्रमेय कहा जाता है)।<ref>Solomonoff, R., "[http://world.std.com/~rjs/publications/solo1.pdf Complexity-Based Induction Systems: Comparisons and Convergence Theorems]," IEEE Trans. on Information Theory, Vol. IT-24, No. 4, pp. 422-432, July 1978</ref>
सोलोमोनोव ने इस वितरण को स्थिर कारक के भीतर मशीन-अपरिवर्तनीय साबित किया (जिसे कोलमोगोरोव जटिलता#इनवेरिएंस प्रमेय कहा जाता है)।<ref>Solomonoff, R., "[http://world.std.com/~rjs/publications/solo1.pdf Complexity-Based Induction Systems: Comparisons and Convergence Theorems]," IEEE Trans. on Information Theory, Vol. IT-24, No. 4, pp. 422-432, July 1978</ref>




Line 37: Line 37:
=== व्याख्या ===
=== व्याख्या ===


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


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


=== प्रमाण ===
=== प्रमाण ===


निम्नलिखित से लिया गया है <ref>Grünwald, P. and Vitany , P. Algorithmic Information Theory. Arxiv. 2008.</ref>
निम्नलिखित से लिया गया है <ref>Grünwald, P. and Vitany , P. Algorithmic Information Theory. Arxiv. 2008.</ref>
संकलक के सिद्धांत से यह ज्ञात होता है कि किन्हीं दो ट्यूरिंग-पूर्ण भाषाओं के लिए <math>U_1</math> और <math>U_2</math>, वहाँ एक संकलक मौजूद है <math>\Lambda_1</math> में व्यक्त किया
संकलक के सिद्धांत से यह ज्ञात होता है कि किन्हीं दो ट्यूरिंग-पूर्ण भाषाओं के लिए <math>U_1</math> और <math>U_2</math>, वहाँ संकलक मौजूद है <math>\Lambda_1</math> में व्यक्त किया
  <math>U_1</math> जो व्यक्त कार्यक्रमों का अनुवाद करता है <math>U_2</math> कार्यात्मक रूप से समतुल्य कार्यक्रमों में व्यक्त किया गया <math>U_1</math>.
  <math>U_1</math> जो व्यक्त कार्यक्रमों का अनुवाद करता है <math>U_2</math> कार्यात्मक रूप से समतुल्य कार्यक्रमों में व्यक्त किया गया <math>U_1</math>.


Line 61: Line 61:
:<math>
:<math>
P(x) = \sum_{U \circ P = x} P(U \circ p = x) = \sum_{U \circ p = x} 2^{-K_U(p)} \leq 1 </math>
P(x) = \sum_{U \circ P = x} P(U \circ p = x) = \sum_{U \circ p = x} 2^{-K_U(p)} \leq 1 </math>
तथ्य यह है कि <math>U</math> एक उपसर्ग-मुक्त यूटीएम का अनुकरण हो सकता है जिसका तात्पर्य दो अलग-अलग विवरणों के लिए है <math>p</math> और <math>p'</math>, <math>p</math> नहीं है
तथ्य यह है कि <math>U</math> उपसर्ग-मुक्त यूटीएम का अनुकरण हो सकता है जिसका तात्पर्य दो अलग-अलग विवरणों के लिए है <math>p</math> और <math>p'</math>, <math>p</math> नहीं है
का एक उपस्ट्रिंग <math>p'</math> और <math>p'</math> का उपस्ट्रिंग नहीं है <math>p</math>.
का उपस्ट्रिंग <math>p'</math> और <math>p'</math> का उपस्ट्रिंग नहीं है <math>p</math>.


=== व्याख्या ===
=== व्याख्या ===


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


=== प्रमाण ===
=== प्रमाण ===
Line 72: Line 72:
यह [[क्राफ्ट-मैकमिलन असमानता]] का तात्कालिक परिणाम है।
यह [[क्राफ्ट-मैकमिलन असमानता]] का तात्कालिक परिणाम है।


क्राफ्ट की असमानता बताती है कि तारों का एक क्रम दिया गया है <math>\{x_i\}_{i=1}^n</math> कोडवर्ड के साथ एक उपसर्ग कोड मौजूद है <math>\{\sigma_i\}_{i=1}^n</math> कहाँ <math>\forall i, |\sigma_i|=k_i</math> अगर और केवल अगर:
क्राफ्ट की असमानता बताती है कि तारों का क्रम दिया गया है <math>\{x_i\}_{i=1}^n</math> कोडवर्ड के साथ उपसर्ग कोड मौजूद है <math>\{\sigma_i\}_{i=1}^n</math> कहाँ <math>\forall i, |\sigma_i|=k_i</math> अगर और केवल अगर:


:<math>
:<math>
Line 84: Line 84:
k_1 \leq k_2 \leq ... \leq k_n
k_1 \leq k_2 \leq ... \leq k_n
</math>
</math>
अब, प्रत्येक चरण में यदि और केवल यदि एक उपसर्ग कोड मौजूद है <math>j</math> चुनने के लिए कम से कम एक कोडवर्ड है जिसमें पिछला कोई भी कोड शामिल नहीं है <math>j-1</math> उपसर्ग के रूप में कोडवर्ड. पिछले चरण में एक कोडवर्ड के अस्तित्व के कारण <math>i<j, s^{k_j-k_i}</math> कोडवर्ड वर्जित हैं क्योंकि उनमें कोडवर्ड शामिल हैं <math>\sigma_i</math> उपसर्ग के रूप में. इसका तात्पर्य यह है कि सामान्य तौर पर एक उपसर्ग कोड मौजूद होता है यदि और केवल यदि:
अब, प्रत्येक चरण में यदि और केवल यदि उपसर्ग कोड मौजूद है <math>j</math> चुनने के लिए कम से कम कोडवर्ड है जिसमें पिछला कोई भी कोड शामिल नहीं है <math>j-1</math> उपसर्ग के रूप में कोडवर्ड. पिछले चरण में कोडवर्ड के अस्तित्व के कारण <math>i<j, s^{k_j-k_i}</math> कोडवर्ड वर्जित हैं क्योंकि उनमें कोडवर्ड शामिल हैं <math>\sigma_i</math> उपसर्ग के रूप में. इसका तात्पर्य यह है कि सामान्य तौर पर उपसर्ग कोड मौजूद होता है यदि और केवल यदि:


:<math>
:<math>
Line 98: Line 98:
== इतिहास ==
== इतिहास ==


सोलोमनॉफ़ ने 1960 के आसपास इससे संबंधित इनवेरिएंस प्रमेय के साथ एल्गोरिथम संभाव्यता की अवधारणा का आविष्कार किया,<ref>Solomonoff, R., [http://world.std.com/~rjs/barc97.pdf "The Discovery of Algorithmic Probability"], ''Journal of Computer and System Sciences'', Vol. 55, No. 1, pp. 73-88, August 1997.</ref> इस पर एक रिपोर्ट प्रकाशित करना: आगमनात्मक अनुमान के एक सामान्य सिद्धांत पर एक प्रारंभिक रिपोर्ट।<ref>Solomonoff, R., "[http://world.std.com/~rjs/z138.pdf A Preliminary Report on a General Theory of Inductive Inference]", Report V-131, Zator Co., Cambridge, Ma. (Nov. 1960 revision of the Feb. 4, 1960 report).</ref> उन्होंने 1964 में ए फॉर्मल थ्योरी ऑफ़ इंडक्टिव इंफ़रेंस, भाग I के साथ इन विचारों को पूरी तरह से स्पष्ट किया।<ref>Solomonoff, R., "[http://world.std.com/~rjs/1964pt1.pdf A Formal Theory of Inductive Inference, Part I]". ''Information and Control'', Vol 7, No. 1 pp 1-22, March 1964.</ref> और भाग II.<ref>Solomonoff, R., "[http://world.std.com/~rjs/1964pt2.pdf A Formal Theory of Inductive Inference, Part II]" ''Information and Control'', Vol 7, No. 2 pp 224–254, June 1964.</ref>
सोलोमनॉफ़ ने 1960 के आसपास इससे संबंधित इनवेरिएंस प्रमेय के साथ एल्गोरिथम संभाव्यता की अवधारणा का आविष्कार किया,<ref>Solomonoff, R., [http://world.std.com/~rjs/barc97.pdf "The Discovery of Algorithmic Probability"], ''Journal of Computer and System Sciences'', Vol. 55, No. 1, pp. 73-88, August 1997.</ref> इस पर रिपोर्ट प्रकाशित करना: आगमनात्मक अनुमान के सामान्य सिद्धांत पर प्रारंभिक रिपोर्ट।<ref>Solomonoff, R., "[http://world.std.com/~rjs/z138.pdf A Preliminary Report on a General Theory of Inductive Inference]", Report V-131, Zator Co., Cambridge, Ma. (Nov. 1960 revision of the Feb. 4, 1960 report).</ref> उन्होंने 1964 में ए फॉर्मल थ्योरी ऑफ़ इंडक्टिव इंफ़रेंस, भाग I के साथ इन विचारों को पूरी तरह से स्पष्ट किया।<ref>Solomonoff, R., "[http://world.std.com/~rjs/1964pt1.pdf A Formal Theory of Inductive Inference, Part I]". ''Information and Control'', Vol 7, No. 1 pp 1-22, March 1964.</ref> और भाग II.<ref>Solomonoff, R., "[http://world.std.com/~rjs/1964pt2.pdf A Formal Theory of Inductive Inference, Part II]" ''Information and Control'', Vol 7, No. 2 pp 224–254, June 1964.</ref>





Revision as of 07:02, 12 July 2023

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

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

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


अवलोकन

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

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

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

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

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

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

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

सोलोमोनोव ने इस वितरण को स्थिर कारक के भीतर मशीन-अपरिवर्तनीय साबित किया (जिसे कोलमोगोरोव जटिलता#इनवेरिएंस प्रमेय कहा जाता है)।[12]


मौलिक प्रमेय

I. कोलमोगोरोव का इनवेरिएंस प्रमेय

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

कहाँ .

व्याख्या

न्यूनतम विवरण ऐसा है कि स्ट्रिंग के प्राकृतिक प्रतिनिधित्व के रूप में कार्य करता है ट्यूरिंग-पूर्ण भाषा के सापेक्ष . इसके अलावा, जैसे इसे और अधिक संपीड़ित नहीं किया जा सकता असंपीड्य और इसलिए अगणनीय स्ट्रिंग है। यह वैज्ञानिकों की यादृच्छिकता की धारणा से मेल खाता है और इस कारण को स्पष्ट करता है कि कोलमोगोरोव जटिलता गणना योग्य क्यों नहीं है।

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

प्रमाण

निम्नलिखित से लिया गया है [13] संकलक के सिद्धांत से यह ज्ञात होता है कि किन्हीं दो ट्यूरिंग-पूर्ण भाषाओं के लिए और , वहाँ संकलक मौजूद है में व्यक्त किया

 जो व्यक्त कार्यक्रमों का अनुवाद करता है  कार्यात्मक रूप से समतुल्य कार्यक्रमों में व्यक्त किया गया .

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

कहाँ , और समरूपता से हम विपरीत असमानता प्राप्त करते हैं।

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

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

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

व्याख्या

संगणनीय ब्रह्मांड में, एन्कोडिंग के साथ घटना दी गई है भौतिक प्रक्रिया द्वारा उत्पन्न उस घटना की संभावना अच्छी तरह से परिभाषित होती है और विशिष्ट और स्वतंत्र कारणों की संभावनाओं के योग के बराबर होती है। उपसर्ग-मुक्त मानदंड वास्तव में कारणात्मक स्वतंत्रता की गारंटी देता है।

प्रमाण

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

क्राफ्ट की असमानता बताती है कि तारों का क्रम दिया गया है कोडवर्ड के साथ उपसर्ग कोड मौजूद है कहाँ अगर और केवल अगर:

कहाँ वर्णमाला का आकार है .

व्यापकता की हानि के बिना, मान लीजिए कि हम आदेश दे सकते हैं ऐसा है कि:

अब, प्रत्येक चरण में यदि और केवल यदि उपसर्ग कोड मौजूद है चुनने के लिए कम से कम कोडवर्ड है जिसमें पिछला कोई भी कोड शामिल नहीं है उपसर्ग के रूप में कोडवर्ड. पिछले चरण में कोडवर्ड के अस्तित्व के कारण कोडवर्ड वर्जित हैं क्योंकि उनमें कोडवर्ड शामिल हैं उपसर्ग के रूप में. इसका तात्पर्य यह है कि सामान्य तौर पर उपसर्ग कोड मौजूद होता है यदि और केवल यदि:

द्वारा दोनों पक्षों को विभाजित करना , हम देखतें है:

है

इतिहास

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


उदाहरण

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

प्रमुख लोग

यह भी देखें

संदर्भ

  1. Markus Müller. Law without Law: from observer states to physics via algorithmic information theory. Quantum: the open journal for quantum science. 06 June 2020.
  2. Solomonoff, R., "A Preliminary Report on a General Theory of Inductive Inference", Report V-131, Zator Co., Cambridge, Ma. (Nov. 1960 revision of the Feb. 4, 1960 report).
  3. Li, M. and Vitanyi, P., An Introduction to Kolmogorov Complexity and Its Applications, 3rd Edition, Springer Science and Business Media, N.Y., 2008
  4. Hutter, M., Legg, S., and Vitanyi, P., "Algorithmic Probability", Scholarpedia, 2(8):2572, 2007.
  5. Li and Vitanyi, 2008, p. 347
  6. Li and Vitanyi, 2008, p. 341
  7. Li and Vitanyi, 2008, p. 339.
  8. Hutter, M., "Algorithmic Information Theory", Scholarpedia, 2(3):2519.
  9. Solomonoff, R., "The Kolmogorov Lecture: The Universal Distribution and Machine Learning" The Computer Journal, Vol 46, No. 6 p 598, 2003.
  10. Gács, P. and Vitányi, P., "In Memoriam Raymond J. Solomonoff", IEEE Information Theory Society Newsletter, Vol. 61, No. 1, March 2011, p 11.
  11. Levin, L.A., "Universal Search Problems", in Problemy Peredaci Informacii 9, pp. 115–116, 1973
  12. Solomonoff, R., "Complexity-Based Induction Systems: Comparisons and Convergence Theorems," IEEE Trans. on Information Theory, Vol. IT-24, No. 4, pp. 422-432, July 1978
  13. Grünwald, P. and Vitany , P. Algorithmic Information Theory. Arxiv. 2008.
  14. Solomonoff, R., "The Discovery of Algorithmic Probability", Journal of Computer and System Sciences, Vol. 55, No. 1, pp. 73-88, August 1997.
  15. Solomonoff, R., "A Preliminary Report on a General Theory of Inductive Inference", Report V-131, Zator Co., Cambridge, Ma. (Nov. 1960 revision of the Feb. 4, 1960 report).
  16. Solomonoff, R., "A Formal Theory of Inductive Inference, Part I". Information and Control, Vol 7, No. 1 pp 1-22, March 1964.
  17. Solomonoff, R., "A Formal Theory of Inductive Inference, Part II" Information and Control, Vol 7, No. 2 pp 224–254, June 1964.


स्रोत

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

अग्रिम पठन


बाहरी संबंध