\documentclass[a4paper,10pt,twocolumn]{article}
\usepackage{aics2006}
\usepackage{curves}

\usepackage[dvips]{graphicx}

% If you use a LaTeX that does not use vector fonts by default 
% uncomment the following \usepackage line.
%\usepackage{times}
% Most packages (e.g., MiKTeX) will automatically use vector fonts.

%%\pagestyle{empty}
%%\pagenumbering{}
% Modify the \setlength values below to suit your LaTeX, dvi2ps and ps2pdf programs
% When printing with Acrobat, make sure that the option 
% ``Auto-rotate and center pages'' is checked.
% Then modify the following values to satisfy the margin requirements
%%\setlength{\topmargin}{-0.5cm}
%%\setlength{\oddsidemargin}{-0.6cm} 
%%\setlength{\evensidemargin}{-0.6cm}



\begin{document}

%\title{Parsing with Fatiguing Leaky Integrate and Fire Neurons}
\title{Parsing with fLIF Neurons}

\author{Christian Huyck \& Yulei Fan,
Middlesex University\\
London, UK. c.huyck@mdx.ac.uk}

\date{}

\maketitle

\begin {abstract}
This paper presents a natural language parsing system based solely on
fatiguing Leaky Integrate and Fire neurons, a relatively faithful
model of biological neurons.  The parser implements cell assemblies,
sequences, finite state automaton and a stack.  The stack enables the
system to parse context free grammars.  The system uses variable
binding to apply the rules, and implement the stack.  A novel form of
variable binding based on short term potentiation is presented.  The
output of the system is a semantic frame of the sentence that was
parsed.  The symbolic interpretation is derived from the underlying
neural firing by a simple count of neurons that fire in a particular
cycle.  The system parses over 99\% of the tested sentences correctly.
\end {abstract}

\begin{keywords}
fatiguing LIF neuron, Cell Assembly, Natural Language Processing, Parsing.
\end{keywords}

\section{Introduction}
Perhaps the most complex task that humans perform is to understand
language.  Virtually every human can do this, but no machine
approaches the general linguistic abilities of the typical primary
school student.  One of the fundamental processes involved in
understanding language is to take a sentence of words, and combine the
meanings of the words in an order dependent fashion to get the meaning
of the entire sentence.  This is typically called parsing the
sentence.  While a great deal of effort has been put into developing
parsers, the best parsers still function below 90\% efficiency in
generating the syntax trees of sentences \cite {Collins}.  There has
been less work on semantic evaluation, but again parsers are
imperfect.

From this earlier parsing work, it is clear that ambiguities exist in
natural language and semantics are needed to resolve these
ambiguities.  Unfortunately, computational interpretation of semantics
is poor.  One way forward may be to mimic human processing at the
neural level.  This may allow a system to learn semantics in a fashion
similar to humans.

This paper presents a natural language parser implemented in fatiguing
Leaky Integrate and Fire (fLIF) neurons.  The model is a variation on
the widely used Leaky Integrate and Fire (LIF) neuron \cite {Tal}, but
these neurons fatigue when fire repeatedly; this fatigue makes it more
difficult for the neurons to fire. This improves the dynamics of the
system, by making it easier to move from one state to another, and
adds an extra degree of biological faithfulness. The actual fLIF model
is not explained in this paper but can be found elsewhere
\cite{Huyck-Tech1,Huyck-IR}.  While the fLIF model is an imperfect
model of biological neurons, it does closely approximate the basic
functions of neurons.  The model is not perfect with discrete cycles
that correspond roughly to 10 ms. of biological time. The loss of
biological faithfulness is partially compensated by the efficiency of
the model allowing a large number of neurons to be simulated in real
time.  The parser takes advantage of Cell Assemblies (CAs) \cite
{Hebb}, a concept that unifies neural and psychological theory (see section 
\ref {sec-SC}).

The parser has a small grammar and lexicon, but is able to repeatedly
generate the correct semantic representation for a number of sentences.
Moreover the parser is one component of a larger video game agent.  The
agent is an assistant to a user and takes text commands using the parser.
The agent also can view the environment and take its own actions.  The
entire agent is implemented in fLIF neurons.

The parser is a partial implementation of a psychologically plausible
symbolic parser \cite {Huyck-Plink}.  This work is similar to a Marcus
parser \cite {Marcus,Jurafsky}, and is based around a stack,
preferences for rule selection, limited look ahead, and grammar rules
that combine syntax and semantics.  

Crucially, implementation of the stack allows the parser to interpret
context free languages \cite {Aho}.  It is widely agreed that natural
languages are at least context free \cite {Pinker}.  A neural parser
is rather unique.  While other connectionist parsers have been built
(e.g.  \cite {Mikkulainen,Henderson}) the authors are aware of only
one other neural parser \cite {Knoblauch}; however, Knoblauch and
Palm's parser does not have a stack and thus is limited to regular
languages.

While parsing, variable binding is used to bind nodes to stack
elements, and to bind slot fillers to verb frames.  The semantic
representation is thus a verb frame \cite {Filmore}.  The system
described in this paper uses a novel form of variable binding based on
short-term synaptic plasticity.

\section {State Change with the System}
\label {sec-SC}

The network consists of 13 subnets shown in Figure \ref {Fig1}.
The action of the system is more fully explained in section \ref 
{sec-Arch}.  It makes extensive use of CAs for stable states, and 
pseudo-CAs for organising simple sequences of actions.


\begin{figure}
\begin{picture}(150,200)(-50,0) 
%the -25 pushes in right centering it a bit

%input box
\put(-20,160){\line(1,0){50}}
\put(-20,160){\line(0,1){30}}
\put(30,190){\line(-1,0){50}}
\put(30,190){\line(0,-1){30}}
\put(-18,180){\texttt{{\bf Input}}}
\put(-18,170){\texttt{{\bf Network}}}

%verb box
\put(50,160){\line(1,0){50}}
\put(50,160){\line(0,1){30}}
\put(100,190){\line(-1,0){50}}
\put(100,190){\line(0,-1){30}}
\put(52,180){\texttt{{\bf Verb}}}
\put(52,170){\texttt{{\bf Network}}}

%noun and other box
\put(120,160){\line(1,0){50}}
\put(120,160){\line(0,1){30}}
\put(170,190){\line(-1,0){50}}
\put(170,190){\line(0,-1){30}}
\put(122,182){\texttt{{\bf Noun and}}}
\put(122,172){\texttt{{\bf Other}}}
\put(122,162){\texttt{{\bf Network}}}

%stack box
\put(-20,110){\line(1,0){50}}
\put(-20,110){\line(0,1){30}}
\put(30,140){\line(-1,0){50}}
\put(30,140){\line(0,-1){30}}
\put(-18,130){\texttt{{\bf Stack}}}
\put(-18,120){\texttt{{\bf Network}}}

%rule box
\put(50,110){\line(1,0){50}}
\put(50,110){\line(0,1){30}}
\put(100,140){\line(-1,0){50}}
\put(100,140){\line(0,-1){30}}
\put(52,130){\texttt{{\bf Rule}}}
\put(52,120){\texttt{{\bf Network}}}

%instance box
\put(120,110){\line(1,0){50}}
\put(120,110){\line(0,1){30}}
\put(170,140){\line(-1,0){50}}
\put(170,140){\line(0,-1){30}}
\put(122,130){\texttt{{\bf Instance}}}
\put(122,120){\texttt{{\bf Network}}}

%stacktop box
\put(-20,60){\line(1,0){50}}
\put(-20,60){\line(0,1){30}}
\put(30,90){\line(-1,0){50}}
\put(30,90){\line(0,-1){30}}
\put(-18,80){\texttt{{\bf Stacktop}}}
\put(-18,70){\texttt{{\bf Network}}}

%pop box
\put(50,60){\line(1,0){50}}
\put(50,60){\line(0,1){30}}
\put(100,90){\line(-1,0){50}}
\put(100,90){\line(0,-1){30}}
\put(52,80){\texttt{{\bf Pop}}}
\put(52,70){\texttt{{\bf Network}}}

%test box
\put(120,60){\line(1,0){50}}
\put(120,60){\line(0,1){30}}
\put(170,90){\line(-1,0){50}}
\put(170,90){\line(0,-1){30}}
\put(122,80){\texttt{{\bf Test}}}
\put(122,70){\texttt{{\bf Network}}}

%skip box
\put(-20,10){\line(1,0){50}}
\put(-20,10){\line(0,1){30}}
\put(30,40){\line(-1,0){50}}
\put(30,40){\line(0,-1){30}}
\put(-18,30){\texttt{{\bf Skip}}}
\put(-18,20){\texttt{{\bf Network}}}

%push box
\put(50,10){\line(1,0){50}}
\put(50,10){\line(0,1){30}}
\put(100,40){\line(-1,0){50}}
\put(100,40){\line(0,-1){30}}
\put(52,30){\texttt{{\bf Push}}}
\put(52,20){\texttt{{\bf Network}}}

%erase box
\put(120,10){\line(1,0){50}}
\put(120,10){\line(0,1){30}}
\put(170,40){\line(-1,0){50}}
\put(170,40){\line(0,-1){30}}
\put(122,30){\texttt{{\bf Erase}}}
\put(122,20){\texttt{{\bf Network}}}


%input to verb
\put(30,170){\vector(1,0){20}}

%input to noun other
\put(70,130){\arc(50,50,180){80}}
\put(110,190){\vector(1,-1){10}}

%input to push 
\put(25,160){\vector(1,-4){30}}

%verb to and from rule 
\put(70,160){\vector(0,-1){20}}
\put(70,140){\vector(0,1){20}}
%verb to instance
\put(100,160){\vector(1,-1){20}}

%noun to rule
\put(120,160){\vector(-1,-1){20}}
%noun to instance
\put(140,160){\vector(0,-1){20}}

%stack to verb
\put(30,140){\vector(1,1){20}}
%stack to noun
\put(30,140){\vector(4,1){90}}

%rule to pop and pop to rule
\put(70,110){\vector(0,-1){20}}
\put(70,90){\vector(0,1){20}}
%rule to verb done in verb
%rule to test
\put(100,110){\vector(1,-1){20}}
%rule to stack
\put(50,125){\vector(-1,0){20}}
%rule to input
\put(50,140){\vector(-1,1){20}}
%rule to stacktop
\put(50,110){\vector(-1,-1){20}}
%rule to instance
\put(100,130){\vector(1,0){20}}

%instance to rule
\put(120,130){\vector(-1,0){20}}

%stacktop to stack
\put(10,90){\vector(0,1){20}}
%stacktop to skip
\put(10,60){\vector(0,-1){20}}
%stacktop to push
\put(30,60){\vector(1,-1){20}}

%pop to noun and verb
\put(97,95){\arc(4,-12,90){50}}
%to rule done in rule
%pop to stack
\put(50,90){\vector(-1,1){20}}
%pop to stacktop
\put(50,75){\vector(-1,0){20}}
%pop to erase
\put(100,60){\vector(1,-1){20}}

%test to noun and verb
\put(120,100){\arc(-10,-10,20){40}}
%test to push
\put(120,60){\vector(-1,-1){20}}
%test to stack
\put(120,90){\vector(-4,1){90}}
%test to instance
\put(150,90){\vector(0,1){20}}
%test to erase
\put(150,60){\vector(0,-1){20}}

%skip to stack
\put(40,60){\arc(-50,50,120){80}}
\put(-17,50){\arc(-10,-10,20){40}}
\put(-20,100){\vector(1,1){10}}

%push to noun and verb
\put(97,45){\arc(4,-12,90){50}}
%push to stack
\put(50,40){\vector(-1,4){20}}
%push to stacktop
\put(50,40){\vector(-1,1){20}}
%push to test
\put(100,40){\vector(1,1){20}}

%erase to noun and verb
\put(110,40){\line(0,1){140}}
\put(120,50){\arc(-10,-10,20){40}}
\put(100,170){\arc(10,10,20){40}}
\put(105,185){\vector(-1,0){5}}
\put(115,160){\arc(4,12,20){40}}
\put(115,172){\vector(1,0){5}}
%erase to skip
\put(81,68){\arc(-50,-50,20){80}}
\put(40,10){\vector(-1,1){10}}
%erase to pop
\put(120,40){\vector(-1,1){20}}
%erase to stack
\put(39,84){\arc(-60,-60,40){60}}
%erase to rule
\put(120,40){\vector(-1,4){20}}
%erase to test
\put(150,40){\vector(0,1){20}}

\end{picture}
\caption{Topology of the Parsing System}\label{Fig1}
\end {figure}

CAs are sets of neurons that have high mutual synaptic strength.  When
a small number of these neurons fire, they spread activation to the
others causing a cascade of firing that enables the complete CA
circuit to remain persistently active practically indefinitely
\cite{Wennekers}.  Most of the subnets in the system are broken up
into CAs.  The process of activating a CA so that it continues to 
fire persistently is called CA ignition or simply ignition.

In a given fLIF network, the ignition and persistence of a CA puts the
system into a state.  Most of our prior work (e.g. \cite {Huyck-Hier,
Huyck-IR}) has focused on these single state systems.  The network is
presented an object, the object causes a CA to ignite, this categorises
the object as a member of that CA, and this state persists indefinitely.
To categorise a new object, the system is reset with each neuron's activity
and fatigue levels reset to zero, then the new object is presented.

Unlike these single state systems, the system discussed in this paper 
is a multi-state system.  Depending on the current state and the current
input, the system moves to a new state.  

It is relatively simple to see how a fLIF network can move from one
state to the next independently of input.  This occurs in the Push,
Pop, Test and Erase sub-networks.  In each of these, the subnet is
broken up into a series of pseudo-CAs.  Neurons in each have high
mutual synaptic strength so they cause each other to fire.  However,
in a given sequence of pseudo-CAs, neurons have excitatory connections
to neurons in the next pseudo-CA and inhibitory connections to neurons
in the prior one.  So after a few cycles, the next pseudo-CA in the
sequence ignites; firing in that pseudo-CA causes the initial
pseudo-CA to cease firing because of the inhibitory connections.
Fatigue also plays a component in shutting down the prior pseudo-CA.
As these pseudo-CAs do not persist for a significant time, they are
not true CAs.

This chain of activation enables the system to execute a sequence of
events.  Unfortunately, it does not allow the system to perform different
actions depending on the input.  Fortunately, a simple mechanism
exists to enable this type of change.  One set of subnets encodes
the current state.  The current state sends activation to the possible
next states.  This activation is enough to prime those next states,
but not enough to ignite them. Similarly, the inputs also send
activation to those next states; again this activation is enough to
prime but not enough to ignite.  The combination of state and input
is, however, enough to ignite the next state.  This pragmatically,
allows the system to function as a finite state automata \cite
{Lewis}.  Combined with the stack, the system functions as a push down
automata.

\section {Overall Architecture}
\label {sec-Arch}
The architecture is based on 13 subnetworks shown in Figure \ref
{Fig1}, which shows 12 subnets and the connections between them.  In
the figure, the noun subnet and the other word subnet are combined as
their coarse external connections are identical.


Figure \ref {Fig1} is quite complex. The entire network implements the
simple parsing algorithm:

\begin{enumerate}
\item Start by pushing a word onto the stack
\item Repeat
\begin{enumerate}
\item  Test rules
\item  If no rule succeeds, 
\begin{enumerate}
\item    Push new word on stack
\end{enumerate}
\item  else (a rule succeeds)
\begin{enumerate}
\item    Apply the rule
\item    Pop stack
\end{enumerate}
\end{enumerate}
\item Until $VP \rightarrow VP Period$ rule applied
\end {enumerate}

An explanation of a parse of
the simple sentence in example 1 is provided to highlight important
aspects of the parser. For clarity, the explanation follows the
algorithm.
\centerline {Example 1. {\it Follow me.}}

{\bf Start by pushing word on stack}

Initially, portions of two subnets are activated.  The two CAs that
receive external activation are the {\it Follow} CA in the Input net
and the 0 element in the Stacktop net. This causes ignition of the
appropriate reverberating circuit in these nets, and many neurons in
these circuits will continue to fire until some other net causes them
to stop firing via inhibitory connections.

The Input, Verb, Noun, Other, Instance, Stack, Skip, and Rule subnets
are each broken into several CAs (see section \ref
{sec-SC}).  In these subnets the CAs are orthogonal so each neuron is
in only one CA.

Firing in the 0 element of the stacktop and any input CA causes
ignition of the Push subnetwork.  In essence, this is the start state of 
the automata.  The Push, Pop, Test and Erase subnetworks
execute processes via neural firing; they are not CAs per se, but are
quite similar (see section \ref {sec-SC}).  The activation of the Push
subnetwork (Pop, Test and Erase) causes a sequence of events to happen
with neural firing in the subnetwork shutting down automatically at the
end of the sequence.  This sequence is implemented by sets of neurons,
similar to CAs, that are connected to the next set of neurons in the
subnetwork.  These connections are excitatory, while reverse connections,
in the set, are inhibitory.  With the Push net, the sequence is to
increment the Stacktop, ignite the appropriate Stack element in
cooperation with the Stacktop, ignite the appropriate word CA (in this
case a Verb CA), and start the Test subnetwork.

The Stacktop is incremented by sending activation to particular neurons 
in it \footnote {The keen observer will note that the stacktop is the only
subnet that has not been specified as a sequence pseudo-CA or a subnet of
orthogonal CAs.  This is because it consists of five CAs, that are linked
with push and pop sequence manipulating neurons.  The push neurons associated
with a particular stacktop element prime the next stack element.  When a push
is generated, activation is sent to all the elements; only the primed element
ignites;  when it ignites it suppresses the prior element.  A similar 
mechanism works for pushing.}.

The appropriate Stack element is ignited by a combined activation from
push and stacktop.  Push sends activation to all the items.  Stacktop
sends activation to the item that corresponds to the active
Stacktop CA.  In this case, the only CA that is receiving activation
from both is the first Stack element.  This ignites.  Similarly, all
of the word CAs in the Verb, Noun and Other Word nets are sent
activation, but only the Follow CA receives activation from the Input
and it is the only one that ignites.  Additionally, the only symbolic
act occurs when the Push net ceases to fire; the Input net moves onto
the next word, in this case {\it me}.  This is the only symbolic act
the system performs. This symbolic act is necessary as there is no reading
component to the system.


The first Stack element is now ignited as is the Verb's {\it Follow} CA. 
The Stack element has some fast bind neurons (see Section \ref {sec-VB}) and
is now bound to {\it Follow}.  

{\bf  Test rules }

The Test subnetwork then becomes active.  It has a sequence of steps
where it shuts down activation in the Stack and the words followed by
igniting elements of the stack.  It activates each of the first three
Stack elements preceded and followed by turning them off.  It does
this twice. If the Stack elements are bound, the corresponding words
are ignited.  Activation in the word nets causes the appropriate rule
to fire.  In this case, no rule corresponds to a verb by itself and
no Rule CA is ignited.  

{\bf If no rule succeeds}

Test finishes by activating Push. Push follows a similar process to
push {\it me} on to the stack as its second element.  The second stack
element and the noun are both ignited.  There simultaneous firing
causes them to be bound.

{\bf Push new word onto stack}

When push finishes, it starts test running (and makes the period the
input).  

{\bf else (a rule succeeds)}

This time the ignition of Verb Noun causes the VP
$\rightarrow$ VP NP-object rule to fire.  Note that in the rule subnet
the leak is quite low so that a significant amount of activation is
retained.  This is important so that the activity of multiple stack
elements can be integrated into the ignition of a given rule.  The retention
of activation (the part that remains after leakage) is a form of memory
that is particularly important in the rule selection of this system.

\begin{figure}
\begin{picture}(150,200)(-50,0) 

%input box
\put(-20,160){\line(1,0){50}}
\put(-20,160){\line(0,1){30}}
\put(30,190){\line(-1,0){50}}
\put(30,190){\line(0,-1){30}}
\put(-18,180){\texttt{{\bf Input}}}
\put(-18,170){\texttt{{\bf Network}}}

%verb box
\put(50,160){\line(1,0){50}}
\put(50,160){\line(0,1){30}}
\put(100,190){\line(-1,0){50}}
\put(100,190){\line(0,-1){30}}
\put(52,180){\texttt{{\bf Verb}}}
\put(52,170){\texttt{{\bf Network}}}

\put(52,163){\line(1,0){46}}
\put(52,164){\line(1,0){46}}
\put(52,165){\line(1,0){46}}

%noun and other box
\put(120,160){\line(1,0){50}}
\put(120,160){\line(0,1){30}}
\put(170,190){\line(-1,0){50}}
\put(170,190){\line(0,-1){30}}
\put(122,182){\texttt{{\bf Noun }}}
\put(122,162){\texttt{{\bf Network}}}
\put(122,172){\line(1,0){46}}
\put(122,173){\line(1,0){46}}
\put(122,174){\line(1,0){46}}


%stack box
\put(-20,110){\line(1,0){50}}
\put(-20,110){\line(0,1){30}}
\put(30,140){\line(-1,0){50}}
\put(30,140){\line(0,-1){30}}
\put(-18,125){\texttt{{\bf Stack}}}
\put(-18,115){\texttt{{\bf Network}}}

\put(-18,135){\line(1,0){46}}
\put(-18,136){\line(1,0){46}}
\put(-18,137){\line(1,0){46}}

%rule box
\put(50,110){\line(1,0){50}}
\put(50,110){\line(0,1){30}}
\put(100,140){\line(-1,0){50}}
\put(100,140){\line(0,-1){30}}
\put(52,130){\texttt{{\bf Rule}}}
\put(52,120){\texttt{{\bf Network}}}
\put(52,111){\line(1,0){46}}
\put(52,112){\line(1,0){46}}
\put(52,113){\line(1,0){46}}

%instance box
\put(120,110){\line(1,0){50}}
\put(120,110){\line(0,1){30}}
\put(170,140){\line(-1,0){50}}
\put(170,140){\line(0,-1){30}}
\put(122,130){\texttt{{\bf Instance}}}
\put(122,120){\texttt{{\bf Network}}}

%stacktop box
\put(-20,60){\line(1,0){50}}
\put(-20,60){\line(0,1){30}}
\put(30,90){\line(-1,0){50}}
\put(30,90){\line(0,-1){30}}
\put(-18,80){\texttt{{\bf Stacktop}}}
\put(-18,70){\texttt{{\bf Network}}}

%pop box
\put(50,60){\line(1,0){50}}
\put(50,60){\line(0,1){30}}
\put(100,90){\line(-1,0){50}}
\put(100,90){\line(0,-1){30}}
\put(52,80){\texttt{{\bf Pop}}}
\put(52,70){\texttt{{\bf Network}}}

%test box
\put(120,60){\line(1,0){50}}
\put(120,60){\line(0,1){30}}
\put(170,90){\line(-1,0){50}}
\put(170,90){\line(0,-1){30}}
\put(122,80){\texttt{{\bf Test}}}
\put(122,70){\texttt{{\bf Network}}}

%skip box
\put(-20,10){\line(1,0){50}}
\put(-20,10){\line(0,1){30}}
\put(30,40){\line(-1,0){50}}
\put(30,40){\line(0,-1){30}}
\put(-18,30){\texttt{{\bf Skip}}}
\put(-18,20){\texttt{{\bf Network}}}

%push box
\put(50,10){\line(1,0){50}}
\put(50,10){\line(0,1){30}}
\put(100,40){\line(-1,0){50}}
\put(100,40){\line(0,-1){30}}
\put(52,30){\texttt{{\bf Push}}}
\put(52,20){\texttt{{\bf Network}}}

%erase box
\put(120,10){\line(1,0){50}}
\put(120,10){\line(0,1){30}}
\put(170,40){\line(-1,0){50}}
\put(170,40){\line(0,-1){30}}
\put(122,30){\texttt{{\bf Erase}}}
\put(122,20){\texttt{{\bf Network}}}

%verb to and from rule 
\put(70,160){\vector(0,-1){20}}

%noun to rule
\put(120,160){\vector(-1,-1){20}}

%test to stack
\put(120,90){\vector(-4,1){90}}

%stack to verb
\put(30,140){\vector(1,1){20}}
%stack to noun
\put(30,140){\vector(4,1){90}}

\end{picture}
\caption{Rule Activated in System}\label{Fig2}
\end {figure}


Figure \ref {Fig2} shows this rule igniting over several cycles.  The
test network activates the stack items in sequence.  The boxes represent
ignited CAs consisting of several hundred neurons.  In the figure, 
stack item 1 is ignited and is igniting the verb Follow.  Before that
stack item 2 had ignited the noun Follow.  The Rule CA has accumulated
activation from the noun, and now that the verb has ignited, enough
activation has accumulated for the rule to ignite.

{\bf Apply the rule}

The ignition of the rule causes the first and second Stack elements to
be activated simultaneously, and shuts off the Test.  The Noun {\it me} CA
has also activated an instance of {\it me} in the Instance net.  The rule
also sends activation to the object slot in all the verbs;  as the only verb
that is active is {\it Follow}, its object slot also ignites.  This
slot has fast bind neurons that bind it with the Verb and bind it
to the {\it me} CA in the instance net.  However, a semantic trace is left
in binding of the object slot to the instance net CA.

{\bf Pop stack}

The rule then causes the Pop
net to become active.  This pops the stack and starts the Erase net.

One could ask why there is an instance net as there is a one to one 
correspondence between instances and nouns.  The answer lies in the 
connection between the noun net and the rule net.  While the active
noun CA sends activation to rules, the active instance does not.  So,
once the noun has been included into a parse and is removed from the
stack, it no longer helps to apply grammar rules.

The Erase net is then activated to complete the clearing of the second
stack element.  This will be described in section \ref {sec-VB}.

{\bf Until $VP \rightarrow VP Period$ rule applied}

The result at this point is that activating the first Stack element will
ignite the Verb {\it Follow} which ignites its object {\it me}.
Reading these activations provides a symbolic semantic interpretation
of the sentence.  The parse will continue to push the period, and
eventually to run the VP $\rightarrow$ VP period rule which stops
processing of the sentence.


This entire process can be viewed as an automata.  The state of the
parser is held by the stack, and the position in the processing
subnets (push, test, pop and erase).  Push modifies the stack and thus
the state.  Test merely inspects the stack, but if the right elements
are on the stack in the right order, they will cause a rule to fire.
This causes pop to modify the stack.  Pop then passes control onto
erase which completes the modification process.  Erase finishes by
passing control back to the test subnet.



\section {Variable Binding}
\label {sec-VB}

One of the fundamental problems of neural processing and indeed 
connectionist systems in general is variable binding.  In brief,
a variable needs to be given a value that it retains for some
significant period of time.  Later, the system needs to be
able to give that variable a new value.  Variable binding
is needed to give the system compositional syntax and semantics \cite
{Fodor}.

This is a simple process in typical computers.  A variable is
associated with a portion of memory.  The memory corresponds to a value in
a circuit.  As long as the electricity is on, the circuit, and thus
the variable, will retain that value.

It is more difficult in neural systems.  One commonly used mechanism
for binding is via synchrony \cite {Shastri}.  Two sets of neurons are
bound together if they tend to fire at the same time.  Unfortunately,
this has problems supporting more than a small number of bindings.

Another option is to bind by permanently changing synaptic weights
\cite {Huyck-Count}. Most simulation of neurons involves learning by
changing synaptic weights permanently.  This is equated to the
biological phenomena of Long-Term Potentiation.  However, a 
mechanism to replace the binding with another binding is still
required.  This can be done with spontaneous neural activation, but
this takes many simulation cycles.

Another biological phenomena is Short-Term Potentiation.  Coactivation
of neurons leads to increased synaptic weights that revert back to the
original weights over time \cite {Hempel}.

This phenomena has been modelled in this simulation by neurons that we
have coined fast bind neurons. These change synaptic weights by a
simple addition of a constant when two neurons are coactive; this
weight is clipped at a maximum.  Each cycle the neurons do not cofire,
the weight is reduced until it reaches zero.

When a CA that has fast bind neurons is coactivated with another CA
that it is connected to, the two are rapidly bound.  Subsequent
ignition of the initial CA will then cause ignition of the bound
CA.  After a period of no activation of the initial CA, the binding
will be gradually but automatically erased.  

So, when a Stack element is activated, the simultaneous activation of
a word CA causes the element's fast bind neurons to rapidly increase
weight.  If the element is turned off and then on again, as the Test
net does, the fast bind neurons will ignite the word CA.  As it is
only bound to one word, only that word is ignited.  A similar process
happens when Verb slots are bound to Instance CAs.

The erase net ignites the active Stack elements, but only those
at or below the stacktop.  It does this in sequence so that, if the
Stacktop is two, the first Stack element is ignited, then shut, then
the second Element.  This is repeated three times.  This ignition
supports the binding by allowing the now reduced weights to regain
their strength.  The elements above the Stacktop are automatically
erased as they are not supported.  Skip comes in here to inhibit the
activation of Stack elements above the Stacktop. This is done by
having the skip CA inhibit the second stack element.  If the skip CA
is on, it prevents the second stack element from igniting.  The skip
CA is only turned on when the stacktop is one, and erase is trying to
activate the second stack element. Figure \ref {Fig3} shows this.
Erase typically activates stack items.  However, if the stacktop is
one, then the skip net comes on (just one CA) when erase is about to
activate stack element two.  This suppresses the ignition of stack
element 2.


\begin{figure}
\begin{picture}(150,200)(-50,0) 
%input box
\put(-20,160){\line(1,0){50}}
\put(-20,160){\line(0,1){30}}
\put(30,190){\line(-1,0){50}}
\put(30,190){\line(0,-1){30}}
\put(-18,180){\texttt{{\bf Input}}}
\put(-18,170){\texttt{{\bf Network}}}

%verb box
\put(50,160){\line(1,0){50}}
\put(50,160){\line(0,1){30}}
\put(100,190){\line(-1,0){50}}
\put(100,190){\line(0,-1){30}}
\put(52,180){\texttt{{\bf Verb}}}
\put(52,170){\texttt{{\bf Network}}}

%noun and other box
\put(120,160){\line(1,0){50}}
\put(120,160){\line(0,1){30}}
\put(170,190){\line(-1,0){50}}
\put(170,190){\line(0,-1){30}}
\put(122,182){\texttt{{\bf Noun and}}}
\put(122,172){\texttt{{\bf Other}}}
\put(122,162){\texttt{{\bf Network}}}

%stack box
\put(-20,110){\line(1,0){50}}
\put(-20,110){\line(0,1){30}}
\put(30,140){\line(-1,0){50}}
\put(30,140){\line(0,-1){30}}
\put(-18,130){\texttt{{\bf Stack}}}
\put(-18,120){\texttt{{\bf Network}}}

%rule box
\put(50,110){\line(1,0){50}}
\put(50,110){\line(0,1){30}}
\put(100,140){\line(-1,0){50}}
\put(100,140){\line(0,-1){30}}
\put(52,130){\texttt{{\bf Rule}}}
\put(52,120){\texttt{{\bf Network}}}

%instance box
\put(120,110){\line(1,0){50}}
\put(120,110){\line(0,1){30}}
\put(170,140){\line(-1,0){50}}
\put(170,140){\line(0,-1){30}}
\put(122,130){\texttt{{\bf Instance}}}
\put(122,120){\texttt{{\bf Network}}}

%stacktop box
\put(-20,60){\line(1,0){50}}
\put(-20,60){\line(0,1){30}}
\put(30,90){\line(-1,0){50}}
\put(30,90){\line(0,-1){30}}
\put(-18,80){\texttt{{\bf Stacktop}}}
\put(-18,70){\texttt{{\bf Network}}}

%pop box
\put(50,60){\line(1,0){50}}
\put(50,60){\line(0,1){30}}
\put(100,90){\line(-1,0){50}}
\put(100,90){\line(0,-1){30}}
\put(52,80){\texttt{{\bf Pop}}}
\put(52,70){\texttt{{\bf Network}}}

%test box
\put(120,60){\line(1,0){50}}
\put(120,60){\line(0,1){30}}
\put(170,90){\line(-1,0){50}}
\put(170,90){\line(0,-1){30}}
\put(122,80){\texttt{{\bf Test}}}
\put(122,70){\texttt{{\bf Network}}}

%skip box
\put(-20,10){\line(1,0){50}}
\put(-20,10){\line(0,1){30}}
\put(30,40){\line(-1,0){50}}
\put(30,40){\line(0,-1){30}}
\put(-18,30){\texttt{{\bf Skip}}}
\put(-18,20){\texttt{{\bf Network}}}

%push box
\put(50,10){\line(1,0){50}}
\put(50,10){\line(0,1){30}}
\put(100,40){\line(-1,0){50}}
\put(100,40){\line(0,-1){30}}
\put(52,30){\texttt{{\bf Push}}}
\put(52,20){\texttt{{\bf Network}}}

%erase box
\put(120,10){\line(1,0){50}}
\put(120,10){\line(0,1){30}}
\put(170,40){\line(-1,0){50}}
\put(170,40){\line(0,-1){30}}
\put(122,30){\texttt{{\bf Erase}}}
\put(122,20){\texttt{{\bf Network}}}


%stacktop to skip
\put(10,60){\vector(0,-1){20}}

%erase to skip
\put(81,68){\arc(-50,-50,20){80}}
\put(40,10){\vector(-1,1){10}}
%erase to stack
\put(39,84){\arc(-60,-60,40){60}}

%skip to stack
\put(40,60){\arc(-50,50,120){80}}
\put(-17,50){\arc(-10,-10,20){40}}
\put(-20,100){\vector(1,1){10}}


\end{picture}
\caption{Skipping Binding During Erase}\label{Fig3}
\end {figure}


\section{Results}
The parser stores a semantic representation of the sentence in the
form of a verb frame.  This subsymbolic verb frame can be readily
translated into a symbolic frame.

To retrieve the semantic interpretation of the sentence after parsing
has completed, the first stack element is ignited.  Activation is sent
to the item for 10 cycles.  This ignites it and, in each case tested,
causes ignition of the verb CA to which it is bound.  Since the verb
CAs are orthogonal, a calculation of which particular CA is ignited is
simply a matter of counting the neurons in that CA that fire in 
the tenth cycle.  For this measurement, if any neuron fires, the CA is on.
If multiple verb CAs are on, it is considered an error.

Similarly, the verb CA has 60 fast bind neurons associated with each
of its three slots (actor, object and location). If the slot has
neurons firing, it is considered on.  Again, multiple or absent slots
are considered an error.  These slot neurons have propagated
activation onto the slot fillers that they are bound to. These slot
fillers are also orthogonal and are measured in the same fashion as the
verbs and slots.

The parser was tested on 17 sentences, uses five grammar rules, and 16
words that fall into five lexical categories.  There is some
randomness in creating the system, and a random system gets roughly
90\% of the semantic representations complete. The networks can be
saved and rerun.

The best system has over 99\% performance with the calculated error
being lost on slot filler absences. In this case, the system was tested
on each of the 17 sentences 32 times.  The system only failed on
2 instances of the sentences for a performance of 542/544 or .9963.

The system can be found at http://www.cwa.mdx.ac.uk/CABot/CANT.html.  It
is written in Java and we are happy to respond to queries for help in 
installing and running the system.

Since the parser, described above, was completed, it has been integrated
into our CABot1 agent.  This is an agent in a Crystal Space video game.
The agent assists a user in the 3D environment.  The user issues commands
that the agent tries to follow.  In addition to the parser there is a 
visual subsystem, a goal propagation subsystem and a control subsystem.
The agent goes through a loop (the control system) of accepting the
user's command, parsing it, setting a goal based on the command, completing
the goal, and then erasing the stack.  Again, except for reading a new
word and sending a command to the game, all of this is done in fLIF neurons.  
This parser has a similar performance though it now has an extra rule, a
few more words and parses a few more sentences.


\section{Discussion}
The parser is effective though it is clearly not an industrial grade
parser.  The construction of the system involves some randomness in
synaptic connections and neural properties.  The system can be rerun
and it is highly likely that a better network can be found.  Moreover,
the existing network could be modified to improve performance.  That
is, the randomness could be eliminated.  However, at this stage,
perfect performance is not the major point of the parser. 

Instead the point is to develop neural parsing algorithms and
integrate them with other neural systems as has been done with the
CABot1 games agent.  The integrated system will then function in an
environment.  Neural learning, not used in the parser presented in
this paper, will then allow the system to learn the semantics of the
environment.  This in turn will enable the system to parse more
effectively than current symbolic parsers.

As few multi-state simulations have been done with neural systems, building
the techniques to develop these systems is a complex task.  By using
sequences, finite state automaton and push down automaton, implemented in fLIF
neurons, this system shows how these things can be implemented.  More formal
treatment of these mechanisms will be explored.

This parser has also shown some weaknesses that need to be explained.
Firstly, the system does not properly account for a verb that has two
or more slot fillers.  One would expect that the activation of a
single slot in a verb frame would only activate the associated slot
filler.  Unfortunately, when the verb ignites, all of its bound slots
also ignite along with all the slot fillers.  This means that they are
all bound together.  For instance, the semantic representation of
example 2 should have the object slot filled with pyramid and the
location slot filled with door. When all of these are co-active,
pyramid is also bound to location via the fast bind synapses.  So when
{\it Move}'s location slot alone is activated, both pyramid and door
will ignite.

\centerline {Example 2. {\it Move the pyramid to the door.}}

We hope to solve this problem using a different form of binding for the
slot fillers.  This is based on a compensatory learning mechanism and
spontaneous activation \cite {Huyck-Count}.

Secondly, the parsing takes too long from a psychological perspective.  Each
cycle in the fLIF model corresponds to roughly 10 ms.  This allows the
system to ignore refractory periods and synaptic transmission delays as
all of these things happen below the 10 ms. level.  Unfortunately, parsing
a typical sentence takes on the order of 1000 cycles, or 10 seconds of
simulated time.  

Like symbolic parsers, neural parsers can also produce semantic output
and account for human parsing failures.  One of the advantages of a
neural model of parsing is it can easily give timing data for sentence
parsing.  All of these can be compared with psycholinguistic data to
reproduce more human-like parsers.

It seems that the problem with the parser is largely around the time that
it takes to erase bindings.  The stack mechanism requires the bindings
to be erased.  Over half the time is spent on erasing.  Similarly, most of the
remaining time is spent running the test.  A better parser would avoid the
use of a stack all together.  Many modern parsers avoid the use
of stacks and merely have a set of active items that can
be used during the parse \cite{RLewis}. Implementing this kind of parser
with fLIF neurons seems viable.  In this type of system neural firing levels
within a CA would probably become more important and the system would
have to deal with multiple items being simultaneously active.

Finally learning is a key factor in neural systems.  Indeed it is one
of the main reasons or hopes why neural subsymbolic systems will surpass
symbolic systems.  Learning needs to be incorporated into the system.
Prior work shows that the fLIF neurons can be used to learn categories
\cite {Huyck-Hier,Huyck-IR}.  These techniques should be readily applied
to learning parsing preferences.  

\section{Conclusion}

This paper has shown a natural language parser implemented in fLIF
neurons.  This parser functions above the 99\% rate.  The parser takes
advantage of the intermediate concepts of CAs, sequences, and finite
state automaton.  It was shown how sets of fLIF neurons can implement
all of these.

The parser shows that a traditionally symbolic task, natural language
parsing, can be implemented in relatively biologically accurate
simulated neurons.  We hope that this system will allow us to explore
the acquisition of grammar rules, semantics and language
understanding.

{\bf Acknowledgements:} This work is supported by EPSRC grant
EP/D059720. 


\begin{thebibliography}{9}

\bibitem {Aho} A. Aho, R. Sethi and J. Ullman (1986) {\em Compilers: 
Principles, Techniques and Tools.} Reading, MA: Addison-Wesley Publishing
Co.

\bibitem {Collins} Collins, M. (1997) Three Generative, Lexicalised 
Models for Statistical Parsing.  In {\em Proceedings of the 35th 
Annual Meeting of the ACL} pp. 16-23.

\bibitem {Filmore} Filmore, C.  (1968) The Case for Case.  In {\em Universals
in Linguistic Theory} E. Back and R. Harms (Eds.) Holt, Rinheart and Winston
Inc.

\bibitem {Fodor}
   J. Fodor and Z. Pylyshyn (1988) Connectionism and Cognitive Architecture: 
   A Critical Analysis. \emph {Cognition} 28 pp. 3--71.

\bibitem{Hebb} 
  D. Hebb (1949) \emph{The Organization of Behavior}, John Wiley and Sons, 
  New York.

\bibitem {Hempel} Hempel C., Hartman, K., Wang, X., Turrigiano, G, and Nelson,
  S. (2000) Multiple Forms of Short-Term Plasticity at Excitatory Synapses
  in Rat Medial Prefrontal Cortex \emph {J. Neurophysiology}
   83 pp. ~3031--3041.

\bibitem {Henderson} J. Henderson (1994) Connectionist Syntactic Parsing 
  Using Temporal Variable Binding. \emph {Journal of Psycholinguistic 
  Research} 23:5 pp. 353--379.

\bibitem {Huyck-Tech1} C. Huyck (1999).  Modelling Cell Assemblies.  
  Middlesex University Technical Report ISSN 1462-0871 CS-99-07

\bibitem {Huyck-Plink} 
  C. Huyck. (2000) A Practical System for Human-Like Parsing,
  Proc. of the 14th European Conference on Artificial Intelligence, Berlin,
  pp. ~436--440 2000.

\bibitem{Huyck-Hier}
   C. Huyck (2007) Creating Hierarchical Categories Using Cell Assemblies.
   \emph {Connection Science} 19:1 pp. 1--24.

\bibitem{Huyck-Count}
   C. Huyck and R. Belavkin (2006) Counting with Neurons: Rule Application 
   with Nets of Fatiguing  Leaky Integrate and Fire Neurons. \emph {
   Proceedings of the Seventh International Conference on Cognitive Modelling}
   pp. 142--147.

\bibitem{Huyck-IR}
   C. Huyck and V. Orengo (2005) Information Retrieval and Categorisation 
   using a Cell Assembly Network. \emph{Neural Computing and Applications}
   14 pp. 282--289.


\bibitem{Jurafsky} 
  D. Jurafsky. (1992) An On-Line Computational Model of
  Human Sentence Interpretation: A Theory of the Representation of
  Linguistic Knowledge, PhD Thesis, University of California, Berkley
  CA.

\bibitem{Knoblauch}
  A. Knoblauch and G. Palm (2001). Pattern separation and synchronization 
  in spiking associative memories and visual areas. \emph {Neural Networks}
  14 pp. 763--780.


\bibitem {Lewis}  Lewis, Harry R. and Christos H. Papadimitriou. 1981. {\em Elements of the Theory of Computation.}  Prentice-Hall, Inc.  Englewood Cliffs, New Jersey.

\bibitem {RLewis} R. Lewis and S. Vasishth (2005)  An activation-based model
  of sentence processing as a skilled memory retrieval. \emph {Cognitive
  Science} 29 pp. 375--419.

\bibitem {Marcus} Marcus, M. 1980 {\em A Theory of Syntactic 
Recognition for Natural Language} Cambridge, MA: MIT Press.
  
\bibitem {Mikkulainen} Mikkulainen, Risto. 1993. {Subsymbolic Natural
Language Processing} Cambridge, MA: MIT Press.

\bibitem {Pinker} Pinker, S. (1994) The Language Instinct.  Penguin
Books, London. 

\bibitem{Shastri}
  L. Shastri and V. Aijanagadde (1993) From Simple Associations to Systematic 
  Reasoning: A Connectionist representation of rules, variables, 
  and dynamic bindings using temporal synchrony. \emph {Behaviour and Brain 
  Science} 16 pp. 417--494.

\bibitem {Tal} D. Tal and E. Schwartz (1997)
   Computing with the Leaky Integrate-and-Fire Neuron: Logarithmic
   Computation and Multiplication, \emph {Neural Computation}
   9:2 pp. ~305--318.

\bibitem {Wennekers} T. Wennekers, M. Garagnani, and F. Pulvermuller. (2006) 
Language models based on Hebbian cell assemblies.
\emph {Journal of Physiology-Paris} 100 pp 16--30

\end{thebibliography} 
\end{document}



