Hatena::ブログ(Diary)

Stargazing && Temporary Escapism ~インプット馬鹿への道~ このページをアンテナに追加 RSSフィード Twitter

プロフィール

Kshi_Kshi

Kshi_Kshi

影響されやすく、すぐに自分にもできるかも!と夢見がち、かつ現実逃避しがちな単純怠惰男が綴る、技術メモ。NLPとかPythonとかPHPとか読んだ本とか...

 

2011-12-31

はてなブログに移行します。

| 00:00 |

きっかけ

前回のエントリーで年内にもう1エントリーすると発言して、ネタもできないまま大晦日を迎えたので、

これをきっかけに、はてなブログに移行することにした。

http://kshi-kshi.hatenablog.com/

http://kshi-kshi.hateblo.jp/ (更に変更しました。)

ポスト数の目標は年に最低50エントリー。週に1エントリーくらいのペースで細々と適当なことを書いていこうと思っている。

2011-12-27

Q学習-最良経路を学習するスクリプト書いた (powered by Python)

| 22:46 |



概要

講義の課題でQ学習について実装してみたので、スクリプト等を晒してみる.

          #   #   #   #   #   #   #
          #   S   0   0 -10   0   #
          #   0 -10   0   0   0   #
          #   0 -10   0 -10   0   #
          #   0   0   0 -10   0   #
          #   0 -10   0   0 100   #
          #   #   #   #   #   #   #

こんな感じの迷路において、S(start地点)からより良い報酬("100")までの経路をQ学習を用いて学習させるという話.



Q学習-概要

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

http://ja.wikipedia.org/wiki/Q%E5%AD%A6%E7%BF%92

強化学習で有名な手法らしい. TD(Temporal difference:時間差分)学習の一つらしい.


参考

キモはQ値の更新式!

Q(s_t, a) ¥leftarrow Q(s_t, a) + ¥alpha¥left[r_{t+1} + ¥gamma¥max_pQ(s_{t+1}, p) - Q(s_t,a)¥right¥]

この式を掴めれば、Q学習はものにできたようなものだと勝手に思っている.

簡単に、この式がどういったことを表しているのかを書いてみる. ( ¥alpha が学習率、 ¥gamma が割引率と言われている.)

この式の目的は、ある状態 s_t における最良な行動 a を選ぶための基準を、各状態における各行動での評価値 Q(s_t, a) を更新するような処理をしたい. 行動の重みづけをするようなイメージ.

基本的なアイディアは、良い報酬につながるような行動を選ぶようにしたいので、良い報酬を得られる行動 a は良い行動. その報酬を得られる行動ができる状態に行けるための行動もちょっぴり良い行動といったような感じで良い報酬に近づいていく行動に対して、良い重みづけをしていくようなイメージ. 悪い行動に対しても同様に悪い重みを与える.


学習率 ¥alpha

¥alphaが大きくなるほど、更新時の影響が強くなる.


割引率 ¥gamma

¥gamma次の行動の影響度を表す. 値が大きいほど、次の状態での行動が効いてくる.



学習させた結果

1エピソードを報酬が得られるまでの行動遷移として、1000エピソードの全行動分、Q値を更新させた.

その時の行動選択アルゴリズムはε-greedy法を用いた. (スクリプトは長くなってしまったので記事の後ろの方に載せました.)

以下の図は、その1000エピソード分学習したQ値を用いて、今度はgreedy法を適用して行動選択させてみた様子.

ちゃんとスタート地点から最短距離で最高の報酬100ポイントに向かっているのがわかる.

ちなみに実行のたびに経路は変わる.(ε-greedyのランダム性のため。)

--- 盤面情報 "#": 壁, "S": スタート地点, "@": 今いる座標, "数値": その座標での報酬 ---

----- Dump Field:  -----
          #   #   #   #   #   #   #
          #   S   0   0 -10   0   #
          #   0 -10   0   0   0   #
          #   0 -10   0 -10   0   #
          #   0   0   0 -10   0   #
          #   0 -10   0   0 100   #
          #   #   #   #   #   #   #

----- Dump Field: (2, 1) -----
          #   #   #   #   #   #   #
          #   S   @   0 -10   0   #
          #   0 -10   0   0   0   #
          #   0 -10   0 -10   0   #
          #   0   0   0 -10   0   #
          #   0 -10   0   0 100   #
          #   #   #   #   #   #   #
        state: (1, 1) -> action:(2, 1)

----- Dump Field: (3, 1) -----
          #   #   #   #   #   #   #
          #   S   0   @ -10   0   #
          #   0 -10   0   0   0   #
          #   0 -10   0 -10   0   #
          #   0   0   0 -10   0   #
          #   0 -10   0   0 100   #
          #   #   #   #   #   #   #
        state: (2, 1) -> action:(3, 1)

----- Dump Field: (3, 2) -----
          #   #   #   #   #   #   #
          #   S   0   0 -10   0   #
          #   0 -10   @   0   0   #
          #   0 -10   0 -10   0   #
          #   0   0   0 -10   0   #
          #   0 -10   0   0 100   #
          #   #   #   #   #   #   #
        state: (3, 1) -> action:(3, 2)

----- Dump Field: (3, 3) -----
          #   #   #   #   #   #   #
          #   S   0   0 -10   0   #
          #   0 -10   0   0   0   #
          #   0 -10   @ -10   0   #
          #   0   0   0 -10   0   #
          #   0 -10   0   0 100   #
          #   #   #   #   #   #   #
        state: (3, 2) -> action:(3, 3)

----- Dump Field: (3, 4) -----
          #   #   #   #   #   #   #
          #   S   0   0 -10   0   #
          #   0 -10   0   0   0   #
          #   0 -10   0 -10   0   #
          #   0   0   @ -10   0   #
          #   0 -10   0   0 100   #
          #   #   #   #   #   #   #
        state: (3, 3) -> action:(3, 4)

----- Dump Field: (3, 5) -----
          #   #   #   #   #   #   #
          #   S   0   0 -10   0   #
          #   0 -10   0   0   0   #
          #   0 -10   0 -10   0   #
          #   0   0   0 -10   0   #
          #   0 -10   @   0 100   #
          #   #   #   #   #   #   #
        state: (3, 4) -> action:(3, 5)

----- Dump Field: (4, 5) -----
          #   #   #   #   #   #   #
          #   S   0   0 -10   0   #
          #   0 -10   0   0   0   #
          #   0 -10   0 -10   0   #
          #   0   0   0 -10   0   #
          #   0 -10   0   @ 100   #
          #   #   #   #   #   #   #
        state: (3, 5) -> action:(4, 5)

----- Dump Field: (5, 5) -----
          #   #   #   #   #   #   #
          #   S   0   0 -10   0   #
          #   0 -10   0   0   0   #
          #   0 -10   0 -10   0   #
          #   0   0   0 -10   0   #
          #   0 -10   0   0   @   #
          #   #   #   #   #   #   #
        state: (4, 5) -> action:(5, 5)

スクリプト晒す

スクリプトの処理内容:
  1. 最初に盤面情報を出力
  2. LEARNING_COUNT(1000回)分 エピソード経過させ、Q値を学習.
  3. 学習後、Q値の情報を出力.
  4. greedy法で学習したQ値の観点で1 エピソードの行動選択をさせ、その遷移を出力.

スクリプト

最後にスクリプト170行ほど。冗長になってしまった感は否めない。もっとスマートに書けるアドバイス等していただけると嬉しいです。


続きを読む

2011-12-18

部分集合を求めるスクリプト

| 01:35 |

概要

id:shibutaka526ブログ頑張っているのを見て刺激を受け、布団に入って寝ようとしていたけど無性にスクリプトを書きたくなったので彼の以下のエントリーの問題をPythonで解いてみたという話.

スクリプト

恐縮ながらポイントを挙げると 0~2の要素数乗までの2進数の以下のような文字列を生成して、

"000", "001", "010", "011", "100", "101", "110", "111"

i番目の文字列が入力された配列のi番目の要素の対として、文字列のi番目が0/1のとき、i番目の要素を使わない/使う。

といったような2進数の文字列をスイッチとして使ったところが個人的に工夫出来たと思っている。

このスクリプト書いてみて、2分岐の実装方法として2進数を使って書けるんだな〜っていうのが発見だった.

#!/usr/bin/env python
# coding:utf-8

def solve(input):
    n = len(input)
    pattern ,result = [], ["φ"]

    for i in range(1, pow(2, n)):
        s = "%0" + str(n) + "d"
        pattern.append(s % int(format(i, 'b')))

    for i in pattern:
        s = ""
        for j, v in enumerate(list(i)[::-1]):
            if v == "1" : s += input[j]
        result.append(s)
    return result


if __name__ == "__main__":
    # test
    test = [['a'],
            ['a', 'b'],
            ['a', 'b', 'c'],
            ['a', 'b', 'c', 'd']]
    for input in test:
        print solve(input)
        print '-------------------------'
result
['\xcf\x86', 'a']
-------------------------
['\xcf\x86', 'a', 'b', 'ab']
-------------------------
['\xcf\x86', 'a', 'b', 'ab', 'c', 'ac', 'bc', 'abc']
-------------------------
['\xcf\x86', 'a', 'b', 'ab', 'c', 'ac', 'bc', 'abc', 'd', 'ad', 'bd', 'abd', 'cd', 'acd', 'bcd', 'abcd']
-------------------------

最後に

向上心あふれる人たちが周りにいて幸せだということをここ最近感じている。彼らに負けないように頑張りたい。

 
カテゴリー
最近のトラックバック