特許ウォッチ

公開番号2024062514
公報種別公開特許公報(A)
公開日2024-05-10
出願番号2022170388
出願日2022-10-25
発明の名称データ処理装置、データ処理方法およびプログラム
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20240501BHJP(計算;計数)
要約【課題】探索対象の状態変数のグループの切り替えを効率的に行う。
【解決手段】処理部12は、イジング問題の状態変数全体を分割した複数のグループを切り替えて解の探索を行う。処理部12は、探索対象を第1グループに切り替える際、変化情報31を基に、第1グループに対する前回の探索後に他グループの探索により値が変化した状態変数と第1グループに含まれる複数の第1状態変数それぞれとのペアに対応する第1重み係数を記憶装置20から記憶部11に読み出し、第1重み係数を基に第1状態変数ごとの局所場を更新する。処理部12は、第1状態変数のペアに対応する第2重み係数を記憶装置20から記憶部11に読み出し、第2重み係数と第1状態変数ごとの局所場とを用いて第1グループの探索を実行する。処理部12は、当該探索を終了すると、今回の探索による第1状態変数ごとの値の変化の有無に応じて変化情報31を更新し、次のグループに切り替える。
【選択図】図1
特許請求の範囲【請求項１】
記憶部と、
複数の状態変数を含むイジングモデルで表される問題の解の探索を、前記複数の状態変数を分割した複数のグループそれぞれを切り替えて行う処理部とを有し、
前記処理部は、
探索対象を前記複数のグループのうちの第１グループに切り替える際に、
前記第１グループに対する前回の前記探索後に前記第１グループ以外の他のグループに対する前記探索により値が変化した状態変数を示す変化情報に基づいて、当該状態変数と前記第１グループに属する複数の第１状態変数それぞれとのペアに対応する第１重み係数を、前記複数の状態変数に関する重み係数の全体を記憶する記憶装置から読み出し、読み出した前記第１重み係数を前記記憶部に格納し、
前記記憶部に記憶された前記第１重み係数に基づいて、前記複数の第１状態変数それぞれの局所場を更新し、
前記複数の第１状態変数における前記第１状態変数のペアに対応する第２重み係数を前記記憶装置から読み出し、読み出した前記第２重み係数を前記記憶部に格納し、
前記記憶部に記憶された前記第２重み係数と前記複数の第１状態変数それぞれの前記局所場とを用いて、前記第１グループに対する前記探索を実行し、
前記第１グループに対する前記探索を終了すると、
今回の前記探索による前記複数の第１状態変数それぞれの値の変化の有無に応じて前記変化情報を更新し、探索対象を次のグループに切り替える、
データ処理装置。
続きを表示（約 2,200 文字）【請求項２】
前記第１グループおよび前記第１グループの直前に前記探索が行われた第２グループそれぞれに属する一部の状態変数は重複しており、
前記処理部は、前記第２重み係数を前記記憶部に格納すると、前記記憶部に記憶された前記第２重み係数と前記第２グループに対する直前の前記探索での前記一部の状態変数に含まれる前記状態変数の値の変化とに基づいて、前記第１グループのうち前記第２グループと重複しない他の一部の状態変数の前記局所場を更新する、
請求項１記載のデータ処理装置。
【請求項３】
前記処理部は、次の探索対象のグループを所定順序で、または、ランダムに選択する、
請求項１記載のデータ処理装置。
【請求項４】
前記記憶装置は、前記変化情報と前記複数の状態変数それぞれの前記局所場と前記第１グループに対する前回の前記探索後の前記複数の状態変数の値を示すステート情報とを記憶し、
前記処理部は、
前記第１グループに対する前記探索を行う際に、前記記憶装置から前記変化情報と前記複数の第１状態変数それぞれの前記局所場と前記ステート情報とを前記記憶部に読み出し、前記変化情報および前記ステート情報から特定される、前記他のグループの前記状態変数の値の変化方向と前記第１重み係数とに基づいて、前記複数の第１状態変数それぞれの前記局所場を更新し、
前記第１グループに対する前記探索を終了すると、今回の前記探索による前記複数の第１状態変数それぞれの値の変化の有無に応じて前記記憶装置に記憶される前記変化情報を更新し、今回の前記探索後の前記複数の第１状態変数それぞれの前記局所場と、今回の前記探索後の前記ステート情報とを前記記憶装置に格納する、
請求項１記載のデータ処理装置。
【請求項５】
前記処理部は、各々が前記複数の状態変数を示す複数のレプリカに対して前記第１グループに対する前記探索を行う場合に、前記複数のレプリカそれぞれの前記変化情報の論理和に基づいて、前記記憶装置から読み出す前記第１重み係数を特定する、
請求項１記載のデータ処理装置。
【請求項６】
データ処理装置が、
複数の状態変数を含むイジングモデルで表される問題の解の探索を、前記複数の状態変数を分割した複数のグループそれぞれを切り替えて行う場合において、探索対象を前記複数のグループのうちの第１グループに切り替える際に、
前記第１グループに対する前回の前記探索後に前記第１グループ以外の他のグループに対する前記探索により値が変化した状態変数を示す変化情報に基づいて、当該状態変数と前記第１グループに属する複数の第１状態変数それぞれとのペアに対応する第１重み係数を、前記複数の状態変数に関する重み係数の全体を記憶する記憶装置から読み出し、読み出した前記第１重み係数を記憶部に格納し、
前記記憶部に記憶された前記第１重み係数に基づいて、前記複数の第１状態変数それぞれの局所場を更新し、
前記複数の第１状態変数における前記第１状態変数のペアに対応する第２重み係数を前記記憶装置から読み出し、読み出した前記第２重み係数を前記記憶部に格納し、
前記記憶部に記憶された前記第２重み係数と前記複数の第１状態変数それぞれの前記局所場とを用いて、前記第１グループに対する前記探索を実行し、
前記第１グループに対する前記探索を終了すると、
今回の前記探索による前記複数の第１状態変数それぞれの値の変化の有無に応じて前記変化情報を更新し、探索対象を次のグループに切り替える、
データ処理方法。
【請求項７】
コンピュータに、
複数の状態変数を含むイジングモデルで表される問題の解の探索を、前記複数の状態変数を分割した複数のグループそれぞれを切り替えて行う場合において、探索対象を前記複数のグループのうちの第１グループに切り替える際に、
前記第１グループに対する前回の前記探索後に前記第１グループ以外の他のグループに対する前記探索により値が変化した状態変数を示す変化情報に基づいて、当該状態変数と前記第１グループに属する複数の第１状態変数それぞれとのペアに対応する第１重み係数を、前記複数の状態変数に関する重み係数の全体を記憶する記憶装置から読み出し、読み出した前記第１重み係数を記憶部に格納し、
前記記憶部に記憶された前記第１重み係数に基づいて、前記複数の第１状態変数それぞれの局所場を更新し、
前記複数の第１状態変数における前記第１状態変数のペアに対応する第２重み係数を前記記憶装置から読み出し、読み出した前記第２重み係数を前記記憶部に格納し、
前記記憶部に記憶された前記第２重み係数と前記複数の第１状態変数それぞれの前記局所場とを用いて、前記第１グループに対する前記探索を実行し、
前記第１グループに対する前記探索を終了すると、
今回の前記探索による前記複数の第１状態変数それぞれの値の変化の有無に応じて前記変化情報を更新し、探索対象を次のグループに切り替える、
処理を実行させるプログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明はデータ処理装置、データ処理方法およびプログラムに関する。
続きを表示（約 1,500 文字）【背景技術】
【０００２】
ノイマン型コンピュータが不得意とする多変数の組合せ最適化問題を、磁性体のスピンの振る舞いを表すモデルであるイジングモデルに置き換えて計算するイジングマシンがある。イジングマシンはボルツマンマシンとも呼ばれる。イジングモデルに置き換えられた問題を実用的な時間で解く手法には、マルコフ連鎖モンテカルロ（ＭＣＭＣ：Markov Chain Monte Carlo）法に基づく、シミュレーテッドアニーリング（ＳＡ：Simulated Annealing）法やレプリカ交換法などがある。
【０００３】
組合せ最適化問題は、複数の状態変数を含むエネルギー関数により定式化される。例えば、イジングマシンは、ＭＣＭＣ法を用いて状態変数の値を変化させることによる状態遷移を繰り返し試行することで、エネルギー関数の値が最小となるイジングモデルの基底状態を探索する。基底状態は組合せ最適化問題の最適解に対応する。
【０００４】
例えば、組合せ最適化問題を複数の部分問題に分割して解き、部分問題の解に基づいて全体の解を求める最適化装置の提案がある。提案の最適化装置は、複数の部分問題のうち、何れかの部分問題についての解を、それぞれが探索する複数のイジング装置を有する。
【０００５】
また、複数のイジング装置を有する情報処理装置の提案もある。この提案では、イジング装置は、１ビットに関する処理を行う複数のニューロン回路を有し、ルータを介して得た他のイジング装置のニューロン状態を自身のニューロン回路に反映する。
【０００６】
また、ニューロン回路において、ニューロン間の結合の強さを示す重み係数の全体のうち、対象ニューロンと結合する結合先ニューロンとの間の重み係数だけを保持することで、ニューロン回路の記憶部の容量を削減する最適化装置の提案もある。
【０００７】
なお、量子ビットを含むアナログプロセッサが出力したサンプルに対し、逆方向のアニーリングスケジュールでＳＡを実行し、その履歴を用いて、重要度サンプリング（importance sampling）に用いるサンプルの重みを計算する計算システムの提案がある。
【先行技術文献】
【特許文献】
【０００８】
特開２０２１－１３１６９５号公報
特開２０１７－２１９９４８号公報
特開２０２０－１９４４４２号公報
米国特許出願公開第２０１７／０１１６１５９号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００９】
イジングモデルに置き換えられた問題の求解では、各状態変数間の相互作用の大きさを表す重み係数が用いられる。問題規模の増大に応じて状態変数の数が増えると、重み係数の数も増加する。このため、求解を実行する演算器によりキャッシュとして用いられる記憶部に全ての重み係数を記憶しきれない可能性がある。
【００１０】
問題を複数の部分問題に分割し、状態変数全体のうち、部分問題に対応する状態変数のグループを対象に求解を行うことで、当該記憶部に保持される重み係数が削減され得る。そこで、例えば大容量の記憶装置に重み係数の全体を記憶し、当該記憶装置からキャッシュ用の記憶部に部分問題の情報を転送し、転送する部分問題を適宜入れ替えて計算を行う方法が考えられる。しかし、この方法では部分問題の入れ替えに伴って生じる、記憶部への重み係数の読み込みやエネルギー関数の値の変化量の計算に用いられる局所場の更新に時間がかかる。
（【００１１】以降は省略されています）

関連特許