이진 삼차 재귀 신경망과 유전자 알고리즘을 이용한 문맥-자유 문법의 추론

다국어 초록 (Multilingual Abstract)

We present the method to infer Context-Free Grammars by applying genetic algorithm to the Binary Third-order Recurrent Neural Networks(BTRNN). BTRNN is a multiple-layered architecture of recurrent neural networks, each of which is corresponding to an input symbol, and is combined with external stack. All parameters of BTRNN are represented as binary numbers and each state transition is performed with any stack operation simultaneously. We apply Genetic Algorithm to BTRNN chromosomes and obtain the optimal BTRNN inferring context-free grammar of positive and negative input patterns. This proposed method infers BTRNN, which includes the number of its states equal to or less than those of existing methods of Discrete Recurrent Neural Networks, with less examples and less learning trials. Also BTRNN is superior to the recent method of chromosomes representing grammars at recognition time complexity because of performing deterministic state transitions and stack operations at parsing process. If the number of non-terminals is p, the number of terminals q, the length of an input string k, and the max number of BTRNN states m, the parallel processing time is O(k) and the sequential processing time is O(km).

참고문헌 (Reference)

1 정순호, "정규문법과 동등한 일반화된 이진 이차 재귀 신경망" 한국지능정보시스템학회 12 (12): 107-123, 2006

2 C. L. Giles, "The effect of higher order in recurrent neural networks : Experiments, In Artificial Neural Networks for Speech and Vision" Chapman & Hall 54-78, 1993

3 N. S. Chouney, "Stochastic Mutation Approach for Grammar Induction Using Genetic Algorithm" 143-146, 2010

4 C. L. Giles, "Second-order recurrent neural networks" 4 (4): 393-405, 1972

5 N. S. Choubey, "PDA Simulator for CFG Induction Using Genetic Algorithm" 92-97, 2010

6 I. Tsoulos, "Neural network construction and training using grammatical evolution" Neurocomputing 1-9, 2008

7 S. Lawrence, "Natural Language Grammatical Inference with RNN" 12 (12): 2000

8 S. Porat, "Learning automata from ordered examples" 7 (7): 109-138, 1991

9 C. L. Giles, "Learning and Extracting finite state automata with second-order recurrent neural networks" 4 (4): 393-405, 1992

10 J. E. Hopcroft, "Introduction Automata Theory, Languages, and Computation" Addison-Wesley 217-232, 1979

11 K. Fu, "Grammatical inference : Introduction and survey" 8 (8): 343-375, 1986

12 U. Harigopal, "Grammatical Inference using Higher Order Recurrent Neural Networks" 338-342, 1993

13 E. Rodrigues, "Genetic Programming for Induciton of Context-free Grammars" 297-302, 2007

14 M. W. Goudreau, "First-order versus second-order single-layer recurrent neural networks" 5 (5): 511-513, 1994

15 A. Cleeremans, "Finite state automata and simple recurrent networks" 1 (1): 327-381, 1989

16 J. L. Elman, "Finding structure in time" 14 : 179-211, 1990

17 Z. Zeng, "Discrete recurrent neural networks forgrammatical inference" 5 (5): 320-330, 1994

18 P. Wyard, "Context Free Grammar Induction Using Genetic Algorithm" 828-831, 1994

19 H. M. Pandey, "Context Free Grammar Induction Library Using Genetic Algorithms" 752-758, 2010

20 윤현수, "Binary second-order recurrent neural networks for inferring regular grammars" IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG E83D (E83D): 1996-2007, 200011