特許ウォッチ

公開番号2024090697
公報種別公開特許公報(A)
公開日2024-07-04
出願番号2022206754
出願日2022-12-23
発明の名称データ処理装置、データ処理方法およびプログラム
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20240627BHJP(計算;計数)
要約【課題】演算の効率化を可能にする。
【解決手段】記憶部11は、総エネルギーと、複数の状態変数の値と、複数の状態変数のそれぞれの間の第1重み値と、複数の状態変数の少なくとも一部の状態変数と制約条件との間の第2重み値と、複数の状態変数のそれぞれの値が変化する場合の総エネルギーの第1変化量を表す第1局所場と、制約条件に対する制約違反量の特定に用いられる第2局所場を記憶する。処理部12は、複数の状態変数のうち第1状態変数の値の変化を許容するか否かを第1局所場に基づいて判定する処理と、第1状態変数の値の変化を許容すると判定した場合、第1重み値に基づいて第1局所場を更新し、第1状態変数と制約条件との間の第2重み値に基づいて第2局所場を更新し、更新前の第2局所場を量子化した第1量子化局所場と更新後の第2局所場を量子化した第2量子化局所場とに基づいて、第1局所場をさらに更新する処理と、を繰り返す。
【選択図】図1
特許請求の範囲【請求項１】
複数の状態変数を含むイジング型の評価関数を用いて計算される値が極小または極大となる前記複数の状態変数の値の組合せを探索するデータ処理装置において、
制約条件の違反の有無に応じた値をもつ制約項と前記評価関数の値との和である総エネルギーと、前記複数の状態変数の値と、前記複数の状態変数それぞれの間の第１重み値と、前記複数の状態変数の少なくとも一部の状態変数と前記制約条件との間の第２重み値と、前記複数の状態変数それぞれの値が変化する場合の前記総エネルギーの第１変化量を表す第１局所場と、前記制約条件に対する制約違反量の特定に用いられる第２局所場と、を記憶する記憶部と、
前記複数の状態変数のうち第１状態変数の値の変化を許容するか否かを前記第１局所場に基づいて判定する処理と、前記第１状態変数の値の変化を許容すると判定した場合、前記第１重み値に基づいて前記第１局所場を更新し、前記第１状態変数と前記制約条件との間の前記第２重み値に基づいて前記第２局所場を更新し、更新前の前記第２局所場を量子化した第１量子化局所場と更新後の前記第２局所場を量子化した第２量子化局所場とに基づいて、前記第１局所場をさらに更新する処理と、を繰り返す処理部と、
を有するデータ処理装置。
続きを表示（約 2,400 文字）【請求項２】
前記処理部は、前記第１量子化局所場と前記第２量子化局所場とが同じである場合、前記第１量子化局所場と前記第２量子化局所場とに基づく前記第１局所場の更新を省略する、
請求項１記載のデータ処理装置。
【請求項３】
前記処理部は、前記第１状態変数の値の変化を許容すると判定した場合、前記第１量子化局所場に対応する、更新前の前記第２局所場の近似値を用いて計算される前記制約項の変化量と、前記第２量子化局所場に対応する、更新後の前記第２局所場の近似値を用いて計算される前記制約項の変化量との差分に基づいて、前記第１局所場を更新する、
請求項１記載のデータ処理装置。
【請求項４】
前記処理部は、前記第１局所場を更新する第１演算器と、前記第２局所場を更新する第２演算器とを有し、
前記第２演算器は、前記第１量子化局所場を示す第１コードであって、前記第２局所場の第１ビット数よりも少ない第２ビット数の前記第１コードと、前記第２量子化局所場を示す、前記第２ビット数の第２コードとを前記第１演算器に出力し、
前記第１演算器は、前記第１コードに基づいて、更新前の前記第２局所場の近似値を取得し、前記第２コードに基づいて、更新後の前記第２局所場の近似値を取得し、更新前後の前記第２局所場の近似値に基づいて、前記第１局所場を更新する、
請求項１記載のデータ処理装置。
【請求項５】
前記処理部は、前記第２局所場を更新すると、更新前の前記第２局所場と更新後の前記第２局所場と前記第１量子化局所場と前記第２量子化局所場とに基づいて、前記総エネルギーを補正する、
請求項１記載のデータ処理装置。
【請求項６】
前記処理部は、
前記第１量子化局所場および前記第２量子化局所場に応じた前記制約項の第２変化量と前記第１局所場とを個別に前記記憶部に格納し、
前記複数の状態変数の値に対して前記制約条件が満たされるか否かを示す補助変数の値の変化に応じて、前記第２重み値に基づき前記第１局所場と前記第２変化量とを更新し、
前記第１状態変数の値の変化を許容するか否かを、前記第１局所場と前記第２変化量とに基づいて判定し、
前記第１状態変数の値の変化に応じて、前記第１局所場に基づき前記総エネルギーを更新し、前記補助変数の値の変化に応じて、前記第２局所場に基づき前記総エネルギーを更新する、
請求項１記載のデータ処理装置。
【請求項７】
前記記憶部に保持される前記第２変化量は、前記制約違反量の表現に用いられる第３ビット数よりも少ないビット数で表され、
前記処理部は、前記第２重み値に対応する、前記第２重み値のビット数よりも少ないビット数のコードに基づいて前記第２変化量を更新し、前記第２変化量を用いて前記第１局所場を更新する際に、前記第２変化量を前記第３ビット数で表される値に変換する、
請求項６記載のデータ処理装置。
【請求項８】
複数の状態変数を含むイジング型の評価関数を用いて計算される値が極小または極大となる前記複数の状態変数の値の組合せの探索を実行するデータ処理装置が、
記憶部に記憶されている、制約条件の違反の有無に応じた値をもつ制約項と前記評価関数の値との和である総エネルギーと、前記複数の状態変数の値と、前記複数の状態変数それぞれの間の第１重み値と、前記複数の状態変数の少なくとも一部の状態変数と前記制約条件との間の第２重み値と、前記複数の状態変数それぞれの値が変化する場合の前記総エネルギーの第１変化量を表す第１局所場と、前記制約条件に対する制約違反量の特定に用いられる第２局所場と、のうち、
前記第１局所場に基づいて、前記複数の状態変数のうち第１状態変数の値の変化を許容するか否かを判定する処理と、
前記第１状態変数の値の変化を許容すると判定した場合、前記記憶部に記憶されている前記第１重み値に基づいて前記第１局所場を更新し、前記第１状態変数と前記制約条件との間の、前記記憶部に記憶されている前記第２重み値に基づいて前記第２局所場を更新し、更新前の前記第２局所場を量子化した第１量子化局所場と更新後の前記第２局所場を量子化した第２量子化局所場とに基づいて、前記第１局所場をさらに更新する処理と、
を繰り返すデータ処理方法。
【請求項９】
複数の状態変数を含むイジング型の評価関数を用いて計算される値が極小または極大となる前記複数の状態変数の値の組合せの探索をコンピュータに実行させるプログラムであって、
記憶部に記憶されている、制約条件の違反の有無に応じた値をもつ制約項と前記評価関数の値との和である総エネルギーと、前記複数の状態変数の値と、前記複数の状態変数それぞれの間の第１重み値と、前記複数の状態変数の少なくとも一部の状態変数と前記制約条件との間の第２重み値と、前記複数の状態変数それぞれの値が変化する場合の前記総エネルギーの第１変化量を表す第１局所場と、前記制約条件に対する制約違反量の特定に用いられる第２局所場と、のうち、
前記第１局所場に基づいて、前記複数の状態変数のうち第１状態変数の値の変化を許容するか否かを判定する処理と、
前記第１状態変数の値の変化を許容すると判定した場合、前記記憶部に記憶されている前記第１重み値に基づいて前記第１局所場を更新し、前記第１状態変数と前記制約条件との間の、前記記憶部に記憶されている前記第２重み値に基づいて前記第２局所場を更新し、更新前の前記第２局所場を量子化した第１量子化局所場と更新後の前記第２局所場を量子化した第２量子化局所場とに基づいて、前記第１局所場をさらに更新する処理と、
を繰り返す処理を前記コンピュータに実行させるプログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明はデータ処理装置、データ処理方法およびプログラムに関する。
続きを表示（約 1,400 文字）【背景技術】
【０００２】
ノイマン型コンピュータが不得意とする大規模な離散最適化問題を計算する装置として、イジング型の評価関数を用いたイジング装置がある。評価関数は、エネルギー関数などとも呼ばれる。また、イジング装置は、ボルツマンマシンとも呼ばれる。
【０００３】
イジング装置は、離散最適化問題を磁性体のスピンの振る舞いを表すイジングモデルに変換する。そして、イジング装置は、疑似焼き鈍し法やレプリカ交換法などのマルコフ連鎖モンテカルロ法により、イジング型の評価関数の値が極小になるイジングモデルの状態を探索する。イジング型の評価関数の値は、エネルギーに相当する。評価関数の極小値のうちの最小値になる状態が最適解となる。なお、イジング装置は、評価関数の符号を変えれば、評価関数の値が極大になる状態を探索することもできる。イジングモデルの状態は、複数の状態変数の値の組合せにより表現できる。各状態変数の値として、０または１を用いることができる。
【０００４】
イジング型の評価関数は、例えば、以下の式（１）のような２次形式の関数で定義される。
【０００５】
TIFF
2024090697000002.tif
19
145
【０００６】
右辺の１項目は、イジングモデルのＮ個の状態変数の全組合せについて、漏れと重複なく、２つの状態変数の値（０または１）と重み値との積を積算したものである。重み値は、２つの状態変数の間の相互作用の強さを表す。ｘ
ｉ
は、識別番号がｉの状態変数、ｘ
ｊ
は、識別番号がｊの状態変数であり、Ｗ
ｉｊ
は、識別番号がｉとｊの状態変数間の相互作用の大きさを示す重み値である。右辺の２項目は、各識別番号についてのバイアス係数と状態変数との積の総和を求めたものである。ｂ
ｉ
は、識別番号がｉについてのバイアス係数を示している。
【０００７】
また、ｘ
ｉ
の値の変化に伴うエネルギーの変化量（ΔＥ
ｉ
）は、以下の式（２）で表される。
【０００８】
TIFF
2024090697000003.tif
19
145
【０００９】
式（２）において、ｘ
ｉ
が１から０に変化するとき、Δｘ
ｉ
は－１となり、状態変数ｘ
ｉ
が０から１に変化するとき、Δｘ
ｉ
は１となる。なお、ｈ
ｉ
は局所場と呼ばれ、Δｘ
ｉ
に応じてｈ
ｉ
に符号（＋１または－１）を乗じたものがΔＥ
ｉ
となる。このため、ｈ
ｉ
はエネルギーの変化量を表す変数、またはエネルギーの変化量を決める変数ということもできる。
【００１０】
そして、例えば、ｅｘｐ（－βΔＥ
ｉ
）（βは温度を表すパラメータの逆数）と表せる受け入れ確率でｘ
ｉ
の値を更新することで状態遷移を発生させ、局所場も更新する、という処理が繰り返される。
（【００１１】以降は省略されています）

関連特許