Top

このブログはなんですか

Talk of tech innovation is bullsh*t. Shut up and get the work done – says Linus Torvalds

Deep Leaning 勉強用ブログ - DeepLearning勉強マン

備考

諸事情により8月中は更新なし

Pointer Networks

[1506.03134] Pointer Networks

論文まとめ

入力系列上のインデックスに対応した要素から成る出力系列の条件付き確率分布を学習するアーキテクチャ.
この種の問題は、出力の各ステップでのターゲットクラスの数が、可変である入力長にいぞんしているので、Seq2SeqやNeural Turing Machineでは解くのは難しい.
(例えば、可変長のソート問題や種々の組み合わせ最適化問題など.)

既存のAttention

  • デコーダの各ステップで、エンコーダの隠れユニットをコンテキストに混ぜる

今回のAttention

  • 出力として、入力系列中の要素を指すポインタ(つまりインデックス)として利用する

Sequence-to-Sequence

\mathcal P = \{ P_1, ..., P_n \} : 入力系列
\mathcal C^{\mathcal P} = \{C_1, ..., C_{m( \mathcal P )} \},  m( \mathcal P ) \in [1, n ] : 出力系列(各出力は入力系列上のインデックス)

トレーニングデータのペア(\mathcal P, \mathcal C^{\mathcal P})が与えられた時、次の条件付き確率を、RNN (LSTM)によるパラメトリックモデルで推定するというもの.
{\displaystyle
p(\mathcal C^{\mathcal P} | \mathcal P ; \theta) = \prod_{i=1}^{m(\mathcal P)} p_{\theta} (C_i | C1, ..., C_{i-1}, \mathcal P; \theta)
}
以下のように、トレーニングセットの条件付き確率を最大化するように学習する.
{\displaystyle
\newcommand{\argmax}{\mathop{\rm arg~max}\limits}

\theta^* = \argmax_{\theta} \sum_{\mathcal P,  \mathcal C^{\mathcal P}} \log {p(\mathcal C^{\mathcal P} | \mathcal P ; \theta) }
}

統計的な独立性は仮定はせずに、RNNは各時刻iにおいて、P_iを入力系列の終わり(\Rightarrow)まで受け取り、出力系列の終わり(\Leftarrow)まで出力記号C_jを生成する.

推定時には、入力系列\mathcal Pが与えられ、学習済みパラメータ\theta^*を用いて、条件付き確率を最大化する列、つまり\newcommand{\argmax}{\mathop{\rm arg~max}\limits} \hat{\mathcal C}^{\mathcal P} = \argmax_{\mathcal C ^ {\mathcal P}} p ( \mathcal C ^ {\mathcal P} | \mathcal P; \theta^*) となる\hat{\mathcal C}^{\mathcal P}を選択する.

最適な系列\hat {\mathcal C}を見つけるには、計算量的に困難なので、ビームサーチを行ったりする.

このsequence-to-sequenceにおいては、出力は入力系列上のインデックスから選択されるのであるから、すべての記号C_iの数は入力列長であるnに固定されている.
つまり異なるnごとに学習しなくてはならない. 

ちなみに、出力の数がO(n)だとしたら、計算量はO(n)となる.

Content Based Input Attention

attentionというものを考えて、seq2seqでは固定的であったdecoderのステートに対してより多くの情報を付加する.

(e_1, ..., e_n): encoder hidden states
(d_1, ..., d_{m(\mathcal P)}): decoder hidden states
としたとき、attentionを以下のように定義する.

{ \displaystyle
\begin{eqnarray}
u_j^i & = &v^T \tanh(W_1e_j + W_2d_i) & j \in (1, ..., n) \\
a_j^i & = &{\rm softmax}(u_j^i) & j \in (1, ..., n) \\
d_i^{'} & = & \sum_{j=1}^n a_j^i e_j  \\
{\rm hidden \ states} & = & {\rm concat}(d_i^{'}, d_i)
\end{eqnarray}
}

 v, W_1, W_2は学習パラメータで、 {\rm softmax}{\bf u}^iを正規化してattention maskを生成する.
計算量的には推定時に、各出力でn命令処理するので、O(n^2)となる.

Seq2Seqより性能は良いが、やはり出力の辞書サイズが入力に依存するような問題には適用できない.

Ptr-Net

Seq2Seqでは、条件付き確率p(C_i | C_1, ..., C_{i-1}, \mathcal P)を計算するために、固定サイズの入力の辞書(系列上のインデックス)における{\rm softmax}の分布を使用する形になる.
したがって、出力が入力の辞書サイズに依存するような場合には適用できなかった. これに対して、以下のように、attentionを用いて条件付き確率p(C_i | C1, ..., C_{i-1}, \mathcal P)モデリングする.

{\displaystyle
\begin {eqnarray}
u_j^i & = & v^T \tanh(W_1e_j + W_2d_i) & \ j \in (1, ..., n) \\
p(C_i | C_1, ..., C_{i-1}, \mathcal P) & = & {\rm softmax}(u^i)
\end {eqnarray}
}

 v, W_1, W_2は学習パラメータで、 {\rm softmax}{\bf u}^iを正規化して、入力の辞書上(インデックス)の確率分布を生成する.
通常のattentionのように、「より多くの情報を伝播させるために、encoderのステートe_jを混ぜる」というようなことはせずに、u_j^iを入力要素へのポインタとして使う.
また、 C_{i-1}で条件付けするために、対応するP_{C_{i-1}}を入力としてコピーする.

図的には以下のような感じ
f:id:wanwannodao:20170612195610p:plain
(論文より引用)

データセット

Convex Hull (凸包)

定義
凸包 - Wikipedia


こんな感じのデータ

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

可視化するとこのような感じ

https://github.com/Wanwannodao/DeepLearning/blob/master/RNN/PtrNet/data.png?raw=true

実装

github.com

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)

結果

https://github.com/Wanwannodao/DeepLearning/blob/master/RNN/PtrNet/loss.png?raw=true

ある程度それっぽい出力をしている例
https://github.com/Wanwannodao/DeepLearning/blob/master/RNN/PtrNet/eval_6.png?raw=true
[ 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]
https://github.com/Wanwannodao/DeepLearning/blob/master/RNN/PtrNet/eval_8.png?raw=true
[ 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]
https://github.com/Wanwannodao/DeepLearning/blob/master/RNN/PtrNet/eval_18.png?raw=true
[ 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]

https://github.com/Wanwannodao/DeepLearning/blob/master/RNN/PtrNet/eval_63.png?raw=true
[ 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]
https://github.com/Wanwannodao/DeepLearning/blob/master/RNN/PtrNet/eval_75.png?raw=true
[ 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]
https://github.com/Wanwannodao/DeepLearning/blob/master/RNN/PtrNet/eval_84.png?raw=true
[ 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 \deltaを用いる.
直感的には、どれだけ"驚いたか"、どれだけ予想していない遷移だったかを表し、bootstrappingした推定値と実測値がどの程度離れていたかを示す尺度.

greedy TD-error prioritization

最も単純な考え方で、TD-errorの絶対値が最大のものをリプレイする.
新しい遷移は、最低1回はサンプリングされることを保証するために最高の優先度で格納される.
メモリサイズをNにスケールさせるために、優先度キューにはバイナリヒープを用いる.
そうするとサンプリングがO(1)で、追加がO(\log N)で可能.

stochastic prioritization

greedy TD-error prioritizationにはいくつか問題点がある.

  • リプレイされたTD-errorのみを更新するので、最初が低いTD-errorだと、長期間放置され得る
  • ノイズのスパイクに過剰反応してしまう(確率的な報酬の場合など). 特にbootstrappingの場合だと、より顕著.
  • 局所的な遷移(TD-error大きいものが頻繁にリプレイされる)しか見ないので学習が遅くなる. 多様性がなくなるので、overfittingの元となる.

確率的なサンプリングによって、uniform(通常のER)とgreedyの中間的なことをする.

どういう確率分布を考えるか?

  • 優先度に関して単調
  • 低い優先度でも非ゼロ

これを踏まえて、遷移iのサンプリング確率を以下で定義する.
{ \displaystyle
P(i) = \frac {p_i^{\alpha}}{\sum_k p_k^{\alpha}}
}
p_i > 0は遷移iの優先度、\alphaはどの程度優先度を重視するかに対応するハイパーパラメータ(\alpha=0ならばuniform)

Proportional Prioritization ( direct )

p_i = |\delta_i| + \epsilon, \epsilonは小さい正定数でTD-errorが0になっても、それ以降サンプリングされないことを防ぐ.
( proportionalについては今回は割愛する )

Rank-based Prioritization ( indirect )

\displaystyle p_i = \frac{1}{rank(i)}, rank(i)は、遷移が|\delta_i|に従ってリプレイメモリに格納された時の順位.
この場合、
{ \displaystyle
P(i) = \frac { \biggl(\frac{1}{rank(i)} \biggr)^{\alpha}}{\sum_k \biggl(\frac{1}{rank(k)} \biggr)^{\alpha}} \\
= const. \biggl(\frac{1}{rank(i)} \biggr)^{\alpha}
}
となるので、Pはスケーリング指数\alphaの冪乗則分布となる.
propotionalと比べて、外れ値に対して過剰反応しないのでよりロバスト性が期待できる(らしい)

サンプリングを効率化するには、計算コストは Nに依存してはならない.

  1. 積分布関数をk個の等確率区間から成る区分線形関数で近似する. 区間の境界はあらかじめ計算される(N\alphaに依存する)
  2. 区間をサンプリングする.
  3. 区間からランダムサンプリングする.

ミニバッチベースの場合、kをミニバッチサイズに設定し、各区間から1遷移をサンプリングする.
これは、層状抽出法(stratified sampling)に対応する.
利点としては、バランスの取れたミニバッチが生成できる.

以下は、自分の実装方法も含めた全体の概略図.
f:id:wanwannodao:20170331180557p:plain

Annealing the bias

PRはこのサンプリングの分布を変化させるような"bias"を生じるので、確率的更新による期待値の推定値の収束する値も変わってしまう.
これをImportance Sampling(IS)によって修正する.
{\displaystyle
w_i = \biggl( \frac{1}{N} \cdot \frac{1}{P(i)} \biggr)^{\beta}
}
(分子くる分布はは一様分布ということ??)
{\beta=1}の場合、完全なISを行うことに対応する.
Q-learningの枠組みではTD-targetをこれで重み付けすればよく、\delta_iの代わりにw_i\delta_iを用いる.
安定性の理由から、重みは\frac{1}{`\max_i w_i}で正規化する.

指数\betaを学習の終了時に1に到達するようにスケジューリングする. (更新にbiasがないことは収束する付近では重要な性質)
例えば、初期値\beta_0から線形的に1に近づける.
(アニーリングする理由は、full IS({\beta=1})の場合重みが小さくなって初期の学習が遅くなるから??)

配列ベースのバイナリヒープによる優先度付きキューを近似的にソートされた配列として使用する.
木が不均衡になりすぎないように,10^6ステップ毎にソートしなおす.
(毎回完全にソートした配列を利用した場合と比較してあまり性能的な変化はなかった)
αとβはたまに更新する.

\beta: とれだけbiasを修正するか
\alpha: どれだけサンプリングの優先度を重要視するか

実装

github.com

データ構造

上図に示したように、一番下は通常の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
今回も時間とメモリの都合上完全な再現はできなかったが、
\alpha=0.7
\beta=0.5 to 1.0
メモリサイズ 50000
 \epsilon = 1.0 to 0.01 (1M step)
target net の更新は30000step毎
ネットワークの構成は"Tuned" Double-DQN
で行った.
f:id:wanwannodao:20170331193114p:plain

右肩上がりの段階で止めてしまったのが惜しい.
追い追い、各手法を比較できればと思う.

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は以下の形であった.
{
\newcommand{\argmax}{\mathop{\rm argmax}\limits}
\displaystyle
R_{t+1} + \gamma \max_aQ(S_{t+1}, a; \theta_t) \\
\displaystyle = R_{t+1} + \gamma Q(S_{t+1}, \argmax_a Q(S_{t+1}, a; \theta_t); \theta_t) 
}
つまり、greedy policyに基づく行動の選択と、その価値の推定は同じQ関数に基づいている.
これは過大評価に繋がりやすく、楽観的(optimistic)な価値の評価になりやすい.

そこで選択と推定を分離することを考える.
つまり、パラメータは\theta\theta'があり、一つはgreedy policyの行動選択に、もう一つは価値の推定に使われる.
するとTD-targetは以下のようになる.
{ \newcommand{\argmax}{\mathop{\rm argmax}\limits}
\displaystyle
R_{t+1} + \gamma Q(S_{t+1}, \argmax_a Q(S_{t+1}, a; \theta_t); \theta_t') 
}

二つの価値関数をランダムに選んだ別個の経験(experience)からそれぞれを更新する.
\theta\theta'の役割を交互に変えることで更新する.
(よくわかってない)

推定誤差によるOveroptimism

過大評価の上界(Thrun and Schwartz (1993))

action-valueが[-\epsilon,\epsilon]の一様分布に従う誤差を含んでいる場合、
過大評価の上界は{\displaystyle \gamma \epsilon \frac{m-1}{m+1}  } (mは行動数)

過大評価の下界

価値の推定が平均的に正しい、{\displaystyle \sum_a(Q_t(s, a)-V_{*}(s))=0 }
が、どこかで何かしらの誤差が生じている{\displaystyle \frac{1}{m} \sum_a (Q_t(s,a)-V_{*}(s))^2 = C } (C>0)
ような時、{\displaystyle \max_a Q_t(s,a) \geq V_{*}(s) + \sqrt{\frac{C}{m-1}}}
となることが証明されている. つまり真値より高く推定(過大評価)してしまう.
また、同じ条件でDouble Q-learningの場合、絶対値誤差の下界が0になることも証明されている.

この式から、下界としては行動数mが増えると小さくなるが、これはあくまで下界の話で、
一般的には行動数が増えると真値との誤差も大きくなる.
またDouble Q-learningの場合は行動数が増えても誤差が小さいことも実験的に示されている.

価値関数と近似関数の柔軟性

真の価値関数をサンプリングして多項式近似した結果として、
価値関数に関わらず、また近似関数の柔軟性に関わらず過大評価は発生することが示されている.

現実的には真値ではなく、bootstrappingするのでより一層悪化する可能性がある(よってpolicyにも影響がでる).

DQNはDNNよって柔軟な関数近似を行えるが、その場合でも過大評価してしまうことがある.

(※ explorationの手法としてのoptimismとは別の話なので混同してはいけない.)

Double DQN

上述のようにDouble Q-learningは選択と評価を分離することで過大評価を回避する.
完全な分離ではないが、DQNのtarget networkが使える(別のネットワークが必要ない).

よってtarget networkのパラメータを\theta_t^{-}とすると、TD-targetは、
{ \newcommand{\argmax}{\mathop{\rm argmax}\limits} 
\displaystyle
R_{t+1} + \gamma Q(S_{t+1}, \argmax_a Q(S_{t+1}, a; \theta_t); \theta_t^{-}) 
}
となる. TD-targetが変わる以外はDQNと同じ.

DQN vs Double DQN

以下のグラフの通り、Double DQNではDQNよりも過大評価がかなり抑えられていることが確認できる.
f:id:wanwannodao:20170305134519p:plain
(論文より引用)

以下のグラフは、価値の推定値とゲームのスコアのグラフだが、過大評価が生じ始めるとスコアが下がることが見てわかる.
つまりこれは、過大評価がpolicyに悪影響を与えるということを意味している.
f:id:wanwannodao:20170305134523p:plain
(論文より引用)
DQNのこの性能悪化は、Off-Policy+関数近似の本質的な不安定性に起因したものではなく、Q-learningの過大評価に起因したものということを意味している.
(現にDouble DQNは安定している)

過大評価は必ずしも悪影響に繋がるわけではないが、減らすことで学習の安定化が図れるという事が言える.
また、Double DQNはより汎用的なpolicyを学習できる(ロバスト性が高い)ということも示されている.

※必ずしも悪影響に繋がらないとは、例えば全てのaction-valueが一様に過大評価されていれば、相対的な振る舞いは同じなので悪くはならない

Double DQN用のチューニング

DQNからDouble DQN用にハイパーパラメータ等を調整することでより高い性能が得られる.

Target Networkの更新間隔

10,000から30,000フレーム間隔に
更新した直後は通常のQ-learningに戻ってしまうので、間隔を広げる

\epsilon-greedy

\epsilon(の最終値)を学習時は0.1から0.01に、評価時は0.001に

shared bias

出力の行動価値に対するbias(最後のfc層のbiasか?)を共有する.

下二つの根拠はわからなかった.

実装

github.com

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ステップで\epsilonが0.01に到達する設定なので、あまり学習が進んでいないかもしれない.
f:id:wanwannodao:20170313182321p:plain

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

{\displaystyle
Q(S_t,A_t) \leftarrow Q(S_t, A_t) + \alpha \biggl(R_{t+1} + \max_{a'} \gamma Q(S_{t+1}, a') - Q(S_t, A_t) \biggr)
}
target policy {\pi} : greedy
behavior policy {\mu} : {\epsilon}-greedy
(TD-TargetにはサンプリングしたBellman Optimality Equation)

パラメータ{\mathbf{w}}関数近似した場合、
{\displaystyle
\mathbf{w} \leftarrow  \mathbf{w} - \alpha \biggl(r_{t+1} + \max_{a'} \gamma \hat{q}(s_{t+1}, a'; \mathbf{w})  - \hat{q}(s_t, a_t ; \mathbf{w}) \biggr) \nabla_{\mathbf{w}} \hat{q}(s_t, a_t ; \mathbf{w}) 
}

論文まとめ

そもそも、action-value(以下Q)関数を非線形関数で近似すると、RLは不安定あるいは発散することが知られている.
理由は例えば以下のようなことが挙げられる.

  • 観測間に依存関係が存在する.
  • Qを多少更新したただけでも、政策関数が大きく変わる可能性があるので、観測データの分布も依存関係も大きく変わってしまう可能性がある.

この不安定性を打破するために以下の2つを行う.

Experience Replay

生物学的なメカニズム(海馬まわり?)からの発想.
過去の観測データをランダムサンプリングして、観測間に生じる依存関係を除去することで、観測データ分布の変化を滑らかにする.
具体的には、経験e_t=(s, a, r, s')を各時刻tにおいて、バッファD_t= \lbrack e_1, ..., e_t \rbrackにプールする. Q関数を更新する時は、このバッファからランダムサンプリングしたミニバッチ(s, a, r, s') \sim U(D)で行う.

Target Network

一定間隔で更新するQ関数をTD-targetに利用する. これも依存関係を除外することに貢献している.
Q-LearningにおけるTD-Target、r + \gamma \max_{a'} Q(s', a'; \theta_i)を、Cステップ毎に更新されるパラメータ\displaystyle \theta_i^{-}で置き換える. (\theta_ii iterでのパラメータ)

DQN

以上をまとめると、DQNは以下の最小化問題を解くことになる.
{ \displaystyle
\min_{\theta_i} L_i(\theta_i)= \min_{\theta_i} \mathbb{E}_{(s,a,r,s') \sim U(D)} 
\lbrack (r + \gamma \max_{a'} Q(s', a'; \theta_i^{-}) - Q(s, a; \theta_i))^2 \rbrack
}

その他

上記の2点が中心ではあるが、その他にも学習を進める上でいくつかのことを行っている.

Error Clipping

これを行うことで更に安定性を上げている.
つまり、TD-Error r + \gamma \max_{a'} Q(s', a'; \theta_i^{-}) - Q(s, a; \theta_i)が、
(-1,1)の外側の場合は絶対値誤差を、内側の場合は二乗誤差利用する.
これは、Hurber Lossに対応する.

前処理、flickeringの除去

あるオブジェクトは偶数フレームにしか現れないなどの現象(flickering)を回避するために、前フレームと現フレームの最大値を1フレームとする.
更にこれを、グレースケール化して、84x84にリサイズする.
直近の4フレームにこの前処理を施したものを1ステートとする.

他frame skipping, reward scaling

実装

github.com

前処理

# 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 + \gamma \max_{a'} Q(s', a'; \theta_i^{-})

# 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)

Q(s, a; \theta_i)

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)

\epsilon-greedy

if np.random.rand() < epsilon:
    a = env.action_space.sample()
else:
    a = dqn.greedy(s, sess)

\epsilon-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程度.
機会があったらもっと長い時間学習させたい.
f:id:wanwannodao:20170312185804p:plain

強化学習基礎(メモ書き)

強化学習基礎

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

{ \displaystyle
\mathbb{P} \lbrack S_{t+1} | S_{t} \rbrack = \mathbb{P} \lbrack S_{t+1} | S_{1}, ..., S_{t} \rbrack
}
これの意味するところは、未来が現在のみに依存し、過去とは独立しているということ.

MPは{ \langle \mathcal{S}, \mathcal{P} \rangle }の組で定義され、{\mathcal{S}}は有限の状態集合、{\mathcal{P}}は状態遷移確率行列で、
{\displaystyle
\mathcal{P}_{ss'} = \mathbb{P} \lbrack S_{t+1} = s' | S_{t} = s \rbrack
}
である.

MRP (Malkov Reward Process)

MPにスカラー値が加わったもので、{ \langle \mathcal{S}, \mathcal{P}, \mathcal{R}, \gamma \rangle }の四つ組で定義される.
{\mathcal{R}}はreward function(報酬関数)で、{\mathcal{R}_s = \mathbb{E} \lbrack R_{t+1} | S_t = s \rbrack}
{\gamma}はdiscount factor(割引率)で、{\gamma \in \lbrack 0, 1 \rbrack} である.

Return

ここでreturnという量を定義する.
return {G_t}とは、時刻{t}からの割り引かれた報酬の合計値.
つまり、
{ \displaystyle
G_t = R_{t+1} + \gamma R_{t+2} + ... = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} 
}

なぜ割引?

discount factorの直感的なイメージは、将来の報酬の、現在の値とみることができる.

  • returnの発散を回避する
  • 将来への不確実性
  • 即時的な報酬の方が重要な場合など
  • 動物は基本的に即時的な報酬の方を重要視する
  • など
Value Function

returnの期待値としてvalue function(価値関数)を定義する.
{\displaystyle
v(s) = \mathbb{E} \lbrack G_t | S_t = s \rbrack
}

Bellman Equation

このvalue functionは二つの量に分解することができる.
{\displaystyle
\begin {equation}
\begin {split}
v(s) &= \mathbb{E} \lbrack G_t | S_t = s \rbrack \\
&= \mathbb{E} \lbrack R_{t+1} + \gamma G_{t+1} | S_t = s \rbrack \\
&= \mathbb{E} \lbrack R_{t+1} + \gamma v_(S_{t+1}) | S_t = s \rbrack
\end {split}
\end{equation}
}
(returnの定義からすぐ分かる)
つまり、即時的な報酬{R_{t+1}}と次の状態の割り引かれた価値{\gamma v_(S_{t+1})}に分解できた.

MDP (Malkov Decision Process)

MRPに決定が加わったもので、{ \langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \rangle }の五つ組で定義される.
{ \mathcal{A} }は、有限な行動の集合
状態遷移確率と報酬も行動に依存するようになるので、
{\displaystyle
\mathcal{P}_{ss'}^a = \mathbb{P} \lbrack S_{t+1} = s' | S_{t} = s, A_{t} = a \rbrack
}
{\mathcal{R}_s^a = \mathbb{E} \lbrack R_{t+1} | S_t = s, A_t = a \rbrack}
これが環境に対応する.

Policy

行動が加わったのでpolicyというものを定義する
{\displaystyle 
\pi(a|s) = \mathbb{P} \lbrack A_t = a | S_t = s \rbrack
}
これは、ある状態での取り得る行動の確率分布を表し、エージェントの振る舞いを決定する.

state-value & action-value function

MDPにおけるstate-value function(状態価値関数)とは
{\displaystyle 
v_{\pi}(s) = \mathbb{E}_{\pi} \lbrack G_t | S_t = s \rbrack 
}
これはpolicy {\pi}に従った場合の、状態{s}からの将来のreturnの期待値で、その状態の価値を表す.
MDPにおけるaction-value function(行動価値関数)とは
{\displaystyle
q_{\pi}(s, a) = \mathbb{E}_{\pi} \lbrack G_t | S_t = s, A_t = a \rbrack
}
これはpolicy {\pi}に従い、状態{s}にいる時に行動{a}を取る時の将来のreturnの期待値で、その行動の価値を表す.

Bellman Expectation Equation

さて、MRPの場合と同様にこれらは、即時的な報酬と、割引された未来の報酬に分割することができる
{\displaystyle 
v_{\pi}(s) = \mathbb{E}_{\pi} \lbrack R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t = s \rbrack 
}
{\displaystyle
q_{\pi}(s, a) = \mathbb{E}_{\pi} \lbrack R_{t+1} + \gamma q_{\pi}(S_{t+1}, A_{t+1}) | S_t = s, A_t = a \rbrack
}
{\pi}を定義したので、状態遷移確率と併せて期待値の部分を展開してみる.
{\displaystyle 
\begin{equation}
\begin{split}
v_{\pi}(s) &= \sum_{a \in \mathcal{A} } \pi(a|s)q_{\pi}(s, a) \\
&= \sum_{a \in \mathcal{A}} \pi(a|s) \biggl( \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a v_{\pi}(s') \biggr)
\end{split}
\end{equation}
}
{\displaystyle 
\begin{equation}
\begin{split}
q_{\pi}(s, a) &= \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a v_{\pi}(s') \\
&= \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a \sum_{a' \in \mathcal{A} } \pi(a'|s')q_{\pi}(s', a')
\end{split}
\end{equation}
}

Optimal value function

最適なstate-value functionとaction-value functionを次のように定義する.
{ \displaystyle
v_{*}(s) = \max_{\pi} v_{\pi}(s) \\
\displaystyle
q_{*}(s, a) = \max_{\pi} q_{\pi}(s, a)
}

Optimal Policy

policyに関して次の半順序を定義する
{\displaystyle
\pi \geq \pi^{'} if v_{\pi} \geq v_{\pi^{'}},  \forall s
}
この時、最適なpolicyとは
{\displaystyle
\pi_{*} \geq \pi, \forall \pi
}
であり、このようなpolicyが存在し、{\pi_{*}}{v_{*}(s)}{q_{*}(s, a)}を達成するという定理がある.
また、最適なpolicyは以下のように得ることができ、決定的なpolicyである.
{\displaystyle
\begin{eqnarray}
\pi_{*}(a|s) = \left\{ \begin{array} {}
1 & if \; a = \displaystyle \arg \max_{a \in \mathcal{A}} q_{*}(s, a) \\
0 & otherwise
\end{array} \right. 
\end{eqnarray}
}

Bellman Optimality Equation

最適なpolicyを仮定した時のBellman Equation. Bellman Expectation Equationと区別しておくことがとても重要
{ \displaystyle
\begin{equation}
\begin{split}
v_{*}(s) &= \max_{a} q_{*}(s, a) \\
&= \max_{a} \biggl( \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a v_{*}(s') \biggr)
\end{split}
\end{equation}
}
{
\begin{equation}
\begin{split}
\displaystyle
q_{*}(s, a) &= \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a v_{*}(s') \\
&= \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a \max_{a'} q_{*}(s', a')
\end{split}
\end{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)というアプローチが存在する.
どちらの手法もイテレーティブに価値関数を更新して評価するのだが、以下の形で表現できる.
{\displaystyle
V(S_t) \leftarrow V(S_t) + \alpha ( return - V(S_t))
}
真のreturnの方向に修正していく. が、真returnは未知なのでこれを何かしらに置き換える.
MCの場合はreturnとして実際に観測した{G_t}を利用するのに対して、TD(0)の場合はreturnの予測値{R_{t+1} + \gamma V(S_{t+1}) }を使う.
したがって、MCでは{G_t}を得るために"episodic"でないといけないし、offlineであり、完全なepisodeを必要とする.
TD(0)の場合は、bootstrappingするのでonlineで、しかも不完全なepisodeから学習することが可能である.

MCには深く立ち入らないでTDに焦点を当てていく.
改めてTD(0)の更新式は、
{\displaystyle
V(S_t) \leftarrow V(S_t) + \alpha ( R_{t+1} + \gamma V(S_{t+1}) - V(S_t))
}
で、{R_{t+1} + \gamma V(S_{t+1}) }TD Target{\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t) }TD Errorと呼ぶ
TD({\lambda)}に拡張できるのだが、とりあえずここではTD(0)にとどめる.

Model-free Control (Policy Improvementの Sample backup版)

value functionを最適化することを考える.
今まで、{V(S)}、つまりstate-valueについて考えていたが、ここでgreedy policy(最大値を与える行動を常に取るpolicy)を想定してみると、
{\displaystyle
\pi(s) = \arg \max_{a \in \mathcal{A}} \mathcal{R}_s^a + \mathcal{P}_{ss'}^a V(S')
}
である.
状態遷移確率{\mathcal{P}_{ss'}}、つまり環境のモデルが必要になってきてしまう.
一方で、action-valueの場合は、
{\displaystyle
\pi(s) = \arg \max_{a \in \mathcal{A}} Q(s, a)
}
これはmodel-free.
したがって、action-valueに基づいて更新を行うことにする.

{\epsilon }-greedy exploration

ここで{\epsilon }-greedyという考え方を定義する.
確率{1-\epsilon }でgreedyな行動を、確率{\epsilon }でランダムな行動を取るというもの.

 { \displaystyle
\begin{eqnarray}
\pi(a|s) = \left\{ \begin{array} {}
\frac{\epsilon} {m} + 1 - \epsilon & if \; a^{*} = \displaystyle \arg \max_{a \in \mathcal{A}} Q(s, a) \\
\frac{\epsilon} {m} & otherwise
\end{array} \right. 
\end{eqnarray}
}
{m}は行動数
これによってPolicy Improvementを行えば{v_{\pi'}(s) \geq v_{\pi}(s)}となるという定理がある.

GLIE (Greedy in the Limit with Infinite Exploration)

全てのstate-actionペアが無限回探索される時、policyがgreedy policyに収束するような探索方法.

例えば、{\epsilon}-greedyで{\epsilon}が0に収束するようなものならば、GLIEである.

On-Policy TD Control (Policy IterationのSample backup版)

Sarsa(0)

Policy Evaluationは以下の更新式に基づく、
{\displaystyle
Q(s, a) \leftarrow Q(s, a) + \alpha (R + \gamma Q(s', a') - Q(s, a))
}
Policy Improvement{\epsilon}-greedy policy に基づいて更新する
returnの予測値は現在の状態{s}において行動{a}を取った時の次の状態{s'}において、policy {\pi}に従って行動{a'}を選んだ場合の予測値になっている.
ここで、(サンプルした)Bellman Expectation Equationに基づいていることを再確認したい.
GLIEかつステップサイズ{\alpha}がRobbins-Monro(略)になっていれば最適なaction-value functionに収束する定理が存在する.

Off-Policy Control (Value IterationのSample backup版)

Off-Policyでは、target policy {\pi(a|s)}を評価するのだが、行動自体はbehavior policy {\mu(a|s)}に従って行う.
なぜそんなことをするのか??

  • ひとつのpolicyに従いながら、複数のpolicyについて学習できる
  • 探索的なpolicyに従いながら、最適なpolicyについて学習できる
  • 例えば、他の人がどう動いているのだろうということを学ぶイメージ
Importance Sampling

さて、確率分布{\pi(a|s)}に関する期待値を確率分布{\mu(a|s)}で取る場合、Importance Samplingという操作を行う.
{\displaystyle
\mathbb{E}_{x \sim \pi} \lbrack f(x) \rbrack = \sum \pi(x) f(x)
= \sum \mu(x) \frac {\pi(x)} {\mu(x)} f(x)
= \mathbb{E}_{x \sim \mu} \lbrack \frac  {\pi(x)} {\mu(x)} f(x) \rbrack
}

例えば、TD(0)のPolicy Evaluationはインクリメンタルな更新なので、以下のようになる
{\displaystyle
V(S_t) \leftarrow V(S_t) + \alpha \biggl( \frac{\pi(A_t|S_t)}{\mu(A_t|S_t)}(R_{t+1} + \gamma V(S_{t+1})) - V(S_t) \biggr)
}

だがしかし、こんなことは必要ない、そうQ-Learningならね.

Q-Learning

{\displaystyle
Q(S_t,A_t) \leftarrow Q(S_t, A_t) + \alpha (R + \gamma Q(S_{t+1}, A') - Q(S_t, A_t))
}
returnの予測値は、状態{S_t}において{\mu}に従って行動{A_t}を取った時の次の状態{S_{t+1}}において、{\pi}に従って行動{A'}を取る時の予測値となっている.

{\pi}{\mu}を具体的に定義する.

  • {\pi}はgreedy policy、{\displaystyle \pi(S_{t+1}) = \arg \max_{a'} Q(S_{t+1}, a')   }
  • {\mu}{\epsilon}-greedy policy

従って、
{\displaystyle
R_{t+1} + \gamma Q(S_{t+1}, A') = R_{t+1} + \gamma Q(S_{t+1}, \arg \max_{a'} Q(S_{t+1}, a') ) = R_{t+1} + \max_{a'} \gamma Q(S_{t+1}, a')
}
ここで、(サンプルした)Bellman Optimality Equationに基づいていることを再確認しておきたい.
Q-Learningは最適なaction-value functionに収束するという定理がある.

関数近似

今までの話をスケールアップさせる上では、value functionを近似することが必要不可欠となる.
ちなみに、今までの収束の話は関数近似した場合、必ずしも成立しなくなる.

確率的勾配降下法(SGD)

今、{\mathbf{w}}でパラメータ化されたvalue functionを{\hat{v}(S, \mathbf{w}) }、真のvalue functionを{v_{\pi}(S)}とした時、以下の最小化問題を解きたい.
{\displaystyle
\min_{\mathbf{w}} J(\mathbf{w}) = \min_{\mathbf{w}} \mathbb{E}_{\pi} \lbrack ( v_{\pi}(S) - \hat{v}(S, \mathbf{w}) )^2\rbrack
}

{\mathbf{w}}に関する勾配は、
{\displaystyle
\nabla_{\mathbf{w}} J(\mathbf{w}) = 2 \mathbb{E}_{\pi} \lbrack (v_{\pi}(S) - \hat{v}(S, \mathbf{w})) \nabla_{\mathbf{w}} \hat{v}(S, \mathbf{w}) \rbrack
}
よって、SDGの各ステップは以下の更新を行う
{\displaystyle
\mathbf{w} \leftarrow \mathbf{w} - \frac {1}{2} \alpha \nabla_{\mathbf{w}} J(\mathbf{w}) = \mathbf{w} - \alpha (v_{\pi}(S) - \hat{v}(S, \mathbf{w})) \nabla_{\mathbf{w}} \hat{v}(S, \mathbf{w}) 
}
期待値でないのは"確率的"勾配降下であるから(勾配をサンプリグする).
インクリメンタルな平均値の更新をイメージすれば、これが期待値になっていくことが直感的にわかる.

ここにおいても、{v_{\pi}(S)}を何かしらに置き換えるわけだが、TD(0)の場合(Policy Evaluation)は、TD Targetで置き換えて、
{\displaystyle
\mathbf{w} \leftarrow  \mathbf{w} - \alpha \biggl(R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w})  - \hat{v}(S_t, \mathbf{w}) \biggr) \nabla_{\mathbf{w}} \hat{v}(S_t, \mathbf{w}) 
}
これは、action-valueについても同様で、
{\displaystyle
\mathbf{w} \leftarrow  \mathbf{w} - \alpha \biggl(R_{t+1} + \gamma \hat{q}(S_{t+1}, A_{t+1}, \mathbf{w})  - \hat{q}(S_t, A_t, \mathbf{w}) \biggr) \nabla_{\mathbf{w}} \hat{q}(S_t, A_t, \mathbf{w}) 
}

では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のアプローチというのは、自分の分布{ \mathbb{P}_\theta }を真の分布{\mathbb{P}_r }に近づけていくというものだが、この分布間の距離/ダイバージェンスの定義の仕方によって、学習の収束性、安定性に差異がある.
基本的な距離/ダイバージェンスの定義としては以下の4つがある.
{\mathbb{P}_r }{\mathbb{P}_g }はあるコンパクト空間{\mathcal{X}}上で定義される確率分布.(コンパクト空間は距離空間においては、有界閉集合をイメージすればよいらしい. ここでは画像の空間({\lbrack 0,1 \rbrack^d} )と思っていてよい)

  • Total Variation (TV) distance

{\displaystyle
 \delta(\mathbb{P}_r , \mathbb{P}_g) = \sup_{A \in \sum} |\mathbb{P}_r(A) - \mathbb{P}_g(A)| }
省略

  • Kullback-Leibler (KL) divergence

{\displaystyle
 KL(\mathbb{P}_r || \mathbb{P}_g) = \int \log( \frac{\mathbb{P}_r(x)}{\mathbb{P}_g(x)} ) \mathbb{P}_r(x) d\mu(x)
}
非対称、発散する可能性がある

  • Jensen-Shannon (JS) divergence

{\displaystyle
  JS(\mathbb{P}_r , \mathbb{P}_g) = KL(\mathbb{P}_r || \mathbb{P}_m) + KL(\mathbb{P}_g || \mathbb{P}_m) \\
  \mathbb{P}_m = \frac {\mathbb{P}_r + \mathbb{P}_g} {2}
}
対称、常に定義可能
GANは近似的にこれを最小化することに対応する

  • Earth-Mover (EM) distance (Wasserstein-1)

{\displaystyle
  W(\mathbb{P}_r , \mathbb{P}_g) = \inf_{\gamma \in \prod (\mathbb{P}_r , \mathbb{P}_g)}  \mathbb{E}_{(x,y) \sim \gamma} \lbrack ||x-y|| \rbrack
}

{\gamma(x,y)}の直感的理解は、{\mathbb{P}_r}{\mathbb{P}_g}に変えるために、地点{x}から地点{y}どれだけの"質量"を移動しなければならないかという量.
よってEM距離は直感的には最適な輸送コストと考えれば良い.
({\prod}は同時分布を表す)

以下JSとEMだけ考えることにする.
次の簡単な状況下での距離の変化を観測してみる.
{ \displaystyle
 Z \sim U \lbrack 0,1\rbrack} (一様分布)
{\mathbb{P}_0}: 確率分布 {(0, Z) \in \mathbb{R}^2 }
{g_{\theta}(z) = (\theta, z), \theta}: パラメータ
簡単に言うと、二直線間の距離みたいなイメージか.
すると各距離は以下の通り.

{\displaystyle
W(\mathbb{P}_r , \mathbb{P}_g) = |\theta| \\
\begin{eqnarray} 
JS(\mathbb{P}_r , \mathbb{P}_g) = \left\{ \begin{array}{}
\log 2 & if \theta \neq 0, \\
0 & if \theta = 0
\end{array} \right.
\end{eqnarray}
}

よって下図のようなグラフが描ける.
(左がEM、右がJS)
f:id:wanwannodao:20170228033758p:plain
(論文より引用)


この図からわかることは、EM距離は連続かつ有用な勾配(距離の直感に合う)JS距離は非連続かつ距離の直感に合わない

論文では、諸定理を証明してEM距離が他の尺度より有利な性質を持っていることを述べている.
どうにかEM距離をロス関数として使いたいのだが、定義通りだと難しい...

どうするか??
まず、次のような双対問題が存在する.

  • Kantorovich-Rubinstein duality

{\displaystyle
  K \cdot W(\mathbb{P}_r , \mathbb{P}_g) = \sup_{||f||_L <= K} \mathbb{E}_{x \sim \mathbb{P}_r \lbrack f(x) \rbrack} - \mathbb{E}_{x \sim \mathbb{P}_{\theta} \lbrack f(X) \rbrack}
}
{K}はある定数で、関数{f}{K}-Lipschitz連続
{K}-Lipschitz連続性の直感的な理解としては、関数の傾きがある定数{K}で抑えられるような一様連続性であると思っている.

であるから、以下のような問題を考えればよい
{ \displaystyle
 \max_{w \in \mathcal{W}} \mathbb{E}_{x \sim \mathbb{P}_r} \lbrack f_w(X) \rbrack - \mathbb{E}_{x \sim p(z)} \lbrack f_w(g_{\theta}(z) \rbrack
}

{\lbrace f_w {\rbrace}_{w \in \mathcal{W}}}はパラメータ化された関数で、GANの枠組みではDiscriminatorに対応する(論文中ではCritic)であり、{K}-Lipschitz連続とする.
もし、先程の双対問題の上限が{w \in \mathcal{W}}によって得られるならば、この最大化問題で{W(\mathbb{P}_r , \mathbb{P}_g)}の定数倍を計算することができる.
{g_{\theta}(z)}は、{\mathbb{P}_{\theta}}に従って、ある分布(ex. Gaussian)に従う確率変数{z}{\mathcal{X}}(画像の空間)にマッピングする関数で、GANのGeneratorに対応するもの. (これが連続ならば、{W(\mathbb{P}_r , \mathbb{P}_g)}も連続となることも証明されている.)
さて、{\theta}に関する勾配が以下になることも定理として示されている.
{\displaystyle
\nabla_{\theta} W(\mathbb{P}_r , \mathbb{P}_g) = -\mathbb{E}_{z 
\sim p(z)} \lbrack \nabla_{\theta} f(g_{\theta}(z)) \rbrack
}

利点
  • 学習の収束性、安定性
  • 意味のある、しかも出力画像の質と相関するロス
  • DiscriminatorとGeneratorの学習の進み具合を調整する必要がない
  • Mode Collapseがない

実装

上でいろいろ書いたが実装に際してはやることは至って簡単.
(Critic = Discriminator)

  1. Criticを何回か更新して、{W(\mathbb{P}_r , \mathbb{P}_g)}の良い近似をする
  2. {f_w}(Critic)の{K}-Lipschitz連続性を保つ
  3. Generatorを{W(\mathbb{P}_r , \mathbb{P}_g)}を最小化する方向に更新する.

{W(\mathbb{P}_r , \mathbb{P}_g)}の計算

これは、上で述べた双対問題から出てきた最大化問題を解くので、以下の確率的勾配を昇る方向に更新する.
よって実装上は、符号反転して最小化問題とする.
{ \displaystyle
 - \nabla_w \lbrack \frac{1}{m} \sum_{i=m}^{m} f_w(x^{(i)}) - \frac{1}{m} \sum_{i=m}^{m} f_w(g_{\theta}(z^{(i)})) \rbrack
}

{f_w}(Critic)の{K}-Lipschitz連続性

パラメータ空間{ \mathcal{W}}がコンパクト空間(有界閉集合)なら{f_w}(Critic)の{K}-Lipschitz連続であることを意味する(らしい).
これは、weight clippingをするだけで達成可能である.

{W(\mathbb{P}_r , \mathbb{P}_g)}を最小化する

GeneratorはEM距離を最小化するので、次の確率的勾配を降る方向に更新する.
{\displaystyle
 - \nabla_{\theta} \frac{1}{m} \sum_{i=m}^{m} f_w(g_{\theta}(z^{(i)})
}

以上をまとめると以下のような雰囲気になる.

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)

結果

https://github.com/Wanwannodao/DeepLearning/blob/master/GAN/WGAN/image_0.png?raw=true

https://github.com/Wanwannodao/DeepLearning/blob/master/GAN/WGAN/image_19.png?raw=true

https://github.com/Wanwannodao/DeepLearning/blob/master/GAN/WGAN/loss.png?raw=true

確かに学習が進むに連れて、ロスも減っていくことは確認できたが最初の方の動作がよくわからなかった.
どっかで目にしたことだが、DCGANなどより多少ぼやけているか.