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=20まで): https://gist.github.com/nishio/8d2dd6511df11c0aa78b542c7563b2a8

追加実験(S=40, 60): https://gist.github.com/nishio/905160abc7766fcf239e6c7854465172

この実験結果を見て「え、なんでこんなに中間層少なくてOKなの？バグってない？」と思ったのだけども、

そもそも状態遷移図はS*Nのone-hotで入力を入れるなら中間層すらなしで実現できる。(図2)

この問題は「中間層を置くことでone-hotのS*Nを2-hotのS+Nに置き換えるとしたら中間層のサイズはいくつ必要か」と言える

で、これが思った以上に圧縮される。 see 恒等写像を学習する

というわけで思ったより小さく単純な多層パーセプトロンで状態遷移図を表現することができる。

連想: 状態のベクトル空間への埋め込み