図面 (/)

技術 情報処理装置、イジング装置及び情報処理装置の制御方法

出願人 富士通株式会社
発明者 タシデビッド田村泰孝塚本三六
出願日 2016年6月17日 (4年0ヶ月経過) 出願番号 2016-120717
公開日 2017年12月21日 (2年6ヶ月経過) 公開番号 2017-224227
状態 特許登録済
技術分野 アナログ計算機
主要キーワード Nw個 実効温度 対象関係 イジング型 ローカルフィールド ノイズ幅 ノイズ発生回路 更新制御回路
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2017年12月21日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

補助的なビットを使用せず、高次エネルギ関数を用いた最適化問題マッピング可能とする。

解決手段

演算回路11a1〜11a(d−1)は、出力値更新許容された第1ニューロンを含む2〜d個のニューロンによる2〜d体結合の強さを示す複数の重み値と、n個のニューロンのnビット出力値に基づき、2〜d体結合で発生するエネルギーを示すd−1個のエネルギー値(hi2〜hid)を算出し、加算回路12がそれらを加算し、比較回路13はその加算値ノイズ値との加算結果に基づく値と閾値とを比較し、第1ニューロンの出力値を決定する。更新回路14は、選択信号と第1ニューロンの出力値とに基づきnビット出力値のうち、1ビットを更新した更新出力値を出力し、保持回路15は、更新出力値を保持し、演算回路11a1〜11a(d−1)が用いるnビット出力値として出力する。

概要

背景

ノイマン型コンピュータが不得意とする多変数最適化問題解く方法として、イジング型エネルギー関数を用いたイジング装置(ボルツマンマシンと呼ばれる場合もある)がある。イジング装置は、計算対象の問題を、磁性体のスピンの振る舞いを表すモデルであるイジングモデルに置き換えて計算する。

イジング装置は、ニューラルネットワークを用いてモデル化することもできる。その場合、イジング装置に含まれる複数のユニットビット)のそれぞれが、他のビットの状態と、他のビットと自身との結合の強さを示す重み値結合係数とも呼ばれる)とに応じて0または1を出力するニューロンとして機能する。イジング装置は、たとえば、シミュレテッドアニーリングにより、上記のようなエネルギー関数(コスト関数目的関数とも呼ばれる)の最小値が得られる各ビットの状態の組み合わせを、解として求める。

従来、イジング装置をハードウェアで実現することによって、計算時間を短縮することが提案されている。
ところで、従来のイジング装置は、2つのビットの結合の強さを示す重み値を含むエネルギー関数(以下2次のエネルギー関数という)を用いるものである。イジング装置を、より多様な最適化問題に適用可能とするため、3つ以上のビットによる相互結合の強さを示す重み値を含むエネルギー関数(以下高次のエネルギー関数という)を用いることが考えられる。

高次のエネルギー関数を用いた最適化問題の解決手法として、高次のエネルギー関数を用いた最適化問題を、複数の2次のエネルギー関数を用いた最適化問題に変換して解く手法が提案されている。

概要

補助的なビットを使用せず、高次エネルギ関数を用いた最適化問題をマッピング可能とする。演算回路11a1〜11a(d−1)は、出力値更新許容された第1ニューロンを含む2〜d個のニューロンによる2〜d体結合の強さを示す複数の重み値と、n個のニューロンのnビット出力値に基づき、2〜d体結合で発生するエネルギーを示すd−1個のエネルギー値(hi2〜hid)を算出し、加算回路12がそれらを加算し、比較回路13はその加算値ノイズ値との加算結果に基づく値と閾値とを比較し、第1ニューロンの出力値を決定する。更新回路14は、選択信号と第1ニューロンの出力値とに基づきnビット出力値のうち、1ビットを更新した更新出力値を出力し、保持回路15は、更新出力値を保持し、演算回路11a1〜11a(d−1)が用いるnビット出力値として出力する。

目的

本発明は、補助的なビットを使用せず、高次のエネルギー関数を用いた最適化問題をマッピングできる情報処理装置、イジング装置及び情報処理装置の制御方法を提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

n(nは3以上の自然数)個のニューロンのうち、出力値更新許容する第1のニューロンをランダムに選択するための選択信号を複数回出力するランダム信号生成回路と、前記n個のニューロンのうち、前記選択信号に基づき選択される前記第1のニューロンを含む2乃至d(dは3以上n以下の自然数)個のニューロンによる2体結合乃至d体結合の強さを示す複数の重み値と、前記n個のニューロンのnビットの出力値に基づき、前記2体結合乃至前記d体結合のそれぞれによって発生するエネルギーを示すd−1個のエネルギー値または前記d−1個のエネルギー値の変化分を算出するd−1個の演算回路と、前記d−1個のエネルギー値を加算した第1の加算値、または前記d−1個のエネルギー値の前記変化分を加算した第2の加算値を求め、前記第1の加算値または前記第2の加算値を出力する加算回路と、前記第1の加算値とノイズ値との加算結果に基づく第1の値と閾値との第1の比較結果、または、前記2体結合乃至前記d体結合のそれぞれによって発生する前記エネルギーの和を示し前記第2の加算値に基づき更新される第2の値と、前記ノイズ値との加算結果に基づく第3の値と前記閾値との第2の比較結果に基づき、前記第1のニューロンの第1の出力値を決定し出力する比較回路と、前記選択信号と前記第1の出力値とに基づいて前記nビットの出力値のうち、1ビットを更新した更新出力値を出力する更新回路と、前記更新出力値を保持し、前記演算回路が用いる前記nビットの出力値として出力する保持回路と、を有するイジング装置と、前記ノイズ値のノイズ幅を制御する制御装置と、を有することを特徴とする情報処理装置

請求項2

前記d−1個の演算回路のそれぞれは記憶部を有し、前記制御装置は、前記複数の重み値のうち、前記複数の重み値の対称性に基づき、前記記憶部に記憶する前記複数の重み値の数を決定する、ことを特徴とする請求項1に記載の情報処理装置。

請求項3

前記制御装置は、前記記憶部に記憶する前記複数の重み値の数を、nd-3×(n2−n)/2とする、ことを特徴とする請求項2に記載の情報処理装置。

請求項4

n(nは3以上の自然数)個のニューロンのうち、出力値の更新を許容する第1のニューロンをランダムに選択するための選択信号を複数回出力するランダム信号生成回路と、前記n個のニューロンのうち、前記選択信号に基づき選択される前記第1のニューロンを含む2乃至d(dは3以上n以下の自然数)個のニューロンによる2体結合乃至d体結合の強さを示す複数の重み値と、前記n個のニューロンのnビットの出力値に基づき、前記2体結合乃至前記d体結合のそれぞれによって発生するエネルギーを示すd−1個のエネルギー値または前記d−1個のエネルギー値の変化分を算出するd−1個の演算回路と、前記d−1個のエネルギー値を加算した第1の加算値、または前記d−1個のエネルギー値の前記変化分を加算した第2の加算値を求め、前記第1の加算値または前記第2の加算値を出力する加算回路と、前記第1の加算値とノイズ値との加算結果に基づく第1の値と閾値との第1の比較結果、または、前記2体結合乃至前記d体結合のそれぞれによって発生する前記エネルギーの和を示し前記第2の加算値に基づき更新される第2の値と、前記ノイズ値との加算結果に基づく第3の値と前記閾値との第2の比較結果に基づき、前記第1のニューロンの第1の出力値を決定し出力する比較回路と、前記選択信号と前記第1の出力値とに基づいて前記nビットの出力値のうち、1ビットを更新した更新出力値を出力する更新回路と、前記更新出力値を保持し、前記演算回路が用いる前記nビットの出力値として出力する保持回路と、を有することを特徴とするイジング装置。

請求項5

n(nは3以上の自然数)個のニューロンのうち、出力値の更新を許容する第1のニューロンをランダムに選択するための選択信号を複数回出力するランダム信号生成回路と、前記n個のニューロンのうち、前記選択信号に基づき選択される前記第1のニューロンを含む2乃至d(dは3以上n以下の自然数)個のニューロンによる2体結合乃至d体結合の強さを示す複数の重み値と、前記n個のニューロンのnビットの出力値に基づき、前記2体結合乃至前記d体結合のそれぞれによって発生するエネルギーを示すd−1個のエネルギー値または前記d−1個のエネルギー値の変化分を算出するd−1個の演算回路と、前記d−1個のエネルギー値を加算した第1の加算値、または前記d−1個のエネルギー値の前記変化分を加算した第2の加算値を求め、前記第1の加算値または前記第2の加算値を出力する加算回路と、前記第1の加算値とノイズ値との加算結果に基づく第1の値と閾値との第1の比較結果、または、前記2体結合乃至前記d体結合のそれぞれによって発生する前記エネルギーの和を示し前記第2の加算値に基づき更新される第2の値と、前記ノイズ値との加算結果に基づく第3の値と前記閾値との第2の比較結果に基づき、前記第1のニューロンの第1の出力値を決定し出力する比較回路と、前記選択信号と前記第1の出力値とに基づいて前記nビットの出力値のうち、1ビットを更新した更新出力値を出力する更新回路と、前記更新出力値を保持し、前記演算回路が用いる前記nビットの出力値として出力する保持回路と、を有するイジング装置に対して、制御装置が、前記複数の重み値を設定し、前記制御装置が、前記ノイズ値のノイズ幅を制御する、ことを特徴とする情報処理装置の制御方法

技術分野

0001

本発明は、情報処理装置、イジング装置及び情報処理装置の制御方法に関する。

背景技術

0002

ノイマン型コンピュータが不得意とする多変数最適化問題解く方法として、イジング型エネルギー関数を用いたイジング装置(ボルツマンマシンと呼ばれる場合もある)がある。イジング装置は、計算対象の問題を、磁性体のスピンの振る舞いを表すモデルであるイジングモデルに置き換えて計算する。

0003

イジング装置は、ニューラルネットワークを用いてモデル化することもできる。その場合、イジング装置に含まれる複数のユニットビット)のそれぞれが、他のビットの状態と、他のビットと自身との結合の強さを示す重み値結合係数とも呼ばれる)とに応じて0または1を出力するニューロンとして機能する。イジング装置は、たとえば、シミュレテッドアニーリングにより、上記のようなエネルギー関数(コスト関数目的関数とも呼ばれる)の最小値が得られる各ビットの状態の組み合わせを、解として求める。

0004

従来、イジング装置をハードウェアで実現することによって、計算時間を短縮することが提案されている。
ところで、従来のイジング装置は、2つのビットの結合の強さを示す重み値を含むエネルギー関数(以下2次のエネルギー関数という)を用いるものである。イジング装置を、より多様な最適化問題に適用可能とするため、3つ以上のビットによる相互結合の強さを示す重み値を含むエネルギー関数(以下高次のエネルギー関数という)を用いることが考えられる。

0005

高次のエネルギー関数を用いた最適化問題の解決手法として、高次のエネルギー関数を用いた最適化問題を、複数の2次のエネルギー関数を用いた最適化問題に変換して解く手法が提案されている。

0006

特開平7−200512号公報

先行技術

0007

C. R. Schneider and H. C. Card, "Analog CMOS Deterministic BoltzmannCircuits", Journal of Solid-State Circuits, pp.907-914, 1993
R. Babbush, B. O'Gorman, and A. Aspuru-Guzik, "Resource Efficient Gadgets for Compiling Adiabatic Quantum Optimization Problems", July 31, 2013, [online], [平成28年5月26日検索]、インターネット
V. S. Denchev, S. Boixo, S. V. Isakov, N. Ding, R. Babbush, V. Smelyanskiy, J. Martinis, and H. Neven, "What is the Computational Value of Finite Range Tunneling?", January 26, 2016, [online], [平成28年5月26日検索]、インターネット

発明が解決しようとする課題

0008

しかし、従来、高次のエネルギー関数を用いた最適化問題を、2次のエネルギー関数を用いた最適化問題に変換する際に“ancillary bit”という補助的なビットを導入していた。この補助的なビットが増えることで、シミュレーテッド・アニーリングで最適解収束する速度の悪化や、使用できるビット数の減少を招くおそれがある。

0009

1つの側面では、本発明は、補助的なビットを使用せず、高次のエネルギー関数を用いた最適化問題をマッピングできる情報処理装置、イジング装置及び情報処理装置の制御方法を提供することを目的とする。

課題を解決するための手段

0010

1つの態様では、n(nは3以上の自然数)個のニューロンのうち、出力値更新許容する第1のニューロンをランダムに選択するための選択信号を複数回出力するランダム信号生成回路と、前記n個のニューロンのうち、前記選択信号に基づき選択される前記第1のニューロンを含む2乃至d(dは3以上n以下の自然数)個のニューロンによる2体結合乃至d体結合の強さを示す複数の重み値と、前記n個のニューロンのnビットの出力値に基づき、前記2体結合乃至前記d体結合のそれぞれによって発生するエネルギーを示すd−1個のエネルギー値または前記d−1個のエネルギー値の変化分を算出するd−1個の演算回路と、前記d−1個のエネルギー値を加算した第1の加算値、または前記d−1個のエネルギー値の前記変化分を加算した第2の加算値を求め、前記第1の加算値または前記第2の加算値を出力する加算回路と、前記第1の加算値とノイズ値との加算結果に基づく第1の値と閾値との第1の比較結果、または、前記2体結合乃至前記d体結合のそれぞれによって発生する前記エネルギーの和を示し前記第2の加算値に基づき更新される第2の値と、前記ノイズ値との加算結果に基づく第3の値と前記閾値との第2の比較結果に基づき、前記第1のニューロンの第1の出力値を決定し出力する比較回路と、前記選択信号と前記第1の出力値とに基づいて前記nビットの出力値のうち、1ビットを更新した更新出力値を出力する更新回路と、前記更新出力値を保持し、前記演算回路が用いる前記nビットの出力値として出力する保持回路と、を有するイジング装置と、前記ノイズ値のノイズ幅を制御する制御装置と、を有する情報処理装置が提供される。

0011

また、1つの態様では、n(nは3以上の自然数)個のニューロンのうち、出力値の更新を許容する第1のニューロンをランダムに選択するための選択信号を複数回出力するランダム信号生成回路と、前記n個のニューロンのうち、前記選択信号に基づき選択される前記第1のニューロンを含む2乃至d(dは3以上n以下の自然数)個のニューロンによる2体結合乃至d体結合の強さを示す複数の重み値と、前記n個のニューロンのnビットの出力値に基づき、前記2体結合乃至前記d体結合のそれぞれによって発生するエネルギーを示すd−1個のエネルギー値または前記d−1個のエネルギー値の変化分を算出するd−1個の演算回路と、前記d−1個のエネルギー値を加算した第1の加算値、または前記d−1個のエネルギー値の前記変化分を加算した第2の加算値を求め、前記第1の加算値または前記第2の加算値を出力する加算回路と、前記第1の加算値とノイズ値との加算結果に基づく第1の値と閾値との第1の比較結果、または、前記2体結合乃至前記d体結合のそれぞれによって発生する前記エネルギーの和を示し前記第2の加算値に基づき更新される第2の値と、前記ノイズ値との加算結果に基づく第3の値と前記閾値との第2の比較結果に基づき、前記第1のニューロンの第1の出力値を決定し出力する比較回路と、前記選択信号と前記第1の出力値とに基づいて前記nビットの出力値のうち、1ビットを更新した更新出力値を出力する更新回路と、前記更新出力値を保持し、前記演算回路が用いる前記nビットの出力値として出力する保持回路と、を有するイジング装置が提供される。

0012

また、1つの態様では、n(nは3以上の自然数)個のニューロンのうち、出力値の更新を許容する第1のニューロンをランダムに選択するための選択信号を複数回出力するランダム信号生成回路と、前記n個のニューロンのうち、前記選択信号に基づき選択される前記第1のニューロンを含む2乃至d(dは3以上n以下の自然数)個のニューロンによる2体結合乃至d体結合の強さを示す複数の重み値と、前記n個のニューロンのnビットの出力値に基づき、前記2体結合乃至前記d体結合のそれぞれによって発生するエネルギーを示すd−1個のエネルギー値または前記d−1個のエネルギー値の変化分を算出するd−1個の演算回路と、前記d−1個のエネルギー値を加算した第1の加算値、または前記d−1個のエネルギー値の前記変化分を加算した第2の加算値を求め、前記第1の加算値または前記第2の加算値を出力する加算回路と、前記第1の加算値とノイズ値との加算結果に基づく第1の値と閾値との第1の比較結果、または、前記2体結合乃至前記d体結合のそれぞれによって発生する前記エネルギーの和を示し前記第2の加算値に基づき更新される第2の値と、前記ノイズ値との加算結果に基づく第3の値と前記閾値との第2の比較結果に基づき、前記第1のニューロンの第1の出力値を決定し出力する比較回路と、前記選択信号と前記第1の出力値とに基づいて前記nビットの出力値のうち、1ビットを更新した更新出力値を出力する更新回路と、前記更新出力値を保持し、前記演算回路が用いる前記nビットの出力値として出力する保持回路と、を有するイジング装置に対して、制御装置が、前記複数の重み値を設定し、前記制御装置が、前記ノイズ値のノイズ幅を制御する、情報処理装置の制御方法が提供される。

発明の効果

0013

開示の情報処理装置、イジング装置及び情報処理装置の制御方法によれば、補助的なビットを使用せず、高次のエネルギー関数を用いた最適化問題をマッピングできる。

図面の簡単な説明

0014

第1の実施の形態の情報処理装置の一例を示す図である。
d体結合のローカルフィールド値を算出する演算回路の一例を示す図である。
更新回路と保持回路の一例を示す図である。
3次のエネルギー関数を用いた最適化問題がマッピングされるイジング装置の一例を示す図である。
2体結合によって発生するローカルフィールド値を算出する演算回路の一例を示す図である。
3体結合によって発生するローカルフィールド値を算出する演算回路の一例を示す図である。
情報処理装置の動作の一例の流れを示すフローチャートである。
シミュレーテッド・アニーリングの一例の流れを示すフローチャートである。
シミュレーテッド・アニーリングの様子を示す図である。
2体結合の重み値の例を示す図である。
3体結合の重み値の例を示す図である。
ニューロン数がn個のときの3体結合の重み値の例を示す図である。
ニューロン数がn個のときの4体結合の重み値の例を示す図である。
重み値リスト作成処理の一例の流れを示すフローチャートである。
重み値リストの例を示す図である。
第2の実施の形態の情報処理装置の一例を示す図である。
回路部の一例を示す図である。
2体結合によって発生するローカルフィールド値の変化分を算出する演算回路の一例を示す図である。
3体結合によって発生するローカルフィールド値の変化分を算出する演算回路の一例を示す図である。
2出力値選択回路の一例を示す図である。
第2の実施の形態の情報処理装置におけるシミュレーテッド・アニーリングの一例の流れを示すフローチャートである。

実施例

0015

以下、発明を実施するための形態を、図面を参照しつつ説明する。
(第1の実施の形態)
図1は、第1の実施の形態の情報処理装置の一例を示す図である。

0016

情報処理装置1は、イジング装置2と制御装置3とメモリ4を有しており、制御装置3によって、高次(d≧3)のエネルギー関数を用いた最適化問題がイジング装置2にマッピングされる。また、本実施の形態のイジング装置2は、n(nは3以上の自然数)個のニューロンを有するニューラルネットワークとして機能する。

0017

イジング装置2は、ランダム信号生成回路10、演算回路11a1,11a2,…,11a(d−1)、加算回路12、比較回路13、更新回路14、保持回路15、バイアス値保持回路16、ノイズ発生回路17を有する。イジング装置2は、たとえば、1つの半導体集積回路チップ)で実現される。

0018

ランダム信号生成回路10は、n個のニューロンのうち、出力値の更新を許容するニューロンをランダムに選択するための選択信号を複数回出力する。たとえば、n個のニューロンには、それぞれ異なる識別番号(以下ニューロンIDという)が割り当てられている。図1には、ランダム信号生成回路10が、ニューロンIDとしてi(1≦i≦n)を指定する選択信号を出力している様子が示されている。なお、ランダム信号生成回路10として、たとえば、LFSR(Linear Feedback Shift Registers)などを用いることができる。

0019

d−1(dは3以上n以下の自然数)個の演算回路11a1〜11a(d−1)は、ランダム信号生成回路10から出力される選択信号と、保持回路15から出力されるn個のニューロンのnビットの出力値x1,x2,…,xnを受ける。そして、演算回路11a1〜11a(d−1)は、選択信号で選択されたニューロンを含む2〜d個のニューロンによる2体結合〜d体結合の強さを示す複数の重み値と、出力値x1〜xnに基づき、d−1個のエネルギー値hi2,hi3,…,hidを算出する。なお、以下ではエネルギー値を、ローカルフィールド値という。ローカルフィールド値hi2〜hidは、2体結合〜d体結合のそれぞれによって発生するエネルギーを示す。

0020

2体結合〜d体結合の強さを示す重み値(以下単に2体結合〜d体結合の重み値という)は、たとえば、制御装置3により、計算対象の問題に応じて設定され、演算回路11a1〜11a(d−1)内の記憶部(たとえば、レジスタ)に記憶される。図1には、n=l個のニューロンの2体結合、3体結合及び4体結合の重み値の例が示されている。たとえば、ニューロンID=i,kのニューロン20,21による2体結合の重み値は、Wikと表記されている。また、ニューロンID=k,jのニューロン21,22による2体結合の重み値は、Wjkと表記されている。また、ニューロンID=i,jのニューロン20,22による2体結合の重み値は、Wijと表記されている。さらに、ニューロンID=i,j,kのニューロン20〜22による3体結合の重み値は、Wijkと表記されている。また、ニューロンID=i,j,k,lのニューロン20〜23による4体結合の重み値は、Wijklと表記されている。

0021

加算回路12は、ローカルフィールド値hi2〜hidを加算して加算結果を出力する。
比較回路13は、加算回路12での加算結果とノイズ値とバイアス値との加算結果と閾値(たとえば、0)との比較結果に基づき、選択信号で選択されたニューロンの出力値を決定し出力する。比較回路13は、たとえば、加算回路12での加算結果とノイズ値とバイアス値とを加算する加算回路を含んでいる。なお、以下では、加算回路12での加算結果とバイアス値とを加算した値(エネルギー値)を、ローカルフィールド値hiという。

0022

たとえば、ローカルフィールド値hiとノイズ値との加算結果が負のときには、比較回路13は1を出力し、ローカルフィールド値hiとノイズ値との加算結果が正のときには、比較回路13は0を出力する。なお、バイアス値は0であってもよい。

0023

更新回路14は、選択信号と、比較回路13から出力される出力値とに基づいて、n個のニューロンのnビットの出力値のうち、1ビットを更新した更新出力値を出力する。たとえば、比較回路13から出力されるニューロンID=iのニューロンの出力値が、前の値と異なるときには、nビットの出力値のうち、i番目のビットを更新したnビットの更新出力値が出力される。なお、比較回路13から出力されるニューロンID=iのニューロンの出力値が、前の値と同じときには、更新回路14は、更新出力値を出力しなくてもよい。

0024

保持回路15は、クロック信号clkに同期して更新回路14から出力される更新出力値を保持し、演算回路11a1〜11a(d−1)が用いるn個のニューロンのnビットの出力値として出力する。保持回路15は、たとえば、複数のフリップフロップを用いて実現される。クロック信号clkは、たとえば、制御装置3から供給される。なお、クロック信号clkは、イジング装置2内またはイジング装置2外に設けられる図示しないクロック信号生成回路から供給されるようにしてもよい。

0025

バイアス値保持回路16は、たとえば、レジスタまたはフラッシュメモリなどであり、n個のニューロンのそれぞれのバイアス値を保持している。そしてバイアス値保持回路16は、ランダム信号生成回路10から出力される選択信号で指定されるニューロンのバイアス値を、たとえば、比較回路13に供給する。バイアス値は、たとえば、制御装置3により、計算対象の問題に応じて予め設定される。

0026

ノイズ発生回路17は、制御装置3の制御のもと、シミュレーテッド・アニーリングを行うためにノイズ値を出力する。ノイズ発生回路17も、ランダム信号生成回路10と同様に、たとえば、LFSRを用いて実現可能である。また、ノイズ発生回路17は、たとえば、増幅回路を有している。制御装置3が増幅回路の増幅率を変化させることで、ノイズ値の振幅が制御可能である。

0027

制御装置3は、ランダム信号生成回路10の制御や、ノイズ幅を制御するためにノイズ発生回路17を制御する。たとえば、制御装置3は、シミュレーテッド・アニーリングを実現するために、ノイズ発生回路17に含まれる増幅回路を制御して、ノイズ値のノイズ幅(ノイズの振幅)を徐々に小さくさせる。また、制御装置3は、計算対象の最適化問題に応じて、予め複数の重み値や複数のバイアス値を設定する。そして、制御装置3は、バス(図示せず)を介して演算回路11a1〜11a(d−1)内のレジスタに複数の重み値を書き込み、複数のバイアス値をバイアス値保持回路16に書き込むことでマッピングを行う。

0028

制御装置3は、たとえば、プロセッサで実現できる。プロセッサは、たとえば、CPU(Central Processing Unit)、MPU(Micro Processing Unit)、DSP(Digital Signal Processor)、ASIC(Application Specific IntegratedCircuit)、またはPLD(Programmable Logic Device)である。またプロセッサは、CPU、MPU、DSP、ASIC、PLDのうちの2以上の要素の組み合わせであってもよい。また、制御装置3は、PC(パーソナルコンピュータ)やサーバコンピュータなどであってもよい。

0029

メモリ4は、たとえば、制御装置3がプロセッサの場合、プロセッサが実行するOS(Operating System)やミドルウェアアプリケーションソフトウェアなどのソフトウェアプログラム、及びデータを記憶する不揮発性記憶装置である。メモリ4は、後述する重み値リストを生成するプログラムを記憶してもよい。なお、不揮発性の記憶装置としては、たとえば、フラッシュメモリやSSD(Solid State Drive)、HDD(Hard Disk Drive)などが用いられる。

0030

以上のような情報処理装置1は、イジング型のエネルギー関数の演算をハードウェアで実現するものである。なお、高次のエネルギー関数E(x)は、たとえば、以下の式(1)で定義される。

0031

0032

式(1)において、右辺の1項目は、全ニューロンから選択可能な2つのニューロンの全組み合わせについて、漏れ重複なく、2つのニューロンの出力値と2体結合の重み値との積を積算したものである。右辺の2項目は、全ニューロンのそれぞれのバイアス値と出力値との積を積算したものである。biは、ニューロンID=iのニューロンのバイアス値を示している。右辺の3項目は、全ニューロンから選択可能な3つのニューロンの全組み合わせについて、漏れと重複なく、3つのニューロンの出力値と3体結合の重み値との積を積算したものである。右辺の4項目は、全ニューロンから選択可能な4つのニューロンの全組み合わせについて、漏れと重複なく、4つのニューロンの出力値と4体結合の重み値との積を積算したものである。

0033

このようなイジング型のエネルギー関数において、あるニューロンの出力値を1から0または0から1に変化させたときのエネルギー値の変化は、そのニューロンと他のニューロンとの結合の重み値と、各ニューロンの出力値から決めることができる。

0034

たとえば、ニューロンID=iのニューロンの出力値が変化したときのエネルギーの変化は以下の式(2)で表せる。

0035

0036

式(2)において、xiが1のとき、2xi−1は1となり、xiが0のとき、2xi−1は−1となる。また、式(2)において、ニューロンID=iのニューロンが関わる結合によって発生するエネルギーを示すローカルフィールド値hiは、以下の式(3)のように表すことができる。

0037

0038

式(3)において、右辺の2項目はニューロンID=iのニューロンを含む2体結合によって発生するエネルギーを表す。また、右辺の3項目はニューロンID=iのニューロンを含む3体結合によって発生するエネルギーを表す。Wijkは、n個のニューロンのうち、ニューロンID=i,j,kのニューロンによる3体結合の重み値である。また、右辺の4項目はニューロンID=iのニューロンを含む4体結合によって発生するエネルギーを表す。Wijklは、n個のニューロンのうち、ニューロンID=i,j,k,lのニューロンによる4体結合の重み値である。

0039

式(2)、式(3)から、ローカルフィールド値hiが負で、且つ、2xi−1が正のとき、または、ローカルフィールド値hiが正で、且つ、2xi−1が負のとき、ΔEiが負となり、エネルギーが減少する。

0040

図1に示した演算回路11a1〜11a(d−1)のそれぞれは、このような2体結合乃至d体結合のそれぞれによって発生するエネルギーを示すローカルフィールド値hi2〜hidを算出する。

0041

たとえば、演算回路11a1は、式(3)の右辺の2項目であるローカルフィールド値hi2を算出し、演算回路11a2は、式(3)の3項目であるローカルフィールド値hi3を算出する。

0042

(演算回路の一例)
図2は、d体結合のローカルフィールド値を算出する演算回路の一例を示す図である。
演算回路11a(d−1)は、レジスタ30a1,30a2,…,30an、選択回路31、乗算部32、加算部33を有している。

0043

レジスタ30a1〜30anには、d個のニューロンによるd体結合の複数の重み値が記憶されている。たとえば、レジスタ30a1には、ニューロンID=1のニューロンを含むd個のニューロンによるd体結合の複数の重み値が記憶されている。レジスタ30a2には、ニューロンID=2のニューロンを含むd個のニューロンによるd体結合の複数の重み値が記憶されている。また、レジスタ30anには、ニューロンID=nのニューロンを含むd個のニューロンによるd体結合の複数の重み値が記憶されている。

0044

選択回路31は、ランダム信号生成回路10が出力する選択信号に基づき、レジスタ30a1〜30anの何れか1つに記憶されている複数の重み値を出力する。たとえば、選択回路31は、ニューロンID=1のニューロンを指定する選択信号を受けると、レジスタ30a1に記憶されている複数の重み値を出力する。

0045

乗算部32と加算部33は、出力値x1〜xnと、選択回路31が出力した複数の重み値とに基づき、式(3)に示したようなローカルフィールド値hiのうち、d体結合により発生するエネルギー(ローカルフィールド値hid)を算出する。乗算部32はm個乗算回路32a1〜32amを有し、加算部33は、p個の加算回路33a1〜33apを有している。乗算回路32a1〜32amと加算回路33a1〜33apの数については後述する。

0046

(更新回路と保持回路の一例)
図3は、更新回路と保持回路の一例を示す図である。
更新回路14は、マルチプレクサ14a、選択回路14b1,14b2,…,14bnを有している。また、保持回路15は、フリップフロップ15a1,15a2,…,15anを有している。

0047

マルチプレクサ14aは、ランダム信号生成回路10から出力される選択信号に基づき、選択回路14b1〜14bnの選択信号を生成する。マルチプレクサ14aは、たとえば、n個のニューロンのうち1つのニューロンを選択する選択信号を受けると、選択回路14b1〜14bnのうち、そのニューロンに対応したものに、選択信号として1を供給し、その他に0を供給する。たとえば、マルチプレクサ14aは、ニューロンID=1のニューロンを指定する選択信号を受けると、選択回路14b1に選択信号として1を供給し、選択回路14b2〜14bnに選択信号として0を供給する。

0048

選択回路14b1〜14bnは、n個のニューロンのそれぞれに対応してn個設けられている。選択回路14b1〜14bnは、それぞれ2つの入力端子を有している。一方の入力端子には、フリップフロップ15a1〜15anの何れか1つの出力端子が接続されており、他方の入力端子には、比較回路13の出力端子が接続されている。選択回路14b1〜14bnは、マルチプレクサ14aから供給される選択信号が1のときは、比較回路13から出力されるニューロンの出力値を選択して出力する。選択回路14b1〜14bnは、マルチプレクサ14aから供給される選択信号が0のときは、フリップフロップ15a1〜15anから出力される値を選択して出力する。

0049

保持回路15のフリップフロップ15a1〜15anは、クロック信号clkに同期して選択回路14b1〜14bnから出力される値(nビットの更新出力値)を取り込み、出力する。

0050

ランダム信号生成回路10が、たとえば、ニューロンID=1のニューロンを指定する選択信号を出力しているとき、選択回路14b1は、比較回路13から出力されるそのニューロンの出力値を選択して出力する。選択回路14b2〜14bnは、フリップフロップ15a2〜15anから出力される値を選択して出力する。これにより、保持回路15は、ニューロンID=1のニューロンに対応したビットの値だけ更新されたnビットの出力値を出力する。

0051

(3次のエネルギー関数を用いた最適化問題がマッピングされるイジング装置の例)
図4は、3次のエネルギー関数を用いた最適化問題がマッピングされるイジング装置の一例を示す図である。図4において、図1に示した要素と同じ要素については同一符号が付されている。

0052

3次のエネルギー関数を用いた最適化問題がマッピングされるイジング装置2aでは、演算回路11a1,11a2の数は、2つとなる。演算回路11a1は、ニューロンID=iのニューロンを含む2つのニューロンによる2体結合によって発生するエネルギーであるローカルフィールド値hi2を算出する。演算回路11a2は、ニューロンID=iのニューロンを含む3つのニューロンによる3体結合によって発生するエネルギーであるローカルフィールド値hi3を算出する。

0053

加算回路12aは、2つのローカルフィールド値hi2,hi3の加算結果を出力する。
図5は、2体結合によって発生するローカルフィールド値を算出する演算回路の一例を示す図である。

0054

演算回路11a1は、レジスタ40a1,40a2,…,40an、選択回路41、乗算部42、加算部43を有している。
レジスタ40a1〜40anには、2個のニューロンによる2体結合の複数の重み値が記憶されている。たとえば、レジスタ40a1には、ニューロンID=1のニューロンを含む2つのニューロンによる2体結合の重み値W12,W13,…,W1nが記憶されている。レジスタ40a2には、ニューロンID=2のニューロンを含む2つのニューロンによる2体結合の複数の重み値W21,W23,…,W2nが記憶されている。また、レジスタ40anには、ニューロンID=nのニューロンを含む2つのニューロンによる2体結合の重み値Wn1,Wn2,…,Wn(n-1)が記憶されている。

0055

選択回路41は、ランダム信号生成回路10が出力する選択信号に基づき、レジスタ40a1〜40anの何れか1つに記憶されている複数の重み値を出力する。
乗算部42はn個の乗算回路42a1〜42anを有し、加算部43は、q個の加算回路43a1〜43aqを有している。乗算部42と加算部43は、出力値x1〜xnと、選択回路41が出力した複数の重み値とに基づき、式(3)に示したようなローカルフィールド値hiのうち、2体結合により発生するエネルギー(ローカルフィールド値hi2)を算出する。

0056

図6は、3体結合によって発生するローカルフィールド値を算出する演算回路の一例を示す図である。
演算回路11a2は、レジスタ50a1,50a2,…,50an、選択回路51、乗算部52、加算部53を有している。

0057

レジスタ50a1〜50anには、3個のニューロンによる3体結合の複数の重み値が記憶されている。たとえば、レジスタ50a1には、ニューロンID=1のニューロンを含む3つのニューロンによる3体結合の重み値W121,W131,W132,…,W1n(n-1)が記憶されている。レジスタ50a2には、ニューロンID=2のニューロンを含む3つのニューロンによる3体結合の複数の重み値W221,W231,W232,…,W2n(n-1)が記憶されている。また、レジスタ50anには、ニューロンID=nのニューロンを含む3つのニューロンによる3体結合の重み値Wn21,Wn31,Wn32,…,Wnn(n-1)が記憶されている。

0058

選択回路51は、ランダム信号生成回路10が出力する選択信号に基づき、レジスタ50a1〜50anの何れか1つに記憶されている複数の重み値を出力する。
乗算部52はr個の乗算回路52a1〜52arを有し、加算部53は、s個の加算回路53a1〜53asを有している。乗算部52と加算部53は、出力値x1〜xnと、選択回路51が出力した複数の重み値とに基づき、式(3)に示したようなローカルフィールド値hiのうち、3体結合により発生するエネルギー(ローカルフィールド値hi3)を算出する。

0059

(第1の実施の形態の情報処理装置の動作例)
以下、制御装置3によって制御される図1の情報処理装置1の動作の一例を、フローチャートを用いて説明する。

0060

図7は、情報処理装置の動作の一例の流れを示すフローチャートである。
まず、制御装置3は、たとえば、メモリ4に記憶されている2体結合〜d体結合の重み値を抽出する(ステップS1)。なお、計算対象の問題に応じた重み値は、予め用意されているものとする。

0061

次に、制御装置3は、抽出した重み値を、演算回路11a1〜11a(d−1)のレジスタ(たとえば、演算回路11a(d−1)ではレジスタ30a1〜30an)に、書き込む(ステップS2)。つまり、ステップS2の処理では、最適化問題のマッピングが行われる。なお、ステップS2の処理で、制御装置3が、各ニューロンのバイアス値をバイアス値保持回路16に書き込んでもよい。

0062

その後、制御装置3の制御によりシミュレーテッド・アニーリングが実行され(ステップS3)、その結果であるn個のニューロンの出力値x1〜xnを最適化問題の解として、制御装置3が取得する(ステップS4)ことで、処理が終了する。

0063

図8は、シミュレーテッド・アニーリングの一例の流れを示すフローチャートである。
まず、制御装置3の制御のもと、ランダム信号生成回路10は、出力値の更新を許容するニューロン(ニューロンID=iのニューロン)をランダムに選択するための選択信号を出力する(ステップS10)。

0064

その後、演算回路11a1〜11a(d−1)により、2体結合〜d体結合により発生するエネルギーであるローカルフィールド値hi2〜hidの算出が行われる(ステップS11)。そして、加算回路12により、ローカルフィールド値hi2〜hidが加算される(ステップS12)。

0065

ローカルフィールド値hi(加算回路12での加算結果とバイアス値との加算値)とノイズ値との加算結果が、閾値(たとえば、0)より小さいとき(ステップS13:YES)、比較回路13は、出力値(new_xi)として1を出力する(ステップS14)。

0066

ローカルフィールド値hiとノイズ値との加算結果が、閾値以上のとき(ステップS13:NO)、比較回路13は、出力値(new_xi)として0を出力する(ステップS15)。

0067

ステップS14,S15の処理後、new_xiが、ニューロンID=iのニューロンの元の出力値xiと異なるとき(ステップS16:NO)、更新回路14は、nビットの出力値のうち、i番目のビットを更新した更新出力値を出力する(ステップS17)。その後、ステップS10からの処理が繰り返される。

0068

new_xiが、出力値xiと同じとき(ステップS16:YES)、制御装置3は、出力値x1〜xn(ニューロン状態)が、一定期間変化していないか否かを判定する(ステップS18)。出力値x1〜xnが、一定期間変化していないとき(ステップS18:YES)、制御装置3は、シミュレーテッド・アニーリングを終了する。

0069

出力値x1〜xnが、一定期間内で変化しているとき(ステップS18:NO)、ステップS10からの処理が繰り返される。
更新を許容するニューロンの選択が行われるたびに、ノイズ発生回路17が、制御装置3の制御のもと、ノイズ幅を徐々に小さくしていくことで、シミュレーテッド・アニーリングが行われる。

0070

ノイズ発生回路17は、たとえば、比較回路13の出力値が1となる確率が、シグモイド関数に従うようなノイズ値を発生する。たとえば、ノイズ発生回路17は、ニューロンID=iのニューロンの出力値xiが1となる確率Pi(hi)が、以下の式(4)の関係になるようなノイズ値を生成する。

0071

0072

式(4)において、Tは、実効温度である。
なお、式(4)に示すような確率Pi(hi)を得るために生成されるノイズ値nsの確率密度関数p(ns)は、以下の式(5)のようになる。

0073

0074

図9は、シミュレーテッド・アニーリングの様子を示す図である。
縦軸はエネルギーEであり、横軸は全ニューロンの出力値の組み合わせqKを示している。組み合わせqKは、“000…0”から“111…1”まである。図9では、ノイズ幅がW1、W2、W3と小さくなっていくときの、解の収束の様子が示されている。ノイズ幅を小さくしていくことは、式(5)の実効温度Tを小さくしていくことに相当する。

0075

ノイズ幅がW1のとき、解が、局所解(エネルギーが局所的な極小値となる解)qk1,qk2,qk4,qk5となっても、エネルギーが高くなる方向に変化でき、局所解から脱出できる。ノイズ幅が、W2、W3と徐々に小さくなるにつれて、解の変化は制限されていき、最終的に、最適解(エネルギーが最小値となる解)qk3に収束する。

0076

以上のような第1の実施の形態の情報処理装置1及びイジング装置2では、2〜d個のニューロンによる2体結合〜d体結合のそれぞれにより発生するエネルギー(ローカルフィールド値hi2〜hid)が演算回路11a1〜11a(d−1)によって算出される。そして、ローカルフィールド値hi2〜hidの加算結果に基づく値と閾値との比較結果に基づき各ニューロンの出力値が決定される。

0077

これにより、補助的なビットなどを設けずとも、高次のエネルギー関数の最適化問題を、イジング装置2にマッピングできる。このため、補助的なビットを設けることで生じる可能性のあった、シミュレーテッド・アニーリングでの最適解への収束速度の悪化や、使用できるビット数の減少を招くことを抑制できる。

0078

また、高次のエネルギー関数を用いた最適化問題を、複数の2次のエネルギー関数を用いた最適化問題に変換するなどの処理が不要であるため、最適化問題を容易にイジング装置2にマッピングできる。

0079

なお、高次のエネルギー関数を用いた最適化問題には、NP(Non-deterministic Polynomial)完全問題などがある。
(重み値の抽出及び重み値の書き込み処理の例)
以下、図7に示したステップS1,S2の処理の一例を説明する。

0080

図10は、2体結合の重み値の例を示す図である。
図10では、ニューロン数が4のときの2体結合の複数の重み値を含む重み値群60aが示されている。たとえば、W21は、ニューロンID=2のニューロンと、ニューロンID=1のニューロンによる2体結合の重み値である。

0081

ボルツマンマシンにおいては、Wii=0、Wij=Wji(i,jは1以上n以下の自然数)という条件がある。このため、W21=W12、W31=W13、W41=W14、W42=W24、W43=W34であり、図10中の重み値群60b内の重み値であるW11,W22,W33,W44は0である。

0082

したがって、重み値W11,W22,W33,W44は、用いなくてよい。一方、W21とW12のような対象関係にある重み値は、図5に示したように、2体結合で発生するローカルフィールド値hi2を算出する際には両方用いられる。

0083

図11は、3体結合の重み値の例を示す図である。
図11では、ニューロン数が4であり、ニューロンID=2のニューロンを含む3つのニューロンによる3体結合の重み値を含む重み値群61aが示されている。たとえば、W231は、ニューロンID=2のニューロンと、ニューロンID=3のニューロンと、ニューロンID=1のニューロンによる3体結合の重み値である。

0084

ボルツマンマシンの上記2条件を3体結合の重み値にも拡張すると、Wijk=0(i=j、i=k、j=kまたはi=j=kの場合)、Wijk=Wikj=Wjik=Wjki=Wkij=Wkji(i,j,kは1以上n以下の自然数)となる。

0085

このため、W221=W212、W231=W213、W241=W214、W242=W224、W243=W234であり、図11中の重み値群61b,61c,61d内の重み値は0である。
上記の点を鑑みて、本実施の形態のイジング装置2,2aが、ニューロンID=2のニューロンを含む3体結合で発生するローカルフィールド値h23を算出する際に用いる重み値の数は、図11三角形領域61e内の重み値の数(図11の例では6個)とする。

0086

図12は、ニューロン数がn個のときの3体結合の重み値の例を示す図である。
図12では、3体結合の重み値Wijk(i,j,kは1以上n以下の自然数)を含む重み値群65a1,65a2,…,65anが示されている。

0087

重み値群65a1は、i=1の重み値W1jkを含み、重み値群65a2は、i=2の重み値W2jkを含み、重み値群65anは、i=nの重み値Wnjkを含む。
重み値群65a1〜65anのそれぞれにおいて、本実施の形態のイジング装置2,2aがローカルフィールド値hi3を算出する際に用いる重み値は、三角形領域65b1,65b2,…,65bnに含まれるものに制限される。すなわち、図12に示すようなマトリクス状に配置されている重み値のうち、対角線部分の複数の重み値(たとえば、重み値群65a1のW111,W122,…,W1nn)及びその下に位置する複数の重み値については用いられない。

0088

三角形領域65b1〜65bnに含まれる重み値の数Nwは、式(6)で表せる。

0089

0090

Nwは、重み値群65a1〜65anのそれぞれに含まれる重み値の個数(n×n)から上記対角線部分の重み値の個数(n)を引いた値を、1/2した値である。つまり、ローカルフィールド値hi3を算出する際に用いる重み値の数は、iごとにNw個となる。

0091

図13は、ニューロン数がn個のときの4体結合の重み値の例を示す図である。
図13では、4体結合の重み値Wijkl(i,j,k,lは1以上n以下の自然数)を含む重み値群66a1,66a2,…,66an,67a1,…,67anが示されている。

0092

重み値群66a1は、i=1,j=1の重み値W11klを含み、重み値群66a2は、i=1,j=2の重み値W12klを含み、重み値群66anは、i=1,j=nの重み値W1nklを含む。重み値群67a1〜67anは、i=2、j=1〜nの重み値W21kl〜W2nklを含む。

0093

重み値群66a1〜66an,67a1〜67anのそれぞれにおいて、イジング装置2がローカルフィールド値hi4を算出する際に用いる重み値は、三角形領域66b1,66b2,…,66bn,67b1,…,67bnに含まれるものに制限される。三角形領域66b1〜66bn,67b1〜67bnに含まれる重み値の数Nwは、上記の式(6)で表せる。

0094

つまり、4体結合で発生するローカルフィールド値hi4を算出する際に用いる重み値の数は、iごとにn×Nw個となる。
上記の観点から、d≧3の場合、iごとのd体結合の重み値の数は、以下の式(7)で表せる。

0095

0096

制御装置3は、上記の内容に基づいて、たとえば、以下のような処理の流れで、演算回路11a1〜11a(d−1)内のレジスタに書き込む重み値のリストを作成する。
図14は、重み値リストの作成処理の一例の流れを示すフローチャートである。

0097

なお、以下ではメモリ4に、たとえば、図10図13に示したような複数の重み値が予め記憶されているものとする。
まず、制御装置3は、変数curr_dを2とする(ステップS20)。そして、制御装置3は、変数curr_dが2であるか否かを判定する(ステップS21)。

0098

変数curr_dが2であるときには(ステップS21:YES)、制御装置3は、重み値リストのサイズSを、ニューロン数と同じnと決定する(ステップS22)。なお、値が0となる重み値Wiiを用いない場合には、サイズS=n−1であってもよい。

0099

ステップS22の処理後、制御装置3は、2体結合用のサイズSの重み値リストを生成する(ステップS23)。サイズSの重み値リストは、n個生成される。生成された重み値リストは、たとえば、メモリ4に記憶される。

0100

そして、制御装置3は、n個の重み値リストのうち、i番目の重み値リストに、ニューロンID=iのニューロンを含む2つのニューロンによる2体結合の重み値を、メモリ4に記憶されている2体結合の重み値群から抽出してコピーする(ステップS24)。制御装置3は、このような処理をiごとに行う。

0101

たとえば、n=4の場合、制御装置3は、図10に示したような重み値群60aから、ニューロンID=1のニューロンを含む2つのニューロンによる2体結合の重み値W12,W13,W14を、1番目の重み値リストにコピーする。また、制御装置3は、重み値群60aから、ニューロンID=2のニューロンを含む2つのニューロンによる2体結合の重み値W21,W23,W24を、2番目の重み値リストにコピーする。また、制御装置3は、重み値群60aから、ニューロンID=3のニューロンを含む2つのニューロンによる2体結合の重み値W31,W32,W34を、3番目の重み値リストにコピーする。さらに、制御装置3は、重み値群60aから、ニューロンID=4のニューロンを含む2つのニューロンによる2体結合の重み値W41,W42,W43を、4番目の重み値リストにコピーする。

0102

一方、変数curr_dが2ではないときには(ステップS21:NO)、制御装置3は、式(7)に基づき、重み値リストのサイズSを算出する(ステップS25)。
ステップS25の処理後、制御装置3は、curr_d体結合用のサイズSの重み値リストを生成する(ステップS26)。curr_d体結合用のサイズSの重み値リストも、n個生成される。生成された重み値リストは、たとえば、メモリ4に記憶される。

0103

そして、制御装置3は、i番目の重み値リストに、ニューロンID=iのニューロンを含むcurr_d個のニューロンによるcurr_d体結合の重み値を、curr_d体結合の重み値群から抽出してコピーする(ステップS27)。このとき、制御装置3は、コピーする重み値を、curr_d体結合の重み値群のうち、たとえば、図13に示したような三角形領域66b1〜66bnに含まれる複数の重み値に限定する。制御装置3は、このような処理をiごとに行う。

0104

図15は、重み値リストの例を示す図である。
図15には、curr_d=4のときに生成されるi=1番目の重み値リスト70の例が示されている。重み値リスト70にコピーされた重み値W1121〜W1nn(n-1)のうち、重み値W1121〜W11n(n-1)は、図13に示した三角形領域66b1に含まれるものでありNw個ある。その他の重み値は、図13に示した三角形領域66b2〜66bnに含まれるものである。したがって、重み値リスト70に含まれる重み値の個数は、n×Nw個である。

0105

図14のステップS24,S27の処理後、制御装置3は、変数curr_dをインクリメントし(ステップS28)、curr_d≦dであるか否かを判定する(ステップS29)。

0106

curr_d≦dであるときには(ステップS29:YES)、制御装置3は、ステップS21からの処理を繰り返す。curr_d≦dではないときには(ステップS29:NO)、制御装置3は、重み値リストの作成処理を終了する。

0107

なお、上記の説明では、制御装置3が重み値リストを生成するものとしたが、これに限定されない。重み値リストは、情報処理装置1とは別の装置からネットワーク経由で情報処理装置1に送信され、メモリ4に記憶されてもよい。別の装置は、ユーザによって操作されるクライアントコンピュータなどのクライアント装置でもよいし、サーバコンピュータなどのサーバ装置でもよい。

0108

制御装置3は、上記のような重み値リストに含まれる重み値を、たとえば、図1に示した演算回路11a1〜11a(d−1)内のレジスタに書き込む。
たとえば、図2に示した演算回路11a(d−1)のレジスタ30a1〜30anには、curr_d=d(d≧3)のときに生成されたi=1番目からi=n番目の重み値リストの重み値が書き込まれる。たとえば、レジスタ30a1には、i=1番目の重み値リストの重み値が書き込まれ、レジスタ30anには、i=n番目の重み値リストの重み値が書き込まれる。そのため、レジスタ30a1〜30anのそれぞれに書き込まれる重み値の数は、前述の式(7)で表される数となる。

0109

上記のように複数の重み値の対称性などに基づいて、レジスタ30a1〜30anのそれぞれに書き込まれる重み値の数が、式(7)で示される数に制限されるため、レジスタ30a1〜30anのサイズが増加することを抑制できる。また、用いられる重み値の数が制限されるため、その重み値を用いてローカルフィールド値を算出する乗算部32の乗算回路32a1〜32amの数m、加算部33の加算回路33a1〜33apの数pについても増加を抑制できる。

0110

乗算回路32a1〜32amの数mについては、以下の式(8)のようになる。

0111

0112

また、加算回路33a1〜33apの数pについては、以下の式(9)のようになる。

0113

0114

(第2の実施の形態)
図16は、第2の実施の形態の情報処理装置の一例を示す図である。図16において、図1に示した要素と同じ要素については同一符号が付されている。

0115

第2の実施の形態の情報処理装置80におけるイジング装置81は、回路部81a1,81a2,81a3,81a4、更新制御回路81bを有している。
回路部81a1〜81a4のそれぞれは、1つのニューロンに相当する。回路部81a1〜81a4としては、たとえば、DeGloriaアルゴリズムと呼ばれるアルゴリズムに基づいて処理を行う回路を用いることができる。なお、図16の例では、回路部81a1〜81a4の数は、ニューロン数nが4であるものとして4つとしているが、扱うニューロン数nに応じて増減できる。

0116

回路部81a1〜81a4のそれぞれは、2〜d体結合の重み値と、4個のニューロンの4ビットの出力値x1,x2,x3,x4に基づき、前述したローカルフィールド値hi(1≦i≦4)を算出する。そして、回路部81a1〜81a4のそれぞれは、ローカルフィールド値hiにノイズ値を加算した値と閾値(たとえば、0)との比較結果に基づき、出力値x1〜x4として0または1を出力する。

0117

回路部81a1〜81a4は、ローカルフィールド値hiを算出する際にDeGloriaアルゴリズムに基づいて以下のような処理を行う。
全ニューロンのうち、一度に状態が更新されるニューロンの数を1つとすると、そのニューロンの接続先では、元のローカルフィールド値hiに対して、その更新による変化分を加算または減算すればよい。

0118

まず、回路部81a1〜81a4は、2〜d体結合の重み値と、出力値x1〜x4と、信号udnに基づき、2〜d体結合のそれぞれによって発生するエネルギーを示すd−1個のローカルフィールド値の変化分を算出する。信号udnは、出力値が更新されたニューロンのニューロンIDを示す。さらに、回路部81a1〜81a4は、d−1個のローカルフィールド値の変化分を加算した加算値を求める。そして、回路部81a1〜81a4は、その加算値を何れかのニューロンの更新後の出力値である信号udsに基づき正負反転させた値を、更新前のその値の積算値に加算して積算値を更新する。この更新された積算値が、ローカルフィールド値hiに相当する。また、回路部81a1〜81a4は、比較結果(出力値)を保持する機能と、保持された前回の出力値と、今回の出力値とが異なる場合に、1となる信号ud1〜ud4を出力する機能を有する。

0119

更新制御回路81bは、制御装置3の制御のもと動作する。更新制御回路81bは、回路部81a1〜81a4から、出力値x1〜x4と、信号ud1〜ud4を受け、出力値が更新されたニューロンのニューロンIDを示す信号udnと、更新後の出力値である信号udsと、出力値x1〜x4とを出力する。

0120

図17は、回路部の一例を示す図である。
図17では、d=3としたときの回路部81a1の一例の回路図が示されている。回路部81a2〜81a4についても同様の回路図となる。

0121

回路部81a1は、演算回路82,83、加算回路84、選択回路85、乗算回路86、加算回路87、レジスタ88、加算回路89、比較回路90、XOR回路91、レジスタ92を有している。

0122

演算回路82は、ニューロンID=1のニューロンを含む2つのニューロンによる2体結合によって発生するローカルフィールド値の変化分Δh12を算出する。
たとえば、ニューロンID=3のニューロンの出力値が更新されたときのΔh12は、以下の式(10)のように表せる。

0123

0124

式(10)のように、2体結合によって発生するローカルフィールド値の変化分Δh12を求める際には、出力値x1〜x4が不要である。
演算回路83は、ニューロンID=1のニューロンを含む3つのニューロンによる3体結合によって発生するローカルフィールド値の変化分Δh13を算出する。

0125

たとえば、ニューロンID=3のニューロンの出力値が更新されたときのΔh13は、以下の式(11)のように表せる。

0126

0127

式(11)のように、3体結合によって発生するローカルフィールド値の変化分Δh13を求める際には、出力値x1〜x4のうち何れか2つが用いられる。
演算回路82,83は、たとえば、以下のような回路で実現できる。

0128

図18は、2体結合によって発生するローカルフィールド値の変化分を算出する演算回路の一例を示す図である。
演算回路82は、レジスタ82a、選択回路82bを有している。

0129

レジスタ82aには、ニューロンID=1のニューロンを含む2つのニューロンによる2体結合の重み値W12,W13,W14が記憶されている。重み値W12〜W14は、前述した制御装置3の処理によってレジスタ82aに書き込まれる。

0130

選択回路82bは、信号udnに基づいて、重み値W12〜W14の1つを選択して、ローカルフィールド値の変化分Δh12として出力する。選択回路82bは、たとえば、ニューロンID=3のニューロンの出力値が更新された旨を示す信号udnを受けると、Δh12は式(10)のように表せるため、選択回路82bは、重み値W13を選択して出力する。また、選択回路82bは、ニューロンID=2のニューロンの出力値が更新された旨を示す信号udnを受けると、重み値W12を選択して出力し、ニューロンID=4のニューロンの出力値が更新された旨を示す信号udnを受けると、重み値W14を選択して出力する。

0131

図19は、3体結合によって発生するローカルフィールド値の変化分を算出する演算回路の一例を示す図である。
演算回路83は、レジスタ83a、選択回路83b,83c、2出力値選択回路83d、乗算回路83e,83f、加算回路83gを有している。

0132

d=3、n=4であるときの、ニューロンID=1のニューロンを含む3つのニューロンによる3体結合の重み値の数は、式(7)から、3つである。
レジスタ83aには、ニューロンID=1のニューロンを含む3つのニューロンによる3体結合の重み値W123,W124,W134が記憶されている。重み値W123〜W134は、前述した制御装置3の処理によってレジスタ83aに書き込まれる。

0133

選択回路83bは、信号udnに基づいて、重み値W123〜W134の1つを選択して出力する。選択回路83cは、信号udnに基づいて、重み値W123〜W134の1つを選択して出力する。

0134

選択回路83b,83cが、たとえば、ニューロンID=3のニューロンの出力値が更新された旨を示す信号udnを受けると、Δh13は式(11)のように表せる。そのため、選択回路83bは重み値W123を選択して出力し、選択回路83cは重み値W134を選択して出力する。また、選択回路83b,83cは、ニューロンID=2のニューロンの出力値が更新された旨を示す信号udnを受けると、選択回路83bは重み値W123を選択して出力し、選択回路83cは重み値W124を選択して出力する。また、選択回路83b,83cは、ニューロンID=4のニューロンの出力値が更新された旨を示す信号udnを受けると、選択回路83bは重み値W124を選択して出力し、選択回路83cは重み値W134を選択して出力する。

0135

2出力値選択回路83dは、信号udnに基づいて、出力値x1〜x4のうち2つを選択して出力する。
2出力値選択回路83dが、たとえば、ニューロンID=3のニューロンの出力値が更新された旨を示す信号udnを受けると、Δh13は式(11)のように表せるため、2出力値選択回路83dは、出力値x2,x4を選択して出力する。また、2出力値選択回路83dが、たとえば、ニューロンID=2のニューロンの出力値が更新された旨を示す信号udnを受けると、2出力値選択回路83dは、出力値x3,x4を選択して出力する。また、2出力値選択回路83dが、たとえば、ニューロンID=4のニューロンの出力値が更新された旨を示す信号udnを受けると、2出力値選択回路83dは、出力値x2,x3を選択して出力する。

0136

このような2出力値選択回路83dは、たとえば、以下のような回路で実現できる。
図20は、2出力値選択回路の一例を示す図である。
2出力値選択回路83dは、レジスタ100,101,102、選択回路103、レジスタ104を有している。

0137

レジスタ100は、出力値x2,x3を保持し、2ビットの信号として出力する。レジスタ101は、出力値x2,x4を保持し、2ビットの信号として出力する。レジスタ102は、出力値x3,x4を保持し、2ビットの信号として出力する。

0138

選択回路103は、信号udnに基づき、レジスタ100〜102の何れかから出力される信号を選択し、出力する。
たとえば、選択回路103は、ニューロンID=4のニューロンの出力値が更新された旨を示す信号udnを受けると、レジスタ100から出力される2ビットの信号を選択して出力する。また、選択回路103は、ニューロンID=3のニューロンの出力値が更新された旨を示す信号udnを受けると、レジスタ101から出力される2ビットの信号を選択して出力する。また、選択回路103は、ニューロンID=2のニューロンの出力値が更新された旨を示す信号udnを受けると、レジスタ102から出力される2ビットの信号を選択して出力する。

0139

レジスタ104は、選択回路103から出力される2ビットの信号を保持し、各ビットの信号を並列に出力する。
なお、ニューロンID=1のニューロンに相当する回路部81a1内に含まれる演算回路83では、出力値x1は用いられないため、図20では出力値x1については図示が省略されている。

0140

図19に示した乗算回路83eは、選択回路83bから出力される重み値と、2出力値選択回路83dから出力される出力値x2〜x4の何れか1つとの積を出力する。たとえば、選択回路83bと、2出力値選択回路83dが、ニューロンID=3のニューロンの出力値が更新された旨を示す信号udnを受けると、Δh13は式(11)のように表せるため、乗算回路83eは、重み値W123と出力値x2との積を出力する。

0141

乗算回路83fは、選択回路83cから出力される重み値と、2出力値選択回路83dから出力される出力値x2〜x4の何れか1つとの積を出力する。たとえば、選択回路83cと、2出力値選択回路83dが、ニューロンID=3のニューロンの出力値が更新された旨を示す信号udnを受けると、Δh13は式(11)のように表せるため、乗算回路83eは、重み値W134と出力値x4との積を出力する。

0142

加算回路83gは、乗算回路83e,83fの出力値を加算し、Δh13として出力する。
以下、図17の説明に戻る。

0143

演算回路82,83で算出された、Δh12とΔh13は、加算回路84で足し合わされ、ローカルフィールド値h1の変化分Δhiとして出力される。
選択回路85は、出力値が更新されたニューロンの更新後の出力値である信号udsに基づき、1または−1を選択して出力する。更新後の出力値が0のときには、選択回路85は、−1を選択して出力し、更新後の出力値が1のときには、選択回路85は、1を選択して出力する。

0144

乗算回路86は、加算回路84から出力される変化分Δh1と、選択回路85から出力される値との積を出力する。
加算回路87は、乗算回路86から出力される値と、レジスタ88に記憶されている値(ローカルフィールド値h1)とを加算して出力する。

0145

レジスタ88は、図示しないクロック信号に同期して、加算回路87から出力される値を取り込み、ローカルフィールド値h1を更新する。レジスタ88は、たとえば、フリップフロップである。なお、レジスタ88の初期値はバイアス値b1である。

0146

加算回路89は、レジスタ88から出力される値に、ノイズ発生回路17から出力されるノイズ値を加算して出力する。
比較回路90は、たとえば、加算回路89から出力される値が、閾値以上のときには0を出力し、閾値より小さいときには1を出力する。

0147

なお、比較回路90は、ランダム信号生成回路10から出力される選択信号によって、有効または無効になる。イジング装置81でアニール動作が行われる際、出力値の更新を許容するニューロンを1つにするために、このような比較回路90が用いられる。たとえば、ランダム信号生成回路10から出力される信号によって、回路部81a1〜81a4に含まれる複数の比較回路(回路部81a1では比較回路90)のうち、ランダムに1つが選択されて有効となり、他は無効になる。

0148

XOR回路91は、比較回路90から出力される値と、レジスタ92に記憶されている値とが、一致しているときは信号ud1として0を出力し、異なるときは信号ud1として1を出力する排他的論理和回路(Exclusive−OR回路)である。

0149

レジスタ92は、信号ud1が1となると、比較回路90から出力される値を取り込む。これにより、回路部81a1の出力値x1が更新される。
以上のような比較回路90、XOR回路91、レジスタ92によって、第1の実施の形態のイジング装置2の比較回路13、更新回路14と、保持回路15と同様の機能が実現されている。

0150

(第2の実施の形態の情報処理装置の動作例)
以下、制御装置3によって制御される図16の情報処理装置80の動作の一例を、フローチャートを用いて説明する。

0151

第2の実施の形態の情報処理装置80も、第1の実施の形態の情報処理装置1と同様に、図7に示したような各処理を行う。ただ、図7のステップS3のシミュレーテッド・アニーリングが、情報処理装置1で行われる図8に示したような処理とは異なっている。以下、第2の実施の形態の情報処理装置80で行われるシミュレーテッド・アニーリングの例を説明する。

0152

図21は、第2の実施の形態の情報処理装置におけるシミュレーテッド・アニーリングの一例の流れを示すフローチャートである。なお、以下ではn=4、d=3、すなわち、ニューロン数が4で、且つ、2体結合と3体結合を扱うものとして説明を行う。

0153

まず、制御装置3の制御のもと、ランダム信号生成回路10は、出力値の更新を許容するニューロン(ニューロンID=iのニューロン)をランダムに選択するための選択信号を出力する(ステップS30)。たとえば、選択信号が、ニューロンID=1のニューロンを選択することを示すときには、回路部81a1の選択回路90が有効になり、回路部81a1の出力値x1の更新が許容される。このとき、回路部81a2〜81a4の出力値x2〜x4は更新されない。

0154

回路部81a1〜81a4は、2体結合によるローカルフィールド値hiの変化分Δhi2と、3体結合によるローカルフィールド値hiの変化分Δhi3とを算出する(ステップS31)。たとえば、回路部81a1では、演算回路82がΔh12を算出し、演算回路83がΔh13を算出する。

0155

次に、回路部81a1〜81a4は、Δhi2とΔhi3とを加算することで、Δhiを算出する(ステップS32)。たとえば、回路部81a1では、加算回路84がΔh12とΔh13とを加算して、Δh1を算出する。

0156

その後、回路部81a1〜81a4は、元のローカルフィールド値hiにΔhiを加えることで、ローカルフィールド値hiを更新する(ステップS33)。たとえば、回路部81a1では、加算回路87が、レジスタ88に記憶されているローカルフィールド値h1にΔh1を加算することで、ローカルフィールド値h1を更新する。

0157

そして、回路部81a1〜81a4のうち、ニューロンID=iのニューロンに対応するものは、ローカルフィールド値hiとノイズ値との加算結果が閾値より小さいとき(ステップS34:YES)、new_xi=1とする(ステップS35)。

0158

ローカルフィールド値hiとノイズ値との加算結果が閾値以上のとき(ステップS34:NO)、回路部81a1〜81a4のうち、出力値の更新が許容されたニューロンに対応するものは、new_xi=0とする(ステップS36)。

0159

たとえば、選択信号が、ニューロンID=1のニューロンを選択することを示すときには、回路部81a1の選択回路90は、ローカルフィールド値h1とノイズ値との加算結果が、閾値より小さいとき、new_x1として1を出力する。また、選択回路90は、ローカルフィールド値h1とノイズ値との加算結果が閾値以上のとき、new_x1として0を出力する。

0160

ステップS35,S36の処理後、new_xiがニューロンID=iのニューロンの元の出力値xiと異なるとき(ステップS37:NO)、回路部81a1〜81a4のうちi番目の回路部の出力値xiを更新した更新出力値が出力される(ステップS38)。

0161

たとえば、選択信号が、ニューロンID=1のニューロンを選択することを示すときには、回路部81a1のXOR回路91は、new_x1がレジスタ92に記憶されている元の出力値x1と異なるときには、信号ud1を1とする。これにより、new_x1がレジスタ92に記憶され、新たな出力値x1として出力される。

0162

その後、ステップS30からの処理が繰り返される。
new_xiが、元の出力値xiと同じとき(ステップS37:YES)、たとえば、制御装置3は、更新制御回路81bを介して出力値x1〜x4を受け、出力値x1〜x4(ニューロン状態)、一定期間変化していないか否かを判定する(ステップS39)。出力値x1〜x4が、一定期間変化していないとき(ステップS39:YES)、制御装置3は、シミュレーテッド・アニーリングを終了する。

0163

出力値x1〜x4が、一定期間内で変化しているとき(ステップS39:NO)、ステップS30からの処理が繰り返される。
更新を許容するニューロンの選択が行われるたびに、ノイズ発生回路17は、制御装置3の制御のもと、ノイズ幅を徐々に小さくしていくことで、シミュレーテッド・アニーリングが行われる。

0164

なお、上記では、n=4、d=3とした場合について説明したが、これらの値に限定されるものではない。たとえば、d(≧4)体結合によって発生するローカルフィールド値の変化分Δh1dを求める際には、演算回路82,83に加えて、Δhidを算出する演算回路が追加される。ニューロン数がn個とすると、Δhidを算出する演算回路では、n個のニューロンの出力値x1〜xnのうちd−1個が用いられる。

0165

以上のような第2の実施の形態の情報処理装置80及びイジング装置81では、2〜d個のニューロンによる2体結合〜d体結合のそれぞれにより発生するローカルフィールド値の変化分が算出される。そして、その変化分の加算結果に基づく値で、ローカルフィールド値hiが更新され、更新されたローカルフィールド値hiとノイズ値との加算値と閾値との比較結果に基づき各ニューロンの出力値が決定される。

0166

これにより、補助的なビットなどを設けずとも、高次のエネルギー関数の最適化問題を、イジング装置81にマッピングできる。このため、補助的なビットを設けることで生じる可能性のあった、シミュレーテッド・アニーリングでの最適解への収束速度の悪化や、使用できるビット数の減少を招くことを抑制できる。

0167

また、高次のエネルギー関数を用いた最適化問題を、複数の2次のエネルギー関数を用いた最適化問題に変換するなどの処理が不要であるため、最適化問題を容易にイジング装置81にマッピングできる。

0168

さらに、第2の実施の形態のイジング装置81では、ローカルフィールド値hiの変化分Δhiを算出して、Δhiでhiを更新するため、第1の実施の形態のイジング装置2よりも、加算回路や乗算回路の数を少なくすることができる。

0169

以上、実施の形態に基づき、本発明の情報処理装置、イジング装置及び情報処理装置の制御方法の一観点について説明してきたが、これらは一例にすぎず、上記の記載に限定されるものではない。

0170

1情報処理装置
2 イジング装置
3制御装置
4メモリ
10ランダム信号生成回路
11a1〜11a(d−1)演算回路
12加算回路
13比較回路
14更新回路
15保持回路
16バイアス値保持回路
17ノイズ発生回路
20〜23ニューロン
clkクロック信号
hi2〜hidローカルフィールド値
i ニューロンID
x1〜xn出力値
Wij,Wik,Wjk,Wijk,Wjjkl 重み値

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 富士通株式会社の「 最適化装置及び最適化装置の制御方法」が 公開されました。( 2020/04/23)

    【課題】k−hot制約をもつ最適化問題の計算時間を短縮する。【解決手段】k個(k>1)のΔE算出回路(ΔE算出回路11i,11Nなど)のそれぞれは、イジングモデルのN個のビットのうち、値=1のk個のビ... 詳細

  • 富士通株式会社の「 最適化装置及び最適化装置の制御方法」が 公開されました。( 2020/04/23)

    【課題】1−hot制約をもつ最適化問題の計算時間を短縮する。【解決手段】複数の算出回路(ΔE算出回路11p1〜11pnを含む)は、イジングモデルのビットをグループ分けした各グループの複数ビットのうち、... 詳細

  • 株式会社デンソーの「 人工ニューラルネットワーク回路」が 公開されました。( 2020/04/09)

    【課題】環境温度が変化した場合の性能の劣化を抑制することが可能な人工NN回路を提供すること【解決手段】人工NN回路は、階層化されたニューロン間で信号の伝達を行うクロスバー回路44を有する。クロスバー回... 詳細

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ