सूचना दूरी: Difference between revisions
No edit summary |
No edit summary |
||
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 दूरी|सामान्यीकृत दूरी]] में लागू होती है। | ||
== गुण == | == गुण == | ||
Line 6: | Line 6: | ||
ID(x,y) = \min \{|p|: p(x)=y \; \& \;p(y) =x \}, | ID(x,y) = \min \{|p|: p(x)=y \; \& \;p(y) =x \}, | ||
</math> | </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> | :<math> | ||
E(x,y) = \max \{K(x\mid y), K(y\mid x)\}, | E(x,y) = \max \{K(x\mid y), K(y\mid x)\}, | ||
</math> जहाँ <math>K(\cdot \mid \cdot)</math> | </math> जहाँ <math>K(\cdot \mid \cdot)</math> समीकरण जटिलता है जिसे उपसर्ग द्वारा परिभाषित किया गया है। | ||
=== सार्वभौमिकता === | === सार्वभौमिकता === | ||
सार्वभौमिकता ऊपरी अर्द्धगणना योग्य दूरियों का वर्ग हो जैसे <math>D(x,y)</math> जो [[घनत्व]] की स्थिति को संतुष्ट करता | सार्वभौमिकता ऊपरी अर्द्धगणना योग्य दूरियों का वर्ग हो जैसे <math>D(x,y)</math> जो [[घनत्व]] की स्थिति को संतुष्ट करता है। | ||
:<math> | :<math> | ||
\sum_{x:x \neq y} 2^{-D(x,y)} \leq 1 , \; \sum_{y:y \neq x} 2^{-D(x,y)} \leq 1, | \sum_{x:x \neq y} 2^{-D(x,y)} \leq 1 , \; \sum_{y:y \neq x} 2^{-D(x,y)} \leq 1, | ||
Line 19: | Line 19: | ||
=== मीट्रिक === | === मीट्रिक === | ||
दूरी <math>E(x,y)</math> योज्य तक एक [[मीट्रिक स्थान|प्रवेशिका स्थान]] है जो <math>O(\log .\max \{K(x\mid y), K(y\mid x)\} )</math> प्रवेशिका <ref name="BGLVZ98"/>1981 में | दूरी <math>E(x,y)</math> योज्य तक एक [[मीट्रिक स्थान|प्रवेशिका स्थान]] है जो <math>O(\log .\max \{K(x\mid y), K(y\mid x)\} )</math> प्रवेशिका <ref name="BGLVZ98"/>1981 में हॉर्न द्वारा दिखाया गया कि प्रवेशिका संभाव्य संस्करण में अद्वितीय है।<ref>[https://www.researchgate.net/publication/268827547_A_uniqueness_of_Shannon%27s_information_distance_and_related_nonnegativity_problems Te Sun Han, A uniqueness of Shannon information distance and related nonnegativity problems, Journal of combinatorics. 6:4 p.320-331 (1981), 30–35]</ref> | ||
=== अधिकतम अतिच्छादन === | === अधिकतम अतिच्छादन === | ||
अगर <math>E(x,y) = K(x\mid y)</math> एक कार्यक्रम होता है तो <math>p</math> लंबाई <math>K(x\mid y)</math> में परिवर्तित हो जाता है <math>y</math> को <math>x</math> और एक कार्यक्रम <math>q</math> लंबाई का <math>K(y\mid x)-K(x\mid y)</math> ऐसा रूपांतरण है कि कार्यक्रम <math>qp</math> धर्मान्तरित <math>x</math> तथा <math>y</math>.अर्थात दो वस्तुओं के बीच परिवर्तित होने वाले सबसे छोटे कार्यक्रमों को अधिकतम अतिव्यापी बनाया जा सकता है <math>K(x\mid y) \leq K(y\mid x)</math> इसे एक कार्यक्रम में विभाजित किया जा सकता है जो बहुविकल्पीय को परिवर्तित करता है इसमें <math>x</math> वस्तु के लिए <math>y</math>और दूसरा कार्यक्रम जो पहले | अगर <math>E(x,y) = K(x\mid y)</math> एक कार्यक्रम होता है तो <math>p</math> लंबाई <math>K(x\mid y)</math> में परिवर्तित हो जाता है <math>y</math> को <math>x</math> और एक कार्यक्रम <math>q</math> लंबाई का <math>K(y\mid x)-K(x\mid y)</math> ऐसा रूपांतरण है कि कार्यक्रम <math>qp</math> धर्मान्तरित <math>x</math> तथा <math>y</math>.अर्थात दो वस्तुओं के बीच परिवर्तित होने वाले सबसे छोटे कार्यक्रमों को अधिकतम अतिव्यापी बनाया जा सकता है <math>K(x\mid y) \leq K(y\mid x)</math> इसे एक कार्यक्रम में विभाजित किया जा सकता है जो बहुविकल्पीय को परिवर्तित करता है इसमें <math>x</math> वस्तु के लिए <math>y</math> और दूसरा कार्यक्रम जो पहले रूपांतरण के साथ जुड़ा हुआ है जैसे <math>y</math> तथा <math>x</math> जबकि इन दो कार्यक्रमों का संयोजन इन वस्तुओं के बीच परिवर्तित करने के लिए सबसे छोटा कार्यक्रम है।<ref name="BGLVZ98"/> | ||
=== न्यूनतम अतिच्छादन === | === न्यूनतम अतिच्छादन === | ||
कार्यक्रम को वस्तुओं के बीच बदलने के लिए <math>x</math> और <math>y</math> न्यूनतम अतिच्छादन के लिए भी बनाया जा सकता है इसमें एक कार्यक्रम होता है जहाँ <math>p</math> लंबाई<math>O(\log (\max \{K(x\mid y), K(y\mid x)\}) )</math> है यहाँ <math>y</math> तथा <math>x</math> छोटी जटिलता है जब <math>x</math> ज्ञात है तो (<math>K(p\mid x)\approx 0</math>).जबकि हमारे पास दो वस्तुओं का आदान-प्रदान करने के लिए दूसरा कार्यक्रम है<ref>{{cite journal| doi=10.1016/S0304-3975(01)00033-0 | volume=271 | issue=1–2 | title=सशर्त जटिलता और कोड| year=2002 | journal=Theoretical Computer Science | pages=97–109 | last1 = Muchnik | first1 = Andrej A.| doi-access=free }}</ref> इसमें [[शैनन सूचना सिद्धांत|शैन्य सूचना सिद्धांत]] और | कार्यक्रम को वस्तुओं के बीच बदलने के लिए <math>x</math> और <math>y</math> न्यूनतम अतिच्छादन के लिए भी बनाया जा सकता है इसमें एक कार्यक्रम होता है जहाँ <math>p</math> लंबाई<math>O(\log (\max \{K(x\mid y), K(y\mid x)\}) )</math> है यहाँ <math>y</math> तथा <math>x</math> छोटी जटिलता है जब <math>x</math> ज्ञात है तो (<math>K(p\mid x)\approx 0</math>).जबकि हमारे पास दो वस्तुओं का आदान-प्रदान करने के लिए दूसरा कार्यक्रम है<ref>{{cite journal| doi=10.1016/S0304-3975(01)00033-0 | volume=271 | issue=1–2 | title=सशर्त जटिलता और कोड| year=2002 | journal=Theoretical Computer Science | pages=97–109 | last1 = Muchnik | first1 = Andrej A.| doi-access=free }}</ref> इसमें [[शैनन सूचना सिद्धांत|शैन्य सूचना सिद्धांत]] और समीकरण की जटिलता की समानता को ध्यान में रखते हुए कोई कह सकता है कि यह परिणाम स्वीडन वुल्फ और कोर्नर इनरे सिज्जार मॉर्टन प्रमेय की समानता है। | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
Line 32: | Line 32: | ||
ए एन ए का परिणाम है | ए एन ए का परिणाम है | ||
जो ऊपर न्यूनतम अतिच्छादन पर मुचनिक ने एक महत्वपूर्ण सैद्धांत दिया है जो दिखा रहा है कि कुछ संकेत एकत्रित हैं जो किसी भी वस्तु से परिमित लक्ष्य पर जाने के लिए एक कार्यक्रम से | जो ऊपर न्यूनतम अतिच्छादन पर मुचनिक ने एक महत्वपूर्ण सैद्धांत दिया है जो दिखा रहा है कि कुछ संकेत एकत्रित हैं जो किसी भी वस्तु से परिमित लक्ष्य पर जाने के लिए एक कार्यक्रम से जुड़ते हैं जो लक्ष्य वस्तु पर निर्भर करता है यह परिणाम काफी सही है और त्रुटि शब्द में महत्वपूर्ण सुधार नहीं किया जा सकता है सूचना दूरी पाठ्यपुस्तक की सामग्री थी यह दूरी पर विश्वकोश में होती है। | ||
व्यवहारिकता | व्यवहारिकता | ||
जीनोम,भाषा, संगीत, इंटरनेट और कृमि, सॉफ्टवेयर कार्यक्रम आदि जैसी वस्तुओं की समानता निर्धारित करने के लिए सूचना दूरी को सामान्यीकृत किया जाता है और | जीनोम,भाषा, संगीत, इंटरनेट और कृमि, सॉफ्टवेयर कार्यक्रम आदि जैसी वस्तुओं की समानता निर्धारित करने के लिए सूचना दूरी को सामान्यीकृत किया जाता है और समीकरण जटिलता की शर्तों को वास्तविक दुनिया द्वारा जोड़ा जाता है समीकरण जटिलता एक निम्न सीमा है जो वस्तु के एक संकुचित संस्करण के बिट्स लंबाई व परिणाम सामान्यीकृत संपीड़न की दूरी है यह कंप्यूटर फाइलों के रूप में दी गई वस्तुओं से संबंधित है जैसे कि माउस का जीनोम या किसी पुस्तक का पाठ यदि वस्तुओं को सिर्फ 'आइंस्टीन' या किसी पुस्तक के नाम तथा 'माउस' के नाम से दिया जाता है तो संपीड़न का कोई मतलब नहीं है इसके बारे में हमें बाहरी जानकारी चाहिए डेटा बेस जैसे इंटरनेट और डेटाबेस को खोजने के साधन जैसे गूगल खोज इंजन का उपयोग करके यह जानकारी प्रदान की जाती है डेटा बेस पर प्रत्येक खोज इंजन जो समग्र पृष्ठ गणना प्रदान करता है तथा सामान्यीकृत गूगल दूरी में उपयोग किया जा सकता है एन वेरिएबल्स के डेटा समूह में सभी सूचनाओं की दूरी और ध्वनि बहुभिन्नरूपी पारस्परिक जानकारी पारस्परिक जानकारी, संयुक्त एन्ट्रापी, कुल सहसंबंधों की गणना के लिए एक पायथन पैकेज उपलब्ध है। | ||
== संदर्भ == | == संदर्भ == |
Revision as of 08:02, 17 May 2023
सूचना दूरी दो परिमित वस्तुओं के बीच की दूरी है जो सबसे छोटे कार्यक्रम में बिट्स की संख्या के रूप में व्यक्त की जाती है तथा यह एक वस्तु को दूसरी वस्तु या इसके विपरीत सार्वभौमिक कार्य में बदल देती है यह जटिलता का विस्तार है [1]इसमें एकल परिमित वस्तु की समीकरण जटिलता उस वस्तु की जानकारी है जो परिमित वस्तुओं की एक जोड़ी के बीच की सूचना दूरी एक वस्तु या इसके विपरीत जाने के लिए आवश्यक न्यूनतम जानकारी है सूचना दूरी को पहली बार में परिभाषित की गई थी [2] ऊष्मागतिकीय सिद्धांतों पर आधारित [3] यह सामान्यीकृत संपीड़न दूरी और सामान्यीकृत दूरी में लागू होती है।
गुण
औपचारिक रूप से सूचना दूरी के बीच में और द्वारा परिभाषित किया गया है
साथ सार्वभौमिक कंप्यूटर के लिए एक परिमित बाइनरी कार्यक्रम इनपुट के रूप में बाइनरी को परिभाषित करें इससे यह सिद्ध है कि साथ
- जहाँ समीकरण जटिलता है जिसे उपसर्ग द्वारा परिभाषित किया गया है।
सार्वभौमिकता
सार्वभौमिकता ऊपरी अर्द्धगणना योग्य दूरियों का वर्ग हो जैसे जो घनत्व की स्थिति को संतुष्ट करता है।
यह अप्रासंगिक दूरियों को बाहर करता है जैसे के लिए यह इस बात का ध्यान रखता है कि यदि दूरी बढ़ती है तो दी गई वस्तु की उस दूरी के भीतर वस्तुओं की संख्या बढ़ती है तो तब यह एक निरंतर योगात्मक शब्द तक की [3]दूरी संभाव्यता अभिव्यक्तियाँ सूचना सममित में पहला वर्ग है [4] जिसे सार्वभौमिकता संपत्ति के रूप में जाना जा सकता है।
मीट्रिक
दूरी योज्य तक एक प्रवेशिका स्थान है जो प्रवेशिका [3]1981 में हॉर्न द्वारा दिखाया गया कि प्रवेशिका संभाव्य संस्करण में अद्वितीय है।[5]
अधिकतम अतिच्छादन
अगर एक कार्यक्रम होता है तो लंबाई में परिवर्तित हो जाता है को और एक कार्यक्रम लंबाई का ऐसा रूपांतरण है कि कार्यक्रम धर्मान्तरित तथा .अर्थात दो वस्तुओं के बीच परिवर्तित होने वाले सबसे छोटे कार्यक्रमों को अधिकतम अतिव्यापी बनाया जा सकता है इसे एक कार्यक्रम में विभाजित किया जा सकता है जो बहुविकल्पीय को परिवर्तित करता है इसमें वस्तु के लिए और दूसरा कार्यक्रम जो पहले रूपांतरण के साथ जुड़ा हुआ है जैसे तथा जबकि इन दो कार्यक्रमों का संयोजन इन वस्तुओं के बीच परिवर्तित करने के लिए सबसे छोटा कार्यक्रम है।[3]
न्यूनतम अतिच्छादन
कार्यक्रम को वस्तुओं के बीच बदलने के लिए और न्यूनतम अतिच्छादन के लिए भी बनाया जा सकता है इसमें एक कार्यक्रम होता है जहाँ लंबाई है यहाँ तथा छोटी जटिलता है जब ज्ञात है तो ().जबकि हमारे पास दो वस्तुओं का आदान-प्रदान करने के लिए दूसरा कार्यक्रम है[6] इसमें शैन्य सूचना सिद्धांत और समीकरण की जटिलता की समानता को ध्यान में रखते हुए कोई कह सकता है कि यह परिणाम स्वीडन वुल्फ और कोर्नर इनरे सिज्जार मॉर्टन प्रमेय की समानता है।
अनुप्रयोग
सैद्धांतिक
ए एन ए का परिणाम है
जो ऊपर न्यूनतम अतिच्छादन पर मुचनिक ने एक महत्वपूर्ण सैद्धांत दिया है जो दिखा रहा है कि कुछ संकेत एकत्रित हैं जो किसी भी वस्तु से परिमित लक्ष्य पर जाने के लिए एक कार्यक्रम से जुड़ते हैं जो लक्ष्य वस्तु पर निर्भर करता है यह परिणाम काफी सही है और त्रुटि शब्द में महत्वपूर्ण सुधार नहीं किया जा सकता है सूचना दूरी पाठ्यपुस्तक की सामग्री थी यह दूरी पर विश्वकोश में होती है।
व्यवहारिकता
जीनोम,भाषा, संगीत, इंटरनेट और कृमि, सॉफ्टवेयर कार्यक्रम आदि जैसी वस्तुओं की समानता निर्धारित करने के लिए सूचना दूरी को सामान्यीकृत किया जाता है और समीकरण जटिलता की शर्तों को वास्तविक दुनिया द्वारा जोड़ा जाता है समीकरण जटिलता एक निम्न सीमा है जो वस्तु के एक संकुचित संस्करण के बिट्स लंबाई व परिणाम सामान्यीकृत संपीड़न की दूरी है यह कंप्यूटर फाइलों के रूप में दी गई वस्तुओं से संबंधित है जैसे कि माउस का जीनोम या किसी पुस्तक का पाठ यदि वस्तुओं को सिर्फ 'आइंस्टीन' या किसी पुस्तक के नाम तथा 'माउस' के नाम से दिया जाता है तो संपीड़न का कोई मतलब नहीं है इसके बारे में हमें बाहरी जानकारी चाहिए डेटा बेस जैसे इंटरनेट और डेटाबेस को खोजने के साधन जैसे गूगल खोज इंजन का उपयोग करके यह जानकारी प्रदान की जाती है डेटा बेस पर प्रत्येक खोज इंजन जो समग्र पृष्ठ गणना प्रदान करता है तथा सामान्यीकृत गूगल दूरी में उपयोग किया जा सकता है एन वेरिएबल्स के डेटा समूह में सभी सूचनाओं की दूरी और ध्वनि बहुभिन्नरूपी पारस्परिक जानकारी पारस्परिक जानकारी, संयुक्त एन्ट्रापी, कुल सहसंबंधों की गणना के लिए एक पायथन पैकेज उपलब्ध है।
संदर्भ
- ↑ 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.
संबंधित साहित्य
- Arkhangel'skii, A. V.; Pontryagin, L. S. (1990), General Topology I: Basic Concepts and Constructions Dimension Theory, Encyclopaedia of Mathematical Sciences, Springer, ISBN 3-540-18178-4
श्रेणी:सांख्यिकीय दूरी