Minimalna długość wiadomości - Minimum message length

Minimalna długość wiadomości (MML) to metoda bayesowskiej teorii informacji służąca do porównywania i selekcji modeli statystycznych. Zapewnia formalną teorię informacji przekształcenia Brzytwy Ockhama : nawet jeśli modele są równe pod względem dokładności dopasowania do obserwowanych danych, ten, który generuje najbardziej zwięzłe wyjaśnienie danych, jest bardziej prawdopodobny (gdzie wyjaśnienie składa się z zestawienie modelu, a następnie bezstratne kodowanie danych przy użyciu podanego modelu). MML został wymyślony przez Chrisa Wallace'a , który po raz pierwszy pojawił się w nowatorskim artykule „Miara informacyjna do klasyfikacji”. MML jest pomyślany nie tylko jako konstrukcja teoretyczna, ale jako technika, którą można zastosować w praktyce. Różni się od pokrewnej koncepcji złożoności Kołmogorowa tym, że nie wymaga użycia kompletnego języka Turinga do modelowania danych.

Definicja

Shannon „s matematyczna teoria komunikacji (1948) stwierdza, że w kodzie optymalną długość wiadomości (binarnie) zdarzenia , gdzie jest prawdopodobieństwo , podaje . ${\ displaystyle E}$${\ displaystyle \ operatorname {długość} (E)}$${\ displaystyle E}$${\ displaystyle P (E)}$${\ displaystyle \ operatorname {długość} (E) = - \ log _ {2} (P (E))}$

Twierdzenie Bayesa stwierdza, że ​​prawdopodobieństwo (zmiennej) hipotezy przy danych ustalonych dowodach jest proporcjonalne do , które z definicji prawdopodobieństwa warunkowego jest równe . Chcemy modelu (hipotezy) o najwyższym takim późniejszym prawdopodobieństwie . Załóżmy, że kodujemy wiadomość, która reprezentuje (opisuje) zarówno model, jak i dane łącznie. Ponieważ najbardziej prawdopodobny model będzie miał najkrótszy taki komunikat. Przerywa wiadomość na dwie części: . Pierwsza część koduje sam model. Druga część zawiera informacje (np. Wartości parametrów lub warunki początkowe itp.), Które po przetworzeniu przez model dają zaobserwowane dane. ${\ displaystyle H}$${\ displaystyle E}$${\ Displaystyle P (E | H) P (H)}$${\ Displaystyle P (H \ ziemia E)}$${\ Displaystyle \ operatorname {długość} (H \ ziemia E) = - \ log _ {2} (P (H \ ziemia E))}$${\ Displaystyle - \ log _ {2} (P (H \ ziemia E)) = - \ log _ {2} (P (H)) + - \ log _ {2} (P (E | H))}$

MML w naturalny i precyzyjny sposób zamienia złożoność modelu na dobre dopasowanie. Bardziej skomplikowany model zajmuje więcej czasu (dłuższa pierwsza część), ale prawdopodobnie lepiej pasuje do danych (krótsza druga część). Tak więc metryka MML nie wybierze skomplikowanego modelu, chyba że ten model się opłaci.

Parametry o wartościach ciągłych

Jednym z powodów, dla których model może być dłuższy, byłby po prostu fakt, że jego różne parametry są określone z większą precyzją, co wymaga transmisji większej liczby cyfr. Duża moc MML wynika z obsługi tego, jak dokładnie określa się parametry w modelu, oraz z różnych przybliżeń, które sprawiają, że jest to wykonalne w praktyce. Pozwala to na użyteczne porównanie, powiedzmy, modelu z wieloma parametrami niedokładnie określonymi z modelem z mniejszą liczbą parametrów, które są dokładniej określone.

Kluczowe cechy MML

• MML może służyć do porównywania modeli o różnej strukturze. Na przykład jego najwcześniejsze zastosowanie polegało na znalezieniu modeli mieszanin o optymalnej liczbie klas. Dodanie dodatkowych klas do modelu mieszaniny zawsze pozwoli na dopasowanie danych z większą dokładnością, ale zgodnie z MML należy to porównać z dodatkowymi bitami wymaganymi do zakodowania parametrów definiujących te klasy.
• MML to metoda porównywania modeli bayesowskich . Daje każdemu modelowi punktację.
• MML jest niezmiennikiem skali i niezmiennym statystycznie. W przeciwieństwie do wielu metod selekcji bayesowskiej, MML nie dba o to, czy zmienisz pomiar długości na objętość, czy ze współrzędnych kartezjańskich na współrzędne biegunowe.
• MML jest statystycznie spójny. W przypadku problemów, takich jak problem Neymana-Scotta (1948) lub analiza czynnikowa, w których ilość danych na parametr jest ograniczona powyżej, MML może oszacować wszystkie parametry ze spójnością statystyczną .
• MML odpowiada za precyzję pomiaru. Wykorzystuje informacje Fishera (w przybliżeniu Wallace'a-Freemana 1987 lub innych hiper-tomów w innych przybliżeniach ), aby optymalnie zdyskretyzować parametry ciągłe. Dlatego późniejsze jest zawsze prawdopodobieństwem, a nie gęstością prawdopodobieństwa.
• MML jest używany od 1968 roku. Schematy kodowania MML zostały opracowane dla kilku dystrybucji i wielu rodzajów uczących się maszyn, w tym klasyfikacja bez nadzoru, drzewa decyzyjne i wykresy, sekwencje DNA, sieci bayesowskie, sieci neuronowe (dotychczas tylko jednowarstwowe), kompresja obrazu, segmentacja obrazu i funkcji itp.

Zobacz też

• Prawdopodobieństwo algorytmiczne
• Algorytmiczna teoria informacji
• Wprowadzenie do gramatyki
• Wnioskowanie indukcyjne
• Prawdopodobieństwo indukcyjne
• Złożoność Kołmogorowa - złożoność absolutna (w ramach stałej, zależnej od konkretnego wyboru Uniwersalnej Maszyny Turinga ); MML jest zwykle obliczalnym przybliżeniem (zobacz)
• Minimalna długość opisu - alternatywa o możliwie innej (nie bayesowskiej) motywacji, opracowana 10 lat po MML.
• Brzytwa Ockhama

Bibliografia

Linki zewnętrzne

Oryginalna publikacja:

• Wallace; Boulton (sierpień 1968). „Miara informacyjna do celów klasyfikacji” . Dziennik komputerowy . 11 (2): 185–194. doi : 10.1093 / comjnl / 11.2.185 .

Książki:

• Wallace, CS (maj 2005). Wnioskowanie statystyczne i indukcyjne na podstawie minimalnej długości wiadomości . Informatyka i statystyka. Springer-Verlag. ISBN   978-0-387-23795-4 . CS1 maint: zniechęcony parametr ( link )
• Allison, L. (2018). Kodowanie brzytwy Ockhama . Skoczek. doi : 10.1007 / 978-3-319-76433-7 . ISBN   978-3319764320 . S2CID   19136282 . , na temat implementacji MML i kodu źródłowego .

Powiązane linki:

• Linki do wszystkich znanych publikacji Chrisa Wallace'a .
• Przeszukiwać bazę publikacji Chrisa Wallace'a .
• Wallace, CS; Dowe, DL (1999). „Minimalna długość wiadomości i złożoność Kołmogorowa”. Dziennik komputerowy . 42 (4): 270–283. CiteSeerX   10.1.1.17.321 . doi : 10.1093 / comjnl / 42.4.270 .
• „Wydanie specjalne o złożoności Kołmogorowa” . Dziennik komputerowy . 42 ust. 4. 1999.
• Dowe, DL; Wallace, CS (1997). Rozwiązywanie problemu Neymana-Scotta przez minimalną długość wiadomości . 28th Symposium on the interface, Sydney, Australia. Informatyka i statystyka . 28 . s. 614–618.
• Historia MML, ostatnia rozmowa CSW .
• Needham, S .; Dowe, D. (2001). Długość wiadomości jako skuteczna brzytwa Ockhama w indukcji drzewa decyzyjnego (PDF) . Proc. 8th International Workshop on AI and Statistics . s. 253–260. (Pokazuje, jak brzytwa Occam działa dobrze, gdy jest interpretowana jako MML.)
• Allison, L. (styczeń 2005). „Modele uczenia maszynowego i eksploracji danych w programowaniu funkcjonalnym”. Journal of Functional Programming . 15 (1): 15–32. doi : 10.1017 / S0956796804005301 . S2CID   5218889 . ( Kod MML, FP i Haskell ).
• Comley, JW; Dowe, DL (kwiecień 2005). „Rozdział 11: Minimalna długość wiadomości, MDL i uogólnione sieci bayesowskie z asymetrycznymi językami” . W Grunwaldzie, P .; Pitt, MA; Myung, IJ (red.). Postęp w minimalnej długości opisu: teoria i zastosowania . MIT Press. s. 265–294. ISBN   978-0-262-07262-5 .
• Comley, Joshua W .; Dowe, DL (5–8 czerwca 2003). Ogólne sieci bayesowskie i języki asymetryczne . Proc. 2. Hawajska Międzynarodowa Konferencja Statystyczna i Dziedzin Pokrewnych. , .pdf . Comley i Dowe ( 2003 , 2005 ) to pierwsze dwa artykuły na temat sieci bayesowskich MML wykorzystujących zarówno dyskretne, jak i ciągłe parametry.

• Dowe, David L. (2010). „MML, hybrydowe modele graficzne sieci bayesowskich, spójność statystyczna, niezmienność i niepowtarzalność” (PDF) . Podręcznik filozofii nauki (tom 7: Podręcznik filozofii statystyki) . Elsevier. s. 901–982. ISBN   978-0-444-51862-0 .
• Minimalna długość wiadomości (MML) , wprowadzenie do MML LA (MML alt.) .
• Minimalna długość wiadomości (MML), badacze i linki .
• „Kolejna witryna badawcza MML” . Zarchiwizowane od oryginału w dniu 12 kwietnia 2017 r.
• Strona Snoba dotycząca modelowania mieszanin MML .
• MITECS : Chris Wallace napisał wpis o MML dla MITECS. (Wymaga konta)
• mikko.ps : Krótkie slajdy wprowadzające autorstwa Mikko Koivisto w Helsinkach
• Kryterium informacyjne Akaike'a ( AIC ) metoda wyboru modelu i porównanie z MML: Dowe, DL; Gardner, S .; Oppy, G. (grudzień 2007). „Bayes to nie biust! Dlaczego prostota nie jest problemem dla Bayesa”. Br. J. Philos. Sci . 58 (4): 709–754. doi : 10.1093 / bjps / axm033 .