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 de asignar una probabilidad previa a una observación determinada. Fue inventado por Ray Solomonoff en la década de 1960. [1] Se utiliza en teoría de inferencia inductiva y análisis de algoritmos. En su teoría general de la inferencia inductiva , Solomonoff utiliza la [ aclaración necesaria ] previa obtenida por esta fórmula [ ¿cuál? ] , en la regla de Bayes para la predicción [se necesita un ejemplo ][ se necesita más explicación ] . [2]
En el formalismo matemático utilizado, las observaciones tienen la forma de cadenas binarias finitas, y el prior universal es una distribución de probabilidad sobre el conjunto de cadenas binarias finitas [ cita requerida ] . Lo anterior es universal en el sentido de la computabilidad de Turing, es decir, ninguna cadena tiene probabilidad cero. No es computable, pero se puede aproximar. [3]
Descripción general
La probabilidad algorítmica se ocupa de las siguientes preguntas: [ cita requerida ] Dado un conjunto de datos sobre algún fenómeno que queremos comprender, ¿cómo podemos seleccionar la hipótesis más probable de cómo fue causado entre todas las hipótesis posibles y cómo podemos evaluar la diferentes hipótesis? ¿Cómo podemos predecir datos futuros y cómo podemos medir la probabilidad de que esa predicción sea la correcta?
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. [4]
La navaja de Occam y el principio de Epicuro son esencialmente dos aproximaciones no matemáticas diferentes del prior universal . [ cita requerida ]
- Navaja de Occam: entre las teorías que son consistentes con los fenómenos observados, se debe seleccionar la teoría más simple . [5]
- El principio de explicaciones múltiples de Epicuro: si más de una teoría es consistente con las observaciones, conserve todas esas teorías . [6]
En el corazón del prior universal hay un modelo abstracto de una computadora, como una máquina de Turing universal . [7] Cualquier computadora abstracta servirá, siempre que sea Turing-completa, es decir, cada cadena binaria finita tiene al menos un programa que la calculará en la computadora abstracta.
La computadora abstracta se utiliza para dar un significado preciso a la frase "explicación simple" [ cita requerida ] . En el formalismo utilizado, las explicaciones o teorías de los fenómenos son programas de computadora que generan cadenas de observación cuando se ejecutan en la computadora abstracta. [ cita requerida ] Una explicación simple es un programa de computadora corto. Una explicación compleja es un largo programa de computadora. [ cita requerida ] Las explicaciones simples 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 quizás por cualquiera de una gran cantidad de programas de computadora un poco más largos. Una cadena de observación de baja probabilidad es aquella que solo puede ser generada por un programa de computadora largo [ cita requerida ] .
Estas ideas pueden hacerse específicas [se necesita un ejemplo ] y las probabilidades pueden usarse para construir una distribución de probabilidad previa para la observación dada. [ cita requerida ] La razón principal de Solomonoff para inventar este a priori es para que se pueda usar en la regla de Bayes cuando se desconoce el a priori real, lo que permite la predicción bajo incertidumbre. [ cita requerida ] Predice la continuación más probable de esa observación y proporciona una medida de qué tan probable será esta continuación. [ cita requerida ]
Aunque la probabilidad universal de una observación (y su extensión) es incomputable, existe un algoritmo informático, Levin Search, [8] que, cuando se ejecuta durante períodos de tiempo cada vez más largos, generará una secuencia de aproximaciones que convergen a la universal. distribución de probabilidad . [ cita requerida ]
Solomonoff demostró que esta distribución es invariante de la máquina dentro de un factor constante (llamado teorema de invariancia ). [9]
Solomonoff inventó el concepto de probabilidad algorítmica con su teorema de invariancia asociado alrededor de 1960, [10] publicando un informe al respecto: "Un informe preliminar sobre una teoría general de la inferencia inductiva". [11] Aclaró estas ideas más completamente en 1964 con "Una teoría formal de la inferencia inductiva", Parte I [12] y Parte II. [13]
Más discusión
Solomonoff describió una computadora universal con un programa de entrada generado aleatoriamente. El programa calcula una salida posiblemente infinita. La distribución de probabilidad universal es la distribución de probabilidad en todas las cadenas de salida posibles con entrada aleatoria. [14]
La probabilidad algorítmica de cualquier prefijo de salida finito dado q es la suma de las probabilidades de los programas que calculan algo que comienza con q . Ciertos objetos largos con programas cortos tienen una alta probabilidad.
La probabilidad algorítmica es el ingrediente principal de la teoría de la inferencia inductiva de Solomonoff , la teoría de la predicción basada en observaciones; fue inventado con el objetivo de usarlo 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 cierto sentido, aunque es incomputable. A diferencia, por ejemplo, de la teoría de la inferencia inductiva informal de Karl Popper , [se necesita aclaración ] la de Solomonoff es matemáticamente rigurosa.
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: el razonamiento inductivo. Solomonoff inventó una única probabilidad a priori universal que puede ser sustituida por cada probabilidad a priori real en la regla de Bayes con la complejidad de Kolmogorov como un producto secundario. [15]
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, [16] que limita el tiempo dedicado a calcular el éxito de los posibles programas, con programas más cortos con más tiempo. Otros métodos para limitar el espacio de búsqueda incluyen secuencias de entrenamiento.
Gente clave
Ver también
Referencias
- ^ Solomonoff, R., " Un informe preliminar sobre una teoría general de la inferencia inductiva ", Informe V-131, Zator Co., Cambridge, Ma. (Revisión de noviembre de 1960 del informe del 4 de febrero de 1960).
- ^ Li, M. y Vitanyi, P., Introducción a la complejidad de Kolmogorov y sus aplicaciones , tercera edición, Springer Science and Business Media, NY, 2008
- ^ Hutter, M., Legg, S. y Vitanyi, P., "Probabilidad algorítmica" , Scholarpedia, 2 (8): 2572, 2007.
- ^ Li y Vitanyi, 2008, p. 347
- ^ Li y Vitanyi, 2008, p. 341
- ^ Li y Vitanyi, 2008, p. 339.
- ^ Hutter, M., "Teoría algorítmica de la información" , Scholarpedia, 2 (3): 2519.
- ^ Levin, LA, "Universal Search Problems", en Problemy Peredaci Informacii 9, págs. 115-116, 1973
- ^ Solomonoff, R., " Sistemas de inducción basados en la complejidad: comparaciones y teoremas de convergencia ", IEEE Trans. sobre teoría de la información, vol. IT-24, núm. 4, págs. 422-432, julio de 1978
- ^ Solomonoff, R., "El descubrimiento de la probabilidad algorítmica" , Revista de Ciencias de la Computación y Sistemas , Vol. 55, núm. 1, págs. 73-88, agosto de 1997.
- ^ Solomonoff, R., " Un informe preliminar sobre una teoría general de la inferencia inductiva ", Informe V-131, Zator Co., Cambridge, Ma. (Revisión de noviembre de 1960 del informe del 4 de febrero de 1960).
- ^ Solomonoff, R., " Una teoría formal de la inferencia inductiva, parte I ". Information and Control , Vol 7, No. 1 pp 1-22, marzo de 1964.
- ^ Solomonoff, R., " Una teoría formal de la inferencia inductiva, Parte II " Información y control , Vol 7, No. 2 pp 224-254, junio de 1964.
- ^ Solomonoff, R., " The Kolmogorov Lecture: The Universal Distribution and Machine Learning " The Computer Journal , Vol 46, No. 6 p 598, 2003.
- ^ Gács, P. y Vitányi, P., "In Memoriam Raymond J. Solomonoff", IEEE Information Theory Society Newsletter , vol. 61, No. 1, marzo de 2011, pág.11.
- ^ Levin, LA, "Universal Search Problems", en Problemy Peredaci Informacii 9, págs. 115-116, 1973
Fuentes
- Li, M. y Vitanyi, P., Introducción a la complejidad de Kolmogorov y sus aplicaciones , tercera edición, Springer Science and Business Media, NY, 2008
Otras lecturas
- Rathmanner, S y Hutter, M., " Un tratado filosófico de inducción universal " en Entropy 2011, 13, 1076-1136: Un análisis filosófico y matemático muy claro de la teoría de la inferencia inductiva de Solomonoff
enlaces externos
- Probabilidad algorítmica en Scholarpedia
- Publicaciones de Solomonoff