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 previa a una observación dada. Fue inventada por Ray Solomonoff en la década de 1960. [2] Se utiliza en la teoría de la inferencia inductiva y en los análisis de algoritmos. En su teoría general de la inferencia inductiva , Solomonoff utiliza el método junto con la regla de Bayes para obtener probabilidades de predicción para los resultados futuros de un algoritmo. [3]
En el formalismo matemático utilizado, las observaciones tienen la forma de cadenas binarias finitas vistas como salidas de máquinas de Turing , y el prior universal es una distribución de probabilidad sobre el conjunto de cadenas binarias finitas calculadas a partir de una distribución de probabilidad sobre programas (es decir, entradas a una máquina de Turing universal ). El prior es universal en el sentido de computabilidad de Turing, es decir, ninguna cadena tiene probabilidad cero. No es computable, pero se puede aproximar. [4]
Formalmente, la probabilidad no es una probabilidad y no es computable. Es solo "semi-computable inferior" y una "semi-medida". Por "semi-medida", significa que . Es decir, la "probabilidad" en realidad no suma uno, a diferencia de las probabilidades reales. Esto se debe a que algunas entradas a 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 "semi-computable inferior", significa que hay una máquina de Turing que, dada una cadena de entrada , puede imprimir una secuencia que converge a desde abajo, pero no existe una máquina de Turing que haga lo mismo desde arriba.
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 utilizarla para el aprendizaje automático; dada una secuencia de símbolos, ¿cuál vendrá a continuación? La teoría de Solomonoff proporciona una respuesta que es óptima en cierto sentido, aunque es incomputable. A diferencia, por ejemplo, de la teoría de inferencia inductiva informal de Karl Popper , [ aclaración necesaria ] la de Solomonoff es matemáticamente rigurosa.
Las cuatro inspiraciones principales para la probabilidad algorítmica de Solomonoff fueron: la navaja de Occam , el principio de explicaciones múltiples de Epicuro , la teoría informática moderna (por ejemplo, el uso de una máquina de Turing universal) y la regla de Bayes para la predicción. [5]
La navaja de Occam y el principio de Epicuro son esencialmente dos aproximaciones no matemáticas diferentes del principio universal.
En el corazón del prior universal hay un modelo abstracto de una computadora, como una máquina de Turing universal. [8] Cualquier computadora abstracta servirá, siempre que sea Turing-completa, es decir, cada función computable tiene al menos un programa que calculará su aplicación en la computadora abstracta.
El término "computadora abstracta" se utiliza para dar un significado preciso a la frase "explicación simple". En el formalismo utilizado, las explicaciones, o teorías de los fenómenos, son programas informáticos que generan cadenas de observaciones cuando se ejecutan en la computadora abstracta. A cada programa informático se le asigna un peso correspondiente a su longitud. La distribución de probabilidad universal es la distribución de probabilidad en 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 comienza con q . [9] Por lo tanto, una explicación simple es un programa informático corto. Una explicación compleja es un programa informático largo. Las explicaciones simples son más probables, por lo que una cadena de observaciones de alta probabilidad es una generada por un programa informático corto, o tal vez por cualquiera de un gran número de programas informáticos ligeramente más largos. Una cadena de observaciones de baja probabilidad es una que solo puede generarse mediante un programa informático largo.
La probabilidad algorítmica está estrechamente relacionada con el concepto de complejidad de Kolmogorov . La introducción de la complejidad por parte de Kolmogorov estuvo 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: el razonamiento inductivo. Solomonoff inventó una única probabilidad previa universal que puede sustituirse por cada probabilidad previa real en la regla de Bayes con la complejidad de Kolmogorov como producto secundario. [10] Predice la continuación más probable de esa observación y proporciona una medida de cuán probable será esta continuación. [ cita requerida ]
La medida enumerable de Solomonoff es universal en cierto sentido poderoso, pero el tiempo de cálculo puede ser infinito. Una forma de abordar este problema es una variante del algoritmo de búsqueda de Leonid Levin [11] , que limita el tiempo empleado en calcular el éxito de los programas posibles, y a los programas más cortos se les da más tiempo. Cuando se ejecuta durante períodos de tiempo cada vez más largos, generará una secuencia de aproximaciones que convergen a la distribución de probabilidad universal. Otros métodos para abordar el problema incluyen limitar el espacio de búsqueda mediante la inclusión de secuencias de entrenamiento.
Solomonoff demostró que esta distribución es invariante respecto de la máquina dentro de un factor constante (llamado teorema de invariancia ). [12]
El teorema de invariancia de Kolmogorov aclara que la complejidad de Kolmogorov, o longitud de descripción mínima , de un conjunto de datos es invariante a la elección del lenguaje Turing-completo utilizado para simular una máquina de Turing universal:
dónde .
La descripción mínima tal que sirve como una representación natural de la cadena relativa al lenguaje Turing-Completo . Además, como no se puede comprimir más, es una cadena incompresible y, por lo tanto, incomputable. Esto corresponde a la noción científica de aleatoriedad y aclara la razón por la que la complejidad de Kolmogorov no es computable.
De ello se deduce que cualquier dato tiene una representación necesaria y suficiente en términos de una cadena aleatoria.
Lo siguiente está tomado de [13]
A partir de la teoría de compiladores, se sabe que para cualesquiera dos lenguajes Turing-Completos y , existe un compilador expresado en que traduce programas expresados en en programas funcionalmente equivalentes expresados en .
De ello se deduce que si dejamos que sea el programa más corto que imprime una cadena dada entonces:
donde , y por simetría obtenemos la desigualdad opuesta.
Dado que cualquier código decodificable de forma única satisface la desigualdad de Kraft-McMillan, la complejidad de Kolmogorov sin prefijo nos permite derivar la distribución universal:
donde el hecho de que pueda simular un UTM sin prefijo implica que para dos descripciones distintas y , no es una subcadena de y no es una subcadena de .
En un Universo Computable, dado un fenómeno con codificación generada por un proceso físico, la probabilidad de ese fenómeno está bien definida y es igual a la suma de las probabilidades de causas distintas e independientes. El criterio de ausencia de prefijos es precisamente lo que garantiza la independencia causal.
Esta es una consecuencia inmediata de la desigualdad de Kraft-McMillan .
La desigualdad de Kraft establece que dada una secuencia de cadenas existe un código de prefijo con palabras de código donde si y solo si:
¿Dónde está el tamaño del alfabeto ?
Sin pérdida de generalidad, supongamos que podemos ordenar de tal manera que:
Ahora bien, existe un código de prefijo si y solo si en cada paso hay al menos una palabra de código para elegir que no contenga ninguna de las palabras de código anteriores como prefijo. Debido a la existencia de una palabra de código en un paso anterior, las palabras de código están prohibidas ya que contienen como prefijo. De ello se deduce que, en general, existe un código de prefijo si y solo si:
Dividiendo ambos lados por , encontramos:
QED.
Solomonoff inventó el concepto de probabilidad algorítmica con su teorema de invariancia asociado alrededor de 1960 [14] , publicando un informe al respecto: "Un informe preliminar sobre una teoría general de la inferencia inductiva". [15] Aclaró estas ideas más completamente en 1964 con "Una teoría formal de la inferencia inductiva", Parte I [16] y Parte II. [17]