アルゴリズム論的情報量に確率の概念を導入する

【 アルゴリズム論的情報量に確率の概念を導入する 】

https://youtu.be/x24csujO1Vk?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K

前回は、アルゴリズム論的情報量の、見かけが異なる二つの定義が、同じものであることを見てきました。今回は、その結果を踏まえて、アルゴリズム論的情報量が、シャノンの情報量と等しいということを見ていきたいと思います。

まず、シャノン的情報量（information gain）とアルゴリズム論的情報量を比較してみましょう。いずれも − log⁡ 𝑋という形をしています。

ただ、 −log⁡ 𝑋のXの部分は、ずいぶん違っています。シャノン的情報量の場合のpは0≤𝑝≤1を満たす「確率」と定義されていますが、アルゴリズム論的情報量ではそうではありません。

アルゴリズム論的情報量には、確率の概念がかけています。そのままでは、アルゴリズム論的情報量と、シャノンの情報量の対応づけは難しいです。

ただ、うまい方法があります。

アルゴリズム論的情報量の対数の内側の量について、ある定数Zを選んで、次のような量𝑝_𝑛を定義します。

この時、p_nが確率であることを示すことができます。（ 0 ≤ p_n ≤ 1 、かつ Σ p_i = 1 )

【 式は、Facebookやメールでは、表現しにくいものも多いので、次のスライドのodfをご覧ください。https://drive.google.com/file/d/1QPs2nqbZxWGhf1NRpM27YR5J3Jc4g9Vq/view?usp=sharing  】

p_nの定義から、次の式を導くことができます。

　　𝑆(𝑛) = − log⁡ p_n  − log⁡𝑍 

これから、nのアルゴリズム論的情報量であるS(n)は、定数の差を除けば、−log⁡p_n  に等しいことがわかります。−log⁡ p_n は、シャノンのinformation gainの情報量です。

どんなinformation gain かと言えば、確率分布Pに従う自然数の集合から、ランダムに一つのnを選んだときに、得られる情報が、−log⁡ p_n です。

こうして、次のように、アルゴリズム論的情報量とシャノン的情報量の対応を考えることができます。

事前には、我々は、ある数nがランダムに選ばれたプログラムの出力であることしか知らないとしましょう。nのアルゴリズム論的情報量は、プログラムの選択をおこなうことで、この数について我々が学ぶ、シャノン的information gain に等しいということになります。

アルゴリズム論的情報量とシャノンの自己情報量は同じものであることを示すことができました。次には、アルゴリズム論的情報理論で、どのようにシャノン的エントロピー概念を扱うのか見ていきたいと思います。

-----------

ショートムービーのpdfファイルは、次から利用できます。https://drive.google.com/file/d/1QPs2nqbZxWGhf1NRpM27YR5J3Jc4g9Vq/view?usp=sharing

セミナー「コロモゴロフ複雑性とアルゴリズム論的情報理」のまとめページは、こちらです。https://www.marulabo.net/docs/info-entropy4/

セミナーのAgendaはこちらです。https://maruyama097.blogspot.com/2021/09/agenda-93.html

セミナーへのお申し込みは、次のサイトからお願いします。
https://info-entropy4.peatix.com/view