Probabilidad algorítmica

De los estados de observación a la física a través de la probabilidad algorítmica ^{[ aclaración necesaria ] [1]}

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. ${\displaystyle P}$ ${\displaystyle 0\leq \sum _{x}P(x)<1}$ ${\displaystyle x}$ ${\displaystyle y_{1}<y_{2}<\cdots }$ ${\displaystyle P(x)}$

Descripción general

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.

• La navaja de Occam: entre las teorías que sean consistentes con los fenómenos observados, se debe seleccionar la teoría más simple . ^[6]
• Principio de explicaciones múltiples de Epicuro: si más de una teoría es consistente con las observaciones, mantén todas esas teorías . ^[7]

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]

Teoremas fundamentales

I. Teorema de invariancia de Kolmogorov

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:

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

dónde . ${\displaystyle K_{U}(x)=\min _{p}\{|p|:U(p)=x\}}$

Interpretación

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. ${\displaystyle p}$ ${\displaystyle U(p)=x}$ ${\displaystyle x}$ ${\displaystyle U}$ ${\displaystyle x}$ ${\displaystyle p}$

De ello se deduce que cualquier dato tiene una representación necesaria y suficiente en términos de una cadena aleatoria.

Prueba

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 . ${\displaystyle U_{1}}$ ${\displaystyle U_{2}}$ ${\displaystyle \Lambda _{1}}$ ${\displaystyle U_{1}}$ ${\displaystyle U_{2}}$ ${\displaystyle U_{1}}$

De ello se deduce que si dejamos que sea el programa más corto que imprime una cadena dada entonces: ${\displaystyle p}$ ${\displaystyle x}$

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

donde , y por simetría obtenemos la desigualdad opuesta. ${\displaystyle |\Lambda _{1}|={\mathcal {O}}(1)}$

II. Distribución universal de Levin

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:

${\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 pueda simular un UTM sin prefijo implica que para dos descripciones distintas y , no es una subcadena de y no es una subcadena de . ${\displaystyle U}$ ${\displaystyle p}$ ${\displaystyle p'}$ ${\displaystyle p}$ ${\displaystyle p'}$ ${\displaystyle p'}$ ${\displaystyle p}$

Interpretación

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. ${\displaystyle x\in \{0,1\}^{*}}$

Prueba

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: ${\displaystyle \{x_{i}\}_{i=1}^{n}}$ ${\displaystyle \{\sigma _{i}\}_{i=1}^{n}}$ ${\displaystyle \forall i,|\sigma _{i}|=k_{i}}$

${\displaystyle \sum _{i=1}^{n}s^{-k_{i}}\leq 1}$

¿Dónde está el tamaño del alfabeto ? ${\displaystyle s}$ ${\displaystyle S}$

Sin pérdida de generalidad, supongamos que podemos ordenar de tal manera que: ${\displaystyle k_{i}}$

${\displaystyle k_{1}\leq k_{2}\leq ...\leq k_{n}}$

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: ${\displaystyle j}$ ${\displaystyle j-1}$ ${\displaystyle i<j,s^{k_{j}-k_{i}}}$ ${\displaystyle \sigma _{i}}$

${\displaystyle \forall j\geq 2,s^{k_{j}}>\sum _{i=1}^{j-1}s^{k_{j}-k_{i}}}$

Dividiendo ambos lados por , encontramos: ${\displaystyle s^{k_{j}}}$

${\displaystyle \sum _{i=1}^{n}s^{-k_{i}}\leq 1}$

QED.

Historia

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]

Personas clave

• Ray Solomonoff
• Andrei Kolmogorov
• Leonid Levin

Véase también

• La teoría de la inferencia inductiva de Solomonoff
• Teoría de la información algorítmica
• Inferencia bayesiana
• Inferencia inductiva
• Probabilidad inductiva
• Complejidad de Kolmogorov
• Máquina universal de Turing
• Complejidad basada en la información

Referencias

1. Markus Müller. Ley sin ley: de los estados observadores a la física a través de la teoría de la información algorítmica. Quantum: la revista abierta para la ciencia cuántica. 6 de junio de 2020.
2. 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).
3. Li, M. y Vitanyi, P., Introducción a la complejidad de Kolmogorov y sus aplicaciones , 3.ª edición, Springer Science and Business Media, NY, 2008
4. Hutter, M., Legg, S. y Vitanyi, P., "Probabilidad algorítmica", Scholarpedia, 2(8):2572, 2007.
5. Li y Vitanyi, 2008, pág. 347
6. Li y Vitanyi, 2008, pág. 341
7. Li y Vitanyi, 2008, pág. 339.
8. Hutter, M., "Teoría de la información algorítmica", Scholarpedia, 2(3):2519.
9. Solomonoff, R., "La conferencia de Kolmogorov: la distribución universal y el aprendizaje automático" The Computer Journal , vol. 46, n.º 6, pág. 598, 2003.
10. 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.
11. Levin, LA, "Problemas de búsqueda universal", en Problemy Peredaci Informacii 9, págs. 115-116, 1973
12. Solomonoff, R., "Sistemas de inducción basados ​​en la complejidad: comparaciones y teoremas de convergencia", IEEE Trans. on Information Theory, vol. IT-24, n.º 4, págs. 422-432, julio de 1978
13. Grünwald, P. y Vitany, P. Teoría de la información algorítmica. Arxiv. 2008.
14. Solomonoff, R., "El descubrimiento de la probabilidad algorítmica", Journal of Computer and System Sciences , vol. 55, núm. 1, págs. 73-88, agosto de 1997.
15. 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).
16. Solomonoff, R., "Una teoría formal de la inferencia inductiva, Parte I". Información y control , vol. 7, n.º 1, págs. 1-22, marzo de 1964.
17. Solomonoff, R., "Una teoría formal de la inferencia inductiva, parte II" Información y control , vol. 7, n.º 2, págs. 224-254, junio de 1964.

Fuentes

• Li, M. y Vitanyi, P., Introducción a la complejidad de Kolmogorov y sus aplicaciones , 3.ª edición, Springer Science and Business Media, NY, 2008
• Hutter, Marcus (2005). Inteligencia artificial universal: decisiones secuenciales basadas en probabilidad algorítmica . Textos de informática teórica. Berlín Heidelberg: Springer. ISBN 978-3-540-22139-5.

Lectura adicional

• 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