アイシー

AIXI / ˈ aɪ k s i /は、汎用人工知能のための理論数学的形式論である。ソロモンオフ帰納法と逐次決定理論を組み合わせたものである。AIXIは2000年にマーカス・ハッターによって初めて提案され^{[ 1 ]} 、AIXIに関するいくつかの結果はハッターの2005年の著書『 Universal Artificial Intelligence』で証明されている^{[ 2 ]}。

AIXIは強化学習（RL）エージェントです。環境から受け取る期待総報酬を最大化します。直感的に言えば、AIXIは計算可能なすべての仮説（または環境）を同時に考慮します。各タイムステップにおいて、AIXIはあらゆる可能性のあるプログラムを検討し、次に実行されるアクションに応じて、各プログラムが生成する報酬の数を評価します。約束された報酬は、このプログラムが真の環境を構成するという主観的な信念によって重み付けされます。この信念はプログラムの長さから計算されます。オッカムの剃刀の法則に従い、長いプログラムは確率が低いと見なされます。AIXIは、これらのすべてのプログラムの重み付けされた合計の中で、期待総報酬が最も高いアクションを選択します。

語源

フッターによれば、「AIXI」という語には複数の解釈がある。AIXIは、ソロモンオフ分布に基づくAI （ギリシャ文字のxiで表される）を表す場合もあれば、例えば、AIと帰納法（I）を「交差」（X）させたものを表す場合もある。他にも解釈は存在する。^{[ 3 ]}${\displaystyle \xi}$

意味

AIXIは、確率的かつ未知だが計算可能な環境 と相互作用する強化学習エージェントです。相互作用は から までのタイムステップで進行します。ここではAIXIエージェントの寿命です。タイムステップtにおいて、エージェントはアクション（例えば、手足の動き）を選択し、それを環境内で実行します。環境は「知覚」 で応答します。知覚は「観測」（例えば、カメラ画像）と報酬で構成され、条件付き確率に従って分布します。ここで は、アクション、観測、報酬の「履歴」です。したがって、環境は完全な履歴に依存する「知覚」（観測と報酬）の確率分布として数学的に表現されるため、マルコフ仮定は適用されません（他の強化学習アルゴリズムとは異なります）。この確率分布はAIXIエージェントには未知であることに再度注意してください。さらに、 は計算可能であることに再度留意してください。つまり、エージェントが環境から受け取る観測値と報酬は、 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}$

AIXI エージェントの唯一の目標は、つまり、タイム ステップ 1 から m までの報酬の合計を最大化することです。 ${\displaystyle \sum _{t=1}^{m}r_{t}}$

AIXIエージェントは確率的ポリシー に関連付けられています。これは、AIXIが各タイムステップで行動を選択するために使用する関数です。ここで、 はAIXIが実行できるすべての可能な行動の空間であり、は環境によって生成されるすべての可能な「知覚」の空間です。環境（または確率分布）は確率的ポリシー（関数）と考えることもできます。ここで、はクリーネスター演算です。 ${\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 *}$

一般的に、時間ステップ（1からmの範囲）で、AIXIは、以前にアクション（文献では と略されることが多い）を実行し、知覚の履歴（ と略されることもある）を観察した上で、以下のように定義されるアクション を選択して環境内で実行する。 ^{[ 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)}}$

または括弧を使用して、優先順位を明確にする

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

直感的に言えば、上記の定義では、AIXIは、時間ステップ先までのすべての可能な「未来」の総報酬の合計（つまり、からまで）を考慮し、その未来を生成できるエージェントの過去（つまり、以前に実行されたアクション、および受信した知覚、 ）と一致するプログラムの複雑さ（つまり、によって）によってそれぞれに重み付けし、期待される将来の報酬を最大化するアクションを選択します。^{[ 4 ]}${\displaystyle mt}$ ${\displaystyle t}$ ${\displaystyle m}$ ${\displaystyle q}$ ${\displaystyle 2^{-{\textrm {長さ}}(q)}}$ ${\displaystyle a_{<t}}$ ${\displaystyle e_{<t}}$

この定義を完全に理解するために、詳しく見ていきましょう。

${\displaystyle o_{t}r_{t}}$ は、 AIXIエージェントが時間ステップにおいて環境（未知かつ確率的）から受け取る「知覚」（観測値と報酬で構成される）です。同様に、はAIXIが時間ステップ（AIXIがアクティブな最後の時間ステップ）において受け取る知覚です。 ${\displaystyle o_{t}}$ ${\displaystyle r_{t}}$ ${\displaystyle t}$ ${\displaystyle o_{m}r_{m}}$ ${\displaystyle m}$

${\displaystyle r_{t}+\ldots +r_{m}}$ はタイムステップ からタイムステップ までの報酬の合計であるため、AIXI はタイムステップ でのアクションを選択するために将来を見据える必要があります。 ${\displaystyle t}$ ${\displaystyle m}$ ${\displaystyle t}$

${\displaystyle U}$ は単調な汎用チューリングマシンを表し、汎用マシン 上のすべての（決定論的）プログラムを対象とします。汎用マシンは、プログラムとアクションのシーケンス（つまり、すべてのアクション）を入力として受け取り、知覚のシーケンスを生成します。したがって、汎用チューリングマシンは、プログラム（環境を「モデル化」する）と AIXI エージェントのすべてのアクションが与えられた場合、環境の応答または知覚を「シミュレート」または計算するために使用されます。この意味で、環境は「計算可能」です（上記のように）。一般に、現在の実際の環境（AIXI が動作する必要がある）を「モデル化」するプログラムは、現在の環境も不明であるため、不明であることに注意してください。 ${\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 {長さ}}(q)}$ はプログラムの長さ（ビット列としてエンコードされている）である。 である点に注意してください。したがって、上記の定義では、は、エージェントの過去と一致するすべての計算可能な環境の混合（この場合は合計）として解釈され、それぞれの環境は複雑さ によって重み付けされます。 はと表記することもでき、 はAIXI エージェントによって環境内ですでに実行されたアクションのシーケンスである点に注意してください。同様に、、 は、環境によってこれまでに生成された知覚のシーケンスです。 ${\displaystyle q}$ ${\displaystyle 2^{-{\textrm {長さ}}(q)}={\frac {1}{2^{{\textrm {長さ}}(q)}}}}$ ${\displaystyle \sum _{q:\;U(q,a_{1}\ldots a_{m})=o_{1}r_{1}\ldots o_{m}r_{m}}2^{-{\textrm {長さ}}(q)}}$ ${\displaystyle 2^{-{\textrm {長さ}}(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}}$

この方程式または定義を理解するために、これらすべての要素をまとめてみましょう。

時間ステップ t で、AIXI は関数が最大値に達するアクションを選択します。 ${\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)}}$

パラメータ

AIXIのパラメータは、汎用チューリングマシンUとエージェントの寿命mであり、これらを選択する必要があります。後者のパラメータは割引を用いることで除去できます。

最適性

AIXIのパフォーマンスは、受け取る報酬の期待総数によって測定されます。AIXIは、以下の方法で最適であることが証明されています。^{[ 2 ]}

• パレート最適性: すべての環境で少なくとも AIXI と同等のパフォーマンスを発揮し、少なくとも 1 つの環境で AIXI より優れたパフォーマンスを発揮するエージェントは他に存在しません。
• バランスのとれたパレート最適性: パレート最適性と同様ですが、環境の加重合計を考慮します。
• 自己最適化：ある環境において、ポリシーpのパフォーマンスが、エージェントの寿命（時間ではなく）が無限大になったときの理論上の最大値に近づく場合、ポリシーpは自己最適化されているとみなされます。自己最適化ポリシーが存在する環境クラスでは、AIXIは自己最適化されます。${\displaystyle \mu}$ ${\displaystyle \mu}$

その後、フッターとヤン・ライケは、バランスのとれたパレート最適性は主観的であり、どのような政策もパレート最適とみなすことができると示しました。これはAIXIのこれまでの最適性の主張を覆すものであると彼らは述べています。^{[ 5 ]}

しかし、AIXIには限界がある。AIXIは、外部状態ではなく知覚に基づいて報酬を最大化するという制約がある。また、AIXIは行動と知覚のチャネルのみを通じて環境と相互作用することを前提としており、損傷や改変の可能性を考慮することができない。言い換えれば、AIXIは相互作用する環境に自身が含まれるとは考えていない。また、AIXIは環境が計算可能であると仮定している。^{[ 6 ]}

計算面

ソロモンオフ帰納法と同様に、AIXIは計算不可能である。しかし、計算可能な近似が存在する。そのような近似の一つがAIXI tlであり、これは少なくとも、時間tと空間lが制限された、おそらく最良のエージェントと同等の性能を示す。^{[ 2 ]}環境クラスが制限されたAIXIのもう一つの近似はMC-AIXI (FAC-CTW)（モンテカルロAIXI FAC-コンテキストツリー重み付けの略）であり、これは部分観測パックマンのような単純なゲームである程度成功を収めている。^{[ 4 ] [ 7 ]}

参照

• ゲーデルマシン

参考文献

1. Marcus Hutter (2000).アルゴリズムの複雑性に基づく汎用人工知能の理論. arXiv : cs.AI/0004001 . Bibcode : 2000cs......4001H .
2. — (2005).ユニバーサル人工知能：アルゴリズム的確率に基づく逐次決定．理論計算機科学テキスト EATCSシリーズ．シュプリンガー．doi : 10.1007 / b138233．ISBN 978-3-540-22139-5. S2CID  33352850 .
3. Hutter, Marcus. 「ユニバーサル人工知能」www.hutter1.net . 2024年9月21日閲覧。
4. Veness, Joel; Kee Siong Ng; Hutter, Marcus; Uther, William; Silver, David (2009). 「モンテカルロAIXI近似」. arXiv : 0909.0801 [ cs.AI ].
5. Leike, Jan; Hutter, Marcus (2015).誤った普遍的事前分布と最適性の概念(PDF) . 第28回学習理論会議議事録.
6. ソアレス、ネイト. 「現実的な世界モデルの2つの問題の形式化」(PDF) . Intelligence.org . 2015年7月19日閲覧。
7. AIXI近似を使用してパックマンをプレイ – YouTube

• 「ユニバーサル・アルゴリズム・インテリジェンス：数学的トップダウンアプローチ」、マーカス・ハッター、arXiv：cs/0701125；また、B. ゴーツェルとC. ペナチン編『人工知能』（Springer、2007年、ISBN）にも収録されている。 9783540237334、227–290ページ、土井：10.1007/978-3-540-68677-4_8。