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

From Vigyanwiki
No edit summary
No edit summary
 
(6 intermediate revisions by 3 users not shown)
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>
 
 
 
==अवलोकन==
==अवलोकन==


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


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


ओकाम का रेजर और एपिकुरस का सिद्धांत अनिवार्य रूप से [[सार्वभौमिक पूर्व]] के दो अलग-अलग गैर-गणितीय अनुमान हैं।
ओकाम का रेजर और एपिकुरस का सिद्धांत अनिवार्य रूप से [[सार्वभौमिक पूर्व]] के दो अलग-अलग गैर-गणितीय अनुमान हैं।
Line 14: Line 11:
* '''ओकाम का उस्तरा''': उन सिद्धांतों में से जो देखी गई घटनाओं के अनुरूप हैं, सबसे सरल सिद्धांत का चयन करना चाहिए।<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> यह उस अवलोकन की सबसे संभावित निरंतरता की पूर्वानुमान करता है, और यह माप प्रदान करता है कि यह निरंतरता कितनी संभावित होगी|


सोलोमनॉफ़ का गणनीय माप एक निश्चित शक्तिशाली अर्थ में [[सार्वभौमिकता (दर्शन)]] है, किन्तु गणना का समय अनंत हो सकता है। इस समस्या से निपटने की एक विधि लियोनिद लेविन के खोज एल्गोरिदम का प्रकार है,<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 34:
=== व्याख्या ===
=== व्याख्या ===


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


इसका तात्पर्य यह है कि डेटा के किसी भी भाग में यादृच्छिक स्ट्रिंग के संदर्भ में आवश्यक और पर्याप्त प्रतिनिधित्व होता है।
इसका तात्पर्य यह है कि डेटा के किसी भी भाग में यादृच्छिक स्ट्रिंग के संदर्भ में आवश्यक और पर्याप्त प्रतिनिधित्व होता है।
Line 45: Line 42:
निम्नलिखित से लिया गया है <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>U_1</math> में व्यक्त एक कंपाइलर <math>\Lambda_1</math> मौजूद है जो <math>U_2</math> में व्यक्त प्रोग्रामों को <math>U_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>p</math> को सबसे छोटा प्रोग्राम मानते हैं जो किसी दिए गए स्ट्रिंग <math>x</math> को प्रिंट करता है:
यह इस प्रकार है कि यदि हम <math>p</math> को सबसे छोटा प्रोग्राम मानते हैं जो किसी दिए गए स्ट्रिंग <math>x</math> को प्रिंट करता है:
Line 60: Line 57:
:<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>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>x \in \{0,1\}^*</math> भौतिक प्रक्रिया द्वारा उत्पन्न उस घटना की संभावना अच्छी तरह से परिभाषित होती है और विशिष्ट और स्वतंत्र कारणों की संभावनाओं के योग के बराबर होती है। उपसर्ग-मुक्त मानदंड वास्तव में कारणात्मक स्वतंत्रता की गारंटी देता है।
संगणनीय यूनिवर्स में, भौतिक प्रक्रिया द्वारा उत्पन्न एन्कोडिंग <math>x \in \{0,1\}^*</math> के साथ घटना को देखते हुए उस घटना की संभावना अच्छी तरह से परिभाषित होती है और विशिष्ट और स्वतंत्र कारणों की संभावनाओं के योग के बराबर होती है। उपसर्ग-मुक्त मानदंड वास्तव में कारणात्मक स्वतंत्रता की गारंटी देता है।


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


क्राफ्ट की असमानता बताती है कि तारों का क्रम दिया गया है <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>
\sum_{i=1}^n s^{-k_i} \leq 1  
\sum_{i=1}^n s^{-k_i} \leq 1  
</math>
</math>
जहाँ <math>s</math> वर्णमाला का आकार है <math>S</math>.
जहाँ <math>s</math> वर्णमाला <math>S</math> का आकार है।


व्यापकता की हानि के बिना, मान लीजिए कि हम आदेश दे सकते हैं <math>k_i</math> ऐसा है कि:
व्यापकता की हानि के बिना, मान लीजिए कि हम <math>k_i</math> को इस प्रकार आदेश दे सकते हैं कि:


:<math>
:<math>
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>
\forall j \geq 2, s^{k_j} > \sum_{i=1}^{j-1} s^{k_j - k_i}
\forall j \geq 2, s^{k_j} > \sum_{i=1}^{j-1} s^{k_j - k_i}
</math>
</math>
द्वारा दोनों पक्षों को विभाजित करना <math>s^{k_j}</math>, हम देखतें है:
दोनों पक्षों को <math>s^{k_j}</math> से विभाजित करने पर, हम पाते हैं:


:<math>
:<math>
\sum_{i=1}^n s^{-k_i} \leq 1  
\sum_{i=1}^n s^{-k_i} \leq 1  
</math>
</math>
है
इति सिद्धम्


== इतिहास ==
== इतिहास ==


सोलोमनॉफ़ ने 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> के साथ इन विचारों को पूरी तरह से स्पष्ट किया ।




Line 110: Line 107:


==यह भी देखें==
==यह भी देखें==
* सोलोमनॉफ का [[आगमनात्मक अनुमान]] का सिद्धांत
* सोलोमनॉफ का [[आगमनात्मक अनुमान|विवेचनात्मक अनुमान]] का सिद्धांत
* एल्गोरिथम सूचना सिद्धांत
* एल्गोरिथम सूचना सिद्धांत
*[[बायेसियन अनुमान]]
*[[बायेसियन अनुमान]]
* आगमनात्मक अनुमान
* विवेचनात्मक अनुमान
* [[आगमनात्मक संभाव्यता]]
* [[आगमनात्मक संभाव्यता|विवेचनात्मक संभाव्यता]]
* कोलमोगोरोव जटिलता
* कोलमोगोरोव जटिलता
* यूनिवर्सल ट्यूरिंग मशीन
* यूनिवर्सल ट्यूरिंग मशीन
Line 134: Line 131:
* [http://world.std.com/~rjs/publications/pubs.html Solomonoff's publications]
* [http://world.std.com/~rjs/publications/pubs.html Solomonoff's publications]


{{DEFAULTSORT:Algorithmic Probability}}[[Category: एल्गोरिथम सूचना सिद्धांत]] [[Category: संभाव्यता व्याख्याएँ]] [[Category: कृत्रिम होशियारी]]
{{DEFAULTSORT:Algorithmic Probability}}
 
 


[[Category: Machine Translated Page]]
[[Category:All articles needing examples|Algorithmic Probability]]
[[Category:Created On 07/07/2023]]
[[Category:Articles needing examples from September 2017|Algorithmic Probability]]
[[Category:Articles with invalid date parameter in template|Algorithmic Probability]]
[[Category:Created On 07/07/2023|Algorithmic Probability]]
[[Category:Machine Translated Page|Algorithmic Probability]]
[[Category:Pages with script errors|Algorithmic Probability]]
[[Category:एल्गोरिथम सूचना सिद्धांत|Algorithmic Probability]]
[[Category:कृत्रिम होशियारी|Algorithmic Probability]]
[[Category:संभाव्यता व्याख्याएँ|Algorithmic Probability]]

Latest revision as of 16:02, 25 July 2023

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

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

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

अवलोकन

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

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

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

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

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

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

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

सोलोमनॉफ़ का गणनीय माप निश्चित शक्तिशाली अर्थ में सार्वभौमिकता (दर्शन) है, किन्तु गणना का समय अनंत हो सकता है। इस समस्या से निपटने की विधि लियोनिद लेविन के खोज एल्गोरिदम का प्रकार है,[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

अग्रिम पठन


बाहरी संबंध