図面 (/)

技術 イジング装置及びイジング装置の制御方法

出願人 富士通株式会社
発明者 松原聡田村泰孝
出願日 2016年6月6日 (4年0ヶ月経過) 出願番号 2016-112551
公開日 2017年12月14日 (2年6ヶ月経過) 公開番号 2017-219952
状態 特許登録済
技術分野 学習型計算機
主要キーワード 実効温度 イジング型 ローカルフィールド ノイズ発生回路 イジングモデル 有無検出回路 ノイマン型コンピュータ デコード出力信号
関連する未来課題
重要な関連分野

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

図面 (9)

課題

最適解収束性を改善する。

解決手段

ニューロン回路5a1〜5anはそれぞれ、自身以外の複数の他のニューロン回路との接続の有無を示す複数の重み値と、複数の他のニューロン回路の複数の出力信号との積の総和に基づく第1の値を算出し、第1の値にノイズ値加算した第2の値と閾値との比較結果に基づき、0または1を出力する。調停回路10は、複数の重み値に基づき、ニューロン回路5a1〜5anのうち、互いに接続されている複数の第1のニューロン回路の複数の第1の出力信号が同時に変化するとき、複数の第1のニューロン回路のうち1つ以外の第1の出力信号の更新禁止し、互いに接続されていない複数の第2のニューロン回路の複数の第2の出力信号が同時に変化するとき、複数の第2の出力信号の更新を許可する。

概要

背景

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

従来、イジング装置をハードウェアで実現する手法の1つとして、たとえば、ニューロンの機能を模擬するニューロン回路を複数並列動作させる手法が提案されている。

概要

最適解収束性を改善する。ニューロン回路5a1〜5anはそれぞれ、自身以外の複数の他のニューロン回路との接続の有無を示す複数の重み値と、複数の他のニューロン回路の複数の出力信号との積の総和に基づく第1の値を算出し、第1の値にノイズ値加算した第2の値と閾値との比較結果に基づき、0または1を出力する。調停回路10は、複数の重み値に基づき、ニューロン回路5a1〜5anのうち、互いに接続されている複数の第1のニューロン回路の複数の第1の出力信号が同時に変化するとき、複数の第1のニューロン回路のうち1つ以外の第1の出力信号の更新禁止し、互いに接続されていない複数の第2のニューロン回路の複数の第2の出力信号が同時に変化するとき、複数の第2の出力信号の更新を許可する。

目的

本発明は、最適解への収束性が改善できるイジング装置及びイジング装置の制御方法を提供する

効果

実績

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

この技術が所属する分野

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

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

請求項1

それぞれが、自身以外の複数の他のニューロン回路との接続の有無を示す複数の重み値と、前記複数の他のニューロン回路の複数の出力信号との積の総和に基づく第1の値を算出し、前記第1の値にノイズ値加算した第2の値と閾値との比較結果に基づき、0または1を出力する複数のニューロン回路と、前記複数の重み値に基づき、前記複数のニューロン回路のうち、互いに接続されている複数の第1のニューロン回路の複数の第1の出力信号が同時に変化するとき、前記複数の第1のニューロン回路のうち1つ以外の第1の出力信号の更新禁止し、互いに接続されていない複数の第2のニューロン回路の複数の第2の出力信号が同時に変化するとき、前記複数の第2の出力信号の更新を許可する調停回路と、を有することを特徴とするイジング装置。

請求項2

前記調停回路は、前記複数の第1のニューロン回路のうちの1つを識別する第1の識別情報を生成し、前記複数のニューロン回路のうち、前記第1の識別情報に対応する第3のニューロン回路は、前記複数の出力信号に基づく更新を行う、ことを特徴とする請求項1に記載のイジング装置。

請求項3

前記複数のニューロン回路のそれぞれを識別する識別情報群を記憶しているメモリを有し、前記調停回路は、前記メモリから前記識別情報群を読み込み、前記複数の第1のニューロン回路のそれぞれを識別する第1の識別情報群を、前記識別情報群から抽出し、前記第1の識別情報群から、ランダムに前記第1の識別情報を選択、または、前記第1の識別情報群から、値が最大または最小となる前記第1の識別情報を選択する、ことを特徴とする請求項2に記載のイジング装置。

請求項4

前記調停回路は、前記複数の重み値に基づき、前記第3のニューロン回路に接続されている第4のニューロン回路を識別する第2の識別情報を、前記識別情報群から抽出し、前記第2の識別情報を、前記第1の識別情報群から除去する、ことを特徴とする請求項3に記載のイジング装置。

請求項5

それぞれが、自身以外の複数の他のニューロン回路との接続の有無を示す複数の重み値と、前記複数の他のニューロン回路の複数の出力信号との積の総和に基づく第1の値を算出し、前記第1の値にノイズ値を加算した第2の値と閾値との比較結果に基づき、0または1を出力する複数のニューロン回路と、前記複数の重み値に基づき、前記複数のニューロン回路のうち、互いに接続されている複数の第1のニューロン回路の複数の第1の出力信号が同時に変化するとき、前記複数の第1のニューロン回路のうち1つ以外の第1の出力信号の更新を禁止し、互いに接続されていない複数の第2のニューロン回路の複数の第2の出力信号が同時に変化するとき、前記複数の第2の出力信号の更新を許可する調停回路と、を有するイジング装置に対して、制御装置が、前記複数の重み値を設定し、前記制御装置が、複数のニューロン回路のうち、有効にする前記複数の第1のニューロン回路または前記複数の第2のニューロン回路を、ランダム信号生成回路にランダムに選択させ、前記制御装置が、ノイズ発生回路が出力する前記ノイズ値の振幅を制御する、ことを特徴とするイジング装置の制御方法

技術分野

0001

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

背景技術

0002

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

0003

従来、イジング装置をハードウェアで実現する手法の1つとして、たとえば、ニューロンの機能を模擬するニューロン回路を複数並列動作させる手法が提案されている。

0004

特開平3−100857号公報

先行技術

0005

S. Geman and D. Geman, "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images,"IEEE Trans. on Pattern Analysis and Machine Intelligence, PAMI-6, pp.721-741, 1984

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

0006

ところで、ボルツマンマシンにおいて、一度に1つのニューロン回路の状態(出力値)が更新される場合には、最適解収束することが証明されている(たとえば、非特許文献1参照)。しかし、複数のニューロン回路の状態が同時に更新される場合には、このような収束性が証明されていない。このため、複数のニューロン回路が並列動作する場合、計算処理高速化が図れることが期待できるものの、最適解への収束性が悪化する可能性があるという問題がある。

0007

1つの側面では、本発明は、最適解への収束性が改善できるイジング装置及びイジング装置の制御方法を提供することを目的とする。

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

0008

1つの態様では、それぞれが、自身以外の複数の他のニューロン回路との接続の有無を示す複数の重み値と、前記複数の他のニューロン回路の複数の出力信号との積の総和に基づく第1の値を算出し、前記第1の値にノイズ値加算した第2の値と閾値との比較結果に基づき、0または1を出力する複数のニューロン回路と、前記複数の重み値に基づき、前記複数のニューロン回路のうち、互いに接続されている複数の第1のニューロン回路の複数の第1の出力信号が同時に変化するとき、前記複数の第1のニューロン回路のうち1つ以外の第1の出力信号の更新を禁止し、互いに接続されていない複数の第2のニューロン回路の複数の第2の出力信号が同時に変化するとき、前記複数の第2の出力信号の更新を許可する調停回路と、を有するイジング装置が提供される。

0009

また、1つの態様では、それぞれが、自身以外の複数の他のニューロン回路との接続の有無を示す複数の重み値と、前記複数の他のニューロン回路の複数の出力信号との積の総和に基づく第1の値を算出し、前記第1の値にノイズ値を加算した第2の値と閾値との比較結果に基づき、0または1を出力する複数のニューロン回路と、前記複数の重み値に基づき、前記複数のニューロン回路のうち、互いに接続されている複数の第1のニューロン回路の複数の第1の出力信号が同時に変化するとき、前記複数の第1のニューロン回路のうち1つ以外の第1の出力信号の更新を禁止し、互いに接続されていない複数の第2のニューロン回路の複数の第2の出力信号が同時に変化するとき、前記複数の第2の出力信号の更新を許可する調停回路と、を有するイジング装置に対して、制御装置が、前記複数の重み値を設定し、前記制御装置が、複数のニューロン回路のうち、有効にする前記複数の第1のニューロン回路または前記複数の第2のニューロン回路を、ランダム信号生成回路ランダムに選択させ、前記制御装置が、ノイズ発生回路が出力する前記ノイズ値の振幅を制御する、イジング装置の制御方法が提供される。

発明の効果

0010

1つの側面では、最適解への収束性を改善することが可能となる。

図面の簡単な説明

0011

本実施の形態のイジング装置の一例を示す図である。
ニューロン回路の一例を示す図である。
状態xiが1となる確率Pi(hi)の一例を示す図である。
ランダム信号生成回路の一例を示す図である。
調停回路の一例を示す図である。
イジング装置で実行される制御処理の一例を示すフローチャートである。
シミュレーテッド・アニーリングの様子を示す図である。
調停回路で実行される調停更新処理の一例を示すフローチャートである。

実施例

0012

以下、発明を実施するための形態を、図面を参照しつつ説明する。
図1は、本実施の形態のイジング装置の一例を示す図である。
イジング装置1は、レジスタ部2a、ノイズ発生回路3、ランダム信号生成回路4、複数(n個)のニューロン回路5a1,…,5ak,…,5an、制御装置6、調停回路10を有している。イジング装置1は、たとえば、1つの半導体集積回路チップ)で実現される。

0013

レジスタ部2aは、レジスタ2b1,2b2,…,2bnを含んでいる。レジスタ2b1,2b2,…,2bnは、ニューロン回路5a1〜5anのうちの任意の2つの間の接続の有無を示す複数の重み値を格納している。たとえば、レジスタ2b1には、1番目のニューロン回路5a1とその他のニューロン回路との間の接続の有無を示す重み値W12,W13,…,W1nが格納されている。レジスタ2bkには、k番目のニューロン回路5akとその他のニューロン回路との間の接続の有無を示す重み値Wk1,Wk2,…,Wknが格納されている。レジスタ2bnには、n番目のニューロン回路5anとその他のニューロン回路との間の接続の有無を示す重み値Wn1,Wn2,…,Wnnが格納されている。

0014

また、図1には、重み値Wij(1≦i≦n,1≦j≦n)の様子の一例がマトリクス状に示されている。この図では、縦横のそれぞれにニューロン回路5a1〜5anの番号(1番目,2番目,3番目,…,k番目,…,n番目)がそれぞれ付されている。なお、図1の例では、重み値Wiiは、0であり、重み値Wjiは重み値Wijと等しいものとしている。

0015

重み値Wijは、ニューロン回路5a1〜5anのうち、i番目とj番目のニューロン回路間の接続の有無を示す重み値である。また、図1において、相互接続している2つのニューロン回路に対応付けられた重み値(Wij≠0)には、斜線が施されており、相互接続していない2つのニューロン回路に対応付けられた重み値(Wij=0)には、斜線が施されていない。

0016

たとえば、図1の例では、1番目のニューロン回路5a1と、2番目のニューロン回路5a2とに対応付けられた重み値W12は0ではないので、ニューロン回路5a1,5a2は相互接続していることが分かる。一方、図1の例では、1番目のニューロン回路5a1と、k番目のニューロン回路5akとに対応付けられた重み値W1kは0であるので、ニューロン回路5a1,5akは相互接続していないことが分かる。

0017

上記のような重み値は、計算対象の問題に応じて適宜設定され、レジスタ2b1〜2bnに格納される。なお、重み値Wiiは0であるので、図1の例ではレジスタ2b1〜2bnに格納されていない。上記のような重み値は、レジスタ2b1〜2bnに格納される代わりに、フラッシュメモリなどの半導体記憶装置や、RAM(Random Access Memory)などのメモリに格納されてもよい。

0018

ノイズ発生回路3は、制御装置6による制御のもと、ニューロン回路5a1〜5anのそれぞれに対してノイズ値を出力する。ノイズ値の例については後述する。
ランダム信号生成回路4は、制御装置6による制御のもと、ニューロン回路5a1〜5anのうち、有効にする複数のニューロン回路をランダムに選択するための選択信号を出力する。

0019

ランダム信号生成回路4としては、LFSR(Linear Feedback Shift Registers)などを用いることができる。なお、ランダム信号生成回路4の一例については、後述する(図4参照)。

0020

ニューロン回路5a1〜5anのそれぞれは、自身以外の複数のニューロン回路との接続の有無を示す複数の重み値と、複数のニューロン回路のそれぞれの出力信号との積の総和に基づく値(以下、ローカルフィールド値という)を算出する。

0021

そして、ニューロン回路5a1〜5anのそれぞれは、ローカルフィールド値に、ノイズ発生回路3から供給されるノイズ値を加算した値と、閾値(たとえば、0)との比較結果に基づき、0または1を出力する。

0022

ニューロン回路5a1〜5anの回路図の一例については後述する(図2参照)。
制御装置6は、ノイズ発生回路3やランダム信号生成回路4を制御する。たとえば、制御装置6は、シミュレーテッド・アニーリングを実現するために、ノイズ発生回路3に含まれる増幅回路(図示せず)を制御して、ノイズ値の振幅を徐々に小さくさせる。また、制御装置6は、バス(図示せず)を介してレジスタ部2aに接続されており、レジスタ部2aのレジスタ2b1〜2bnに重み値をそれぞれ書き込む。

0023

制御装置6は、たとえば、プロセッサで実現できる。プロセッサは、たとえば、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以上の要素の組み合わせであってもよい。また、制御装置6は、PC(パーソナルコンピュータ)であってもよい。

0024

調停回路10は、上記の複数の重み値に基づき、ニューロン回路5a1〜5anのうち、相互接続されている複数のニューロン回路の複数の出力信号(状態)が同時に変化するとき、そのうち1つ以外の状態の更新を禁止する。

0025

これにより、相互接続されている複数のニューロン回路の状態が同時に更新されることがなくなり、最適解への収束性を改善できる。
なお、前述のように、重み値が0か0ではないかにより、相互接続されている複数のニューロン回路と、相互接続されていない複数のニューロン回路が特定される。

0026

また、調停回路10は、上記の複数の重み値に基づき、ニューロン回路5a1〜5anのうち、相互接続されていない複数のニューロン回路の状態が同時に変化するとき、その状態の更新を許可する。

0027

これにより、収束性に影響を与えない相互接続されていない複数のニューロン回路の状態を同時に更新することができるため、計算時間を短縮できる。
なお、調停回路10の一例については後述する(図5参照)。

0028

(ニューロン回路の一例)
図2は、ニューロン回路の一例を示す図である。
図2では、ニューロン回路5a1〜5anのうち、ニューロン回路5a1,5ak,5anの一例が示されている。

0029

なお、図2では、図1のイジング装置1と同様の要素には同じ符号を付しており、それらの説明については省略する。
ニューロン回路5a1,5ak,5anは、乗算回路5c11,5c1k,5c1nを有している。さらに、ニューロン回路5a1,5ak,5anは、加算回路部5d1,5dk,5dn、加算回路5e1,5ek,5en、比較回路5f1,5fk,5fnを有している。

0030

乗算回路5c11〜5c1nは、レジスタ2b1に格納されている重み値と、調停回路10から出力されるニューロン回路5a1〜5anの状態x1〜xn(0または1)との積を出力する。乗算回路5ck1〜5cknは、レジスタ2bkに格納されている重み値と、調停回路10から出力されるニューロン回路5a1〜5anの状態x1〜xnとの積を出力する。乗算回路5cn1〜5cnnは、レジスタ2bnに格納されている重み値と、調停回路10から出力されるニューロン回路5a1〜5anの状態x1〜xnとの積を出力する。

0031

加算回路部5d1は、乗算回路5c11〜5c1nから出力される値をそれぞれ加算して出力する。加算回路部5dkは、乗算回路5ck1〜5cknから出力される値をそれぞれ加算して出力する。加算回路部5dnは、乗算回路5cn1〜5cnnから出力される値をそれぞれ加算して出力する。

0032

加算回路5e1は、加算回路部5d1から出力される値(ローカルフィールド値)に、ノイズ発生回路3から出力されるノイズ値を加算して出力する。加算回路5ekは、加算回路部5dkから出力される値に、ノイズ発生回路3から出力されるノイズ値を加算して出力する。加算回路5enは、加算回路部5dnから出力される値に、ノイズ発生回路3から出力されるノイズ値を加算して出力する。

0033

比較回路5f1は、ランダム信号生成回路4から供給される選択信号により、無効(または有効)になる。比較回路5f1は、加算回路5e1から出力される値が、閾値(たとえば、0)よりも大きいときにはニューロン回路5a1の状態x1として1を、閾値以下のときにはニューロン回路5a1の状態x1として0を出力する。比較回路5fkは、ランダム信号生成回路4からの選択信号により、無効(または有効)になる。比較回路5fkは、加算回路5ekから出力される値が、閾値よりも大きいときにはニューロン回路5akの状態xkとして1を、閾値以下のときにはニューロン回路5akの状態xkとして0を出力する。比較回路5fnは、ランダム信号生成回路4からの選択信号により、無効(または有効)になる。比較回路5fnは、加算回路5enから出力される値が、閾値よりも大きいときにはニューロン回路5anの状態xnとして1を、閾値以下のときにはニューロン回路5anの状態xnとして0を出力する。

0034

なお、ニューロン回路5a1〜5anのうち、ニューロン回路5a1,5ak,5an以外についても、ニューロン回路5a1,5ak,5anと同様の回路となっている。
以上のような、ニューロン回路5a1〜5anは、イジング型のエネルギー関数演算をハードウェアで実現するものである。なお、イジング型のエネルギー関数E(x)は、たとえば、以下の式(1)で定義される。

0035

0036

右辺の1項目は、全ニューロン回路から選択可能な2つのニューロン回路の全組み合わせについて、漏れ重複なく、2つのニューロン回路の状態と重み値との積を積算したものである。なお、既述の通り、Wij=Wji、Wii=0である。

0037

右辺の2項目は、全ニューロン回路のそれぞれのバイアス値と状態との積を積算したものである。biは、i番目のニューロン回路のバイアス値を示している。
上記のようなエネルギー関数E(x)をハードウェアで表現するため、図2に示したニューロン回路5a1〜5anのそれぞれは、ローカルフィールド値h1〜hnを演算する。たとえば、i番目のニューロン回路におけるローカルフィールド値hiは以下の式(2)で表される。

0038

0039

右辺の1項目は、i番目のニューロン回路と、複数の他のニューロン回路のそれぞれとの間の接続の有無を示す複数の重み値と、複数の他のニューロン回路のそれぞれの状態との積を積算したものである。

0040

このようなローカルフィールド値hiは、i=1のときは、加算回路部5d1から出力される値に相当する。なお、図2の例では、バイアス値は0としているが、加算回路部5d1から出力される値にバイアス値を加える加算回路を設けるようにしてもよい。なお、バイアス値は、問題に応じて制御装置6から与えられる。

0041

図2に示したようなニューロン回路5a1〜5anでは、シミュレーテッド・アニーリングを行うために、ローカルフィールド値h1〜hnにノイズ値を加えた値に対して、比較回路5f1〜5fnで閾値との比較が行われる。

0042

たとえば、比較回路5f1〜5fnの出力値(ニューロン回路5a1〜5anの状態x1〜xn)が1となる確率が、シグモイド関数に従うようにノイズ値が加えられる。たとえば、i番目のニューロン回路の状態xiが1となる確率Pi(hi)が、以下の式(3)の関係になるように、ノイズ値が加えられる。

0043

0044

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

0045

0046

図3は、状態xiが1となる確率Pi(hi)の一例を示す図である。
横軸は、ローカルフィールド値hiにノイズ値nsを加算した値を示し、縦軸は、状態xiが1となる確率を示している。

0047

波形30は、ローカルフィールド値hiに、式(4)に示すような確率密度関数p(ns)に従うノイズ値nsが加算されたときに、状態xiが1となる確率Pi(hi)を示す。波形31は、ローカルフィールド値hiにノイズ値nsが加算されないときに、状態xiが1となる確率Pi(hi)を示す。

0048

波形31に示すように、ノイズ値nsがローカルフィールド値hiに加算されないときは、ローカルフィールド値hiが、閾値Vth以下では、Pi(hi)=0、閾値Vthを超えると、Pi(hi)=1となる。

0049

これに対して、ノイズ値nsがローカルフィールド値hiに加算されるときは、波形30に示すように、シグモイド関数に従って確率Pi(hi)が変化する。
次に、ランダム信号生成回路4の一例について、図4を用いて説明する。

0050

図4は、ランダム信号生成回路の一例を示す図である。
ランダム信号生成回路4は、たとえば、7次の原始多項式(X7+X6+1)に基づく7ビットのランダム信号を発生させるLFSRである。ランダム信号生成回路4は、レジスタ4a〜4g(フリップフロップ)と、XOR回路4hと、デコード回路4iとを有している。

0051

レジスタ4a〜4gは、直列に接続されている。また、レジスタ4a〜4gには、それぞれ初期値を付与するための信号線(“seed”)と、初期値を設定するための信号線(“reset”)とが接続されている。また、レジスタ4a〜4gは、クロック信号に同期して、動作する。クロック信号は、たとえば、制御装置6から供給される。

0052

XOR回路4hは、レジスタ4fから出力された値と、レジスタ4gから出力された値のXOR演算結果を出力する。XOR回路4hの出力端子は、初段のレジスタ4aの入力端子に接続されている。

0053

デコード回路4iは、レジスタ4a〜4gの出力端子(out0〜out6)から出力される7ビットのランダム信号をデコードして128ビットのデコード信号を出力する。
このようなランダム信号生成回路4では、レジスタ4a〜4gの出力端子(out0〜out6)から、7ビットのランダム信号が出力される。デコード回路4iがランダム信号をデコードすることによって、ニューロン回路5a1〜5an(n=128)の比較回路5f1〜5fnが、有効、または無効となる。たとえば、出力端子enの最下位ビットの値が0のとき、比較回路5f1は無効化される。

0054

なお、ノイズ発生回路3も、LFSRを用いて実現できる。
(調停回路10の一例)
図5は、調停回路の一例を示す図である。

0055

調停回路10は、メモリ11、レジスタ部12、デコード回路13、XOR回路部14、識別情報抽出回路15、ニューロン選択回路16、選択回路17、接続ニューロン検出回路18、加算回路19を有している。また、調停回路10は、識別情報有無検出回路20、AND回路部21を有している。

0056

メモリ11は、ニューロン回路5a1〜5anのそれぞれを識別する識別情報群を記憶している。メモリ11として、たとえば、フラッシュメモリなどの半導体記憶装置、RAMなどを用いることができる。

0057

レジスタ部12は、ニューロン回路5a1〜5anの状態x1〜xnを格納するn個のレジスタを含んでいる。レジスタ部12のn個のレジスタは、後述する識別情報有無検出回路20の出力がH(High)レベルになっている状態で、AND回路部21から供給される信号に同期して、ニューロン選択回路16で選択された状態xiのみを取り込む。

0058

デコード回路13は、ニューロン選択回路16が選択する1つのニューロン回路の識別情報に基づき、デコード出力信号を出力する。
XOR回路部14は、レジスタ部12のn個のレジスタにそれぞれ対応して、n個のXOR回路を含んでいる。たとえば、i番目のXOR回路は、i番目のレジスタの入力値と出力値のXOR演算結果を出力する。これにより、i番目のXOR回路は、i番目のニューロン回路の状態xiの変化を検出する。たとえば、i番目のニューロン回路の状態xiが、i番目のレジスタに格納されている値と異なる値に変化すると、i番目のXOR回路は、1を出力する。一方、i番目のニューロン回路の状態xiが、i番目のレジスタに格納されている値と同じであるときには、i番目のXOR回路は、0を出力する。

0059

このようにして、XOR回路部14は、ニューロン回路5a1〜5anの状態x1〜xnの変化を表す値を出力する。
識別情報抽出回路15は、メモリ11に記憶されている識別情報群を、クロック信号に同期して読み込む。そして、識別情報抽出回路15は、XOR回路部14からの出力結果に基づき、状態が変化したニューロン回路の識別情報を、その識別情報群から抽出する。以下では、状態が変化したニューロン回路が複数あるものとして、メモリ11から読み込んだ識別情報群から、状態が変化した複数のニューロン回路の識別情報群が抽出されるものとする。

0060

ニューロン選択回路16は、識別情報抽出回路15が抽出した識別情報群から、1つのニューロン回路の識別情報を選択する。たとえば、ニューロン選択回路16は、識別情報群から、1つのニューロン回路の識別情報をランダムに選択するか、値が最小(または最大)の識別情報を選択する。

0061

選択回路17は、レジスタ部2aに格納されている複数の重み値から、ニューロン選択回路16が選択した識別情報に対応したニューロン回路と、他のニューロン回路との間の接続の有無を示す重み値を選択する。

0062

接続ニューロン検出回路18は、選択回路17が選択した重み値を参照して、当該重み値が0であるか否かに基づき、ニューロン選択回路16が選択した識別情報に対応したニューロン回路に相互接続されている他のニューロン回路を検出する。そして、接続ニューロン検出回路18は、検出した他のニューロン回路の識別情報を、メモリ11から取得して出力する。

0063

加算回路19は、識別情報抽出回路15から出力される識別情報群から、ニューロン選択回路16が選択したニューロン回路の識別情報と、接続ニューロン検出回路18から出力される識別情報とを除く。

0064

識別情報有無検出回路20は、加算回路19から出力されている識別情報の有無を検出する。たとえば、識別情報有無検出回路20は、識別情報があることを検出するたびに、L(Low)レベルからH(High)レベルになる信号を出力する。

0065

AND回路部21は、レジスタ部12のn個のレジスタにそれぞれ対応して、n個のAND回路を含んでいる。たとえば、i番目のAND回路は、識別情報有無検出回路20の出力(Hレベル)と、デコード回路13から供給されるi番目のニューロン回路の識別情報に基づくデコード出力信号とのAND演算結果をi番目のレジスタに出力する。これにより、i番目のAND回路は、i番目のニューロン回路の状態xiを更新する。

0066

次に、上記のようなイジング装置1で実行される、計算対象の問題を計算する際に行われる制御処理について、図6を用いて説明する。
図6は、イジング装置で実行される制御処理の一例を示すフローチャートである。

0067

[ステップS1]制御装置6は、レジスタ部2aなどを初期化する。
[ステップS2] 制御装置6は、レジスタ部2aの各レジスタ2b1〜2bnに、計算対象の問題に応じた重み値を設定する。

0068

なお、このようにして設定された重み値は調停回路10に供給される。
[ステップS3]制御装置6は、ランダム信号生成回路4に選択信号を出力させ、ランダムに複数のニューロン回路を選択する(有効にする)。

0069

なお、制御装置6は、ニューロン回路の選択を行うたびに、シミュレーテッド・アニーリングを実現するために、ノイズ発生回路3に含まれる増幅回路(図示せず)を制御して、ノイズ値の振幅を徐々に小さくさせる。

0070

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

0071

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

0072

[ステップS4] ステップS4の処理では、調停回路10を用いた、調停/更新処理が行われる。ステップS4の処理については後述する。
[ステップS5]制御装置6は、調停回路10から出力される更新を許容するニューロン回路の識別情報の出力回数が、予め決められた回数cnt1に達したか否か判定する。

0073

更新を許容するニューロン回路の識別情報の出力回数が、回数cnt1に達すると、ステップS6の処理が実行され、回数cnt1に達しなければ、ステップS4からの処理が繰り返される。

0074

[ステップS6]制御装置6は、ステップS3によるニューロン回路の選択回数が、予め決められた回数cnt2に達したか否かを判定する。
ニューロン回路の選択回数が、回数cnt2に達しなければ、ステップS3の処理が再び実行され、回数cnt2に達すると、制御装置6による制御処理が終了する。

0075

次に、図5に示した調停回路10を用いた調停/更新処理について、図8を用いて説明する。
図8は、調停回路で実行される調停/更新処理の一例を示すフローチャートである。

0076

[ステップS4a]識別情報抽出回路15は、クロック信号に同期して、メモリ11から、識別情報群を読み込む。そして、識別情報抽出回路15は、XOR回路部14からの出力結果に基づき、状態が変化した複数のニューロン回路の識別情報を含む識別情報群を、メモリ11から読み込んだ識別情報群から抽出して出力する。

0077

[ステップS4b]ニューロン選択回路16は、識別情報抽出回路15が抽出した識別情報群から、1つのニューロン回路の識別情報を選択する。たとえば、ニューロン選択回路16は、識別情報群から、1つのニューロン回路の識別情報をランダムに選択するか、値が最小(または最大)の識別情報を選択する。

0078

[ステップS4c]加算回路19から出力される識別情報があるときには、識別情報有無検出回路20は、Hレベルの信号を出力する。デコード回路13は、ニューロン選択回路16が選択した1つのニューロン回路の識別情報に基づきデコード出力信号を出力する。AND回路部21は、Hレベルの信号と、デコード出力信号とに基づくAND演算結果の信号を出力する。レジスタ部12のn個のレジスタは、AND回路部21が出力する信号に応じて、ニューロン選択回路16で選択された識別情報に対応する状態xiを更新して、出力する。

0079

[ステップS4d] 接続ニューロン検出回路18は、選択回路17が選択した重み値を参照して、当該重み値が0であるか否かに基づき、ニューロン選択回路16が選択した識別情報に対応したニューロン回路に相互接続されている他のニューロン回路を検出する。そして、接続ニューロン検出回路18は、検出した他のニューロン回路の識別情報を、メモリ11から取得して出力する。

0080

[ステップS4e]加算回路19は、識別情報抽出回路15から出力される識別情報群から、ニューロン選択回路16が選択したニューロン回路の識別情報と、接続ニューロン検出回路18から出力される識別情報とを除く。

0081

[ステップS4f]識別情報有無検出回路20は、加算回路19から出力されている識別情報の有無を(判定)検出する。識別情報があるときは、ステップS4bからの処理が繰り返される。識別情報がないときは、調停/更新処理が終了する。

0082

以上のような動作により、各ニューロン回路5a1〜5anが出力する状態x1〜xnのうち、ニューロン選択回路16で選択された識別情報に対応する状態xiが更新されて、出力される。

0083

これにより、相互接続されている複数のニューロン回路の状態が同時に更新されることがなくなり、最適解への収束性の悪化を防げる。また、収束性に影響を与えない相互接続されていない複数のニューロン回路の状態を同時に更新することができるため、計算時間を短縮できる。言い換えると、イジング装置1は、複数のニューロン回路5a1〜5anを並列動作させても、最適解への収束性に悪影響が及ぶことなく、計算時間を短縮することができるようになる。

0084

最適化問題では、変数の数が103個から106個と、非常に多くなる場合があり、計算時間が極めて長くなってしまう。特に、最適解への収束に近づくにつれて、状態の更新により、全体のエネルギーを下げられるニューロン回路の数が減少してしまうために、全体からランダムに選択して有効なニューロン回路を選択できる確率も減少してしまう。このため、状態が変化しない無駄なニューロン回路の動作が増加して、計算時間が非常に長くなってしまう。実際には、有効な更新頻度は103回の動作に1回以下となってしまう。

0085

そこで、本実施の形態のイジング装置1は、たとえば、1000個のニューロン回路を並列動作させると、状態が変化するニューロン回路を検出できる確率は1000倍向上する。これにより、計算時間の多くを占めていた状態の変化が起きない無駄なニューロン回路の動作の発生確率を1/1000に減らすことができ、計算時間の大幅な短縮が可能となる。

0086

ところで、ニューロン回路は、図2に示したような回路に限定されない。たとえば、DeGloriaアルゴリズムと呼ばれるアルゴリズムに基づく回路を用いることもできる。DeGloriaアルゴリズムに基づく複数のニューロン回路のそれぞれは、複数の他のニューロン回路の状態に他のニューロン回路との接続の有無を示す重み値を掛けた値の総和に基づく値(ローカルフィールド値)を保持する。そして、複数のニューロン回路のそれぞれは、ローカルフィールド値にノイズ値を加算した値と閾値(たとえば、0)との比較結果に基づき、0または1を出力する。さらに、複数のニューロン回路のそれぞれは、他のニューロン回路の状態の変化時に、調停回路10から供給される識別情報で指定されたニューロン回路は、変化したニューロン回路の状態に基づいて、ローカルフィールド値の変化分を求め、その変化分を、上記状態の変化前のローカルフィールド値に対して加算または減算することで、ローカルフィールド値を更新する。調停回路10は、複数のニューロン回路の状態が変化したとき、相互接続されている複数のニューロン回路のうち、1つ以外に対応した識別情報は出力しない。また、調停回路10は、複数のニューロン回路の状態が変化したとき、相互接続されていない複数のニューロン回路の識別情報を出力する。これにより、ニューロン回路として、図2に示したような回路を用いた場合と同様の効果が得られる。

0087

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

0088

1 イジング装置
2aレジスタ部
2b1〜2bn,4a〜4g レジスタ
3ノイズ発生回路
4ランダム信号生成回路
5a1〜5anニューロン回路
6制御装置
10 調停回路

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

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

関連する公募課題

ページトップへ

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

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

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

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

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

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

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

関連性が強い 技術一覧

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

関連性が強い人物一覧

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

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

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

関連する公募課題一覧

astavision 新着記事

サイト情報について

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

主たる情報の出典

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