TOP特許意匠商標
特許ウォッチ Twitter
10個以上の画像は省略されています。
公開番号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
特許請求の範囲【請求項1】
記憶部と、
複数の状態変数を含むイジングモデルで表される問題の解の探索を、前記複数の状態変数を分割した複数のグループそれぞれを切り替えて行う処理部とを有し、
前記処理部は、
探索対象を前記複数のグループのうちの第1グループに切り替える際に、
前記第1グループに対する前回の前記探索後に前記第1グループ以外の他のグループに対する前記探索により値が変化した状態変数を示す変化情報に基づいて、当該状態変数と前記第1グループに属する複数の第1状態変数それぞれとのペアに対応する第1重み係数を、前記複数の状態変数に関する重み係数の全体を記憶する記憶装置から読み出し、読み出した前記第1重み係数を前記記憶部に格納し、
前記記憶部に記憶された前記第1重み係数に基づいて、前記複数の第1状態変数それぞれの局所場を更新し、
前記複数の第1状態変数における前記第1状態変数のペアに対応する第2重み係数を前記記憶装置から読み出し、読み出した前記第2重み係数を前記記憶部に格納し、
前記記憶部に記憶された前記第2重み係数と前記複数の第1状態変数それぞれの前記局所場とを用いて、前記第1グループに対する前記探索を実行し、
前記第1グループに対する前記探索を終了すると、
今回の前記探索による前記複数の第1状態変数それぞれの値の変化の有無に応じて前記変化情報を更新し、探索対象を次のグループに切り替える、
データ処理装置。
続きを表示(約 2,200 文字)【請求項2】
前記第1グループおよび前記第1グループの直前に前記探索が行われた第2グループそれぞれに属する一部の状態変数は重複しており、
前記処理部は、前記第2重み係数を前記記憶部に格納すると、前記記憶部に記憶された前記第2重み係数と前記第2グループに対する直前の前記探索での前記一部の状態変数に含まれる前記状態変数の値の変化とに基づいて、前記第1グループのうち前記第2グループと重複しない他の一部の状態変数の前記局所場を更新する、
請求項1記載のデータ処理装置。
【請求項3】
前記処理部は、次の探索対象のグループを所定順序で、または、ランダムに選択する、
請求項1記載のデータ処理装置。
【請求項4】
前記記憶装置は、前記変化情報と前記複数の状態変数それぞれの前記局所場と前記第1グループに対する前回の前記探索後の前記複数の状態変数の値を示すステート情報とを記憶し、
前記処理部は、
前記第1グループに対する前記探索を行う際に、前記記憶装置から前記変化情報と前記複数の第1状態変数それぞれの前記局所場と前記ステート情報とを前記記憶部に読み出し、前記変化情報および前記ステート情報から特定される、前記他のグループの前記状態変数の値の変化方向と前記第1重み係数とに基づいて、前記複数の第1状態変数それぞれの前記局所場を更新し、
前記第1グループに対する前記探索を終了すると、今回の前記探索による前記複数の第1状態変数それぞれの値の変化の有無に応じて前記記憶装置に記憶される前記変化情報を更新し、今回の前記探索後の前記複数の第1状態変数それぞれの前記局所場と、今回の前記探索後の前記ステート情報とを前記記憶装置に格納する、
請求項1記載のデータ処理装置。
【請求項5】
前記処理部は、各々が前記複数の状態変数を示す複数のレプリカに対して前記第1グループに対する前記探索を行う場合に、前記複数のレプリカそれぞれの前記変化情報の論理和に基づいて、前記記憶装置から読み出す前記第1重み係数を特定する、
請求項1記載のデータ処理装置。
【請求項6】
データ処理装置が、
複数の状態変数を含むイジングモデルで表される問題の解の探索を、前記複数の状態変数を分割した複数のグループそれぞれを切り替えて行う場合において、探索対象を前記複数のグループのうちの第1グループに切り替える際に、
前記第1グループに対する前回の前記探索後に前記第1グループ以外の他のグループに対する前記探索により値が変化した状態変数を示す変化情報に基づいて、当該状態変数と前記第1グループに属する複数の第1状態変数それぞれとのペアに対応する第1重み係数を、前記複数の状態変数に関する重み係数の全体を記憶する記憶装置から読み出し、読み出した前記第1重み係数を記憶部に格納し、
前記記憶部に記憶された前記第1重み係数に基づいて、前記複数の第1状態変数それぞれの局所場を更新し、
前記複数の第1状態変数における前記第1状態変数のペアに対応する第2重み係数を前記記憶装置から読み出し、読み出した前記第2重み係数を前記記憶部に格納し、
前記記憶部に記憶された前記第2重み係数と前記複数の第1状態変数それぞれの前記局所場とを用いて、前記第1グループに対する前記探索を実行し、
前記第1グループに対する前記探索を終了すると、
今回の前記探索による前記複数の第1状態変数それぞれの値の変化の有無に応じて前記変化情報を更新し、探索対象を次のグループに切り替える、
データ処理方法。
【請求項7】
コンピュータに、
複数の状態変数を含むイジングモデルで表される問題の解の探索を、前記複数の状態変数を分割した複数のグループそれぞれを切り替えて行う場合において、探索対象を前記複数のグループのうちの第1グループに切り替える際に、
前記第1グループに対する前回の前記探索後に前記第1グループ以外の他のグループに対する前記探索により値が変化した状態変数を示す変化情報に基づいて、当該状態変数と前記第1グループに属する複数の第1状態変数それぞれとのペアに対応する第1重み係数を、前記複数の状態変数に関する重み係数の全体を記憶する記憶装置から読み出し、読み出した前記第1重み係数を記憶部に格納し、
前記記憶部に記憶された前記第1重み係数に基づいて、前記複数の第1状態変数それぞれの局所場を更新し、
前記複数の第1状態変数における前記第1状態変数のペアに対応する第2重み係数を前記記憶装置から読み出し、読み出した前記第2重み係数を前記記憶部に格納し、
前記記憶部に記憶された前記第2重み係数と前記複数の第1状態変数それぞれの前記局所場とを用いて、前記第1グループに対する前記探索を実行し、
前記第1グループに対する前記探索を終了すると、
今回の前記探索による前記複数の第1状態変数それぞれの値の変化の有無に応じて前記変化情報を更新し、探索対象を次のグループに切り替える、
処理を実行させるプログラム。

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

この特許をJ-PlatPatで参照する

関連特許

富士通株式会社
情報処理プログラム、情報処理方法および情報処理装置
今日
個人
暗号化記憶媒体
27日前
個人
プロジェクター
1か月前
個人
求人支援システム
16日前
キヤノン電子株式会社
周辺機器
1か月前
個人
求人マッチングサーバ
1か月前
カゴメ株式会社
営農支援プログラム
1か月前
カゴメ株式会社
営農支援プログラム
1か月前
カゴメ株式会社
営農支援プログラム
1か月前
カゴメ株式会社
営農支援プログラム
1か月前
アスエネ株式会社
水管理の方法
1か月前
株式会社ワコム
電子ペン
1か月前
シャープ株式会社
情報出力装置
14日前
株式会社ワコム
電子ペン
2日前
株式会社ワコム
電子ペン
28日前
大日本印刷株式会社
作業台
1か月前
東洋電装株式会社
操作装置
2日前
CKD株式会社
遠隔支援システム
1か月前
東洋電装株式会社
操作装置
2日前
株式会社寺岡精工
システム
1か月前
東洋電装株式会社
操作装置
2日前
トヨタ紡織株式会社
検査装置
23日前
日本信号株式会社
料金精算システム
12日前
個人
ポイント増量アプリ「太陽光銭サー」
1か月前
株式会社カロニマ
情報発信システム
6日前
株式会社アジラ
異常行動検出システム
23日前
株式会社小野測器
移動量計測システム
1か月前
BH株式会社
商品販売システム
1か月前
個人
スマートフォンにおける使用料金削減方法
13日前
個人
特許審査支援ボットおよびボットシステム
13日前
個人
AI営業システム
26日前
株式会社mov
情報処理システム
22日前
シーアンドアールエム株式会社
広告装置
9日前
ソニーグループ株式会社
装置
1か月前
トヨタ自動車株式会社
文字認識装置
23日前
富士フイルム株式会社
タッチセンサ
9日前
続きを見る