コルモゴロフ複雑性とランダム

ショートカット: 違い、類似点、ジャカード類似性係数、参考文献。

コルモゴロフ複雑性とランダムの違い

コルモゴロフ複雑性 vs. ランダム

ルモゴロフ複雑性（コルモゴロフふくざつせい、Kolmogorov complexity）とは、計算機科学において有限長のデータ列の複雑さを表す指標のひとつで、出力結果がそのデータに一致するプログラムの長さの最小値として定義される。コルモゴロフ複雑度、コルモゴロフ＝チャイティン複雑性 (Kolmogorov-Chaitin complexity) とも呼ばれる。 コルモゴロフ複雑性の概念は一見すると単純なものであるが、チューリングの停止問題やゲーデルの不完全性定理と関連する深遠な内容をもつ。コルモゴロフ複雑性やその他の文字列やデータ構造の複雑性の計量を研究する計算機科学の分野はアルゴリズム情報理論と呼ばれており、1960 年代末にアンドレイ・コルモゴロフ、レイ・ソロモノフ、グレゴリー・チャイティンによって創始された。. ランダム（random）とは、事象の発生に法則性（規則性）がなく、な状態である。ランダムネス（randomness）、無作為性（むさくいせい）ともいう。 事象・記号などのランダムな列には秩序がなく、理解可能なパターンや組み合わせに従わない。個々のランダムな事象は定義上予測不可能であるが、多くの場合、何度も試行した場合の結果の頻度は予測可能である。例えば、2つのサイコロを投げるとき、1回ごとの出目は予測できないが、合計が7になる頻度は4になる頻度の2倍になる。この見方では、ランダム性とは結果の不確実性の尺度であり、確率・情報エントロピーの概念に適用される。 数学、確率、統計の分野では、ランダム性の正式な定義が使用される。統計では、事象空間の起こり得る結果に数値を割り当てたものを確率変数(random variable)という。この関連付けは、事象の確率の識別および計算を容易にする。確率変数の列を(random sequence)という。ランダム過程（不規則過程、確率過程）は、結果が決定論的パターンに従わず、確率分布によって記述される進化に従う確率変数の列である。これらの構造と他の構造は、確率論や様々なランダム性の応用に非常に有用である。 ランダム性は、よく定義された統計的特性を示すために統計で最も頻繁に使用される。ランダムな入力（や擬似乱数発生器など）に依存するモンテカルロ法は、計算科学などの科学において重要な技術である。これに対し、では乱数列ではなく一様分布列を使用している。 無作為抽出(random selection)は、ある項目を選択する確率が母集団内におけるその項目の割合と一致している集団から項目を選択する方法である。例えば、赤い石10個と青い石90個を入れた袋に入れた場合、この袋から何らかのランダム選択メカニズムによって石を1個選択した時にそれが赤い石である確率は1/10である。しかし、ランダム選択メカニズムによって実際に10個の石を選択したときに、それが赤1個・青9個であるとは限らない。母集団が識別可能な項目で構成されている状況では、ランダム選択メカニズムは、選択される項目に等しい確率を必要とする。つまり、選択プロセスが、母集団の各メンバー（例えば、研究対象）が選択される確率が同じである場合、選択プロセスはランダムであると言うことができる。.

乱数列

乱数列（らんすうれつ）とはランダムな数列のこと。 数学的に述べれば、今得られている数列 x1, x2,..., xn から次の数列の値 xn+1 が予測できない数列。乱数列の各要素を乱数という。.

コルモゴロフ複雑性と乱数列 · ランダムと乱数列 · 続きを見る »

チャイティンの定数

チャイティンの定数（チャイティンのていすう、Chaitin's constant）は、計算機科学の一分野であるアルゴリズム情報理論の概念で、非形式的に言えば無作為に選択されたプログラムが停止する確率を表した実数である。グレゴリー・チャイティンの研究から生まれた。停止確率（ていしかくりつ、Halting probability）とも。 停止確率は無限に多数存在するが、Ω という文字でそれらをあたかも1つであるかのように表すのが普通である。Ω はプログラムを符号化する方式に依存するので、符号化方式を特定せずに議論する場合は Chaitin's construction と呼ぶことがある。 個々の停止確率は正規かつ超越的な実数であり、計算不可能である。つまりその各桁を列挙するアルゴリズムは存在しない。.

コルモゴロフ複雑性とチャイティンの定数 · チャイティンの定数とランダム · 続きを見る »

レイ・ソロモノフ

レイ・ソロモノフ（Ray Solomonoff、1926年7月25日 - 2009年12月7日）はアメリカの人工知能学者であり、アルゴリズム情報理論の創始者の1人。また、algorithmic probability を考案し、機械学習と予測と確率に基づく人工知能の分野を創始した。1956年、非意味論的機械学習についての論文を発表している。 1960年に algorithmic probability についてカリフォルニア工科大学での会議で発表し、同年2月には "A Preliminary Report on a General Theory of Inductive Inference" という論文を発表。1964年には "A Formal Theory of Inductive Inference" の第一部と第二部を発表し、さらに考え方を明確化した。そこからコルモゴロフ複雑性とアルゴリズム情報理論が発展した。 algorithmic probability は、オッカムの剃刀と多説明原理の組合せを数学的に定式化したものである。それは与えられた観察結果を説明するそれぞれの仮説（アルゴリズム、プログラム）に確率値を割り当てる機械に依存しない手法であり、最も単純な仮説が最も高い確率を割り当てられ、仮説が複雑になるほど割り当てる確率が低くなる。 他にも帰納推論の一般理論でも知られているが、確率的手法を用いて難しい問題を機械で解くという人工知能研究の過程で他にも様々な発見をしている。.

コルモゴロフ複雑性とレイ・ソロモノフ · ランダムとレイ・ソロモノフ · 続きを見る »

アルゴリズム的ランダムな無限列

アルゴリズム的ランダムな無限列（あるごりずむてきらんだむなむげんれつ、Algorithmically random sequence）、あるいは単にランダムな列は、直感的にはどんなアルゴリズムにとってもランダムに見える二進無限列のことを言う。この定義は有限文字の列にも上手く適用される。ランダムな列はアルゴリズム情報理論において中心となる対象である。実行時間に特定の上限のあるアルゴリズムや神託への伺いを許したアルゴリズムなど、いくつかの異なった種類のアルゴリズムが考えられ、それに応じて異なったランダムネスの概念が存在する。もっとも良く知られているのはマルティンレーフランダムネス（1ランダムネスとも言う）であるが、もっと強いランダムネスや弱いランダムネスも存在する。単に「ランダム」と言った場合には、マルティンレーフランダムであることを意味することが多い。二進無限列は単位区間の実数と同一視できるので、ランダムな2進無限列はランダムな実数と呼ばれることもある。さらに、二進無限列は自然数の集合の特性関数とも同一視されるので、自然数の集合と見ることもある。二進のマルティンレーフランダムの無限列のクラスはRANDやMLRで表される。.

アルゴリズム的ランダムな無限列とコルモゴロフ複雑性 · アルゴリズム的ランダムな無限列とランダム · 続きを見る »

アルゴリズム情報理論

アルゴリズム情報理論（あるごりずむじょうほうりろん、Algorithmic information theory）は、情報理論と計算機科学の一分野であり、計算理論や情報科学とも関連がある。グレゴリー・チャイティンによれば、「シャノンの情報理論とチューリングの計算複雑性理論をシェイカーに入れて、力いっぱいシェイクしてできたもの」である。.

アルゴリズム情報理論とコルモゴロフ複雑性 · アルゴリズム情報理論とランダム · 続きを見る »

アンドレイ・コルモゴロフ

アンドレイ・ニコラエヴィッチ・コルモゴロフ（Андре́й Никола́евич Колмого́ров, Andrey Nikolaevich Kolmogorov, 1903年4月25日 - 1987年10月20日）はロシアの数学者であり、確率論および位相幾何学の大きな発展に寄与した。彼以前の確率論はラプラスによる「確率の解析的理論」に基づく古典的確率論が中心であったが、彼が「測度論に基づく確率論」「確率論の基礎概念（1933年）」で公理主義的確率論を立脚させ、現代確率論の始まりとなった。 初期には直観論理やフーリエ級数に関する研究を行っており、乱流や古典力学に関する研究成果もある。また彼はアルゴリズム情報理論の創始者でもある。なお、イズライル・ゲルファント、ウラジーミル・アーノルドをはじめ、コルモゴロフには数多くの弟子がいる。.

アンドレイ・コルモゴロフとコルモゴロフ複雑性 · アンドレイ・コルモゴロフとランダム · 続きを見る »

カオス理論

論（カオスりろん、、、）は、力学系の一部に見られる、数的誤差により予測できないとされている複雑な様子を示す現象を扱う理論である。カオス力学ともいう。 ここで言う予測できないとは、決してランダムということではない。その振る舞いは決定論的法則に従うものの、積分法による解が得られないため、その未来（および過去）の振る舞いを知るには数値解析を用いざるを得ない。しかし、初期値鋭敏性ゆえに、ある時点における無限の精度の情報が必要であるうえ、（コンピューターでは無限桁を扱えないため必然的に発生する）数値解析の過程での誤差によっても、得られる値と真の値とのずれが増幅される。そのため予測が事実上不可能という意味である。.

カオス理論とコルモゴロフ複雑性 · カオス理論とランダム · 続きを見る »

グレゴリー・チャイティン

レゴリー・チャイティン（Gregory "Greg" J. Chaitin, 1947年 - ）は、アルゼンチン出身、アメリカ在住の数学者、コンピュータ科学者。 60年代に情報理論の分野に、ゲーデルの不完全性定理とよく似た現象を見いだす。つまり、その分野上での決定不可能な命題を発見し別種の不完全性定理を得た。チャイティンの定理によると、十分な算術を表現可能などのような理論においても、いかなる数であろうともcよりも大きなコルモゴロフ複雑性を有することがその理論上では証明できないような、上限 c が存在する。ゲーデルの定理が嘘つきのパラドックスと関係しているのに対し、チャイティンの結果はベリーのパラドックスに関係している。 1995年に、メイン大学から博士号を授与される。IBMのトーマス・J・ワトソン研究所に勤務した後、現在はリオデジャネイロ連邦大学に在籍。 幾つかの本を執筆しており、日本語に訳されている。.

グレゴリー・チャイティンとコルモゴロフ複雑性 · グレゴリー・チャイティンとランダム · 続きを見る »

円周率

円周率（えんしゅうりつ）は、円の周長の直径に対する比率として定義される数学定数である。通常、ギリシア文字 （パイ、ピー、ラテン文字表記: ）で表される。数学をはじめ、物理学、工学といった様々な科学分野に出現し、最も重要な数学定数とも言われる。 円周率は無理数であり、その小数展開は循環しない。円周率は、無理数であるのみならず、超越数でもある。 円周率の計算において功績のあったルドルフ・ファン・コーレンに因み、ルドルフ数とも呼ばれる。ルドルフは、小数点以下35桁までを計算した。小数点以下35桁までの値は次の通りである。.

コルモゴロフ複雑性と円周率 · ランダムと円周率 · 続きを見る »

複雑性

複雑性（ふくざつせい、complexity）という用語は、多数の部品が入り組んで配置された何らかのものを特徴付ける言葉として使われる。科学として複雑性を研究するアプローチはいくつか存在しており、本項目ではそれらを概説する。マサチューセッツ工科大学のセス・ロイドは、複雑性の定義を32種類集めてプレゼンテーションしたことがあるという。.

コルモゴロフ複雑性と複雑性 · ランダムと複雑性 · 続きを見る »

擬似乱数

擬似乱数（ぎじらんすう、pseudorandom numbers）は、乱数列のように見えるが、実際には確定的な計算によって求めている擬似乱数列による乱数。擬似乱数列を生成する機器を擬似乱数列生成器、生成アルゴリズムを擬似乱数列生成法と呼ぶ。 真の乱数列は本来、規則性も再現性もないものであるため、本来は確定的な計算によって求めることはできない（例：サイコロを振る時、今までに出た目から次に出る目を予測するのは不可能）。一方、擬似乱数列は確定的な計算によって作るので、その数列は確定的であるうえ、生成法と内部状態が既知であれば、予測可能でもある。 ある擬似乱数列を、真の乱数列とみなして良いかを確実に決定することはできない。シミュレーション等の一般的な用途には、対象とする乱数列の統計的な性質が、使用対象とする目的に合致しているかどうかを判断する。これを検定と言い、各種の方法が提案されている。 しかし、特に暗号に使用する擬似乱数列については注意が必要であり、シミュレーション等には十分な擬似乱数列生成法であっても、暗号にそのまま使用できるとは限らない。暗号で使用する擬似乱数列については暗号論的擬似乱数の節および暗号論的擬似乱数生成器の記事を参照。.

コルモゴロフ複雑性と擬似乱数 · ランダムと擬似乱数 · 続きを見る »