特許ウォッチ

公開番号2025105525
公報種別公開特許公報(A)
公開日2025-07-10
出願番号2024224650
出願日2024-12-20
発明の名称棄却なしの並列試行マルコフ連鎖モンテカルロ法を用いた統計的サンプリング
出願人富士通株式会社,ザガバニングカウンシルオブザユニバーシティオブトロント,THE GOVERNING COUNCIL OF THE UNIVERSITY OF TORONTO
代理人弁理士法人ITOH
主分類G06F 17/18 20060101AFI20250703BHJP(計算;計数)
要約【課題】棄却なしの並列試行マルコフ連鎖モンテカルロ法を用いた統計的サンプリングを提供する。
【解決手段】方法は、系の推定された状態を表すレプリカを取得することを含みうる。第1の温度のセットの中で最低温度を有する第1のレプリカが識別され、メモリの第1の状態に書き込まれてもよい。方法は、各レプリカに対して第1のマルコフ連鎖モンテカルロ(MCMC)試行を実行して、それぞれのレプリカの温度の変化の影響をシミュレートすることを含みうる。第2の温度のセットの中で最低温度を有する第2のレプリカが識別され、メモリの第2の状態に書き込まれてもよい。第1および第2のレプリカの第1および第2の多重度が計算されてもよく、多重度は、棄却をもたらすであろうMCMC試行の数の推定を表す。システムの終了状態の表現が、第1のレプリカ、第2のレプリカ、第1の多重度、および第2の多重度に基づいて生成されうる。
【選択図】図1

特許請求の範囲【請求項１】
複数のレプリカを取得する段階であって、前記複数のレプリカの各レプリカが系のそれぞれの推定された状態を表す複数のビットを含む、段階と；
前記複数のレプリカのそれぞれのレプリカを第1の温度セットの異なる対応する温度に割り当てる段階と；
前記第1の温度セットにおける他のどの温度よりも低い第1の温度を有する第1のレプリカを識別する段階と；
前記第1のレプリカを、メモリの第1の状態に書き込む段階と；
前記複数のレプリカのそれぞれのレプリカに対して第1のマルコフ連鎖モンテカルロ（MCMC）試行を実行する段階であって、前記系の前記状態の変化を表す、前記複数のビットのうちのランダムなそれぞれのビットが前記複数のレプリカのそれぞれのレプリカにおいて反転され、前記ランダムなビットを反転させることは、前記それぞれのレプリカの対応する温度の変化に影響を及ぼす、段階と；
第2の温度セットにおける他のどの温度よりも低い第2の温度を有する第2のレプリカを識別する段階であって、前記第2の温度セットは、前記第1のMCMC試行を実行した後の前記それぞれのレプリカのそれぞれに対応する温度を含む、段階と；
前記第2のレプリカを、前記メモリの第2の状態に書き込む段階と；
前記第1のレプリカを含む前記メモリの前記第1の状態と、前記第2のレプリカを含む前記メモリの前記第2の状態とに基づいて、前記系の表現を生成する段階と；
前記第1の温度で前記第1のレプリカに対して実行された場合に棄却をもたらすMCMC試行の第1の数の推定を表す前記第1のレプリカの第1の多重度を計算する段階と；
前記第2の温度で前記第2のレプリカに対して実行された場合に棄却をもたらすMCMC試行の第2の数の推定を表す前記第2のレプリカの第2の多重度を計算する段階と；
前記第1の多重度および前記第2の多重度を、前記系の前記表現に適用する段階と；
前記第1の温度セットおよび前記第2の温度セットの隣接する温度をスワッピングすることによって、前記複数のレプリカに関して並列スワッピングを実行する段階と；
前記第2の温度セットに基づいて、前記複数のレプリカのそれぞれのレプリカに対して第2のMCMC試行を実行する段階と；
前記系の終了状態の表現を、前記第1のレプリカ、前記第2のレプリカ、前記第1の多重度、および前記第2の多重度に基づいて生成する段階とを含む、
方法。
続きを表示（約 2,300 文字）【請求項２】
前記第1のMCMC試行および前記第2のMCMC試行が、それぞれ、棄却なし試行として実行される、請求項１に記載の方法。
【請求項３】
前記第1のレプリカをメモリの前記第1の状態に書き込むことは、前記複数のレプリカのそれぞれのレプリカに対して前記第1のMCMC試行を実行することと同時並行して行われる、請求項１に記載の方法。
【請求項４】
前記第1のMCMC試行および前記第2のMCMC試行はそれぞれ、前記第1のMCMC試行における前記複数のレプリカのうちのあるレプリカにおける第1のニューロンによる使用のために乱数を生成し、前記複数のレプリカのうちの前記レプリカにおける第2のニューロンに、前記第2のMCMC試行における使用のために前記乱数を与えることを含む、請求項１に記載の方法。
【請求項５】
前記第1の多重度および前記第2の多重度を計算することは、前記第1のMCMC試行および前記第2のMCMC試行において使用される前記乱数に基づく、請求項４に記載の方法。
【請求項６】
前記第1の多重度を計算することは：
前記複数のレプリカのうちのあるレプリカに関連付けられた一つまたは複数のビットをフラグ・ビットとして識別し；
前記フラグ・ビットを総和し；
前記フラグ・ビットの和を用いて前記第1の多重度を計算することを含む、
請求項１に記載の方法。
【請求項７】
前記第1の多重度を計算することは：
前記複数のレプリカの各レプリカに対応するそれぞれのビット反転に関するエネルギーの潜在的変化に基づいて最小エネルギー差を決定し；
前記最小エネルギー差に対応する前記レプリカに関連する一つまたは複数のビットをフラグ・ビットとして識別し；
前記フラグ・ビットを総和し；
前記最小エネルギー差に対応するオフセット値を決定し；
前記フラグ・ビットの和と前記オフセット値とを使用して前記第1の多重度を計算することを含む、
請求項１に記載の方法。
【請求項８】
実行されることに応答して、システムに動作を実行させる命令を記憶するように構成された一つまたは複数の非一時的なコンピュータ可読記憶媒体であって、前記動作が：
複数のレプリカを取得する段階であって、前記複数のレプリカの各レプリカが系のそれぞれの推定された状態を表す複数のビットを含む、段階と；
前記複数のレプリカのそれぞれのレプリカを第1の温度セットの異なる対応する温度に割り当てる段階と；
前記第1の温度セットにおける他のどの温度よりも低い第1の温度を有する第1のレプリカを識別する段階と；
前記第1のレプリカを、メモリの第1の状態に書き込む段階と；
前記複数のレプリカのそれぞれのレプリカに対して第1のマルコフ連鎖モンテカルロ（MCMC）試行を実行する段階であって、前記系の前記状態の変化を表す、前記複数のビットのうちのランダムなそれぞれのビットが前記複数のレプリカのそれぞれのレプリカにおいて反転され、前記ランダムなビットを反転させることは、前記それぞれのレプリカの対応する温度の変化に影響を及ぼす、段階と；
第2の温度セットにおける他のどの温度よりも低い第2の温度を有する第2のレプリカを識別する段階であって、前記第2の温度セットは、前記第1のMCMC試行を実行した後の前記それぞれのレプリカのそれぞれに対応する温度を含む、段階と；
前記第2のレプリカを、前記メモリの第2の状態に書き込む段階と；
前記第1のレプリカを含む前記メモリの前記第1の状態と、前記第2のレプリカを含む前記メモリの前記第2の状態とに基づいて、前記系の表現を生成する段階と；
前記第1の温度で前記第1のレプリカに対して実行された場合に棄却をもたらすMCMC試行の第1の数の推定を表す前記第1のレプリカの第1の多重度を計算する段階と；
前記第2の温度で前記第2のレプリカに対して実行された場合に棄却をもたらすMCMC試行の第2の数の推定を表す前記第2のレプリカの第2の多重度を計算する段階と；
前記第1の多重度および前記第2の多重度を、前記系の前記表現に適用する段階と；
前記第1の温度セットおよび前記第2の温度セットの隣接する温度をスワッピングすることによって、前記複数のレプリカに関して並列スワッピングを実行する段階と；
前記第2の温度セットに基づいて、前記複数のレプリカのそれぞれのレプリカに対して第2のMCMC試行を実行する段階と；
前記系の終了状態の表現を、前記第1のレプリカ、前記第2のレプリカ、前記第1の多重度、および前記第2の多重度に基づいて生成する段階とを含む、
一つまたは複数の非一時的なコンピュータ可読記憶媒体。
【請求項９】
前記第1のMCMC試行および前記第2のMCMC試行が、それぞれ、棄却なし試行として実行される、請求項８に記載の一つまたは複数の非一時的なコンピュータ可読記憶媒体。
【請求項１０】
前記第1のレプリカをメモリの前記第1の状態に書き込むことは、前記複数のレプリカのそれぞれのレプリカに対して前記第1のMCMC試行を実行することと同時並行して行われる、請求項８に記載の一つまたは複数の非一時的なコンピュータ可読記憶媒体。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本明細書で説明される実施形態は、棄却なしの並列試行マルコフ連鎖モンテカルロ法（rejection-free parallel trial Markov Chain Monte Carlo processes）を使用する統計的サンプリングに関する。
続きを表示（約 1,900 文字）【背景技術】
【０００２】
状態空間の表現を得るためにサンプリング技術が使用されてもよい。いくつかの事例では、デジタル・アニーラーがサンプラーとして使用されてきたが、比較的大きな計算資源を必要とする。さらに、デジタル・アニーラーは、状態空間の分布を歪めることがあり、そのため、結果として得られる表現が不正確になることがある。追加的または代替的に、伝統的なデジタル・アニーラー動作は、状態空間をサンプリングするために使用されうる無効なマルコフ連鎖モンテカルロ（Markov Chain Monte Carlo、MCMC）プロセスをもたらすような仕方で動作を実行することがある。
【０００３】
本明細書で特許請求される主題は、任意の欠点を解決する実施形態、または上述のような環境でのみ動作する実施形態に限定されない。むしろ、この背景は、本明細書に記載されるいくつかの実施形態が実施されうる1つの例示的な技術分野を示すためにのみ提供されている。
【発明の概要】
【課題を解決するための手段】
【０００４】
ある実施形態のある側面によれば、方法は、レプリカを取得することを含んでいてもよく、各レプリカが系のそれぞれの推定された状態を表す複数のビットを含む。この方法は、各それぞれのレプリカを第1の温度セットの異なる対応する温度に割り当てることと、第1の温度セット内の他のどの温度よりも低い第1の温度を有する第1のレプリカを識別することとを含みうる。第1のレプリカは、メモリの第1の状態に書き込まれてもよい。本方法はまた、系の状態の変化を表すランダムなそれぞれのビットがそれぞれのレプリカにおいて反転される、それぞれのレプリカに対して第1のマルコフ連鎖モンテカルロ（MCMC）試行を実行することを含みうる。ランダムなビットを反転させることは、それぞれのレプリカの対応する温度の変化に影響を及ぼしうる。第2の温度セット内の他のどの温度よりも低い第2の温度を有する第2のレプリカが識別されてもよく、第2の温度セットは、第1のMCMC試行を実行した後のそれぞれのレプリカのそれぞれに対応する温度を含む。第2のレプリカは、メモリの第2の状態に書き込まれてもよい。本方法は、第1のレプリカを含むメモリの第1の状態と、第2のレプリカを含むメモリの第2の状態とに基づいて、系の表現を生成することを含みうる。本方法は、第1の温度で第1のレプリカに対して実行された場合に棄却をもたらすMCMC試行の第1の数の推定を表す第1のレプリカの第1の多重度を計算することも含むことができる。本方法は、第2の温度で第2のレプリカに対して実行された場合に棄却をもたらすMCMC試行の第2の数の推定を表す第2のレプリカの第2の多重度を計算することをさらに含むことができる。第1の多重度および第2の多重度は、系の表現に適用されてもよく、第1の温度のセットおよび第2の温度のセットの隣接する温度をスワッピングすることによって、レプリカに関して並列スワッピングが実行されてもよい。第2のMCMC試行は、第2の温度のセットに基づいて各それぞれのレプリカに対して実行されてもよく、系の終了状態の表現は、第1のレプリカ、第2のレプリカ、第1の多重度、および第2の多重度に基づいて生成されうる。
【０００５】
実施形態の目的および利点は、少なくとも、特許請求の範囲において特に指摘される要素、特徴、および組み合わせによって実現され、達成される。上記の一般的な記述および以下の詳細な説明は説明するものであり、特許請求される発明を制約するものではないことが理解されるものとする。
【図面の簡単な説明】
【０００６】
例示的な実施形態は、添付の図面の使用を通じて、さらなる具体性および詳細とともに記載され、説明される。
【０００７】
本開示の少なくとも1つの実施形態による、情報がDRAMに書き込まれる例示的な実施形態を示す。
【０００８】
本開示の少なくとも1つの実施形態による、例示的なハードウェア・アーキテクチャーを示す。
【０００９】
本開示の少なくとも1つの実施形態による、例示的なノイズ生成器を示す。
【００１０】
本開示の少なくとも1つの実施形態による、棄却なしのマルコフ連鎖モンテカルロ鎖と、該棄却なしのマルコフ連鎖モンテカルロ鎖に対応する多重度との例を示す。
（【００１１】以降は省略されています）

関連特許