Q学習で迷路を学習
昔、授業でQ学習を習ったの思い出したのでQ学習使って迷路学習させるスクリプトをrubyで書いた
Q学習とは
Q学習は機械学習手法の方策オフ型TD学習の一つである。概念自体は古くから存在するが、Q学習(Q-learning)という名前で今日の手法がまとめられたのは、1989年のクリス・ワトキンズ(Chris Watkins)の論文に端を発する。
Q学習は有限マルコフ決定過程において全ての状態が十分にサンプリングできるようなエピソードを無限回試行した場合、最適な評価値に収束することが理論的に証明されている。実際の問題に対してこの条件を満たすことは困難ではあるが、この証明はQ学習の有効性を示す要素の一つとして挙げられる。
Q学習 - Wikipedia
なんか難しい感じだけど、マルコフ条件の元で状態遷移する場合(ある状態は直前の状態からのみ影響を受ける場合)、無限回試行すると、最適な行動を学習出来るってことらしい。たぶん
Q値の更新
Q学習のきもはQ値の更新で
でQ値をどんどん更新していく
Q学習で迷路を学習するときのイメージは複数回試行することで報酬(ゴール)がどんどん伝搬していって各状態におけるQ値が決まっていく感じ
実験
こんな感じの迷路を学習させてみた
##################### #S 0 0 0 0# #0 -10 0 0 0# #0 0 -10 0 -10# #0 -10 0 0 0# #0 0 0 -10 50# #####################
Sが初期位置で右下の50がゴールになっている
この迷路を5000ステップ学習して、学習したQ値を使って迷路を解いた
学習時の行動選択は、ある小さな確率εでランダムに選択し、それ以外では Q値の最大の行動を選択するε-グリーディ法を利用した。
学習したQ値を利用して迷路を解いたところ、以下のような結果になった
x: 0 y: 0 @ 0 0 0 0 0 -10 0 0 0 0 0 -10 0 -10 0 -10 0 0 0 0 0 0 -10 50 x: 1 y: 0 0 @ 0 0 0 0 -10 0 0 0 0 0 -10 0 -10 0 -10 0 0 0 0 0 0 -10 50 x: 2 y: 0 0 0 @ 0 0 0 -10 0 0 0 0 0 -10 0 -10 0 -10 0 0 0 0 0 0 -10 50 x: 2 y: 1 0 0 0 0 0 0 -10 @ 0 0 0 0 -10 0 -10 0 -10 0 0 0 0 0 0 -10 50 x: 3 y: 1 0 0 0 0 0 0 -10 0 @ 0 0 0 -10 0 -10 0 -10 0 0 0 0 0 0 -10 50 x: 3 y: 2 0 0 0 0 0 0 -10 0 0 0 0 0 -10 @ -10 0 -10 0 0 0 0 0 0 -10 50 x: 3 y: 3 0 0 0 0 0 0 -10 0 0 0 0 0 -10 0 -10 0 -10 0 @ 0 0 0 0 -10 50 x: 4 y: 3 0 0 0 0 0 0 -10 0 0 0 0 0 -10 0 -10 0 -10 0 0 @ 0 0 0 -10 50
ちゃんと解けてるっぽい
結構楽しかったので、これを気に機械学習とかちゃんと勉強してみたい
rubyでRANSAC
研究で必要になったから調べてみた
観測したデータから最小二乗法などでモデルを推定する際に、観測したデータに外れ値が混じっていた場合、推定したモデルは外れ値に引っ張られてしまいます。そこで、RANSACアルゴリズムを利用することで、外れ値を無視したモデルの推定を行うことが出来ます
RANSACアルゴリズム
1.観測データ群からランダムに幾つかのデータを取り出す
2.取り出したデータを用いてモデルを推定
3.推定したモデルに対して、観測データ群を適用し、モデルを評価する
4.1~3を複数回行い、一番評価が高いモデルを採用
意外とシンプルなアルゴリズムです。
実験
今回は、直線のモデルを最小二乗法で推定します。
直線のモデルなんで、
のaとbの部分を推定します。
今回は正解のモデルを
っぽい直線としました。
正解データは
(1- rand() / 10) * x
また外れ値は
rand(0.0..5.0) * x
として生成しました。
ちなみにxは1から100までの整数です。
グラフの描画はgnuplotなるライブラリを使いました。
まずは外れ値なしの最小二乗法から
なかなかよい感じ
続いて、外れ値ありの最小二乗法
めっちゃ外れ値に引っ張られてます。
最後にRANSAC使った場合です。
きれいに外れ値を無視してくれました。
RANSACは簡単に実装できて、強力なんですが、
複数回、モデルの推定を行って、それを更に観測データ群に適応させるので、
計算量がめっちゃ大きい感じがします。
実際にRANSACを使う場合には工夫が必要かもしれません
ちなみに今回書いたコードはこんな感じです。
c++でイベント駆動っぽくTCPを書いた
思いつきでc++でイベント駆動っぽいTCPのクラス書いてみた
これでTCPのサーバーとクライアント両方ともイベント駆動っぽくかける
試しにエコーサーバ
サーバ
#include <iostream> #include "TCPEventServer.h" int main(void) { eventTCP server(5432); server.on("connect", [](Socket *sock){ std::cout << "connect" << std::endl; sock->on("echo", [sock](std::string data){ std::cout << data << std::endl; sock->emit("echo", data); }); sock->on("disconnect", [sock](std::string data){ std::cout << "disconnect" << std::endl; sock->close(); }); }); server.listen(5); return 0; }
クライアント
#include <iostream> #include "TCPEventClient.h" int main(void) { TCPEventClient client; client.connect("127.0.0.1", 5432); client.on("connect", [](Socket *sock){ std::cout << "connect" << std::endl; sock->on("echo", [sock](std::string data){ std::cout << data << std::endl; }); sock->on("disconnect", [sock](std::string data){ sock->close(); }); sock->emit("echo", "echo server"); }); return 0; }
rubyでオセロのコンソールアプリ作った
プロキシ切り替えるクロム拡張作った
面倒くさかったから勉強も兼ねてクロム拡張を作った。
マニュフェストファイルはこんな感じ
{ "manifest_version": 2, "name": "Proxy Changer", "version": "1.0", "description": "change http proxy", "browser_action": { "default_icon": "icon.png", "default_popup": "popup.html" }, "permissions": [ "tabs", "proxy" ], "icons" : { "128": "icon.png" } }
続いてhtml
<!DOCTYPE HTML> <html lnag="ja"> <head> <meta charset="utf-8"> <title>proxy changer</title> </head> <body> <button id="scholl">scholl proxy</button> <button id="outer">outer proxy</button> <script src="background.js"></script> </body> </html>
js
window.onload=function(){ document.getElementById("scholl").addEventListener("click", changeShollProxy); document.getElementById("outer").addEventListener("click", changeOuterProxy); } var config = { mode: "fixed_servers", rules: { proxyForHttp: { scheme: "http", host: "xx.xx.xx.xx", port: xxxx }, bypassList: ["127.0.0.1"] } }; function changeShollProxy(){ chrome.proxy.settings.set( {value: config, scope: "regular"}, function(){} ); } function changeOuterProxy(){ config.mode = "auto_detect"; chrome.proxy.settings.set( {value: config, scope: "regular"}, function(){} ); }
html適当なのは許して
本当は
<button id="scholl" onclick="chagneSchollProxy">scholl</button>
みたいにしたかったけど、クロム拡張では出来ないみたい(違ってたらごめんなさい)。
参考
いまさらまとめるChrome ExtensionでのJavaScript挿入 - console.lealog();
バイト列の任意の位置から32ビット読み込んでint型として扱う
TCPやUDPなどのネットワークプログラムを書いてると、受信したバイト列の任意の位置から32ビットを読み込んでint型として扱いたくなる時がある。
例えば、受信したバイト列に整数「123」が含まれているとする。
整数「123」はバイト列に直すと
00 00 00 7b
となる。実際には、バイト列には他のデータも含まれているので
00 00 00 64 00 00 00 7b 00 00 04 d2
みたいな感じになる(「00 00 00 7b」以外は適当)。
このバイト列から4バイト(00 00 00 7b)をうまく切り出してint型にキャストすると整数「123」を復元することができる。
c言語で書くとこんな感じ
#include <stdio.h> typedef unsigend char UINT8; typedef unsigned int UINT32; UINT32 readUint32(UINT8 *bytes, int index){ return (UINT32)((UINT32)(bytes[index] << 0) | ((UINT32)bytes[index + 1] << 8) | ((UINT32)bytes[index + 2] << 16) | ((UINT32)bytes[index + 3] << 24)); } int main(void){ UINT8 bytes[] ={0xd2m 0x04, 0x00, 0x00, 0x7b, 0x00, 0x00, 0x00, 0x64, 0x00, 0x00, 0x00}; UINT32 temp; int *intVal; temp = readUint32(bytes, 4); intVal = (int *)&temp; printf("%d\n", *intVal); return 0; }