Algoritmisk sannsynlighet - Algorithmic probability

I algoritmisk informasjonsteori er algoritmisk sannsynlighet , også kjent som Solomonoff-sannsynlighet , en matematisk metode for å tilordne en tidligere sannsynlighet til en gitt observasjon. Det ble oppfunnet av Ray Solomonoff på 1960-tallet. Det brukes i induktiv inferenssteori og analyser av algoritmer. I sin generelle teori om induktiv inferens bruker Solomonoff den tidligere oppnådd med denne formelen, i Bayes regel for prediksjon.

I den anvendte matematiske formalismen har observasjonene form av endelige binære strenger, og den universelle tidligere er en sannsynlighetsfordeling over settet med endelige binære strenger. Den forrige er universell i Turing-beregbarhet, det vil si at ingen streng har null sannsynlighet. Den er ikke beregbar, men den kan tilnærmes.


Oversikt

Algoritmisk sannsynlighet omhandler følgende spørsmål: Gitt en mengde data om et fenomen som vi ønsker å forstå, hvordan kan vi velge den mest sannsynlige hypotesen om hvordan den ble forårsaket av alle mulige hypoteser, og hvordan kan vi evaluere de forskjellige hypotesene? Hvordan kan vi forutsi fremtidige data, og hvordan kan vi måle sannsynligheten for at prediksjonen er den riktige?

Fire viktigste inspirasjoner for Solomonoffs algoritmiske sannsynlighet var: Occams høvel , Epicurus 'prinsipp om flere forklaringer , moderne beregningsteori (f.eks. Bruk av en universal Turing-maskin ) og Bayes' regel for prediksjon.

Occams barberhøvel og Epicurus ’prinsipp er i hovedsak to forskjellige ikke-matematiske tilnærminger av det universelle tidligere .

  • Occams høvel: blant teoriene som stemmer overens med de observerte fenomenene, bør man velge den enkleste teorien .
  • Epicurus 'prinsipp om flere forklaringer: Hvis mer enn en teori er i samsvar med observasjonene, behold alle slike teorier .

I hjertet av universal prior er en abstrakt modell av en datamaskin, for eksempel en universal Turing-maskin . Enhver abstrakt datamaskin vil gjøre det, så lenge den er Turing-komplett, dvs. at hver endelige binære streng har minst ett program som vil beregne det på den abstrakte datamaskinen.

Den abstrakte datamaskinen brukes til å gi nøyaktig mening til uttrykket "enkel forklaring". I den anvendte formalismen er forklaringer eller teorier om fenomener dataprogrammer som genererer observasjonsstrenger når de kjøres på den abstrakte datamaskinen. En enkel forklaring er et kort dataprogram. En kompleks forklaring er et langt dataprogram. Enkle forklaringer er mer sannsynlig, så en observasjonsstreng med høy sannsynlighet er en generert av et kort dataprogram, eller kanskje av et stort antall litt lengre dataprogrammer. En observasjonsstreng med lav sannsynlighet er en som bare kan genereres av et langt dataprogram.

Disse ideene kan gjøres spesifikke og sannsynlighetene som brukes til å konstruere en tidligere sannsynlighetsfordeling for den gitte observasjonen. Solomonoffs viktigste grunn til å oppfinne dette tidligere er slik at det kan brukes etter Bayes regel når den faktiske tidligere er ukjent, noe som muliggjør spådom under usikkerhet. Den spår den mest sannsynlige fortsettelsen av observasjonen, og gir et mål på hvor sannsynlig denne fortsettelsen vil være.

Selv om den universelle sannsynligheten for en observasjon (og dens utvidelse) er uberegnelig, er det en datamaskinalgoritme, Levin Search, som, når den kjøres i lengre og lengre perioder, vil generere en sekvens av tilnærminger som konvergerer til den universelle sannsynlighetsfordelingen .

Solomonoff beviste denne fordelingen som maskininvariant innenfor en konstant faktor (kalt invarianseteoremet ).

Solomonoff oppfant begrepet algoritmisk sannsynlighet med dets tilknyttede invarianseteorem rundt 1960, og publiserte en rapport om det: "En foreløpig rapport om en generell teori om induktiv inferens." Han avklarte disse ideene mer fullstendig i 1964 med "En formell teori om induktiv inferens", del I og del II.

Videre diskusjon

Solomonoff beskrev en universell datamaskin med et tilfeldig generert input-program. Programmet beregner noen mulig uendelig utgang. Den universelle sannsynlighetsfordelingen er sannsynlighetsfordelingen på alle mulige utgangstrenger med tilfeldig inngang.

Den algoritmiske sannsynligheten for et gitt endelig utgangsprefiks q er summen av sannsynlighetene til programmene som beregner noe som starter med q . Visse lange objekter med korte programmer har stor sannsynlighet.

Algoritmisk sannsynlighet er hovedingrediensen i Solomonoffs teori om induktiv inferens , teorien om prediksjon basert på observasjoner; den ble oppfunnet med målet om å bruke den til maskinlæring; gitt en sekvens av symboler, hvilken kommer neste? Solomonoffs teori gir et svar som er optimalt i en viss forstand, selv om det er uberegnelig. I motsetning til for eksempel Karl Poppers uformelle induktive inferenssteori, er Solomonoffs matematisk streng.

Algoritmisk sannsynlighet er nært knyttet til konseptet Kolmogorov-kompleksitet . Kolmogorovs introduksjon av kompleksitet ble motivert av informasjonsteori og problemer i tilfeldighet, mens Solomonoff introduserte algoritmisk kompleksitet av en annen grunn: induktiv resonnement. En enkelt universell tidligere sannsynlighet som kan erstattes for hver faktisk tidligere sannsynlighet i Bayes regel ble oppfunnet av Solomonoff med Kolmogorov-kompleksitet som et biprodukt.

Solomonoffs tallrike mål er universell i en viss kraftfull forstand, men beregningstiden kan være uendelig. En måte å håndtere dette problemet på er en variant av Leonid Levins søkealgoritme, som begrenser tidsbruken til å beregne suksessen til mulige programmer, med kortere programmer som får mer tid. Andre metoder for å begrense søkeområdet inkluderer treningssekvenser.

Nøkkel folk

Se også

referanser

kilder

  • Li, M. og Vitanyi, P., En introduksjon til Kolmogorov-kompleksitet og dens anvendelser , 3. utgave, Springer Science and Business Media, NY, 2008

Videre lesning

Eksterne linker