はじめに
本記事はJijにてインターンとして勤務してくださっている方が中心となって書いた記事です。
概要
組合せ最適化問題のような難しいとされる問題が与えられたとき、その問題を(近似的にでも)解く手法の開発は言うまでもありませんが非常に重要です。そしてその開発において、それが他と比べてどれくらい優れているのかを把握しておく必要があります。しかし一般に異なるアルゴリズムの性能を比べることは簡単ではありません。分からない問題があるから様々な手法が開発されるのであって、例えば与えられた問題の「真の値」からどれくらい近いかを知ることは一般には不可能だからです。また、答えがあらかじめ分かっている問題を解かせて性能を測ろうとしても、多くの場合その問題は簡単に解けてしまい、差が見えにくくなってしまうこともあり得ます。 従って、真の値は知っているが、解くことは難しい問題を作る必要があり、この記事で紹介するWishart Planted Ensemble (WPE)はイジングモデルにおいてまさにそのような問題を生成する手法の一つとなっているため、アニーリングアルゴリズムのベンチマークとして用いることが可能です。
原論文はこちら (https://arxiv.org/abs/1906.00275)にありますので、この記事を閲覧頂いた上でより詳細な内容を知りたい方は参照してみるといいでしょう。
追記 (2020/10/12)
この記事を見つけてくださった原論文の著者であるFiras HamzeさんとHelmut Katzgraberさんからメールで連絡があり、この話を二体相互作用から一般の相互作用に拡張した話 (https://arxiv.org/abs/2005.14344)がアップデートとしてあり、
$ pip install chook
でインストールできるとのことなので、是非試してみてください。
問題設定
概要で述べたことをもう少し具体的に定式化してみましょう。
古典スピン系(自由度がの系)を考え、スピンの総数は
とします。系の次元は任意です。この系に対してplanted solution, すなわち基底状態をこちらで設定したとして、これを
とします。例えば強磁性解
や反強磁性解
が考えられるでしょう。しかし解がこれらのようにオーダーしている必要はなく、任意のスピン配置で構いません。Planted solutionが与えられたとき、それを基底状態にもつようなハミルトニアン
を生成することが目標です。またイジングモデルの時間反転対称性(でハミルトニアンが不変)より、
を解くと
も基底状態となることが分かります。
WPEの構築
まず次のような関数を考えます。
これまでの議論からこのハミルトニアンがを基底状態に持つことが分かります。
従って、任意のスピン配置
について、
となるような行列
を定義できればハミルトニアンがうまく定義されることが分かりました。次にそのような行列をどのように見つけてくるかを考えましょう。これは
と直交するような
を
個見つける問題と等価です。イジングモデルでの変数は
であること、すなわち
であることを使うと、実は簡単に探すことが出来ます。次の行列を定義します。
明らかに対称行列でかつであることが分かります。この性質を利用すると次のようにして
を生成できます。まず
を取ってきます。すなわち各成分独立に正規分布からランダムに実数を選びます。そうすれば
で
が定義できます。
の性質から、直交性は明らかでしょう。
ここで定義されたベクトルは
、すなわち平均がゼロで共分散行列が
であるような正規分布に従っています。一般にこのような分布をWishart分布と呼び、WPEの名前の由来となっています。
なお、以下のpythonコードでハミルトニアンを辞書型で生成できます。
import numpy as np def wpe_interaction(solution, M): n = len(solution) sol_arr = [solution] tmp_mat = 1 / n * np.dot(np.transpose(sol_arr), sol_arr) sigma_mat = np.sqrt(n / (n - 1)) * (np.identity(n) - tmp_mat) int_mat = [] for i in range(M): int_mat.append(np.dot(sigma_mat, np.random.randn(n))) int_mat = 1 / n * np.dot(np.transpose(int_mat), int_mat) int_dict = {(i, j): int_mat[i, j] for i in range(n) for j in range(n)} for i in range(n): key = (i, i) int_dict.pop(key) return int_dict
問題の難しさ
これまでの議論から、実際に任意のスピン配置を基底状態に持つイジングモデルが生成できることが分かりました。しかしこのようにして出来た問題が「使える」ためには、簡単に解けてはいけません。そこでここでは問題がどれくらい難しいのかを考えましょう。
直感的な議論
いきなり数学の問題として議論する前に、直感的にどのようなとき問題が難しくなるのかのイメージをつかんでおきましょう。上のように構成されたイジングモデルの基底状態探索は、言い換えると次の問題を解いていることになります:
与えられた行列に対して、
明らかにこの問題の難しさは列ベクトルの数、すなわち
に依存することが分かるでしょう。そこで、
を変えたときに問題の難しさはどのようになるかを考えましょう。
まずスピン配置などとは考えず(すなわち
の成分が
だけであることを忘れて)、純粋に線形代数の問題として考えてみましょう。その際解空間
の大きさは
となっていることが分かります。ここではとりあえず
の場合を考えています。従って、
が小さいとき、例えば
の時は解空間が非常に大きくなることが分かります。解空間が大きいと基底状態探索は難しくなり、特に
の時に最も問題が難しくなりそうですが、実は実機のコンピューター上でWPEを作るうえではそうはなりません。これはコンピュータが完全な実数を実装できないことが原因で、実際には小数点以下どこかで打ち切らないといけませんが、その丸めこみによって多くの状態が基底状態に「見えて」しまいます。すなわち実際の基底状態とは異なる状態のエネルギーと基底状態のエネルギーの差が非常に小さくなってしまうのです。従って実は
が小さいときに基底状態(誤差を許してエネルギー最小となる状態の意味で、厳密な基底状態ではない)を探すことはそこまで難しくありません。
その逆のが大きい場合を考えましょう。ここで特に
を仮定することをしません。相互作用に定数を加えた
は次のように書けます。
ここでの議論から、
が小さいときは低エネルギー状態を探すことは丸め誤差によって簡単になる
が大きいときは大数の法則から基底状態探索が簡単になる
ことが分かります。従って、エネルギー最小状態を探すという意味ではが小さすぎもせず、大きすぎもしない場合に問題が一番難しくなると考えられます。
定量的な考察
ここでは上の議論をもう少し定量的にしていきたいと思います。ふつうは系が与えられたときに基底状態を知ることが目標なので、ランダムにスピン配置を決めたとき、その状態のエネルギーがとなる確率
を考えます。簡単のため、基底状態のエネルギーがゼロになるようにしましょう。これはWPEで生成するイジングモデルの相互作用を
ではなく、
に取ることに対応しますが、エネルギー値の定数のシフトなので本質的には変わりません。詳しい導出はここでは省くことにして、
は次のような結果になります。

となります。
次に解を探すためにはどれくらいの状態を探せばよいのでしょうか。ですが、これは線形代数の問題のときでイジングスピンの時は一般にどうなるのか自明ではありません。しかし、(ここでも導出は省きますが) 実はイジングスピンの時でも
個の状態を探せばよいことが示せます。スピン反転対称性を鑑みると
個の状態を調べればよいことになります。
ここでランダムに個の状態から選んでいき、その状態のエネルギーを調べることを考えます。何回目の試行で基底状態を選べるかを表す指標を
とかくと、
になります。ここで丸め誤差を考慮して
と定義しなおすと、次のような定量的に問題の難しさを測る指標を得ることが出来ます。
基底状態を得るのに必要な試行数がであるため、
が大きくなればなるほど、つまり問題が難しくなればなるほど上の指標は小さい値となる仕組みです。
この量を
と定義して
を変えた際にどの程度
が小さくなるかを見ていきましょう。
一番問題が難しくなるとは、言い換えると
が最小になるような
を考えていることになります。また各
について問題が一番難しくなる
を調べていくと次のような線形の関係にあることが示唆されています。
(以下は論文の内容ではなく筆者の考えになります)
では具体的にはどれくらいの値なのでしょうか?以下のグラフがそのプロットになります。
ここから分かることは、一般には
のときに非常に小さくなり得るということです。従って例えばWPEを使ってベンチマークを取ったりする際には、
を最小化するような
を選んでしまうと、ほとんどの場合正しい解にはたどり着きません。また、論文での議論から明らかなように
を増やすほど問題は簡単になっていきますが、
の場合には
は定義は出来ますが、この量の意味を与えることが難しくなります。従って、とても実務的な観点からは、
の際にうまく意味づけが出来ないという点からも実は
の概念はそこまで便利なものではなく、
の時の考察が必要になってくるといえるでしょう。
実際に実装した結果
ここでは実際にWPEからイジングハミルトニアンを生成して、それをopenjijで解いた結果を載せます。
上の図はで、上から順に
の場合に1000回WPEからハミルトニアンを生成し、それをアニーリングで解いた時のエネルギーヒストグラムになります。またここでplanted solutionは強磁性解としています。ここから分かるように
が小さいときは低エネルギー状態が多く、
が大きいときは正しい解が出て来ています。
それではで動かした際にどれほど基底状態に近いエネルギーを持つ解を出す回数が増えるかを見てみましょう。
が小さいときは上の議論にあるような縮退が原因で回数が増えますが、
が増大するとともに縮退が減って、その分基底状態に近いようなエネルギーを持つスピン配置にはたどり着けなくなっていきます。そして
くらいからようやく低エネルギー状態が増え(これは基底状態そのものと考えることが出来ます。)、
では、おおよそ5%の割合で基底状態が求められていることになります。
上の結果はすべて強磁性解をplantした際の結果ですが、強磁性解以外だとどうなるでしょうか?次にネール状態(反強磁性解)の場合を見てみましょう。
上のプロットから分かるように、反強磁性解でもおおよそ強磁性解と同じような分布になります。
それではで動かした際にどれほど基底状態に近いエネルギーを持つ解を出す回数が増えるかを見てみましょう。
基底状態が正しく求まる確率の
依存性も強磁性解とほぼ同じになります。
上の2つの例は基底状態がオーダーしている場合での結果でしたが、オーダーしていない場合はどのようになるでしょうか。基底状態をランダムに与えた場合は次のようになります。
ほぼ秩序相と同じ振る舞いですが、のときはエネルギーが少し広めに分布しています。正しい解を出す確率は次のようになります。
従ってWPEで生成された問題は基底状態が秩序相か無秩序相かに関わらず、似たような性質を持つことが分かります。
統計力学的な議論
WPEで生成された系の振る舞いを物理サイドから考察してみましょう。
TAP自由エネルギー
WPEの親戚にあたるSKモデルなどのスピングラスで良く考察される系を解析するときには、平均場方程式を拡張したTAP方程式と呼ばれる方程式を解いて系の大まかなふるまいを理解することがあります。ここでもWPEに対応するTAP方程式及びTAP自由エネルギーを解析することでこの系のふるまいを考えたいと思います。詳しい導出はしませんが、WPEで与えられた系に対するTAP自由エネルギーは次のように表すことが出来ます。
ここで
は逆温度、
で定義されています。また
はスピン
にたいするエントロピーで
この表式の第一項はでスケールするため、熱力学極限 (
)を考える上では無視して構いません。従って次の自由エネルギー密度を考えれよいかもしれません。ばよいことが分かります。
このエネルギー密度をプロットすると次のようになります。
明らかに一次転移している様子が見て取れます。
系の安定性
自由エネルギーの様子から、高温相ではがエネルギーが最も低く、低温相では
が有限の時にエネルギーが最小になることが分かりますが、それに加えて、ある温度では
が準安定になることも見て取れます。これは1次転移の特徴の一つで、この場合は系の安定性を調べる必要があります。(細かいことをいうと準安定な相が出てくるには必ずしも1次転移である必要はありません。)そこで
の状態が不安定になるときの温度を調べましょう。これは自由エネルギーのヘッセ行列を見ることと等価です。
従っての時は
まとめ
本記事では真の解から解くことが難しい問題を生成する手法である Wishart Planted Ensemble と呼ばれる手法を紹介し、定量的、統計力学的な議論を行いました。 生成される問題の難しさも制御できるため、アニーリング等で用いられる提案手法のベンチマークとして極めて有効だと思われます。 記事中に問題を生成するためのPythonコードも用意したので、興味のある方は試してみるとよいかもしれません。