情報変動の複雑さ

情報変動複雑性は、エントロピーに関する情報の変動として定義される情報理論上の量である。これは、動的システムにおける秩序と混沌の優位性の変動から導き出され、さまざまな分野で複雑性の尺度として使用されている。これは、1993年の論文でベイツとシェパード^[1]

離散動的システムの情報変動の複雑さは、ランダムな外部入力データを受けたときの状態の確率分布の関数です。乱数ジェネレータやホワイト ノイズ信号などの豊富な情報源を使用してシステムを駆動する目的は、周波数が豊富なインパルスが信号処理で使用されるのとほぼ同じ方法で、システムの内部ダイナミクスを調査することです。

システムが可能な状態を持ち、その状態確率が分かっている場合、その情報エントロピーは ${\displaystyle N}$ ${\displaystyle p_{i}}$

${\displaystyle \mathrm {H} =\sum _{i=1}^{N}p_{i}I_{i}=-\sum _{i=1}^{N}p_{i}\log p_{i},}$

は状態の情報内容です。 ${\textstyle I_{i}=-\log p_{i}}$${\displaystyle i}$

システムの情報変動複雑さは、その平均値の標準偏差または変動として定義されます。 ${\displaystyle I}$${\displaystyle \mathrm {H} }$

${\displaystyle \sigma _{I}={\sqrt {\sum _{i=1}^{N}p_{i}(I_{i}-\mathrm {H} )^{2}}}={\sqrt {\sum _{i=1}^{N}p_{i}I_{i}^{2}-\mathrm {H} ^{2}}}}$

または

${\displaystyle \sigma _{I}={\sqrt {\sum _{i=1}^{N}p_{i}\log ^{2}p_{i}-{\Biggl (}\sum _{i=1}^{N}p_{i}\log p_{i}{\Biggr )}^{2}}}.}$

状態情報の変動は 、すべて である最大無秩序システムではゼロです。つまり、システムはランダム入力を単純に模倣します。 は、入力に関係なく、システムが 1 つの固定状態のみで完全に秩序立っている場合もゼロです。 は、これら 2 つの極端な状態の間でゼロではなく、状態空間には高確率状態と低確率状態が混在します。 ${\displaystyle \sigma _{I}}$${\textstyle p_{i}={\frac {1}{N}}}$${\displaystyle \sigma _{I}}$${\textstyle (p_{1}=1)}$${\displaystyle \sigma _{I}}$

複雑で動的なシステムは時間の経過とともに進化しますが、状態間の遷移の仕方は外部刺激によって不規則に変わります。外部刺激に対して敏感になる場合 (不安定) もあれば、敏感でなくなる場合もあります (安定)。特定の状態に複数の次の状態がある場合、外部情報によって次の状態が決定され、システムは状態空間内の特定の軌跡をたどることでこの情報を取得します。ただし、複数の異なる状態がすべて同じ次の状態につながる場合、次の状態に入ると、システムはその前の状態に関する情報を失います。したがって、複雑なシステムは時間の経過とともに進化するにつれて、交互に情報を獲得したり失ったりします。この情報の交替または変動は、一時的な情報ストレージまたはメモリである記憶と忘却に相当し、重要な計算の重要な機能です。

状態間の遷移に関連する情報の獲得または喪失は、状態情報と関連している可能性があります。状態から状態への遷移の純情報獲得は、状態を離れるときに得られる情報から、状態に入るときに失われる情報を差し引いたものです。 ${\displaystyle i}$${\displaystyle j}$${\displaystyle i}$${\displaystyle j}$

${\displaystyle \Gamma_{ij}=-\logp_{i\rightarrowj}+\logp_{i\leftarrowj}.}$

ここでは、現在の状態が の場合に次の状態が になる順方向条件付き確率、現在の状態が の場合に前の状態が であったという逆方向条件付き確率です。条件付き確率は、状態から状態への遷移が発生する確率である遷移確率と次のように関連しています。 ${\textstyle p_{i\rightarrow j}}$${\displaystyle i}$${\displaystyle j}$${\textstyle p_{i\leftarrow j}}$${\displaystyle j}$${\displaystyle i}$ ${\displaystyle p_{ij}}$${\displaystyle i}$${\displaystyle j}$

${\displaystyle p_{ij}=p_{i}p_{i\rightarrow j}=p_{i\leftarrow j}p_{j}.}$

条件付き確率を排除する:

${\displaystyle \Gamma _{ij}=-\log(p_{ij}/p_{i})+\log(p_{ij}/p_{j})=\log p_{i}-\log p_{j}=I_{j}-I_{i}.}$

したがって、遷移の結果としてシステムが得る純情報は、初期状態から最終状態までの状態情報の増加のみに依存する。これは、複数の連続した状態遷移の場合でも当てはまることが示される。遷移^[1]

${\textstyle \Gamma =\Delta I}$は、力と位置エネルギーの関係を彷彿とさせます。は位置エネルギーに似ており、は力に似ています。外部情報は、質量を坂道でより高い重力位置の状態に押し上げるとエネルギーが蓄えられるのと同じように、情報を蓄積するために、システムを「坂道」でより高い情報ポテンシャルの状態に「押し上げ」ます。 蓄積されるエネルギーの量は、最終的な高さにのみ依存し、坂道を上る経路には依存しません。 同様に、蓄積される情報の量は、初期の共通状態と最終的なまれな状態の間の遷移経路には依存しません。 システムが、高い情報ポテンシャルを持つまれな状態に達すると、それまで蓄積されていた情報を失い、一般的な状態に「落ち込む」可能性があります。 ${\displaystyle I}$${\displaystyle \Phi }$${\displaystyle \Gamma }$${\displaystyle \mathbf {F} }$${\textstyle \mathbf {F} ={\nabla \Phi }}$

平均値（ゼロ）の標準偏差、つまり純情報利得の変動を計算すると役に立つかもしれない。${\displaystyle \Gamma }$ ${\displaystyle \sigma _{\Gamma }}$, ^[1]しかし、状態空間における複数の遷移メモリ ループを考慮に入れるため、システムの計算能力をより正確に表すことになります。さらに、状態よりも遷移の数が多い可能性があるため、適用が簡単です。 ${\displaystyle \sigma _{I}}$${\displaystyle \sigma _{I}}$

外部情報に敏感な動的システム (不安定) は混沌とした動作を示しますが、外部情報に鈍感なシステム (安定) は秩序立った動作を示します。複雑なシステムは両方の動作を示し、豊富な情報源にさらされると、動的バランスを保ちながらそれらの間で変動します。変動の度合いは によって定量化されます。これは、複雑なシステムが時間の経過とともに進化するにつれて、混沌と秩序の優位性が交互に変化する様子を捉えます。 ${\displaystyle \sigma _{I}}$

出典: ^[2]

ルール110 の初等セルオートマトンバリアントは、汎用計算が可能であることが証明されています。この証明は、グライダーと呼ばれる凝集性があり自己永続的なセルパターンの存在と相互作用に基づいています。グライダーは、複雑なシステムに関連する創発現象の例であり、オートマトンセルのグループがグライダーが通過していることを記憶する能力があることを意味します。したがって、情報の増加と減少、不安定性と安定性、混沌と秩序の交替によって、状態空間にメモリループが存在することが予想されます。

ルール 110 に従う隣接するオートマトン セルの 3 つのセル グループを考えます。端-中心-端中央のセルの次の状態は、ルールで指定された中央のセル自体と端のセルの現在の状態によって決まります。

このシステムの情報変動の複雑さを計算するには、3つのセルのグループの各端にドライバーセルを接続して、次のようにランダムな外部刺激を与えます。ドライバー→エンド-センター-エンド←ドライバー、ルールを 2 つのエンド セルに適用できるようにします。次に、各可能な現在の状態とドライバー セルの内容の各可能な組み合わせに対して次の状態が何になるかを判断して、順方向の条件付き確率を決定します。

このシステムの状態図は下図の通りで、円は状態を表し、矢印は状態間の遷移を表しています。このシステムの可能な8つの状態は、1-1-1に0-0-0、3 セル グループの 3 ビットの内容の 8 進数に相当する 7 から 0 でラベル付けされています。遷移矢印には、順方向の条件付き確率のラベル付けがされています。矢印の発散と収束には、ドライバー セルから発生する情報の獲得と喪失の変動に対応して変動があることに注意してください。

順方向の条件付き確率は、特定の遷移を駆動する可能性のあるドライバー セルの内容の割合によって決まります。たとえば、2 つのドライバー セルの内容の 4 つの可能な組み合わせでは、状態 7 は状態 5、4、1、0 につながるため、、、、およびはそれぞれ1 ⁄ 4つまり 25% になります。同様に、状態 0 は状態 0、1、0、1 につながるため、およびはそれぞれ1 ⁄ 2 つまり 50% になります。以下同様です。 ${\textstyle p_{7\rightarrow 5}}$${\textstyle p_{7\rightarrow 4}}$${\textstyle p_{7\rightarrow 1}}$${\textstyle p_{7\rightarrow 0}}$${\textstyle p_{0\rightarrow 1}}$${\textstyle p_{0\rightarrow 0}}$

状態確率は次のように関係している。

${\displaystyle p_{j}=\sum _{i=0}^{7}p_{i}p_{i\rightarrow j}}$そして${\displaystyle \sum _{i=0}^{7}p_{i}=1.}$

これらの線形代数方程式は、次のように状態確率について解くことができる。結果: ^[2]

情報エントロピーと複雑さは状態確率から計算できます。

${\displaystyle \mathrm {H} =-\sum _{i=0}^{7}p_{i}\log _{2}p_{i}=2.86{\text{ bits}},}$

${\displaystyle \sigma _{I}={\sqrt {\sum _{i=0}^{7}p_{i}\log _{2}^{2}p_{i}-\mathrm {H} ^{2}}}=0.56{\text{ bits}}.}$

8 つの状態の最大可能エントロピーは であり、これはすべての の場合に当てはまることに注意してください。したがって、ルール 110 は という比較的高いエントロピーまたは状態利用率を持ちます。ただし、これはエントロピーに関する状態情報の大幅な変動、したがって複雑さのかなりの値を排除するものではありません。一方、最大エントロピーは複雑さを排除します 。${\displaystyle 3{\text{ bits}}}$${\textstyle p_{i}={\frac {1}{8}}}$${\displaystyle 2.86{\text{ bits}}}$

上記の解析方法が実行不可能な場合は、状態確率を取得するために別の方法を使用できます。システムの入力（ドライバーセル）でランダムソースを使用して何世代にもわたって駆動し、状態確率を経験的に観察します。これを1000万世代のコンピューターシミュレーションで実行すると、結果は次のようになります。以下: ^[2]

と は両方ともシステム サイズとともに増加するため、それらの無次元比、つまり相対的な情報変動複雑度 が、異なるサイズのシステムを比較するために含められます。 3 セル オートマトンでは経験的結果と解析的結果が一致し、相対複雑度が10 セル程度で横ばいになることに注意してください。 ${\displaystyle \mathrm {H} }$${\displaystyle \sigma _{I}}$${\displaystyle \sigma _{I}/\mathrm {H} }$${\displaystyle 0.10}$

ベイツとシェパード、^[1] ${\displaystyle \sigma _{I}}$はすべての基本セルオートマトンルールに対して計算され、ルール 110 のように、ゆっくり動くグライダーやおそらくは静止した物体を示すルールは、 の大きな値と高い相関関係にあることが観察されました。したがって、証明するのが難しい普遍的な計算の候補ルールを選択するためのフィルターとして使用できます。 ${\displaystyle \sigma _{I}}$${\displaystyle \sigma _{I}}$

情報変動複雑性の公式の導出は動的システムにおける情報変動に基づいていますが、この公式は状態確率のみに依存するため、静的画像やテキストから導出される確率分布も含め、あらゆる確率分布に適用できます。

長年にわたり、原著論文^[1]は、複雑性理論、^[3]複雑系科学、^[4]複雑ネットワーク、^[5]カオスダイナミクス、^[6]多体局在エンタングルメント、^[7]環境工学、^[8]生態学的複雑性、^[9]生態学的時系列分析、^[10]生態系の持続可能性、^[11]大気^[12]と水^[13]汚染、水文学的ウェーブレット解析、^[14]土壌水流、^{[15] 土壌水分、[ 16] 源流流出、[17] 地下水深、[18] 航空交通管制、[19] 流れパターン [20] と洪水事象、[21] 位相幾何学、[22] 経済学、[23] 金属 [24] と電気 [25] 価格の市場予測、健康情報学、[26]}人間の^認知、^[ 27 ^]人間^の歩行^運動学^、 [ ^{28 ]}神経^学、[ ²⁹ ]^脳波解析^など、^さまざまな分野の研究者によって参照されてきました。^[30]教育、^[31]投資、^[32]人工生命^[33]美学。^[34]