読者です 読者をやめる 読者になる 読者になる

pyvenvをactivateすると"parameter not set"とか言われる場合の対処

Python zsh

zshからpyvenvをactivateしようとすると

$ source bin/activate
deactivate:2: _OLD_VIRTUAL_PATH: parameter not set

というエラーになることがあります。これはzshno_unsetオプションを設定していると起こります。no_unsetオプションを設定したままこれを回避するには、無名関数を使って

$ (){ setopt local_options unset; source bin/activate }

とすればいいようです。deactivate時も同様に

$ (){ setopt local_options unset; deactivate }

でOK。

OpenAI GymのPong-ram用資料

OpenAI GymのPong-ram環境用のメモ。

とりあえずメモリアドレスを軽く調べました(趣旨的には解析とか一切なしで解くことが求められているのでしょうけど)。なお、Atari2600は $80-$FF の128 バイトがRAMとなっています(参考: Atari 2600 Specifications)。

address type description
$88 U8 フレームカウンタ
$8D U8 COMスコア
$8E U8 PLAYERスコア
$95 U8 COM座標y
$B1 U8 ボール座標x
$B6 U8 ボール座標y
$B8 S8 ボール速度y?
$BA S8 -1 * ボール速度x
$BC U8 PLAYER座標y

ボールのy方向の動きについては完全には理解していません($B8 に疑問符がついてるのはそのため)。もしかしたらサブピクセルまで計算されていたり、場合により $B8 が2回加えられるかもしれません。ボールの動き計算コード自体は $F554 にあります。

自機の動きには多少の慣性がかかりますが、これをメモリ内容だけで把握する方法はよくわかっていません。多分 $84 を目的座標として前回述べたような処理が行われるのだと思いますが、$84 は1Fおきに全く関係ない値に変わるため、その他のアドレスも参照しないと自機の慣性は正しく把握できないと思います。

とりあえず自機座標とボール座標/速度がわかれば最低限足りるとは思いますが、慣性も考慮しないと得点率が悪くなるかもしれません。手でプレイするとわかりますが適切な角度で打ち返さないとCOMは失点してくれないので、結構繊細な操作が要求されるんですよね…。

ただ、Pong-ram環境では1ステップごとに2-4フレーム進むようなので、そこまで繊細なことを考えても仕方ないのかもしれません。この辺はやってみないとわからない感じですね。

環境に関する情報をまとめておきます:

attribute value
env.action_space Discrete(6)
env.observation_space Box(128,)
env.reward_range (-inf,inf)
env.spec.timestep_limit 10000

actionの意味は以下の通りと思われます(2と4, 3と5の移動量は多分同じだと思いますが確証はありません):

意味
0,1 何もしない
2,4 上へ移動
3,5 下へ移動

observationは128バイトのRAMをそのまま格納した配列です。なお、配列の要素は numpy.uint8 で、Pythonの int と振る舞いが異なるので注意が必要です。

1点取ったとき 1.0, 1点取られたとき -1.0 の報酬が得られるようです。

ターン制限(10000)があるので、単に失点しないだけでなく得点率が求められると思われます。1ステップあたり2-4フレーム進むので、最悪の場合20000フレームで打ち切られます。なお、全く操作せずパーフェクト負けした場合は大体1000ステップ程度かかるようです。

メモリを見つつ1ステップずつ動かせるスクリプトを書いたので一応貼っておきます。

Atari2600 Pong 風にぬるっと動いてみるテスト

OpenAI GymのAtariゲーム環境の中にPong-ramというのがあって、ゲーム画面ではなくメモリ内容を直接見られるようなので、Stellaで動かしながらメモリアドレスなどを調べています。

幸いAtari 2600はNESと同じでCPUが6502(正確には機能削減版の6507)なので、少しコードを読んでみました。わりと癖があるというかNESゲームとは違う書き方をしているところが多くて読みにくいですが、自機の移動に関するコードがちょっと面白かったので紹介してみます。

自機の移動は擬似コードで書くとこんな感じになっています:

y = (y + dst_y) / 2

これはつまり現座標と最終的な移動先座標の中間点へ移動するということで、一気に移動するのではなく徐々に移動する感じになります。実際にこのゲームをプレイしてみると自機の移動がぬるっとした感じなのですが、それを実現するのがこのコードだったというわけですね(こういうのをeasingって言うのかな?)。

なんとなくjavascript同じようなものを作ってみました(玉がマウスカーソルを追いかけてくるだけ)。上のスライダーで係数を変えると動きの勢いが変わります。

多層パーセプトロンを書いてみる

前回は単純パーセプトロン(SLP)でAND, ORを学習し、XORは学習に失敗することを確認しました。今回は多層パーセプトロン(Multi Layer Perceptron, MLP)を使ってXORも含めて学習してみます。内容的には高卒でもわかる機械学習第3回以降に相当します。

相変わらず定義がいいかげんなまま記号を使ったりするのでお察しください^^;

今回は入力層、出力層に加えて1つの隠れ層を設けます。バイアス抜きで入力層のユニット数2, 隠れ層のユニット数2, 出力層のユニット数1とします*1。今回も出力側のみ値を {-1,1} の形式にします。

         in  hidden  out
bias      o     o

{0,1} --> o     o

{0,1} --> o     o     o --> {-1,1}

言い換えると、出力層の活性化関数をこのように定義します:

{ \displaystyle
f^{(2)}(u) = \begin{cases}
   1 & (u^{(2)} \ge 0) \\
  -1 & (u^{(2)} < 0)
\end{cases}
}

今回は隠れ層もあるのでここにも活性化関数を定義する必要があります。これを  f^{(1)}(u) と書くことにします。この関数の定義は任意ですが、XORを学習するためには非線形関数でなければなりません。線形関数だと出力層のユニット値は結局入力の線型結合にしかならないため、線形分離不能なXORは学習できないためです。このことは後に実際に試してみます。

今回も訓練データ1件ごとのオンライン学習とし、誤差関数を以下のように定義します(SLPのときと同様。微分ができるならこれで問題ないはず):

{ \displaystyle
E = max(0, -yu^{(2)})
}

u(2) は出力層のユニット値(w(2)*o(1)), y は教師データです。重みの更新は不正解時のみ行うので、実質的には

{ \displaystyle
E = -yu^{(2)}
}

と考えて問題ありません。これが全ての重みについて微分できるかどうか見ていきます。

まず重み行列の形を確認しておきます。入力層から隠れ層への重みを W(1), 隠れ層から出力層への重みを W(2) とすると、以下のようになります:

{ \displaystyle
W^{(1)} = \begin{bmatrix}
  w^{(1)}_{1,0} & w^{(1)}_{1,1} & w^{(1)}_{1,2} \\
  w^{(1)}_{2,0} & w^{(1)}_{2,1} & w^{(1)}_{2,2}
\end{bmatrix} \\
W^{(2)} = \begin{bmatrix}
  w^{(2)}_{1,0} & w^{(2)}_{1,1} & w^{(2)}_{1,2}
\end{bmatrix}
}

出力側の W(2) から考えてみます。簡単のため1要素についてのみ考えます:

{ \displaystyle
\frac{\partial E}{\partial w^{(2)}_{1,0}} =
\frac{\partial E}{\partial u^{(2)}} \frac{\partial u^{(2)}}{\partial w^{(2)}_{1,0}} =
-yo^{(1)}_0
}

よって出力層の重みについては微分可能です。次は隠れ層の W(1) について考えます。やはり1要素についてのみ考えると:

{ \displaystyle
\frac{\partial E}{\partial w^{(1)}_{1,0}} =
\frac{\partial E}{\partial o^{(1)}_1} \frac{\partial o^{(1)}_1}{\partial u^{(1)}_1} \frac{\partial u^{(1)}_1}{\partial w^{(1)}_{1,0}}
}

この3項を個別に求めると:

{ \displaystyle
\frac{\partial E}{\partial o^{(1)}_1} =
\frac{\partial E}{\partial u^{(2)}} \frac{\partial u^{(2)}}{\partial o^{(1)}_1} =
-yw^{(2)}_{1,1} \\
\frac{\partial o^{(1)}_1}{\partial u^{(1)}_1} = f'^{(1)}(u^{(1)}_1) \\
\frac{\partial u^{(1)}_1}{\partial w^{(1)}_{1,0}} = x_0
}

よって、全て代入して

{ \displaystyle
\frac{\partial E}{\partial w^{(1)}_{1,0}} = -yw^{(2)}_{1,1}f'^{(1)}(u^{(1)}_1)x_0
}

となり、隠れ層の重みについても微分可能です。これで勾配がわかるので、後は勾配降下法により学習可能です。

ということでPythonコードを書いてみました。今回は重みを乱数で初期化し、隠れ層の活性化関数と学習率をコマンドラインから与える方式にしています。シグモイド関数を指定し、学習率を 0.1 としたときの出力例を示します:

#------------------------------------------------------------
# Learning "AND" (eta=0.1)
w1 = [[-0.11631637 -0.32964966 -0.76916355]
 [ 0.05914025 -0.94074692  0.49658873]]
w2 = [ 0.4131751  -0.8584504  -0.27154784]

# Test "AND"
[1 0 0] -> -1
[1 0 1] -> -1
[1 1 0] -> -1
[1 1 1] -> 1

#------------------------------------------------------------
# Learning "OR" (eta=0.1)
w1 = [[-0.12387904  0.52193623 -0.35688955]
 [-0.25589149 -1.01165379 -0.52477719]]
w2 = [ 0.15433217  0.06677338 -0.56990398]

# Test "OR"
[1 0 0] -> -1
[1 0 1] -> 1
[1 1 0] -> 1
[1 1 1] -> 1

#------------------------------------------------------------
# Learning "XOR" (eta=0.1)
w1 = [[ 0.26898265  0.64685031 -1.14389473]
 [-2.09612791 -1.51971218  1.74802215]]
w2 = [-0.69779446  0.9496701   1.01464362]

# Test "XOR"
[1 0 0] -> -1
[1 0 1] -> 1
[1 1 0] -> 1
[1 1 1] -> -1

今回はXORも正しく学習できています。なお、隠れ層の活性化関数として恒等関数(identity)も選べますが、これは線形関数なのでXORは正しく学習できません。前述の記事の第3回でXORはOR, NAND, ANDの組み合わせで実現できると述べられていますが、これはORとNANDの出力がステップ関数などの非線形関数を通したものだからということです。

実は今回はSLPのときと違って色々ハマり所があります。まず、全ての重みを0初期化すると隠れ層の活性化関数が何であってもXORは正しく学習できなくなります。これは全ての重みが0だと実質SLPと変わらなくなるためだと思われます。隠れ層の重みが全て0なので隠れ層のユニット値は全て0になり、出力層の重みも全て0なので、隠れ層の2ユニットの重みが毎回同じように更新されてしまい、実質1ユニットと変わらなくなってしまいます。ということで今回は重みを乱数で初期化しています。

これに伴い、学習成功率が100%ではなくなっています。実験した結果シグモイド関数で学習率0.1なら安定して学習できるように見えますが、活性化関数や学習率を変えると結構学習失敗が起こります(AND, ORすら学習できないこともあります)。そもそも収束判定を行っていないのと、重みを初期化する際の乱数の範囲が -1.0 から 1.0 なので場合によっては非常に0に近い値で初期化されることなどが原因なのかなぁと思いますが、正直よくわかってません。ちゃんと理論を勉強しなさいというのが結論かなと思いますが、ひとまずハマり所はある程度実感できたということで。

*1:前述の記事の第3回にある通り、XORはOR, NAND, ANDの組み合わせで実現できるので、隠れ層のユニット数は2で足りるはず。

単純パーセプトロンを書いてみる

今更感漂うネタですが簡単なパーセプトロンのコードを書いてみたいと思います。高卒でもわかる機械学習というシリーズが非常にわかりやすかったのですが、動くコードがなかったのでそこだけ補完してみようという感じです。

今回は単純パーセプトロン(Single Layer Perceptron, SLP)でAND, ORを学習してみます(ついでにXORが学習できないことも確かめます)。内容的には前述の記事の第2回, 第3回に相当します。これらの記事を前提とするので記号などはちゃんとした定義なしにいきなり使ったりします。ご了承ください。

SLPということで層は入力層と出力層の2つだけです。またAND, ORということは2つの論理値から1つの論理値を計算するので、入力層のユニット数は2(バイアス除く), 出力層のユニット数は1となります。

         in  out
          o

{0,1} --> o

{0,1} --> o   o --> {-1,1}

計算の都合上、出力層からの出力は {0,1} ではなく {-1,1} とし、訓練データの形式もこれに合わせます(False が -1 になるだけです)。入力側は普通に {0,1} とします。例えばANDの真理値表は以下のようになります:

a b a AND b
0 0 -1
0 1 -1
1 0 -1
1 1 1

言い換えると、出力層の活性化関数をこのように定義します:

{ \displaystyle
f(u) = \begin{cases}
   1 & (u \ge 0) \\
  -1 & (u < 0)
\end{cases}
}

学習は訓練データ1件ごとのオンライン学習とし、誤差関数を以下のように定義します*1:

{ \displaystyle
E = max(0, -yu)
}

u は出力層のユニット値(w*x), y は教師データです。前述の通り出力側の値は {-1,1} としているので、SLPが正解を出力したら u と y は同符号、不正解なら異符号となります。重み w の更新は不正解時のみ行うので、実質的には

{ \displaystyle
E = -yu
}

と考えて問題ありません。これは明らかに重み w の各要素について微分可能で、例えば

{ \displaystyle
\frac{\partial E}{\partial w_0} = -yx_0
}

となります。これで勾配がわかるので、後は勾配降下法により学習可能です。

ということでPythonコードを書いてみました。AND, OR, XORそれぞれについて教師データを与え、10000セット学習させています*2。一応学習率ηは 0.01 に設定していますが、重みを0初期化しているので学習率は結果に影響しないはずです*3。出力はこんな感じになります:

#------------------------------------------------------------
# [AND]
#------------------------------------------------------------
### Learning ###
w = [-0.03  0.02  0.01]

### Test ###
[1 0 0] -> -1
[1 0 1] -> -1
[1 1 0] -> -1
[1 1 1] -> 1

#------------------------------------------------------------
# [OR]
#------------------------------------------------------------
### Learning ###
w = [-0.01  0.01  0.01]

### Test ###
[1 0 0] -> -1
[1 0 1] -> 1
[1 1 0] -> 1
[1 1 1] -> 1

#------------------------------------------------------------
# [XOR]
#------------------------------------------------------------
### Learning ###
w = [ 0.   -0.01  0.  ]

### Test ###
[1 0 0] -> 1
[1 0 1] -> 1
[1 1 0] -> -1
[1 1 1] -> -1

予想通り、AND, ORは学習できていますがXORは正しく学習できていません(XORは線形分離不能)。次回は隠れ層を増設した多層パーセプトロン(Multi Layer Perceptron, MLP)でXORも含めて学習してみたいと思います。

*1:バッチ学習だとリンク先の式をそのまま使うことはできないと思われるので、リンク先にある通りオンライン学習としました。

*2:実は数回で学習は終わっていますが、収束判定とかはとりあえず考えないことにします。

*3:重み更新式より、初期重みが0なら最終的な重みはηの定数倍となり、η自体は出力結果に影響しない。ちゃんとした本にはこの辺の証明も書いてあるらしいです。

ゲームの自動プレイAIに関する妄想

別に上手くなくていいので普通プレイができるAIがあるとTAS制作が色々捗るんだろうなぁと思ったりしてます(まぁ、それが難しいんでしょうけど)。AIだけで人間が作ったTASを超えるのは(ゲームにもよるでしょうが)難しいんじゃないかなと思いますが、逆にテクニックなりバグなりを探す際に自動プレイAIがあると非常に便利そうです。

基本的にバグ探しは数をこなしてナンボだと思いますが、大量に数をこなせるほどプレイヤー人口が多いゲームって全体から見ると少ないんですよね。マイナータイトルは真面目に調べると大抵変な挙動とかバグが新たに見つかりますし。なのでAIでプレイ記録を大量に蓄積するだけでも色々と新しい発見はあるのではないかと思ったりしてます(データだけあっても見るべきところを探すのが大変なので、異常検知システムみたいなものと組み合わせる必要がありそうですが)。

OpenAI GymのFrozenLakeをQ学習で解く

前回はFrozenLakeを自前のアルゴリズムで解いてみました。今回はQ学習をやってみようと思います。

その前に、前回変な結論を出してたので訂正しておきます。前回8x8が通らなかったのは明らかに試行回数不足だと思います。1エピソードあたりの成功報酬が1なので、平均報酬はそのまま勝率を表すことになりますが、通算勝率が 0.88 なら100回中99回勝つ確率は 0.00004 程度なので、10000回では明らかに試行回数が足りないです。実際に1000000回試行したものを提出したら約10万回で通りました(ついでに初手だけ修正)。通算勝率がもう少し悪くてもこれだけ試行すれば通るはずなので、この問題に関してはいい所取り100回より通算勝率を見る方がいいかも?

また、提出前に要求水準を満たしているか調べる方法がないのかと思ってモニタのソースを読んだりしたのですが、よくわからなかったので自前で通算/いい所取り平均報酬を計算するスクリプトを書きました。使い方はモニタが出力したjsonを食わせるだけです。

今回はOpenAI Gymの本来の趣旨通りに強化学習で解いてみることにします。学習法はとりあえずQ学習にします(今のところこれくらいしか知りません)。

前提として、学習ができるためにはある程度の成功体験が必要ということがあります。学習中は何らかの方策に従って探索を行いますが、その探索でゴールに辿り着ける確率があまりに低いと学習が進みにくいと考えられます。簡単な基準として4x4, 8x8それぞれに対し完全なランダムプレイを100000エピソード行い、平均報酬を調べてみました:

環境 平均報酬
4x4 0.014
8x8 0.002

どちらもかなり低い値なので、学習中もゴールに辿り着きやすくなるように方策を工夫するか、もしくは単純に学習回数を増やすなどの対処が必要かもしれないと考えられます。

本題のQ学習に入ります。理論的なことは私より詳しい方がたくさんネット上に資料を上げてくれているので省略しますが、学習の大まかな流れは以下のようになると思います:

  • 行動価値関数 Q(s,a) を任意に初期化(テーブルとして保持)
  • 以下を一定エピソード数繰り返す:
    • 状態 state を初期化
    • 以下を一定ステップ数繰り返す(ここではターン制限まで):
      • 何らかの方策により行動 act を決定
      • act を実行し、次状態 state_next, 報酬 reward を得る
      • Q(state,act) := (1-alpha) * Q(state,act) + alpha * (reward + gamma * max_a(Q(state_next,a)))
      • state := state_next
      • state が終端状態なら break

少し難しい問題になると状態空間が大きかったりして Q(s,a) をテーブルで持つことが不可能になって関数近似…とかいう話になるようですが、この問題では状態数16, 行動数4なのでそのままテーブルで持てます(というか、この問題を選んだ理由がそれだったりします)。

ここで alpha は学習率、gamma は割引率です。割引率は Q(s,a) が発散するのを防ぐとともに、同じ報酬なら遠い未来より近い未来のものを優先するといった効果をもたらすようです。

学習中の行動は「何らかの方策」により決定されるとしていますが、Q学習ではこの方策は任意ということみたいです。要は状態と行動の全ての組み合わせを網羅できるような方策であれば十分学習を繰り返せば Q(s,a) は正しく収束するということです。

実装ですが、とりあえずシンプルにしたいので「何らかの方策」はランダムプレイでやってみることにします。前述の通りこれだとなかなか成功しないので学習が遅くなりそうですが、そこは回数でカバーすることにします。

パラメータはとりあえず alpha=0.1, gamma=0.99 としました。多少実験はしましたがほとんど野生の勘で決めてます。一応学習自体はできてるっぽいのであまり深く考えない方向で。

以上の設定で106回学習後に106回テストしたところ4x4は問題なく解けました(スクリプト添付)。

同じ設定で8x8も106回学習後に106回テストしてみましたが、通算勝率 0.85, いい所取り100エピソードの平均勝率 0.98 でわずかに足りませんでした。通算勝率 0.85 だと100回中99回勝てる確率は 0.0000015 程度なので、確かに106回のテストでは通らない可能性もあります。そこで同じ設定で学習回数を107に増やしてみましたが、なぜか通算勝率 0.82, いい所取り 0.97 と成績が落ちてしまいました。原因はよくわかりませんが、ブレるということはまだ収束しきっていないのかもしれません。

学習率や割引率をいじったりしてみましたがほとんど成績が落ちるだけだったので、やはり学習時の探索がランダムプレイなせいで成功体験が少ないのが問題なのかと考えました。ということで、学習中にもQ関数を使って行動を決定するようにして、ある程度の探索を保証するためにε-greedy法(確率εでQ関数を無視してランダム選択を行う)を使うようにしてみました。

alpha=0.1, gamma=0.99, epsilon=0.1 で106回学習後に106回テストしてみたところ、一応8x8も解けました(スクリプト添付)。通算勝率は 0.864 で、自前のアルゴリズムに比べると少し劣るのでまだ改善の余地はあるのかもしれませんが、とりあえず通ったのでよしとしておきます。