Mindste beskedlængde - Minimum message length

Minimum beskedlængde (MML) er en bayesisk informationsteoretisk metode til sammenligning og valg af statistisk model. Det giver en formel informationsteori tilpasning af Occam's Razor : selv når modellerne er ens i deres mål for pasningsnøjagtighed til de observerede data, er den, der genererer den mest præcise forklaring af data, mere sandsynligt at være korrekt (hvor forklaringen består af erklæring om modellen efterfulgt af tabsfri kodning af data ved hjælp af den angivne model). MML blev opfundet af Chris Wallace , der først blev vist i den sædvanlige artikel "Et informationsmål for klassificering". MML er ikke kun beregnet som en teoretisk konstruktion, men som en teknik, der kan implementeres i praksis. Det adskiller sig fra det relaterede koncept af Kolmogorov-kompleksitet , da det ikke kræver brug af et Turing-komplet sprog for at modellere data.

Definition

Shannon 's A Matematisk meddelelse (1948), at i en optimal kode, længde meddelelsen (i binær) af en begivenhed , hvor har sandsynlighed , er givet ved . ${\ displaystyle E}$${\ displaystyle \ operatorname {længde} (E)}$${\ displaystyle E}$${\ displaystyle P (E)}$${\ displaystyle \ operatorname {længde} (E) = - \ log _ {2} (P (E))}$

Bayes sætning siger, at sandsynligheden for en (variabel) hypotese givet fast bevis er proportional med , som ved definitionen af betinget sandsynlighed er lig med . Vi ønsker modellen (hypotese) med den højeste sådanne bageste sandsynlighed . Antag, at vi koder en meddelelse, der repræsenterer (beskriver) både model og data i fællesskab. Siden vil den mest sandsynlige model have den korteste sådan besked. Meddelelsen bryder i to dele: . Den første del koder selve modellen. Den anden del indeholder information (f.eks. Parameterværdier eller startbetingelser osv.), Der, når de behandles af modellen, udsender de observerede data. ${\ displaystyle H}$${\ displaystyle E}$${\ displaystyle P (E | H) P (H)}$${\ displaystyle P (H \ land E)}$${\ displaystyle \ operatorname {længde} (H \ land E) = - \ log _ {2} (P (H \ land E))}$${\ displaystyle - \ log _ {2} (P (H \ land E)) = - \ log _ {2} (P (H)) + - \ log _ {2} (P (E | H))}$

MML handler naturligt og præcist med modelkompleksitet for god pasform. En mere kompliceret model tager længere tid at angive (længere første del), men passer sandsynligvis dataene bedre (kortere anden del). Så en MML-metrisk vælger ikke en kompliceret model, medmindre den model betaler for sig selv.

Kontinuerligt værdiansatte parametre

En af grundene til, at en model kan være længere, ville simpelthen være, fordi dens forskellige parametre er angivet med større præcision, hvilket kræver transmission af flere cifre. Meget af kraften i MML stammer fra dens håndtering af, hvor nøjagtigt at angive parametre i en model, og en række tilnærmelser, der gør dette muligt i praksis. Dette gør det muligt at sammenligne f.eks. En model med mange parametre, der er præcist angivet med en model med færre parametre, der er mere præcist angivet.

Nøglefunktioner i MML

• MML kan bruges til at sammenligne modeller med forskellig struktur. For eksempel var dets tidligste anvendelse at finde blandingsmodeller med det optimale antal klasser. Tilføjelse af ekstra klasser til en blandingsmodel gør det altid muligt at tilpasse dataene til større nøjagtighed, men ifølge MML skal dette afvejes mod de ekstra bits, der kræves for at kode de parametre, der definerer disse klasser.
• MML er en metode til sammenligning af Bayesian-modeller . Det giver hver model en score.
• MML er skala-invariant og statistisk invariant. I modsætning til mange bayesiske selektionsmetoder er MML ligeglad med, om du skifter fra måling af længde til volumen eller fra kartesiske koordinater til polære koordinater.
• MML er statistisk konsistent. For problemer som Neyman-Scott (1948) -problemet eller faktoranalyse, hvor mængden af ​​data pr. Parameter er afgrænset ovenfor, kan MML estimere alle parametre med statistisk konsistens .
• MML tegner sig for målingens nøjagtighed. Den bruger Fisher-informationen (i Wallace-Freeman 1987-tilnærmelsen eller andre hypervolumener i andre tilnærmelser ) til optimalt at diskretisere kontinuerlige parametre. Derfor er den bageste altid en sandsynlighed, ikke en sandsynlighedstæthed.
• MML har været i brug siden 1968. MML-kodningsordninger er udviklet til flere distributioner, og mange slags maskinelever inklusive klassifikation uden opsyn, beslutningstræer og grafer, DNA-sekvenser, Bayesiske netværk , neurale netværk (kun et lag indtil videre), billedkomprimering, billed- og funktionssegmentering osv.

Se også

• Algoritmisk sandsynlighed
• Algoritmisk informationsteori
• Grammatikinduktion
• Induktiv slutning
• Induktiv sandsynlighed
• Kolmogorov-kompleksitet - absolut kompleksitet (inden for en konstant, afhængigt af det særlige valg af Universal Turing Machine ); MML er typisk en beregningsbar tilnærmelse (se)
• Minimum beskrivelse længde - et alternativ med en muligvis anden (ikke-Bayesisk) motivation, udviklet 10 år efter MML.
• Occams barbermaskine

Referencer

eksterne links

Oprindelig publikation:

• Wallace; Boulton (august 1968). "Et informationsmål for klassificering" . Computerjournal . 11 (2): 185–194. doi : 10.1093 / comjnl / 11.2.185 .

Bøger:

• Wallace, CS (maj 2005). Statistisk og induktiv inferens efter minimum beskedlængde . Informationsvidenskab og statistik. Springer-Verlag. ISBN   978-0-387-23795-4 . CS1 maint: modløs parameter ( link )
• Allison, L. (2018). Kodning af Ockham's Razor . Springer. doi : 10.1007 / 978-3-319-76433-7 . ISBN   978-3319764320 . S2CID   19136282 . om implementering af MML og kildekode .

Relaterede links:

• Links til alle Chris Wallaces kendte publikationer.
• En søgbar database med Chris Wallaces publikationer .
• Wallace, CS; Dowe, DL (1999). "Minimum beskedlængde og Kolmogorov-kompleksitet". Computerjournal . 42 (4): 270-283. CiteSeerX   10.1.1.17.321 . doi : 10.1093 / comjnl / 42.4.270 .
• "Særudgave om Kolmogorov-kompleksitet" . Computerjournal . 42 (4). 1999.
• Dowe, DL; Wallace, CS (1997). Løsning af Neyman-Scott-problemet ved minimum beskedlængde . 28. symposium om grænsefladen, Sydney, Australien. Computing videnskab og statistik . 28 . s. 614–618.
• Historie om MML, CSWs sidste tale .
• Needham, S .; Dowe, D. (2001). Beskedlængde som en effektiv Ockhams barbermaskine i beslutningstræinduktion (PDF) . Proc. 8. internationale workshop om AI og statistik . s. 253-260. (Viser hvordan Occams barbermaskine fungerer fint, når den fortolkes som MML.)
• Allison, L. (jan 2005). "Modeller til maskinindlæring og datamining i funktionel programmering". Tidsskrift for funktionel programmering . 15 (1): 15–32. doi : 10.1017 / S0956796804005301 . S2CID   5218889 . (MML-, FP- og Haskell- kode ).
• Comley, JW; Dowe, DL (april 2005). "Kapitel 11: Minimum beskedlængde, MDL og generaliserede bayesiske netværk med asymmetriske sprog" . I Grunwald, P .; Pitt, MA; Myung, IJ (red.). Fremskridt i minimum beskrivelse Længde: Teori og applikationer . MIT Tryk. s. 265-294. ISBN   978-0-262-07262-5 .
• Comley, Joshua W. Dowe, DL (5. - 8. juni 2003). Generelle bayesiske netværk og asymmetriske sprog . Proc. 2. Hawaii internationale konference om statistik og relaterede felter. , .pdf . Comley & Dowe ( 2003 , 2005 ) er de to første papirer om MML Bayesian-net, der bruger både diskrete og kontinuerlige værdiparametre.

• Dowe, David L. (2010). "MML, hybrid Bayesian-netværk grafiske modeller, statistisk konsistens, uforanderlighed og unikhed" (PDF) . Handbook of Philosophy of Science (bind 7: Handbook of Philosophy of Statistics) . Elsevier. s. 901–982. ISBN   978-0-444-51862-0 .
• Minimum beskedlængde (MML) , LA's MML introduktion, (MML alt.) .
• Minimum beskedlængde (MML), forskere og links .
• "Et andet MML-forskningswebsted" . Arkiveret fra originalen den 12. april 2017.
• Snobside til MML- blandingsmodellering .
• MITECS : Chris Wallace skrev en post på MML for MITECS. (Kræver konto)
• mikko.ps : Korte indledende dias af Mikko Koivisto i Helsinki
• Akaike informationskriterium ( AIC ) metode til modelvalg og en sammenligning med MML: Dowe, DL; Gardner, S .; Oppy, G. (dec. 2007). "Bayes ikke buste! Hvorfor enkelhed er ikke noget problem for Bayesians". Br. J. Philos. Sci . 58 (4): 709-754. doi : 10.1093 / bjps / axm033 .