プログラミング!?で遊ぶ

強化学習で遊びます。

学習するもの
今回学習させたのは"じゃんけん"です。
エージェント(学習者)は「グー」「チョキ」「パー」のいずれかの手を選択し、「勝ち」「あいこ」「負け」の結果として、それぞれ「1」「0」「-１」の報酬を得ます。
エージェントは手に対して、その手を出したときに得られる報酬の推定値(V(グー)、V(チョキ)、V(パー))を持っていて、この推定値を正しくすることが学習の目標です。

学習の方法
1.エージェントが適当に手xを出す。
2.じゃんけんの結果の報酬 rを得る。
3.V(x) := V(x) + α( r - V(x) ) でV(x)を変更する。(αは学習率)
上の１〜３を何度も繰り返してVを正しい値に近づけていきます。

学習の結果
「グー」しか出さない人をじゃんけんの相手にしました。
つまり、V(グー)=0、V(チョキ)＝-1、V(パー)＝1が正しいVになります。
Vの初期値を0.0として、上の１〜３を1万回繰り返したところ、
V(グー)＝0.0
V(チョキ)=-1.0
V(パー)=1.0
となって、正しい値を学習してくれました。

本日はここまで。
(今回は文章を書くのが大変でした。これで理解してもらえるのでしょうか・・・)

TopCoder SRM452に参加しました。
緑コーダーなのでDiv2です。

Easy
サクッと解くもミスがあってシステムテストを通らず。(無念)

Medium
少し考えてgreedyで良さそうな気がする。確信が持てないもののとりあえず実装→提出。
提出後にしばらく考えてgreedyで良いことを確信。
システムテストも無事通過。

Hard
しばらく考えて、アルゴリズムを思いつき(正しいかどうかは未確認)実装に取りかかる。
30分以上あったにもかかわらず実装できず・・・。(泣)

感想
今回はEasyのミスが痛かったです。レートも落としてしまいました。
また、Hardが実装できなかったことで実装能力の不足を痛感しました。
練習として、まずは今回のHardをちゃんと実装しましょうか。

以上、参戦記でした。

再び、ニューラルネットにsinを学習させてみました。
ただし、今回は訓練データに誤差があります。
結果は下の図。

緑の線がsin、青い点が訓練データ、赤い線が学習したニューラルネットの出力です。
xが4〜5の部分で赤い線がsinより多少下にありますが、
この辺では訓練データが下に寄っているので仕方がないところでしょう。

次にニューラルネットに過学習させようとパラメータを変更してみました。
各ニューロンの出力を決めるシグモイド関数のゲインを10倍にした場合を載せます。

とりあえず過学習してくれたようです。
本当はもう少し期待していたのですが・・・。

今日はここまで。

topcoder SRM450に参加しました。
2問サクッと解いたものの、最後の1問が解けませんでした。

とはいえ、なかなか早く解けたので初めてのroom1位。
レートも上がって、Div1が近づいてきたでしょうか・・・。

少し前に、焼きなまし法で遊びました。
その時、温度の調整に苦労したので温度によって探索がどう変化するかを調べてみました。

対象は以前と同様
f(x)=z^2-cos(10*pi/2*z) (zはx/10)
の最小化。(xは-50〜50の整数)
近傍、遷移確率なども以前と同じです。
（詳しくはここ　以下では前の記事で用いた記号を使います）

初期値ランダム、温度一定で10000回探索を行った結果を図で示します。
(1回の探索では100回近傍の評価をしています)

まず、温度が高い場合。

緑色の線は評価関数(左側の目盛)、赤い棒グラフはそこで探索を終えた回数(右側の目盛)です。
ご覧のように温度が高い場合、探索を終えた位置はすべての場所で100前後になりました。
評価関数の影響はなく、ランダムウォークになっていることがわかります。
改悪解に移動する確率exp(-d/t)がほぼ1になるので当然ですね。

次に、温度が低い場合。

exp(-d/t)がほぼ0になるので、すべての探索が局所解で終了しています。
初期値をランダムに選んだので、各局所解で探索を終えた回数は大体同じになっています。

最後に温度が"ほどほど"だった場合。

図の両端に近いところでは、探索を終える回数が少なくなっていることがわかります。
端の近くでは中へ移動するとき、たとえ改悪であってもdが小さいのでexp(-d/T)が大きな値になり山を越えやすいことが理由でしょう。

ここに書いたことは当たり前の事ばかりですが、今回のいろんな温度で探索を行ったことで、温度変化が私の想像以上に大きく探索に影響を与えることがわかりました。
そのあたりのことをもっと詳しく調べたい気もしますが、「目標：がんばらない」です。
今日はここまで。