|
NeuroCOLT
Technical Report NC-TR-96-035
A
recurrent network that performs a context-sensitive prediction task
Mark
Steijvers
Indiana University
Peter
Grünwald
CWI, Dept. of Algorithmics
The Netherlands
Abstract
We address the problem of processing a context-sensitive language
with a recurrent neural network (RN). So far, the language processing
capabilities of RNs have only been investigated for regular and context-free
languages. We present an extremely simple RN with only one parameter
for its two hidden nodes that can perform a prediction task on sequences
of symbols from the language $\{ (ba^{k})^n \mid k \geq 0, n >
0 \}$, a language that is context-sensitive but not context-free.
The input to the RN consists of any string of the language, one symbol
at a time. The network should then, at all times, predict the symbol
that should follow. This means that the network must be able to count
the number of $a$'s in the first subsequence and to retain this number
for future use. Our network can solve the task for $k=1$ up to $k=120$.
The network represents the count of $a$'s in the subsequence by having
different limit cycles for every different number of $a$'s counted.
The limit cycles are related in such a way that the representation
of network states in which an $a$ should be predicted are linearly
separable from those in which a $b$ should be predicted. Our work
shows that connectionism in general can handle more complex formal
languages than was previously known.
Download Compressed
Postscript
|