アルゴリズム確率

コルモゴロフの不変性定理は、データセットのコルモゴロフ複雑度、すなわち最小記述長が、汎用チューリングマシンをシミュレートするために使用されるチューリング完全な言語の選択に左右されないことを明確にしています。

${\displaystyle \forall x\in \{0,1\}^{*},|K_{U}(x)-K_{U'}(x)|\leq {\mathcal {O}}(1)}$

どこ${\displaystyle K_{U}(x)=\min _{p}\{|p|:U(p)=x\}}$。

最小限の説明${\displaystyle p}$そのため${\displaystyle U(p)=x}$弦の自然な表現として機能する${\displaystyle x}$チューリング完全言語に関して${\displaystyle U}$さらに、${\displaystyle x}$これ以上圧縮できない${\displaystyle p}$これは圧縮不可能な文字列であり、したがって計算不可能な文字列である。これは科学者のランダム性の概念に対応し、コルモゴロフ複雑性が計算不可能である理由を明確にする。

したがって、あらゆるデータは、ランダムな文字列によって必要かつ十分な表現を持つことになる。

以下は^{[ 13 ]からの引用です。}

コンパイラ理論から、任意の2つのチューリング完全言語に対して、${\displaystyle U_{1}}$そして${\displaystyle U_{2}}$コンパイラが存在する$\displaystyle \Lambda _{1}}$表現された ${\displaystyle U_{1}}$プログラムを翻訳する${\displaystyle U_{2}}$機能的に同等のプログラムに表現する${\displaystyle U_{1}}$。

したがって、もし${\displaystyle p}$与えられた文字列を出力する最短のプログラム${\displaystyle x}$それから：

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

どこ${\displaystyle |\Lambda _{1}|={\mathcal {O}}(1)}$そして対称性により、反対の不等式が得られる。

一意に復号可能な符号はすべてクラフト・マクミランの不等式を満たすという前提のもと、プレフィックスフリーのコルモゴロフ複雑性を用いることで、普遍分布を導出できる。

${\displaystyle P(x)=\sum _{U(p)=x}P(U(p)=x)=\sum _{U(p)=x}2^{-K_{U}(p)}\leq 1}$

事実${\displaystyle U}$接頭辞のないUTMをシミュレートする可能性があるということは、2つの異なる記述に対して${\displaystyle p}$そして${\displaystyle p'}$、${\displaystyle p}$は部分文字列ではありません${\displaystyle p'}$そして${\displaystyle p'}$は部分文字列ではありません${\displaystyle p}$。

計算可能な宇宙では、符号化された現象が与えられます${\displaystyle x\in \{0,1\}^{*}}$物理的プロセスによって生成される現象の確率は明確に定義され、それぞれ異なる独立した原因の確率の合計に等しい。接頭辞のない基準こそが、因果関係の独立性を保証するものである。

これはクラフト＝マクミラン不等式の直接的な結果である。

クラフトの不等式は、文字列の列が与えられた場合、${\displaystyle \{x_{i}\}_{i=1}^{n}}$コードワードを持つ接頭辞コードが存在する${\displaystyle \{\sigma _{i}\}_{i=1}^{n}}$どこ$\displaystyle \forall i,|\sigma _{i}|=k_{i}}$の場合に限り：

$\sum_{i=1}^{n}s^{-k_{i}}\leq 1$

どこ${\displaystyle s}$アルファベットのサイズ${\displaystyle S}$。

一般性を失うことなく、次のように順序付けできると仮定しましょう。${\displaystyle k_{i}}$すなわち、以下の通りである。

${\displaystyle k_{1}\leq k_{2}\leq ...\leq k_{n}}$

さて、各ステップで、プレフィックスコードが存在するのは、${\displaystyle j}$少なくとも1つのコードワードを選択する必要があり、そのコードワードには上記のいずれも含まれない。${\displaystyle j-1}$接頭辞としてのコードワード。前のステップでコードワードが存在するため${\displaystyle i<j,s^{k_{j}-k_{i}}}$暗号語は禁止されています。$\displaystyle \sigma _{i}}$接頭辞として。したがって、一般に接頭辞コードが存在するのは、以下の条件を満たす場合に限られる。

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

両辺を$\displaystyle s^{k_{j}}}$すると、次のことがわかります。

$\sum_{i=1}^{n}s^{-k_{i}}\leq 1$

証明終了。

帰納的推論、すなわち過去の観察に基づいて将来の出来事を予測するプロセスは、知的な行動の中核をなすものです。ハッターはこのプロセスをオッカムの剃刀とアルゴリズム的確率を用いて定式化しました。このフレームワークは、データの単純さを最短記述プログラムの長さで測定するコルモゴロフ複雑性に基づいています。この概念は、レイ・ソロモノフによって導入された普遍分布MMの基盤となっており、より単純な仮説に高い確率を割り当てます。ハッターは普遍分布を拡張して行動を含めることで、構造が未知の環境における予測、最適化、強化学習などの問題に対処できるフレームワークを構築しました。

AIXIモデルは、ハッターの理論の中核を成すものです。これは、未知の環境において期待報酬を最大化するように設計された、普遍的な人工エージェントを記述しています。AIXIは、環境が計算可能な確率分布で表現できるという前提に基づいて動作します。過去の観測データを用いて、アルゴリズム的確率を活用し、最も可能性の高い環境モデルを推論します。数学的には、AIXIは将来のあらゆる行動と観測のシーケンスを評価します。そして、それらのアルゴリズム的確率と期待効用を計算し、累積報酬を最大化する行動シーケンスを選択します。このアプローチにより、逐次的な意思決定が最適化問題に変換されます。しかし、AIXIの一般的な定式化は計算不可能であるため、直接実装することは現実的ではありません。

AIXIは、あらゆる計算可能な環境において他のどのエージェントよりも優れた性能を発揮するという意味で、普遍的に最適です。この普遍性により、AIXIは知能の理論的ベンチマークとなっています。しかし、アルゴリズムの確率に依存しているため、計算が非現実的であり、すべての可能性を評価するには指数関数的な時間が必要となります。この制約に対処するため、Hutterは、AIXItlなどの時間制限付き近似を提案しました。これらの近似は、元のモデルの多くの理論的特性を維持しながら、計算負荷を軽減します。これらの近似は、計算の実現可能性と最適性の間のより実用的なバランスを提供します。

AIXIフレームワークは、人工知能および関連分野において重要な意義を持つ。知能を測定するための正式なベンチマークを提供するとともに、予測、強化学習、最適化など、様々な問題を解決するための理論的基盤を提供する。しかし、その強みにもかかわらず、このフレームワークには限界もある。AIXIは、環境が計算可能であることを前提としており、カオス的システムや計算不可能なシステムは対象外となる。さらに、高い計算能力を必要とするため、実世界での応用は困難である。

ハッターの理論は、知能と計算の本質に関する哲学的問いを提起する。アルゴリズム的確率への依存は、知能を計算能力と予測能力に結びつけるが、これは特定の自然現象やカオス現象を排除する可能性がある。とはいえ、AIXIモデルは知的行動の理論的な上限に関する洞察を提供し、より実用的なAIシステムへの足がかりとなる。