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

Revision as of 10:06, 12 July 2023

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

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

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

अवलोकन

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

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

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

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

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

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

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

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

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

मौलिक प्रमेय

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$ असंपीड्य और इसलिए अगणनीय स्ट्रिंग है। यह वैज्ञानिकों की यादृच्छिकता की धारणा से मेल खाता है और इस कारण को स्पष्ट करता है कि कोलमोगोरोव जटिलता गणना योग्य क्यों नहीं है।

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

प्रमाण

निम्नलिखित से लिया गया है ^[13]

संकलक के सिद्धांत से, यह ज्ञात है कि किन्हीं दो ट्यूरिंग-कम्प्लीट भाषाओं $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 के आसपास इससे संबंधित अपरिवर्तनीय प्रमेय के साथ एल्गोरिथम संभाव्यता की अवधारणा का आविष्कार किया,^[14] इस पर रिपोर्ट प्रकाशित की: आगमनात्मक अनुमान के सामान्य सिद्धांत पर प्रारंभिक रिपोर्ट।^[15] उन्होंने 1964 में ए फॉर्मल थ्योरी ऑफ़ इंडक्टिव इंफ़रेंस, भाग I^[16] और भाग II^[17] के साथ इन विचारों को पूरी तरह से स्पष्ट किया ।

उदाहरण

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

प्रमुख लोग

यह भी देखें

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

संदर्भ

↑ 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.
↑ 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).
↑ Li, M. and Vitanyi, P., An Introduction to Kolmogorov Complexity and Its Applications, 3rd Edition, Springer Science and Business Media, N.Y., 2008
↑ Hutter, M., Legg, S., and Vitanyi, P., "Algorithmic Probability", Scholarpedia, 2(8):2572, 2007.
↑ Li and Vitanyi, 2008, p. 347
↑ Li and Vitanyi, 2008, p. 341
↑ Li and Vitanyi, 2008, p. 339.
↑ Hutter, M., "Algorithmic Information Theory", Scholarpedia, 2(3):2519.
↑ Solomonoff, R., "The Kolmogorov Lecture: The Universal Distribution and Machine Learning" The Computer Journal, Vol 46, No. 6 p 598, 2003.
↑ 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.
↑ Levin, L.A., "Universal Search Problems", in Problemy Peredaci Informacii 9, pp. 115–116, 1973
↑ 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
↑ Grünwald, P. and Vitany , P. Algorithmic Information Theory. Arxiv. 2008.
↑ Solomonoff, R., "The Discovery of Algorithmic Probability", Journal of Computer and System Sciences, Vol. 55, No. 1, pp. 73-88, August 1997.
↑ 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).
↑ Solomonoff, R., "A Formal Theory of Inductive Inference, Part I". Information and Control, Vol 7, No. 1 pp 1-22, March 1964.
↑ Solomonoff, R., "A Formal Theory of Inductive Inference, Part II" Information and Control, Vol 7, No. 2 pp 224–254, June 1964.

स्रोत

ली, एम. और विटानी, पी., एन इंट्रोडक्शन टू कोलमोगोरोव कॉम्प्लेक्सिटी एंड इट्स एप्लीकेशन्स, तीसरा संस्करण, स्प्रिंगर साइंस एंड बिजनेस मीडिया, एन.वाई., 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

बाहरी संबंध

[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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

@@ 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: @@
 ==अवलोकन==
-एल्गोरिथम संभाव्यता सोलोमनॉफ़ के आगमनात्मक अनुमान के सिद्धांत का मुख्य घटक है, जो अवलोकनों पर आधारित भविष्यवाणी का सिद्धांत हैं; इसका आविष्कार मशीन लर्निंग के लिए उपयोग करने के लक्ष्य से किया गया था; प्रतीकों का क्रम दिया गया है, कि अगला कौन सा आएगा? सोलोमोनॉफ़ का सिद्धांत उत्तर प्रदान करता है जो एक निश्चित अर्थ में इष्टतम है, चूंकि यह गणना योग्य नहीं है। उदाहरण के लिए, [[कार्ल पॉपर]] के अनौपचारिक आगमनात्मक अनुमान सिद्धांत सोलोमोनॉफ़ गणितीय रूप से कठोर है।
+एल्गोरिथम संभाव्यता सोलोमनॉफ़ के आगमनात्मक अनुमान के सिद्धांत का मुख्य घटक है, जो अवलोकनों पर आधारित भविष्यवाणी का सिद्धांत हैं; इसका आविष्कार मशीन लर्निंग के लिए उपयोग करने के लक्ष्य से किया गया था; प्रतीकों का क्रम दिया गया है, कि अगला कौन सा आएगा? सोलोमोनॉफ़ का सिद्धांत उत्तर प्रदान करता है जो निश्चित अर्थ में इष्टतम है, चूंकि यह गणना योग्य नहीं है। उदाहरण के लिए, [[कार्ल पॉपर]] के अनौपचारिक आगमनात्मक अनुमान सिद्धांत सोलोमोनॉफ़ गणितीय रूप से कठोर है।
 सोलोमोनोव की एल्गोरिथम संभाव्यता के लिए चार प्रमुख प्रेरणाएँ थीं: ओकाम का रेजर, एपिकुरस का कई स्पष्टीकरणों का सिद्धांत, आधुनिक कंप्यूटिंग सिद्धांत (उदाहरण के लिए सार्वभौमिक ट्यूरिंग मशीन का उपयोग) और भविष्यवाणी के लिए बेयस का नियम।<ref>Li and Vitanyi, 2008, p. 347</ref>
@@ Line 16: / Line 16: @@
 यूनिवर्सल प्रायर के केंद्र में कंप्यूटर का अमूर्त मॉडल है, जैसे यूनिवर्सल ट्यूरिंग मशीन।<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>
@@ Line 37: / Line 37: @@
 === व्याख्या ===
-न्यूनतम विवरण <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 45: @@
 निम्नलिखित से लिया गया है <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>U_1</math> में व्यक्त कंपाइलर <math>\Lambda_1</math> उपस्थित है जो <math>U_2</math> में व्यक्त प्रोग्रामों को <math>U_1</math> में व्यक्त कार्यात्मक-समतुल्य प्रोग्रामों में अनुवाद करता है।
 यह इस प्रकार है कि यदि हम <math>p</math> को सबसे छोटा प्रोग्राम मानते हैं जो किसी दिए गए स्ट्रिंग <math>x</math> को प्रिंट करता है:
@@ Line 60: / Line 60: @@
 :<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 70: @@
 यह [[क्राफ्ट-मैकमिलन असमानता]] का तात्कालिक परिणाम है।
-क्राफ्ट की असमानता बताती है कि स्ट्रिंग <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>
@@ Line 82: / Line 82: @@
 k_1 \leq k_2 \leq ... \leq k_n
 </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>

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 10:06, 12 July 2023

Contents

अवलोकन

मौलिक प्रमेय

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

व्याख्या

प्रमाण

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

व्याख्या

प्रमाण

इतिहास

उदाहरण

प्रमुख लोग

यह भी देखें

संदर्भ

स्रोत

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 10:06, 12 July 2023

अवलोकन

मौलिक प्रमेय

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

व्याख्या

प्रमाण

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

व्याख्या

प्रमाण

इतिहास

उदाहरण

प्रमुख लोग

यह भी देखें

संदर्भ

स्रोत

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories