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

Minimální délka zprávy (MML) je Bayesovská informační teoretická metoda pro srovnání a výběr statistických modelů. Poskytuje formální přepracování teorie informace o Occamu Razor : i když jsou modely stejné v míře přesnosti přizpůsobení pozorovaným datům, ten, který generuje nejstručnější vysvětlení dat, je pravděpodobně správnější (kde vysvětlení sestává z vyjádření modelu, následované bezztrátovým kódováním dat pomocí uvedeného modelu). MML vynalezl Chris Wallace , který se poprvé objevil v seminární práci „Informační míra pro klasifikaci“. MML není zamýšleno jen jako teoretický konstrukt, ale jako technika, kterou lze nasadit v praxi. Od souvisejícího konceptu Kolmogorovovy složitosti se liší tím, že pro modelování dat nevyžaduje použití Turingova úplného jazyka.

Definice

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

Bayesova věta uvádí, že pravděpodobnost (variabilní) hypotézy dané pevným důkazem je úměrná , což se podle definice podmíněné pravděpodobnosti rovná . Chceme model (hypotézu) s nejvyšší takovou zadní pravděpodobností . Předpokládejme, že zakódujeme zprávu, která představuje (popisuje) model i data společně. Protože nejpravděpodobnější model bude mít nejkratší takovou zprávu. Tato zpráva láme do dvou částí: . První část kóduje samotný model. Druhá část obsahuje informace (např. Hodnoty parametrů, počáteční podmínky atd.), Které při zpracování modelem vydávají pozorovaná data. ${\ displaystyle H}$${\ displaystyle E}$${\ displaystyle P (E | H) P (H)}$${\ displaystyle P (H \ land E)}$${\ displaystyle \ operatorname {délka} (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 přirozeně a přesně obchoduje se složitostí modelu pro 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 proti 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í modelů směsí 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 srovnání Bayesianského modelu . 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í. U problémů, jako je Neyman-Scottova (1948) problémová nebo faktorová analýza, kde je výše dat na parametr omezena výše, může MML odhadnout všechny parametry se statistickou konzistencí .
• MML odpovídá za přesnost měření. Využívá Fisherovy informace (v aproximaci Wallace-Freemana 1987 nebo jiné hyperobjemy v jiných aproximacích ) k 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 byly vyvinuty pro několik distribucí a mnoho druhů strojových studentů, včetně nekontrolované klasifikace, rozhodovacích stromů a grafů, sekvencí DNA, Bayesovských sítí , neuronových 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 Machine ); MML je obvykle vypočítatelná aproximace (viz)
• Minimální délka popisu - alternativa s možná odlišnou (nebajesovskou) motivací, vyvinutá 10 let po MML.
• Occamova břitva

Reference

externí odkazy

Původní publikace:

• Wallace; Boulton (srpen 1968). Msgstr "Informační opatření ke klasifikaci" . Počítačový deník . 11 (2): 185–194. doi : 10,1093 / comjnl / 11.2.185 .

Knihy:

• Wallace, CS (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 . CS1 maint: discouraged parameter ( link )
• Allison, L. (2018). Kódování Ockhamova břitva . Springer. doi : 10,1007 / 978-3-319-76433-7 . ISBN   978-3319764320 . S2CID   19136282 . , o implementaci MML a zdrojového kódu .

Související odkazy:

• Odkazy na všechny známé publikace Chrise Wallacea .
• Databáze s možností vyhledávání Chrise Wallaceových publikací .
• Wallace, CS; Dowe, DL (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 .
• "Zvláštní vydání o Kolmogorovově složitosti" . Počítačový deník . 42 (4). 1999.
• Dowe, DL; 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.
• 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. (Ukazuje, jak holicí strojek Occam 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 . S2CID   5218889 . (MML, FP a Haskellův kód ).
• Comley, JW; Dowe, DL (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, MA; Myung, IJ (eds.). Pokroky v minimální délce popisu: Teorie a aplikace . MIT Stiskněte. 265–294. ISBN   978-0-262-07262-5 .
• Comley, Joshua W .; Dowe, DL (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. , .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 .
• Minimální délka zprávy (MML) , úvod do MML LA, (MML alt.) .
• Minimální délka zprávy (MML), výzkumníci a odkazy .
• Msgstr "Další web pro výzkum MML" . Archivovány od originálu dne 12. dubna 2017.
• Stránka Snob pro modelování směsi MML .
• MITECS : Chris Wallace napsal příspěvek na MML pro MITECS. (Vyžaduje účet)
• mikko.ps : Krátké úvodní snímky od Mikka Koivisto v Helsinkách
• Metoda výběru modelu Akaike podle informačního kritéria ( AIC ) a srovnání s MML: Dowe, DL; 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 .