Minimální délka zprávy - Minimum message length

Minimální délka zprávy (MML) je bayesovská informační teoretická metoda pro srovnávání a výběr statistických modelů.^[1] Poskytuje formální teorie informace přepracování Occamova břitva: i když jsou modely stejné ve své míře přesnosti přizpůsobení pozorovaným datům, generuje nejstručnější vysvětlení údajů bude pravděpodobněji správný (kde vysvětlení Skládá se z prohlášení modelu, za nímž následuje bezztrátové kódování dat pomocí uvedeného modelu). MML vynalezl Chris Wallace, který se poprvé objevil v seminární práci „Informační míra pro klasifikaci“.^[2] MML není zamýšleno jen jako teoretický konstrukt, ale jako technika, kterou lze nasadit v praxi.^[3] Liší se od souvisejícího konceptu Kolmogorovova složitost v tom, že nevyžaduje použití a Turing-kompletní jazyk pro modelování dat.^[4]

Definice

Shannon je Matematická teorie komunikace (1948) uvádí, že v optimálním kódu je délka zprávy (v binární podobě) události ${ displaystyle E}$, ${ displaystyle operatorname {délka} (E)}$, kde ${ displaystyle E}$ má pravděpodobnost ${ displaystyle P (E)}$, darováno ${ displaystyle operatorname {délka} (E) = - log _ {2} (P (E))}$.

Bayesova věta uvádí, že pravděpodobnost hypotézy (proměnné) ${ displaystyle H}$ daný pevný důkaz ${ displaystyle E}$ je úměrný ${ displaystyle P (E | H) P (H)}$, který podle definice podmíněná pravděpodobnost, je rovný ${ displaystyle P (H land E)}$. Chceme model (hypotézu) s nejvyšší takovou zadní pravděpodobnost. Předpokládejme, že kódujeme zprávu, která představuje (popisuje) model i data společně. Od té doby ${ displaystyle operatorname {délka} (H land E) = - log _ {2} (P (H land E))}$, nejpravděpodobnější model bude mít nejkratší takovou zprávu. Zpráva se dělí na dvě části: ${ displaystyle - log _ {2} (P (H land E)) = - log _ {2} (P (H)) + - log _ {2} (P (E | H))}$. První část kóduje samotný model. Druhá část obsahuje informace (např. Hodnoty parametrů nebo počáteční podmínky atd.), Které při zpracování modelem vydávají pozorovaná data.

MML přirozeně a přesně vyměňuje složitost modelu za dobrou shodu. Stav složitějšího modelu trvá déle (delší první část), ale pravděpodobně lépe zapadá do dat (kratší druhá část). Metrika MML si tedy nevybere komplikovaný model, pokud se tento model nezaplatí.

Parametry s kontinuální hodnotou

Jedním z důvodů, proč by model mohl být delší, by byl jednoduše proto, že jeho různé parametry jsou uvedeny s větší přesností, což vyžaduje přenos více číslic. Velká část síly MML pochází z manipulace s tím, jak přesně stavět parametry v modelu, a z různých aproximací, které to v praxi umožňují. To mu umožňuje užitečně porovnat, řekněme, model s mnoha parametry nepřesně uvedenými oproti modelu s menším počtem parametrů přesněji.

Klíčové vlastnosti MML

• MML lze použít k porovnání modelů různé struktury. Například jeho první aplikace byla při hledání smíšené modely s optimálním počtem tříd. Přidání dalších tříd do modelu směsi vždy umožní přizpůsobení dat s větší přesností, ale podle MML to musí být zváženo oproti bitům navíc potřebným pro kódování parametrů definujících tyto třídy.
• MML je metoda Bayesovské srovnání modelů. Dává každému modelu skóre.
• MML je škálově invariantní a statisticky neměnný. Na rozdíl od mnoha Bayesianových metod výběru MML nezáleží na tom, zda přecházíte z měření délky na objem nebo z kartézských souřadnic na polární souřadnice.
• MML je statisticky konzistentní. Pro problémy, jako je Neyman-Scott (1948) analýza problému nebo faktoru, kde je výše dat na parametr omezena výše, může MML odhadnout všechny parametry pomocí statistická konzistence.
• MML odpovídá za přesnost měření. Využívá Fisher informace (v aproximaci Wallace-Freeman 1987, nebo jiné hyperobjemy v další aproximace ) pro optimální diskretizaci spojitých parametrů. Proto je zadní vždy pravděpodobnost, nikoli hustota pravděpodobnosti.
• MML se používá od roku 1968. Schémata kódování MML byla vyvinuta pro několik distribucí a mnoho druhů strojových studentů, včetně nekontrolované klasifikace, rozhodovacích stromů a grafů, sekvencí DNA, Bayesovské sítě, neuronové sítě (zatím pouze jedna vrstva), komprese obrazu, segmentace obrazu a funkcí atd.

Viz také

• Algoritmická pravděpodobnost
• Algoritmická teorie informací
• Gramatická indukce
• Indukční závěr
• Indukční pravděpodobnost
• Kolmogorovova složitost - absolutní složitost (v konstantě, v závislosti na konkrétní volbě Universal Turingův stroj ); MML je obvykle vypočítatelná aproximace (viz ^[5])
• Minimální délka popisu - alternativa s možná odlišnou (nebajesiánskou) motivací, vyvinutá 10 let po MML.
• Occamova břitva

Reference

externí odkazy

Původní publikace:

• Wallace; Boulton (srpen 1968). „Informační opatření ke klasifikaci“. Počítačový deník. 11 (2): 185–194. doi:10.1093 / comjnl / 11.2.185.CS1 maint: ref = harv (odkaz)

Knihy:

• Wallace, C.S. (Květen 2005). Statistické a indukční závěry podle minimální délky zprávy. Informační věda a statistika. Springer-Verlag. ISBN  978-0-387-23795-4.
• Allison, L. (2018). Kódování Ockhamova břitva. Springer. doi:10.1007/978-3-319-76433-7. ISBN  978-3319764320.o implementaci MML a zdrojový kód.

Související odkazy:

• Odkazy na všechny Chris Wallace známé publikace.
• A prohledávatelná databáze publikací Chrise Wallacea.
• Wallace, C.S .; Dowe, D.L. (1999). „Minimální délka zprávy a složitost Kolmogorovova“. Počítačový deník. 42 (4): 270–283. CiteSeerX  10.1.1.17.321. doi:10.1093 / comjnl / 42.4.270.CS1 maint: ref = harv (odkaz)
• „Zvláštní vydání o Kolmogorovově složitosti“. Počítačový deník. 42 (4). 1999.
• Dowe, D.L .; Wallace, CS (1997). Řešení problému Neyman-Scott podle minimální délky zprávy. 28. sympozium o rozhraní, Sydney, Austrálie. Výpočetní věda a statistika. 28. str. 614–618.CS1 maint: ref = harv (odkaz)
• Historie MML, poslední přednáška CSW.
• Needham, S .; Dowe, D. (2001). Délka zprávy jako efektivní Ockhamova břitva při indukci rozhodovacího stromu (PDF). Proc. 8. mezinárodní workshop o AI a statistice. 253–260.CS1 maint: ref = harv (odkaz) (Ukazuje jak Occamova břitva funguje dobře, když je interpretován jako MML.)
• Allison, L. (leden 2005). "Modely pro strojové učení a dolování dat ve funkčním programování". Journal of Functional Programming. 15 (1): 15–32. doi:10.1017 / S0956796804005301.CS1 maint: ref = harv (odkaz) (MML, FP a Haskell kód ).
• Comley, J.W .; Dowe, D.L. (Duben 2005). „Kapitola 11: Minimální délka zprávy, MDL a zobecněné Bayesovské sítě s asymetrickými jazyky“. In Grunwald, P .; Pitt, M. A .; Myung, I.J. (eds.). Pokroky v minimální délce popisu: Teorie a aplikace. M.I.T. Lis. 265–294. ISBN  978-0-262-07262-5.CS1 maint: ref = harv (odkaz)
• Comley, Joshua W .; Dowe, D.L. (5. – 8. Června 2003). Obecné Bayesovské sítě a asymetrické jazyky. Proc. 2. mezinárodní konference o statistice a souvisejících oborech na Havaji.CS1 maint: ref = harv (odkaz), .pdf. Comley & Dowe (2003, 2005 ) jsou první dva příspěvky o MML Bayesianových sítích využívajících jak diskrétní, tak kontinuální hodnotové parametry.

• Dowe, David L. (2010). „MML, hybridní Bayesovské síťové grafické modely, statistická konzistence, invariance a jedinečnost“ (PDF). Příručka filozofie vědy (svazek 7: Příručka filozofie statistiky). Elsevier. str. 901–982. ISBN  978-0-444-51862-0.CS1 maint: ref = harv (odkaz)
• Minimální délka zprávy (MML), Úvod MML v LA, (MML alt.).
• Minimální délka zprávy (MML), výzkumní pracovníci a odkazy.
• „Další web pro výzkum MML“. Archivovány od originál dne 12. dubna 2017.
• Snob stránka pro MML modelování směsi.
• MITECS: Chris Wallace napsal záznam na MML pro MITECS. (Vyžaduje účet)
• mikko.ps: Krátké úvodní snímky Mikka Koivisto v Helsinkách
• Informační kritérium Akaike (AIC ) metoda výběr modelu a srovnání s MML: Dowe, D.L .; Gardner, S .; Oppy, G. (prosinec 2007). „Bayes není Bust! Proč pro Bayesians není jednoduchost žádný problém“. Br. J. Philos. Sci. 58 (4): 709–754. doi:10.1093 / bjps / axm033. Archivovány od originál dne 16. 12. 2008.CS1 maint: ref = harv (odkaz)