論文ではなくてリサーチ記事.
Finite State Machine (FSM) を考える. ここで考える FSM は次のようなもの.
ただし全て有限の空間で考えてる.
初期状態は長さ \(|S|\) の one-hot ベクトルで与える. \(\rho\) から出力 \(I \times S \to O\) を取り出したものを3次テンソル
\[R \in \mathbb{R}_{I,S}^O\]で書いて, 状態の遷移 \(I \times S \to S\) を取り出したものを3次テンソル
\[T \in \mathbb{R}_{I,S}^S\]で書く. これで, 入力を長さ \(I\) のベクトル \(x\) , 状態を長さ \(|S|\) のベクトル \(s\) で書くと,
というテンソル積の計算で求まる.
決定的なマシンは \(R,T\) を \({0,1}\) のテンソルとして与えることで表現される. また \(s_0\) も one-hot ベクトルとしてある. これを緩めて非負実数からなるテンソルとベクトルとすることで確率的マシンとして動作する. さらに緩めて実数全体範囲で, それらを学習するパラメータだとすることで, FSM の学習ができそう.
この記事では次の小さなオートマトンを題材に実験する.
学習データとして与えられるのは入力列と出力列のペア. オートマトンが持つ状態数はわからないので, 実験では 8 あるとしてある. Adam (lr=0.25) で学習すると上手くロスは下がって 400 イテレーションで十分収束した. できたモデルを見ると 8 つある状態を全て使っていて真のオートマトンとはまた別なものになっていそう.
そこでエントロピー罰則項を設ける. 全ステップでの状態 \(s\) のエントロピーが小さいほど良い（つまり偏っているほど良くて one-hot ベクトルになっているのが最適）とする.
\[p_i = \frac{1}{N} \sum_t s^t_i\] \[H = - \sum_i p_i \log(p_i)\]ここで \(s^t_i\) は時刻 \(t\) における状態 \(s\) の第 \(i\) 成分の値. これを足した平均を \(p_i\) としている. これを \(w = 0.01\) 倍したものをロスに加えて学習させた.
\[L = L_{\mathrm{FSM}} + w H\]すると状態 8 を使う設定で学習した結果, 2 状態だけを使うオートマトンが得られた.
実験では \(w=0.01\) が最適だったが, 100 回実験を回すと 2 状態になるのは 40 回で, 残りの 60 回では 3 状態以上を使うものになった. 学習の安定性はその程度. この回数は \(w\) を大きくするに連れて増えるが, エラーも増える.
パラメータは最初全て \(\epsilon \times \mathcal{N}(0,1)\) で初期化してあるが, \(T\) の対角成分だけ
\[T_{s}^s \sim 1 + \epsilon \times \mathcal{N}(0,1)\]という風に \(1\) だけ加えて初期化すると, 学習が安定化したそう. \(w=0.01\) で 100 回回して, 100 回が状態 2 になった.
他に 4 状態くらいのオートマトンを 6 種類作って試したが, 全て上手く学習できた.