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

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

परिभाषा

क्लाउड ई. शैनन की संचार का एक गणितीय सिद्धांत (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.