こんにちは! メルカリ量子アニーリングインターン @shitian-ni です。
2018/09/13 ~ 14 に開催された GPU Technology Conference Japan で "Performance comparison on CFRBM between GPU and Quantum Annealing" についてポスター発表をしてきました。
このポスターの話を今回のブログで紹介したいと思います。

ポスターファイル: https://github.com/mercari/CFQIRBM/blob/master/doc/QRBM_vs_GPU_Poster.pdf

背景

筑波大学大学院と野村アセットマネジメント株式会社が2018年度人工知能学会全国大会で発表した論文"半教師学習と特異値分解によるCold-Start問題へのアプローチ"とSeth Lloyd教授が慶應義塾大学で講演した話”量子コンピューターは特異値分解を解ける”をもとに、量子アニーラーD-Waveでメルカリの推薦システムを拡張、改善できると思いました。つまり、特異値分解による協調フィルタリングを量子アニーリングで実現しようとしました。
ですがその後、特異値分解を解けるのはゲート式量子コンピュータであり、量子アニーラーであるD-Waveではまだ解けないことが分かりました。
特異値分解は解けないですが、特異値分解よりさらにいい精度を出せるRestricted Boltzmann Machine (RBM)による協調フィルタリング[出典] なら量子アニーリングで実現できることが分かりました。

RBMはニューラルネットワークの一種です。既存の実装手法はマトリックス演算を使いました。
それで、マトリックス演算のGPU高速化とRBMサンプリングのD-Wave量子アニーリング実装について、パフォーマンス比較をしてみました。

RBMに関する詳しい話については今回公開したポスターやWikipediaを参照していただきたいと思います。
要するに、RBMを利用するにはRBMのエネルギー式に関してサンプリングをする必要があります。
RBMの学習には1 Epochにつき3回のサンプリングが必要です。
推論する時には2回のサンプリングが必要です。
サンプリング計算について、既存CPU/GPUの解法ではマトリックス演算をすることに対し、D-Waveでは量子アニーリングで直接サンプルを取ることができます。
サンプリング精度と計算時間について比較することになります。

量子アニーリングによるRBM

D-Waveで動く量子アニーリングはイジングモデルを解くことで精度保証なし近似解を得られます。

begin{gather}
H(sigma)=-sum{i,j}J{ij}sigma_isigmaj – musum{j} sigma_j
end{gather}
begin{gather}
sigma_i in { -1, +1 }
end{gather}

イジングモデルに関する論文がNIPS 2017で2本も採択されたので、注目度の高さがよくわかりますね。
http://papers.nips.cc/paper/6607-concentration-of-multilinear-functions-of-the-ising-model-with-applications-to-network-data
http://papers.nips.cc/paper/6674-a-screening-rule-for-l1-regularized-ising-model-estimation
イジングモデルは変数がバイナリーのQUBO(Quadratic Unconstrained Binary Optimization)に等価変換できます。
RBMのvisible unitとhidden unitを合わせて変数と呼ぶと、RBMのエネルギー式はQUBOと同じ形になります。
よって、量子アニーリングでRBMのサンプリング部分を実装することは可能になります。

GPU / CPUによるRBM

サンプリング計算をマトリックス演算、ベルヌーイ分布とシグモイド関数で近似します。

def sample_bernoulli(probs):
return tf.nn.relu(tf.sign(probs - tf.random_uniform(tf.shape(probs))))
hidden_p = tf.nn.sigmoid(tf.matmul(self.x, self.w) + self.hidden_bias)
visible_recon_p = tf.nn.sigmoid(tf.matmul(sample_bernoulli(hidden_p), tf.transpose(self.w)) + self.visible_bias)
hidden_recon_p = tf.nn.sigmoid(tf.matmul(visible_recon_p, self.w) + self.hidden_bias)

TensorFlowのCPU / GPUバージョンでそれぞれパフォーマンスを評価します。

協調フィルタリング

ユーザーからもらった別々のデータが協力して一つの推薦モデルを学習して、推薦時に全部の商品からフィルタリングをして関連商品だけを出します。
Amazonの推薦システムの動作原理です。

RBMにおける(v’)再構築の段階で、visible unitの一部を重み拡大などで入力に固定したら、予測値として定義した他の固定されていないvisible unitのサンプルを出力として得られます。
この性質を利用して、RBMも協調フィルタリングを実現できます。 詳しい話に関しては、ポスターや論文を参照してください。

実験

一つのCFRBMは複数の小さいRBMの組み合わせで構成されます。今回は６x６格子模様画像の再構築について評価をしました。

モデル学習時、D-Waveは 3 Epoch かけて元の入力をようやく再構築できましたが、既存TensorFlowの場合は 1 Epoch だけで再構築できます。

乱数入力による学習入力再構築も、既存TensorFlow CPU/GPUの手法ではAccuracy 100%に対し、量子アニーリングはいくつか間違いをしました。

ですが、一回のサンプリング時間について、量子アニーリングの場合かかる時間 (D-Waveのqpu_sampling_time) はCPU/GPUよりダントツに速いことがわかります。
よって、サンプリング時間の合計 (totalunderline{ }samplingunderline{ }time) で考えると量子アニーリングの方が速いです。
begin{equation} totalunderline{ }samplingunderline{ }time = numunderline{ }epochs times numunderline{ }samplingsunderline{ }perunderline{ }epoch times samplingunderline{ }elapsedunderline{ }timeend{equation}
RBMの量子アニーリング実装とCPU/GPU実装の違いはサンプリング時間の合計にあるので、量子アニーリングの方が速いことになります。
GPUの計算時間も普通はデータ転送などを考慮しないので、量子アニーリングも今回はアニーリングの時間だけを考えます。

なぜ6×6程度の小さい画像しか使っていないかというと、D-Waveのハードウェアで解ける問題サイズが限られているためです。
visible unit 36, hidden unit 56のRBMを最新のD-Wave 2000Qに入れると下図のようにD-Waveアニーラーのチップが成す構造chimera graph半分のQubit (Quantum Bit, 量子コンピューティングシステムのビット) が使われます。

これからD-Waveは4000Qubitを持つ新しいシステムをリリースするそうです。その時にはさらに大きいRBMを実現できるでしょう。

D-Waveを使ってRBMを実装する既存研究は既に数件ありましたが、どちらもソースコードをリリースすることありませんでした。今回我々はソースコードをリリースしてみなさんと一緒にこの分野の研究を発展していきたいと思います。
量子アニーリングRBM：
https://github.com/mercari/CFQIRBM
TensorFlow RBM：
https://github.com/shitian-ni/tensorflow-rbm
TensorFlow RBMのサンプリング時間を計測するコード：
https://github.com/shitian-ni/tensorflow-rbm/blob/master/measure_time.py

今後さらにできること

hidden unitを多層にするとCPU/GPUのTensorFlow実装はsigmoidの近似誤差が蓄積するから、量子アニーリングのほうが良い結果を出すかもしれません。
リバースアニーリングを試したら量子アニーリングがいい結果を出せるかもしれません。
既存研究では量子アニーリングの場合の方がKL-Divergenceを低くできていい結果を出すことを発表していますが、今回は単一画像の再構築しかやっていなかったので量子アニーリングに不利な状況になりました。もっと複雑なデータセットを使うと量子アニーリングの価値が出るかもしれません。

外部資料

• リバースアニーリング：
  https://www.dwavesys.com/sites/default/files/14-1018A-A_Reverse_Quantum_Annealing_for_Local_Refinement_of_Solutions.pdf
• D-Waveシステムへの問題Embed：
  https://arxiv.org/pdf/1704.01996.pdf