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

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

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

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

अवलोकन

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

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

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

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

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

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

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

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

मौलिक प्रमेय

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

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

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

कहाँ $K_{U}(x)=\min _{p}\{|p|:U(p)=x\}$.

व्याख्या

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

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

प्रमाण

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

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

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

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

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

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

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

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

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

व्याख्या

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

प्रमाण

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

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

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

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

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

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

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

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

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

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

है

इतिहास

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

उदाहरण

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

प्रमुख लोग

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

यह भी देखें

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

स्रोत

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

अग्रिम पठन

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

बाहरी संबंध

• Algorithmic Probability at Scholarpedia
• Solomonoff's publications