Top
このブログはなんですか
Talk of tech innovation is bullsh*t. Shut up and get the work done – says Linus Torvalds
何を実装しましたか(Deep Learning)
RNN
その他
備考
諸事情により8月中は更新なし
Pointer Networks
論文まとめ
入力系列上のインデックスに対応した要素から成る出力系列の条件付き確率分布を学習するアーキテクチャ.
この種の問題は、出力の各ステップでのターゲットクラスの数が、可変である入力長にいぞんしているので、Seq2SeqやNeural Turing Machineでは解くのは難しい.
(例えば、可変長のソート問題や種々の組み合わせ最適化問題など.)
既存のAttention
- デコーダの各ステップで、エンコーダの隠れユニットをコンテキストに混ぜる
今回のAttention
- 出力として、入力系列中の要素を指すポインタ(つまりインデックス)として利用する
Sequence-to-Sequence
: 入力系列
] : 出力系列(各出力は入力系列上のインデックス)
トレーニングデータのペアが与えられた時、次の条件付き確率を、RNN (LSTM)によるパラメトリックモデルで推定するというもの.
以下のように、トレーニングセットの条件付き確率を最大化するように学習する.
統計的な独立性は仮定はせずに、RNNは各時刻において、を入力系列の終わり()まで受け取り、出力系列の終わり()まで出力記号を生成する.
推定時には、入力系列が与えられ、学習済みパラメータを用いて、条件付き確率を最大化する列、つまりとなるを選択する.
最適な系列を見つけるには、計算量的に困難なので、ビームサーチを行ったりする.
このsequence-to-sequenceにおいては、出力は入力系列上のインデックスから選択されるのであるから、すべての記号の数は入力列長であるに固定されている.
つまり異なるごとに学習しなくてはならない.
ちなみに、出力の数がだとしたら、計算量はとなる.
Content Based Input Attention
attentionというものを考えて、seq2seqでは固定的であったdecoderのステートに対してより多くの情報を付加する.
: encoder hidden states
: decoder hidden states
としたとき、attentionを以下のように定義する.
は学習パラメータで、はを正規化してattention maskを生成する.
計算量的には推定時に、各出力で命令処理するので、となる.
Seq2Seqより性能は良いが、やはり出力の辞書サイズが入力に依存するような問題には適用できない.
Ptr-Net
Seq2Seqでは、条件付き確率を計算するために、固定サイズの入力の辞書(系列上のインデックス)におけるの分布を使用する形になる.
したがって、出力が入力の辞書サイズに依存するような場合には適用できなかった. これに対して、以下のように、attentionを用いて条件付き確率をモデリングする.
は学習パラメータで、はを正規化して、入力の辞書上(インデックス)の確率分布を生成する.
通常のattentionのように、「より多くの情報を伝播させるために、encoderのステートを混ぜる」というようなことはせずに、を入力要素へのポインタとして使う.
また、で条件付けするために、対応するを入力としてコピーする.
図的には以下のような感じ
(論文より引用)
データセット
Convex Hull (凸包)
に
こんな感じのデータ
0.12597930 0.57132358 0.77404416 0.01266053 0.69612552 0.98888917 0.56750540 0.30860638 0.25714026 0.99675915 0.41245506 0.03328769 0.99328556 0.97091931 0.82174988 0.08516088 0.63969443 0.51914056 0.45612945 0.54733761 0.32766033 0.43352998 0.49206557 0.89107185 0.13685374 0.00708945 0.61040137 0.43254429 0.88256464 0.81985257 0.07880500 0.53008275 0.42095766 0.92055700 0.02109736 0.33024543 0.76352942 0.73969747 0.08505665 0.51877561 0.62335861 0.39605697 0.86642364 0.09540971 0.89609816 0.87439433 0.57799306 0.40433588 0.01053175 0.77368518 0.49862115 0.26769698 0.94832038 0.56638474 0.03807545 0.71314326 0.97767538 0.72042601 0.82861561 0.41455754 0.56748456 0.32859033 0.87639463 0.93457765 0.28872692 0.14781993 0.18529194 0.06272494 0.32126462 0.56453709 0.81442383 0.01964365 0.56290155 0.64332693 0.93979231 0.16170123 0.36700478 0.97992791 0.26060579 0.12514376 0.33918180 0.76817253 0.41583231 0.49321529 0.41187788 0.27050384 0.19393678 0.46065066 0.29478536 0.77983912 0.54389681 0.26205415 0.20471867 0.04153719 0.95478980 0.33200250 0.04618655 0.56410345 0.99342056 0.87685348 output 2 36 38 48 50 7 3 5 25 18 13 2
可視化するとこのような感じ
実装
Decoder
dec_cell_in = utils.fc(dec_inputs, dec_inputs.get_shape()[-1], lstm_width, init_w=initializer, a_fn=tf.nn.elu) (dec_cell_out, dec_state) = dec_cell(dec_cell_in, dec_state) # W1, W2 are square matrixes (SxS) # where S is the size of hidden states W1 = tf.get_variable("W1", [lstm_width, lstm_width], dtype=tf.float32, initializer=initializer) W2 = tf.get_variable("W2", [lstm_width, lstm_width], dtype=tf.float32, initializer=initializer) # v is a vector (S) v = tf.get_variable("v", [lstm_width], dtype=tf.float32, initializer=initializer) # W2 (SxS) d_i (S) = W2d (S) W2d = tf.matmul(dec_state.h, W2) # u_i (n) u_i = [] for j in range(num_steps): # W1 (SxS) e_j (S) = W1e (S) # t = tanh(W1e + W2d) (S) t = tf.tanh( tf.matmul(enc_states[j].h, W1) + W2d ) # v^T (S) t (S) = U_ij (1) u_ij = tf.reduce_sum(v*t, axis=1) # cuz t is acutually BxS u_i.append(u_ij) u_i = tf.stack(u_i, axis=1) # asarray probs = tf.nn.softmax(u_i)
Loss
L2 Loss
self.loss = tf.nn.l2_loss(targets - self.C_prob)
入力データ
上の方で貼った図に倣い、入力の先頭(index 0)を終了記号に対応させるようにした.
具体的にどのような値を設定するべきなのかわからなかったので入力系列のインデックス0には[-1.0, -1.0]を対応させた.
トレーニングデータの出力系列はzero-padidngした。
enc.insert(0, '-1.0') enc.insert(0, '-1.0') while len(dec) != len(enc) // 2: dec = np.append(dec, _STOP)
結果
ある程度それっぽい出力をしている例
[ 2 11 21 21 39 28 40 50 47 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[ 1 18 42 42 31 25 25 49 26 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[ 2 2 44 12 30 36 36 21 29 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[ 2 2 7 26 6 6 44 4 27 27 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[ 5 34 34 32 8 43 43 45 18 25 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[ 6 31 28 41 41 48 39 9 9 13 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
微妙なものも多くあったので、実装に不備があるのかもしれない...
Prioritized Experience Replay
[1511.05952] Prioritized Experience Replay
論文まとめ
Online RLの問題点
- 遷移(transition)間の依存関係の影響が大きい
- レアな遷移をすぐに捨ててしまう
そこで、
Experience Replay(ER)
DQNでは、replay mem.からランダムサンプリングしたミニバッチを使って更新する.
ERをより効率的、効果的にするには??
優先順位を付けてサンプリングする.
より学習の進行が期待される遷移をより頻繁にリプレイするようにする.
ニューロサイエンス的な話
休憩している時や寝ている時に、海馬は過去の経験を"リプレイ"している.
特に、報酬に結びついている経験をより頻繁にリプレイしているらしい.
更に、"TD-error"の大きい経験もより頻繁にリプレイされるらしい.
Planningにおけるprioritization
planning(つまりmodel-freeではない)では、prioritizingが有効的であることが知られている.
Prioritized sweeping(更新した時の価値の変化に応じて優先度付けするような手法)
model-freeではTD-errorがこの優先度の基準に対応する尺度のひとつとなる. 更にここではstochastic prioritizationを行うことで、サンプルから関数近似を行う場合よりロバストになる.
Prioritized Replay
優先度を付けるには、以下の二つの方針があるが、今回は下の方
- どの経験を格納するか?
- どの経験をリプレイするか?
TD-errorによるprioritization
理想的な尺度→現在のステートにおいて、どの遷移からどの程度学習することができるか
これは直接的には分からないので、代わりに TD-error を用いる.
直感的には、どれだけ"驚いたか"、どれだけ予想していない遷移だったかを表し、bootstrappingした推定値と実測値がどの程度離れていたかを示す尺度.
greedy TD-error prioritization
最も単純な考え方で、TD-errorの絶対値が最大のものをリプレイする.
新しい遷移は、最低1回はサンプリングされることを保証するために最高の優先度で格納される.
メモリサイズをにスケールさせるために、優先度キューにはバイナリヒープを用いる.
そうするとサンプリングがで、追加がで可能.
stochastic prioritization
greedy TD-error prioritizationにはいくつか問題点がある.
- リプレイされたTD-errorのみを更新するので、最初が低いTD-errorだと、長期間放置され得る
- ノイズのスパイクに過剰反応してしまう(確率的な報酬の場合など). 特にbootstrappingの場合だと、より顕著.
- 局所的な遷移(TD-error大きいものが頻繁にリプレイされる)しか見ないので学習が遅くなる. 多様性がなくなるので、overfittingの元となる.
確率的なサンプリングによって、uniform(通常のER)とgreedyの中間的なことをする.
どういう確率分布を考えるか?
- 優先度に関して単調
- 低い優先度でも非ゼロ
これを踏まえて、遷移のサンプリング確率を以下で定義する.
は遷移の優先度、はどの程度優先度を重視するかに対応するハイパーパラメータ(ならばuniform)
Proportional Prioritization ( direct )
, は小さい正定数でTD-errorが0になっても、それ以降サンプリングされないことを防ぐ.
( proportionalについては今回は割愛する )
Rank-based Prioritization ( indirect )
, は、遷移がに従ってリプレイメモリに格納された時の順位.
この場合、
となるので、はスケーリング指数の冪乗則分布となる.
propotionalと比べて、外れ値に対して過剰反応しないのでよりロバスト性が期待できる(らしい)
サンプリングを効率化するには、計算コストはに依存してはならない.
ミニバッチベースの場合、をミニバッチサイズに設定し、各区間から1遷移をサンプリングする.
これは、層状抽出法(stratified sampling)に対応する.
利点としては、バランスの取れたミニバッチが生成できる.
以下は、自分の実装方法も含めた全体の概略図.
Annealing the bias
PRはこのサンプリングの分布を変化させるような"bias"を生じるので、確率的更新による期待値の推定値の収束する値も変わってしまう.
これをImportance Sampling(IS)によって修正する.
(分子くる分布はは一様分布ということ??)
の場合、完全なISを行うことに対応する.
Q-learningの枠組みではTD-targetをこれで重み付けすればよく、の代わりにを用いる.
安定性の理由から、重みはで正規化する.
指数を学習の終了時に1に到達するようにスケジューリングする. (更新にbiasがないことは収束する付近では重要な性質)
例えば、初期値から線形的に1に近づける.
(アニーリングする理由は、full IS()の場合重みが小さくなって初期の学習が遅くなるから??)
配列ベースのバイナリヒープによる優先度付きキューを近似的にソートされた配列として使用する.
木が不均衡になりすぎないように,ステップ毎にソートしなおす.
(毎回完全にソートした配列を利用した場合と比較してあまり性能的な変化はなかった)
αとβはたまに更新する.
※
: とれだけbiasを修正するか
: どれだけサンプリングの優先度を重要視するか
実装
データ構造
上図に示したように、一番下は通常のExperience Replayと同様に、リングバッファで管理する.
そのリングバッファ上のインデックスを管理して、Prioritized Replay を行う.
つまり、PRのバイナリヒープは対応するリングバッファのインデックスと、優先度付けのためのTD-errorの情報を持っている.
一方、リングバッファの方は対応するバイナリヒープのインデックスと、遷移の情報を持っている.
確率分布
dist = np.asarray([(1.0/(i+1))**self.alpha for i in range(n)], dtype=np.float32)
累積密度分布
cdf = np.cumsum(dist)
区間の計算
unit = (1.0 - cdf[0])/self.k self.seg = [ np.searchsorted(cdf, cdf[0]+unit*i) for i in range(self.k) ]
アニーリング
self.beta += self.beta_step
サンプリングとIS weight
h_indices =[ np.random.randint(self.seg[i], self.seg[i+1]) \ for i in range(self.k) ] h = np.asarray(self.heap)[h_indices] d_indices = [i['D'] for i in h] d = np.asarray(self.D)[d_indices] rank = np.asarray([ p['heap']+1 for p in d], dtype=np.int32) is_w = ((rank**self.alpha) * self.p_n)** self.beta return d, is_w
更新
max_is = tf.reduce_max(self.is_w) self.loss = tf.reduce_mean( (self.is_w / max_is) * self.delta)
結果
環境はOpenAI gymのMsPacman-v0
今回も時間とメモリの都合上完全な再現はできなかったが、
メモリサイズ
(1M step)
target net の更新はstep毎
ネットワークの構成は"Tuned" Double-DQN
で行った.
右肩上がりの段階で止めてしまったのが惜しい.
追い追い、各手法を比較できればと思う.
Deep Reinforcement Learning with Double Q-learning (Double DQN)
Deep Reinforcement Learning with Double Q-learning
[1509.06461] Deep Reinforcement Learning with Double Q-learning
論文まとめ
Q-learningは、maxを取っている関係上、action-valueを過大評価(overestimate)する傾向があることが知られている.
これまでに挙げられていた過大評価の原因
- 柔軟性が不十分な関数近似による誤差 Thrun and Schwartz (1993)
- 環境のノイズ van Hasselt (2010)
この論文ではより一般的に、任意の推定誤差によって過大評価は引き起こされることが示されている.
学習過程では必ず不正確な推定値になってしまうのでこれは重要な問題.
Double Q-learning (van Hasselt, 2010)
そもそも、Q-learningのTD-targetは以下の形であった.
つまり、greedy policyに基づく行動の選択と、その価値の推定は同じ関数に基づいている.
これは過大評価に繋がりやすく、楽観的(optimistic)な価値の評価になりやすい.
そこで選択と推定を分離することを考える.
つまり、パラメータはとがあり、一つはgreedy policyの行動選択に、もう一つは価値の推定に使われる.
するとTD-targetは以下のようになる.
二つの価値関数をランダムに選んだ別個の経験(experience)からそれぞれを更新する.
との役割を交互に変えることで更新する.
(よくわかってない)
推定誤差によるOveroptimism
過大評価の上界(Thrun and Schwartz (1993))
action-valueが]の一様分布に従う誤差を含んでいる場合、
過大評価の上界は (は行動数)
過大評価の下界
価値の推定が平均的に正しい、
が、どこかで何かしらの誤差が生じている ()
ような時、
となることが証明されている. つまり真値より高く推定(過大評価)してしまう.
また、同じ条件でDouble Q-learningの場合、絶対値誤差の下界が0になることも証明されている.
この式から、下界としては行動数が増えると小さくなるが、これはあくまで下界の話で、
一般的には行動数が増えると真値との誤差も大きくなる.
またDouble Q-learningの場合は行動数が増えても誤差が小さいことも実験的に示されている.
Double DQN
上述のようにDouble Q-learningは選択と評価を分離することで過大評価を回避する.
完全な分離ではないが、DQNのtarget networkが使える(別のネットワークが必要ない).
よってtarget networkのパラメータをとすると、TD-targetは、
となる. TD-targetが変わる以外はDQNと同じ.
DQN vs Double DQN
以下のグラフの通り、Double DQNではDQNよりも過大評価がかなり抑えられていることが確認できる.
(論文より引用)
以下のグラフは、価値の推定値とゲームのスコアのグラフだが、過大評価が生じ始めるとスコアが下がることが見てわかる.
つまりこれは、過大評価がpolicyに悪影響を与えるということを意味している.
(論文より引用)
DQNのこの性能悪化は、Off-Policy+関数近似の本質的な不安定性に起因したものではなく、Q-learningの過大評価に起因したものということを意味している.
(現にDouble DQNは安定している)
過大評価は必ずしも悪影響に繋がるわけではないが、減らすことで学習の安定化が図れるという事が言える.
また、Double DQNはより汎用的なpolicyを学習できる(ロバスト性が高い)ということも示されている.
※必ずしも悪影響に繋がらないとは、例えば全てのaction-valueが一様に過大評価されていれば、相対的な振る舞いは同じなので悪くはならない
実装
TD-target
a_max = tf.expand_dims(tf.argmax(Q(self.s_, reuse=True), axis=1), axis=1) a_max = tf.to_int32(a_max) target_q_val = tf.expand_dims( tf.gather_nd(target_Q(self.s_), tf.concat(values=[first, a_max], concat_dim=1)) , axis=1) self.y = self.r + gamma*(1.0 - self.done)*target_q_val
shared bias
# shared bias with tf.variable_scope("shared", reuse=s_bias): b = tf.get_variable("shared_b", [self.a], dtype=tf.float32, initializer=tf.constant_initializer(0.0))
結果
OpenAI gymのMsPacman-v0
500000ステップでが0.01に到達する設定なので、あまり学習が進んでいないかもしれない.
Deep Q Network (DQN)
http://www.nature.com/nature/journal/v518/n7540/full/nature14236.html
[1312.5602] Playing Atari with Deep Reinforcement Learning
Q-Learningにおいて、action-value functionをDNNで関数近似したもので、Deep RLの皮切りとなった.
Q-Learningとはなんだったか?
自分用の強化学習メモからの復習的ななにか.
Model-free、Off-Policy、Value-basedなControl
target policy : greedy
behavior policy : -greedy
(TD-TargetにはサンプリングしたBellman Optimality Equation)
パラメータで関数近似した場合、
論文まとめ
そもそも、action-value(以下)関数を非線形関数で近似すると、RLは不安定あるいは発散することが知られている.
理由は例えば以下のようなことが挙げられる.
- 観測間に依存関係が存在する.
- を多少更新したただけでも、政策関数が大きく変わる可能性があるので、観測データの分布も依存関係も大きく変わってしまう可能性がある.
この不安定性を打破するために以下の2つを行う.
Experience Replay
生物学的なメカニズム(海馬まわり?)からの発想.
過去の観測データをランダムサンプリングして、観測間に生じる依存関係を除去することで、観測データ分布の変化を滑らかにする.
具体的には、経験を各時刻において、バッファにプールする. 関数を更新する時は、このバッファからランダムサンプリングしたミニバッチで行う.
Target Network
一定間隔で更新する関数をTD-targetに利用する. これも依存関係を除外することに貢献している.
Q-LearningにおけるTD-Target、を、ステップ毎に更新されるパラメータで置き換える. (は iterでのパラメータ)
その他
上記の2点が中心ではあるが、その他にも学習を進める上でいくつかのことを行っている.
Error Clipping
これを行うことで更に安定性を上げている.
つまり、TD-Error が、
の外側の場合は絶対値誤差を、内側の場合は二乗誤差利用する.
これは、Hurber Lossに対応する.
前処理、flickeringの除去
あるオブジェクトは偶数フレームにしか現れないなどの現象(flickering)を回避するために、前フレームと現フレームの最大値を1フレームとする.
更にこれを、グレースケール化して、84x84にリサイズする.
直近の4フレームにこの前処理を施したものを1ステートとする.
他frame skipping, reward scaling
実装
前処理
# gray-scaling gray = cv2.cvtColor(obs, cv2.COLOR_RGB2GRAY) # resizing gray = cv2.resize(gray, (84, 84)) # squashing return (gray - 127.5) / 127.5
pre = self._preprocess(obs) self.state = np.concatenate( (self.state[:, :, 1:], pre[:,:,np.newaxis]), axis=2 )
OpenAI gymではframe skippingなどは内部的に行われているようで、特に何かする必要はなさそう.
サンプリング
samples = random.sample(self.D, self.batch_size)
パラメータのコピー(target networkの更新)
def copy_params(src, dst): src_params = [v for v in tf.trainable_variables() if v.name.startswith(src.scope)] dst_params = [v for v in tf.trainable_variables() if v.name.startswith(dst.scope)] op = [d.assign(s) for s, d in zip(src_params, dst_params)] return op
Hurber Loss
def Hurber_loss(x, y, delta=1.0): error = tf.abs(y - x) cond = tf.less(error, delta) return tf.where(cond, 0.5*tf.square(error), delta*error - 0.5*tf.square(delta))
# r: reward # s_: next state # done: 1 (terminated), 0 (otherwise) self.y = self.r + gamma*(1.0 - self.done)*tf.reduce_max(target_Q(self.s_), axis=1, keep_dims=True)
self.probs = Q(self.s) first = tf.expand_dims(tf.range(self.batch_size), axis=1) indices = tf.concat(values=[first, self.a], concat_dim=1) # gather corresiponding q_vals self.q_val = tf.expand_dims(tf.gather_nd(self.probs, indices), axis=1)
-greedy
if np.random.rand() < epsilon: a = env.action_space.sample() else: a = dqn.greedy(s, sess)
-decay
epsilon = 1.0 if global_step < FLAGS.replay_start_size else \ max(FLAGS.min_epsilon, np.interp( global_step, [0, FLAGS.decay], [1.0, FLAGS.min_epsilon]))
結果
OpenAI gymのMsPacman-v0
あんまり回してないので、微妙な結果.
メモリが少ないのでReplay Bufferのサイズも50000程度.
機会があったらもっと長い時間学習させたい.
強化学習基礎(メモ書き)
強化学習基礎
MDP→TD→Q-Learning→DQN手前まで、強化学習の基本的なことをかいつまんだまとめ
(自分用の自己満メモ)
素晴らしい講義
David Silver氏による強化学習講義
これにほぼ対応した素晴らしい演習問題+α
GitHub - dennybritz/reinforcement-learning: Implementation of Reinforcement Learning Algorithms. Python, OpenAI Gym, Tensorflow. Exercises and Solutions to accompany Sutton's Book and David Silver's course.
Malkov Decision Process (MDP)
完全に観測可能(fully observable)な環境を表す過程
MP (Malkov Process, Malkov Chain)
Malkov Property
これの意味するところは、未来が現在のみに依存し、過去とは独立しているということ.
MPはの組で定義され、は有限の状態集合、は状態遷移確率行列で、
である.
MRP (Malkov Reward Process)
MPにスカラー値が加わったもので、の四つ組で定義される.
はreward function(報酬関数)で、
はdiscount factor(割引率)で、 である.
Return
ここでreturnという量を定義する.
return とは、時刻からの割り引かれた報酬の合計値.
つまり、
なぜ割引?
discount factorの直感的なイメージは、将来の報酬の、現在の値とみることができる.
- returnの発散を回避する
- 将来への不確実性
- 即時的な報酬の方が重要な場合など
- 動物は基本的に即時的な報酬の方を重要視する
- など
Value Function
returnの期待値としてvalue function(価値関数)を定義する.
Bellman Equation
このvalue functionは二つの量に分解することができる.
(returnの定義からすぐ分かる)
つまり、即時的な報酬と次の状態の割り引かれた価値に分解できた.
MDP (Malkov Decision Process)
MRPに決定が加わったもので、の五つ組で定義される.
は、有限な行動の集合
状態遷移確率と報酬も行動に依存するようになるので、
これが環境に対応する.
Policy
行動が加わったのでpolicyというものを定義する
これは、ある状態での取り得る行動の確率分布を表し、エージェントの振る舞いを決定する.
state-value & action-value function
MDPにおけるstate-value function(状態価値関数)とは
これはpolicy に従った場合の、状態からの将来のreturnの期待値で、その状態の価値を表す.
MDPにおけるaction-value function(行動価値関数)とは
これはpolicy に従い、状態にいる時に行動を取る時の将来のreturnの期待値で、その行動の価値を表す.
Bellman Expectation Equation
さて、MRPの場合と同様にこれらは、即時的な報酬と、割引された未来の報酬に分割することができる
を定義したので、状態遷移確率と併せて期待値の部分を展開してみる.
Optimal value function
最適なstate-value functionとaction-value functionを次のように定義する.
Optimal Policy
policyに関して次の半順序を定義する
この時、最適なpolicyとは
であり、このようなpolicyが存在し、はとを達成するという定理がある.
また、最適なpolicyは以下のように得ることができ、決定的なpolicyである.
Bellman Optimality Equation
最適なpolicyを仮定した時のBellman Equation. Bellman Expectation Equationと区別しておくことがとても重要
Policy/Value Iteration(簡単に)
強化学習において、Dynamic Programming (Full backup)によるアプローチには、大きく次の2種類のアプローチが存在する.
Policy Iteration
Policy EvaluationとPolicy Improvementを繰り返してpolicyを最適化する.
Policy Evaluation: 現在のpolicyを評価することのみを行う.
これはBellman Expectation Equationに基づいて行われる.
Policy Improvement: 評価に基づいてpolicyの更新を行う.
Value Iteration
明示的にpolicyは持たない.
value functionをBellman Optimality Equationに基づいて更新することで、最適なvalue functionに近づけていく.
Model-free Prediction (Policy EvaluationのSample backup版)
Model-freeというのは、環境のダイナミクスを利用しない(知らなくて良い)という意味.
Dynamic ProgrammingでのPlanningと比較すると分かりやすいが、例えばDPは状態遷移確率行列が必要になる.
Predictionでは、value functionを予測することを目的とする. (最適化することは後述のControlの領分)
基本的にMonte-Carlo(MC)とTemporal-Difference(TD)というアプローチが存在する.
どちらの手法もイテレーティブに価値関数を更新して評価するのだが、以下の形で表現できる.
真のreturnの方向に修正していく. が、真returnは未知なのでこれを何かしらに置き換える.
MCの場合はreturnとして実際に観測したを利用するのに対して、TD(0)の場合はreturnの予測値を使う.
したがって、MCではを得るために"episodic"でないといけないし、offlineであり、完全なepisodeを必要とする.
TD(0)の場合は、bootstrappingするのでonlineで、しかも不完全なepisodeから学習することが可能である.
MCには深く立ち入らないでTDに焦点を当てていく.
改めてTD(0)の更新式は、
で、をTD Target、をTD Errorと呼ぶ
TD(に拡張できるのだが、とりあえずここではTD(0)にとどめる.
Model-free Control (Policy Improvementの Sample backup版)
value functionを最適化することを考える.
今まで、、つまりstate-valueについて考えていたが、ここでgreedy policy(最大値を与える行動を常に取るpolicy)を想定してみると、
である.
状態遷移確率、つまり環境のモデルが必要になってきてしまう.
一方で、action-valueの場合は、
これはmodel-free.
したがって、action-valueに基づいて更新を行うことにする.
-greedy exploration
ここで-greedyという考え方を定義する.
確率でgreedyな行動を、確率でランダムな行動を取るというもの.
は行動数
これによってPolicy Improvementを行えばとなるという定理がある.
GLIE (Greedy in the Limit with Infinite Exploration)
全てのstate-actionペアが無限回探索される時、policyがgreedy policyに収束するような探索方法.
例えば、-greedyでが0に収束するようなものならば、GLIEである.
On-Policy TD Control (Policy IterationのSample backup版)
Sarsa(0)
Policy Evaluationは以下の更新式に基づく、
Policy Improvementは-greedy policy に基づいて更新する
returnの予測値は現在の状態において行動を取った時の次の状態において、policy に従って行動を選んだ場合の予測値になっている.
ここで、(サンプルした)Bellman Expectation Equationに基づいていることを再確認したい.
GLIEかつステップサイズがRobbins-Monro(略)になっていれば最適なaction-value functionに収束する定理が存在する.
Off-Policy Control (Value IterationのSample backup版)
Off-Policyでは、target policy を評価するのだが、行動自体はbehavior policy に従って行う.
なぜそんなことをするのか??
- ひとつのpolicyに従いながら、複数のpolicyについて学習できる
- 探索的なpolicyに従いながら、最適なpolicyについて学習できる
- 例えば、他の人がどう動いているのだろうということを学ぶイメージ
Importance Sampling
さて、確率分布に関する期待値を確率分布で取る場合、Importance Samplingという操作を行う.
例えば、TD(0)のPolicy Evaluationはインクリメンタルな更新なので、以下のようになる
だがしかし、こんなことは必要ない、そうQ-Learningならね.
Q-Learning
returnの予測値は、状態においてに従って行動を取った時の次の状態において、に従って行動を取る時の予測値となっている.
とを具体的に定義する.
- はgreedy policy、
- は-greedy policy
従って、
ここで、(サンプルした)Bellman Optimality Equationに基づいていることを再確認しておきたい.
Q-Learningは最適なaction-value functionに収束するという定理がある.
関数近似
今までの話をスケールアップさせる上では、value functionを近似することが必要不可欠となる.
ちなみに、今までの収束の話は関数近似した場合、必ずしも成立しなくなる.
確率的勾配降下法(SGD)
今、でパラメータ化されたvalue functionを、真のvalue functionをとした時、以下の最小化問題を解きたい.
に関する勾配は、
よって、SDGの各ステップは以下の更新を行う
期待値でないのは"確率的"勾配降下であるから(勾配をサンプリグする).
インクリメンタルな平均値の更新をイメージすれば、これが期待値になっていくことが直感的にわかる.
ここにおいても、を何かしらに置き換えるわけだが、TD(0)の場合(Policy Evaluation)は、TD Targetで置き換えて、
これは、action-valueについても同様で、
ではQ-Learningにおいては...? → DQN
Wasserstein GAN (WGAN)
Wasserstein GAN (WGAN)
[1701.07875] Wasserstein GAN
([1701.04862] Towards Principled Methods for Training Generative Adversarial Networks WGANの話の前にこの話がある)
Martin Arjovsky氏の実装(Torch)
GitHub - martinarjovsky/WassersteinGAN
WGANをTensorFlowで実装した
github.com
論文まとめ
深く理解しようとするとかなり数学的知識が要求されるので、直感的な理解だけを追っていくことにする.
そもそもVAEやGANのアプローチというのは、自分の分布を真の分布に近づけていくというものだが、この分布間の距離/ダイバージェンスの定義の仕方によって、学習の収束性、安定性に差異がある.
基本的な距離/ダイバージェンスの定義としては以下の4つがある.
とはあるコンパクト空間上で定義される確率分布.(コンパクト空間は距離空間においては、有界閉集合をイメージすればよいらしい. ここでは画像の空間( )と思っていてよい)
- Total Variation (TV) distance
省略
- Kullback-Leibler (KL) divergence
非対称、発散する可能性がある
- Jensen-Shannon (JS) divergence
対称、常に定義可能
GANは近似的にこれを最小化することに対応する
- Earth-Mover (EM) distance (Wasserstein-1)
の直感的理解は、をに変えるために、地点から地点にどれだけの"質量"を移動しなければならないかという量.
よってEM距離は直感的には最適な輸送コストと考えれば良い.
(は同時分布を表す)
以下JSとEMだけ考えることにする.
次の簡単な状況下での距離の変化を観測してみる.
(一様分布)
: 確率分布
: パラメータ
簡単に言うと、二直線間の距離みたいなイメージか.
すると各距離は以下の通り.
よって下図のようなグラフが描ける.
(左がEM、右がJS)
(論文より引用)
この図からわかることは、EM距離は連続かつ有用な勾配(距離の直感に合う)、JS距離は非連続かつ距離の直感に合わない
論文では、諸定理を証明してEM距離が他の尺度より有利な性質を持っていることを述べている.
どうにかEM距離をロス関数として使いたいのだが、定義通りだと難しい...
どうするか??
まず、次のような双対問題が存在する.
- Kantorovich-Rubinstein duality
はある定数で、関数は-Lipschitz連続
-Lipschitz連続性の直感的な理解としては、関数の傾きがある定数で抑えられるような一様連続性であると思っている.
であるから、以下のような問題を考えればよい
はパラメータ化された関数で、GANの枠組みではDiscriminatorに対応する(論文中ではCritic)であり、-Lipschitz連続とする.
もし、先程の双対問題の上限がによって得られるならば、この最大化問題での定数倍を計算することができる.
は、に従って、ある分布(ex. Gaussian)に従う確率変数を(画像の空間)にマッピングする関数で、GANのGeneratorに対応するもの. (これが連続ならば、も連続となることも証明されている.)
さて、に関する勾配が以下になることも定理として示されている.
利点
- 学習の収束性、安定性
- 意味のある、しかも出力画像の質と相関するロス
- DiscriminatorとGeneratorの学習の進み具合を調整する必要がない
- Mode Collapseがない
実装
上でいろいろ書いたが実装に際してはやることは至って簡単.
(Critic = Discriminator)
- Criticを何回か更新して、の良い近似をする
- (Critic)の-Lipschitz連続性を保つ
- Generatorをを最小化する方向に更新する.
の計算
これは、上で述べた双対問題から出てきた最大化問題を解くので、以下の確率的勾配を昇る方向に更新する.
よって実装上は、符号反転して最小化問題とする.
(Critic)の-Lipschitz連続性
パラメータ空間がコンパクト空間(有界閉集合)なら(Critic)の-Lipschitz連続であることを意味する(らしい).
これは、weight clippingをするだけで達成可能である.
を最小化する
GeneratorはEM距離を最小化するので、次の確率的勾配を降る方向に更新する.
以上をまとめると以下のような雰囲気になる.
self.gen_img = self.G() # g(z) g_logits = self.C(self.gen_img, self.p) # f(g(z)) self.g_loss = -tf.reduce_mean(g_logits) # Generatorのロス self.c_loss = tf.reduce_mean(-self.C(self.X, self.p, reuse=True) + g_logits) # Criticのロス c_opt = tf.train.RMSPropOptimizer(learning_rate=5e-5) g_opt = tf.train.RMSPropOptimizer(learning_rate=5e-5) c_grads_and_vars = c_opt.compute_gradients(self.c_loss) g_grads_and_vars = g_opt.compute_gradients(self.g_loss) # Criticに関する勾配のみ c_grads_and_vars = [[grad, var] for grad, var in c_grads_and_vars \ if grad is not None and var.name.startswith("C") ] # Generatorに関する勾配のみ g_grads_and_vars = [[grad, var] for grad, var in g_grads_and_vars \ if grad is not None and var.name.startswith("G") ] self.c_train_op = c_opt.apply_gradients(c_grads_and_vars) self.g_train_op = g_opt.apply_gradients(g_grads_and_vars) # Weight Clipping self.w_clip = [var.assign(tf.clip_by_value(var, -0.01, 0.01)) \ for var in tf.get_collection(tf.GraphKeys.TRAINABLE_VARIABLES, scope="C")]
# 1 Step内 # よい近似となるまで for n in range(5): batch_xs, _ = mnist.train.next_batch(64) batch_xs = batch_xs.reshape([-1, 28, 28, 1]) feed = {wgan.X: batch_xs} # Critic更新 _ = sess.run(wgan.c_train_op, feed_dict=feed) # Weight Clipping _ = sess.run(wgan.w_clip) # Generator更新 _ = sess.run(wgan.g_train_op)
ちなみに、DCGANの反省活かして少しはきれいな実装になったかと思う.
CriticとGeneratorのモデルは以下の通り.
(Batch Normalizationがなくてもよい結果は得られる、更にMLPでもよいとは書かれている)
ラッパーを色々用意したので割りとすっきり書けた(そんなことしなくてもTF-Slimを使えばいい...)
# ==================== # Generator # ==================== class Generator(): def __init__(self, batch_size): self.batch_size = batch_size def build_model(self, reuse): with tf.variable_scope("G", reuse=reuse): z = tf.random_uniform([self.batch_size, 100], minval=-1.0, maxval=1.0) fc1 = tf.nn.relu(batch_norm(fully_connected(z, 100, 1024, scope="fc1"), axes=[0])) fc2 = tf.nn.relu(batch_norm(fully_connected(fc1, 1024, 128*7*7, scope="fc2"), axes=[0])) fc2 = tf.reshape(fc2, [-1, 7, 7, 128]) convt1 = tf.nn.relu(batch_norm(convt(fc2, kernel=[5, 5, 64, 128], stride=[1, 2, 2, 1], output=[self.batch_size, 14, 14, 64], scope="convt1"), axes=[0, 1, 2])) convt2 = convt(convt1, kernel=[5, 5, 1, 64], stride=[1, 2, 2, 1], output=[self.batch_size, 28, 28, 1], activation_fn=tf.nn.tanh, scope="convt2") return convt2 def __call__(self, reuse=False): return self.build_model(reuse) # ==================== # Critic # ==================== class Critic(): def __init__(self, batch_size): self.batch_size = batch_size def build_model(self, X, p, reuse=False): with tf.variable_scope("C", reuse=reuse): conv1 = conv(X, kernel=[5, 5, 1, 64], stride=[1, 2, 2, 1], activation_fn=leaky_relu, scope="conv1") conv2 = conv(conv1, kernel=[5, 5, 64, 128], stride=[1, 2, 2, 1], activation_fn=leaky_relu, scope="conv2") convt2, dim = flatten(conv2) fc1 = fully_connected(convt2, dim, 256, activation_fn=leaky_relu, scope="fc1") # without sigmoid logits = fully_connected(fc1, 256, 1, scope="fc2") return logits def __call__(self, X, p, reuse=False): return self.build_model(X, p, reuse)