Evolving context-free language predictors
Mikael Bodén, Henrik Jacobsson, Tom Ziemke · 2000
Recurrent neural networks can represent and process simple context-free languages. However, the difficulty of finding with gradient-based learning appropriate weights for context-free language prediction motivates an investigation on the applicability of evolutionary algorithms. By empirical studies, an evolutionary algorithm proves to be more reliable in finding prediction solutions to a simple CFL. Moreover, the evolutionary algorithm demonstrates greater diversity by making use of a larger repertoire of dynamical behaviors for solving the problem. 1 INTRODUCTION A series of investigations (Wiles and Elman, 1995; Tonkes et al., 1998; Rodriguez et al., 1999; Bod'en et al., 1999) has established that the one-step lookahead prediction task for simple context-free languages (CFLs) is difficult to learn for a Simple Recurrent Network (SRN; Elman, 1990) using a gradient-based learning algorithm. A simple CFL is 0 n 1 n which allows strings starting with any number of 0s f...