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通りの入力全てを正解できたサイズを表にした。
全パターン正解に必要な中間層の数
↓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 |
実験(S=20まで): https://gist.github.com/nishio/8d2dd6511df11c0aa78b542c7563b2a8 | ||||
追加実験(S=40, 60): https://gist.github.com/nishio/905160abc7766fcf239e6c7854465172 |
この実験結果を見て「え、なんでこんなに中間層少なくてOKなの?バグってない?」と思ったのだけども、 そもそも状態遷移図はSNのone-hotで入力を入れるなら中間層すらなしで実現できる。(図2) この問題は「中間層を置くことでone-hotのSNを2-hotのS+Nに置き換えるとしたら中間層のサイズはいくつ必要か」と言える で、これが思った以上に圧縮される。 see 恒等写像を学習する
というわけで思ったより小さく単純な多層パーセプトロンで状態遷移図を表現することができる。
連想: 状態のベクトル空間への埋め込み