Principen om minsta beskrivningslängd

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 12 mars 2021; verifiering kräver 1 redigering .

Principen om minsta beskrivningslängd ( MDL ) är en formalisering av Occams rakhyvel , där den bästa hypotesen (modellen och dess parametrar) för en given datamängd är den som leder till bättre datakomprimering . MDL-principen föreslogs av Jorma Rissanen 1978 [1] . Principen är ett viktigt begrepp inom informationsteori och beräkningslärandeteori [2] [3] [4] .

Översikt

Vilken uppsättning data som helst kan representeras som en sträng av tecken från ett ändligt (säg binärt ) alfabet .

[MDL-principen] är baserad på följande insikt: vilket mönster som helst i en given datauppsättning kan användas för att komprimera data , det vill säga beskriva data med en mindre teckenuppsättning än vad som behövs för att beskriva data bokstavligt. (Grunwald, 1998) [5]

MDL är en teori om inferens och statistisk slutledning som börjar med tanken att all statistisk inlärning handlar om att upptäcka mönster i data, och den bästa hypotesen för att beskriva mönster i data är den som komprimerar data mest. I likhet med andra statistiska metoder kan principen användas för att träna modellparametrar med hjälp av vissa data. Även om vanliga statistiska metoder förutsätter att modellens allmänna form är fast. MDL-principens främsta styrka är att den kan användas för att välja det allmänna utseendet på en modell och dess parametrar. En kvantitativ egenskap (ibland bara modellen, ibland bara parametrarna, ibland både modellen och parametrarna) kallas en hypotes. Grundidén är att överväga en tvåstegskod (förlustfri) som kodar data genom att först koda hypotesen i den uppsättning hypoteser som övervägs och sedan koda "med" . I sitt enklaste sammanhang betyder detta helt enkelt "kodningen av avvikelsen för data från den förutsägelse som erhålls av" : $D$ $H$ ${\cal {H}}$ $D$ $H$ $H$

{L(D)}=\min _{H\in {\cal {H))}\ (\ L(H)+L(D|H)\ )\

Hypotesen på vilken miniminivån uppnås anses då vara den bästa förklaringen till uppgifterna . Som ett enkelt exempel, överväg ett regressionsproblem: låt data bestå av en sekvens av punkter , låt mängden vara mängden av alla polynom från till . För att beskriva ett gradpolynom (säg) måste man först diskretisera parametrarna till viss precision, sedan måste man beskriva denna precision ( ett naturligt tal ). Sedan ska man beskriva graden (ett annat naturligt tal) och slutligen bör man beskriva parametrarna. Den totala längden blir . Sedan beskriver vi punkterna med att använda någon fast kod för x-värdena, och sedan använda en kod för varianserna . $H$ $D$ $D$ $D=(x_{1},y_{1}),\ldots ,(x_{n},y_{n})$ ${\cal {H}}$ $X$ $Y$ $H$ $k$ $k$ $k+1$ $L(H)$ $D$ $n$ $y_{i}-H(x_{i})$

I praktiken används ofta (men inte alltid) en statistisk modell . Till exempel, associera varje polynom med motsvarande villkorsfördelning, vilket indikerar att datan är normalfördelad med ett medelvärde och viss varians , som antingen kan fixeras eller läggas till som parametrar. Sedan reduceras mängden hypoteser till en linjär modell med i form av ett polynom. $H$ $X$ $Y$ $H(X)$ $\sigma ^{2}$ ${\cal {H}}$ $Y=H(X)+\epsilon$ $H$

Dessutom är de specifika värdena för parametrarna ofta inte direkt intressanta, utan bara till exempel graden av polynomet är intressant. I det här fallet sätts mängden lika med , där varje element representerar hypotesen att data bäst beskrivs av ett polynom av grad j. Koda sedan de givna hypotesdata med en endelad kod utformad så att när någon hypotes passar data väl är koden kort. Utvecklingen av sådana koder kallas universell kodning . Det finns olika typer av universella koder som kan användas, som ofta ger liknande längder för långa datasekvenser men olika för korta sekvenser. De "bästa" koderna (i den meningen att de har egenskapen minimax-optimalitet) är normaliserade koder för maximal sannolikhet (NML) eller Shtarkov- koder . En mycket användbar klass av koder är Bayesianska marginella sannolikhetskoder. För en familj av exponentialfördelningar, när Jeffreys prior används och parameterutrymmet är lämpligt begränsat, är de asymptotiskt samma som NML-koder. Detta för MDL-teorin närmare det objektiva Bayesianska modellvalet, på vilket Jeffreys prioriteten också ibland tillämpas, om än av olika anledningar. ${\cal {H}}$ ${\cal {H}}=\{{\cal {H}}_{0},{\cal {H}}_{1},\ldots \}$ ${\cal {H}}_{j}$ $D$ ${\cal {H}}_{j}$ $H\in {\cal {H}}_{j}$ $L(D|H)$

MDL kontra Salomons teori om slutledning

För att välja den hypotes som fångar mest regelbundenhet i data letar forskarna efter den hypotes som ger bäst komprimering. För att göra detta är datakomprimeringskoden fixerad . Den kanske vanligaste koden som kan användas är ett ( turing- komplett ) datorspråk . Utdataprogrammet är skrivet på detta språk. Sedan presenterar programmet effektivt data. Längden på det kortaste programmet som matar ut data kallas Kolmogorovs komplexitet för data. Detta är den centrala idén i Ray Solomons idealiserade teori om slutledning , som är inspirationen till MDL.

Slutsats

Denna matematiska teori ger dock ingen praktisk metod för att få en slutsats. De viktigaste anledningarna till detta är:

Kolmogorovs komplexitet är inte beräkningsbar - det finns ingen algoritm som, givet en godtycklig sekvens av data, producerar det kortaste programmet som återger data.
Kolmogorovs komplexitet beror på vilket datorspråk som används. Valet av språk är godtyckligt, men det påverkar komplexiteten med någon ytterligare konstant. Av denna anledning förkastas konstanten i Kolmogorovs komplexitetsteori. I praktiken är dock bara en liten mängd data tillgänglig, så konstanterna kan ha en mycket stor inverkan på utdataresultaten - bra resultat garanteras inte när man arbetar med en begränsad uppsättning data.

MDL försöker bekämpa detta problem genom att:

Begränsning av uppsättningen tillåtna koder så att det blir möjligt (beräkningsmässigt) att hitta den minsta kodlängden för data enligt de tillåtna koderna.
Välja koder som är rimligt effektiva oavsett data. Idén om "rimlig effektivitet" återspeglas i idén om "universell kod".

En av de viktigaste egenskaperna hos MDL-metoder är att de ger ett naturligt skydd mot överanpassning , eftersom de implementerar en avvägning mellan komplexiteten i hypotesen (modellklassen) och komplexiteten i data [3] .

MDL-exempel

Myntet kastas 1000 gånger och antalet huvuden eller svansar registreras. Tänk på två klasser av modeller:

Den första är en kod som skriver 0 för huvuden och 1 för svansar. Den här koden representerar hypotesen att myntet är symmetriskt (dvs huvud och svans måste vara lika sannolika). Längden på koden, enligt denna kodning, är alltid exakt 1000 bitar.
Den andra består av alla koder som är effektiva för ett skevt mynt och representerar hypotesen att myntet är snedställt. Låt oss säga att vi ser 510 huvuden och 490 svansar. Då är kodlängden som motsvarar den bästa kodningen i den andra klassen av modeller mindre än 1000 bitar.

Av denna anledning kan en naiv statistisk metod välja den andra modellen som den bästa förklaringen till data. MDL-metoden skulle dock bygga en kod baserad på hypotesen istället för att använda den bästa koden. Denna kod kan vara en normaliserad maximal sannolikhetskod eller en Bayesiansk kod. Om en sådan kod används skulle den totala längden på koden baserat på den andra klassen av modeller vara mer än 1000 bitar. Därför är slutsatsen som oundvikligen följer av MDL-metoden att det inte finns tillräckligt med bevis för snedmynthypotesen, även om det bästa inslaget i den andra klassen av modeller ger en bättre passform till data.

MDL-beteckning

Centralt för MDL-teorin är en-till-en-överensstämmelsen mellan funktionskodlängder och sannolikhetsfördelningar ( detta följer av Kraft-McMillan-olikheten ). För vilken sannolikhetsfördelning som helst kan du konstruera en kod så att längden (i bitar) är . Denna kod minimerar den förväntade kodlängden. Omvänt, om en kod ges kan man konstruera en sannolikhetsfördelning så att ovanstående påstående håller. ( Avrundningsproblem ignoreras här.) Att hitta en effektiv kod motsvarar med andra ord att hitta en bra sannolikhetsfördelning. $P$ $C$ $C(x)$ $-\log _{2}P(x)$ $C$ $P$

Relaterade begrepp

MDL-principen är starkt relaterad till sannolikhetsteori och statistik genom kodmatchningen och sannolikhetsfördelningen som nämnts ovan. Detta har fått vissa forskare att dra slutsatsen att MDL-principen är likvärdig med Bayesiansk inferens - modellkodens längd och data i MDL motsvarar den tidigare sannolikheten och marginella sannolikheten i det Bayesianska schemat [6] .

Medan bayesianska algoritmer ofta är användbara för att konstruera effektiva MDL-koder, rymmer MDL-principen även andra icke-bayesianska koder. Ett exempel är Starkovs normaliserade maximum likelihood -kod, som spelar en central roll i nuvarande MDL-teori men inte har någon motsvarighet i Bayesiansk slutledning. Rissanen framhåller dessutom att vi inte bör göra några antaganden om riktigheten av datainsamlingsprocessen - i praktiken är en klass av modeller vanligtvis en förenkling av verkligheten, och innehåller därför inte några koder eller sannolikhetsfördelningar som är sanna i ett mål. känsla [7] [8] . I den sista länken för Rissanen den matematiska grunden för MDL-principen till Kolmogorov-strukturfunktionen .

Enligt MDL-filosofin bör Bayesianska metoder undvikas om de är baserade på en opålitlig tidigare sannolikhet , vilket kan leda till dåliga resultat. A priori-förhållanden som är acceptabla ur MDL-synpunkt är också att föredra framför den så kallade Bayesianska objektiva analysen. Här är dock orsakerna oftast olika [9] .

Andra system

MDL var inte den första informationsteoretiska inlärningsmetoden. Redan 1968 introducerade Wallace och Bolton ett relaterat koncept som kallas minimimeddelandelängden ( MML ) . Skillnaden mellan MDL och MML är en källa till ständig förvirring. Externt verkar metoderna vara mestadels likvärdiga, men det finns några betydande skillnader, särskilt i tolkning:

MML är ett helt subjektivt Bayesianskt tillvägagångssätt - det börjar med tanken att det finns en viss tro på processen att erhålla data i form av en tidigare distribution. MDL-principen undviker alla antaganden om datainsamlingsprocessen.
Båda metoderna använder tvådelade koder - en del representerar alltid informationen de försöker träna, såsom indexet för klassmodellen (i modellval ) eller parametervärden (i parameterutvärdering ). Den andra delen innehåller kodad data enligt informationen från den första delen. Skillnaden i metoder är att MDL-litteraturen rekommenderar att man lägger in oönskade parametrar i den andra delen av koden, där de kan representeras med data med hjälp av den så kallade endelade koden , som ofta är mer effektiv än tvådelad koda. I den ursprungliga MML-beskrivningen är alla parametrar kodade i den första delen, så att alla parametrar tränas.
I MML-schemat är varje parameter satt till exakt den position som resulterar i den optimala totala meddelandelängden - exemplet som ges skulle inträffa om vissa parametrar från början ansågs vara "möjligen användbara" för modellen, men senare visade sig vara oförmögna för att förklara uppgifterna. MDL-schemat fokuserar mer på att jämföra modellklasser snarare än själva modellerna, och det är mer naturligt att ställa samma fråga genom att jämföra modellklasser än att explicit inkludera en sådan parameter i en klass och lämna den utanför en annan.

Se även

Anteckningar

↑ Rissanen, 1978 , sid. 465–658.
↑ Minsta beskrivningslängd (nedlänk) . Helsingfors universitet . Hämtad 3 juli 2010. Arkiverad från originalet 18 februari 2010. (obestämd)
↑ 1 2 Grünwald, 2007 .
↑ Grünwald, Myung, Pitt, 2005 .
↑ Grünwald, 2004 .
↑ MacKay, 2003 .
↑ Rissanen, Jorma . Jorma Rissanens hemsida . Arkiverad från originalet den 10 december 2015. Hämtad 3 juli 2010.
↑ Rissanen, 2007 .
↑ Nannen, 2010 .

Litteratur

Rissanen J. Modellering efter kortaste databeskrivning // Automatica. - 1978. - T. 14 , nr. 5 . - doi : 10.1016/0005-1098(78)90005-5 .
Peter D. Grunwald. principen om minsta beskrivningslängd. — Cambridge, Massachusetts; London, England: MIT Press , 2007. - ISBN 978-0-262-07281-6 .
Framsteg i minsta beskrivningslängd: teori och tillämpningar / Peter D. Grünwald, In Jae Myung, Mark A. Pitt. — Cambridge, Massachusetts; London, England: MIT Press , 2005. - (Neural Information Processing). — ISBN 0-262-07262-9 .

Peter Grunwald. [1] . – 2004.
Rissanen J. Information och komplexitet i statistisk modellering . - Springer, 2007. - (Informationsvetenskap och statistik). - ISBN 0-387-36610-5 .
Volker Nannen. En kort introduktion till modellval, Kolmogorovs komplexitet och minsta beskrivningslängd // förtryck. — 2010.
David Mackay. Informationsteori, slutledningsalgoritmer och inlärningsalgoritmer . — Cambridge University Press , 2003.

Läsning för vidare läsning

Minsta beskrivningslängd på webben , av Helsingfors universitet. Innehåller läsningar, demonstrationer, evenemang och länkar till MDL-forskare.
Jorma Rissanens hemsida , med föreläsningsanteckningar och annat aktuellt material om MDL.
Advances in Minimum Description Length , MIT Press , ISBN 0-262-07262-9 .

Minsta kvadrater och regressionsanalys

Beräkningsstatistik _

Minsta kvadratiska metod
Linjär MNC
Icke-linjära minsta kvadrater
LSM med iterativ omräkning av vikter

Korrelation
och beroende

Pearson korrelationskoefficient
Rank korrelation ( Spearman
Kendall )
Partiell korrelation
Snedvridande faktor

Regressionsanalys

Vanlig MNC
Partiell minsta kvadratmetod
Minst hela kvadrater
Ridge regression

Regression som
statistisk
modell

Linjär regression	Enkel linjär regression Vanlig MNC Generaliserade minsta kvadrater Viktade minsta rutor Grundläggande linjär modell
prediktiv struktur	Polynomregression tillväxtkurva Segmenterad regression Lokal regression
Anpassad regression	icke-linjär Icke-parametrisk semi-parametrisk hållbar kvantil isotoniska
Icke -standardfel	Generaliserad linjär modell Binomial regression Poisson-regression Logistisk tillbakagång

Variansupplösning

Variansanalys
Kovariansanalys
Multivariat variansanalys

Modellstudie

C p Malva
Stegvis regression
Att välja en statistisk modell
Validering av regressionsmodell

Förutsättningar

Genomsnittlig och förväntad respons
Gauss-Markovs teorem
Fel och avvikelser
Statistiskt test
Studentiserad balans
Minsta medelkvadratfel

Experimentplanering
_

Responsytmetodik
Optimal experimentdesign
Bayesiansk experimentdesign

Numerisk
uppskattning

Ansökningar

Approximation med hjälp av kurvor
Kalibreringskurva
Savitsky-Golay filter
Systemidentifiering
Metod för att flytta minsta kvadrater