AIXI

Formalismo matemático para la inteligencia artificial general

AIXI ['ai̯k͡siː] es un formalismo matemático teórico para la inteligencia artificial general . Combina la inducción de Solomonoff con la teoría de decisiones secuenciales . AIXI fue propuesto por primera vez por Marcus Hutter en 2000 ^[1] y varios resultados relacionados con AIXI se prueban en el libro de Hutter de 2005, Universal Artificial Intelligence ^[2] .

AIXI es un agente de aprendizaje por refuerzo (RL). Maximiza las recompensas totales esperadas recibidas del entorno. Intuitivamente, considera simultáneamente cada hipótesis computable (o entorno). En cada paso de tiempo, observa cada programa posible y evalúa cuántas recompensas genera ese programa dependiendo de la siguiente acción realizada. Las recompensas prometidas se ponderan luego 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 recompensa total esperada más alta en la suma ponderada de todos estos programas.

Definición

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

AIXI es un agente de aprendizaje por refuerzo que interactúa con un entorno estocástico y desconocido pero computable . La interacción se produce en pasos de tiempo, desde hasta , donde es la vida útil del agente AIXI. En el paso de tiempo t , el agente elige una acción (por ejemplo, un movimiento de extremidades) y la ejecuta en el entorno, y el entorno responde con un "percepto" , que consiste en una "observación" (por ejemplo, una imagen de cámara) y una recompensa , distribuida de acuerdo con la probabilidad condicional , donde es el "historial" de acciones, observaciones y recompensas. Por tanto, el entorno 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 una suposición de Markov (a diferencia de otros algoritmos de RL). Nótese nuevamente que esta distribución de probabilidad es desconocida para el agente AIXI. Además, observe nuevamente que es computable, es decir, las observaciones y recompensas recibidas por el agente del entorno pueden ser calculadas por algún programa (que se ejecuta en una máquina de Turing ), dadas las acciones pasadas del agente AIXI. ^[4] ${\displaystyle \mu }$ ${\displaystyle t=1}$ ${\displaystyle t=m}$ ${\displaystyle m\in \mathbb {N} }$ ${\displaystyle a_{t}\in {\mathcal {A}}}$ ${\displaystyle e_{t}\in {\mathcal {E}}={\mathcal {O}}\times \mathbb {R} }$ ${\displaystyle o_{t}\in {\mathcal {O}}}$ ${\displaystyle r_{t}\in \mathbb {R} }$ ${\displaystyle \mu (o_{t}r_{t}|a_{1}o_{1}r_{1}...a_{t-1}o_{t-1}r_{t-1}a_{t})}$ ${\displaystyle a_{1}o_{1}r_{1}...a_{t-1}o_{t-1}r_{t-1}a_{t}}$ ${\displaystyle \mu }$ ${\displaystyle \mu }$ ${\displaystyle \mu }$

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

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

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

${\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, 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 "futuros" posibles hasta pasos de tiempo hacia adelante (es decir, desde hasta ), pondera cada uno de ellos por la complejidad de los programas (es decir, por ) consistentes con el pasado del agente (es decir, las acciones ejecutadas previamente, , y las percepciones recibidas, ) que pueden generar ese futuro, y luego elige la acción que maximiza las recompensas futuras esperadas. ^[4] ${\displaystyle m-t}$ ${\displaystyle t}$ ${\displaystyle m}$ ${\displaystyle q}$ ${\displaystyle 2^{-{\textrm {length}}(q)}}$ ${\displaystyle a_{<t}}$ ${\displaystyle e_{<t}}$

Vamos a desglosar esta definición para intentar comprenderla en su totalidad.

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

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

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

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

Juntemos ahora todos estos componentes para poder entender esta ecuación o definición.

En el paso de tiempo t, AIXI elige la acción donde la función alcanza su máximo. ${\displaystyle a_{t}}$ ${\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)}}$

Parámetros

Los parámetros de AIXI son la máquina universal de Turing U y el tiempo de vida del agente m , que deben elegirse. El último parámetro puede eliminarse mediante el uso de descuento .

Optimalidad

El rendimiento de AIXI se mide por la cantidad total esperada de recompensas que recibe. Se ha demostrado que AIXI es óptimo en los siguientes aspectos: ^[2]

• Optimalidad de Pareto : no hay otro agente que tenga un rendimiento al menos tan bueno como AIXI en todos los entornos y que tenga un rendimiento estrictamente mejor en al menos un entorno. ^{[ cita requerida ]}
• Optimalidad de Pareto equilibrada: similar a la optimalidad de Pareto, pero considerando una suma ponderada de entornos.
• Optimización automática: una política p se considera optimizada automáticamente para un entorno si el rendimiento de p se acerca al máximo teórico para cuando la duración de la vida del agente (no el tiempo) tiende a infinito. Para las clases de entorno donde existen políticas de optimización automática, AIXI es optimizada automáticamente. ${\displaystyle \mu }$ ${\displaystyle \mu }$

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

Sin embargo, AIXI tiene limitaciones. Se limita a maximizar las recompensas en función de las percepciones en lugar de los estados externos. También supone 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 términos coloquiales, esto significa que no se considera contenido por el entorno con el que interactúa. También supone que el entorno es computable. ^[6]

Aspectos computacionales

Al igual que la inducción de Solomonoff , AIXI es incomputable . Sin embargo, existen aproximaciones computables de ella. Una de esas aproximaciones es AIXI tl , que funciona al menos tan bien como el agente limitado en tiempo t y espacio l , que es probablemente 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 el parcialmente observable Pac-Man . ^{[4] [7]}

Véase también

• Máquina de Gödel

Referencias

1. Marcus Hutter (2000). Una teoría de la inteligencia artificial universal basada en la complejidad algorítmica. arXiv : cs.AI/0004001 . Bibcode :2000cs........4001H.
2. — (2005). Inteligencia artificial universal: decisiones secuenciales basadas en probabilidad algorítmica. Textos en informática teórica, serie EATCS. ​​Springer. doi :10.1007/b138233. ISBN 978-3-540-22139-5.S2CID33352850  .​
3. Hutter, Marcus. "Inteligencia artificial universal". www.hutter1.net . Consultado el 21 de septiembre de 2024 .
4. Veness, Joel; Kee Siong Ng; Hutter, Marcus; Uther, William; Silver, David (2009). "Una aproximación AIXI de Monte Carlo". arXiv : 0909.0801 [cs.AI].
5. Leike, Jan; Hutter, Marcus (2015). Priores universales incorrectos y nociones de optimalidad (PDF) . Actas de la 28.ª Conferencia sobre teoría del aprendizaje.
6. Soares, Nate. "Formalización de dos problemas de modelos mundiales realistas" (PDF) . Intelligence.org . Consultado el 19 de julio de 2015 .
7. Jugando a Pacman con la aproximación AIXI – YouTube

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