Reber Grammar

The reber grammar can be used for generating artifical data for the evaluation of recurrent neural networks.

A valid string can be generated by the following automaton.

Example: BTSSXXTVVE is a valid string in the grammar.

Embedded Reber Grammar

The embedded reber grammar is an extension of the "standard" reber grammar:

So the string generated from the standard reber grammar BTSSXXTVVE can be embedded in two ways:

• BTBTSSXXTVVETE
• BPBTSSXXTVVEPE

Note that the second char is always the same as the second last char. This is an example of a long range dependency.

Training data

For training a recurrent network with valid reber grammar strings each char of the string (char sequence) is represented by a 7-bit Vector. The postions correspond to 'BTSXPVE', for example S is coded as 0010000.

For the target we mark all possible outcomes. For example the start of the string BPBTS... is codes by the following training sequence:

       input       target
t=1    10000000    0100100
t=2    00000100    1000000
t=3    10000000    0100100
t=4    00100000    0011000
...        ...


Alternatively the target could correspond to exact one of the possible outcomes.

Output squashing and cost function

For simplicity we assume that the elements of the target vector are independent. So the output activation is a logistic function (not softmax) and the cost is the (Bernoulli) cross entropy cost.

Implementation

The following python code generates reber grammar data.

In [1]:
#!/usr/bin/python

import numpy as np

chars='BTSXPVE'

graph = [[(1,5),('T','P')] , [(1,2),('S','X')], \
[(3,5),('S','X')], [(6,),('E')], \
[(3,2),('V','P')], [(4,5),('V','T')] ]

def in_grammar(word):
if word[0] != 'B':
return False
node = 0
for c in word[1:]:
transitions = graph[node]
try:
node = transitions[0][transitions[1].index(c)]
except ValueError: # using exceptions for flow control in python is common
return False
return True

def sequenceToWord(sequence):
"""
converts a sequence (one-hot) in a reber string
"""
reberString = ''
for s in sequence:
index = np.where(s==1.)[0][0]
reberString += chars[index]
return reberString

def generateSequences(minLength):
while True:
inchars = ['B']
node = 0
outchars = []
while node != 6:
transitions = graph[node]
i = np.random.randint(0, len(transitions[0]))
inchars.append(transitions[1][i])
outchars.append(transitions[1])
node = transitions[0][i]
if len(inchars) > minLength:
return inchars, outchars

def get_one_example(minLength):
inchars, outchars = generateSequences(minLength)
inseq = []
outseq= []
for i,o in zip(inchars, outchars):
inpt = np.zeros(7)
inpt[chars.find(i)] = 1.
outpt = np.zeros(7)
for oo in o:
outpt[chars.find(oo)] = 1.
inseq.append(inpt)
outseq.append(outpt)
return inseq, outseq

def get_char_one_hot(char):
char_oh = np.zeros(7)
for c in char:
char_oh[chars.find(c)] = 1.
return [char_oh]

def get_n_examples(n, minLength=10):
examples = []
for i in xrange(n):
examples.append(get_one_example(minLength))
return examples

emb_chars = "TP"

def get_one_embedded_example(minLength=10):
i, o = get_one_example(minLength)
emb_char = emb_chars[np.random.randint(0, len(emb_chars))]
new_in = get_char_one_hot(('B',))
new_in += get_char_one_hot((emb_char,))
new_out= get_char_one_hot(emb_chars)
new_out+= get_char_one_hot('B',)
new_in += i
new_out += o
new_in += get_char_one_hot(('E',))
new_in += get_char_one_hot((emb_char,))
new_out += get_char_one_hot((emb_char, ))
new_out += get_char_one_hot(('E',))
return new_in, new_out

def get_n_embedded_examples(n, minLength=10):
examples = []
for i in xrange(n):
examples.append(get_one_embedded_example(minLength))
return examples

In [4]:
get_one_embedded_example() # pair (train-sequence, target-sequence)

Out[4]:
([array([ 1.,  0.,  0.,  0.,  0.,  0.,  0.]),
array([ 0.,  1.,  0.,  0.,  0.,  0.,  0.]),
array([ 1.,  0.,  0.,  0.,  0.,  0.,  0.]),
array([ 0.,  1.,  0.,  0.,  0.,  0.,  0.]),
array([ 0.,  0.,  0.,  1.,  0.,  0.,  0.]),
array([ 0.,  0.,  0.,  1.,  0.,  0.,  0.]),
array([ 0.,  1.,  0.,  0.,  0.,  0.,  0.]),
array([ 0.,  0.,  0.,  0.,  0.,  1.,  0.]),
array([ 0.,  0.,  0.,  0.,  1.,  0.,  0.]),
array([ 0.,  0.,  0.,  1.,  0.,  0.,  0.]),
array([ 0.,  0.,  0.,  0.,  0.,  1.,  0.]),
array([ 0.,  0.,  0.,  0.,  1.,  0.,  0.]),
array([ 0.,  0.,  0.,  1.,  0.,  0.,  0.]),
array([ 0.,  1.,  0.,  0.,  0.,  0.,  0.]),
array([ 0.,  0.,  0.,  0.,  0.,  1.,  0.]),
array([ 0.,  0.,  0.,  0.,  0.,  1.,  0.]),
array([ 0.,  0.,  0.,  0.,  0.,  0.,  1.]),
array([ 0.,  1.,  0.,  0.,  0.,  0.,  0.])],
[array([ 0.,  1.,  0.,  0.,  1.,  0.,  0.]),
array([ 1.,  0.,  0.,  0.,  0.,  0.,  0.]),
array([ 0.,  1.,  0.,  0.,  1.,  0.,  0.]),
array([ 0.,  0.,  1.,  1.,  0.,  0.,  0.]),
array([ 0.,  0.,  1.,  1.,  0.,  0.,  0.]),
array([ 0.,  1.,  0.,  0.,  0.,  1.,  0.]),
array([ 0.,  1.,  0.,  0.,  0.,  1.,  0.]),
array([ 0.,  0.,  0.,  0.,  1.,  1.,  0.]),
array([ 0.,  0.,  1.,  1.,  0.,  0.,  0.]),
array([ 0.,  1.,  0.,  0.,  0.,  1.,  0.]),
array([ 0.,  0.,  0.,  0.,  1.,  1.,  0.]),
array([ 0.,  0.,  1.,  1.,  0.,  0.,  0.]),
array([ 0.,  1.,  0.,  0.,  0.,  1.,  0.]),
array([ 0.,  1.,  0.,  0.,  0.,  1.,  0.]),
array([ 0.,  0.,  0.,  0.,  1.,  1.,  0.]),
array([ 0.,  0.,  0.,  0.,  0.,  0.,  1.]),
array([ 0.,  1.,  0.,  0.,  0.,  0.,  0.]),
array([ 0.,  0.,  0.,  0.,  0.,  0.,  1.])])