Minsta meddelandelängd

Minsta meddelandelängd (MML) är en Bayesiansk informationsteoretisk metod för statistisk modelljämförelse och urval. Den tillhandahåller en formell informationsteori som återupptar Occams Razor : även när modellerna är lika i sitt mått på passningsnoggrannhet med de observerade data, är det mer sannolikt att den som genererar den mest kortfattade förklaringen av data är korrekt (där förklaringen består av beskrivning av modellen, följt av förlustfri kodning av data med användning av den angivna modellen). MML uppfanns av Chris Wallace , som först dök upp i tidningen "An information measure for classification". MML är inte bara tänkt som en teoretisk konstruktion, utan som en teknik som kan användas i praktiken. Det skiljer sig från det relaterade konceptet Kolmogorovs komplexitet genom att det inte kräver användning av ett Turing-komplett språk för att modellera data.

Definition

Shannons A Mathematical Theory of Communication (1948) säger att i en optimal kod, meddelandelängden (i binär) för en händelse ${\displaystyle E} ,$ längd $\displaystyle \operatorname {length} (E )}$ , där $E$ har sannolikheten $P(E)$ , ges av $\operatorname { length} (E)=-\log _{2}(P(E))$ .

Bayes teorem säger att sannolikheten för en (variabel) hypotes $H$ givet fast bevis $E$ är proportionell mot $P(E|H)P (H)$ , som enligt definitionen av betingad sannolikhet är lika med $P(H\land E)$ . Vi vill ha modellen (hypotesen) med högst sådan posterior sannolikhet . Anta att vi kodar ett meddelande som representerar (beskriver) både modell och data gemensamt. Eftersom $\operatorname {length} (H\land E)=-\log _{2}(P(H\land E) ))$ kommer den mest sannolika modellen att ha det kortaste meddelandet. Meddelandet delas upp i två delar: $-\log _ {2}(P(H\land E))=-\log _{2}(P(H))+-\log _{2}(P(E|H))$ . Den första delen kodar själva modellen. Den andra delen innehåller information (t.ex. värden på parametrar, eller initiala villkor, etc.) som, när den bearbetas av modellen, matar ut observerade data.

MML byter naturligt och precist ut modellkomplexitet mot god passform. En mer komplicerad modell tar längre tid att ange (längre första del) men passar förmodligen data bättre (kortare andra del). Så ett MML-mått väljer inte en komplicerad modell om inte den modellen betalar för sig själv.

Kontinuerligt värderade parametrar

En anledning till att en modell kan vara längre är helt enkelt för att dess olika parametrar anges med större precision, vilket kräver överföring av fler siffror. Mycket av kraften hos MML kommer från dess hantering av hur exakt man ska ange parametrar i en modell, och en mängd olika approximationer som gör detta genomförbart i praktiken. Detta gör det möjligt att på ett användbart sätt jämföra, låt säga, en modell med många parametrar som är oprecist angivna mot en modell med färre parametrar mer exakt angivna.

Nyckelfunktioner i MML

MML kan användas för att jämföra modeller med olika struktur. Till exempel, dess tidigaste tillämpning var att hitta blandningsmodeller med det optimala antalet klasser. Att lägga till extra klasser till en blandningsmodell kommer alltid att tillåta att data anpassas med större noggrannhet, men enligt MML måste detta vägas mot de extra bitar som krävs för att koda parametrarna som definierar dessa klasser.
MML är en metod för bayesiansk modelljämförelse . Det ger varje modell ett betyg.
MML är skalinvariant och statistiskt invariant. Till skillnad från många Bayesianska urvalsmetoder bryr sig MML inte om du ändrar från att mäta längd till volym eller från kartesiska koordinater till polära koordinater.
MML är statistiskt konsekvent. För problem som Neyman-Scott (1948) problem eller faktoranalys där mängden data per parameter är begränsad ovan, kan MML uppskatta alla parametrar med statistisk konsistens .
MML står för mätnoggrannheten. Den använder Fisher-informationen (i Wallace-Freemans approximation 1987, eller andra hypervolymer i andra approximationer ) för att optimalt diskretisera kontinuerliga parametrar. Därför är den bakre alltid en sannolikhet, inte en sannolikhetstäthet.
MML har använts sedan 1968. MML-kodningsscheman har utvecklats för flera distributioner och många typer av maskininlärare, inklusive oövervakad klassificering, beslutsträd och grafer, DNA-sekvenser, Bayesiska nätverk, neurala nätverk (endast ett lager hittills ) , bildkomprimering, bild- och funktionssegmentering m.m.

Se även

Algoritmisk sannolikhet
Algoritmisk informationsteori
Grammatikinduktion
Induktiv slutledning
Induktiv sannolikhet
Kolmogorov komplexitet – absolut komplexitet (inom en konstant, beroende på det speciella valet av Universal Turing Machine ); MML är vanligtvis en beräkningsbar approximation (se )
Minsta beskrivningslängd – ett alternativ med en möjligen annan (icke-bayesiansk) motivation, utvecklat 10 år efter MML.
Occams rakkniv

externa länkar

Originalpublikation:

Wallace; Boulton (augusti 1968). "En informationsåtgärd för klassificering" . Datorjournal . 11 (2): 185–194. doi : 10.1093/comjnl/11.2.185 .

Böcker:

Wallace, CS (maj 2005). Statistisk och induktiv slutledning efter minsta meddelandelängd . Informationsvetenskap och statistik. Springer-Verlag. doi : 10.1007/0-387-27656-4 . ISBN 978-0-387-23795-4 .
Allison, L. (2018). Kodar Ockham's Razor . Springer. doi : 10.1007/978-3-319-76433-7 . ISBN 978-3319764320 . S2CID 19136282 . , om implementering av MML och källkod .

Relaterade länkar:

Länkar till alla Chris Wallaces kända publikationer.
En sökbar databas med Chris Wallaces publikationer .
Wallace, CS; Dowe, DL (1999). "Minsta meddelandelängd och Kolmogorov-komplexitet". Datorjournal . 42 (4): 270–283. CiteSeerX 10.1.1.17.321 . doi : 10.1093/comjnl/42.4.270 .
"Specialutgåva om Kolmogorovs komplexitet" . Datorjournal . 42 (4). 1999. ^{[ död länk ]}
Dowe, DL; Wallace, CS (1997). Lösa Neyman-Scott-problemet med minsta meddelandelängd . 28:e symposium om gränssnittet, Sydney, Australien. Datavetenskap och statistik . Vol. 28. s. 614–618.
Historia om MML, CSW:s sista föredrag .
Needham, S.; Dowe, D. (2001). Meddelandelängd som en effektiv Ockhams rakhyvel i beslutsträdsinduktion ( PDF) . Proc. 8:e internationella workshop om AI och statistik . s. 253–260. (Visar hur Occams rakhyvel fungerar bra när den tolkas som MML.)
Allison, L. (januari 2005). "Modeller för maskininlärning och datautvinning i funktionell programmering". Journal of Functional Programming . 15 (1): 15–32. doi : 10.1017/S0956796804005301 . S2CID 5218889 . (MML-, FP- och Haskell- kod ).
Comley, JW; Dowe, DL (april 2005). "Kapitel 11: Minsta meddelandelängd, MDL och generaliserade Bayesianska nätverk med asymmetriska språk" . I Grunwald, P.; Pitt, MA; Myung, IJ (red.). Framsteg i minsta beskrivningslängd: teori och tillämpningar . MIT Press. s. 265–294. ISBN 978-0-262-07262-5 .
Comley, Joshua W.; Dowe, DL (5–8 juni 2003). Allmänna bayesianska nätverk och asymmetriska språk . Proc. 2:a Hawaii internationella konferens om statistik och relaterade områden. , .pdf . Comley & Dowe ( 2003, 2005 ) är de två första artiklarna om MML Bayesian-nät som använder både diskreta och kontinuerliga värderade parametrar.

Dowe, David L. (2010). "MML, hybrid Bayesian nätverks grafiska modeller, statistisk konsistens, invarians och unikhet" ( PDF) . Handbook of Philosophy of Science (Volume 7: Handbook of Philosophy of Statistics) . Elsevier. s. 901–982. ISBN 978-0-444-51862-0 .
Minsta meddelandelängd (MML) , LA:s MML-introduktion, (MML alt.) .
Minsta meddelandelängd (MML), forskare och länkar .
"En annan MML-forskningswebbplats" . Arkiverad från originalet den 12 april 2017.
Snobsida för MML- blandningsmodellering .
MITECS : Chris Wallace skrev ett inlägg om MML för MITECS. (Kräver konto)
mikko.ps : Korta introduktionsbilder av Mikko Koivisto i Helsingfors
Akaike information criterium ( AIC ) metod för modellval , och en jämförelse med MML: Dowe, DL; Gardner, S.; Oppy, G. (dec 2007). "Bayes inte bust! Varför enkelhet är inget problem för Bayesians". Br. J. Philos. Sci . 58 (4): 709–754. doi : 10.1093/bjps/axm033 .