न्यूनतम संदेश लंबाई

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

परिभाषा

क्लाउड ई. शैनन की संचार का गणितीय सिद्धांत (1948) में कहा गया है कि इष्टतम कोड में, किसी घटना की संदेश लंबाई (बाइनरी में) $E$, $\operatorname {length} (E)$, जहाँ $E$ संभावना है, इस प्रकार $P(E)$ द्वारा $\operatorname {length} (E)=-\log _{2}(P(E))$ दिया गया है .

बेयस प्रमेय बताता है कि (परिवर्तनीय) परिकल्पना की संभावना $H$ निश्चित प्रमाण दिये $E$ के लिए आनुपातिक $P(E|H)P(H)$ है , जो, सशर्त संभाव्यता की परिभाषा के अनुसार, $P(H\land E)$ के समान है . हम ऐसी उच्चतम पश्च संभाव्यता वाला मॉडल (परिकल्पना) चाहते हैं। मान लीजिए कि हम संदेश को एनकोड करते हैं जो मॉडल और डेटा दोनों को संयुक्त रूप से दर्शाता (वर्णन) करता है। तब से $\operatorname {length} (H\land E)=-\log _{2}(P(H\land E))$, सबसे संभावित मॉडल में ऐसा संदेश सबसे छोटा होता है। संदेश दो भागों में विभाजित है: $-\log _{2}(P(H\land E))=-\log _{2}(P(H))+-\log _{2}(P(E|H))$. पहला भाग मॉडल को ही एन्कोड करता है। दूसरे भाग में जानकारी होती है (उदाहरण के लिए, मापदंड के मान, या प्रारंभिक स्थितियां इत्यादि) जो मॉडल द्वारा संसाधित होने पर, देखे गए डेटा को आउटपुट करती है।

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

निरंतर-मूल्यवान मापदंड

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

एमएमएल की मुख्य विशेषताएं

• एमएमएल का उपयोग विभिन्न संरचना के मॉडल की तुलना करने के लिए किया जा सकता है। उदाहरण के लिए, इसका प्रारंभिक अनुप्रयोग कक्षाओं की इष्टतम संख्या के साथ मिश्रण मॉडल खोजने में था। मिश्रण मॉडल में अतिरिक्त कक्षाएं जोड़ने से डेटा को सदैव अधिक स्पष्टता के साथ फिट किया जा सकता है, किन्तु एमएमएल के अनुसार इसे उन कक्षाओं को परिभाषित करने वाले मापदंडों को एन्कोड करने के लिए आवश्यक अतिरिक्त बिट्स के विरुद्ध मापा जाना चाहिए।
• एमएमएल बायेसियन मॉडल तुलना की विधि है। यह प्रत्येक मॉडल को अंक देता है।
• एमएमएल स्केल-अपरिवर्तनीय और सांख्यिकीय रूप से अपरिवर्तनीय है। कई बायेसियन चयन विधियों के विपरीत, एमएमएल को इसकी परवाह नहीं है कि आप लंबाई मापने से आयतन में या कार्टेशियन निर्देशांक से ध्रुवीय निर्देशांक में बदलते हैं।
• एमएमएल सांख्यिकीय रूप से सुसंगत है। जैसी समस्याओं के लिए CITEREFDoweWallace1997 नेमैन-स्कॉट (1948) समस्या या कारक विश्लेषण जहां प्रति मापदंड डेटा की मात्रा ऊपर सीमित है, एमएमएल सांख्यिकीय स्थिरता के साथ सभी मापदंडों का अनुमान लगा सकता है।
• एमएमएल माप की स्पष्टता के लिए उत्तरदायी है। यह फिशर जानकारी का उपयोग करता है (वालेस-फ्रीमैन 1987 सन्निकटन में, या अन्य हाइपर-वॉल्यूम में) CITEREFWallace_(posthumous)2005 निरंतर मापदंडों को इष्टतम रूप से अलग करने के लिए इसलिए संभाव्यता घनत्व नहीं पश्च भाग सदैव संभाव्यता है, ।
• एमएमएल 1968 से उपयोग में है। एमएमएल कोडिंग योजनाएं कई वितरणों और कई प्रकार के मशीन सीखने वालों के लिए विकसित की गई हैं, जिनमें अप्रशिक्षित वर्गीकरण, निर्णय वृक्ष और ग्राफ, डीएनए अनुक्रम, बायेसियन नेटवर्क, तंत्रिका नेटवर्क (अब तक केवल परत) सम्मिलित हैं। , इमेज संपीड़न, इमेज और फलन विभाजन, आदि।

यह भी देखें

• एल्गोरिथम संभाव्यता
• एल्गोरिथम सूचना सिद्धांत
• व्याकरण प्रेरण
• प्रेरक अनुमान
• प्रेरक संभाव्यता
• कोलमोगोरोव जटिलता - पूर्ण जटिलता (एक स्थिरांक के अन्दर, यूनिवर्सल ट्यूरिंग मशीन की विशेष पसंद पर निर्भर करता है); एमएमएल सामान्यतः गणना योग्य सन्निकटन है (देखें)।
• न्यूनतम विवरण लंबाई - संभवतः भिन्न (गैर-बायेसियन) प्रेरणा के साथ विकल्प, एमएमएल के 10 साल बाद विकसित हुआ था।
• ओकाम का रेजर

बाहरी संबंध

Original Publication:

• Wallace; Boulton (August 1968). "An information measure for classification". Computer Journal. 11 (2): 185–194. doi:10.1093/comjnl/11.2.185.

Books:

• Wallace, C.S. (May 2005). Statistical and Inductive Inference by Minimum Message Length. Information Science and Statistics. Springer-Verlag. doi:10.1007/0-387-27656-4. ISBN 978-0-387-23795-4.
• Allison, L. (2018). Coding Ockham's Razor. Springer. doi:10.1007/978-3-319-76433-7. ISBN 978-3319764320. S2CID 19136282., on implementing MML, and source-code.

Related Links:

• Links to all Chris Wallace's known publications.
• A searchable database of Chris Wallace's publications.
• Wallace, C.S.; Dowe, D.L. (1999). "Minimum Message Length and Kolmogorov Complexity". Computer Journal. 42 (4): 270–283. CiteSeerX 10.1.1.17.321. doi:10.1093/comjnl/42.4.270.
• "Special Issue on Kolmogorov Complexity". Computer Journal. 42 (4). 1999.
• Dowe, D.L.; Wallace, C.S. (1997). Resolving the Neyman-Scott Problem by Minimum Message Length. 28th Symposium on the interface, Sydney, Australia. Computing Science and Statistics. Vol. 28. pp. 614–618.
• History of MML, CSW's last talk.
• Needham, S.; Dowe, D. (2001). Message Length as an Effective Ockham's Razor in Decision Tree Induction (PDF). Proc. 8th International Workshop on AI and Statistics. pp. 253–260. (Shows how Occam's razor works fine when interpreted as MML.)
• Allison, L. (Jan 2005). "Models for machine learning and data mining in functional programming". Journal of Functional Programming. 15 (1): 15–32. doi:10.1017/S0956796804005301. S2CID 5218889. (MML, FP, and Haskell code).
• Comley, J.W.; Dowe, D.L. (April 2005). "Chapter 11: Minimum Message Length, MDL and Generalised Bayesian Networks with Asymmetric Languages". In Grunwald, P.; Pitt, M. A.; Myung, I. J. (eds.). Advances in Minimum Description Length: Theory and Applications. M.I.T. Press. pp. 265–294. ISBN 978-0-262-07262-5.
• Comley, Joshua W.; Dowe, D.L. (5–8 June 2003). General Bayesian Networks and Asymmetric Languages. Proc. 2nd Hawaii International Conference on Statistics and Related Fields., .pdf. Comley & Dowe (2003, 2005) are the first two papers on MML Bayesian nets using both discrete and continuous valued parameters.

• Dowe, David L. (2010). "MML, hybrid Bayesian network graphical models, statistical consistency, invariance and uniqueness" (PDF). Handbook of Philosophy of Science (Volume 7: Handbook of Philosophy of Statistics). Elsevier. pp. 901–982. ISBN 978-0-444-51862-0.
• Minimum Message Length (MML), LA's MML introduction, (MML alt.).
• Minimum Message Length (MML), researchers and links.
• "Another MML research website". Archived from the original on 12 April 2017.
• Snob page for MML mixture modelling.
• MITECS: Chris Wallace wrote an entry on MML for MITECS. (Requires account)
• mikko.ps: Short introductory slides by Mikko Koivisto in Helsinki
• Akaike information criterion (AIC) method of model selection, and a comparison with MML: Dowe, D.L.; Gardner, S.; Oppy, G. (Dec 2007). "Bayes not Bust! Why Simplicity is no Problem for Bayesians". Br. J. Philos. Sci. 58 (4): 709–754. doi:10.1093/bjps/axm033.