AIXI - AIXI

AIXI ['ai̯k͡siː] est un formalisme mathématique théoriquepour l'intelligence artificielle générale . Il combine l' induction de Solomonoff avec la théorie de la décision séquentielle . AIXI a été proposé pour la première fois par Marcus Hutter en 2000 et plusieurs résultats concernant AIXI sont prouvés dans le livre de Hutter de 2005 Universal Artificial Intelligence .

AIXI est un agent d'apprentissage par renforcement . Il maximise les récompenses totales attendues reçues de l'environnement. Intuitivement, il considère simultanément chaque hypothèse (ou environnement) calculable. À chaque pas de temps, il examine tous les programmes possibles et évalue le nombre de récompenses générées par ce programme en fonction de la prochaine action entreprise. Les récompenses promises sont alors pondérées par la croyance subjective que ce programme constitue le véritable environnement. Cette croyance est calculée à partir de la durée du programme : les programmes plus longs sont considérés comme moins probables, conformément au rasoir d'Occam . AIXI sélectionne ensuite l'action qui a la récompense totale attendue la plus élevée dans la somme pondérée de tous ces programmes.

Définition

AIXI est un agent d'apprentissage par renforcement qui interagit avec un environnement stochastique et inconnu mais calculable . L'interaction se déroule par pas de temps, de à , où est la durée de vie de l'agent AIXI. Au pas de temps t , l'agent choisit une action (par exemple un mouvement de membre) et l'exécute dans l'environnement, et l'environnement répond par un "percept" , qui consiste en une "observation" (par exemple, une image de caméra) et une récompense , distribué selon la probabilité conditionnelle , où est « l'historique » des actions, observations et récompenses. L'environnement est ainsi représenté mathématiquement comme une distribution de probabilité sur des "percepts" (observations et récompenses) qui dépendent de l' historique complet , il n'y a donc pas d' hypothèse de Markov (contrairement aux autres algorithmes RL). A noter encore que cette distribution de probabilité est inconnue de l'agent AIXI. De plus, notez encore que c'est calculable, c'est-à-dire que les observations et les récompenses reçues par l'agent de l'environnement peuvent être calculées par un programme (qui s'exécute sur une machine de Turing ), étant donné les actions passées de l'agent AIXI. ${\style d'affichage \mu }$${\style d'affichage t=1}$${\style d'affichage 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}}$${\style d'affichage \mu }$${\style d'affichage \mu }$${\style d'affichage \mu }$

Le seul objectif de l'agent AIXI est de maximiser , c'est-à-dire la somme des récompenses du pas de temps 1 à m. ${\displaystyle \sum _{t=1}^{m}r_{t}}$

L'agent AIXI est associé à une politique stochastique , qui est la fonction qu'il utilise pour choisir des actions à chaque pas de temps, où est l'espace de toutes les actions possibles qu'AIXI peut prendre et est l'espace de toutes les "percepts" possibles qui peuvent être produits par l'environnement. L'environnement (ou distribution de probabilité) peut également être considéré comme une politique stochastique (qui est une fonction) : , où est l' opération de l' étoile de Kleene . ${\displaystyle \pi :({\mathcal {A}}\times {\mathcal {E}})^{*}\rightarrow {\mathcal {A}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {E}}}$${\style d'affichage \mu }$${\displaystyle \mu :({\mathcal {A}}\times {\mathcal {E}})^{*}\times {\mathcal {A}}\rightarrow {\mathcal {E}}}$${\style d'affichage *}$

En général, au pas de temps (qui va de 1 à m), AIXI, ayant préalablement exécuté des actions (qui est souvent abrégé dans la littérature en ) et ayant observé l'histoire des percepts (qui peut être abrégé en ), choisit et exécute en l'environnement l'action, , définie comme suit ${\style d'affichage 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}}$${\style d'affichage 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)}}$

ou, en utilisant des parenthèses, pour lever l'ambiguïté des priorités

${\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)}$

Intuitivement, dans la définition ci-dessus, AIXI considère la somme de la récompense totale sur tous les « futurs » possibles jusqu'à des pas de temps à venir (c'est-à-dire de à ), pondère chacun d'eux par la complexité des programmes (c'est-à-dire par ) cohérent avec le passé de l'agent (c'est-à-dire les actions précédemment exécutées, , et les perceptions reçues, ) qui peuvent générer ce futur, puis choisit l'action qui maximise les récompenses futures attendues. ${\displaystyle mt}$${\style d'affichage t}$${\style d'affichage m}$${\style d'affichage q}$${\displaystyle 2^{-{\textrm {length}}(q)}}$${\displaystyle a_{<t}}$${\displaystyle e_{<t}}$

Décomposons cette définition pour tenter de la comprendre pleinement.

${\style d'affichage o_{t}r_{t}}$est le "percept" (qui consiste en l'observation et la récompense ) reçu par l'agent AIXI au pas de temps de l'environnement (qui est inconnu et stochastique). De même, est le percept reçu par AIXI au pas de temps (le dernier pas de temps où AIXI est actif). ${\style d'affichage o_{t}}$${\style d'affichage r_{t}}$${\style d'affichage t}$${\style d'affichage o_{m}r_{m}}$${\style d'affichage m}$

${\displaystyle r_{t}+\ldots +r_{m}}$est la somme des récompenses d'un pas de temps à un pas de temps , donc AIXI doit se projeter dans le futur pour choisir son action au pas de temps . ${\style d'affichage t}$${\style d'affichage m}$${\style d'affichage t}$

${\style d'affichage U}$désigne une machine de Turing universelle monotone et couvre tous les programmes (déterministes) de la machine universelle , qui reçoit en entrée le programme et la séquence d'actions (c'est-à-dire toutes les actions) et produit la séquence de perceptions . La machine de Turing universelle est ainsi utilisée pour « simuler » ou calculer les réponses ou les perceptions de l'environnement, compte tenu du programme (qui « modélise » l'environnement) et de toutes les actions de l'agent AIXI : en ce sens, l'environnement est « calculable » (comme indiqué ci-dessus). Notez qu'en général, le programme qui « modélise » l' environnement actuel et réel (où AIXI doit agir) est inconnu car l'environnement actuel est également inconnu. ${\style d'affichage q}$${\style d'affichage U}$${\style d'affichage q}$${\displaystyle a_{1}\dots a_{m}}$${\displaystyle o_{1}r_{1}\ldots o_{m}r_{m}}$${\style d'affichage U}$${\style d'affichage q}$

${\displaystyle {\textrm {longueur}}(q)}$est la longueur du programme (qui est codée sous forme de chaîne de bits). Notez que . Par conséquent, dans la définition ci-dessus, doit être interprété comme un mélange (dans ce cas, une somme) sur tous les environnements calculables (qui sont cohérents avec le passé de l'agent), chacun pondéré par sa complexité . Notez que peut également être écrit comme , et est la séquence d'actions déjà exécutées dans l'environnement par l'agent AIXI. De même, , et est la séquence de perceptions produites par l'environnement jusqu'à présent. ${\style d'affichage 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 {longueur}}(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}}$

Regroupons maintenant tous ces composants afin de comprendre cette équation ou définition.

Au pas de temps t, AIXI choisit l'action où la fonction atteint son maximum. ${\style d'affichage 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 {longueur}}(q)}}$

Paramètres

Les paramètres d'AIXI sont la machine de Turing universelle U et la durée de vie de l'agent m , qu'il faut choisir. Ce dernier paramètre peut être supprimé par l'utilisation de l' actualisation .

Le sens du mot AIXI

Selon Hutter, le mot « AIXI » peut avoir plusieurs interprétations. AIXI peut signifier AI sur la base de la distribution de Solomonoff, désignée par (qui est la lettre grecque xi), ou par exemple, elle peut signifier AI "croisée" (X) avec induction (I). Il y a d'autres interprétations. ${\style d'affichage \xi }$

Optimalité

La performance d'AIXI est mesurée par le nombre total attendu de récompenses qu'elle reçoit. AIXI s'est avéré optimal des manières suivantes.

• Optimité de Pareto : il n'y a pas d'autre agent qui fonctionne au moins aussi bien qu'AIXI dans tous les environnements tout en étant strictement meilleur dans au moins un environnement.
• Optimité de Pareto équilibrée : comme l'optimalité de Pareto, mais en considérant une somme pondérée d'environnements.
• Auto-optimisation : une politique p est dite auto-optimisante pour un environnement si la performance de p approche le maximum théorique lorsque la durée de vie de l'agent (et non le temps) tend vers l'infini. Pour les classes d'environnement où des politiques d'auto-optimisation existent, AIXI s'auto-optimise.${\style d'affichage \mu }$${\style d'affichage \mu }$

Il a ensuite été montré par Hutter et Jan Leike que l'optimalité de Pareto équilibrée est subjective et que toute politique peut être considérée comme optimale de Pareto, ce qu'ils décrivent comme sapant toutes les revendications d'optimalité précédentes pour AIXI.

Cependant, AIXI a des limites. Il se limite à maximiser les récompenses basées sur des perceptions par opposition aux états externes. Il suppose également qu'il interagit avec l'environnement uniquement par des canaux d'action et de perception, l'empêchant d'envisager la possibilité d'être endommagé ou modifié. Familièrement, cela signifie qu'il ne se considère pas comme contenu par l'environnement avec lequel il interagit. Il suppose également que l'environnement est calculable.

Aspects informatiques

Comme l' induction de Solomonoff , AIXI est incalculable . Cependant, il existe des approximations calculables. Une de ces approximations est AIXI tl , qui fonctionne au moins aussi bien que l' agent limité dans le temps t et l'espace l . Une autre approximation d'AIXI avec une classe d'environnement restreinte est MC-AIXI (FAC-CTW) (qui signifie Monte Carlo AIXI FAC -Context-Tree Weighting ), qui a eu un certain succès en jouant à des jeux simples tels que Pac-Man partiellement observable .

Voir également

• Machine de Gödel

Les références

• "Universal Algorithmic Intelligence: A Mathématique Top->Down Approach ", Marcus Hutter, arXiv : cs/0701125 ; également dans Intelligence Générale Artificielle , eds. B. Goertzel et C. Pennachin, Springer, 2007, ISBN  9783540237334 , pp. 227-290, doi : 10.1007/978-3-540-68677-4_8 .