過去・現在・未来

【 アルゴリズム論的熱力学 】 https://youtu.be/n2O8H0UDhqE?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K ここでは、John BaezとMike Stayの 2013年の論文 “Algorithmic Thermodynamics” を紹介します。https://arxiv.org/abs/1010.2067　 John Baez は、先に見た古典的な熱力学の観測量を、アルゴリズム論的情報理論の観測量で置き換えたモデルを考えました。 　　E(x)を、プログラムxの実行時間の対数 　　V(x)を、プログラムxの長さ 　　N(x)を、プログラムxの出力 とします。 この時、ある分配関数を考えて、確率分布 Gibbs Ensemble を構成します。 式については、pdfを参照ください。 https://drive.google.com/file/d/1rZY-ePmL9Ox1gPnkhL1fYFbO3kfjVXKx/view?usp=sharing これらから、観測量 E(x), V(x), N(x) の共役変数 𝛽,𝛾,𝛿を使って、期待値 E,V,Nを定義できます。 注意して欲しいのは、ここでの、E(x), V(x), N(x) の選択は、必然的なものではありません。ある意味、恣意的です。 用語については、まぎらわしいかもしれないですが、古典的な熱力学のGibbs Ensembleの例を流用しています。 重要なことは、、古典的な熱力学と同じ方法で、アルゴリズム論的熱力学が構成可能なことを示せるということです。それが、Gibbs Ensembleの方法の強みです。 また、計算時間、プログラムの長さ、プログラムの出力という観測量は、アルゴリズム論的情報理論にとっては、重要なものです。 さきには、「まぎらわしい」と言いましたが、次のように考えることもできます。 アルゴリズム論的熱力学のE、すなわち、計算時間の対数は、古典的熱力学のガスの内部エネルギーに似ている。 アルゴリズム論的熱力学のV、すなわち、プログラムの長さは、古典的熱力学の容器の体積に似ている。 アルゴリズム論的熱力学のN、すなわち、プログラムの出力は、古典的熱力学の分子の数に似ている。 はたして、こうしたアナロジーは、どこまで有効なものになる

【 Gibbs Ensemble と共役変数 】 https://youtu.be/xa845uRr8fY?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K ここでは、"Gibbs Ensemble" と「共役変数」という二つの概念を導入します。 式が少し複雑になるので、次のpdfファイルをご利用ください。 https://drive.google.com/file/d/1GAOuC99EKwpGY6JV8Pokj1dEdXkayg0q/view?usp=sharing まず、古典的な熱力学の単純な例から。 次のような確率分布と分配関数Zが与えられているとします。Eはエネルギーです。 　　p(x) = 1/Z (e^{βE(x)}) 　　Z = Σ e^{βE(x)} こうした系は、"Gibbs Ensemble" で、βはエネルギーEの「共役変数」です。 この時、β = 1/T （逆温度）になるのは、以前、見てきました。 （マルゼミ「情報とエントロピー 」を参照ください https://www.marulabo.net/docs/info-entropy2/　） 次に、もう少し複雑な例を考えます。 ガスの分子からなるある系について、エネルギーEだけでなく、体積V、圧力P、ガスの分子数Nについても観測量の期待値が与えられているすると、観測量とその共役変数に次のような対応があることがわかります。 　　　　観測量　　　　　共役変数 　　エネルギー E　　　　　1/T 　　体積          V 　　　　　P/T 　　分子数　    N_i             −μ_i/T  ----------- ショートムービーのpdfファイルは、次から利用できます。 https://drive.google.com/file/d/1GAOuC99EKwpGY6JV8Pokj1dEdXkayg0q/view?usp=sharing セミナー「コロモゴロフ複雑性とアルゴリズム論的情報理」のまとめページは、こちらです。 https://www.marulabo.net/docs/info-entropy4/ セミナーのAgendaはこちらです。 https://maruyama097.blogspot.com/

【 アルゴリズム論的情報理論への分配関数Zの応用 】 https://youtu.be/9Jnjz2qQULs?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K 先に見たのは、系のエネルギーEが、各部分系に\(𝐸_𝑖\)として分配されているとして、エントロピーが最大になる条件を求めるものでした。 確率が、 $$p_i = \frac{1}{Z}e^{−βE_i } $$ で与えられる時、 分配関数Zは　 $$Z = \sum  e^{−βE_i } $$ になります。 先にプログラムxの確率を次のように定義しました。 $$q_x = \frac{1}{Z}e^{−V(x) } $$ 実は、プログラムの確率がこの形をしているという積極的な理由があるわけではありません。 ただ、次のような形を作れば、熱力学の手法が応用できるというのが、この形を選んだ一番大きな理由です。 　　\(p_x = \frac{1}{Z} e^{−γV(x) }  \) 　　\(Z = \sum e^{−γV(x) }  \) この\(𝑝_𝑥\) と𝑍に、次のような解釈を与えることができます。 プログラムの集合上の確率分布Pのエントロピーを最大にする条件を考えます。拘束条件が、プログラムの長さだとすれば、その答えは、次のようになります。 $$p_x = \frac{1}{Z} e^{−γV(x) } $$ ここで、次のZが、\(p_x\)の和が1となること、すなわち、 \(p_x\)が確率であることを保証します。 $$Z = \sum e^{−γV(x) } $$ 先の \(q_x\) は、\(𝛾 = ln⁡ 2\)  と置いたものです。 こうした、確率変数 \(p_x\) と分配関数Zの関係は、一般的なものです。 今まで、拘束条件として、EやVの期待値を一つだけとってきたのですが、複数の観測の期待値から、同じような導出が可能です。 $$p_x = \frac{1}{Z} e^{−βE(x)−γV(x)−δN(x) } $$ ここでは、次のZが、\(p_x\) の和が1となること、すなわち、 \(p_x\) が確率であることを保証します。 $$Z = \sum  e^{−βE(x)−γV(x)−δN(x) }   $$ ----------- ショートムー

【 分配関数 Z – 統計力学の方法を振り返る 】 https://youtu.be/li-BsDN9JBY?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K 前回、アルゴリズム論的情報量に確率の概念を導入することができて、そうするとシャノンの情報量との関係がわかってくるという話をしました。アルゴリズム論的情報量をある数Zで割ると、その総和が1となるような確率p_n が定義できるということでした。 今回は、そのZがどういうものかという話です。二つの見方を紹介します。 一つは、アルゴリズム論的情報理論的には、ここで導入されたZの値は、ある条件のもとでは、チャイティンのΩに等しくなります。これは、とても面白いことなのですが、今回は深入りしません。 もう一つは、このZは、統計力学的には分配関数と言われるものと同じ役割を果たしているということです。今回は、改めて、統計力学の方法を振り返ってみようと思います。 ある条件が与えられた時に、ある式が極値をもつが条件を考えようというアプローチです。熱力学的には、ある条件として系のエネルギーの平均値Eが与えられた時、エントロピーSが最大になる条件を考えていきます。   与えられた拘束条件を、C1 = 0 , C2 = 0 の形で表せば、 　　S = S + α・C1 + β・C2 と書き換えることができます。（後ろの二項はゼロですので） この時、エントロピーSが最大になる必要な条件は、上の式を何らかの変数で微分したとき、その値がゼロになることです。こうして、α、βが満たすべき条件を得ることができます。 具体的には、拘束条件 C1として「確率の和は1になる」、拘束条件 C2として「系のエネルギーの平均値はEである」という条件を利用します。 こうしたやり方を「ラグランジェの未定乗数法」というのですが、その中で、Zを導入します。Zの具体的な導出は、スライドのpdfをご覧ください。 https://drive.google.com/file/d/1n4UA2AvgX_C_g-z-w3t22wzqxy2sYu_l/view?usp=sharing 詳しくは、マルゼミ「情報とエントロピー」を参照ください。 https://www.marulabo.net/docs/info-entropy2/ ここでは、拘束条件は二

【 アルゴリズム論的情報量に確率の概念を導入する 】 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 です。 こうして、次のように、アルゴリズム論的情報量とシャノン的情報量の対応を考えることができます。 事前には、我々は、ある

【 二つのアルゴリズム論的情報量の関係 】 Xをプログラムの集合、𝑉(𝑥) をプログラムの長さ、𝑁(𝑥)をプログラムxの出力とすると、二つの情報量の定義は、次のようになります、 第一の定義 （コロモゴロフ複雑性） $$𝑆_{𝑓𝑖𝑟𝑠𝑡} (𝑛) = min_{𝑥∈𝑋}⁡ \{ 𝑉(𝑥) : 𝑁(𝑥)=𝑛 \}$$ 第二の定義 $$𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑} (𝑛) = − log⁡ \sum_{𝑥∈𝑋, 𝑁(𝑥)=𝑛} 2^{−𝑉(𝑥) } $$ \(𝑆_{𝑓𝑖𝑟𝑠𝑡} (𝑛)と𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑} (𝑛)\)の関係を考えてみましょう\( S(𝑛) = − log⁡ \sum_{𝑥∈𝑋, 𝑁(𝑥)=𝑛}2^{−𝑉(𝑥) } \) で、nを出力とするようなプログラムxが一つしかなかったとしましょう。総和の項は一つしかないということです。 この時、 $$𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑 }(𝑛) = − log⁡ 2^{−𝑉(𝑥)} = 𝑉(𝑥)$$ となります。 nを出力とするようなプログラムxが一つしかないというのですから、V(x)は、𝑁(𝑥)=𝑛 を満たすプログラムの最小の長さになります。この時、 $$𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑} (𝑛)=𝑆_{𝑓𝑖𝑟𝑠𝑡} (𝑛) $$  になります。 もちろん、nを出力するプログラムは、複数存在し得ます。この時、アルゴリズム論的情報量の第二の定義による、 \(𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑} (𝑛)\)は、それらのプログラムの長さの項 \(− log⁡ 2^{−𝑉(𝑥)} \)が寄与しますので、その分、\(𝑆_{𝑓𝑖𝑟𝑠𝑡} (𝑛)\)より小さくなります。 $$𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑} (𝑛)≤ 𝑆_{𝑓𝑖𝑟𝑠𝑡} (𝑛)$$ 1974年に、Leonid Levinは、次のような定理を証明しました。すなわち、prefix free なプログラム言語については、すべてのnについて、次の式が成り立つような定数cが存在すると。 $$𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑} (𝑛) ≥ 𝑆_{𝑓𝑖𝑟𝑠𝑡} (𝑛) − 𝑐$$ このこと

【アルゴリズム論的情報量】 https://youtu.be/UgDNZzXIBik?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K ここでは、「アルゴリズム論的情報量」の定義を２つ与えます。 プログラム言語を固定します。ここで、プログラムは、有限のビット列で、プログラムが停止するなら、その出力も、有限のビット列です。 この時、ある有限なビット列の「アルゴリズム論的情報量」を、そのビット列を出力するプログラムの最小の長さで定義します。 この、ある自然数nの「アルゴリズム論的情報量」の第一の定義では、それが、nの「コロモゴロフ複雑性」に等しいと考えます。 「アルゴリズム論的情報量」＝「コロモゴロフ複雑性」を、通常の、シャノン情報理論での「情報量」＝「シャノン・エントロピー」とを比較してみましょう。 あるイベントxが確率pで起きたとしましょう。シャノンの情理論では、あるイベントxが起きたことを知った時に、「獲得した情報量」を、 　　−log ⁡𝑝 で表します。 “information gain” とか “information content”、“surprise” あるいは「自己情報量」といわれる情報量です。 ただ、シャノンの情報理論で、通常、「情報量」と言われるのは、X上の確率分布Pが与えられ、𝑥∈𝑋が確率𝑝_𝑥で起きる時、次の式で与えられる量です。 　　𝑆(𝑃 ) = −∑_(𝑥∈𝑋) 𝑝_𝑥  log ⁡𝑝_𝑥  これをシャノン・エントロピー と呼びます。 ただ、この「情報量」＝「エントロピー」は、先に見た「アルゴリズム論的情報量」と似ているようには見えませんね。 通常のシャノンの「情報量」との関係を、もっと分かりやすくするために、「アルゴリズム論的情報量」の二番目の定義を導入することにしましょう。 引き続き、プログラムは、有限のビット列だと考えます。もちろん、すべての有限のビット列が停止するプログラムを与えるわけではありません。  Xをプログラムのビット列の集合とする時、 𝑥∈𝑋なら任意のビット列yについて、𝑥𝑦∉𝑋とします。プログラム 𝑥で始まり、その後ろに𝑦をつなげた𝑥𝑦は、プログラムのビット列にはならないということです。 この条件を満たす時、Xをprefix free と言いま