@yuichirominato 2018.06.30更新 150views

量子アニーリング+強化学習の基礎の確認

D-Wave QUBO サンプリング 強化学習 深層学習 量子アニーリング

はじめに

量子アニーリングや量子コンピュータを使って強化学習をする方法はいくつかあり、自由エネルギーをベースとしたマルコフ過程を利用した強化学習などもありますが、今回はベルマン方程式+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という報酬テーブルをつくって、最適な報酬を更新していきます。

引用: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


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

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) \approx Q^\pi(s,a)$

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


ベルマン方程式から学習を行う場合、これから得られる報酬の期待値と現在の期待値の誤差を修正するように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の入れ方

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


引用:Reinforcement Learning Using Quantum Boltzmann Machines
https://arxiv.org/pdf/1612.05695.pdf

学習のさせ方

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

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

参考:
「D-Waveで深層学習の基礎となるRBMのボルツマン学習を実行してみた」
http://blog.mdrft.com/post/258

$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}
$

あわせて読みたい

SERVICE

汎用量子コンピュータ向けアプリケーション開発SDK

詳しく見る Githubで入手する(無料)

汎用量子コンピュータ向け高速シミュレータ

詳しく見る

量子コンピュータ向けクラウドサービス(準備中)

詳しく見る

イジングマシン向けアプリケーション開発SDK

詳しく見る Githubで入手する(無料)

COMMUNITY

量子コンピュータのことを学びたい、仕事としたいなどの情報交換の場を設け、コミュニティの形成を進めています。オフラインの勉強会と、オンラインのチャットコミュニティの2種類あります。オフラインのConnpassは1400名、オンラインのSlackは880名を超える参加があります。どちらも無料ですのでお気軽にご参加ください。

CONNPASS SLACK

CONTACT

弊社あての連絡はinfo@mdrft.comより用件を明記の上、メールで連絡を頂けますと幸いです。

ブログトップに戻る

Recent Posts