共同利用

イジングモデルに対するSimulated Annealingの解析


種別 短期共同研究
研究計画題目 イジングモデルに対するSimulated Annealingの解析
研究代表者 大輪拓也(国立情報学研究所 ビッグデータ数理国際研究センター・特任研究員)
研究実施期間 平成27年8月27日(木)~ 平成27年8月31日(月)
研究分野のキーワード ising model, simulated annealing, glauber dynamics, mixing time, cut-off phenomenon
目的と期待される成果 カナダのベンチャー企業であるD-Wave Systems社が開発した計算機が、GoogleとNASAによって2013年に設立された「量子人工知能研究所」へ導入された事は記憶に新しい。この計算機は最適化問題を解く事に特化したものであり、機械学習や人工知能への応用が期待されている。実際に最適化問題を解く際には、最適化問題をイジングモデルに帰着させて最適解を得る方法を採用している。一般に、ある種の最適化問題はイジングモデルに変換できる事が知られており、変換されたイジングモデルを解くためにはアルゴリズムが必要となる。代表的なアルゴリズムにQuantum Annealing とSimulated Annealing(SA)があり、前者は後者より速いアルゴリズムとして注目されているが、実現可能性の問題は未解決である。一方、SAはアルゴリズムがシンプルであり汎用性が高いため、効率的に実装すれば上記のような計算機が広く実現可能となる。そこで本研究では、イジングモデルをSAで解くための効率的なアルゴリズムを得る事を目標とする。主な課題の一つはSA内で使われるループの回数を決める事であり、数学的にはSAの定めるマルコフ連鎖のmixing timeに対応する。Mixing timeについて相転移のような臨界現象が観察される例が知られており、それはcut-off現象と呼ばれている。SAのmixingに対するcut-off現象の詳細な解析に成功すれば、SAの実装だけでなく数学的な貢献も大きいため、これを具体的な研究課題の一つとして考えている。また、その他の課題の解決のためには確率論以外の数学や計算機シミュレーションなども必要なため、課題の整理や問題提起も重視する。
組織委員(研究集会)
参加者(短期共同利用)
久保田直樹(日本大学理工学部理工学研究所・研究員)
大輪拓也(国立情報学研究所・特任研究員)
吉村地尋(日立製作所中央研究所・研究員)
奥山拓哉(日立製作所中央研究所・研究員)
白井朋之(九州大学IMI・教授)
竹居正登(横浜国立大学・准教授)
樋口雄介(昭和大学・講師)