Tighter Bounds for Algorithmic Complexity Estimation Using a Reusable Code-Based Block Decomposition Method

技術要約：再利用可能なコードに基づくブロック分解法を用いたアルゴリズム複雑性推定のよりタイトな境界

問題提起
アルゴリズム情報理論（AIT）は、対象の複雑さはその最短記述の長さ（コルモゴロフ複雑性、$K(x)$）によって定義されると仮定している。コーディング定理法（CTM）は、アルゴリズム確率を利用することで、小さな対象に対する $K(x)$ の実用的な推定値を提供するが、大きな対象に対しては実行不可能である。ブロック分解法（BDM）は、大きな対象を小さなブロックに分解し、各一意なブロックの複雑さを推定し、シャノン・エントロピー項を通じて反復を考慮することで、CTMをスケールアップするために導入された。

しかし、オリジナルのBDM（BDM 1.0と呼ぶ）には、構造的な限界が残されている。それは、異なるブロックを独立した記述として扱う点である。たとえ異なるブロック同士がアルゴリズム的情報を共有している場合（例えば、関連するプログラムによって生成されていたり、短いメカニズムを介して互いに変換可能であったりする場合）であっても、BDM 1.0はそれらに独立した複雑性のコストを割り当てる。これは、構成要素を生成または変換する計算可能なメカニズムから生じる規則性を捉えきれず、正確な反復のみに依存している。

手法：BDM 2.0とアルゴリズム的注意（Algorithmic Attention）
本論文では、ブロック間の依存関係を利用して記述長を削減することにより、ブロック分解を拡張するフレームワークであるBDM 2.0を導入する。核心となる革新は、総記述長の減少を最も大きく実現できる、説明的構成要素（プログラムまたはブロック）のサブセットへの選択的なリソース割り当てとして定義される、**アルゴリズム的注意（algorithmic attention）**の概念である。

主な手法構成要素は以下の通りである：

1. 条件付き記述： すべての異なるブロック $x_i$ を独立して記述する代わりに、BDM 2.0では、ブロック（またはその生成プログラム $p_i$）を、他の選択されたブロックやプログラムから条件付きで記述することを可能にする。コストは、以下の最小値によって決定される：
   • プログラム空間の条件付き複雑性：$\hat{K}(p_j | p_i)$
   • 観測空間の条件付き複雑性：$\hat{K}(x_j | x_i)$
2. 再利用の最適化： 本手法は、推定を最適化問題として定式化する。それは、代表的なプログラムの集合 $S$（「注意」の焦点）を求め、それらの無条件複雑性の総和と、残りのすべてのプログラム（$S$ に対して条件付けられたもの）の条件付き複雑性の総和を最小化することである。
3. 形式的定義： BDM 2.0の推定値は以下のように定義される：
   $$BDM_2(X) = \min_{P \in \mathcal{E}_X} \min_{\emptyset \neq S \subseteq P} \left( \sum_{p_i \in S} \hat{K}(p_i) + \sum_{p_j \in P \setminus S} \min_{p_i \in S} \{ \hat{K}(p_j | p_i), \hat{K}(x_j | x_i) \} \right) + \sum \log m_i$$
   ここで、$m_i$ はブロック $x_i$ の多重度である。
4. CTMによる運用化： 本論文は、既存のCTMを用いてBDM 2.0を実装するためのロードマップを概説している。これには、無条件複雑性（$\hat{K}$）および条件付き複雑性（$\hat{K}(\cdot|\cdot)$）の両方について、プログラム表現と出力ブロックの両方に関する有限なテーブルを生成することが含まれる。また、プログラムレベルと観測レベルの推定値の間の整合性を確保するために、これらのスケールを較正する必要がある。

主な結果と理論的貢献
本論文は、いくつかの理論的境界と関係性を確立している：

• 限界としてのBDM 1.0： 定理1は、BDM 1.0がBDM 2.0の許容可能な独立記述限界であることを証明している。BDM 2.0は、BDM 1.0と、ブロック推定値とその最短プログラム生成器との間の不一致を説明する表現オーバーヘッド項（$C_{rep}$）によって上限が抑えられる。
• 再利用ゲインと改善： 定理2は、総推定再利用ゲイン（$\hat{\Delta}$）がベースラインの表現オーバーヘッドを上回る場合、BDM 2.0がBDM 1.0を厳密に改善することを実証している。この改善は、独立した記述をより短い条件付き記述に置き換える能力によって駆動される。
• 相互情報量との接続： 定理3は、理論的な再利用ゲイン（$\Delta$）をアルゴリズム相互情報量（$I(x:y)$）に関連付けている。これは、総再利用ゲインが、対数的な条件付けオーバーヘッドを除いて、再利用されるプログラムまたはブロック間の累積されたアルゴリズム相互情報量によって下限が抑えられることを示している。これにより、ゲインが統計的な類似性ではなく、共有された因果構造に根ざしていることが確認される。
• 計算複雑性： 本論文は、代表的な集合 $S$ の厳密な最適化がNP困難（重み付きドミナント集合問題への帰着）であることを証明している。したがって、実際の実装は、ヒューリスティック、制限された候補集合（例：最短の生成器のみ）、または貪欲な集合被覆のような近似アルゴリズムに依存しなければならない。

意義と主張
著者らは、BDM 2.0がアルゴリズム複雑性の推定を、AITの原則により忠実なものにするための重要なステップであると主張している。

• 統計的反復を超えて： 正確な反復を捉えるBDM 1.0とは異なり、BDM 2.0は「あるコンポーネントを別のコンポーネントから生成または変換する短いメカニズム」を捉える。これにより、本手法は、単なる統計的な適合性ではなく、因果的生成器と普遍的圧縮に結びついた構造を検出することが可能になる。
• アルゴリズム的注意： 本論文は、「アルゴリズム的注意」をアルゴリズム情報力学（AID）における形式的な原理として導入している。これは、局所的な複雑さから、記述のグローバルな効率性へと焦点を移し、他の観測の「アルゴリズム的ハブ」として機能するコンポーネントを優先させるものである。
• 実用的なロードマップ： 本論文は、完全に実装されたソフトウェアスイートや新しい実験的ベンチマークを提示しているわけではないが、既存のCTMインフラストラクチャを用いてBDM 2.0のエスティメータを構築するための厳密な理論的枠組みと具体的な運用ロードマップを提供している。また、条件付き推定器が、単なる偽の相関ではなく、真のアルゴリズム相互情報量を反映していることを保証するために、条件付き推定器を検証する必要性を強調している。

結論として、本論文は、再利用可能なコードベースのブロック分解と条件付き記述を組み込むことにより、BDM 2.0がアルゴリズム複雑性推定においてよりタイトな境界を提供し、局所的なアルゴリズム推定と、複雑なシステムに内在するグローバルな構造的依存性の間のギャップを埋めるものであると論じている。