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.

reber grammar

Example: BTSSXXTVVE is a valid string in the grammar.

Embedded Reber Grammar

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

embedded 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.])])