はてなブログに移行します。
きっかけ
前回のエントリーで年内にもう１エントリーすると発言して、ネタもできないまま大晦日を迎えたので、
これをきっかけに、はてなブログに移行することにした。
http://kshi-kshi.hatenablog.com/
http://kshi-kshi.hateblo.jp/ (更に変更しました。)
ポスト数の目標は年に最低50エントリー。週に1エントリーくらいのペースで細々と適当なことを書いていこうと思っている。
Q学習-最良経路を学習するスクリプト書いた (powered by Python)
概要
講義の課題で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学習 - Wikipedia
- Q-Learning
- わかりやすい図がたくさん載っている.
- TD学習とは-強化学習アルゴリズム
- 根本のTD学習について詳しく書かれている.
キモはQ値の更新式！
この式を掴めれば、Q学習はものにできたようなものだと勝手に思っている.
簡単に、この式がどういったことを表しているのかを書いてみる. ( が学習率、
が割引率と言われている.)
この式の目的は、ある状態 における最良な行動
を選ぶための基準を、各状態における各行動での評価値
を更新するような処理をしたい. 行動の重みづけをするようなイメージ.
基本的なアイディアは、良い報酬につながるような行動を選ぶようにしたいので、良い報酬を得られる行動 は良い行動. その報酬を得られる行動ができる状態に行けるための行動もちょっぴり良い行動といったような感じで良い報酬に近づいていく行動に対して、良い重みづけをしていくようなイメージ. 悪い行動に対しても同様に悪い重みを与える.
学習率 
が大きくなるほど、更新時の影響が強くなる.
割引率 
次の行動の影響度を表す. 値が大きいほど、次の状態での行動が効いてくる.
学習させた結果
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)
スクリプトを晒す
スクリプトの処理内容:
- 最初に盤面情報を出力
- LEARNING_COUNT(1000回)分 エピソード経過させ、Q値を学習.
- 学習後、Q値の情報を出力.
- greedy法で学習したQ値の観点で1 エピソードの行動選択をさせ、その遷移を出力.
部分集合を求めるスクリプト
概要
id:shibutaka526 がブログ頑張っているのを見て刺激を受け、布団に入って寝ようとしていたけど無性にスクリプトを書きたくなったので彼の以下のエントリーの問題をPythonで解いてみたという話.
- 部分集合を求めるプログラム - shibu_t最強伝説
- ※ こちらの問題の解釈が間違っていて、違う問題を解いているかもしれません。
スクリプト
恐縮ながらポイントを挙げると 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'] -------------------------
最後に
向上心あふれる人たちが周りにいて幸せだということをここ最近感じている。彼らに負けないように頑張りたい。
CODE VS (#codevs) Python サンプルコード
概要
昨日からCODE VSにkshi_kshiとして参戦している。
言語が標準入出力を扱えるものであれば何でも可能というのは参加者としてとても嬉しい限り。
ということでPythonです。
実際に動くまでに少しハマったので簡単なテンプレート的なものを晒してみる。
※ この程度のスクリプトなら、公開しても問題ないだろうという勝手な独断で晒しています。
もし関係者の方々にとって不都合なことがありましたら、お手数ですが、コメントなどでご連絡いただければ、この記事を削除する次第です。よろしくお願いいたします。
参考記事
簡単なサンプルを作って、テストの入力ファイル(sample.in)でチェックした後、専用のクライアントアプリケーションで動かしてみたら5分立つまで、何も結果が返ってこなくて、困っていたら、
以下の素晴らしい記事がきっかけで動きました。id:sucrose さんありがとうございます。
動かなかった原因としては
sys.stdout.flush()
がなかったので、ダメだったみたい.
サンプルコード
実行環境
- Windows, python2.5.4
内容
level1の時に砲台を3つ設置してあとは何もしないという内容。1-19面で力尽きるしょぼいAI。
(Moneyは全く考慮していないません。)
#mixi_scrap に参加してきた.
概要
本日Mixiが主催するエンジニア志望の学生向けイベントに参加してきた.
イベントの終わり際に会場の写真を記念にと撮影してたら、社員さんに「写真撮ったらブログに書いてね〜」って言われたので、素直にエントリー.
イベント概要
イベントスケジュール
| 10:30 | 開催の挨拶 |
| 10:35 | 講義 |
| 11:30 | 休憩 |
| 11:40 | チュートリアル準備 |
| 12:10 | チュートリアル |
| 12:40 | 昼食・休憩 |
| 13:30 | 実践 |
| 16:00 | 解説 |
| 16:30 | 表彰・総括 |
| 16:50 | 懇親会 |
| 17:30 | 終了 |
ワークショップ
参加者情報
- 参加者: 23人.
- 全8チーム.(1team のみ2人だった.)
- この手のイベントは院生が多めのイメージがあったが、半分くらいは学部生だったんじゃないかな？B1〜B4, M1と様々だった.参加者のスキルがとても高い印象を持った。mixiというビッグネームの力大きいな〜って感じた。普通のイベントじゃこんな濃い〜人達と会えないと思う。
イベントの様子
渋谷東口から徒歩5分くらい？新しいビルディング。グルーポンも同じビル内に入っているのは知らなかった。意外とワンフロアーのみ。
mixiは7階。
会場の様子。かなりの解放感。
会場の様子2。
会場の様子3。畳がある。寝転がりたかったが、さすがに自重した。
人事の方がいろいろとサポートしてくれた。ピッツァをたらふくいただきました。ごちそうさまでしたー。
トイレもとても綺麗。
参加者のスーパーハカー達のシルエット。
イベント終了後の様子。
廊下。みんな帰っていく。お疲れ様でしたー。
ワークショップ中は課題でひ〜ひ〜言っていて、撮影する余裕がなくて撮れなかったのが残念。
感想
ワークショップは残念な結果に終わったが、いろいろと勉強になったイベントだった。
一番の収穫は学部1,2年という自分より年下の優秀な人達を生で見れた・交流できたことが良かったのかなと思っている。エンジニアとしてやっていくにあたって、そういう優秀な人等と同じ土俵で真っ向勝負していくのは分が悪いよね〜って今までぼんやりと感じていたものがハッキリしてきた気がする。
専門性を身につけて自分なりの色をつけたエンジニアになって、優秀なそういう人等と違ったフィールドかつ異なる武器を持ってエンジニア戦線を生き残っていきたいと思っている今日この頃。
データマイニング、機械学習あたりに本腰入れていくつもり。
ということで、集合知プログラミングの勉強会の後は、入門ソーシャルデータ 勉強会やろうと思います。
今日本を入手して、手にしてみたら、意外と薄い本という印象を持った.(厚さ的な意味で) 中身はとても面白そう。
【告知】#PCII参加者募集中
HHKのお掃除したら、無刻印パニック。
vim置換メモ: optionタグ => python 辞書型
問題設定
optionタグで囲まれた情報を、Python辞書型にする. (最終イメージは以下参照)
置換対象の文字列
skymarkの予約ページのhtmlの一部.
# 置換対象文字
<option value="HND">羽田</option> <option value="AKJ">旭川</option> <option value="CTS">札幌（新千歳）</option> <option value="IBR">茨城</option> <option value="NRT">成田</option> <option value="NGO">名古屋（中部）</option> <option value="UKB">神戸</option> <option value="KKJ">北九州</option> <option value="FUK">福岡</option> <option value="NGS">長崎</option> <option value="KMJ">熊本</option> <option value="KOJ">鹿児島</option> <option value="OKA">那覇</option> <option value="MMY">宮古</option>
こんな形にしたい (GOAL)
airport_info = {
"haneda" : "HND", # 羽田
"asahikawa" : "AKJ", # 旭川
"sapporo" : "CTS", # 札幌（新千歳）
"ibaraki" : "IBR", # 茨城
"narita" : "NRT", # 成田
"nagoya" : "NGO", # 名古屋（中部）
"kobe" : "UKB", # 神戸
"kitakyusyu": "KKJ", # 北九州
"hukuoka" : "FUK", # 福岡
"nagasaki" : "NGS", # 長崎
"kumamoto" : "KMJ", # 熊本
"kagoshima" : "KOJ", # 鹿児島
"naha" : "OKA", # 那覇
"miyako" : "MMY" # 宮古
}
Step 1: とりあえず、前方の部分文字列をカット. (vim基本操作)
Ctr+vで短縮選択してxで削除
"HND">羽田</option> "AKJ">旭川</option> "CTS">札幌（新千歳）</option> "IBR">茨城</option> "NRT">成田</option> "NGO">名古屋（中部）</option> "UKB">神戸</option> "KKJ">北九州</option> "FUK">福岡</option> "NGS">長崎</option> "KMJ">熊本</option> "KOJ">鹿児島</option> "OKA">那覇</option> "MMY">宮古</option>
Step 2-α: パターンマッチを使用した置換
対象を選択した後、以下で置換.
:'<,'>s/">\(.*\)<\/option>/" # \1/g
日本語文字列の部分に()で囲んで、置換後の文字列に再利用する.
そうするとこうなる.
"HND" # 羽田 "AKJ" # 旭川 "CTS" # 札幌（新千歳） "IBR" # 茨城 "NRT" # 成田 "NGO" # 名古屋（中部） "UKB" # 神戸 "KKJ" # 北九州 "FUK" # 福岡 "NGS" # 長崎 "KMJ" # 熊本 "KOJ" # 鹿児島 "OKA" # 那覇 "MMY" # 宮古
う〜んもうちょっと、楽したいな〜
てことで、やり直し.
Step 2-β: パターンマッチ(回数指定繰り返し)を使用した置換
αのやつを少し改良する.
'<,'>s/"\([A-Z]\{3\}\)">\(.*\)<\/option>/\t"": "\1", # \2/g大文字英数字が3回させた文字列にパターンマッチさせた感じ。
そうするとこうなる.
"": "HND", # 羽田 "": "AKJ", # 旭川 "": "CTS", # 札幌（新千歳） "": "IBR", # 茨城 "": "NRT", # 成田 "": "NGO", # 名古屋（中部） "": "UKB", # 神戸 "": "KKJ", # 北九州 "": "FUK", # 福岡 "": "NGS", # 長崎 "": "KMJ", # 熊本 "": "KOJ", # 鹿児島 "": "OKA", # 那覇 "": "MMY", # 宮古
まぁ満足.
Step3: 手打ちする
あとはしょうがない。手打ちする。
最後の"宮古"のカンマを消して、{}で囲って終わり。
Step2-γ: 番外編 - optionタグの情報のみを利用する場合
こっちの方が利用頻度は多いのでないかと思ったので、一応やってみた.
:'<,'>s/"\([A-Z]\{3\}\)">\(.*\)<\/option>/\t"\1": "\2",/g置換後の位置を変えただけ.
そうしたらこうなる
"HND": "羽田",
"AKJ": "旭川",
"CTS": "札幌（新千歳）",
"IBR": "茨城",
"NRT": "成田",
"NGO": "名古屋（中部）",
"UKB": "神戸",
"KKJ": "北九州",
"FUK": "福岡",
"NGS": "長崎",
"KMJ": "熊本",
"KOJ": "鹿児島",
"OKA": "那覇",
"MMY": "宮古",
