(57)【要約】【課題】  アニーリングマシンに埋め込むグラフのパラメータ調整の手法として、より効率的な手法を提供する。【解決手段】  複数のスピンユニットを備えたアニーリング計算回路を備え、イジングモデルを用いて解を求める情報処理装置である。この装置では、複数のスピンユニットの其々は、イジングモデルのスピンの値を記憶する第１のメモリセルと、スピンに相互作用を及ぼす隣接スピンとの相互作用係数を記憶する第２のメモリセルと、スピンの外部磁場係数を記憶する第３のメモリセルと、隣接スピンの値、相互作用係数、及び外部磁場係数に基づいて、スピンの次の値を決定する演算を行う演算回路と、を備える。さらに、外部磁場係数を単調増加あるいは単調減少で更新する、外部磁場係数更新回路を備え、アニーリング計算回路は、更新された外部磁場係数に基づいて、演算回路により複数回のアニーリング計算を行う情報処理装置である。【選択図】  図３Ａ
2020009301.tif 000002
【特許請求の範囲】
【請求項１】
複数のスピンユニットを備えたアニーリング計算回路を備え、イジングモデルを用いて解を求める情報処理装置であって、
前記複数のスピンユニットの其々は、
前記イジングモデルのスピンの値を記憶する第１のメモリセルと、
前記スピンに相互作用を及ぼす隣接スピンとの相互作用係数を記憶する第２のメモリセルと、
前記スピンの外部磁場係数を記憶する第３のメモリセルと、
前記隣接スピンの値、前記相互作用係数、及び前記外部磁場係数に基づいて、前記スピンの次の値を決定する演算を行う演算回路と、
を備え、さらに、
前記外部磁場係数を単調増加あるいは単調減少で更新する、外部磁場係数更新回路を備え、
前記アニーリング計算回路は、更新された前記外部磁場係数に基づいて、前記演算回路により複数回のアニーリング計算を行う情報処理装置。
【請求項２】
前記外部磁場係数更新回路は、スピンのインデックスをｉとし、
ｈｉ＝ａ（ｘｉ−λ（ｌ））
の式に基づいて、変数ｌを変更することにより、パラメータλ（ｌ）を変更して外部磁場係数ｈｉを更新する、
請求項１記載の情報処理装置。
【請求項３】
前記外部磁場係数更新回路は、スピンのインデックスをｉとし、
ｈｉ＝ａ（ｋ）（ｘｉ−λ（ｌ））
の式に基づいて、変数ｋと変数ｌを変更することにより、パラメータａ（ｋ）とパラメータλ（ｌ）を変更して外部磁場係数ｈｉを更新する、
請求項１記載の情報処理装置。
【請求項４】
ループ条件格納メモリと、係数格納メモリを備え、
前記ループ条件格納メモリには、前記パラメータａ（ｋ）と前記パラメータλ（ｌ）のデータを格納し、
前記係数格納メモリには、前記係数ｘｉのデータを格納する、
請求項３記載の情報処理装置。
【請求項５】
前記外部磁場係数更新回路は、
浮動小数点演算によりｈｉ＝ａ（ｋ）（ｘｉ−λ（ｌ））の計算を行う外部磁場係数計算回路と、
計算されたｈｉの値域を制限するクリップ回路と、
前記クリップ回路の出力を定数倍する定数倍回路と、
前記定数倍回路の出力を整数型データに変換する型変換回路と、を備える、
請求項３記載の情報処理装置。
【請求項６】
検証誤差計算回路を備え、
前記アニーリング計算回路は、アニーリング計算によりイジングモデルのエネルギー状態が極小値または最小値になった際の前記スピンの値を解として得、
前記検証誤差計算回路は、前記解と検証データとに基づいて検証誤差を計算し、
前記外部磁場係数更新回路が、前記検証誤差の演算後に外部磁場係数を更新した後、前記アニーリング計算回路が、次のアニーリング計算を行なって次の解を得る、
請求項１記載の情報処理装置。
【請求項７】
分類結果格納メモリを備え、
前記分類結果格納メモリは、前記検証データのインデックスν毎に前記スピンのインデックスｉに対応した分類結果Δｍｉ（ν）を格納し、
前記検証誤差計算回路は、前記解と分類結果Δｍｉ（ν）に基づいて計算を行う、
請求項６記載の情報処理装置。
【請求項８】
スピン値検証誤差格納メモリを備え、
前記スピン値検証誤差格納メモリは、前記演算回路による複数回の演算の結果のうち、前記検証誤差が最小の場合の前記検証誤差の値と、前記スピンの値を記憶する、
請求項６記載の情報処理装置。
【請求項９】
前記スピン値検証誤差格納メモリに、前記検証誤差が最小の場合の前記検証誤差の値と、前記スピンの値を記憶した後、
前記アニーリング計算回路は、前記第１のメモリセル、前記第２のメモリセル、および前記第３のメモリセルの内容を更新し、
前記外部磁場係数更新回路で更新された前記外部磁場係数に基づいて、再度、前記演算回路により複数回の演算を行う、
請求項８記載の情報処理装置。
【請求項１０】
前記外部磁場係数の更新の結果、隣接スピンの値に関わらず、自スピンの値が固定されるスピンユニットに対しては、アニーリング計算を行わない、
請求項１記載の情報処理装置。
【請求項１１】
前記外部磁場係数の値を前記相互作用係数の総和よりも大きくできるように、前記第２のメモリセルと前記第３のメモリセルのビット数を設定する、
請求項１記載の情報処理装置。
【請求項１２】
上位装置である情報処理装置と、イジングモデルを用いてアニーリング計算を行い解を求めるアニーリングマシンを用いる情報処理方法であって、
前記情報処理装置において、
弱分類器を生成し、
検証データで弱分類器の分類結果を得、
弱分類器で強分類器を構成する際の弱分類器の選択問題を、前記アニーリングマシンのハードウェアに適合したイジングモデルに変換して前記アニーリングマシンに送り、
前記アニーリングマシンにおいて、
前記イジングモデルのパラメータである、外部磁場係数と相互作用係数をそれぞれメモリセルに格納し、
複数回のアニーリング計算を行なう際には、前記外部磁場係数を単調増加あるいは単調減少で更新してから、其々のアニーリング計算を実行する、
情報処理方法。
【請求項１３】
前記上位装置から前記アニーリングマシンに送られるイジングモデルは、イジングモデルのエッジに対応するＪｉｊと、次の式で表されるパラメータｘｉであり、
【数１】
2020009301.tif 000011
（ただし、ｉは前記弱分類器のインデックス、Ｔは弱分類器に対する訓練データの集合、ｔは訓練データのインデックス、ｃｉ（ｔ）はインデックスｉの弱分類器によるインデックスｔの訓練データの分類結果、ｙ（ｔ）はインデックスｔの訓練データの正しい分類）
前記メモリセルに格納されるパラメータは、前記相互作用係数を表す前記Ｊｉｊと、前記外部磁場係数を表すｈｉ＝ａ（ｘｉ−λ（ｌ））であり、
前記λ（ｌ）の値を変化させることにより、前記外部磁場係数を表すｈｉを計算して更新する、
請求項１２記載の情報処理方法。
【請求項１４】
前記ａ＝ａ（ｋ）であり、前記ａ（ｋ）の値と前記λ（ｌ）の値を独立に変化させることにより、前記外部磁場係数を表すｈｉを更新する、
請求項１３記載の情報処理方法。
【請求項１５】
前記アニーリングマシンのハードウェアに適合したイジングモデルに変換する際に、元のモデルのエッジの一部が欠落している、
請求項１２記載の情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理技術、特に最適解の探索を行うアルゴリズムとしてアニーリングを採用する情報処理装置および情報処理方法に関する。
【背景技術】
【０００２】
機械学習分野で分類問題を解くアプローチとして、個々に学習した単純な弱分類器を組み合わせて、最終的な分類結果を得るアンサンブル学習が知られている。弱分類器は、真の分類と若干の相関のある分類器と定義される。弱分類器と比較して、強分類器とは真の分類とより相関する分類器である。アンサンブル学習には、ブースティングやバギング等の手法が知られている。アンサンブル学習では、高精度だが学習コストがかかる深層学習と比べて、高速でそれなりの精度を得ることができる。
【０００３】
一方、最適解の探索を行う汎用アルゴリズムとしてアニーリングが知られている。アニーリングマシンはアニーリングを高速に実行し近似最適解を出力する専用の装置である（例えば特許文献１、非特許文献１、非特許文献２参照）。アニーリングマシンでは汎用的に問題を受け付け可能な計算モデルとして、イジングモデルを用いている。アニーリングマシンはイジングモデルのパラメータを入力として持つ。そのためアニーリングマシンのユーザは解きたい問題をイジングモデルに変換する必要がある。
【０００４】
アンサンブル学習で、正答率が高く、互い類似しない弱分類器の組合せを求めるための評価関数は、イジングモデルに変換が可能である。これについて、ディー・ウェイブ・システムズ社のハードウェアに適用した例が報告されている（非特許文献１、非特許文献２参照）。これらの非特許文献では、アニーリングマシンにより、互いに相関が小さく、必要最小限の弱分類器により構成される、単純性が優れた強分類器の構成を導出できることが示唆されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】国際公開ＷＯ２０１５／１３２８８３
【非特許文献】
【０００６】
【非特許文献１】“NIPS 2009 Demonstration: Binary Classification usingHardware Implementation of Quantum Annealing”Hartmut Neven et.al., December 7, 2009
【非特許文献２】“Deploying a quantum annealing processor to detect tree cover in aerial imagery of California”Edward Boyda et.al., PLOS ONE ｜ DOI:10.1371/journal.pone.0172505 February 27, 2017
【発明の概要】
【発明が解決しようとする課題】
【０００７】
先に述べたようにアニーリングマシンはイジングモデルを入力として持つが、アニーリングマシンにより分類問題を解く際、イジングモデルに定式化された完全グラフの構造から、ハードウェアに実装可能な単純かつ規則的なグラフ構造に変換するための変換工程が必要となる。
【０００８】
特許文献１にも記載されるように、イジングモデルは一般に以下のエネルギー関数Ｈ（ｓ）で表される。アニーリングマシンへの入力としてはＪｉｊ,ｈｉを与えることになる。一般にＪｉｊは相互作用係数と呼ばれ、他のスピン（隣接スピンと呼ばれる）から自スピンへの影響を規定する。また、ｈｉは外部磁場係数と呼ばれる。これらのパラメータを与えるとマシンがアニーリングを実行し、エネルギーが最小となるスピン配列ｓの近似解を出力する。
【０００９】
【数１】
2020009301.tif 000003
【００１０】
図１は、発明者らが検討した、非特許文献１の概要およびその課題を説明する概念図である。
【００１１】
処理Ｓ１０１では、弱分類器の辞書を用意する。弱分類器は、基本的な学習アルゴリズムで弱分類器単体として学習されている。用意された弱分類器から互いに補完しあう弱分類器を選択し、選択された弱分類器で精度のよい強分類器を構成することが以降の処理の目的である。
【００１２】
処理Ｓ１０２では、弱分類器の選択問題をイジングモデルのエネルギー関数に定式化する。イジングモデルのエネルギー関数に定式化することにより、アニーリングマシンで解を得ることができるようになる。
【００１３】
図１中で、Ｈはエネルギー関数で、これが最小となった場合が求める解となる。ｔは訓練データ（特徴量）であり、訓練データの集合Ｔに含まれる。訓練データに対しては、正解となる分類結果（クラス）が用意されている。正解としては例えば人間が判定した結果を用いる。
【００１４】
右辺第１項で、ｗｉはｉ番目の弱分類器の選択結果である重みであり、ｗｉ∈｛０、＋１｝である。０は非選択、＋１は選択を示す。Ｎは用意した弱分類器の数である。ｃｉ（ｔ）は訓練データｔに対するｉ番目の弱分類器による分類結果である。また、ｙ（ｔ）は訓練データｔの分類結果の正解である。分類結果は２クラスへの分類ラベルであり、（−１ or ＋１）になる。ここで例えば、分類結果が正解であった分類器のみを選択すると、右辺第１項は０となり最小値をとる。
【００１５】
右辺第２項は正則化項であり、冗長性回避と過学習（over−fitting）の抑制のために導入される。訓練データに対する過学習は、後の検証データを用いた分類に影響を与える。すなわち、選択される弱分類器の数が増えると、右辺第２項が大きくなるため、右辺第２項はペナルティ関数として機能する。λの値を調整することにより、ペナルティ関数の重みを調整し、選択される弱分類器の数を調整することができる。一般に、λの値が大きくなると、選択される弱分類器の数は少なくなる。
【００１６】
このような問題を解くことで、準備された弱分類器の集合から、適切な弱分類器を選択することができる。処理Ｓ１０３以降で、この問題をアニーリングマシンに処理させる。
【００１７】
処理Ｓ１０３のグラフ埋め込みでは、定式化したイジングモデルの複雑なグラフ構造を、アニーリングマシンのハードウェアに実装可能な単純で規則的なグラフ構造に変換する。このためのアルゴリズムは公知のため、説明は省略する。定式化したイジングモデルの例としては、例えばＳ１０２の式で表現される完全結合グラフ（全ての頂点同士が接続された状態）がある。
【００１８】
以上の処理Ｓ１０１〜処理Ｓ１０３までは、サーバ等の情報処理装置（上位装置）でソフトウェア的に処理を行なう。
【００１９】
処理Ｓ１０４では、専用ハードウェアであるアニーリングマシンにより、アニーリング計算を行なう。具体的には、エネルギー状態が最小となったときのアニーリングマシンのスピン配列ｓを読み出すことで、最適解を得る。
【００２０】
アニーリングマシンの例として、例えば特許文献１では、半導体メモリ技術を適用したスピンユニットを、複数アレイ状に構成した例が開示されている。スピンユニットには、スピンを表す情報を格納するメモリ、他のスピン（隣接スピン）との相互作用を表す相互作用係数を格納するメモリ、外部磁場係数を格納するメモリ、および相互作用計算を行いスピンを表す情報を生成する演算回路が内蔵されている。複数スピンユニットで並列的に相互作用計算を行い、スピンの状態をエネルギーの小さい状態に遷移させることで、基底状態探索を行なう。
【００２１】
アニーリングマシンで処理を行なうためには、処理Ｓ１０３で変換したグラフ構造をデータとして上位装置からアニーリングマシンのメモリに書き込む。その後、アニーリングの処理を行ない、基底状態に至った時点のスピンｓｉを読み出して解を得る。弱分類器の選択問題の場合の解とは、弱分類器の選択結果ｗｉであり、スピンｓｉで定まる。
【００２２】
スピンの定義は自由であるが、例えばスピンが上向きのときｓｉ＝“＋１（あるいは１）”、スピンが下向きのときｓｉ＝“−１（あるいは０）”とする。重みを示すｗｉとして計算の便宜上（１ or ０）の値域を取る場合には、ｓｉ＝２ｗｉ−１で換算すればよい。具体的なアニーリングマシンの構成や動作については、特許文献1やディー・ウェイブ・システムズ社の製品などで公知なので、ここでは省略する。
【００２３】
処理Ｓ１０５では、アニーリングマシンで得た解をもとに弱分類器を選択して強分類器を構成する。通常このような弱分類器、強分類器はソフトウェアで構成することができ、アニーリングマシン外の情報処理装置（上位装置）が行なう。この強分類器に検証データを入力し、解を得て性能を検証する。
【００２４】
ここでＣ（ν）は強分類器で検証データνを分類した結果であり、それはＮ個から選択された弱分類器ｃｉによる分類結果（−１ or ＋１）の多数決として得られる。また、ｅｒｒは集合Ｖに含まれる検証データνに対して分類を誤った数をカウントした結果である。ｅｒｒ（ν）は“０”か“１”の２値をとり、強分類器の分類結果Ｃ（ν）が正解ｙ（ν）と一致したとき“０”、一致しないとき“１”としている。
【００２５】
処理Ｓ１０５で得られた分類精度ｅｒｒに基づいて、処理Ｓ１０２に戻り必要なパラメータを調整し、処理Ｓ１０４にフィードバックする。図１の例では調整するパラメータはλである。そして、例えばｅｒｒが所定閾値を下回るなど、満足できる強分類器の精度を得られるまで処理Ｓ１０４と処理１０５を繰り返すことで、パラメータを最適化する。
【００２６】
上記のシーケンスにおいて、実用上の課題の一つは、処理Ｓ１０４と処理１０５を繰り返すことによる処理時間の増加である。先に述べたように、処理Ｓ１０４では、専用ハードウェアであるアニーリングマシンにより処理を行なうが、処理のたびにサーバ等の上位装置からアニーリングマシンへのデータの書き込みと読み出しを行なう必要があり、データ転送時間のため処理に時間がかかる。
【００２７】
図２Ａ、図２Ｂを用いて、グラフ埋め込みの処理Ｓ１０３の概念を説明する。先に述べたように、グラフ埋め込みでは、イジングモデルの複雑なグラフ構造を、アニーリングマシンのハードウェアに実装可能なグラフ構造に変換する必要がある。具体的には、イジングモデルのグラフ構造は、解くべき問題から論理的に変換された構造となる。一方、アニーリングマシンのハードウェアでは、例えば１つのノードに対するエッジの数、すなわち接続されている他のノードの数は、当初から固定されている。よって、ハードウェアの制約条件に基づいて、ハードウェアに実装可能なグラフ構造に変換する必要がある。
【００２８】
変換の方式の一つは、グラフ構造のエッジとノードを全て保存して変換する完全型グラフ埋め込みである。この方式では、変換に際してエッジとノードの欠落がないが、アニーリングマシンに実装されているスピンのうち、複数のスピンをグラフ構造の１つのノードに対応させる必要がある。このため、アニーリングマシンに実装されているスピンの数をＮとすると、√Ｎ＋１の弱分類器しか同時に処理できなくなる。
【００２９】
一方、アニーリングマシンのスピンとモデルのノードを１対１対応させるone−to−oneグラフ埋め込みでは、アニーリングマシンのスピンの数Ｎと同じＮ個の分類器を１回で処理できる。よって、アニーリングマシンに実装されたスピン数を有効活用できるが、元のグラフ構造のエッジの一部が欠落する場合がある。
【００３０】
例えば、非特許文献１に記載される技術では、スピン数を有効活用するため、変換の前後でグラフの頂点（ノード）数を確保し、重みが大きいエッジすなわち弱分類器間の相関が大きいエッジを優先して残すようにグラフ変換を行なう。しかし、相関が小さいエッジの消失により、結合係数の総和よりも常に外部磁場係数が大きくなるスピンが生じ、最適化できない弱分類器が発生する。これはスピン数が多くなるほど影響が大きくなる。
【００３１】
図２Ａに示す例で説明する。この例では、グラフ埋め込み前の完全グラフを、ハードウェアによって定まるKing's graphと呼ばれるグラフに埋め込む例である。この場合、グラフ埋め込み前の相関が小さいエッジＪ１４とＪ２３は、グラフ埋め込み後には消失している。すると、ノード２において、常に外部磁場係数ｈ２＞Ｊ１２＋Ｊ２５＋Ｊ２４となる場合が想定される。常に外部磁場係数が隣接スピンの相互作用より大きくなると、最適化ができなくなる。
【００３２】
例えば、特許文献１に記載のアニーリングマシンでは、アニーリング中に遷移するスピンの次状態を決めるに当たり、各スピンユニットでは隣接スピンとの間でエネルギーを最小化するようにスピンの次状態を決定する。この処理は、隣接スピンと相互作用係数Ｊｉｊの積、及び、外部磁場係数ｈｉを観察したときに、正の値と負の値のどちらが支配的か判断することと等価である。ところが、グラフ埋め込みによって所定のエッジが欠落することにより、外部磁場係数ｈｉが元のモデル以上に支配的になる。
【００３３】
図２Ｂでその影響を説明する。図２Ｂに見られるように、スピン数が増えるととともに埋め込むことができるエッジすなわち相互作用係数Ｊｉｊの割合が減っていく。このため、スピン数が増えるに従って、精度が下がると考えられる。グラフ２００１は埋め込みの限界値を示す。グラフ２００２は非特許文献１に記載の埋め込みアルゴリズムを用いて、重みの大きいエッジを優先的に選択してグラフ変換を実施した結果である。グラフ２００３は、全ての重みの平均値とエッジ数の積であり、機械的にグラフを変換した場合である。いずれの手法でも、スピン数（ノード数）が１００を超えるグラフでは、埋め込み可能な相互作用係数が１０％以下になってしまうことが分かる。
【００３４】
アニーリング計算では妥当な結果を得るために、ｈｉやλのようなパラメータを調節することが望ましい。しかし、図１に示した従来の手法では、ｈｉやλのようなパラメータを変更するためには、上位装置での処理Ｓ１０５の結果を基にパラメータを調整し、アニーリング計算を繰り返す必要があった。この場合、アニーリングマシンに対するデータの書き込み、読み出しのため、処理に時間がかかる問題がある。よって、アニーリングマシンに埋め込むグラフのパラメータ調整の手法として、より効率的な手法が求められる。
【課題を解決するための手段】
【００３５】
本発明の好ましい一側面は、複数のスピンユニットを備えたアニーリング計算回路を備え、イジングモデルを用いて解を求める情報処理装置である。この装置では、複数のスピンユニットの其々は、イジングモデルのスピンの値を記憶する第１のメモリセルと、スピンに相互作用を及ぼす隣接スピンとの相互作用係数を記憶する第２のメモリセルと、スピンの外部磁場係数を記憶する第３のメモリセルと、隣接スピンの値、相互作用係数、及び外部磁場係数に基づいて、スピンの次の値を決定する演算を行う演算回路と、を備える。さらに、外部磁場係数を単調増加あるいは単調減少で更新する、外部磁場係数更新回路を備え、アニーリング計算回路は、更新された外部磁場係数に基づいて、演算回路により複数回のアニーリング計算を行う情報処理装置である。
【００３６】
本発明の好ましい他の一側面は、上位装置である情報処理装置と、イジングモデルを用いてアニーリング計算を行い解を求めるアニーリングマシンを用いる情報処理方法である。この方法では、情報処理装置において、弱分類器を生成し、検証データで弱分類器の分類結果を得、弱分類器で強分類器を構成する際の弱分類器の選択問題を、アニーリングマシンのハードウェアに適合したイジングモデルに変換してアニーリングマシンに送る。また、アニーリングマシンにおいて、イジングモデルのパラメータである、外部磁場係数と相互作用係数をそれぞれメモリセルに格納し、複数回のアニーリング計算を行なう際には、外部磁場係数を単調増加あるいは単調減少で更新してから、其々のアニーリング計算を実行する。
【発明の効果】
【００３７】
アニーリングマシンに埋め込むグラフのパラメータ調整の手法として、より効率的な手法を提供できる。
【図面の簡単な説明】
【００３８】
【図１】発明の課題を説明する概念図。
【図２Ａ】グラフ埋め込みの概念を説明する概念図。
【図２Ｂ】グラフ埋め込みで埋め込まれる相互作用係数の割合を説明するグラフ図。
【図３Ａ】実施例の情報処理システムの全体構成を示すブロック図。
【図３Ｂ】アニーリング計算回路の一つのスピンユニットを示す回路ブロック図。
【図４】実施例の情報処理システムの全体処理を示すフロー図。
【図５】分類結果データの例を示す表図。
【図６】検証誤差検証回路の例を示すブロック図。
【図７】検証誤差検証回路の計算例を示す概念図。
【図８】他の実施例の情報処理システムの全体構成を示すブロック図。
【図９】外部磁場係数更新回路の例を示すブロック図。
【図１０】ブースティングを利用した実施例の情報処理システムの全体処理を示すフロー図。
【図１１】ブースティングの手法を取り入れた実施例の処理の一部を示すフロー図。
【図１２】ブースティングにおいて検証誤差計算を合理化する手法の概念図。
【図１３】検証誤差計算回路で行なわれる検証誤差計算のフロー図。
【図１４】ブースティングの検証誤差に関する考え方を説明する概念図。
【図１５】完全型埋め込みに適用した実施例の全体フロー図。
【図１６Ａ】分類器の相関を表す相互作用係数ｊｉｊの分布を示すグラフ図。
【図１６Ｂ】横軸に相互作用係数ｊｉｊのビット数を示し、縦軸に許容可能な学習サンプル数を示したグラフ図。
【図１６Ｃ】あるスピンに対する相互作用係数ｊｉｊと外部磁場係数ｈｉの関係を示す模式図。
【発明を実施するための形態】
【００３９】
実施の形態について、図面を用いて詳細に説明する。ただし、本発明は以下に示す実施の形態の記載内容に限定して解釈されるものではない。本発明の思想ないし趣旨から逸脱しない範囲で、その具体的構成を変更し得ることは当業者であれば容易に理解される。
【００４０】
以下に説明する発明の構成において、同一部分又は同様な機能を有する部分には同一の符号を異なる図面間で共通して用い、重複する説明は省略することがある。
【００４１】
同一あるいは同様な機能を有する要素が複数ある場合には、同一の符号に異なる添字を付して説明する場合がある。ただし、複数の要素を区別する必要がない場合には、添字を省略して説明する場合がある。
【００４２】
本明細書等における「第１」、「第２」、「第３」などの表記は、構成要素を識別するために付するものであり、必ずしも、数、順序、もしくはその内容を限定するものではない。また、構成要素の識別のための番号は文脈毎に用いられ、一つの文脈で用いた番号が、他の文脈で必ずしも同一の構成を示すとは限らない。また、ある番号で識別された構成要素が、他の番号で識別された構成要素の機能を兼ねることを妨げるものではない。
【００４３】
図面等において示す各構成の位置、大きさ、形状、範囲などは、発明の理解を容易にするため、実際の位置、大きさ、形状、範囲などを表していない場合がある。このため、本発明は、必ずしも、図面等に開示された位置、大きさ、形状、範囲などに限定されない。
【００４４】
本明細書で引用した刊行物、特許および特許出願は、そのまま本明細書の説明の一部を構成する。
本明細書において単数形で表される構成要素は、特段文脈で明らかに示されない限り、複数形を含むものとする。
【実施例１】
【００４５】
図３Ａは実施例の情報処理システムの全体ブロック図である。制御装置３００は例えばサーバ等の上位装置である。制御装置３００にはＩ／Ｏインターフェース５００を介してアニーリングマシン６００が接続されている。またアニーリングマシン６００は外部メモリ７００をアクセス可能である。Ｉ／Ｏインターフェース５００、アニーリングマシン６００、外部メモリ７００は、それぞれ１チップの半導体装置として、例えばボード４００上に搭載する。なお、ボード４００上には複数のアニーリングマシン６００や複数の外部メモリ７００が搭載されていても良い。
【００４６】
制御装置３００は一般的なサーバで構成され、サーバは入力装置、出力装置、プロセッサ、記憶装置等の周知の構成を備える（図示せず）。本実施例では制御装置３００の計算や制御等の機能は、記憶装置に格納されたプログラムがプロセッサによって実行されることで、定められた処理を他のハードウェアと協働して実現される。計算機などが実行するプログラム、その機能、あるいはその機能を実現する手段を、「機能」、「手段」、「部」、「ユニット」、「モジュール」等と呼ぶ場合がある。
【００４７】
制御装置３００には、弱分類器を構成し、学習するための弱分類器生成部３１０、弱分類器の選択問題をイジングモデルの基底状態探索に変換し、アニーリングマシンのハードウェアにグラフ埋め込みする問題変換部３２０、および、アニーリングマシンを制御するアニーリングマシン制御部３３０がソフトウェアで実装されている。
【００４８】
本実施例では、アニーリングマシン６００の一部として、特許文献1記載の構成を採用することを考える。アニーリングマシン６００は、例えば１チップの半導体装置で構成されており、メモリアクセスインターフェース６１０、外部メモリアクセスインターフェース６２０、内蔵メモリ６３０、アニーリング計算回路６４０、外部磁場係数更新回路６５０、検証誤差計算回路６６０、制御部６７０を搭載している。内蔵メモリ６３０や外部メモリ７００は、例えばＳＲＡＭ（Static Random Access Memory）やフラッシュメモリのような、揮発性もしくは不揮発性の半導体メモリで構成することができる。
【００４９】
メモリアクセスインターフェース６１０は、制御装置３００から内蔵メモリ６３０のアクセスを可能とする。外部メモリアクセスインターフェース６２０は、アニーリングマシン６００から外部メモリ７００のアクセスを可能とする。制御部６７０は、後に図４で説明するアニーリングマシン６００の各部の処理全体を統括制御する。
【００５０】
内蔵メモリ６３０は、アニーリングマシン６００で処理するもしくは処理したデータを格納する。内蔵メモリ６３０は便宜的に、アニーリングのためのループ条件を格納するループ条件格納メモリ６３１、アニーリングの条件を格納するアニーリング条件格納メモリ６３２、アニーリング計算に用いる係数値を格納する係数格納メモリ６３３、弱分類器の分類結果を格納する分類結果格納メモリ６３４、および、スピン値の検証誤差を格納するスピン値検証誤差格納メモリ６３５を含む。データの内容については後述する。
【００５１】
アニーリング計算回路６４０は、例えば特許文献１に開示されているスピンの基底状態探索が可能なデバイスである。外部磁場係数更新回路６５０は、アニーリング計算回路の計算で用いる外部磁場係数の更新を行なう回路である。検証誤差計算回路６６０は、アニーリング計算回路６４０の計算結果による弱分類器の検証誤差を計算する回路である。
【００５２】
図３Ｂはアニーリング計算回路６４０を構成するスピンユニットの詳細構成例を示す回路図である。本実施例では、アニーリング計算回路６４０は、特許文献１で開示されている半導体メモリおよび論理回路で構成されたスピンユニット６４１を複数個並べて、スピンアレイを構成し、並列動作させて基底状態探索をする。本明細書に記載のない部分については、特許文献１などの公知技術を踏襲してよい。
【００５３】
スピンユニット６４１は一つのスピンに対応するものであり、イジングモデルの一つのノードに対応している。１個のスピンユニット６４１は、インターフェース６４２であるＮＵ，ＮＬ，ＮＲ，ＮＤ，ＮＦを用いて、隣接スピンのスピンユニットと結線されており、隣接スピンのスピンの値を入力としている。また、自スピンの値ｓｉはスピンメモリセル６４３に格納され、出力Ｎとして隣接スピンに出力される。この例では、一つのノードは５つのエッジを持つ。
【００５４】
スピンユニット６４１は、イジングモデルの相互作用係数Ｊj,iおよび外部磁場係数ｈｉを保持するために、係数メモリセル群６４４を備えている。係数メモリセルは外部磁場係数ｈｉを保持するＩＳ０，ＩＳ１と、相互作用係数Ｊj,iを保持するＩＵ０，ＩＵ１，ＩＬ０，ＩＬ１，ＩＲ０，ＩＲ１，ＩＤ０，ＩＤ１，ＩＦ０，ＩＦ１として図示されている。なお、この例ではＩＳ０とＩＳ１、ＩＵ０とＩＵ１、ＩＬ０とＩＬ１、ＩＲ０とＩＲ１、ＩＤ０とＩＤ１、および、ＩＦ０とＩＦ１はそれぞれ２個１組で役割を果たすが、特に限定するものではない。以後の説明では、それぞれまとめてＩＳｘ，ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ，および、ＩＦｘと略記する。
【００５５】
スピンユニット６４１が有する各メモリセルの構造の一例としては、公知のＳＲＡＭメモリのセルを利用することができる。もっとも、メモリセル構造はこれに限られず、少なくとも２値を記憶できる構成であればよい。例えば、ＤＲＡＭやフラッシュメモリのような他のメモリを用いることができる。
【００５６】
ここで、スピンユニット６４１はｉ番目のスピンｓｉを表現するものとして説明を行う。スピンメモリセル６４３はスピンｓｉを表現するためのメモリセルでありスピンの値を保持する。スピンの値はイジングモデルでは＋１／−１（＋１を上、−１を下とも表現する）であるが、メモリ内部では２値である１／０に対応させる。この例では、＋１を１、−１を０に対応させることにするが、逆の対応でもかまわない。
【００５７】
ＩＳｘは外部磁場係数を表現する。また、ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ，ＩＦｘはそれぞれ相互作用係数を表現する。ＩＵｘは上側のスピン（Ｙ軸方向で−１）、ＩＬｘは左側のスピン（Ｘ軸方向で−１）、ＩＲｘは右側のスピン（Ｘ軸方向で＋１）、ＩＤｘは下側のスピン（Ｙ軸方向で＋１）、ＩＦｘは奥行き方向に接続するスピン（Ｚ軸方向で＋１ないしは−１）との相互作用係数を示している。
【００５８】
論理回路６４５は隣接スピンとの間でエネルギー計算を行なって、自スピンの次状態を計算する。本実施例では、スピンの値を仮想的な温度Ｔで決まる確率で反転させることにした。ここで温度Ｔは基底状態探索の過程を物理的なアニーリングに例えたものである。基底状態探索の初期では高い温度とし、徐々に温度を下げながら局所的な探索を行い、最終的に温度がゼロとなる状態まで冷却していく。この条件の設定は、アニーリング条件格納メモリ６３２に格納しておく。
【００５９】
スピンの値を所定確率で反転させるために、例えば乱数発生器とビット調整器を用いる。ビット調整器は、基底状態探索の初期では高い確率でスピンの値を反転させ、終期では低い確率でスピンの値を反転させるように、乱数発生器からの出力ビットを調整するものである。具体的には、乱数発生器の出力から所定ビット数を取り出し、多入力のＡＮＤ回路またはＯＲ回路で演算することにより、基底状態探索の初期では１が多く、基底状態探索の終期では０が多く発生するように出力を調整する。
【００６０】
ビット調整器出力がＶＡＲである。ビット調整器出力ＶＡＲは反転論理回路６４６に入力される。論理回路６４５の出力は局所解であるスピンの値を出力するが、反転論理回路６４６でＶＡＲが１だった場合、スピンの値を反転させる。このようにして、スピンの値を格納するスピンメモリセル６４３には、所定確率で反転された値が格納されることになる。
【００６１】
ライン６４７は、複数のスピンユニット６４１で単一の乱数発生器とビット調整器を共有するための構成であり、隣接するスピンユニットへビット調整器出力ＶＡＲを転送する。
【００６２】
図４は図３Ａの情報処理システムによる処理の全体フローを示す図である。フロー左側は制御装置３００で実行される処理Ｓ３０００である。また、フロー右側はアニーリングマシン６００で実行される処理Ｓ６０００である。
【００６３】
まず、制御装置３００側での処理を説明する。制御装置３００の処理は一般的なサーバがソフトウェアを実行することで実現される。
【００６４】
処理Ｓ４１１では、弱分類器生成部３１０は、訓練データＴを準備し、データｔそれぞれに重みｄを付与する。重みの初期値は均等でよい。訓練データＴは特徴量とそれに対する分類の正解が付与されたデータである。本明細書では、特徴量とそれに対する分類の正解が付与された個々の訓練データをｔと、その集合をＴと表記することにする。なお処理Ｓ４１１は省略し固定的に均等重みとしてもよい。重み付けを利用したブースティングの手法については後の実施例で説明する。
【００６５】
処理Ｓ４１２では、弱分類器生成部３１０は、訓練データＴを用いて個々の弱分類器を生成（学習）する。弱分類器としてはStump（決定株）など公知の種々のものを用いることができ、特に制限はない。Stumpは特徴ベクトルのある次元の値を閾値θと比較して判別する分類器であり、簡単な例では、ｆｉ，θ（ｘ）＝｛＋１，−１｝で示される。もしｘｉ，≧θであれば“＋１”であり、それ以外で“−１”の値を取る。個々の弱分類器の学習とはθの学習である。
【００６６】
処理Ｓ４１３では、弱分類器生成部３１０は、検証データＶで弱分類器の分類結果を計算する。本例では、検証データＶは訓練データＴとは異なるデータを持つが、訓練データと同様正解が分かっているデータである。
【００６７】
図５は、検証データＶで弱分類器の分類結果を検証した例を示す表図である。図５（ａ）では、横軸が検証データＶのサンプルのインデックスνであり、縦軸は弱分類器のインデックスｉである。表において、νとｉの交点は該当する検証データを該当する弱分類器で正しく分類したかどうかを示す結果を示す。すなわち、弱分類器の分類結果ｃｉ（ν）が正解ｙ（ν）と一致するかどうかを、一致する場合チェックマークで、一致しない場合ｘマークで表したものである。
【００６８】
図５（ｂ）は、図５（ａ）で示す検証結果を、アニーリングマシン６００の分類結果格納メモリ６３４に分類結果として格納するための関数Δｍｉ（ν）に変換した例を示す図である。横軸が検証データＶのサンプルのインデックスνであり、縦軸は弱分類器のインデックスｉである。弱分類器の分類結果ｃｉ（ν）が正解ｙ（ν）と一致するかどうかを、関数Δｍｉ（ν）の値として、一致する場合“１”、一致しない場合“−１”の値で格納している。
【００６９】
処理Ｓ４１４では、問題変換部３２０は、学習した弱分類器に基づいて、エネルギー関数により相互作用係数Ｊｉｊ，ｐｒｉとｘｉを定める。弱分類器としてStumpを用いた場合であれば、弱分類器の決定木のθに依存して、イジングモデルのパラメータＪｉｊ，ｐｒｉとｘｉが得られることになる。より詳細には，Ｊｉｊは訓練データの分類結果に基づく弱分類器間の相関、ｈｉは各弱分類器の訓練データに対する分類精度で決まるので、弱分類器の訓練データに対する分類結果に依存してイジングモデルのパラメータが定まるが、分類結果はθに依存するので、パラメータはθに依存することになる。
（数式２）
【００７０】
【数２】
2020009301.tif 000004
【００７１】
上の（数式２）は、一般的なイジングモデルのエネルギー関数Ｈを表現する式である。イジングモデルは与えられたスピン配列、相互作用係数、および、外部磁場係数から、その時のエネルギーＨ（ｓ）を計算することが出来る。ｓｉ，ｓｊはそれぞれｉ番目とｊ番目のスピンの値で“＋１”か“−１”の値をとる。なお、図１の重みｗｉとの関係ではｓｉ＝２ｗｉ−１となる。Ｊi,jはｉ番目とｊ番目のスピンの間の相互作用係数、ｈｉはｉ番目のスピンに対する外部磁場係数、ｓはスピンの配列を表わすものとする。本実施例のイジングモデルではｉ番目スピンからｊ番目スピンへの相互作用と、ｊ番目スピンからｉ番目スピンへの相互作用を区別することはない。つまり、Ｊi,jとＪj,iは同一である。イジングモデルをアニーリングマシンの入力とし、アニーリングを行なうことでＨ（ｓ）最小のときのスピンの配列ｓを得ることができる。
（数式３）
【００７２】
【数３】
2020009301.tif 000005
【００７３】
上の（数式３）は、本実施例において弱分類器の決定木を変換したイジングモデルである。基本的に（数式２）と同様だが、（数式２）の右辺第２項の外部磁場係数ｈｉをａ（ｘｉ−λ）ｓｉに置き換えている。すなわち本実施例では、グラフ埋め込みによる精度劣化を補償するために、正則化係数λに加えて外部磁場係数ｈｉを調整するパラメータａを導入している。Ｊｉｊ priは、グラフ埋め込み前のモデルの相互作用係数を示している。
【００７４】
処理Ｓ４１４では、問題変換部３２０は、準備した弱分類器に基づいて、エネルギー関数により、（数式３）中の相互作用係数Ｊｉｊ priとｘｉを計算する。
【００７５】
【数４】
2020009301.tif 000006
【００７６】
Ｊｉｊ priを計算する（数式４）で、左辺Ｊｉｊ priに対する右辺は、弱分類器間の相関を判定し、同じデータに対して同じ分類結果を持つ弱分類器を同時に選択しないように機能する。すなわち、ｉ番目の弱分類器の分類結果ｃｉ（ｔ）とｊ番目の弱分類器の分類結果ｃｊ（ｔ）が同じ場合にはＪｉｊ priが負になり、両方の弱分類器を選択すると(数式３）のＨ（ｓ）を示す第１式の右辺第１項が増加するため、ペナルティ関数として機能することになる。パラメータｔは訓練データＴの集合から選ばれる訓練データである。
【００７７】
【数５】
2020009301.tif 000007
【００７８】
ｘｉを計算する（数式５）で、右辺は弱分類器と分類結果との相関を判定し、正答率が高い弱分類器を選択するものである。すなわち、右辺第１項は、ｉ番目の弱分類器の分類結果ｃｉ（ｔ）と正解ｙ（ｔ）が同じ場合に大きくなり、ｘｉの絶対値は大きくなる。（数式３）の右辺第２項ではｘｉにマイナスがかかっているため、スピンＳｉが−１（非選択）のときのエネルギーＨ（ｓ）は大きくなり、スピンＳｉが＋１（選択）のときエネルギーが小さくなるため、不正解時のペナルティ関数として機能することになる。また、右辺第２項は、（数式４）と同様に類似する結果を持つ弱分類器を同時に選択しないように機能する。
【００７９】
処理Ｓ４１５では、問題変換部３２０は、エネルギー関数をアニーリングマシン６００のハードウェアに適合するように、グラフ埋め込み行なう。グラフ埋め込みの結果、相互作用係数Ｊｉｊ，ｐｒｉは、ハードウェアに制約された相互作用係数Ｊｉｊに変換される。このとき、非特許文献１で説明されるように、相互作用係数Ｊｉｊが重いものから優先的にグラフに埋め込んでいく。
【００８０】
【数６】
2020009301.tif 000008
【００８１】
（数式６）は、本実施例においてone−to−oneグラフ埋め込みを行なった例である。第１式において、左辺のＨ（ｓ）はエネルギー関数で、Ｈ（ｓ）が最小となるスピンｓの組み合わせが解となる。概念的に一つのスピンは一つの弱分類器に対応する。右辺第１項のｉ，ｊはアニーリングマシンに埋め込まれたスピンの集合εから選ばれるスピンを表すインデックスである。Ｊｉｊは、ｉ番目のスピンからｊ番目のスピンへの相互作用係数であり、（数式４）で規定される。スピンｓは“１”が弱分類器の選択を、“−１”が弱分類器の非選択を示す。右辺第２項はグラフ埋め込みによる外部磁場係数ｈｉと正則化係数λを調整するための項である。
【００８２】
（数式６）の第２式は、左辺の外部磁場係数ｈｉを再定義したものである。パラメータａを導入することで、外部磁場を制御し、グラフ埋め込みの処理を１回で終了できるようにする。ここで、ｈｉ＝ａ（ｘｉ−λ）であり、λは正則化項、ａはダンピングパラメータである。
【００８３】
処理Ｓ４１６では、アニーリングマシン制御部３３０が、処理Ｓ４１５でグラフに埋め込まれたイジングモデルをアニーリングマシン６００に送信する。また、処理Ｓ４１３で得られた分類結果Δｍｉ（ν）をアニーリングマシン６００に送信する。グラフ埋め込みされたイジングモデルのデータは、具体的には（数式６）の相互作用係数Ｊi,jとパラメータｘｉである。ａとλについては、最初からアニーリングマシンに記憶させておいても良いが、制御装置３００からａとλを送信しても良い。
【００８４】
処理Ｓ４１７では、アニーリングマシンにアニーリングの実行を命令する。次に、アニーリングマシン６００側での処理を説明する。
【００８５】
処理Ｓ４２１では、処理Ｓ４１６で送信されたデータを受信したアニーリングマシン６００では、相互作用係数Ｊi,jとパラメータｘｉを係数値として係数格納メモリ６３３に格納する。相互作用係数Ｊi,jとパラメータｘｉはスピンのインデックスｉ，ｊに対応して記憶される。また、図５に示した分類結果Δｍｉ（ν）を分類結果格納メモリ６３４に格納する。なお、アニーリング条件格納メモリ６３２は、アニーリングを行なう際の温度に相当するパラメータＴや、その他のパラメータ（例えばアニーリング回数ｑなど）を格納するものである。このパラメータＴもアニーリングマシン制御部３３０から送信することができる。アニーリングを行なう際の温度パラメータＴその他については、アニーリングマシンの構成と共に公知であるため、説明は省略する。
【００８６】
本実施例では、制御装置３００から一度これらのデータをアニーリングマシン６００に送ると、最終的な解を得るまではアニーリングマシンとデータの送受信を行なう必要がない。パラメータａとλは、ループ条件を規定する関数ａ（ｋ），λ（ｌ）として、例えばテーブル形式でループ条件格納メモリ６３１に格納されている。なお、ループ条件は必要に応じて制御装置３００から送信しても良い。処理Ｓ４２２以降では、ループ条件ａ，λを変更することで、外部磁場係数ｈiを変更しながらアニーリングを繰り返し、最適なスピン値を検索する。
【００８７】
アニーリングマシン６００では、イジングモデルに基づいて係数を設定する。すなわち、（数式６）の相互作用係数Ｊｉｊおよび外部磁場係数ｈｉを設定する。そして、アニーリングを行い基底状態を探索する。例えば、既に述べたように、特許文献１に記載されているハードウェアでは、一つのスピンに対して、相互作用係数Ｊｉｊおよび外部磁場係数ｈｉを設定するためのメモリが、ＳＲＡＭ互換インターフェースによりリード・ライト可能となっている。従って、このハードウェアをアニーリング計算回路６４０に採用する場合には、メモリアクセスインターフェース６１０としてＳＲＡＭ互換インターフェースを用い、アニーリング計算回路６４０のメモリに、各スピンに対応して相互作用係数Ｊｉｊおよび外部磁場係数ｈｉをセットする。
【００８８】
本実施例では、処理Ｓ４２２以降で外部磁場係数ｈｉの値を変更しつつアニーリングを行う、より具体的にはａ（ｋ）とλ（ｌ）の値を変更しつつ、最適なスピンの値を探す。外部磁場係数ｈｉの値の変更の範囲は、グラフに埋め込み前の外部磁場係数を最大値とし、０を最小値とする。本実施例では、ａ（ｋ）とλ（ｌ）は単調増加関数として説明する。ただし、ａ（ｋ）とλ（ｌ）の種々の組み合わせが試行できるのであれば、一方または両方を単調減少関数としてもよい。単調増加関数とは、ｋあるいはｌが増えると必ず値が増える関数であり、単調減少関数はｋあるいはｌが増えると必ず値が減る関数である。
【００８９】
まず処理Ｓ４２３では、ａ（ｋ）を読み込む。ｋは１から始まり、処理Ｓ４２２で最大値ｋｍａｘに至るまでインクリメントされる。ｋが最大値ｋｍａｘを越えた場合には、アニーリングは終了となる（処理Ｓ４２２）。なお、本実施例ではａ（ｋ）を最小値から増加する方向で処理を進めるが、逆にａ（ｋ）を最大値から減少する方向で処理を進めてもよい。なお、ａ（ｋ）の最大値としては、たとえば弱分類器のトータル個数の２倍のように決める。
【００９０】
次に処理Ｓ４２５では、処理Ｓ４２３で設定したａ（ｋ）において、λ（ｌ）を読み込む。ｌは１から始まり、処理Ｓ４２４で最大値ｌｍａｘに至るまでインクリメントされる。ｌが最大値ｌｍａｘを越えた場合には、処理Ｓ４２２〜Ｓ４２３でａ（ｋ）を更新する。なお、本実施例ではλ（ｌ）を最小値から増加する方向で処理を進めるが、逆にλ（ｌ）を最大値から減少する方向で処理を進めてもよい。処理Ｓ４２２でｋがｋｍａｘを超えると、制御装置３００に終了通知が送られる（処理Ｓ４１８）。
【００９１】
ａ（ｋ）、λ（ｌ）は前述のようにテーブル形式でループ条件格納メモリ６３１に格納しておくが、所定の関数形式で記憶しておいても良い。
【００９２】
処理Ｓ４２６では、外部磁場係数更新回路６５０が、係数格納メモリ６３３からｘｉを読み出すと共に、設定されたａ（ｋ）とλ（ｌ）に基づいて外部磁場係数ｈｉを計算する。外部磁場係数ｈｉ＝ａ（ｋ）（ｘｉ−λ（ｌ））である。
【００９３】
処理Ｓ４２７〜４３０では、処理Ｓ４２６の計算で得られた外部磁場係数ｈｉを用いて、ｑｍａｘ回アニーリングを繰り返す。図３Ｂで説明した回路では、各スピンに対応する外部磁場係数ｈｉは、係数メモリセル群６４４のメモリセルに格納される。従って、当該メモリセルの外部磁場係数ｈｉを更新しつつ、アニーリングを行なうことになる。
【００９４】
処理Ｓ４２８では、アニーリング計算回路６４０はアニーリングを行い、基底状態を探索し、基底状態におけるスピン配列ｓを得る。（数式６）においてスピンの値ｓｉはインデックスｉの弱分類器の選択結果（＋１  or  −１）を示す。アニーリングに関しては特許文献１や非特許文献１，２でも公知のため説明は省略する。
【００９５】
処理Ｓ４２９では、検証誤差計算回路６６０は、解として得られた弱分類器の選択結果を用いて検証誤差ｅｒｒを計算する。
【００９６】
図６は検証誤差計算回路６６０の構成例を示すブロック図である。検証誤差計算回路６６０は、アニーリング計算回路６４０で得られた基底状態におけるスピン配列ｓと、分類結果格納メモリ６３４から読み出された分類結果Δｍｉ（ν）を用いて、検証誤差ｅｒｒを計算する。ここでスピンｓｉ＝｛＋１，−１｝はｓｉ＝２ｗｉ−１で重みｗｉ＝｛１，０｝に変換するものとする。重み“１”は分類器の選択、“０”は分類器の非選択を示す。
【００９７】
図７は検証誤差計算回路６６０が行なう計算を説明する概念図である。まず、乗算器６６１で分類結果Δｍｉ（ν）と重みｗｉを乗算する。この結果、選択された弱分類器の正誤判定が正答“＋１”、誤答“−１”として集計される。選択しなかった弱分類器については“０”として無視される。
【００９８】
これを加算器６６２で検証データサンプルのインデックス毎に合算すると、検証マージンｍ（ν）が得られる。検証マージンｍ（ν）は、弱分類器によるデータνの分類結果の正誤判定の集計を示している。エラー判定回路６６３では、検証マージンｍ（ν）を所定閾値と比較してエラー判定を行なう。例えば単純な多数決を基準とする場合には、閾値０として検証マージンｍ（ν）が負数の場合はｅｒｒ（ν）＝１（当該データサンプルに対してエラー有）、検証マージンｍ（ν）が正数の場合は、ｅｒｒ（ν）＝０（当該データサンプルに対してエラーなし）となる。加算器６６４では、ｅｒｒ（ν）を合算し、ｅｒｒを得る。図７の例ではｅｒｒ＝１（エラー有）となる。
【００９９】
以上のように、本実施例のアニーリングマシン６００は、グラフ埋め込み処理に影響しないパラメータを変更することで、アニーリング計算回路６４０の計算の条件を変更することができる。そして、分類結果格納メモリ６３４が弱分類器の分類結果Δｍｉ（ν）を格納しているため、これとアニーリング計算回路６４０の計算結果である重みｗｉを用いて、エラー判定を行なうことができる。よって、アニーリングマシン６００の中だけで、最適パラメータによる解を得ることが可能となる。
【０１００】
アニーリングは確率的な挙動に基づく計算なので、通常アニーリングマシンは複数回（図４の例ではｑｍａｘ回）のアニーリングを行なう。処理Ｓ４２８では、アニーリングマシンの機能を用いて基底状態を探索し、基底状態におけるスピンの値を計算する。
【０１０１】
処理Ｓ４３０では、エラー値ｅｒｒをそれまでのベスト値（エラーが最小の値）ｅｒｒ  ｂｅｓｔと比較する。最新のエラーの値がそれまでのベスト値より小さい場合には、そのときのスピン配列ｓとエラー値ｅｒｒを処理Ｓ４３１でｓｐｉｎ  ｂｅｓｔ，ｅｒｒ  ｂｅｓｔとして、スピン値検証誤差格納メモリ６３５に記憶し、ループ内で最適値を更新する。
【０１０２】
処理Ｓ４２２でｋがｋｍａｘを超えたとき、処理Ｓ４１８でアニーリングマシン６００から制御装置３００に終了通知が送られる。すると、ｓｐｉｎ  ｂｅｓｔ，ｅｒｒ  ｂｅｓｔの値は、処理Ｓ４１９のデータ読み出し指示により、スピン値検証誤差格納メモリ６３５から読み出され、制御装置３００に送信される。これが、アニーリングマシン６００で計算した最適な弱分類器の組み合わせとなる。
【０１０３】
本実施例によると、（数式６）のＨ（ｓ）を示す第１式において、グラフ埋め込みに依存するＪｉｊを含む右辺第１項以外の部分（すなわち右辺第２項）で、アニーリング条件を変更することができる。よって、グラフ埋め込み後に、アニーリングマシン６００の中でアニーリング条件の変更が可能となる。また、検証データの分類結果をアニーリングマシン６００に転送し、これを用いて結果の判定をアニーリングマシン６００の中で行なうことを可能としている。これらにより、アニーリング条件の変更と結果の判定をアニーリングマシン６００中で完結することができる。
【０１０４】
よって、例えば特許文献1記載のようなアニーリングマシンをＦＰＧＡ（Field−Programmable Gate Array）で構成した場合、ＦＰＧＡ内部で得た最適なスピンの組み合わせ結果（すなわち弱分類器の選択結果）を１回だけ制御装置３００に送信すればよいので、データ読み出しやデータ転送の時間を節約できる。
【実施例２】
【０１０５】
図８は、実施例２の情報処理システムの全体ブロック図である。実施例１では、分類結果格納メモリ６３４として、アニーリングマシン６００の内蔵メモリ６３０の一部を用いている。内蔵メモリ６３０は、例えばＦＰＧＡなどの１チップで構成されるアニーリングマシン６００の内蔵メモリであり、ＳＲＡＭ等の高速メモリである。しかし、分類結果が検証データの規模によりデータ容量が大きい場合には、内蔵メモリ６３０の代わりに、外部メモリ７００の一部を分類結果格納メモリ６３４に用いても良い。例えば同一ボード上に搭載された別チップにより構成される外部メモリであれば、制御装置３００からの読み出しに比べて高速な読み出しが可能である。
【０１０６】
また、外部メモリ７００には、場合によりアニーリング条件格納メモリ６３２や、スピン値検証誤差格納メモリ６３５を代替させてもよい。一方、外部磁場係数ｈｉを計算するための変数を格納するループ条件格納メモリ６３１や係数格納メモリ６３３は、高速に読み出すことが望ましいので、内蔵メモリ６３０を用いることが望ましい。なお、外部メモリ７００は、内蔵メモリ６３０に比べて容量を大きくすることが容易なので、デバッグ用に全てのスピンの値などの他のデータを格納してもよい。
【０１０７】
また、分類結果を外部メモリ７００に格納した場合、アニーリング計算中に前回のアニーリング結果の検証誤差の計算を並列で実施すれば良いので、外部メモリ７００とアニーリングマシン６００間のデータ転送で生じる遅延の影響を全体としては少なくすることが可能となる。
【実施例３】
【０１０８】
図９は、図３や図８で示した外部磁場係数更新回路６５０の一例を示す、詳細なブロック図である。実施例３では、外部磁場係数更新回路６５０の好適な具体例を示す。
【０１０９】
外部磁場係数ｈｉの計算はできるだけ高精度で行なうことが望ましい。一方、アニーリングマシン６００に実装できる外部磁場係数ｈｉのためのメモリの容量には制約がある。そこで、外部磁場係数ｈｉの計算には浮動小数点データを用いた浮動小数点演算を行い、その後整数データに変換した外部磁場係数ｈｉでアニーリング計算を行なう
データａ，λ，ｘｉは上位装置（サーバ）で計算されているので、浮動小数点型のデータとして送信されてくる。外部磁場係数更新回路６５０の外部磁場係数計算回路６５１は、ループ条件格納メモリ６３１と係数格納メモリ６３３から、浮動小数点型のデータａ，λ，ｘｉを読み出してｈｉを高精度で計算する。
【０１１０】
クリップ回路６５２は、計算結果のｈｉをアニーリング計算に影響ない範囲でクリッピングして値域を制限する。すなわち、前述のように例えば特許文献１に記載のアニーリングマシンでは、隣接スピンと相互作用係数Ｊｉｊの積、及び、外部磁場係数ｈｉを観察したときに、正の値と負の値のどちらが支配的か判断することでスピンの次状態を決定する。よって、この例では外部磁場係数ｈｉとして、隣接スピンの数（すなわちエッジの数）より大きな値を与えても結果は変わらないことになる。例えば、係数ｈｉの分解能は１０ビット、アニーリングマシンのグラフ構造を１スピン当たりのエッジ数８とし、Ｊi,j∈｛−１，１｝とすると、係数ｈｉは＋８〜−８でクリップしても精度劣化の問題を補償しつつデータ量を削減可能である。
【０１１１】
そこで、クリップ回路６５２では、係数ｈｉを＋８〜−８でクリップする。アニーリング計算に要求される分解能を１０ビットとした場合には、クリップした係数を定数倍回路６５３で６４倍し、型変換回路６５４で整数値とする。この結果、アニーリング計算に要求される１０ビットに合わせた整数値＋５１１〜−５１１で、アニーリング計算を実施することができる。このようにデータの型変換を行なうことで、メモリ量を節約しながら必要な精度で計算が可能である。
【実施例４】
【０１１２】
実施例１では、弱分類器を用いたアンサンブル学習一般に適用可能な実施例を説明した。実施例４では、アンサンブル学習のうちブースティングの手法を取り入れた例を説明する。
【０１１３】
公知のように、ブースティングは、逐次的に弱学習器を構築していくアンサンブル学習のアルゴリズムで、AdaBoost等が知られている。AdaBoostは、分類器の間違いに基づいて、それをフィードバックして、調整された次の分類器を作る手法である。訓練データＴに対して、弱分類器を、ｔ＝１からｔ＝ｔｍａｘ（ｔｍａｘは訓練データ（の集合）Ｔのサンプル数）まで順に適用していき、それぞれが正解したかどうかを判定していく。この際に、間違って分類されたサンプルに対する重みを重く調整したり、逆に正解したサンプルに対する重みを減らしたりしながら、調整を行なう。
【０１１４】
図１０は、ブースティングの手法を取り入れた実施例の情報処理システムによる処理の全体フローを示す図である。図４で示したフローにブースティング処理Ｓ９０００を追加したものであり、図４に示す処理と同じ処理には同じ符号を付して説明を省略する。処理Ｓ９０００内の制御装置による処理Ｓ３０００−ｎとアニーリングマシンによる処理Ｓ６０００−ｎは、基本的には既述の処理Ｓ３０００、処理Ｓ６０００と同様であるが、以下では相違点について主に説明する。
【０１１５】
電源投入、リセットの後、図４のフローと同様の処理を行ない、制御装置３００は処理Ｓ４１９でアニーリング（最適化）の結果のデータを読み出す。
【０１１６】
制御装置３００の弱分類器生成部３１０は、処理Ｓ９０１で、アニーリングマシン６００による最適化により選択された弱分類器ｃｉと検証誤差値ｅｒｒを保存する。次に、制御装置３００の弱分類器生成部３１０は、選択された弱分類器ｃｉについて、訓練データＴに対する分類結果ｃｉ（ｔ）を得、変数ｃｆ（ｔ）に代入する。また、ｅｒｒ  ｂｅｓｔを、変数ｅｒｒ  ｂｅｓｔ  ｏｌｄに代入する。
【０１１７】
弱分類器生成部３１０では、処理Ｓ９０２で訓練データｔの重み付け係数ｄを更新する。なお、重み付け係数ｄの初期値は、訓練データのサンプル数をｔｍａｘとすると、ｄ＝１／ｔｍａｘで全体の和が１になるように正規化してもよい。
【０１１８】
図１０の例では、処理Ｓ９０２で、ｙ（ｔ）は訓練データｔの分類結果の正解であり、ｗｆｏｐｔは処理Ｓ６０００で最適化された弱分類器の重みｗｆｏｐｔ∈｛０，＋１｝である。Σでは弱分類器の数Ｆだけ加算を行なう。ｃｆ（ｔ）−ｙ（ｔ）は正答の場合０になるので、誤答の多い訓練データｔに対する重みｄが重くなる。処理Ｓ９０２により、次の処理Ｓ３０００−ｎ内の処理Ｓ４１１−ｎでは、図４の処理Ｓ３０００内の処理Ｓ４１１では均等であった重み付け係数ｄは更新されることになる。
【０１１９】
重み付け係数ｄの更新後、図４の処理Ｓ３０００、処理Ｓ６０００と同様に、再度、制御装置３００による処理Ｓ３０００−ｎとアニーリングマシン６００による処理Ｓ６０００−ｎを行なう。このとき、間違った訓練データｔに対する重み付け係数ｄは、重くするように更新されている。制御装置３００による処理Ｓ３０００−ｎでは、重み付け更新された訓練データＴで、処理Ｓ４１２と同様に弱分類器を学習する。
【０１２０】
ブースティングでは、過去に得られている弱分類器および新しく得られた弱分類器の選択問題を、アニーリングマシンに設定する。このため、図１０の処理Ｓ３０００−ｎ内の処理Ｓ４１４−ｎ〜Ｓ４１５−ｎでは、過去に得られている弱分類器および新しく得られた弱分類器に対して、グラフ埋め込みを行なう。
【０１２１】
処理Ｓ６０００−ｎでは、埋め込まれたグラフに基づいて、外部磁場係数、相互作用係数、スピンを格納するメモリの内容を更新する。そして問題をアニーリングマシン６００で解き、この結果処理Ｓ４３１で得られた新たなｅｒｒ  ｂｅｓｔを、変数ｅｒｒ  ｂｅｓｔ  ｏｌｄと比較し、優れたｅｒｒ  ｂｅｓｔ  ｏｌｄが得られたら、処理Ｓ９０３で学習を終了する。得られない場合には、処理Ｓ９０１で結果を保存しつつ、処理Ｓ９０２で重み付け係数を更新して、処理Ｓ３０００−ｎと処理Ｓ６０００−ｎを繰り返す。
【０１２２】
ブースティングの処理Ｓ９０００は、任意の回数繰り返してもよい。検討によると、ブースティングによる最適化を繰り返すことで、弱分類器の個数が増えるとともに検証誤差は減少する。しかし、弱分類器の個数がある程度以上増えると、検証誤差が増加に転じるため、この検証誤差の増加傾向を検知して、ブースティング処理の終了を判断しても良い。以上の例によると、ブースティングの処理Ｓ９０００によって、前回の弱分類器の弱点を補う弱分類器が生成、選択される。
【０１２３】
上記の処理では、過去の最適化で選択された弱分類器の数と新しく得られた弱分類器の数の合計が、アニーリングマシンに搭載されているスピン数より小さい場合には、これらを纏めて処理できる。弱分類器の合計数がスピン数を上回る場合には、例えば、これまで選択されてきた弱分類器はプールしておき、新しく生成した弱分類器（個数はスピン数以下）のみでアニーリングをおこない、検証誤差評価は、最適化した分類器のｅｒｒ＋プールされたこれまでの弱分類器のｅｒｒで実施するというような手法が考えられる。
【０１２４】
図１１は、図１０において、処理Ｓ３０００−ｎの弱分類器の生成処理Ｓ４１２以降に追加する処理のフロー図である。制御装置３００側では弱分類器生成部３１０が実行するものとする。なお、図１１では、弱分類器の生成処理Ｓ４１２は重み付けｄを変更された訓練データで生成されるため、処理Ｓ４１２ｂと表記している。
【０１２５】
処理Ｓ４１２ｂでは重み付けを変更された訓練データＴで弱分類器ｃｉ（ν）を生成する。
【０１２６】
処理Ｓ４１３ｂでは、処理Ｓ４１２ｂで生成された弱分類器ｃｉ（ν）に対して、検証データＶで分類結果Δｍｉ（ν）を求める。この処理は、図５で説明した、図４の処理Ｓ４１３と同様に行なう。
【０１２７】
処理Ｓ１２０１では、過去の最適化Ｓ６０００で選択された弱分類器ｃｆ（ｔ）の検証マージンｍｏｌｄ（ν）を求める。過去２回以上の最適化が行なわれていれば、それら全ての結果である。ｍｏｌｄ（ν）の求め方は、図７で説明した、アニーリングマシン６００の検証誤差計算回路６６０のｍ（ν）を求める処理と同様である。このため、制御装置３００は、検証誤差計算回路６６０と等価な処理を行なう機能を備える。処理のために選択された弱分類器ｃｆ（ｔ）の重みｗｉは、処理Ｓ４３１を行なう際にアニーリングマシン６００から取得する。あるいは、別途アニーリングマシン６００が計算した検証マージンｍ（ν）を送信しておき、ｍｏｌｄ（ν）として記憶しておくように構成してもよい。
【０１２８】
処理Ｓ１２０３では、ｍｏｌｄ（ν）の絶対値に対して、値が小さい順にソートし、検証マージンｍｏｌｄ（ν）の絶対値がスピン数Ｎより小さくなる、ソートした後の最大のｍｏｌｄ（ν）のインデックスであるνｍａｘを求める。ゆえにνｍａｘはｍｏｌｄ（ν）の絶対値がスピン数Ｎより小さい検証データの個数と等しい。
【０１２９】
ブースティング処理により、弱分類器が増加することで、検証マージンの絶対値も増加する可能性があるため、ｍｏｌｄ（ν）を格納するのに必要なメモリ量が設計時に不明である。しかし、本処理を実施することで、検証マージンの最大数はＮ以下に制限されるので、必要なメモリ量を設計時に見積もることが可能となる。また、絶対値がＮ以上のｍｏｌｄ（ν）については、処理Ｓ１２０４により予めエラーの結果がわかるので、計算する必要がない。
【０１３０】
処理Ｓ１２０４では、ｍｏｌｄ（ν）≦−Ｎの検証データのサンプルの総和からｅｒｒを求める。上記条件で抽出された検証データは、次の最適化の結果に関わらずエラーであるという結果（ｅｒｒ＝１）が変わらないため、予めエラーとして処理することで、計算量を削減することができる。
【０１３１】
処理Ｓ４１６ｂでは、データをアニーリングマシン６００に送信する。
【０１３２】
アニーリングマシン６００側では、処理Ｓ４２１ｂで分類結果に関するパラメータΔｍｉ（ν），ｍｏｌｄ（ν），νｍａｘ，ｅｒｒを分類結果格納メモリ６３４に格納する。その後、最適化計算の処理Ｓ６０００−ｎを実行する。
【０１３３】
図１２は、ブースティングにおいて検証誤差計算を合理化する手法の概念図である。横軸に検証データＶのインデックスνを、縦軸に過去に選択された弱分類器の検証マージンｍｏｌｄ（ν）を示している。ｍｏｌｄ（ν）がスピン数Ｎ以上の場合には、その次の最適化計算において、たとえ全ての弱分類器が選択され、それらの分類結果が誤答を出しても、多数決による検証誤差の結果は変わらないので、エラー判定は誤差なし（ｅｒｒ＝０）として差し支えなく、これ以上検証誤差の計算は必要ないと考えられる。また、ｍｏｌｄ（ν）が−Ｎ以下の場合には、その次の最適化計算において、たとえ全ての弱分類器が選択され、それらの分類結果が正答を出しても、エラー判定の結果（ｅｒｒ＝１）は変わらないので、これ以上検証誤差の計算は必要ないと考えられる。そうすると、検証誤差の計算が必要になる領域は図１２中斜線を施した部分と考えられる。
図１３は、検証誤差計算回路６６０で行なわれる検証誤差計算Ｓ４２９のフロー図である。なお、このフローにおいては、処理Ｓ１２０３でソートされた検証データＶの順番を、ループパラメータｎに代入している。
【０１３４】
処理Ｓ１３０１では、検証データサンプルのインデックスｎをνｍａｘと比較する。νｍａｘは検証マージンの絶対値がＮ以下のサンプル数に等しい。
【０１３５】
処理Ｓ１３０２では、インデックスｎがνｍａｘより小さい場合、変数ｔｍｐを初期値０に設定する。変数ｔｍｐは各検証データサンプルｎごとの検証マージンを計算するのに使用する。
【０１３６】
処理Ｓ１３０３では、弱分類器のインデックスｉをスピン数Ｎと比較する。すなわち、図１３の処理では、過去に選択された弱分類器の数が多くても、Ｎ個までを処理するものとする。
【０１３７】
処理Ｓ１３０４では、インデックスｉがＮ以下の場合、変数ｔｍｐにΔｍ［ｎ，ｉ］・ｗｉｏｐｔ［ｉ］を加算する。これは、図７の検証マージンの計算処理に対応する。
【０１３８】
処理Ｓ１３０５では、変数ｔｍｐ＋ｍｏｌｄ［ｎ］≦０かどうかを判定する。これは、今回の最適化による検証マージンｔｍｐと過去の最適化による検証マージンｍｏｌｄ［ｎ］とを総合した、エラー有無の判定処理である。検証マージンが０以下であれば
処理Ｓ１３０６では、処理Ｓ１３０５でｔｍｐ＋ｍｏｌｄ［ｎ］≦０であれば、ｅｒｒに１を加算し、ループ処理が終了するまでｅｒｒ値をインクリメントする。
【０１３９】
処理Ｓ１３０５でｔｍｐ＋ｍｏｌｄ［ｎ］≦０でなければ、処理Ｓ１３０３に戻りｉをインクリメントする。処理Ｓ１３０３でインデックスｉがＮより大きい場合、処理Ｓ１３０１に戻り、検証データのインデックスｎをインクリメントする。
【０１４０】
後半のＳ１３０３〜Ｓ１３０５のループ処理は、検証データｎに対して、スピン数Ｎまで弱分類器iの検証結果を加算し、検証マージン（変数ｔｍｐ）を算出するものとなる。
【０１４１】
なお、検証誤差の計算の一例は（数式７）による。
【０１４２】
図１４は図１１〜図１３で説明した、ブースティングの検証誤差計算に関する考え方を説明する概念図である。ここでは簡略化のため５スピンが実装されているものとし、過去２回の最適化が行なわれ、３回目の最適化計算後に行なわれる処理とする。
【０１４３】
図１４において、データ１４０１は１回目の最適化で選択された弱分類器の分類結果であり、データ１４０２は２回目の最適化で選択された弱分類器の分類結果である。図１１の処理Ｓ１２０１では、制御装置３００がデータ１４０１，１４０２からｍｏｌｄ（ν）を求め、処理Ｓ４１６ｂでアニーリングマシン６００に送る。このとき、検証マージンｍｏｌｄ（ν）の絶対値がスピン数Ｎ（この例では５）以上のデータ１４０３、１４０４の検証データサンプルについては、その後の計算から除外することができる。なぜならば、過去の最適化によって選択された弱分類器の検証マージンがスピン数（＝最適化される弱分類器の個数）以上の場合、最適化によって３回目に新たに選択された弱分類器によって、多数決の結果は変わらないためである。
【０１４４】
また、検証マージンｍｏｌｄ（ν）の絶対値がスピン数Ｎ以上で、かつマイナスの値であるデータ１４０４の検証データサンプルについては、３回目の最適化計算結果にかかわらず既にエラーが確定しているので、その数は処理Ｓ１２０４で「ｅｒｒ＝１」としてカウントする。この値も処理Ｓ４１６ｂでアニーリングマシン６００に送られる。
【０１４５】
一方、データ１４０６は、処理Ｓ４１２ｂで新たに作成された弱分類器の分類結果Δｍｉ（ν）であり、処理Ｓ４１３ｂで計算され、処理Ｓ４１６ｂでアニーリングマシン６００に送られる。
【０１４６】
アニーリングマシン６００側では、新たに作成された弱分類器の最適化を行ない、選択結果であるスピン値１４０７を得る。図７と同様に分類結果Δｍｉ（ν）とスピン値ｗｉから検証マージンｍ（ν）を得る。そして、過去の最適化結果から得られた検証マージンｍｏｌｄ（ν）のうち、意味のある部分（検証マージンの絶対値がＮより小さいもの）と加算を行いエラー値１４０８を求める。このエラー値１４０８と確定済みのエラー値１４０５を加算したものが、最終的なエラー値１４０９となる。
【０１４７】
【数７】
2020009301.tif 000009
【実施例５】
【０１４８】
上述の実施例ではアニーリングマシンに対してone−to−oneグラフ埋め込みを行なっているが、完全型グラフ埋め込みを行なってもよい。完全型グラフ埋め込みを行なう場合には、ダンピングパラメータａを固定することができる。完全型グラフ埋め込みでは、アニーリングマシンのハードウェア（ノード数）を十分に活用できなくなるが、パラメータａを変更する必要がなくなる。この場合、図４のフローで、パラメータａの変更を省略し、λの変更のみ行なえばよい。λの変更により外部磁場ｈｉが調整されることになる。
【０１４９】
図１５は本実施例の全体フロー図である。実施例１の変形例として説明し、図４のフローと同じ構成には同じ符号を付して説明を省略している。相違点として、処理Ｓ４１５ａにおいて、完全型グラフ埋め込みを行なう。アニーリング条件としてはパラメータａは一定値（定数）として、処理Ｓ４２１ａでアニーリング条件格納メモリ６３２に格納する。図４のフローと比較してパラメータａを変更するループが消失しており、外部磁場係数を計算する処理Ｓ４２６ａではａを定数として、ｈｉ＝ａ（ｘｉ−λ（ｌ））を計算する。
【実施例６】
【０１５０】
実施例１の変形例として、さらに処理を高速にできる例を示す。全てのスピンｓi(i=１,・・・Ｎ）に関して以下（数式８）の関係を満たす場合、そもそもスピンの最適化ができない。すなわち、隣接スピンの値に関わらず、自スピンの値が固定される。そのためアニーリング計算を行なう必要がない。
【０１５１】
【数８】
2020009301.tif 000010
【０１５２】
このため、上記の関係を満たすパラメータ空間を事前に調べることで、ループ処理の回数を減らし処理の高速化が可能である。また、上記の関係を満たすスピン数が比較的に多い領域については、解空間全体の最適解を見つける上であまり重要でない領域と想定される。このため、この領域に関しては、アニーリングの回数やアニーリングの温度スケジュールを粗にすることで、高速化することができる。
【０１５３】
この領域については、図３、図４の実施例の制御装置３００において、処理Ｓ４１４で（数式７）の計算を行ない、結果を反映したアニーリング条件を作成し、処理Ｓ４１６でアニーリングマシンに送信し、アニーリング条件格納メモリ６３２に格納することで対応できる。アニーリング条件によって、具体的には、特定範囲のａやλをスキップして処理Ｓ６０００のループ処理を実行することになる。あるいは特定範囲のａやλを実行するが、アニーリング条件を変更して、処理Ｓ６０００のループ処理を実行することになる。
【実施例７】
【０１５４】
上記の各実施例において、高精度の結果を得られる、係数の好ましいビット数設定について説明する。
【０１５５】
図１６Ａは、分類器の相関を表す相互作用係数ｊｉｊの分布を示すグラフ図である。学習サンプル数が増えるとｊｉｊの離散化が進むが、離散化に伴う精度劣化を抑えるには、相互作用係数の分解能は少なくとも、ばらつき（２σ）すなわち９５％をカバーする範囲と同等なオーダであることが望ましい。
【０１５６】
図１６Ｂは、上の思想に基づいて、横軸に相互作用係数ｊｉｊのビット数を示し、縦軸に許容可能な学習サンプル数を示したグラフ図である。学習サンプル数を増やすことは、弱分類器の学習上好ましいが、必要な相互作用係数のビット数も指数関数的に増加する。たとえば、サンプル数として２００００程度を想定すると、必要な相互作用係数ｊｉｊのビット数は７ビットとなる。
【０１５７】
図１６Ｃは、あるスピンに対する相互作用係数ｊｉｊと外部磁場係数ｈｉの関係を示す模式図である。中央のインデックス５のスピンに対して、インデックス１〜４、６〜９の８個のスピンが隣接スピンとなる。この図では、スピンの値は弱分類器の重みｗに換算しており、ｗは１または０の値をとる。ここで、外部磁場ｈｉの値は、相互作用係数との計算を常に可能とするためには、周囲の相互作用係数の総和よりも大きくする必要がある。このため、相互作用係数のビット数に加えて、エッジ数に相当するビット数（この場合、エッジ数８＝３ビット）が更に必要となる。すなわち、サンプル数として１０４〜１０５程度を想定すると、必要な相互作用係数のビット数は７＋３＝１０ビットとなる。よって、これらを考慮して係数を格納するメモリセルのビット数を設定する。
【０１５８】
本発明は上記した実施形態に限定されるものではなく、様々な変形例が含まれる。例えば、ある実施例の構成の一部を他の実施例の構成に置き換えることが可能であり、また、ある実施例の構成に他の実施例の構成を加えることが可能である。また、各実施例の構成の一部について、他の実施例の構成の追加・削除・置換をすることが可能である。
【符号の説明】
【０１５９】
制御装置３００、アニーリングマシン６００、アニーリング計算回路６４０、外部磁場係数更新回路６５０、検証誤差計算回路６６０
【図１】
2020009301.tif 000012
【図２Ａ】
2020009301.tif 000013
【図２Ｂ】
2020009301.tif 000014
【図３Ａ】
2020009301.tif 000015
【図３Ｂ】
2020009301.tif 000016
【図４】
2020009301.tif 000017
【図５】
2020009301.tif 000018
【図６】
2020009301.tif 000019
【図７】
2020009301.tif 000020
【図８】
2020009301.tif 000021
【図９】
2020009301.tif 000022
【図１０】
2020009301.tif 000023
【図１１】
2020009301.tif 000024
【図１２】
2020009301.tif 000025
【図１３】
2020009301.tif 000026
【図１４】
2020009301.tif 000027
【図１５】
2020009301.tif 000028
【図１６Ａ】
2020009301.tif 000029
【図１６Ｂ】
2020009301.tif 000030
【図１６Ｃ】
2020009301.tif 000031