Probabilidad algorítmica - Enciclopedia

En la teoría de la información algorítmica, la probabilidad algorítmica, también conocida como probabilidad de Solomonoff, es un método matemático para asignar una probabilidad a priori a una observación dada. Fue inventada por Ray Solomonoff en la década de 1960.
Se utiliza en la teoría de inferencia inductiva y en el análisis de algoritmos. En su teoría general de inferencia inductiva, Solomonoff utiliza el método junto con la regla de Bayes para obtener probabilidades de predicción para las salidas futuras de un algoritmo.

En la formalización matemática utilizada, las observaciones tienen la forma de cadenas binarias finitas vistas como salidas de las máquinas de Turing, y la prioridad universal es una distribución de probabilidad sobre el conjunto de cadenas binarias finitas calculada a partir de una distribución de probabilidad sobre los programas (es decir, las entradas de una máquina de Turing universal). La prioridad es universal en el sentido de Turing-computabilidad, es decir, ninguna cadena tiene probabilidad cero. No es computable, pero puede ser aproximada.

Formalmente, la probabilidad



P


{\displaystyle P}

no es una probabilidad y no es computable. Es solo "semicomputable" y una "semimesura". Por "semimesura", se significa que



0
≤

∑

x


P
(
x
)
<
1


{\displaystyle 0\leq \sum _{x}P(x)<1}

. Esto es, la "probabilidad" no suma realmente uno, a diferencia de las probabilidades reales. Esto se debe a que algunas entradas de la máquina de Turing hacen que nunca se detenga, lo que significa que la masa de probabilidad asignada a esas entradas se pierde. Por "semicomputable", se significa que hay una máquina de Turing que, dada una cadena de entrada



x


{\displaystyle x}

, puede imprimir una secuencia




y

1


<

y

2


<
⋯


{\displaystyle y_{1}<y_{2}<\cdots }

que converge a



P
(
x
)


{\displaystyle P(x)}

desde abajo, pero no hay tal máquina de Turing que lo haga desde arriba.

Resumen
La probabilidad algorítmica es el ingrediente principal de la teoría de inferencia inductiva de Solomonoff, la teoría de predicción basada en observaciones; fue inventada con el objetivo de usarla para el aprendizaje automático; dada una secuencia de símbolos, ¿cuál vendrá después? La teoría de Solomonoff proporciona una respuesta que es óptima en ciertos sentidos, aunque es incomputable.

Las cuatro principales inspiraciones para la probabilidad algorítmica de Solomonoff fueron: la navaja de Ockham, el principio de múltiples explicaciones de Epicuro, la teoría moderna de la computación (por ejemplo, el uso de una máquina de Turing universal) y la regla de Bayes para la predicción.

La navaja de Ockham y el principio de múltiples explicaciones de Epicuro son esencialmente dos aproximaciones no matemáticas diferentes de la prioridad universal.

La navaja de Ockham: entre las teorías que son consistentes con los fenómenos observados, se debe seleccionar la más sencilla.

El principio de múltiples explicaciones de Epicuro: si más de una teoría es consistente con las observaciones, se deben mantener todas esas teorías.

En el corazón de la prioridad universal hay un modelo abstracto de una computadora, como una máquina de Turing universal. Cualquier computadora abstracta servirá, siempre y cuando sea Turing-completa, es decir, cada función computable tiene al menos un programa que calculará su aplicación en la computadora abstracta.

El computador abstracto se utiliza para dar un significado preciso a la frase "explicación sencilla". En la formalización utilizada, las explicaciones o teorías de los fenómenos son programas de computadora que generan cadenas de observación cuando se ejecutan en el computador abstracto. Cada programa de computadora se asigna un peso correspondiente a su longitud. La distribución de probabilidad universal es la distribución de probabilidad sobre todas las posibles cadenas de salida con entrada aleatoria, asignando para cada prefijo de salida finito q la suma de las probabilidades de los programas que calculan algo que comience con q. Por lo tanto, una explicación sencilla es un programa de computadora corto. Una explicación compleja es un programa de computadora largo. Las explicaciones sencillas son más probables, por lo que una cadena de observación de alta probabilidad es una generada por un programa de computadora corto, o tal vez por cualquier número grande de programas de computadora ligeramente más largos. Una cadena de observación de baja probabilidad es una que solo se puede generar por un programa de computadora largo.

La probabilidad algorítmica está estrechamente relacionada con el concepto de complejidad de Kolmogorov. La introducción de la complejidad de Kolmogorov fue motivada por la teoría de la información y los problemas de aleatoriedad, mientras que Solomonoff introdujo la complejidad algorítmica por una razón diferente: la razón inductiva. Solomonoff inventó una única medida enumerable universal que puede sustituir a cada probabilidad a priori real en la regla de Bayes como subproducto. Predice la continuación más probable de esa observación y proporciona una medida de cuán probable será esta continuación.

La medida enumerable de Solomonoff es universal en un sentido poderoso, pero el tiempo de cómputo puede ser infinito. Una manera de manejar este problema es una variante del Algoritmo de Búsqueda de Leonid Levin, que limita el tiempo dedicado a calcular el éxito de posibles programas, dándoles más tiempo a los programas más cortos. A medida que se ejecuta durante periodos de tiempo más largos y más largos, generará una secuencia de aproximaciones que convergen a la distribución de probabilidad universal. Otras formas de manejar el problema incluyen limitar el espacio de búsqueda mediante la inclusión de secuencias de entrenamiento.

Solomonoff probó que esta distribución es invariante en términos de máquina dentro de un factor constante (llamado teorema de invarianza).

Teoremas Fundamentales


= I. Teorema de Invarianza de Kolmogorov =
El teorema de invarianza de Kolmogorov aclara que la complejidad de Kolmogorov, o longitud mínima de descripción, de un conjunto de datos es invariante al elegir el lenguaje Turing-completo utilizado para simular una máquina de Turing universal:




∀
x
∈
{
0
,
1

}

∗


,

|


K

U


(
x
)
−

K


U
′



(
x
)

|

≤


O


(
1
)


{\displaystyle \forall x\in \{0,1\}^{*},|K_{U}(x)-K_{U'}(x)|\leq {\mathcal {O}}(1)}


donde




K

U


(
x
)
=

min

p


{

|

p

|

:
U
(
p
)
=
x
}


{\displaystyle K_{U}(x)=\min _{p}\{|p|:U(p)=x\}}

.


= Interpretación =
La descripción mínima


p


{\displaystyle p}

tal que


U
(
p
)
=
x


{\displaystyle U(p)=x}

actúa como una representación natural de la cadena


x


{\displaystyle x}

con respecto al lenguaje Turing-completo


U


{\displaystyle U}

. Además, como


x


{\displaystyle x}

no puede ser comprimida más,


p


{\displaystyle p}

es una cadena incompresible y, por lo tanto, incomputable. Esto corresponde a la noción de los científicos de la aleatoriedad y aclara por qué la complejidad de Kolmogorov no es computable.

Sigue que cualquier fragmento de datos tiene una representación necesaria y suficiente en términos de una cadena aleatoria.


= Prueba =
Lo siguiente se toma de

Desde la teoría de los compiladores, se sabe que para cualquier dos lenguajes Turing-completos


U
1




{\displaystyle U_{1}}

y


U
2




{\displaystyle U_{2}}

, existe un compilador


Λ
1




{\displaystyle \Lambda _{1}}

expresado en


U
1




{\displaystyle U_{1}}

que traduce programas expresados en


U
2




{\displaystyle U_{2}}

en programas funcionalmente equivalentes expresados en


U
1




{\displaystyle U_{1}}

.
Por lo tanto, si tomamos


p


{\displaystyle p}

como el programa más corto que imprime una cadena dada


x


{\displaystyle x}

entonces:


K
U
1


(
x
)
≤

|

Λ
1


|

+

|

p

|

≤
K
U
2


(
x
)
+

O


(
1
)


{\displaystyle K_{U_{1}}(x)\leq |\Lambda _{1}|+|p|\leq K_{U_{2}}(x)+{\mathcal {O}}(1)}


donde


|

Λ
1


|

=

O


(
1
)


{\displaystyle |\Lambda _{1}|={\mathcal {O}}(1)}

, y por simetría obtenemos la desigualdad opuesta.


= II. Distribución Universal de Levin =
Dado que cualquier código únicamente decodificable satisface la desigualdad de Kraft-McMillan, la complejidad de Kolmogorov prefix-free permite derivar la distribución universal:




P
(
x
)
=

∑

U
(
p
)
=
x


P
(
U
(
p
)
=
x
)
=

∑

U
(
p
)
=
x



2

−

K

U


(
p
)


≤
1


{\displaystyle P(x)=\sum _{U(p)=x}P(U(p)=x)=\sum _{U(p)=x}2^{-K_{U}(p)}\leq 1}


donde el hecho de que


U


{\displaystyle U}

puede simular una máquina de Turing prefix-free implica que para dos descripciones


p


{\displaystyle p}

y



p
′



{\displaystyle p'}

diferentes,


p


{\displaystyle p}

no es una subcadena de


p
′



{\displaystyle p'}

y


p
′



{\displaystyle p'}

no es una subcadena de


p


{\displaystyle p}

.


= Interpretación =
En un universo computable, dado un fenómeno con codificación


x
∈
{
0
,
1

}

∗




{\displaystyle x\in \{0,1\}^{*}}

generado por un proceso físico, la probabilidad de ese fenómeno está bien definida y es igual a la suma sobre las probabilidades de causas independientes y diferentes. El criterio prefix-free garantiza la independencia causal.


= Prueba =
Esto es una consecuencia inmediata de la desigualdad de Kraft-McMillan.

La desigualdad de Kraft establece que, dada una secuencia de cadenas


{

x

i



}

i
=
1


n




{\displaystyle \{x_{i}\}_{i=1}^{n}}

hay un código de prefijo con códigos


{

σ

i



}

i
=
1


n




{\displaystyle \{\sigma _{i}\}_{i=1}^{n}}

donde


∀
i
,

|

σ
i


|

=

k
i




{\displaystyle \forall i,|\sigma _{i}|=k_{i}}

si y solo si: