AIXI

AIXI / ˈ aɪ k s i / es un formalismo matemático teórico para la inteligencia artificial general . Combina la inducción de Solomonoff con la teoría de la decisión secuencial . AIXI fue propuesto por primera vez por Marcus Hutter en 2000 ^{[ 1 ]} y varios resultados relacionados con AIXI se demuestran en el libro de Hutter de 2005, Inteligencia Artificial Universal . ^{[ 2 ]}

AIXI es un agente de aprendizaje por refuerzo (RL). Maximiza las recompensas totales esperadas del entorno. Intuitivamente, considera simultáneamente cada hipótesis computable (o entorno). En cada paso de tiempo, examina cada programa posible y evalúa cuántas recompensas genera según la siguiente acción. Las recompensas prometidas se ponderan según la creencia subjetiva de que este programa constituye el entorno real. Esta creencia se calcula a partir de la duración del programa: los programas más largos se consideran menos probables, de acuerdo con la navaja de Occam . A continuación, AIXI selecciona la acción que tiene la mayor recompensa total esperada en la suma ponderada de todos estos programas.

Según Hutter, la palabra "AIXI" puede tener varias interpretaciones. AIXI puede significar IA basada en la distribución de Solomonoff, denotada por${\displaystyle \xi }$(que es la letra griega xi), o por ejemplo puede representar IA "cruzada" (X) con inducción (I). Hay otras interpretaciones. ^{[ 3 ]}

AIXI es un agente de aprendizaje por refuerzo que interactúa con un entorno estocástico, desconocido pero computable.${\displaystyle \mu }$. La interacción se desarrolla en pasos de tiempo, desde${\displaystyle t=1}$a${\displaystyle t=m}$, dónde${\displaystyle m\in \mathbb {N} }$es la vida útil del agente AIXI. En el paso de tiempo t , el agente elige una acción.${\displaystyle a_{t}\in {\mathcal {A}}}$(p. ej., un movimiento de una extremidad) y lo ejecuta en el entorno, y el entorno responde con una "percepción".${\displaystyle e_{t}\in {\mathcal {E}}={\mathcal {O}}\times \mathbb {R} }$, que consiste en una "observación"${\displaystyle o_{t}\in {\mathcal {O}}}$(por ejemplo, una imagen de la cámara) y una recompensa${\displaystyle r_{t}\in \mathbb {R} }$, distribuidos según la probabilidad condicional${\displaystyle \mu (o_{t}r_{t}|a_{1}o_{1}r_{1}...a_{t-1}o_{t-1}r_{t-1}a_{t})}$, dónde${\displaystyle a_{1}o_{1}r_{1}...a_{t-1}o_{t-1}r_{t-1}a_{t}}$es la "historia" de acciones, observaciones y recompensas. El entorno${\displaystyle \mu }$se representa matemáticamente como una distribución de probabilidad sobre "percepciones" (observaciones y recompensas) que dependen del historial completo , por lo que no hay ninguna suposición de Markov (a diferencia de otros algoritmos de aprendizaje por refuerzo). Nótese de nuevo que esta distribución de probabilidad es desconocida para el agente AIXI. Además, nótese de nuevo que${\displaystyle \mu }$es computable, es decir, las observaciones y recompensas recibidas por el agente del entorno.${\displaystyle \mu }$puede ser calculado por algún programa (que se ejecuta en una máquina de Turing ), dadas las acciones pasadas del agente AIXI. ^{[ 4 ]}

El único objetivo del agente AIXI es maximizar${\displaystyle \sum _{t=1}^{m}r_{t}}$, es decir, la suma de las recompensas desde el paso de tiempo 1 hasta m.

El agente AIXI está asociado a una política estocástica.${\displaystyle \pi$ :({\mathcal {A}}\times {\mathcal {E}})^{*}\rightarrow {\mathcal {A}}} , que es la función que utiliza para elegir acciones en cada paso de tiempo, donde${\displaystyle {\mathcal {A}}}$es el espacio de todas las acciones posibles que AIXI puede realizar y${\displaystyle {\mathcal {E}}}$es el espacio de todas las posibles "percepciones" que puede producir el entorno. El entorno (o distribución de probabilidad)${\displaystyle \mu }$También puede considerarse como una política estocástica (que es una función):${\displaystyle \mu$ :({\mathcal {A}}\times {\mathcal {E}})^{*}\times {\mathcal {A}}\rightarrow {\mathcal {E}}} , donde el${\displaystyle *}$es la operación estrella de Kleene .

En general, en el paso de tiempo${\displaystyle t}$(que va de 1 a m), AIXI, habiendo ejecutado previamente acciones${\displaystyle a_{1}\dots a_{t-1}}$(que a menudo se abrevia en la literatura como${\displaystyle a_{<t}}$) y habiendo observado la historia de las percepciones${\displaystyle o_{1}r_{1}...o_{t-1}r_{t-1}}$(que se puede abreviar como${\displaystyle e_{<t}}$), elige y ejecuta en el entorno la acción,${\displaystyle a_{t}}$, definido de la siguiente manera: ^{[ 3 ]}

${\displaystyle a_{t}:=\arg \max _{a_{t}}\sum _{o_{t}r_{t}}\ldots \max _{a_{m}}\sum _{o_{m}r_{m}}[r_{t}+\ldots +r_{m}]\sum _{q:\;U(q,a_{1}\ldots a_{m})=o_{1}r_{1}\ldots o_{m}r_{m}}2^{-{\textrm {length}}(q)}}$

o bien, utilizando paréntesis, para desambiguar las precedencias.

${\displaystyle a_{t}:=\arg \max _{a_{t}}\left(\sum _{o_{t}r_{t}}\ldots \left(\max _{a_{m}}\sum _{o_{m}r_{m}}[r_{t}+\ldots +r_{m}]\left(\sum _{q:\;U(q,a_{1}\ldots a_{m})=o_{1}r_{1}\ldots o_{m}r_{m}}2^{-{\textrm {length}}(q)}\right)\right)\right)}$

Intuitivamente, en la definición anterior, AIXI considera la suma de la recompensa total sobre todos los posibles "futuros" hasta${\displaystyle mt}$pasos de tiempo adelante (es decir, desde${\displaystyle t}$a${\displaystyle m}$), pondera cada uno de ellos según la complejidad de los programas${\displaystyle q}$(es decir, por${\displaystyle 2^{-{\textrm {longitud}}(q)}}$) coherente con el pasado del agente (es decir, las acciones ejecutadas previamente,${\displaystyle a_{<t}}$y recibió percepciones,${\displaystyle e_{<t}}$) que puede generar ese futuro, y luego elige la acción que maximiza las recompensas futuras esperadas. ^{[ 4 ]}

Vamos a desglosar esta definición para intentar comprenderla por completo.

${\displaystyle o_{t}r_{t}}$es la "percepción" (que consiste en la observación)${\displaystyle o_{t}}$y recompensa${\displaystyle r_{t}}$) recibido por el agente AIXI en el paso de tiempo${\displaystyle t}$del entorno (que es desconocido y estocástico). De manera similar,${\displaystyle o_{m}r_{m}}$es la percepción recibida por AIXI en el paso de tiempo${\displaystyle m}$(el último paso de tiempo en el que AIXI está activo).

${\displaystyle r_{t}+\ldots +r_{m}}$es la suma de las recompensas del paso de tiempo${\displaystyle t}$paso de tiempo${\displaystyle m}$Por lo tanto, AIXI necesita mirar hacia el futuro para elegir su acción en el paso de tiempo.${\displaystyle t}$.

${\displaystyle U}$denota una máquina de Turing universal monótona y${\displaystyle q}$abarca todos los programas (deterministas) en la máquina universal.${\displaystyle U}$, que recibe como entrada el programa${\displaystyle q}$y la secuencia de acciones${\displaystyle a_{1}\dots a_{m}}$(es decir, todas las acciones), y produce la secuencia de percepciones${\displaystyle o_{1}r_{1}\ldots o_{m}r_{m}}$La máquina de Turing universal${\displaystyle U}$Se utiliza, por lo tanto, para "simular" o calcular las respuestas o percepciones del entorno, dado el programa.${\displaystyle q}$(que «modela» el entorno) y todas las acciones del agente AIXI: en este sentido, el entorno es «computable» (como se indicó anteriormente). Cabe señalar que, en general, el programa que «modela» el entorno actual y real (donde AIXI necesita actuar) es desconocido porque el entorno actual también lo es.

${\displaystyle {\textrm {longitud}}(q)}$es la duración del programa${\displaystyle q}$(que se codifica como una cadena de bits). Tenga en cuenta que${\displaystyle 2^{-{\textrm {longitud}}(q)}={\frac {1}{2^{{\textrm {longitud}}(q)}}}}$. Por lo tanto, en la definición anterior,${\displaystyle \sum _{q:\;U(q,a_{1}\ldots a_{m})=o_{1}r_{1}\ldots o_{m}r_{m}}2^{-{\textrm {length}}(q)}}$debe interpretarse como una mezcla (en este caso, una suma) sobre todos los entornos computables (que son consistentes con el pasado del agente), cada uno ponderado por su complejidad.${\displaystyle 2^{-{\textrm {longitud}}(q)}}$. Tenga en cuenta que${\displaystyle a_{1}\ldots a_{m}}$también se puede escribir como${\displaystyle a_{1}\ldots a_{t-1}a_{t}\ldots a_{m}}$, y${\displaystyle a_{1}\ldots a_{t-1}=a_{<t}}$es la secuencia de acciones ya ejecutadas en el entorno por el agente AIXI. De manera similar,${\displaystyle o_{1}r_{1}\ldots o_{m}r_{m}=o_{1}r_{1}\ldots o_{t-1}r_{t-1}o_{t}r_{t}\ldots o_{m}r_{m}}$, y${\displaystyle o_{1}r_{1}\ldots o_{t-1}r_{t-1}}$es la secuencia de percepciones producidas por el entorno hasta el momento.

Ahora vamos a juntar todos estos componentes para comprender esta ecuación o definición.

En el instante t, AIXI elige la acción.${\displaystyle a_{t}}$donde la función${\displaystyle \sum _{o_{t}r_{t}}\ldots \max _{a_{m}}\sum _{o_{m}r_{m}}[r_{t}+\ldots +r_{m}]\sum _{q:\;U(q,a_{1}\ldots a_{m})=o_{1}r_{1}\ldots o_{m}r_{m}}2^{-{\textrm {length}}(q)}}$alcanza su máximo.

El rendimiento de AIXI se mide por el número total esperado de recompensas que recibe. Se ha demostrado que AIXI es óptimo de las siguientes maneras. ^{[ 2 ]}

• Optimalidad de Pareto : no existe ningún otro agente que tenga un rendimiento al menos tan bueno como AIXI en todos los entornos, a la vez que tenga un rendimiento estrictamente mejor en al menos un entorno.
• Optimalidad de Pareto equilibrada: similar a la optimización de Pareto, pero considerando una suma ponderada de entornos.
• Autooptimización: una política p se denomina autooptimización para un entorno.${\displaystyle \mu }$si el rendimiento de p se aproxima al máximo teórico para${\displaystyle \mu }$cuando la duración de la vida útil del agente (no el tiempo) tiende a infinito. Para las clases de entorno donde existen políticas autooptimizadas, AIXI es autooptimizable.

Posteriormente, Hutter y Jan Leike demostraron que la optimalidad de Pareto equilibrada es subjetiva y que cualquier política puede considerarse óptima en términos de Pareto, lo que, según ellos, socava todas las afirmaciones previas de optimalidad para AIXI. ^{[ 5 ]}

Sin embargo, AIXI tiene limitaciones. Se restringe a maximizar las recompensas basándose en percepciones en lugar de estados externos. También asume que interactúa con el entorno únicamente a través de canales de acción y percepción, lo que le impide considerar la posibilidad de sufrir daños o modificaciones. En otras palabras, no se considera limitado por el entorno con el que interactúa. Además, asume que el entorno es computable. ^{[ 6 ]}

Al igual que la inducción de Solomonoff , AIXI es incomputable . Sin embargo, existen aproximaciones computables. Una de ellas es AIXI tl , que se desempeña al menos tan bien como el agente con limitaciones de tiempo t y espacio l , demostrablemente el mejor . ^{[ 2 ]} Otra aproximación a AIXI con una clase de entorno restringida es MC-AIXI (FAC-CTW) (que significa Monte Carlo AIXI FAC- Context-Tree Weighting ), que ha tenido cierto éxito jugando juegos simples como Pac-Man parcialmente observable . ^{[ 4 ] [ 7 ]}

• Máquina Gödel

• «Inteligencia algorítmica universal: un enfoque matemático descendente», Marcus Hutter, arXiv : cs/0701125 ; también en Inteligencia artificial general , eds. B. Goertzel y C. Pennachin, Springer, 2007, ISBN 9783540237334, págs.  227–290, doi : 10.1007/978-3-540-68677-4_8 .