Introduktion til informationsteori

Kursusbeskrivels

Formålet med kurset er at gøre opmærksom på nytten af den kortest mulige beskrivelse af data som metode til modelvalg. Denne længde kaldes Kolmogorov kompleksiteten, og Minimum Description Length (MDL) er en praktisk beregnelig approksimation. Målestøj er et begreb alle med bare en anelse eksperimentel-videnskabelig baggrund stifter bekendtskab med. I f.eks. fysik undervisningen i gynmasiet og på universitetet bruger vi megen tid på at indlære forskellige matematiske modeller til at beskrive det vi ser gennem vores sanser eller via måleapparater. Modellerne er valgt fordi de til en vis nøjagtighed kan verificeres gennem egentlige eksperimenter. Modellerne har altafgørende betydning for den videre forståelse af de studerede fænomener og de benyttes i vid udstrækning til at lave forudsigelser for experimenter endnu ikke foretaget. Data måles altid med en usikkerhed, måledata har ikke uendelig mange decimaler! Man skal derfor kun forvente at en model beskriver det essentielle. Begrebet "essentiel'' viser sig at kunne defineres algoritmisk: En models evne til at simulere data afvejes mod mængden af målestøj, der implicit antages. Men for at foretage denne afvejning samt at sammenligne forskellige modellers evne til at beskrive det samme fænomen (datasæt), må man vedtage en og samme enhed til at beskrive kompleksiteten af model og målestøj. Som eksempel tænk på et datasæt der er overvejende polynomielt, f.eks. en sampling af funktionen f(x) = a x^2+støj. Vi kan sammeligne modeller ved at nedskrive deres parametre som en liste af rationelle tal dvs. heltalspar, algoritmen til at producere funktionen, samt listen af målestøj (også par af heltal). Dette perspektiv giver anledning til en naturlig 2-delt databeskrivelse. En syntaktisk og en semantisk. Som oftest har man ikke, som i det ovenstående eksempel, en nøjagtig forhåndsviden om datakildens karakter og man er derfor nød til at antage en mest sandsynlig klasse af modeller, såsom klassen af polynomier, neurale netværk, sum af cosinus funktioner m.m. Denne antagelse bliver beskrivelsens semantik, mens elementerne i klassen dikterer beskrivelsens syntaks. Semantikken bestemmer således hvilken type modeller (og dermed målestøj) vi hælder til, og det semantiske valg bliver det eneste men altafgørende ikke automatiske (altså subjektive) valg i modelvalgsprocessen.

Litteraturliste:

• Brøndum og Monrad: "Statistik I - Sandsynlighedsregning og statistiske grundbegreber", Den Private Ingeniør Fond, 1993, ca. kr. 75.
• Shannon og Weaver: "The Mathematical Theory of Communication", University of Illinois Press, 1963, ISBN 0-252-72548-4, ca. kr. 100.
• Rissanen: "Stochastic Complexity in Statistical Inquiry", World Scientific, 1989, ISBN 981-02-0311-X, ca. kr. 370.
• Rissanen: "Fisher Information and Stochastic Complexity", IEEE Transactions on Information Theory, Vol. 42, No. 1, Jan.\ 1996, (kopi pris).
• Dom: "MDL Estimation for Small Sample Sizes and Its Application to Linear Regression",, Technical Report RJ 10030 (90526), IBM Almaden Research Center, 1996, (kopi pris).
• Jaynes: "Prior Probabilities", IEEE Transactions on Systems Science and Cybernetics, Vol. 4, No. 3, 1968, (kopi pris).

Kursusplan:

Frivillig 3 pkt. skriftlig opgave:

Løbende bemærkninger: