An Approximate Method for Finite Automata Identification Problem via Higher-Order Elman Neural Networks

未知の正則言語の正例と負例の集合が与えられたとき,これと無矛盾なN状態以下の有限オートマトンを求める問題は,有限オートマトン同定問題とよばれNP-完全である.ニューラルネットワークの学習能力に基づき,有限オートマトン同定問題の近似解を求める場合.定められた状態数以下の有限オートマトンのみが解となるような学習モデルが必要となる.また,解の存在を保証するためには,初期状態の最終状態集合への所属を学習時に決定できる仕組みが必要となる.本論文では,「log_2N⌉次元空間内の点{(P_l,P_2,…,P「log_2N&recil;):P_i∈{0,1}}の近傍にニューラルネットワークの状態を集約し,結合重みに制約を加えて同値な状態集合を構成することで,状態数制約を満足できる近似解法を提案する.初期状態の所属を決定するために,所属を判別する出力ユニットを備える高次Elman型ニューラルネットワークを構成する.勾配法に基づく学習アルゴリズムを用いて初期状態の所属を学習により決定することを可能とする.富田文法とランダム生成文法を例とし,この学習モデルが状態数制約を満たす有限オートマトンを11%から93%の割合で同定できることを計算機実験により確認する.Identification of an automaton with N states which agrees with a finite set of positive or negative examples is NP-complete. In order to get a solution approximately via learning method for neural networks, learning models which can realize any finite automata with in N states are needed. In addition, the learning models need to determine the assignment of initial state for final states set. In this paper, we propose a approximate method which can satisfy the limitation of states. The neighbourhoods of {(P_l,P_2,…,P「log_2N⌉):P_i∈{0,1}} vertices in [log_2N&recil; dimensional space are regarded as gathering points. We propose Higher-Order Elman Neural Network with output unit which assigns the initial state. We derive a learning algorithm which can determine the assignment by use of gradient method. We show that our learning model can identify the automata in a ratio from 11% to 93% within provided number of states by computer simulation