状態遷移図の学習
S状態N入力の状態遷移図を学習するのにどの程度の規模のニューラルネットワークが必要か。 当初「O(S^2)のサイズの中間層2枚が必要」と思っていたが、だいぶ小さいもので学習できたので限界を探ってみた。
入力はS次元のone-hotとN次元のone-hotをconcatしたもの。
出力は新しい状態S次元のone-hot。
状態遷移表はランダムに生成する。
現実にはもっと構造があって圧縮が効きやすい。ランダムは一番難しい問題。
S * N通りの入力について1つのSが決まる
活性化関数はReLU
early_stopping=Falseとする。Trueだと学習が始まる前にstopしてしまうため。
中間層のサイズを小さい方から試していき、S * N通りの入力全てを正解できたサイズを表にした。
table:全パターン正解に必要な中間層の数
↓S\N→ 3 10 30 100
3 4 8 8 8
6 8 8 16 24
10 8 16 24 36
13 8 16 32 60
16 8 8 36 60
20 8 8 32 90
40 16 28 60 135
60 16 28 90 135
この実験結果を見て「え、なんでこんなに中間層少なくてOKなの？バグってない？」と思ったのだけども、
そもそも状態遷移図はS*Nのone-hotで入力を入れるなら中間層すらなしで実現できる。(図2)
この問題は「中間層を置くことでone-hotのS*Nを2-hotのS+Nに置き換えるとしたら中間層のサイズはいくつ必要か」と言える
https://gyazo.com/d70cfab3fd55d1a5ea810e2f5c25eb15
というわけで思ったより小さく単純な多層パーセプトロンで状態遷移図を表現することができる。