量子アニーリング+ボルツマンマシンでの強化学習


はじめに

量子アニーリングや量子コンピュータを使って強化学習をする方法はいくつかあり、自由エネルギーをベースとしたマルコフ過程を利用した強化学習などもありますが、今回はベルマン方程式+RBM(制限付きボルツマンマシン)やDBM(ディープボルツマンマシン)を今後活用することを目的として後者を学んでいきたいと思います。


参考文献

RBMの参考文献はYoshua Bengio先生やGeoffrey Hinton先生のこちらがとても役にたちました。

On the Challenges of Physical Implementations of RBMs

Vincent Dumoulin and Ian J. Goodfellow and Aaron Courville and Yoshua Bengio

https://arxiv.org/pdf/1312.5258.pdf

A Practical Guide to Training Restricted Boltzmann Machines

Geoffrey Hinton

https://www.cs.toronto.edu/~hinton/absps/guideTR.pdf

また、実際にD-Waveを活用してRBMの学習などの手順は、

Application of Quantum Annealing to Training of Deep Neural Networks

Steven H. Adachi, Maxwell P. Henderson

https://arxiv.org/abs/1510.06356

名著です。

また、SAやSQAをつかって強化学習を行う手順は、

Reinforcement Learning Using Quantum Boltzmann Machines

By Daniel Crawford, Anna Levit, Navid Ghadermarzy, Jaspreet S. Oberoi, & Pooya Ronagh

https://arxiv.org/pdf/1612.05695.pdf

また、深層強化学習に関しては量子コンピュータではないですが、

Deep Reinforcement Learning

David Silver, Google DeepMind

http://www0.cs.ucl.ac.uk/staff/d.silver/web/Resources_files/deep_rl.pdf

これらを活用しました。


Q学習

Q学習は機械学習手法の方策オフ型TD学習の一つである。概念自体は古くから存在するが、Q学習(Q-learning)という名前で今日の手法がまとめられたのは、1989年のクリス・ワトキンズ(Chris Watkins)の論文に端を発する。

Q学習は有限マルコフ決定過程において全ての状態が十分にサンプリングできるようなエピソードを無限回試行した場合、最適な評価値に収束することが理論的に証明されている。実際の問題に対してこの条件を満たすことは困難ではあるが、この証明はQ学習の有効性を示す要素の一つとして挙げられる。

引用:https://ja.wikipedia.org/wiki/Q%E5%AD%A6%E7%BF%92

下記のようなQ-Tableという報酬テーブルをつくって、最適な報酬を更新していきます。

4.png

引用:Markov Decision Processes and Reinforcement Learning

https://s3.amazonaws.com/ml-class/notes/MDPIntro.pdf


ベルマン方程式

ベルマン方程式(ベルマンほうていしき、英: Bellman equation)は、「動的計画法(Dynamic programming)」として知られる数学的最適化において、最適性の必要条件を表す方程式であり、発見者のリチャード・ベルマンにちなんで命名された。動的計画方程式 (dynamic programming equation)とも呼ばれる。 ベルマン方程式は、決定問題(decision problem)において、ある時刻の初期選択と、それ以降の決定問題の価値との関係を記述する。これにより、動的な最適化問題を、「ベルマンの最適性の原理」が示す指針にしたがって、より単純な部分問題(subproblems)に分解するのである。

引用:https://ja.wikipedia.org/wiki/%E3%83%99%E3%83%AB%E3%83%9E%E3%83%B3%E6%96%B9%E7%A8%8B%E5%BC%8F

5.png

環境や状態があり、そこで行う行動があるとき、上記のように報酬を最大化するような方策を選びます。


Deep Q-Learning

参考資料は下記です。

Deep Reinforcement Learning

David Silver, Google DeepMind

http://www0.cs.ucl.ac.uk/staff/d.silver/web/Resources_files/deep_rl.pdf

本当はもっと色々進んでいる研究分野ですが、量子コンピュータ向けは文献が少なく、研究もこれからなのでこれくらい基本的なところを参考にしていきます。

Q(s,a,w)≈Qπ(s,a)まずは前述のQ-Tableの代わりに結合荷重wを使用したNNで評価関数を表現します。

6.png

ベルマン方程式から学習を行う場合、これから得られる報酬の期待値と現在の期待値の誤差を修正するようにwを更新します。


テクニック

1.Experience Replay

To remove correlations, build data-set from agent’s own experience

連続した時系列データの相関を除くデータセットを作る。

2.Fixed Target Q-Network

To avoid oscillations, fix parameters used in Q-learning target

値の頻繁な変更を許容しないミニバッチの際のパラメータの固定

3.Reward/Value Range

DQN clips the rewards to [−1, +1] I This prevents Q-values from becoming too large

Q値が大きくなりすぎないように配慮

正直ここら辺のテクニックは普通に使えそうです。うまくいけば使っていくような方針で今後は。基本的には誤差計算の部分が異なるだけで、基本的な手順は同じのようです。


RBMとstateとactionの入れ方

基本的には可視層に入れます。推論方法は様々です。

7.png

引用:Reinforcement Learning Using Quantum Boltzmann Machines

https://arxiv.org/pdf/1612.05695.pdf


学習のさせ方

基本はRBMです。D-Waveなどの量子アニーリングマシンからボルツマン分布と呼ばれる確率分布を仮定した上で、出てきた答えを誤差計算に使います。

下記のように確率分布を仮定し、逆温度係数βとRBMのハミルトニアンから誤差計算をします。

P(x) = \frac{1}{Z}exp\left(-\beta_{eff}H_f(x)\right)

勾配の更新式は、

\frac{\partial logP}{\partial W_{ij}} = < v_ih_j > _{data}- < v_ih_j > _{model}\\ 

\frac{\partial logP}{\partial b_i} = < v_i > _{data}- < v_i > _{model}\\
\frac{\partial logP}{\partial c_j} = < h_j > _{data}- < h_j > _{model}

このなかで、こちらの式は多少計算が大変です。

< v_ih_j > _{model} = \frac{1}{Z}\sum_{\{v_k\}}\sum_{\{h_l\}}v_ih_j exp\left(\sum_kb_kv_k+\sum_lc_lh_l+\sum_{kl}W_{kl}v_kh_l\right)

確率分布を使ったハミルトニアンからの分布式を使うと、

\overline{v_ih_j} = \frac{1}{N}\sum_{n=1}^N v_i^{(n)}h_j^{(n)}

これくらいの近似で済むという方法を採用して、誤差計算をD-Waveのサンプリングで行います。

より具体的な実装方法は今後おって書いていきたいと思います。


量子アニーリング

量子アニーリングでは量子性により分布がずれることもあるようです。シミュレーションを行う場合には、量子モンテカルロを使用したシミュレーテッド量子アニーリングというのが高速でよく使われます。モンテカルロシミュレーションを行う際に使用する分配関数は量子系を鈴木トロッタ展開により1次元増やして近似し導出します。あとは古典系になおっているので、普通にモンテカルロを行います。

E=-\sum_{i,j}\sum^m_{k=1}\frac{J_{ij}}{m}q_{i,k}q_{j,k}-\sum_i\sum^m_{k=1}\frac{h_i}{m}q_{i,k}-\frac{T}{2}\sum_{i,j}\sum^m_{k=1}lncoth(\frac{\Gamma}{mT})q_{i,k}q_{i,k+1}


応用論文

今回は実機ではなく、量子アルゴリズムシミュレーションを中心として確認します。


参考文献

Reinforcement Learning Using Quantum Boltzmann Machines

Daniel Crawford, Anna Levit, Navid Ghadermarzy, Jaspreet S. Oberoi, Pooya Ronagh

(Submitted on 17 Dec 2016 (v1), last revised 25 Dec 2016 (this version, v2))

https://arxiv.org/abs/1612.05695


概要

量子アニーリングをベースとして、制限付きボルツマンマシンと、複層のディープボルツマンマシン、そして横磁場の影響の残る段階での学習を行う量子ボルツマンマシンの3種類をシミュレーションを通じて学習を評価する。特にディープボルツマンマシンや量子ボルツマンマシンは古典計算機では本質的に効率的な学習は難しいので、量子性を用いたアナログ計算機の特性が活かせると思われる。

1-11.png

引用:https://arxiv.org/abs/1612.05695


課題

今回は迷路の課題を設定している。

11.png

引用:https://arxiv.org/abs/1612.05695

Wは壁、Rは報酬、Pはペナルティ。強化学習でこの迷路の報酬の期待値を最大にするように学んでもらう。


State(状態)

状態は迷路の中でのエージェントの位置で、状態sは縦横のマス目の位置の値をとる。

S={1, …, r} x {1, …, c}


Action(行動)

どの状態でもエージェントは下記5つの行動をとることができる。

a ∈ {↑,↓,←,→,stay}

エージェントが取りうる行動は、留まるもしくは上下左右に移動するの5通り設定する。


移動できない場所への移動

a : S → S.

そのような移動は留まるような行動とする。


時間割引率

強化学習における割引率を0.8にしている。


報酬の設定など

固定報酬は200、可変の報酬はベルヌーイ分布で200Ber(0.5)で期待値が100に。


アルゴリズムごとの性能比較

12.png

各迷路で3つのアルゴリズムの比較をしている。

RBMは二層のボルツマンマシンで、値の更新は古典計算。

DBMは量子アニーリングのシミュレーションSQAでの更新。

QBMも横磁場の影響を残しながらのSQAでの更新。

様々な迷路でのパラメータを変更した過程でQBMが良い結果を残している。


迷路サイズに対するアルゴリズムの性能

13.png

RBMとDBMの比較において、迷路サイズを大きくした時のFidelityを求めている。RBM/DBM共にhidden layerの数は20として、DBMの方がいい結果が出ている。


具体的アルゴリズム手順、SQA

SQAアルゴリズムは鈴木トロッタ展開を用いた経路積分の量子アニーリングを使用している。

12.png

横磁場の強さはΓが20から0.01もしくは2.00まで変化。逆温度βは2.00で固定、レプリカのトロッタ数は25としている。


アルゴリズム1、 RBM

1.png

2.png

RBMはシグモイド関数を使用して隠れ層の期待値を計算。それによってRBMの結合荷重を更新している。

3.png


アルゴリズム2、DBM

DBMは複層のボルツマンマシンで、下記の通りの手順でアルゴリズムを実行。

4.png

自由エネルギーは、

5.png

更新にはアルゴリズムはSQAもしくはSAが使用できる。

また、これまで出てこなかったのが、隠れ層同士の接続部分の計算で下記の通りに与えられる。

6.png


アルゴリズム3、QBM

7.png

最後のアルゴリズムはQBMで横磁場の影響を考慮しながらDBMをアップデートする。

自由エネルギーは下記式で表される。

8.png

Γは最後まで落とさず2.00くらいでとめて測定をする。