सूचना में अस्थिरता जटिलता

सूचना उतार-चढ़ाव जटिलता सूचना सिद्धांत है|सूचना-सैद्धांतिक मात्रा जिसे एन्ट्रॉपी (सूचना सिद्धांत) के बारे में जानकारी के उतार-चढ़ाव के रूप में परिभाषित किया गया है। यह गतिशील प्रणाली में व्यवस्था और अराजकता की प्रबलता में उतार-चढ़ाव से व्युत्पन्न है और इसका उपयोग कई विविध क्षेत्रों में जटिलता के माप के रूप में किया गया है। इसे बेट्स और शेपर्ड द्वारा 1993 के पेपर में पेश किया गया था।

परिभाषा

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

यदि कोई सिस्टम है ${\textstyle N}$ संभावित राज्य और राज्य संभावनाएँ ${\textstyle p_{i}}$ज्ञात हैं, तो इसकी एन्ट्रॉपी (सूचना सिद्धांत)#परिभाषा है

$\mathrm {H} =\sum _{i=1}^{N}p_{i}I_{i}=-\sum _{i=1}^{N}p_{i}\log p_{i},$

कहाँ ${\textstyle I_{i}=-\log p_{i}}$ राज्य की सूचना सामग्री है ${\textstyle i}$.

सिस्टम की सूचना उतार-चढ़ाव जटिलता को मानक विचलन#असतत यादृच्छिक चर या उतार-चढ़ाव के रूप में परिभाषित किया गया है ${\textstyle I}$ इसके माध्य के बारे में ${\textstyle \mathrm {H} }$:

$\sigma _{I}={\sqrt {\sum _{i=1}^{N}p_{i}(I_{i}-\mathrm {H} )^{2}}}={\sqrt {\sum _{i=1}^{N}p_{i}I_{i}^{2}-\mathrm {H} ^{2}}}$

या

$\sigma _{I}={\sqrt {\sum _{i=1}^{N}p_{i}\log ^{2}p_{i}-{\Biggl (}\sum _{i=1}^{N}p_{i}\log p_{i}{\Biggr )}^{2}}}.$

राज्य की जानकारी में उतार-चढ़ाव $\sigma _{I}$ सभी के साथ अधिकतम अव्यवस्थित प्रणाली में शून्य है $p_{i}=1/N$; सिस्टम बस अपने यादृच्छिक इनपुट की नकल करता है। $\sigma _{I}$ यह भी शून्य है जब सिस्टम केवल निश्चित स्थिति के साथ पूरी तरह से व्यवस्थित होता है $(p_{1}=1)$, इनपुट की परवाह किए बिना। $\sigma _{I}$ इन दो चरम सीमाओं के बीच गैर-शून्य है जिसमें उच्च-संभावना वाले राज्यों और निम्न-संभावना वाले राज्यों दोनों का मिश्रण राज्य स्थान को आबाद करता है।

सूचना का उतार-चढ़ाव स्मृति और गणना की अनुमति देता है

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

राज्यों के बीच संक्रमण से जुड़ी जानकारी का लाभ या हानि राज्य की जानकारी से संबंधित हो सकती है। राज्य से संक्रमण का शुद्ध सूचना लाभ $i$ कहना $j$ राज्य छोड़ते समय प्राप्त की गई जानकारी है $i$ राज्य में प्रवेश करते समय खोई गई जानकारी कम होगी $j$:

$\Gamma _{ij}=-\log p_{i\rightarrow j}+\log p_{i\leftarrow j}.$

यहाँ ${\textstyle p_{i\rightarrow j}}$ आगे की सशर्त संभावना है कि यदि वर्तमान स्थिति है $i$ फिर अगला राज्य है $j$ और $p_{i\leftarrow j}$ विपरीत सशर्त संभावना है कि यदि वर्तमान स्थिति है $j$ तब पूर्व स्थिति थी $i$. सशर्त संभावनाएँ संक्रमण संभावना से संबंधित हैं $p_{ij}$, संभावना है कि राज्य से संक्रमण $i$ कहना $j$ होता है, द्वारा:

$p_{ij}=p_{i}p_{i\rightarrow j}=p_{j}p_{i\leftarrow j}.$

सशर्त संभावनाओं को ख़त्म करना:

$\Gamma _{ij}=-\log(p_{ij}/p_{i})+\log(p_{ij}/p_{j})=\log p_{i}-\log p_{j}=I_{j}-I_{i}.$

इसलिए संक्रमण के परिणामस्वरूप सिस्टम द्वारा प्राप्त शुद्ध जानकारी केवल प्रारंभिक से अंतिम स्थिति तक राज्य की जानकारी में वृद्धि पर निर्भर करती है। यह दिखाया जा सकता है कि यह लगातार कई बदलावों के लिए भी सच है।

$\Gamma =\Delta I$ बल और संभावित ऊर्जा के बीच संबंध की याद दिलाता है#किसी क्षमता से व्युत्पन्न। $I$ क्षमता की तरह है $\Phi$ और $\Gamma$ बल की तरह है $\mathbf {F}$ स्थितिज ऊर्जा में#_संभावना_से_व्युत्पन्न|$\mathbf {F} ={\nabla \Phi }$. बाहरी जानकारी मेमोरी स्टोरेज को पूरा करने के लिए सिस्टम को उच्च सूचना क्षमता की स्थिति में "ऊपर की ओर" धकेलती है, ठीक उसी तरह जैसे किसी द्रव्यमान को उच्च गुरुत्वाकर्षण क्षमता की स्थिति में ऊपर की ओर धकेलना ऊर्जा को संग्रहीत करता है। ऊर्जा भंडारण की मात्रा केवल अंतिम ऊंचाई पर निर्भर करती है, पहाड़ी के रास्ते पर नहीं। इसी तरह, सूचना भंडारण की मात्रा राज्य स्थान में दो राज्यों के बीच संक्रमण पथ पर निर्भर नहीं करती है। बार जब कोई सिस्टम उच्च सूचना क्षमता वाली दुर्लभ स्थिति में पहुंच जाता है, तो यह पहले से संग्रहीत जानकारी खोकर अधिक सामान्य स्थिति में आ सकता है।

मानक विचलन#असतत यादृच्छिक चर की गणना करना उपयोगी हो सकता है $\Gamma$ इसके माध्य के बारे में (जो शून्य है), अर्थात् शुद्ध सूचना लाभ का उतार-चढ़ाव $\sigma _{\Gamma }$,लेकिन $\sigma _{I}$ राज्य स्थान में बहु-संक्रमण मेमोरी लूप को ध्यान में रखता है और इसलिए यह सिस्टम की कम्प्यूटेशनल शक्ति का बेहतर संकेतक होना चाहिए। इसके अतिरिक्त, $\sigma _{I}$ गणना करना आसान है क्योंकि राज्यों की तुलना में कई अधिक संक्रमण हो सकते हैं।

अराजकता और व्यवस्था

गतिशील प्रणाली जो बाहरी जानकारी के प्रति संवेदनशील है (अस्थिर) कैओस सिद्धांत व्यवहार प्रदर्शित करती है जबकि जो बाहरी जानकारी के प्रति असंवेदनशील है (स्थिर) व्यवस्थित व्यवहार प्रदर्शित करती है। जटिल प्रणाली दोनों व्यवहार प्रदर्शित करती है, समृद्ध सूचना स्रोत के अधीन होने पर गतिशील संतुलन में उनके बीच उतार-चढ़ाव होता है। उतार-चढ़ाव की डिग्री की मात्रा निर्धारित की जाती है $\sigma _{I}$; यह समय के साथ विकसित होने पर जटिल प्रणाली में अराजकता और व्यवस्था की प्रबलता में परिवर्तन को पकड़ता है।

उदाहरण: प्राथमिक सेलुलर ऑटोमेटन का नियम 110 संस्करण

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

आसन्न ऑटोमेटन कोशिकाओं के 3-सेल समूह पर विचार करें जो नियम 110 का पालन करते हैं:end-center-end. केंद्र कोशिका की अगली स्थिति स्वयं की वर्तमान स्थिति और नियम द्वारा निर्दिष्ट अंतिम कोशिकाओं पर निर्भर करती है:

Elementary cellular automaton rule 110

3-cell group	1-1-1	1-1-0	1-0-1	1-0-0	0-1-1	0-1-0	0-0-1	0-0-0
next center cell	0	1	1	0	1	1	1	0

इस प्रणाली की सूचना उतार-चढ़ाव जटिलता की गणना करने के लिए, 3-सेल समूह के प्रत्येक छोर पर ड्राइवर सेल संलग्न करें ताकि यादृच्छिक बाहरी उत्तेजना प्रदान की जा सके, 'driver→end-center-end←driver, ताकि नियम को दो अंतिम कोशिकाओं पर लागू किया जा सके। आगे की सशर्त संभावनाओं को निर्धारित करने के लिए, आगे निर्धारित करें कि प्रत्येक संभावित वर्तमान स्थिति के लिए और ड्राइवर सेल सामग्री के प्रत्येक संभावित संयोजन के लिए अगली स्थिति क्या है।

इस प्रणाली का राज्य आरेख नीचे दर्शाया गया है, जिसमें वृत्त राज्यों का प्रतिनिधित्व करते हैं और तीर राज्यों के बीच संक्रमण का प्रतिनिधित्व करते हैं। इस प्रणाली की आठ अवस्थाएँ, 1-1-1 को 0-0-0 को 3-सेल समूह की 3-बिट सामग्री के ऑक्टल समकक्ष के साथ लेबल किया गया है: 7 से 0. संक्रमण तीरों को आगे की सशर्त संभावनाओं के साथ लेबल किया गया है। ध्यान दें कि अराजकता और व्यवस्था, संवेदनशीलता और असंवेदनशीलता, चालक कोशिकाओं से बाहरी जानकारी के लाभ और हानि में परिवर्तनशीलता के अनुरूप तीरों के विचलन और अभिसरण में परिवर्तनशीलता है।

नियम 110 प्राथमिक सेलुलर ऑटोमेटन के लिए 3-सेल राज्य आरेख यादृच्छिक उत्तेजना के साथ आगे की सशर्त संक्रमण संभावनाओं को दर्शाता है।

आगे की सशर्त संभावनाएं संभावित ड्राइवर सेल सामग्री के अनुपात से निर्धारित होती हैं जो विशेष संक्रमण को चलाती हैं। उदाहरण के लिए, दो ड्राइवर सेल सामग्री के चार संभावित संयोजनों के लिए, स्थिति 7 स्थिति 5, 4, 1 और 0 की ओर ले जाती है इसलिए $p_{7\rightarrow 5}$, $p_{7\rightarrow 4}$, $p_{7\rightarrow 1}$, और $p_{7\rightarrow 0}$ प्रत्येक ¼ या 25% हैं। इसी प्रकार, अवस्था 0 अवस्था 0, 1, 0 और 1 की ओर ले जाती है $p_{0\rightarrow 1}$और $p_{0\rightarrow 0}$प्रत्येक ½ या 50% हैं। इत्यादि।

राज्य की संभावनाएँ इससे संबंधित हैं

$p_{j}=\sum _{i=0}^{7}p_{i}p_{i\rightarrow j}$ और $\sum _{i=0}^{7}p_{i}=1.$

इन रैखिक बीजगणितीय समीकरणों को राज्य संभावनाओं के लिए मैन्युअल रूप से या कंप्यूटर प्रोग्राम की सहायता से निम्नलिखित परिणामों के साथ हल किया जा सकता है:

Rule 110 state probabilities for 3-cell automaton with random stimulation

p0	p1	p2	p3	p4	p5	p6	p7
2/17	2/17	1/34	5/34	2/17	2/17	2/17	4/17

सूचना एन्ट्रापी और जटिलता की गणना राज्य संभावनाओं से की जा सकती है:

$\mathrm {H} =-\sum _{i=0}^{7}p_{i}\log _{2}p_{i}=2.86{\text{ bits}},$

$\sigma _{I}={\sqrt {\sum _{i=0}^{7}p_{i}\log _{2}^{2}p_{i}-\mathrm {H} ^{2}}}=0.56{\text{ bits}}.$

ध्यान दें कि आठ राज्यों के लिए अधिकतम संभव एन्ट्रापी है $\log _{2}8=3{\text{ bits}},$ जो कि स्थिति होगी यदि सभी आठ राज्य ⅛ (यादृच्छिकता) की संभावनाओं के साथ समान रूप से संभावित हों। इस प्रकार नियम 110 में 2.86 बिट्स पर अपेक्षाकृत उच्च एन्ट्रापी या राज्य उपयोग है। लेकिन यह एन्ट्रापी के बारे में राज्य की जानकारी में पर्याप्त उतार-चढ़ाव और इस प्रकार जटिलता के पर्याप्त मूल्य को नहीं रोकता है। जबकि, अधिकतम एन्ट्रापी जटिलता को दूर कर देगी।

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

Information variables for the rule 110 elementary cellular automaton

number of cells	3	4	5	6	7	8	9	10	11	12	13
$\mathrm {H}$ (bits)	2.86	3.81	4.73	5.66	6.56	7.47	8.34	9.25	10.09	10.97	11.78
$\sigma _{I}$(bits)	0.56	0.65	0.72	0.73	0.79	0.81	0.89	0.90	1.00	1.01	1.15
$\sigma _{I}/\mathrm {H}$	0.20	0.17	0.15	0.13	0.12	0.11	0.11	0.10	0.10	0.09	0.10

चूंकि दोनों $\mathrm {H}$ और $\sigma _{I}$ सिस्टम आकार के साथ उनके आयाम रहित अनुपात में वृद्धि होती है $\sigma _{I}/\mathrm {H}$, सापेक्ष सूचना उतार-चढ़ाव जटिलता, विभिन्न आकारों की प्रणालियों की बेहतर तुलना करने के लिए शामिल है। ध्यान दें कि अनुभवजन्य और विश्लेषणात्मक परिणाम 3-सेल ऑटोमेटन के लिए सहमत हैं।

बेट्स और शेपर्ड के पेपर में, $\sigma _{I}$ सभी प्राथमिक सेलुलर ऑटोमेटन नियमों के लिए गणना की गई है और यह देखा गया है कि जो धीमी गति से चलने वाले ग्लाइडर और संभवतः स्थिर वस्तुओं को प्रदर्शित करते हैं, जैसा कि नियम 110 करता है, बड़े मूल्यों के साथ अत्यधिक सहसंबद्ध हैं $\sigma _{I}$. $\sigma _{I}$ इसलिए इसे सार्वभौमिक गणना के लिए उम्मीदवार नियमों का चयन करने के लिए फिल्टर के रूप में उपयोग किया जा सकता है, जिसे साबित करना कठिन है।

अनुप्रयोग

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

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