ベルマン方程式

ベルマン方程式は、動的計画法(動的な最適化問題)の最適性の必要条件を表す方程式らしい。必要条件は、再帰を使って部分を解くことで全体が解ける状態にあることと、メモ化を使うことです。最適化問題とは、集合内のすべての数値を、ある関数にいれたときに最小あるいは最大となる集合内の元を探すことを目的とする問題のことです。

動的計画法において、問題の目的を数式で表したものを目的関数といいます。

xは状態です。aは行動です。tは時間です。βは割引率です。F(x, a)は、状態xのときに行動aをとることで得られる報酬が出力される関数です。この式は、報酬を最大化させることが目的になっています。割引率は0 < β < 1で、0であればどの時間tに得られた報酬も同じ重さで扱います。1に近ければ未来のtで得られた報酬程重要視します。t100のときの報酬は、βの100乗が掛けられるからです。 この式は再帰可能な形態に変形できます。まず下記のようにします。

最初のx0のときの報酬だけ左に出しました。βも一つ左に出すことで、右の式はt0がt1になっただけで、あとは上記の式とまったく同じです。よって下記のように書けます。

これを下記のように簡単に書いたのが、ベルマン方程式だそうです。

なぜ、上の式のx1が、下ではT(x, a)に変わっているかというと、T(x, a)は、状態xのときに、行動aをとった場合に次に遷移する状態を返す関数として定義しているからです。変数の添え字を消したかったのでこれを使っています。

強化学習の勉強に良さそうなサイト一覧

OpenAI Gym
Pythonではじめる強化学習
深層強化学習:ピクセルから『ポン』 – 前編
深層強化学習:ピクセルから『ポン』 – 後編
超シンプルにTensorFlowでDQN (Deep Q Network) を実装してみる 〜解説編② 学習の流れを理解する〜
PyBrainを用いて強化学習をしてみた
Q学習(Q-Learning)やバンディットアルゴリズムなどの強化学習のデモ用のコードを公開して保守していくことにした。
path-finding-q-learning-tutorial
DQNをKerasとTensorFlowとOpenAI Gymで実装する
強化学習で参考になったサイトまとめ
Q学習で最良経路をPythonで求めてみる

Python3 – 動的計画法(フィボナッチ数列)

動的計画法は、分割統治法メモ化を合わせた方法のことらしい。分割統治法は、問題を細分化して、細かい部分を順に解いていくことで全体を解明するようなことの総称らしい。

分割統治法は、コード的には下記のようになり、再帰することになる。

メモ化とは、再帰の際に同じ副問題を複数回解いてしまうことによる効率低下を防ぐために、副問題の結果を保存して再利用することらしい。キャッシュみたいな感じ。

下記のフィボナッチ数列を表示するプログラムは、動的計画法の具体的な例らしい。

Python3だと下記のような感じ。

ちなみに、ネットでフィボナッチ数列のPython版しらべたら下記がでてきたけど、これはまさしく動的計画法じゃない例だと思った。毎回メモらずに計算しているようだ。

せっかくだから時間図ってみる。

結果

おー40倍速いってことか。さすが動的計画法だ。

下記のような方法もある。

greedyアルゴリズム(貪欲法)

greedyアルゴリズムは、全部をN回試して、報酬の平均が最も高いやつを選択するというアルゴリズムです。

当たりか外れがでる機械が4個あって、どれが一番当たり率が高いか分からないのでgreedyアルゴリズムでやってみる想定にします。機械はa~dまであってそれぞれ当たり率は下記のとおりとします。

a b c d
0.3 0.6 0.8 0.95

当たりが出たら1点もらえて、外れたら0点とします。

結果

Python3 – random

randomを試してみます。

下記をやってみます。100回randintを0~100まででやってみます。

結果

10000回やってみます。

100000回やってみます。

100万回やってみます。

seed設定してみます。

何回やっても、下記でした。

何回やっても下記でした。

seedが同じだと、プログラムを実行する度に、まったく同じ数字が同じ順番ででてくる。

60%の確率で正解を出す機械をつくってみます。
random.random()が0.6以内だったら当たりにします。

結果

手書き文字を作れるJavascriptをつくってTensorFlowで予測させてみた(2)

この前、「手書き文字を作れるJavascriptをつくってTensorFlowで予測させてみた」という投稿でブラウザ上で手書きした文字画像を、MNISTで訓練したモデルで予測してみましたが、ものすごく精度が悪かったです。今回改めて、CNNを使ってやってみたらかなり精度が上がりました。何%か測ったりしてませんが、自分の手書きだと90%は超える感じでした。やっぱりCNNはすごいなーと思いました。でももしかしたら前回のものにミスがあり、CNNではなくても精度は本当はもっと高い可能性はあります。

もうちょっとやるとしたら、文字を画像の中心に適度な大きさで書く必要があり、例えば右上に小さく2と書いても認識されません。あとは、現在はMNISTに合わせて、手書き文字画像も背景黒、文字色白で作成するように固定していますが、これらの色を変えても認識するようにしたいです。今度やってみます。

Github

https://github.com/endoyuta/mnist_test

index.html

cgi-bin/mnist.py

cgi-bin/mytensor.py

TensorFlow – Local Response Normalization(LRN)(局所的応答正規化)

参考:theanoで局所コントラスト正規化(Local Contrast Normalization)を使う

正規化の方法にはいろいろあり、代表的なものを挙げると

Global Contrast Normalization(GCN)
Local Contrast Normalization(LCN)
Local Response Normalization(LRN)
ZCA whitening
Local mean subtraction

CNN内の正規化層としては、LCNやらLRNが使われる。

LCNはその名の通り、特徴マップの局所領域内でコントラストを正規化する。この処理は一つの特徴マップ内で完結するので、すべての特徴マップに対して独立して行う。
対してLRNでは、同一位置における異なる特徴マップ間で正規化する。どちらもいくつかのハイパーパラメータはあるが、学習の対象となるパラメータはないので、誤差伝播が容易に可能である。

参考:theanoでLocal Response Normalization(LRN)を使う

LRNは端的に述べると、「同一位置(ピクセル)において複数の特徴マップ間で正規化する」ということだそうだ。元の論文にも書いてあるが、LRNは”brightness normalization”であり、LCNのように輝度の平均を減算して0にしないことがミソらしい。


$$\displaystyle
b^i_{x,y}=a^i_{x,y}/ \left( k+\alpha \sum^{min(N-1,i+\frac{n}{2})}_{j=max(0,i-\frac{n}{2})} (a^j_{x,y})^2 \right)^\beta
$$

k, n, α, βがパラメータである{a^i_{x,y}}はi番目の特徴マップの(x,y)のピクセルを、Nは特徴マップの総数を表す。
summationの部分は、「i番目の特徴マップに対して、n近傍の特徴マップの二乗和をとる」という意味である。

参考:tf.nn.local_response_normalization(input, depth_radius=None, bias=None, alpha=None, beta=None, name=None)

Local Response Normalization.

The 4-D input tensor is treated as a 3-D array of 1-D vectors (along the last dimension), and each vector is normalized independently. Within a given vector, each component is divided by the weighted, squared sum of inputs within depth_radius. In detail,

翻訳結果

4次元入力テンソルは、(最後の次元に沿って)1次元ベクトルの3次元配列として扱われ、各ベクトルは独立して正規化されます。 所与のベクトル内で、各成分は、depth_radius内の入力の加重二乗和で除算される。

使用例

Python3で関数をつくってみる

使ってみる

結果

tf.nn.lrnを使ってみる

コード

結果

おーほぼほぼ同じだ。適当な別の配列でも試してみよう。

適当な配列でも試してみる

適当な配列

結果

自作関数の結果

tf.nn.lrnの結果

ほぼ同じ。

大きい写真にLRNをしてみて結果をみてみる

画像はこれです。

コード

結果

これをCNNに入れ込むと効果が高まるって気づいた人すごいっす。

Python3 – NumpyとPythonの配列のスライスでマイナス使った場合

  • 開始位置より終了位置が小さい場合は空。
  • マイナスの場合、後ろから数える。一番最後が-1。
  • 終了位置が実際の配列の最後より大きい場合は、実際の配列の最後になる。
  • 開始位置は0だったら0番目も含まれるが、終了位置が例えば10だった場合、9番目までが含まれる。
  • 終了位置が-1だったら、-2までが含まれる。

コード

結果

TensorFlow – tf.nn.max_pool(value, ksize, strides, padding, data_format=’NHWC’, name=None)

tf.nn.max_pool(value, ksize, strides, padding, data_format=’NHWC’, name=None)

  • value: A 4-D Tensor with shape [batch, height, width, channels] and
    type tf.float32.
  • ksize: A list of ints that has length >= 4. The size of the window for
    each dimension of the input tensor.
  • strides: A list of ints that has length >= 4. The stride of the sliding
    window for each dimension of the input tensor.
  • padding: A string, either 'VALID' or 'SAME'. The padding algorithm.
    See the comment here
  • data_format: A string. ‘NHWC’ and ‘NCHW’ are supported.
  • name: Optional name for the operation.

max poolingは、特定の領域から最大の数字を取り出します。ksizeが領域の大きさ、stridesが間隔です。ksizeが[1, 2, 2, 1]で、stridesが[1, 2, 2, 1]であれば、2 x 2のmax poolingです。2 x 2の領域から最大値をとります。間隔が2の場合出力サイズは半分になります。ksizeが[1, 3, 3, 1]で、stridesが[1, 2, 2, 1]の場合、3 x 3の領域から最大値をとり、間隔が2になるので、出力サイズは半分のままですが、数値を広範囲から取得することになるので、よりちょっとの差に動じなくなります。

tf.nn.max_poolの動きを確認してみます。
この画像を使います。

画像を読み込む

とりあえず画像を読み込んで、shapeを表示させてみます。

結果

Max poolingしてみる

結果

おーできてるっぽい。

画像を表示してみる。

結果

では、わかり易くksizeを[1, 10, 10, 1]でやってみます。

結果

TensorFlow – weight decay

機械学習のweight decayは、重みの2乗ノルム(L2ノルム)を損失関数に加えること。これによって重みが大きいと損失関数の値が大きくなるので、重みが大きくなりすぎないようになる。過学習は重みが大きくなることで発生することが多いからこういうことする。L2ノルムは、各次元の値の2乗の和。

サンプル(TensorFlow使ってない)

サンプル(TensorFlow)

上記の、_variable_on_cpu()は、下記。

そして、_variable_with_weight_decay()は下記のように使われる。

(tf.nn.l2_loss()

多分2乗した合計かその半分が出てくるんじゃないかと思うので、確かめてみる。

結果

2乗和の半分っぽい。

TensorFlowのサンプルのように、wdを0.0にしてるってことは、weight decayに含めないってことか。畳み込み層は含まず、全結合層だけwdを0.004にしてる。

TensorFlowで損失関数にL2ノルムのweight decayを足してるところ

バッチ処理してるので、cross_entropyの平均をとって、weigt decayが入った’losses’というコレクションに入れて、コレクション内の数字を全部足している。

TensorFlow – tf.add_to_collection

tf.add_to_collection(name, value)は、tf.Graph.add_to_collection(name, value)のラッパーだそうです。

引数

  • name: The key for the collection. The GraphKeys class
    contains many standard names for collections.
  • value: The value to add to the collection.

すごい単純だな。

結果

TensorFlow – tf.train.MonitoredTrainingSession

tf.train.MonitoredTrainingSessionを確認します。
訓練をモニターするのに特化したセッションという感じでしょうか?チュートリアルのコードでは下記のような使われ方をしています。

普通のセッションを使う代わりに使っています。

https://www.tensorflow.org/api_docs/python/train/distributed_execution#MonitoredTrainingSession

tf.train.MonitoredTrainingSession(master=”, is_chief=True, checkpoint_dir=None, scaffold=None, hooks=None, chief_only_hooks=None, save_checkpoint_secs=600, save_summaries_steps=100, config=None)

引数的に、勝手に変数の保存をしてくれたりするようです。

For a chief, this utility sets proper session initializer/restorer. It also creates hooks related to checkpoint and summary saving. For workers, this utility sets proper session creator which waits for the chief to inialize/restore.

引数は下記です。

  • master: String the TensorFlow master to use.
  • is_chief: If True, it will take care of initialization and recovery the
    underlying TensorFlow session. If False, it will wait on a chief to
    initialize or recover the TensorFlow session.
  • checkpoint_dir: A string. Optional path to a directory where to restore
    variables.
  • scaffold: A Scaffold used for gathering or building supportive ops. If
    not specified, a default one is created. It’s used to finalize the graph.
  • hooks: Optional list of SessionRunHook objects.
  • chief_only_hooks: list of SessionRunHook objects. Activate these hooks if
    is_chief==True, ignore otherwise.
  • save_checkpoint_secs: The frequency, in seconds, that a checkpoint is saved
    using a default checkpoint saver. If save_checkpoint_secs is set to
    None, then the default checkpoint saver isn’t used.
  • save_summaries_steps: The frequency, in number of global steps, that the
    summaries are written to disk using a default summary saver. If
    save_summaries_steps is set to None, then the default summary saver
    isn’t used.
  • config: an instance of tf.ConfigProto proto used to configure the session.
    It’s the config argument of constructor of tf.Session.

hookというのはコールバック的な感じで、session.runの前後に実行できるクラスらしい。これを紐づけることができて、リストで複数のhookを登録することができる。カスタマイズできるのが、SessionRunHookで、それ以外に用途が決まっているhookが複数事前に提供されているといったような感じのイメージを持った気がする。

class tf.train.SessionRunHook
class tf.train.StopAtStepHook
class tf.train.NanTensorHook

configは設定で、log_device_placementは、手動でデバイス指定してる場合にTrueにすると、手動設定したデバイスを選んでくれる的なやつっぽい。自分の非力な1体のPC環境ではあまり関係がないと思う。非力な1体のPC環境の場合、hookは自作する_LoggerHook()だけで、configは未設定でもよさそう。

引数でcheckpoint_dirを聞いてるくらいだから、tf.summary.FileWriter(‘.\logs’, sess.graph)みたいのを書かなくてもログが保存されるようになったりしてるのか試してみようと思います。

結果

そして、logsディレクトリにログファイルが登録されていて、TensorBoardでも見られた。
before_runのreturnで、tf.train.SessionRunArgs(add)とやると、after_runのrun_values.resultsに結果が入ってくる。