Probabilitat algorísmica

En la teoria de la informació algorísmica, la probabilitat algorísmica, també coneguda com a probabilitat de Solomonoff, és un mètode matemàtic per assignar una probabilitat prèvia a una observació determinada. Va ser inventat per Ray Solomonoff a la dècada de 1960. S'utilitza en teoria d'inferència inductiva i anàlisis d'algorismes. En la seva teoria general de la inferència inductiva, Solomonoff utilitza el mètode juntament amb la regla de Bayes per obtenir probabilitats de predicció per a les sortides futures d'un algorisme.

Des dels estats d'observador fins a la física mitjançant la probabilitat algorísmica.

En el formalisme matemàtic utilitzat, les observacions tenen la forma de cadenes binàries finites vistes com a sortides de les màquines de Turing, i el prior universal és una distribució de probabilitat sobre el conjunt de cadenes binàries finites calculades a partir d'una distribució de probabilitat sobre programes (és a dir, entrades a una màquina de Turing universal). El prior és universal en el sentit de la computabilitat de Turing, és a dir, cap cadena té probabilitat zero. No és computable, però es pot aproximar.

Formalment, la probabilitat $P$ no és una probabilitat i no és computable. Només és "semicomputable inferior" i una "semi-mesura". Per "semi-mesura", vol dir que $0<\sum _{x}P(x)<1$. És a dir, la "probabilitat" en realitat no suma un, a diferència de les probabilitats reals. Això es deu al fet que algunes entrades a la màquina de Turing fan que no s'aturi mai, el que significa que es perd la massa de probabilitat assignada a aquestes entrades. Per "semicomputable inferior", vol dir que hi ha una màquina de Turing que, donada una cadena d'entrada $x$, pot imprimir una seqüència $y_{1}<y_{2}<\cdots$ que convergeix a $P(x)$ des de baix, però no hi ha cap màquina de Turing que faci el mateix des de dalt.

Solomonoff va inventar el concepte de probabilitat algorísmica amb el seu teorema d'invariància associat al voltant de 1960, publicant un informe sobre ell: "A Preliminary Report on a General Theory of Inductive Inference". Va aclarir aquestes idees més completament el 1964 amb "A Formal Theory of Inductive Inference", Part I i Part II.

Visió general

La probabilitat algorísmica és l'ingredient principal de la teoria de la inferència inductiva de Solomonoff, la teoria de la predicció basada en observacions; es va inventar amb l'objectiu d'utilitzar-lo per a l'aprenentatge automàtic; donada una seqüència de símbols, quin serà el següent? La teoria de Solomonoff proporciona una resposta òptima en cert sentit, tot i que és incomputable. A diferència, per exemple, de la teoria de la inferència inductiva informal de Karl Popper.

Quatre inspiracions principals per a la probabilitat algorísmica de Solomonoff van ser: la navalla d'Occam, el principi d'explicacions múltiples d'Epicur, la teoria informàtica moderna (per exemple, l'ús d'una màquina de Turing universal) i la regla de Bayes per a la predicció.

La probabilitat algorísmica està estretament relacionada amb el concepte de complexitat de Kolmogorov. La introducció de la complexitat per part de Kolmogorov va ser motivada per la teoria de la informació i els problemes de l'aleatorietat, mentre que Solomonoff va introduir la complexitat algorísmica per una raó diferent: el raonament inductiu. Solomonoff va inventar una única probabilitat a priori universal que es pot substituir per cada probabilitat a priori real de la regla de Bayes amb la complexitat de Kolmogorov com a producte secundari. Preveu la continuació més probable d'aquesta observació i proporciona una mesura de la probabilitat que serà aquesta continuació.

La mesura enumerable de Solomonoff és universal en un cert sentit poderós, però el temps de càlcul pot ser infinit. Una manera d'afrontar aquest problema és una variant de l'algorisme de cerca de Leonid Levin, que limita el temps dedicat a calcular l'èxit de possibles programes, amb programes més curts i més temps. Quan s'executa durant períodes de temps cada cop més llargs, generarà una seqüència d'aproximacions que convergeixen a la distribució de probabilitat universal. Altres mètodes per tractar el problema inclouen limitar l'espai de cerca mitjançant la inclusió de seqüències d'entrenament.