１． 発表者：
ティモシー ルル（東京大学 生産技術研究所）
山本 喜久（科学技術振興機構）
ピーター マクマホン （スタンフォード大学）
合原 一幸（東京大学 生産技術研究所 ニューロインテリジェンス国際研究機構）
２． 発表のポイント：
◆創薬、自動運転、機械学習、新材料、集積回路など、社会のいたるところに存在する「組合せ最適化」問題を解くための新しいアナログニューラルネットワークを提案した。
◆従来のアナログニューラルネットワークでは、通常、局所最適解にトラップされるため最適解は求まらないが、本提案手法では、各ニューロンのアナログスピンの振幅不均一性を補正する誤差変数を導入し、局所最適解を不安定化することでトラップを防いだ。
◆本提案手法は、様々な組合せ最適化問題へと拡張することができ、実問題の組合せ最適化を促進することが期待される。また、Field programmable gate arrays（FPGA）回路や光電子システムなどでハードウェア実装することによって、さらなる高速性を実現できる可能性がある。
３．発表概要：
膨大な数の離散的な組合せから最適な解を得る計算問題を「組合せ最適化」問題という。組合せ最適化問題は、創薬、自動運転、機械学習、新材料、集積回路など、社会のいたるところに存在し、効率的に解決することが求められている。他方で、ムーアの法則の減速によって示唆されるように、従来の古典的デジタル計算技術の発展速度が飽和し始めており、それに代わる新しい計算システムの必要性が高まってきている。
東京大学 生産技術研究所のティモシー ルル 特任助教らは、科学技術振興機構およびスタンフォード大学と共同で、制約なし二値変数二次計画問題（quadratic unconstrained binaryoptimization problems: QUBO）と呼ばれる組合せ最適化問題のクラスを解くための新しいアナログニューラルネットワークを用いた計算方式を提案した。現実世界の多くの問題が、組合せ最適化問題にマッピングできる。本提案手法は、今後様々な分野における組合せ最適化を促進することが期待される。また、Field programmable gate arrays（FPGA）や光電子システムなどでハードウェア実装することによって、さらなる高速性を実現できる可能性がある。
本研究成果は、2019年2月1日にフィジカル・レビュー・レターズ誌（Physical Review Letters）のオンライン版で公開される。
４．発表内容：
【背景】
膨大な数の離散的な組合せから最適な解を得ることを必要とする計算問題は、「組合せ最適化」問題としてよく知られ、コンピュータアルゴリズム分野で何十年もの間、研究されてきている。中でも、問題のサイズが大きくなりすぎると、スーパーコンピュータでも効率的に解決できないクラスの問題（NP-困難と呼ばれる）があることはよく知られ、これらの問題が、創薬、自動運転、機械学習、新材料開発、集積回路、さらには物流、ポートフォリオなど社会に遍在している。これらの組合せ最適化問題の解決は社会にとって非常に重要であり、組合せ最適化問題をターゲットにした新しいタイプの計算システムの開発が、近年活発に行われている。
【内容】
本研究は、制約なし二値変数二次計画問題（quadratic unconstrained binary optimization problems: QUBO）と呼ばれる組合せ最適化問題を対象にして研究したものである。
組み合わせ最適化は、たくさんの離散的な組合せの中から最適な解を見つける問題である。解はスピンと呼ばれる2値（+1または-1）の変数のセットによって符号化される。所与の問題に対して、最適な（例えば、+1、-1、+1、-1、-1 などの）2値スピンの特定の配列がある。本提案手法は、2値スピンのアナログ変数への緩和に基づいている。つまり、各スピンは、2値ではなく -1 から+1 の間の任意の実数値をとることができる。このような緩和は、Hopfield-Tank ニューラルネットワークのように以前から提案されているが、通常、局所最適解にトラップされるため最適解は求まらない。
本研究では、局所最適解でのトラップの問題を回避するために、組合せ可変最適化問題をアナログ空間へマッピングして最適解を求めるための新しいアナログニューラルネットワークを提案した。従来のアナログニューラルネットワークの問題点の1 つは、計算中にアナログスピンの振幅が不均一になることであった。そこで、振幅の不均一性を補正する誤差変数を追加することによって、局所最適解を不安定化してそこへのトラップを避けるダイナミクスを考案した。さらに、システムが最適な解を見つけるのを妨げるような振動解やカオス解の発生を防ぐ、新しい方法も開発した。振動解やカオス解へのトラップは、システムに供給されるエネルギー量が散逸されるエネルギー量よりも大きい、利得支配型ダイナミクスになるようにシステムを構築することによって防止することができる。
【効果】
組合せ最適化問題のリファレンスベンチマークセットを使用して、本提案手法を最先端のヒューリスティック手法と比較した。本提案手法は、最先端のヒューリスティック手法と同程度、または場合によってはさらに良好な性能を示した。さらに、本提案手法をField programmable gate arrays（FPGA）や光電子システムなどのハードウェア上で実装することによって、さらなる高速性が実現される可能性がある。本提案手法は、今後様々な人工知能関連タスクを解決するための組合せ最適化手法の品質と速度を向上させることが期待される。
５．発表雑誌：
雑誌名：「Physical Review Letters」（PRL: フィジカル・レビュー・レターズ誌）（2月1日（金）にオンライン版で公開）
論文タイトル： Destabilization of local minima in analog spin systems by correction of amplitude heterogeneity
著者： Timothée Leleu*, Yoshihisa Yamamoto, Peter L. McMahon, and Kazuyuki Aihara（*：責任著者）
６．問い合わせ先：
東京大学 生産技術研究所
特任助教 Timothée Leleu（ティモシー ルル）
東京大学 生産技術研究所
教授 合原 一幸（あいはら かずゆき）
研究室URL：https://www.sat.t.u-tokyo.ac.jp/
