モンテカルロ法と次元の呪い

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

モンテカルロ法と次元の呪いの違い

モンテカルロ法 vs. 次元の呪い

モンテカルロ法 (モンテカルロほう、Monte Carlo method, MC) とはシミュレーションや数値計算を乱数を用いて行う手法の総称。元々は、中性子が物質中を動き回る様子を探るためにスタニスワフ・ウラムが考案しジョン・フォン・ノイマンにより命名された手法。カジノで有名な国家モナコ公国の4つの地区（カルティ）の1つであるモンテカルロから名付けられた。ランダム法とも呼ばれる。. 次元の呪い（じげんののろい、The curse of dimensionality）という言葉は、リチャード・ベルマンが使ったもので、（数学的）空間の次元が増えるのに対応して問題の算法がなることを表している。 例えば、単位区間をサンプリングするには100個の点を等間隔で、かつ点間の距離を 0.01 以上にならないように配置すれば十分である。同じようなサンプリングを10次元の単位超立方体について行おうとすると、必要な点の数は 1020 にもなる。したがって、10次元の超立方体はある意味では単位区間の1018倍の大きさとも言える。 高次元ユークリッド空間の広大さを示す別の例として、単位球と単位立方体の大きさを次元を上げながら比較してみればよい。次元が高くなると、単位球は単位立方体に比較して小さくなっていく。したがってある意味では、ほとんど全ての高次元空間は中心から遠く、言い換えれば、高次元単位空間はほとんど超立方体の角で構成されており、「中間」がない。このことは、カイ二乗分布を理解する上で重要である。.

乱択アルゴリズム

乱択アルゴリズム（らんたくアルゴリズム、Randomized algorithm、ランダム・アルゴリズム）または確率的アルゴリズム（かくりつてき-、Probabilistic algorithm）は、その論理の一部に無作為性を導入したアルゴリズムである。通常のアルゴリズムでは自然数を順番にあてはめるような決定的な部分で、乱数による非決定的な選択を入れることで、「平均的に」よい性能を実現することを目的としている。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その期待値を「期待実行時間; expected runtime」と呼ぶ。最悪の場合に関して「無視できる」ほどに低い確率であることが、一般に、この類のアルゴリズムが効果的である要件となる。.

モンテカルロ法と乱択アルゴリズム · 乱択アルゴリズムと次元の呪い · 続きを見る »

マルコフ連鎖

マルコフ連鎖（マルコフれんさ、Markov chain）とは、確率過程の一種であるマルコフ過程のうち、とりうる状態が離散的（有限または可算）なもの（離散状態マルコフ過程）をいう。また特に、時間が離散的なもの（時刻は添え字で表される）を指すことが多い（他に連続時間マルコフ過程というものもあり、これは時刻が連続である）。マルコフ連鎖は、未来の挙動が現在の値だけで決定され、過去の挙動と無関係である（マルコフ性）。各時刻において起こる状態変化（遷移または推移）に関して、マルコフ連鎖は遷移確率が過去の状態によらず、現在の状態のみによる系列である。特に重要な確率過程として、様々な分野に応用される。.

マルコフ連鎖とモンテカルロ法 · マルコフ連鎖と次元の呪い · 続きを見る »

マルコフ連鎖モンテカルロ法

マルコフ連鎖モンテカルロ法（マルコフれんさモンテカルロほう、Markov chain Monte Carlo methods、MCMC）とは、求める確率分布を均衡分布として持つマルコフ連鎖を作成することをもとに、確率分布のサンプリングを行うアルゴリズムの総称である。M-H アルゴリズムやギブスサンプリングなどのランダムウォーク法もこれに含まれる。充分に多くの回数の試行を行った後のマルコフ連鎖の状態は求める目標分布の標本として用いられる。試行の回数を増やすとともにサンプルの品質も向上する。 求められる特性を持つマルコフ連鎖を作成することは通常難しくない。問題は許容できる誤差内で定常分布に収束する試行の回数を決めることである。適切な連鎖なら任意の位置から始めても定常分布に速く達し、これを高速混合（rapid mixing）とよぶ。 典型的なMCMCは常にある程度の初期値の影響が残るため目標分布しか近似することができない。CFTP法（）など、より洗練されたMCMCベースのアルゴリズムは完全標本を作成することができるが、より多くの計算と（期待値では有限だが）限界のない実行時間を要する。 このアルゴリズムの最も一般的な応用は多重積分を数値的に計算することである。ランダムに歩き回る粒子の集団を想定し、粒子が点を通過するたびに、その点の被積分関数の値を積分に加算する。粒子は次に積分への貢献が高い所を探して複数の仮の動作をする。このような方法はランダムウォーク法とよばれ、これは乱数的なシミュレーションつまりモンテカルロ法の一種である。従来のモンテカルロ法で用いられる被積分関数のランダムな標本が独立であるのに対して、MCMCで用いられる標本は相関がある。被積分関数を均衡分布に持つようなマルコフ連鎖を作成する必要があるが、多くの場合において容易に行うことができる。 多重積分はベイズ統計学、計算物理学、計算生物学などにしばしば現れるため、そのような分野でMCMC法も広く使われている。例としては や を参照のこと。.

マルコフ連鎖モンテカルロ法とモンテカルロ法 · マルコフ連鎖モンテカルロ法と次元の呪い · 続きを見る »

ラスベガス法

ラスベガス法（Las Vegas algorithm）は、間違った解を返さない乱択アルゴリズムを指す。すなわち、解を返すときは常に正しく、正しい解が求められない場合は失敗を通知する。換言すれば、ラスベガス法は答え（解）については賭けをせず、計算に使用するリソース量についてのみ賭けをする。さらに平均実行時間が入力長の多項式関数で押さられるようなラスベガス法は(efficient)であるという。ラスベガス法の単純な例にランダム化されたクイックソートがある。ピボット値をランダムに選択するクイックソートではソート結果は常に正しい。一般に無作為な情報に対してラスベガス法を使う際には、定義上、実行時間の上限を設けることが多い。.

モンテカルロ法とラスベガス法 · ラスベガス法と次元の呪い · 続きを見る »

粒子フィルタ

粒子フィルタ(Particle filter)、または逐次モンテカルロ法 (Sequential Monte Carlo: SMC)とは、シミュレーションに基づく複雑なモデルの推定法である。 この手法はふつうベイズモデルを推定するのに用いられ、バッチ処理であるマルコフ連鎖モンテカルロ法 (MCMC) の逐次 (オンライン) 版である。またこの手法は重点サンプリング法にも似たところがある。 うまく設計すると、粒子フィルタはMCMCよりも高速である。拡張カルマンフィルタや無香カルマンフィルタ (Unscented カルマンフィルタ) に対して、十分なサンプル点があればベイズ最適推定に近付くためにより精度が高くなることから、これらの代わりに用いられることがある。手法を組み合わせ、カルマンフィルタを粒子フィルタの提案分布として使うこともできる。.

モンテカルロ法と粒子フィルタ · 次元の呪いと粒子フィルタ · 続きを見る »

機械学習

機械学習（きかいがくしゅう、machine learning）とは、人工知能における研究課題の一つで、人間が自然に行っている学習能力と同様の機能をコンピュータで実現しようとする技術・手法のことである。.

モンテカルロ法と機械学習 · 機械学習と次元の呪い · 続きを見る »