モンテカルロアルゴリズム

コンピューターにおいて、モンテカルロアルゴリズムとは、ある確率（通常は小さい確率）で出力が不正確になる可能性のあるランダム化アルゴリズムです。このようなアルゴリズムの例として、カーガー・スタインアルゴリズム^[1]と最小フィードバックアークセットのモンテカルロアルゴリズム^[2]が挙げられます。この名前は、ギャンブルの象徴として世界中でよく知られているモナコ公国のモンテカルロカジノに由来しています。「モンテカルロ」という用語は、1947年にニコラ・メトロポリスによって初めて導入されました。^[3]

ラスベガスアルゴリズムはモンテカルロアルゴリズムの双対であり、誤った答えを返すことはありません。ただし、処理の一環としてランダムな選択を行う場合があります。その結果、同じ入力であっても、実行ごとに所要時間が異なる場合があります。モンテカルロアルゴリズムによって返される答えが正しいかどうかを検証する手順があり、正解の確率が0より上に制限されている場合、確率1でアルゴリズムを繰り返し実行し、答えを検証すると、最終的に正解が得られます。このプロセスがラスベガスアルゴリズムであるかどうかは、確率1で停止することが定義を満たすかどうかによって決まります。

量子モンテカルロアルゴリズムのフローチャート

片側誤差と両側誤差

決定論的アルゴリズムによって返される答えは常に正しいと期待されますが、モンテカルロアルゴリズムの場合はそうではありません。決定問題の場合、これらのアルゴリズムは一般に偽バイアスまたは真バイアスに分類されます。偽バイアスのあるモンテカルロアルゴリズムは、偽を返す場合は常に正しいです。真バイアスのあるアルゴリズムは、真を返す場合は常に正しいです。これは片側誤差のあるアルゴリズムについて説明していますが、バイアスのないアルゴリズムもあります。これらは両側誤差があると言われています。それらが提供する答え（真または偽）は、ある限られた確率で正しくないか正しくないかになります。^[要出典]

例えば、ソロベイ・ストラッセン素数判定は、与えられた数が素数かどうかを判定するために使用されます。素数入力に対しては常に真と判定されますが、合成数入力に対しては、少なくとも1 ⁄ 2の確率で偽と判定され、1 ⁄ 2未満の確率で真と判定されます。したがって、このアルゴリズムからの偽の判定結果は確実に正しいのに対し、真の判定結果は不確定なままです。これは1 ⁄ 2正解の偽バイアスアルゴリズムと呼ばれます。^[要出典]

増幅

片側誤差を持つモンテカルロアルゴリズムの場合、アルゴリズムをk回実行することで失敗確率を低減（成功確率を増幅）できます。1 ⁄ 2正解で偽バイアスのあるソロベイ・ストラッセンアルゴリズムを再び考えてみましょう。このアルゴリズムを複数回実行し、 k回の反復で偽の応答に達した場合は偽の回答を返し、それ以外の場合は真を返します。したがって、数が素数であれば回答は常に正解であり、数が合成数であれば、少なくとも1−(1−1 ⁄ 2) k = 1−2 −k の確率で正解となります。両側誤差を^持つ モンテカルロ^決定アルゴリズムの場合、アルゴリズムをk回実行し、回答の多数決関数を返すことで、失敗確率を再び低減できます。 ^[要出典]

複雑度クラス

複雑性クラス BPP は、両側誤りの確率が制限された多項式時間モンテカルロアルゴリズムで解くことができる決定問題を表します。複雑性クラスRP は、片側誤りの確率が制限されたモンテカルロアルゴリズムで解くことができる問題を表します。つまり、正解が偽の場合、アルゴリズムは常にそのように判断しますが、正解が真である場合でも誤って偽と判断することがあります。^[4]対照的に、複雑性クラスZPP は、多項式期待時間ラスベガスアルゴリズムで解ける問題を表します。ZPP ⊆ RP ⊆ BPP ですが、これらの複雑性クラスが互いに異なるかどうかはわかっていません。つまり、モンテカルロアルゴリズムはラスベガスアルゴリズムよりも計算能力が高い可能性がありますが、これは証明されていません。^[4]別の複雑性クラスPP は、コインを投げるよりも正確ですが、誤り確率が必ずしも1 ⁄ 2から制限されるとは限らない多項式時間モンテカルロアルゴリズムによる決定問題を表します。^[4]

モンテカルロ法とラスベガス法のアルゴリズムのクラス

ランダム化アルゴリズムは主にモンテカルロ法とラスベガス法という2つの主要な種類に分けられますが、これらは階層の最上位に過ぎず、さらに分類することができます。^[4]

• ラスベガス
  • シャーウッド - 「ラスベガスのパフォーマンスと効率性に優れた特別なケース」
  • 数値的—「数値的ラスベガス」
• モンテカルロ
  • アト​​ランティックシティ—「モンテカルロの誤差限定の特殊ケース」
  • 数値的—「数値近似モンテカルロ法」

「ラスベガス法とモンテカルロ法はどちらも決定問題、つまり決定版の問題を扱っています。」^[4]「しかし、これは誤った印象を与え、これらのアルゴリズムをそのような問題に限定するべきではありません。どちらのタイプのランダム化アルゴリズムも数値問題、つまり単純な「はい」/「いいえ」ではなく、本質的に数値的な結果を受け取る必要がある問題にも使用できます。」^[4]

ラスベガス法とモンテカルロ法の比較

	効率	最適	故障（LV）/エラー（MC）
ラスベガス（LV）	確率的	確実	${\displaystyle <{\tfrac {1}{2}}}$
シャーウッド	確実、あるいは確率的シャーウッド （通常のLVよりも強い結合）	確実	0
数値的	確率的、確実、または シャーウッド確率的	確実	${\displaystyle <{\tfrac {1}{2}}}$ または0
モンテカルロ（MC）	確実	確率的	${\displaystyle <1}$ （繰り返し実行することで指数関数的に増加する確率） アルゴリズムの有用性を阻害する。典型的なケースは、 ${\displaystyle <{\tfrac {1}{2}}}$
アトランティックシティ	確実	確率的	${\displaystyle <{\tfrac {1}{4}}}$
数値的	確実	確率的	${\displaystyle <1}$ （アルゴリズムの種類によって異なります）

前の表は、モンテカルロ法とラスベガス法のランダム化アルゴリズムの一般的な枠組みを表しています。^[4]数学記号の代わりにを使うことで、最悪の場合の確率を等しくすることができます。^[4]${\displaystyle <}$ ${\displaystyle \leq}$

応用

統計学において、ハミルトンモンテカルロ法は、観測データに基づいて観測されていないパラメータを再構築するために一般的に用いられる手法です。ベイズの定理は、あらゆる可能なパラメータセットの事後確率を計算するために使用され、物理シミュレーションはその事後確率分布をサンプリングするために使用されます

よく知られているモンテカルロアルゴリズムには、ソロベイ・シュトラッセン素数判定、ベイリー・PSW素数判定、ミラー・ラビン素数判定、そして計算群論におけるシュライアー・シムズアルゴリズムの高速版などがある。確率が事前に分かっておらず経験的に決定される確率最適化（SO）グループのアルゴリズムでは、モンテカルロとそのようなアルゴリズムを統合して「事前に計算された確率の境界と確率最適化コンポーネントの両方を持つ」ことが可能な場合がある。^[4]「そのようなアルゴリズムの例としては、Ant Inspired Monte Carloがある。」^{[4] [5]}このようにして、「SOの欠点は軽減され、解の信頼性が確立された。」^{[4] [5]}

参照

• アト​​ランティックシティアルゴリズム
• 計算統計
• モンテカルロ法
• ラスベガス・アルゴリズム

参考文献

引用文献

1. Karger, David R.; Stein, Clifford (1996). 「最小カット問題への新しいアプローチ」. J. ACM . 43 (4): 601– 640. doi : 10.1145/234533.234534 . ISSN  0004-5411. S2CID  5385337
2. Kudelić, Robert (2016-04-01). 「最小フィードバックアーク集合問題のためのモンテカルロランダム化アルゴリズム」. Applied Soft Computing . 41 : 235– 246. doi :10.1016/j.asoc.2015.12.018.
3. メトロポリス、N. (1987)。 「モンテカルロ法の始まり」(PDF)。ロス アラモス サイエンス(スタニスワフ ウラムに捧げられた 1987 年の特別号): 125–130。
4. Kudelić, Robert; Ivković, Nikola; Šmaguc, Tamara (2023). 「ランダム化アルゴリズムの概要」 Choudrie, Jyoti; Mahalle, Parikshit N.; Perumal, Thinagaran; Joshi, Amit (編). IoT with Smart Systems . Lecture Notes in Networks and Systems. Vol. 720. シンガポール: Springer Nature. pp.  651– 667. doi :10.1007/978-981-99-3761-5_57. ISBN 978-981-99-3761-5。
5. Kudelić, Robert; Ivković, Nikola (2019). 「最小フィードバックアークセットのためのアリに着想を得たモンテカルロアルゴリズム」 . Expert Systems with Applications . 122 : 108–117 . doi :10.1016/j.eswa.2018.12.021. ISSN  0957-4174

さらに詳しい情報

• モトワニ、ラジーブ、ラガヴァン、プラバカール（1995年）。『ランダム化アルゴリズム』。ニューヨーク：ケンブリッジ大学出版局。ISBN 0-521-47465-5。
• コーメン、トーマス・H.、レイサーソン、チャールズ・E.、リベスト、ロナルド・L.、スタイン、クリフォード(2001)。「第5章 確率解析とランダム化アルゴリズム」アルゴリズム入門（第2版）。ボストン：MITプレスおよびマグロウヒル。ISBN 0-262-53196-8。
• ケネス・A・バーマン、ジェローム・L・ポール (2005)。「第24章 確率的アルゴリズムとランダム化アルゴリズム」。アルゴリズム：逐次、並列、分散。ボストン：コーステクノロジー。ISBN 0-534-42057-5。