probabilidad algorítmica

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

En la teoría algorítmica de la información , 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 determinada. Fue inventado por Ray Solomonoff en los años 1960. ^[2] Se utiliza en teoría de inferencia inductiva y 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 de 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 las 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 la 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 sólo una "semimedida inferior" y una "semimedida". Por "semimedida" se entiende 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 se pierde la masa de probabilidad asignada a esas entradas. Por "semicomputable inferior", significa que hay una máquina de Turing que, dada una cadena de entrada , puede imprimir una secuencia que converge 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 la inferencia inductiva de Solomonoff, la teoría de la predicción basada en observaciones; fue inventado con el objetivo de utilizarlo para el aprendizaje automático; Dada una secuencia de símbolos, ¿cuál vendrá después? La teoría de Solomonoff proporciona una respuesta óptima en cierto sentido, aunque incomputable. A diferencia, por ejemplo, de la teoría informal de la inferencia inductiva de Karl Popper , ^{[ se necesita aclaración ]} la de Solomonoff es matemáticamente rigurosa.

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 predicción de Bayes. ^[5]

La navaja de Occam y el principio de Epicuro son esencialmente dos aproximaciones no matemáticas diferentes del prior universal.

• La navaja de Occam: entre las teorías que son 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, conserve todas esas teorías . ^[7]

En el corazón del prior universal hay un modelo abstracto de 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.

La 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 de computadora que generan cadenas de observación cuando se ejecutan en una 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 de todas las cadenas de salida posibles 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 breve programa de computadora. Una explicación compleja es un largo programa de computadora. Las explicaciones simples son más probables, por lo que una cadena de observación de alta probabilidad es aquella generada por un programa de computadora corto, o quizás por cualquiera de un gran número de programas de computadora ligeramente más largos. Una cadena de observación de baja probabilidad es aquella que sólo 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 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 probabilidad previa universal única que puede sustituir 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 necesaria ]}

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 dedicado a calcular el éxito de posibles programas, dando más tiempo a los programas más cortos. 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 para 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 mínima de descripción , de un conjunto de datos es invariante con la elección del lenguaje Turing completo utilizado para simular una máquina universal de Turing:

${\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 que sirve como una representación natural de la cadena en relación con el lenguaje Turing-Complete . Además, como no se puede comprimir más, es una cadena incompresible y, por lo tanto, no computable. Esto corresponde a la noción de aleatoriedad de los científicos y aclara la razón por la cual la Complejidad de Kolmogorov no es computable. ${\displaystyle p}$ ${\displaystyle U\circ 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 los compiladores, se sabe que para dos lenguajes Turing-Complete y , existe un compilador expresado en que traduce los programas expresados ​​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 el que imprima una cadena determinada, 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\circ P=x}P(U\circ p=x)=\sum _{U\circ 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 e es igual a la suma de las probabilidades de causas distintas e independientes. El criterio sin prefijo es precisamente el que garantiza la independencia causal. ${\displaystyle x\in \{0,1\}^{*}}$

Prueba

Esta es una consecuencia inmediata de la desigualdad Kraft-McMillan .

La desigualdad de Kraft establece que dada una secuencia de cadenas existe un código de prefijo con palabras clave donde si y sólo 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 tales que: ${\displaystyle k_{i}}$

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

Ahora bien, existe un código de prefijo si y sólo 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 en clave en un paso anterior, las palabras en clave están prohibidas ya que contienen un prefijo. De ello se deduce que, en general, existe un código de prefijo si y sólo 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]

Gente clave

• Ray Solomonoff
• Andréi Kolmogorov
• Leonid Levin

Ver 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 vía la teoría algorítmica de la información. Quantum: la revista abierta de la ciencia cuántica. 06 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 , tercera edición, Springer Science and Business Media, Nueva York, 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 Kolmogorov: la distribución universal y el aprendizaje automático" The Computer Journal , Vol 46, No. 6 p 598, 2003.
10. Gács, P. y Vitányi, P., "In Memoriam Raymond J. Solomonoff", Boletín de la sociedad de teoría de la información del IEEE , vol. 61, núm. 1, marzo de 2011, p. 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. sobre teoría de la información, vol. IT-24, núm. 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", Revista de ciencias de la computación y los sistemas , 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 pp 1-22, marzo de 1964.
17. Solomonoff, R., "Una teoría formal de la inferencia inductiva, parte II" Información y control , volumen 7, núm. 2, páginas 224-254, junio de 1964.

Fuentes

• Li, M. y Vitanyi, P., Introducción a la complejidad de Kolmogorov y sus aplicaciones , tercera edición, Springer Science and Business Media, Nueva York, 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.

Otras lecturas

• Rathmanner, S y Hutter, M., "A Philosophical Treatise of Universal Induction" 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