एन्ट्रॉपी और विनर

एंट्रोपी की अवधारणा का उपयोग विज्ञान और प्रौद्योगिकी के लगभग सभी क्षेत्रों में किया जाता है,
बायलर रूम डिजाइन करने से लेकर मानव चेतना के मॉडल तक।
थर्मोडायनामिक्स और डायनेमिक सिस्टम और कैलकुलेशन मेथड दोनों के लिए मूल परिभाषा समझना मुश्किल नहीं है। लेकिन जंगल में दूर - और अधिक लकड़ी। उदाहरण के लिए, मुझे हाल ही में पता चला (आर। पेनरोज़, "द वे टू रियलिटी, पीपी। 592-593) के लिए धन्यवाद, जो न केवल सौर ऊर्जा, बल्कि पृथ्वी पर जीवन के लिए इसकी कम एन्ट्रापी महत्वपूर्ण है ।

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

परिचय

सूचनात्मक एन्ट्रापी का उल्लेख करते हुए, वे अक्सर शैनन का "जादू" सूत्र देते हैं:

जहां एन संभव कार्यान्वयन की संख्या है, बी माप की इकाइयां हैं (2 - बिट्स, 3 - ट्रिट्स, ..), पी _i - कार्यान्वयन की संभावनाएं।
बेशक, सब कुछ इतना सरल नहीं है (लेकिन दिलचस्प है!)। पहली (दूसरे और साथ ही तीसरे) परिचित के लिए, मैं ए। याग्लोम, आई। याग्लोम "प्रायिकता और सूचना", 1973 की पुरानी पुस्तक को नहीं सुझाता।
"बच्चों के" प्रश्न के उत्तर के रूप में: " सूत्र द्वारा प्राप्त संख्या का क्या अर्थ है?"
ऐसा विशद चित्रण करेगा।

चलो एन = 16 कोशिकाएं हैं, जिनमें से एक क्रॉस के साथ चिह्नित है:

[] [] [] [] [] [] [] [] [] [] [] [] [x] [] [] []]

चुनाव यादृच्छिक है; i-th सेल लेबल होने की संभावना p _i = 1/16 है
शैनन की एन्ट्रापी के बराबर है

अब एक खेल की कल्पना करो; एक खिलाड़ी कोशिकाओं को खींचता है, डैश करता है और केवल दूसरे को बताता है
कोशिकाओं की संख्या। दूसरा यह पता लगाना है कि कौन सा टैग किया गया है और सवाल पूछता है;
लेकिन पहले केवल "हां" या "नहीं" का जवाब देंगे ।
कितने (न्यूनतम!) प्रश्न यह जानने के लिए पूछे जाने चाहिए कि क्रॉस कहाँ है?
जवाब " 4 " है। ऐसे सभी खेलों में, प्रश्नों की न्यूनतम संख्या सूचनात्मक प्रवेश के बराबर होगी।
इससे कोई फर्क नहीं पड़ता कि क्या पूछना है सही रणनीति का एक उदाहरण है
कोशिकाओं को आधे में विभाजित करें (यदि एन विषम है, तो 1 सेल की अधिकता / कमी के साथ) और पूछें:
"पहली छमाही में क्रॉस?" सीखा है कि इस तरह के और ऐसे में, हम इसे आधे में विभाजित करते हैं, आदि।

एक और तरह का "भोला" लेकिन गहरा सवाल: शैनन फॉर्मूला में एक लघुगणक क्यों है?
और वास्तव में, एक लघुगणक कार्य क्या है? रिवर्स एक्सपोनेंशियल ... और एक्सपोनेंशियल क्या है?
वास्तव में, परिपक्वता के दौरान कठोर परिभाषाएँ दी जाती हैं, लेकिन वे बिल्कुल भी जटिल नहीं हैं।
ऐसा अक्सर होता है कि कई बार "इनपुट" बढ़ने से हमें "आउटपुट" कुछ ही यूनिट अधिक मिलता है।
ऑगस्टिन कॉची ने साबित किया कि समीकरण

f (xy) = f (x) + f (y) x, y> 0

केवल एक निरंतर समाधान है ; यह लघुगणक समारोह है।
अब कल्पना कीजिए कि हम दो स्वतंत्र परीक्षण कर रहे हैं; उनके पास मौजूद परिणामों की संख्या n और m है, वे सभी समान रूप से संभावित हैं (उदाहरण के लिए, एक ही समय में एक पासा और एक सिक्का फेंकें; n = 6, m = 2)
जाहिर है, दोहरे अनुभव के परिणामों की संख्या उत्पाद n · m के बराबर है।
प्रयोगों की अनिश्चितताओं को जोड़ते हैं; और अनिश्चितता, इस अनिश्चितता के उपाय के रूप में, चाहिए
स्थिति को संतुष्ट करें h (mn) = h (m) + h (n), अर्थात लघुगणक होना।

कोलमोगोरोव-सिनाई की एंट्री

इस मौलिक अवधारणा की एक सख्त परिभाषा को समझना काफी मुश्किल है।
हम धीरे-धीरे उसके पास जाते हैं;
हमारा "चरण स्थान" प्राकृतिक संख्याओं का एक-आयामी एरे होगा।
उदाहरण के लिए, संख्या "Pi" के दशमलव अंक: {3, 1, 4, 1, 5, 9, 2, 6, ...}}
वास्तव में, किसी भी प्रकार का डेटा (नुकसान के साथ, निश्चित रूप से) इस फॉर्म में लाया जा सकता है।
यह मानों की पूरी श्रृंखला को एन अंतराल में विभाजित करने के लिए पर्याप्त है और, जब के-वें अंतराल में गिरते हैं, तो संख्या k लिखिए (जैसे ध्वनि नमूनाकरण के साथ)।
यह या यह अनुक्रम कितना यादृच्छिक या स्टोकेस्टिक है?
सूचना एन्ट्रापी, निश्चित रूप से, "अराजकता मीटर" के लिए एक अच्छा उम्मीदवार है।
यह साबित करना आसान है कि यह अधिकतम है जब विभिन्न संख्याओं की उपस्थिति की सभी संभावनाएं समान हैं।

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



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

संग्रह और Entropy

हैबे पर सूचना संपीड़न के तरीकों और एल्गोरिदम के बारे में एक से अधिक बार बताया गया था,
habrahabr.ru/post/142242
habrahabr.ru/post/132683
मूल स्रोतों का उल्लेख नहीं है।
एक समय में, पूर्ण पुनर्प्राप्ति के साथ 50% तक संपीड़ित करने की क्षमता ने मुझ पर एक चौंकाने वाला प्रभाव डाला।
मुझे हाल ही में कोई आश्चर्य नहीं हुआ जब मुझे पता चला कि डेटा संपीड़न और उनकी कोलमोगोरोव-सिनाई एन्ट्रॉपी की डिग्री के बीच संबंध सख्ती से साबित हुआ था । सहज रूप से, यह समझ में आता है - जितना अधिक डेटा का आदेश दिया, संपीड़न एन्कोडिंग के लिए अधिक अवसर।
हालांकि, कठोर गणितीय विचार हमेशा "सामान्य ज्ञान" की पुष्टि नहीं करता है;
और यद्यपि इस विषय पर लेख बल्कि जटिल हैं (और मुख्य भुगतान भी किया जाता है), हम सिद्धांतवादियों का मानना ​​है कि सब कुछ कानूनी है और प्रयोगों के लिए आगे बढ़ें।

4 प्रकार के डेटा बनाएँ:

• pi के दशमलव अंक (i)
• PRNG वोल्फ्राम मैथमेटिका (रैंडम)
• अराजकता का निर्धारण करने वाला सबसे चमकीला और सरल उदाहरण लॉजिस्टिक मैपिंग है
• एक "1" (कांस्ट) की एक सरणी
• पहली नज़र (मानचित्र) में यादृच्छिक संख्या उत्पन्न करने वाले कुछ प्रकार के चमकदार सूत्र

बेशक, हम शैनन फार्मूला (एंट्रोपी [के रूप में गणितज्ञ में निर्मित) का उपयोग करके एन्ट्रापी की गणना कर सकते हैं।
हालांकि, जैसा कि ऊपर उल्लेख किया गया है, परिणाम बहुत संख्या प्रणाली, डेटा प्रस्तुति के रूप, आदि पर निर्भर करेगा।
उदाहरण के लिए, डेटा की बढ़ती मात्रा के लिए लॉजिस्टिक एंट्रियों का एक ग्राफ है:



यह बहुत स्पष्ट नहीं है कि एन्ट्रॉपी सरणी के आकार में वृद्धि के साथ एक निश्चित मूल्य पर जाता है या नहीं।
अब चलो संपीड़न का उपयोग करके एन्ट्रॉपी को मापने का प्रयास करें। प्रत्येक उदाहरण के लिए, हम विभिन्न आकारों के सरणियों का निर्माण करेंगे और "आकार संपीड़न के बाद आकार / संपीड़न के लिए आकार" का निर्माण करेंगे। सरणी की लंबाई के आधार पर संबंध ग्राफ (ईमानदार होने के लिए, मैं WinRAR हेडर के बजाय अंतर्निहित मैथेमेटिका ज़िप अभिलेखागार का उपयोग करता था)



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

एक विचार के विकास का एक उदाहरण।

“उबाऊ” संख्याओं के बजाय हम सार्थक साहित्यिक ग्रंथों को लेते हैं। उनकी स्टोचैस्टिसिटी और कम्प्रेशन विधियों की डिग्री एक बहुत व्यापक विषय है ( उदाहरण के लिए देखें)
यहां हम सिर्फ यह सुनिश्चित करते हैं कि अभिलेखों का उपयोग करने वाले माप भी समझ में आए।
उदाहरण के रूप में, रूसी परियों की कहानियों के लगभग समान अंश, जेद्दा कृष्णमूर्ति की आध्यात्मिक बातचीत और एल के भाषण। ब्रेजनेव।



यह दिलचस्प निकला - छोटे मार्ग के लिए, ग्रंथों के संपीड़न (यानी, ऑर्डरिंग) की डिग्री स्पष्ट रूप से भिन्न होती है, साथ ही ब्रेझनेव अग्रणी होता है!