投稿

再掲「チャイティンのΩとバエズのエントロピー」

【「チャイティンのΩとバエズのエントロピー」】 今回から、バエズのエントロピーの話を始めようと思います。といっても、今回は、バエズのエントロピーの式が、先日話したチャイティンが定義した不思議な数Ωの定義によく似ているという話で終わります。 https://youtu.be/ZjMfjlBxO5o?list=PLQIrJ0f9gMcPPgVvBB4BWA7-RuBmWLqqz 今回は、シャノンのエントロピーとコルモゴロフの複雑性について、いくつか基本的なことを確認したいと思います。 シャノンの理論は、 複数のオブジェクトの集まりをどのようにエンコードし、そうしたオブジェクトのシークエンスを如何に効率的に送るかについて考えます。それに対して、コルモゴロフの複雑性は、一つのオブジェクトを、最も効率的にエンコードすることを考えます。 ただ、「情報圧縮」という点では、二つの理論は共通の関心があります。 シャノンの理論では、例えば、アルファベットの集まりXがある確率分布に従う時、そのエントロピーH(X)を用いて、N文字のメッセージを。NH(X)ビットに情報圧縮できることを示せます。 コルモゴロフの複雑性理論では、次のような形で情報圧縮に関心を持ちます。 「Berryのパラドックス」というのがあります。  「30文字以下では定義されない最小の自然数B」 これはある意味、Bの定義ですが、Bは日本語では21文字で定義されています。 こうした「定義」「名前づけ」「記述」の曖昧さを避けるために、あるオブジェクトの「記述」はそれを出力するプログラムで与えられると考えます。 コルモゴロフの複雑性𝐶_𝑈 (𝑥)は、万能チューリングマシンUにプログラムpが与えられた時、xを出力するプログラムpのうち、最小のプログラムの長さ(|p|)です。その時、pは、オブジェクトの最小の記述を与えていると考えることができます。 こうした考えが威力を発揮するのは、あるビット列の「ランダムさ」を定義しようとする時です。 あるオブジェクトが、それより短い記述を持たない時、そのオブジェクトを「圧縮不可能」ということにしましょう。あるビット列が「ランダム」だと判断されるのは、それが「圧縮不可能」な時であると考えることができます。 Per Martin-Lofは、 1966年の論文 “The Definition o

Agenda 9/30マルゼミ

「コロモゴロフ複雑性とアルゴリズム論的情報理論」  Agenda    ● 第一部 ランダムさの不思議 エピソード 1 「ランダムさの不思議」( video   pdf    blog ) エピソード 2 「Randomness と Symmetry」 ( video   pdf   blog ) エピソード 3 「ランダムの力  — 量子論のインパクト」 ( video   pdf   blog )  エピソード 4 「ランダムさの定義の難しさ」 ( video   pdf   blog ) エピソード 5 「ランダムさ への新しいアプローチ」 ( video    pdf   blog )  ● 第二部 計算可能性理論とコロモゴロフの複雑性 エピソード 0 「コロモゴロフの複雑性」( video   pdf   blog ) エピソード 1 「すべての計算可能な関数は、プログラムで表現できる」 ( video   pdf   blog ) エピソード 2 「コロモゴロフ複雑性の「不変性」」( video   pdf   blog ) エピソード 3 「コロモゴロフ複雑性の「計算不能性」」 ( video   pdf   blog ) エピソード 4 「チャイティンの不完全性定理」 ( video   slide   blog )  ● 第三部 アルゴリズム論的熱力学 エピソード 4-1 「チャイティンのΩとバエズのエントロピー」 ( video pdf blog )

お詫びとお知らせ:9/3 マルゼミのタイトルを変更します

【 お詫びとお知らせ:9/3 マルゼミのタイトルを変更します】 9/3マルゼミのタイトルを、「計算科学とエントロピー」から「コロモゴロフ複雑性とアルゴリズム論的情報理論」へと変更したいと思っています。 予告した基本的なコンテンツや、現在展開中のショートムービーは、そのまま引継ぎますが、今回のセミナーでは、コロモゴロフ複雑性とシャノンの情報理論のエントロピーとの接点をあまりお話しすることができません。今回は、タイトルから、「エントロピー」を消そうと思いました。 タイトル、「計算科学と情報理論」でも良かったのですが、すこし一般的すぎると思います。いっそ、今回中心的に取り上げることのできるトピックをタイトルにしようと考えました。 セミナーは、次の三部構成です。  ● 第一部 ランダムさの不思議  ● 第二部 計算可能性理論とコロモゴロフの複雑性  ● 第三部 アルゴリズム論的熱力学 今週から、第三部の「アルゴリズム論的熱力学」のショートムービーの展開を始めます。お楽しみに。 セミナーに向けた資料は、次のページにまとめられています。ご利用ください。 https://www.marulabo.net/docs/info-entropy4/ セミナーのお申し込みは、次のサイトからお願いします。 https://info-entropy4.peatix.com/view    「コロモゴロフ複雑性とアルゴリズム論的情報理論」      Agendaとショートムービー・リンクのリスト    リンクにジャンプできる次のURLからご利用ください   https://maruyama097.blogspot.com/2021/09/agenda-93.html  ● 第一部 ランダムさの不思議 エピソード 2-1 「ランダムさの不思議」( video   pdf    blog ) エピソード 2-2 「Randomness と Symmetry」 ( video   pdf   blog ) エピソード 2-3 「ランダムの力  — 量子論のインパクト」 ( video   pdf   blog )  エピソード 2-4 「ランダムさの定義の難しさ」 ( video   pdf   blog ) エピソード 2-5 「ランダムさ への新しいアプローチ」 ( video    pdf  

コロモゴロフ複雑性の「計算不能性」

【 コロモゴロフ複雑性の「計算不能性」】 https://youtu.be/Iir7Y9WNcZk?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K コロモゴロフ複雑性には、重要な性質があります。 それは、コロモゴロフ複雑性は、xを出力するプログラムの最小の長さとして定義されるのですが、計算理論的には、それは「計算不能」です。 ここでは、そのことを見ていきましょう。 つぎのような関数Lを考えます。   𝐿(𝑛)=𝐾(𝑘)≥2𝑛 となるような最小の𝑘 関数 L : ℕ → 𝒪 は、nに対して、そのコロモゴロフ複雑性𝐾(𝑘)が2n 以上となるような最小の kを返します。もし、Kがすべてのnについて計算可能だとすると、Lもすべてのnについて計算可能です。   ここで、すべての𝑛に対して、𝐾(𝐿(𝑛))≥2𝑛 です。 なぜならば、すべての𝑛について、𝐿(𝑛)は、𝐾(𝐿(𝑛)) ≥ 2𝑛を満たす最小のものであるからです。 ここで、ある V : 𝒪  → ℕ  が、「最適」であるとしましょう。この時、𝐾=𝐾_𝑉 と書くことができます。前回見た「不変性定理」から、𝐾 ≤ 𝐾_𝐿 + 𝑐 である定数cが存在することがわかります。     𝐾_𝐿 の定義から、𝐾_𝐿 (𝐿(𝑛)) ≤ 𝑛 が成り立ちます。 なぜならば、𝐾_𝜑 (𝑦)=min⁡{ |𝑝|  :𝜑(𝑝)=𝑦 } で、𝜑=𝐿として、 𝐾_𝐿 (𝐿(𝑛))=min⁡{ |𝑝|  :𝐿(𝑝)=𝐿(𝑛) }となります。 𝑝=𝑛 の場合、L(𝑝)=𝐿(𝑛)  が成り立つので、𝐾_𝐿 (𝐿(𝑛)) ≤ 𝑛 がいえます。 そうすると、次の不等式が成り立ちます。   2𝑛 ≤ 𝐾(𝐿(𝑛)) ≤ 𝐾_𝐿 (𝐿(𝑛)) + 𝑐 ≤ 𝑛 + 𝑐    2𝑛 ≤ 𝑛 + 𝑐 から 𝑛 ≤ 𝑐 ということになります。 ただし、この不等式は、全ての n については成り立ちません。𝑛 > 𝑐 なるnについては矛盾します。 Kがすべてのnについて計算可能だと仮定すると、矛盾が導かれるので、Kは計算可能ではありません。 ------------ このショ

ランダムさ への新しいアプローチ

イメージ
【 ランダムさ への新しいアプローチ 】 https://youtu.be/Ks4iav2PR10?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K ランダムさへのアプローチは、1960年代の半ばに、旧ソヴィエトの数学者コロモゴロフとその学派が登場して、新しい段階に入りました。 「コロモゴロフ複雑性」を中心的な武器とした「アルゴリズム論的情報理論」は、チャーチ=チューリングらの計算理論との接点を深化し(Chaitinの「不完全性定理」)、また、シャノンの情報理論との結びつきを探求します(「条件付きエントロピー」、「相互エントロピー」)。 ここでは、まず、彼らのランダムさへのアプローチの概略を、次の三つのトピックで、紹介しようと思います。  ● 「オブジェクトの記述」=「プログラム」  ● プログラムの長さへの注目  ● 圧縮可能な情報と圧縮不可能な情報 【「オブジェクトの記述」=「プログラム」】 ある認識の対象を「記述」するには、いろいろな方法があります。 ・その定義を、記述する。 ・その特徴を、記述する。 ・その時間的変化を、記述する。 ・その意味を、記述する。 ・ … アルゴリズム論的情報理論では、少なくとも文字列として表現されるもの(それは、基本的には {0, 1}^∗ すなわち、0と1の並び に還元されるのですが)、その「記述」とは、その文字列を出力する「プログラム」に等しいと考えます。 【 プログラムの長さへの注目 】 私たちの認識の対象は、多様です。対象の「記述」=「プログラム」だとしても、ある対象を「記述」する「プログラム」も多様です。 一般的にいって、対象が複雑であれば、その「記述」、すなわちその対象を出力する「プログラム」も複雑なものになり、対象が単純なものであれば、その対象を出力する「プログラム」も単純なものになるのは、容易に想像できると思います。 プログラムの複雑さを、そのプログラムの「長さ」で代表させましょう。そうすることで、我々の認識の対象に、その複雑さを表す尺度を導入できます。 ある対象xを出力するプログラムは、複数あり得ます。この複数あるxを出力するプログラムで、最小の長さを持つものの長さを、xの「コロモゴロフ複雑性」と言います。 確認して欲しいのは、このように、xのコロモゴロフ複雑性は、一つの自然数だとい

ランダムさの定義の難しさ

【ランダムさの定義の難しさ】 「ランダムさ」を数学的に定義することは、実は、難しいのです。 確率論でも量子力学でも、「ランダムさ」は、もっとも基本的な概念の一つです。基本的な概念が数学的にうまく定義できないというのは、なにか奇妙なことのように思えるかもしれませんが、そういうことは、厳密な学と思われる思われる数学でも、よく起きることです。 例えば、幾何学では、「点」・「直線」・「図形」といった、最も基本的な概念は、うまく数学的に定義されている訳ではありません。集合論でも、「要素」・「集合」・「ある集合がある要素を含む」といった基本的な概念も、ある意味、天下り的に与えられます。 重要なことは、一つには、我々がそれらの概念についてある種の「直観」を持っていることと、もう一つには、それらの基本的な概念を、厳密ではなくとも、他のものとの関係で説明することができることです。 事実、確率論でも統計学でも量子論の解釈でも、「ランダムさ」を数学的にうまくは定義できなくても、それらの学は発展することが出来ました。ただ、いつまでもそれでいい訳ではありません。 数学的な認識の発展は、数学的認識の基礎に対する新しい反省を可能にします。「ランダムさ」についても、新しい数学的なアプローチが発見されます。 今回は、まず、「ランダムさの定義」の「失敗」を振り返ろうと思います。 19世紀のラプラスは、「ランダムさ」を次のように考えました。  「ある数列は、規則性をほとんど含まないなら、ランダムである。」 これは、「規則的」でないものでランダムさを特徴づけようとするものです。 確かに、「0が100個続く数列は規則的である。」これはいいです。ただ、3.14159....と続くπ の並びは、規則的でしょうか? あるいは、規則的でないものの例を、我々は具体的に示せるのでしょうか? 20世紀に入って、フォン・ミーゼスは、フォン・ミーゼスは、数列無限Sの「ランダムさ」の定義として、次の二つの条件を提案しました。  ● Sの1項目からn項目までの部分列S_{1:n }での1の出現確率は、nが大きくなるにつれて一定の確率に近づく  ● ある関数によって選ばれた任意のSの部分列についても、その部分列での1の出現確率は、nが大きくなるにつれて一定の確率に近づく これは正しいでしょうか? この「ランダムさ」の定義は、Sから

コロモゴロフ複雑性の「不変性」

【 コロモゴロフ複雑性の「不変性」】 コロモゴロフ複雑性\(𝐾_𝜑 (𝑦)\)の定義: 「yを出力するプログラムpの最小の長さ」の問題の一つは、この\(𝐾_𝜑 (𝑦)\)が、プログラムを実行する𝜑に強く依存していることです。       \(𝐾_𝜑 (𝑦)\) = min ⁡{ |𝑝| : 𝜑(𝑝)=𝑦 }  事実、プログラムが Pythonで書かれているか、Javaで書かれているか、Assemblerで書かれているか, …. で、同じyを出力するプログラムの長さは、それぞれ違います。 ただ、任意の𝜑に対して、次の不等式を満たすVが存在することを示すことが出来ます。 $$𝐾_𝑉 (𝑦) ≤ 𝐾_𝜑 (𝑦) + 𝑐$$ ここで、cは定数です。(証明は、後に回します) すべての𝜑に対して、この不等式を満たすVと定数cが存在することを、コロモゴロフ複雑性の「不変性定理」と呼びます。 この不等式を満たすVを「最適な」Vと呼ぶことにしましょう。   「不変性定理」は、 𝜑がいろいろ変わっても、\(𝐾_𝜑\) の(正確に言えば \(𝐾_𝜑 (𝑦) + 𝑐\) の)最小値𝐾_𝑉を与える 「最適な」Vが存在することを主張しています。 「不変性定理」で定義される「最適な」 V を使って、新しいコロモゴロフ複雑性 K(y)を次のように定義できます。 $$𝐾(𝑦)≡𝐾_𝑉 (𝑦)$$ この𝐾(𝑦)が、新しいコロモゴロフ複雑性の定義になります。 $$𝐾(𝑦)≡𝐾_𝑉 (𝑦) ≤ 𝐾_𝜑 (𝑦) + 𝑐$$ ですので、𝐾(𝑦)は、\(𝐾_𝜑 (𝑦)\)たちの取る値の最小値です。 もし、𝑉と𝑉 'が共に「最適」であるなら、 $$|𝐾_𝑉 (𝑦) − 𝐾_{𝑉′'} (𝑦)| ≤ 𝑐$$ が成り立ちます。 コロモゴロフは、論文”Three approaches to the quantitative definition of information” 1965 の中でこの定数について、次のように述べています。 「もちろん、特定の関数Vを考えることで、この定数cに関連した非決定性を避けることはできる。しかし、あからさまな恣意性抜きに、そうしたことができるか