सूचना दूरी: Difference between revisions

Revision as of 14:31, 29 April 2023

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

गुण

औपचारिक रूप से सूचना दूरी के $ID(x,y)$ बीच में $x$ और $y$ द्वारा परिभाषित किया गया है

ID(x,y)=\min\{|p|:p(x)=y\;\&\;p(y)=x\},

साथ $p$ सार्वभौमिक कंप्यूटर के लिए एक परिमित बाइनरी कार्यक्रम इनपुट के रूप में बाइनरी को में परिभाषित करें इससे यह सिद्ध है कि $ID(x,y)=E(x,y)+O(\log \cdot \max\{K(x\mid y),K(y\mid x)\})$ साथ

E(x,y)=\max\{K(x\mid y),K(y\mid x)\},

जहाँ

K(\cdot \mid \cdot )

द्वारा परिभाषित कोलमोगोरोव की जटिलता है।

सार्वभौमिकता

होने देना $\Delta$ ऊपरी अर्द्धगणना योग्य दूरियों का वर्ग हो $D(x,y)$ जो घनत्व की स्थिति को संतुष्ट करता है

\sum _{x:x\neq y}2^{-D(x,y)}\leq 1,\;\sum _{y:y\neq x}2^{-D(x,y)}\leq 1,

यह अप्रासंगिक दूरियों को बाहर करता है जैसे $D(x,y)={\frac {1}{2}}$ के लिए $x\neq y$ ; यह इस बात का ध्यान रखता है कि यदि दूरी बढ़ती है तो दी गई वस्तु की उस दूरी के भीतर वस्तुओं की संख्या बढ़ती है। अगर $D\in \Delta$ तब $E(x,y)\leq D(x,y)$ एक निरंतर योगात्मक शब्द तक।^[3]दूरी की संभाव्यता अभिव्यक्तियाँ सूचना सममित कोहोलॉजी में पहला कोहोमोलॉजिकल वर्ग है,^[4] जिसे सार्वभौमिकता संपत्ति के रूप में माना जा सकता है।

मीट्रिक

दूरी $E(x,y)$ एक योज्य तक एक मीट्रिक स्थान है $O(\log .\max\{K(x\mid y),K(y\mid x)\})$ मीट्रिक (इन) समानता में शब्द।^[3]1981 में हान द्वारा दिखाया गया मीट्रिक का संभाव्य संस्करण वास्तव में अद्वितीय है।^[5]

अधिकतम ओवरलैप

अगर $E(x,y)=K(x\mid y)$ , फिर एक कार्यक्रम होता है $p$ लंबाई का $K(x\mid y)$ जो परिवर्तित हो जाता है $y$ को $x$ , और एक कार्यक्रम $q$ लंबाई का $K(y\mid x)-K(x\mid y)$ ऐसा है कि कार्यक्रम $qp$ धर्मान्तरित $x$ को $y$ . (कार्यक्रम स्व-परिसीमन प्रारूप के होते हैं, जिसका अर्थ है कि कोई यह तय कर सकता है कि एक कार्यक्रम कहाँ समाप्त होता है और दूसरा कार्यक्रमों के संयोजन में शुरू होता है।) अर्थात, दो वस्तुओं के बीच परिवर्तित होने वाले सबसे छोटे कार्यक्रमों को अधिकतम अतिव्यापी बनाया जा सकता है: $K(x\mid y)\leq K(y\mid x)$ इसे एक प्रोग्राम में विभाजित किया जा सकता है जो ऑब्जेक्ट को परिवर्तित करता है $x$ वस्तु के लिए $y$ , और दूसरा प्रोग्राम जो पहले धर्मान्तरित के साथ जुड़ा हुआ है $y$ को $x$ जबकि इन दो कार्यक्रमों का संयोजन इन वस्तुओं के बीच परिवर्तित करने के लिए सबसे छोटा कार्यक्रम है।^[3]

न्यूनतम ओवरलैप

प्रोग्राम वस्तुओं के बीच कनवर्ट करने के लिए $x$ और $y$ न्यूनतम ओवरलैपिंग भी बनाया जा सकता है। एक कार्यक्रम होता है $p$ लंबाई का $K(x\mid y)$ की योगात्मक अवधि तक $O(\log(\max\{K(x\mid y),K(y\mid x)\}))$ वह मानचित्र $y$ को $x$ और छोटी जटिलता है जब $x$ ज्ञात है ( $K(p\mid x)\approx 0$ ). हमारे पास दो वस्तुओं का आदान-प्रदान करने के लिए दूसरा कार्यक्रम है^[6] शैनन सूचना सिद्धांत और कोल्मोगोरोव जटिलता सिद्धांत के बीच समानता को ध्यान में रखते हुए, कोई कह सकता है कि यह परिणाम स्लीपियन-वुल्फ कोडिंग | स्लीपियन-वुल्फ और कोर्नर-इमरे सिस्ज़ार-मार्टन प्रमेयों के समानांतर है।

अनुप्रयोग

सैद्धांतिक

An.A का परिणाम। ऊपर न्यूनतम ओवरलैप पर मुचनिक एक महत्वपूर्ण सैद्धांतिक अनुप्रयोग दिखा रहा है कि कुछ कोड मौजूद हैं: किसी भी वस्तु से परिमित लक्ष्य वस्तु पर जाने के लिए एक कार्यक्रम है जो लगभग केवल लक्ष्य वस्तु पर निर्भर करता है! यह परिणाम काफी सटीक है और त्रुटि शब्द में महत्वपूर्ण सुधार नहीं किया जा सकता है।^[7] पाठ्यपुस्तक में सूचना दूरी सामग्री थी,^[8] यह एनसाइक्लोपीडिया ऑन डिस्टेंस में होता है।^[9]

व्यावहारिक

जीनोम, भाषा, संगीत, इंटरनेट हमले और वर्म्स, सॉफ़्टवेयर प्रोग्राम आदि जैसी वस्तुओं की समानता निर्धारित करने के लिए, सूचना दूरी को सामान्यीकृत किया जाता है और कोलमोगोरोव जटिलता की शर्तों को वास्तविक दुनिया कंप्रेशर्स द्वारा अनुमानित किया जाता है (कोलमोगोरोव जटिलता एक निम्न सीमा है वस्तु के एक संकुचित संस्करण के बिट्स में लंबाई)। परिणाम वस्तुओं के बीच सामान्यीकृत संपीड़न दूरी (NCD) है। यह कंप्यूटर फ़ाइलों के रूप में दी गई वस्तुओं से संबंधित है जैसे कि माउस का जीनोम या किसी पुस्तक का पाठ। यदि वस्तुओं को सिर्फ 'आइंस्टीन' या 'टेबल' या किसी पुस्तक के नाम या 'माउस' नाम से दिया जाता है, तो संपीड़न का कोई मतलब नहीं है। नाम का अर्थ क्या है, इसके बारे में हमें बाहरी जानकारी चाहिए। डेटा बेस (जैसे इंटरनेट) और डेटाबेस को खोजने के साधन (जैसे Google जैसे खोज इंजन) का उपयोग करके यह जानकारी प्रदान की जाती है। डेटा बेस पर प्रत्येक खोज इंजन जो समग्र पृष्ठ गणना प्रदान करता है, सामान्यीकृत Google दूरी (NGD) में उपयोग किया जा सकता है। एन वेरिएबल्स के डेटासेट में सभी सूचनाओं की दूरी और वॉल्यूम, बहुभिन्नरूपी पारस्परिक जानकारी, सशर्त पारस्परिक जानकारी, संयुक्त एन्ट्रापी, कुल सहसंबंधों की गणना के लिए एक पायथन पैकेज उपलब्ध है।^[10]

संदर्भ

↑ A.N. Kolmogorov, Three approaches to the quantitative definition of information, Problems Inform. Transmission, 1:1(1965), 1–7
↑ M. Li, P.M.B. Vitanyi, Theory of Thermodynamics of Computation, Proc. IEEE Physics of Computation Workshop, Dallas, Texas, USA, 1992, 42–46
↑ ^3.0 ^3.1 ^3.2 ^3.3 C.H. Bennett, P. Gacs, M. Li, P.M.B. Vitanyi, W. Zurek, Information distance, IEEE Transactions on Information Theory, 44:4(1998), 1407–1423
↑ P. Baudot, The Poincaré-Shannon Machine: Statistical Physics and Machine Learning Aspects of Information Cohomology , Entropy, 21:9 - 881 (2019)
↑ Te Sun Han, A uniqueness of Shannon information distance and related nonnegativity problems, Journal of combinatorics. 6:4 p.320-331 (1981), 30–35
↑ Muchnik, Andrej A. (2002). "सशर्त जटिलता और कोड". Theoretical Computer Science. 271 (1–2): 97–109. doi:10.1016/S0304-3975(01)00033-0.
↑ N.K Vereshchagin, M.V. Vyugin, Independent minimum length programs to translate between given strings, Proc. 15th Ann. Conf. Computational Complexity, 2000, 138–144
↑ M.Hutter, Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability, Springer, 1998
↑ M.M. Deza, E Deza, Encyclopedia of Distances, Springer, 2009, doi:10.1007/978-3-642-00234-2
↑ "InfoTopo: Topological Information Data Analysis. Deep statistical unsupervised and supervised learning - File Exchange - Github". github.com/pierrebaudot/infotopopy/. Retrieved 26 September 2020.

@@ Line 1: / Line 1: @@
-सूचना दूरी दो परिमित वस्तुओं ([[कंप्यूटर]] फ़ाइलों के रूप में प्रतिनिधित्व) के बीच की दूरी है जो सबसे छोटे कार्यक्रम में बिट्स की संख्या के रूप में व्यक्त की जाती है जो एक वस्तु को दूसरे में या इसके विपरीत एक में बदल देती है।
+सूचना दूरी दो परिमित वस्तुओं के बीच की दूरी है जो सबसे छोटे कार्यक्रम में बिट्स की संख्या के रूप में व्यक्त की जाती है तथा यह एक वस्तु को दूसरी वस्तु या इसके विपरीत सार्वभौमिक [[यूनिवर्सल कंप्यूटर|कंप्यूटर]] में बदल देती है यह  [[कोलमोगोरोव जटिलता|जटिलता]] का विस्तार है <ref name="Ko65">[http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=68&option_lang=eng A.N. Kolmogorov, Three approaches to the quantitative definition of information, Problems Inform. Transmission, 1:1(1965), 1–7]</ref>इसमें एकल परिमित वस्तु की कोलमोगोरोव जटिलता उस वस्तु की जानकारी है जो परिमित वस्तुओं की एक जोड़ी के बीच की सूचना दूरी एक वस्तु से या इसके विपरीत जाने के लिए आवश्यक न्यूनतम जानकारी है सूचना दूरी को पहली बार में परिभाषित और जांच की गई थी <ref name="LV92">[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.9045 M. Li, P.M.B. Vitanyi, Theory of Thermodynamics of Computation, Proc. IEEE Physics of Computation Workshop, Dallas, Texas, USA, 1992, 42–46]</ref> [[thermodynamic|ऊष्मागतिकीय]] सिद्धांतों पर आधारित <ref name="BGLVZ98">[http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=681318&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D681318 C.H. Bennett, P. Gacs, M. Li, P.M.B. Vitanyi, W. Zurek, Information distance, IEEE Transactions on Information Theory, 44:4(1998), 1407–1423]</ref> यह [[सामान्यीकृत संपीड़न दूरी]] और [[सामान्यीकृत Google दूरी|सामान्यीकृत दूरी]] में लागू होता है।
-[[यूनिवर्सल कंप्यूटर]]। यह [[कोलमोगोरोव जटिलता]] का विस्तार है।<ref name="Ko65">[http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=68&option_lang=eng A.N. Kolmogorov, Three approaches to the quantitative definition of information, Problems Inform. Transmission, 1:1(1965), 1–7]</ref> एकल परिमित वस्तु की कोलमोगोरोव जटिलता उस वस्तु की जानकारी है; परिमित वस्तुओं की एक जोड़ी के बीच की सूचना दूरी एक वस्तु से दूसरी या इसके विपरीत जाने के लिए आवश्यक न्यूनतम जानकारी है।
-सूचना दूरी को पहली बार में परिभाषित और जांच की गई थी <ref name="LV92">[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.9045 M. Li, P.M.B. Vitanyi, Theory of Thermodynamics of Computation, Proc. IEEE Physics of Computation Workshop, Dallas, Texas, USA, 1992, 42–46]</ref> [[thermodynamic]] सिद्धांतों पर आधारित, यह भी देखें।<ref>[http://rspa.royalsocietypublishing.org/content/452/1947/769.short M. Li, P.M.B. Vitanyi, Reversibility and Adiabatic Computation: Trading Time and Space for Energy,  Proc. R. Soc. Lond. A 9 April 1996 vol. 452 no. 1947 769–789]</ref> इसके बाद, में अंतिम रूप प्राप्त किया।<ref name="BGLVZ98">[http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=681318&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D681318 C.H. Bennett, P. Gacs, M. Li, P.M.B. Vitanyi, W. Zurek, Information distance, IEEE Transactions on Information Theory, 44:4(1998), 1407–1423]</ref> यह [[सामान्यीकृत संपीड़न दूरी]] और [[सामान्यीकृत Google दूरी]] में लागू होता है।
 == गुण ==
-औपचारिक रूप से सूचना दूरी <math>ID(x,y)</math> बीच में <math>x</math> और <math>y</math> द्वारा परिभाषित किया गया है
+औपचारिक रूप से सूचना दूरी के <math>ID(x,y)</math> बीच में <math>x</math> और <math>y</math> द्वारा परिभाषित किया गया है
 :<math>
 ID(x,y) = \min \{|p|: p(x)=y \; \& \;p(y) =x \},
 </math>
-साथ <math>p</math> फिक्स्ड यूनिवर्सल कंप्यूटर के लिए एक परिमित बाइनरी प्रोग्राम
+साथ <math>p</math> सार्वभौमिक कंप्यूटर के लिए एक परिमित बाइनरी कार्यक्रम इनपुट के रूप में बाइनरी को में परिभाषित करें इससे यह सिद्ध है कि<math>ID(x,y) = E(x,y)+O(\log \cdot \max \{K(x\mid y), K(y\mid x)\} )</math> साथ
-इनपुट के रूप में बाइनरी स्ट्रिंग्स को परिमित करें <math>x,y</math>. में <ref name="BGLVZ98"/>यह सिद्ध है
-<math>ID(x,y) = E(x,y)+O(\log \cdot \max \{K(x\mid y), K(y\mid x)\} )</math> साथ
 :<math>
 E(x,y) = \max \{K(x\mid y), K(y\mid x)\},
-</math> कहाँ <math>K(\cdot \mid \cdot)</math> द्वारा परिभाषित कोलमोगोरोव जटिलता है <ref name="Ko65"/>उपसर्ग प्रकार का।<ref>[http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=1039&option_lang=eng  L.A. Levin, Laws of Information Conservation (Nongrowth) and Aspects of the Foundation of Probability Theory, Problems Inform. Transmission, 10:3(1974), 30–35]</ref> यह <math>E(x,y)</math> महत्वपूर्ण मात्रा है।
+</math> जहाँ <math>K(\cdot \mid \cdot)</math> द्वारा परिभाषित कोलमोगोरोव की जटिलता है।
 === सार्वभौमिकता ===

Anonymous

Search

सूचना दूरी: Difference between revisions

Namespaces

More

Page actions

Revision as of 14:31, 29 April 2023

Contents