情報揺動複雑性 - 百科事典

情報揺動複雑性とは、エントロピーに関する情報の揺動を定義した情報理論の量であり、動的システムの秩序と混沌の優位性の揺動から導き出されます。多くの異なる分野で複雑性の測定として使われています。1993年のBatesとShepardによる論文で紹介されました。

定義
离散動的システムの情報揺動複雑性は、ランダムな外部入力データにさらされたときのその状態の確率分布の関数です。ランダム数生成器やホワイトノイズシグナルなどの豊富な情報源でシステムを駆動することの目的は、信号処理で豊かな周波数を持つインパルスを使用するのと同様に、システムの内部動態を探ることです。

システムが

N

{\displaystyle N}

状態の可能性があり、状態確率

p
i

{\displaystyle p_{i}}

が既知であれば、その情報エントロピーは以下の通りです：





H
=
∑
i
=
1
N

p
i
I
i
=
−
∑
i
=
1
N

p
i
log
p
i
,


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


ここで

I
i
=
−
log
p
i
{\textstyle I_{i}=-\log p_{i}}

は状態

i
{\displaystyle i}

の情報内容です。

システムの情報揺動複雑性は、以下の通り定義されます：





σ
I
=
∑
i
=
1
N

p
i
(
I
i
−
H
)
2
=
∑
i
=
1
N

p
i
I
i
2
−
H
2
{\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}}}}


または





σ
I
=
∑
i
=
1
N

p
i
log
2
⁡
p
i
−
(
∑
i
=
1
N

p
i
log
p
i
)
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}}}.}


状態情報の揺動

σ
I
{\displaystyle \sigma _{I}}

は、全

p
i
=
1
N
{\textstyle p_{i}={\frac {1}{N}}}

である最大混乱度のシステムではゼロです；システムは単にランダムな入力を模倣します。




また、システムが完全な秩序で唯一の固定状態

(
p
1
=
1
)
{\textstyle (p_{1}=1)}

であれば、入力に関係なく

σ
I
{\displaystyle \sigma _{I}}

もゼロです。




これらの二つの極端な状態の間で、高い確率の状態と低い確率の状態が状態空間に住んでいるとき、




σ
I
{\displaystyle \sigma _{I}}

は非ゼロです。

情報の揺動が記憶と計算を可能にする
複雑な動的システムが時間とともに進むと、状態間の移行は外部刺激に不規則な方法で依存します。ある時は外部刺激に対してより敏感（不安定）で、別の時はより不敏感（安定）です。ある状態が複数の次の状態を持つ場合、外部情報がどれが次に来るかを決定し、システムは状態空間の特定の軌跡に従ってその情報を得ます。しかし、いくつかの異なる状態が同じ次の状態に導く場合、次の状態に入るときにその前にどの状態があったかに関する情報を失います。したがって、複雑なシステムは時間とともに進む間に情報の得失を交互に行い、記憶と忘却、一時的な情報保存または記憶、重要な計算の機能を持つものとみなされます。

状態間の移行に関連する情報の得失は状態情報に関連できます。状態

i
{\displaystyle i}

から状態

j
{\displaystyle j}

への移行の総情報得失

Γ
i
j
{\displaystyle \Gamma _{ij}}

は、状態

i
{\displaystyle i}

から出たときに得られる情報と、状態

j
{\displaystyle j}

に入るときに失われる情報の差です：





Γ
i
j
=
−
log
p
i
→
j
+
log
p
i
←
j
.


{\displaystyle \Gamma _{ij}=-\log p_{i\rightarrow j}+\log p_{i\leftarrow j}.}


ここで

p
i
→
j
{\textstyle p_{i\rightarrow j}}

は、現在の状態が

i
{\displaystyle i}

である場合に次の状態が

j
{\displaystyle j}

になる確率の前向き条件確率であり、

p
i
←
j
{\textstyle p_{i\leftarrow j}}

は現在の状態が

j
{\displaystyle j}

である場合に前の状態が

i
{\displaystyle i}

である確率の逆向き条件確率です。

条件確率は次の通り関連します：





p
i
j
=
p
i
p
i
→
j
=
p
i
←
j
p
j
.


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


条件確率を除去します：





Γ
i
j
=
−
log
(
p
i
j
/
p
i
)
+
log
(
p
i
j
/
p
j
)
=
log
p
i
−
log
p
j
=
I
j
−
I
i
.


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


したがって、システムが移行した結果として得られる総情報得失は、初めの状態から最終状態への状態情報の増加に依存します。これは、連続的な複数の移行に対しても真です。





Γ
=
Δ
I

は力と潜在エネルギーの関係を思い出させます。





I
{\displaystyle I}

は潜在エネルギー

Φ
{\displaystyle \Phi }

であり、

Γ
{\displaystyle \Gamma }

は力

F
{\displaystyle \mathbf {F} }

であり、以下の通りです：





F
=
∇
Φ

で

F
=
∇
Φ

です。外部情報はシステムを高情報潜在能の状態に「上り坂」に「押し」、情報保存を達成するために役立ちます。これと同様に、質量を上り坂に押して高重力潜在能の状態に保存するときのエネルギーが増加するのと同様に、保存されるエネルギーの量は上り坂の道のりに依存しません。同様に、保存される情報の量も初めの共通状態から最終の稀な状態への移行パスに依存しません。システムが高情報潜在能の稀な状態に達すると、それから共通状態に「落ちる」として、以前に保存された情報を失うことができます。





Γ
{\displaystyle \Gamma }

の標準偏差をその平均（ゼロ）について計算することが役立つかもしれませんが、

σ
I
{\displaystyle \sigma _{I}}

は状態空間の多移行記憶ループを考慮しており、したがってシステムの計算能力をより示すべきです。さらに、

σ
I
{\displaystyle \sigma _{I}}

は応用がより簡単で、移行が状態よりももっと多いことがあります。

混沌と秩序
外部情報に対して敏感（不安定）な動的システムは混沌の行動を示し、外部情報に対して不敏感（安定）なシステムは整然とした行動を示します。複雑なシステムはどちらの行動も示し、豊富な情報源にさらされたときにこれらの行動の間で揺動します。揺動の度は

σ
I
{\displaystyle \sigma _{I}}

で量化されます；これは時間とともに進む複雑なシステムにおける混沌と秩序の優位性の変化を捕らえます。

例：素子細胞自动機のルール110の変種
ソース：
素子細胞自动機のルール110の変種は、グライダーと呼ばれる、複雑なシステムに関連する現象としての集合的現象と見なされる凝聚して自発的に持続する細胞パターンの存在と相互作用に基づいて、汎用計算能力を持つことが証明されています。これらは、自动機細胞のグループがグライダーが彼らを通過していることを覚えているという能力を示唆しており、状態空間における情報の得失、不安定と安定、混沌と秩序の変化による状態空間の記憶ループの存在を期待できます。

ルール110に従う隣接する3細胞グループ、端-中央-端を考える：中心細胞の次の状態は、ルールに指定されたように自身と端細胞の現在の状態に依存します。

このシステムの情報揺動複雑性を計算するために、3細胞グループの両端に駆動細胞を接続し、次のようになります：driver→end-center-end←driver、ルールが両端細胞に適用できるようにします。次に、各可能な現在の状態と駆動細胞内容の各可能な組み合わせに対して次の状態がどれになるかを決定し、前向き条件確率を決定します。

このシステムの状態図は以下に示されています：円は状態を、矢印は状態間の移行を表します。このシステムの8つの可能な状態、1-1-1から0-0-0まで、3細胞グループの3ビット内容のオクテル相当数：7から0にラベル付けされています。移行矢印は前向き条件確率にラベル付けされています。駆動細胞からの情報の得失が起因する収束と散開の変動があることが注意されます。

前向き条件確率は特定の移行を引き起こす可能な駆動細胞内容の割合で決定されます。例えば、2つの駆動細胞内容の4つの可能な組み合わせの場合、状態7は状態5、4、1、0に移行しますので、以下の通りです：





p
7
→
5
{\textstyle p_{7\rightarrow 5}}

p
7
→
4
{\textstyle p_{7\rightarrow 4}}

p
7
→
1
{\textstyle p_{7\rightarrow 1}}

p
7
→
0
{\textstyle p_{7\rightarrow 0}}

それぞれ1/4または25％です。同様に、状態0は状態0、1、0、1に移行しますので、以下の通りです：





p
0
→
1
{\textstyle p_{0\rightarrow 1}}

p
0
→
0
{\textstyle p_{0\rightarrow 0}}

それぞれ1/2または50％です。




状態確率は次のように関連します：





p
j
=
∑
i
=
0
7

p
i
p
i
→
j
{\displaystyle p_{j}=\sum _{i=0}^{7}p_{i}p_{i\rightarrow j}}

∑
i
=
0
7

p
i
=
1.


{\displaystyle \sum _{i=0}^{7}p_{i}=1.}


これらの線形代数方程式は、以下の結果で解かれます：




情報エントロピーと複雑性は、次のように状態確率から計算されます：





H
=
−
∑
i
=
0
7

p
i
log
2
⁡
p
i
=
2.86
bits

,


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




σ
I
=
∑
i
=
0