Probabilidad algorítmica

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\}}$.

La descripción mínima${\displaystyle p}$de tal manera que${\displaystyle U(p)=x}$sirve como una representación natural de la cuerda${\displaystyle x}$en relación con el lenguaje Turing-completo${\displaystyle U}$Además, como${\displaystyle x}$no se puede comprimir más${\displaystyle p}$es una cadena incompresible y, por lo tanto, incomputable. Esto se corresponde con 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 se ha tomado de ^{[ 13 ]}

De la teoría de compiladores, se sabe que para cualesquiera dos lenguajes Turing-completos${\displaystyle U_{1}}$y${\displaystyle U_{2}}$, existe un compilador${\displaystyle \Lambda _{1}}$expresado en ${\displaystyle U_{1}}$que traduce programas expresados ​​en${\displaystyle U_{2}}$en programas funcionalmente equivalentes expresados ​​en${\displaystyle U_{1}}$.

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

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

dónde${\displaystyle |\Lambda _{1}|={\mathcal {O}}(1)}$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 prefijos 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${\displaystyle U}$puede simular una UTM sin prefijo implica que para dos descripciones distintas${\displaystyle p}$y${\displaystyle p'}$,${\displaystyle p}$no es una subcadena de${\displaystyle p'}$y${\displaystyle p'}$no es una subcadena de${\displaystyle p}$.

En un Universo Computable, dado un fenómeno con codificación${\displaystyle x\in \{0,1\}^{*}}$Si un fenómeno es generado por un proceso físico, su probabilidad está bien definida y es igual a la suma de las probabilidades de causas distintas e independientes. El criterio sin 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${\displaystyle \{x_{i}\}_{i=1}^{n}}$Existe un código de prefijo con palabras clave.${\displaystyle \{\sigma _{i}\}_{i=1}^{n}}$dónde${\displaystyle \forall i,|\sigma _{i}|=k_{i}}$si y solo si :

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

dónde${\displaystyle s}$es el tamaño del alfabeto${\displaystyle S}$.

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

${\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${\displaystyle j}$Hay al menos una palabra clave para elegir que no contiene ninguna de las anteriores.${\displaystyle j-1}$palabras clave como prefijo. Debido a la existencia de una palabra clave en un paso anterior.${\displaystyle i<j,s^{k_{j}-k_{i}}}$Las palabras clave están prohibidas ya que contienen${\displaystyle \sigma _{i}}$como prefijo. De ello se deduce que, en general, existe un código de prefijo si y solo si:

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

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

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

QED.

El razonamiento inductivo, el proceso de predecir eventos futuros a partir de observaciones pasadas, es fundamental para el comportamiento inteligente. Hutter formalizó este proceso utilizando la navaja de Occam y la probabilidad algorítmica. El marco se basa en la complejidad de Kolmogorov, que mide la simplicidad de los datos mediante la longitud de su programa descriptivo más corto. Este concepto sustenta la distribución universal MM, introducida por Ray Solomonoff, que asigna mayores probabilidades a las hipótesis más simples. Hutter extendió la distribución universal para incluir acciones, creando un marco capaz de abordar problemas como la predicción, la optimización y el aprendizaje por refuerzo en entornos con estructuras desconocidas.

El modelo AIXI es la pieza central de la teoría de Hutter. Describe un agente artificial universal diseñado para maximizar las recompensas esperadas en un entorno desconocido. AIXI opera bajo el supuesto de que el entorno puede representarse mediante una distribución de probabilidad computable. Utiliza observaciones pasadas para inferir el modelo ambiental más probable, aprovechando la probabilidad algorítmica. Matemáticamente, AIXI evalúa todas las posibles secuencias futuras de acciones y observaciones. Calcula sus probabilidades algorítmicas y utilidades esperadas, seleccionando la secuencia de acciones que maximiza las recompensas acumuladas. Este enfoque transforma la toma de decisiones secuenciales en un problema de optimización. Sin embargo, la formulación general de AIXI es incomputable, lo que la hace poco práctica para su implementación directa.

AIXI es universalmente óptimo en el sentido de que su rendimiento es igual o superior al de cualquier otro agente en todos los entornos computables. Esta universalidad lo convierte en un referente teórico para la inteligencia. Sin embargo, su dependencia de la probabilidad algorítmica lo hace computacionalmente inviable, requiriendo un tiempo exponencial para evaluar todas las posibilidades. Para abordar esta limitación, Hutter propuso aproximaciones con límite de tiempo, como AIXItl, que reducen las exigencias computacionales a la vez que conservan muchas propiedades teóricas del modelo original. Estas aproximaciones proporcionan un equilibrio más práctico entre la viabilidad computacional y la optimización.

El marco AIXI tiene implicaciones significativas para la inteligencia artificial y campos afines. Proporciona un punto de referencia formal para medir la inteligencia y una base teórica para resolver diversos problemas, como la predicción, el aprendizaje por refuerzo y la optimización. A pesar de sus ventajas, el marco presenta limitaciones. AIXI presupone que el entorno es computable, excluyendo los sistemas caóticos o no computables. Además, sus elevados requisitos computacionales dificultan su aplicación en el mundo real.

La teoría de Hutter plantea interrogantes filosóficos sobre la naturaleza de la inteligencia y la computación. Su dependencia de la probabilidad algorítmica vincula la inteligencia con la capacidad de calcular y predecir, lo que podría excluir ciertos fenómenos naturales o caóticos. No obstante, el modelo AIXI ofrece perspectivas sobre los límites teóricos superiores del comportamiento inteligente y sirve como punto de partida para sistemas de IA más prácticos.