\documentclass{llncs}
\begin{document}
\title{Towards a Dynamic Syntax for Language Modelling}
\author{David Tugwell}
\institute{ITRI, University of Brighton}

\maketitle              

\begin{abstract}
This paper argues that a dynamic, ``left-to-right'' approach to
modelling syntax is best suited to the demands of the language
modelling task.  An outline of a dynamic grammar is presented, which
is based on word-by-word transitions between incomplete ``prefix''
semantic structures. It is argued that a further advantage of this
approach is that it dispenses with the need for any notion of
syntactic structure, whether based on constituents or dependencies,
and is thus preferable by the argument of Occam's razor.
\end{abstract}

\section{Background}
Probabilistic language modelling, the prediction of the next word in a
string, has obvious importance in the task of speech recognition and
other domains.  Important recent work (\cite{chelba}, \cite{wu}) has
demonstrated that exploiting the information in an incrementally
constructed syntactic structure has benefits for language modelling,
achieving decreases in perplexity and word-error rate over existing
n-gram techniques. Given the nature of language, where statistically
significant relations regularly hold between words which are more than
two or three words apart, such demonstrations of the usefulness of
syntax are long overdue. It is argued in \cite{chelba} that one reason
for this may be that standard approaches to natural language syntax,
based on a static syntactic structure, have obvious disadvantages when
applied to the task of language-modelling and that dynamic,
``left-to-right'' grammars are desirable for this task.

Given this, let us consider what properties we might desire from our
syntactic model from the perspective of language modelling.

\begin{enumerate}
\item
{\bf ``Deep'' rather than ``surface'' relations}. A little
consideration will show that the most significant relations for
prediction of words are essentially semantic, rather than the surface
syntactic ones such as subject or object. Consider the sentence: {\it
The dog seemed to be about to bark.}  The relation of surface subject
between {\it dog} and {\it seem} is of little use here, we need to
construct the deeper relation that {\it dog} is the theme of the verb
{\it bark}.  Of course, in many cases the two relations will
coincide, but a syntactic model which only constructs surface
syntactic structure will consistently miss important relations with a
consequent loss of predictive power.

\item
{\bf Incrementality}.  It is also of paramount importance that such
information can be employed as soon as possible in the left-to-right
processing of the sentence, both in order to to make a good prediction
of the next word in the string and also to prune sub-optimal paths as
early as possible.  Approaches based on syntactic constituency often
do not allow this, even in cases where it is clear that human language
users are in a position to make such early decisions.  For example, in
the sentence: {\it The dog barked and growled}, a constituency-based
syntax would typically force us to wait until the entire VP {\it barked
and growled} is constructed before we can add this to the NP {\it the
dog} and recover the relation between {\it bark} and {\it dog}.  Note
that the same problem holds for dependency-based approaches such as
\cite{hudson} and even approaches based on categorial grammar with
flexible constituents, such as \cite{steedman}. 
\end{enumerate}

Now let us turn our attention to how we might build a model of syntax
that satisfies these conditions.

\section{How to construct a dynamic model of syntax}

A model of  syntax must specifies the relation between
form and meaning, broadly speaking the relation between a string of
words ({\it w$_1$, w$_2$, w$_3$....  w$_n$}) and its possible
interpretation ({\normalsize {\bf M}$_{w_{1..n}}$}).

It has been standardly assumed since the inception of generative
grammar that this relation must be specified by introducing some
abstract level of syntactic structure or derivation.  However, it is
also possible to make use of the knowledge that not the meaning of
sentence does not arise spontaneously at the end of a sentence but is
built up on a word-by-word basis. So, given any sentence prefix {\it
w$_1$....  w$_i$}) we can use as objects of our grammar the associated
potential meanings of that prefix ({\normalsize {\bf M}$_{w_{1..}}$}),
which we will refer to as prefix meanings.

\begin{quotation}{\bf M}$_{w_0} \stackrel{w_1}{\longrightarrow}$ {\bf M}$_{w_{0,1}}
  \stackrel{w_2}{\longrightarrow}$ {\bf M}$_{w_{0..2}}$ 
  .......  {\bf M}$_{w_{0..n-1}} \stackrel{w_n}{\longrightarrow}$ {\bf M}$_{w_{0..n}}$
\end{quotation}

Assuming such an approach, the whole of the grammar is reduced to
specifying the change a word can make to the growing
semantic/conceptual interpretation of the sentence, that is the
grammar has to define all possible transitions of the form:
{\normalsize \{$w_i$, {\bf M}$_j$, {\bf M}$_k$\}}

As such transitions do not depend on previous transitions, but only
the present ``prefix meaning'', we have a simple Markov process.  Of
course, since the size of prefix meanings increases with the length of
the sentence, they do not belong to a finite set, and we do not have a
finite-state Markov process.

It should be stressed that this is a declarative grammar, not a model
of processing.  The above represents a {\it possible} derivation of
the meaning of the sentence.  At any word there may be multiple
transitions possible and it is not the job of the grammar to decide
which path or paths to pursue. The distinction is thus preserved
between a competence grammar and the use of this grammar in a
processing system.  This is point often leads to confusion since the
grammar is referring to objects (prefix meanings) that in a typical
architecture are outside the realm of grammar and have to be specified
and constructed by the processor.  By putting these objects in the
grammar, we are in effect reslicing the competence/performance cake.
It is argued that such a redistribution not only simplifies the
grammar in that it only deals with objects which are conceptually
necessary\footnote{Unlike syntactic structures, for which it is
generally admitted there is little direct evidence.}, but that it also
greatly simplifies the extra work that the processor has to do in
employing the grammar, reducing it to specifying which path or paths to take, when to backtrack and so on.

Although the relation between grammar and processor is therefore much
more transparent than in approaches based on constituent structure, it
clearly separates the two.  This contrasts the approach with models
such as ATN's and deterministic parsers such as that described in \cite{marcus},
where with hindsight the unclear relation between grammar and
parser was held to be a major drawback to their usability.

To see how such a dynamic grammar might look in practise, we must
first look at how the building blocks of the grammar, the prefix
meanings, are to be represented.

\subsection{Semantic structures}

We shall assume a psychologically-real, representationalist conception
of semantic structures, akin to that of \cite{jackendoff},
\cite{hudson} and others, and that we can represent these in complex
hierarchical networks of conceptual constituents linked by
semantic/thematic relations. To illustrate, suppose that we can
represent important elements of the meaning of the simple sentence
{\it he fed the horse today} in the following network:

\begin{center}
\setlength{\unitlength}{0.0145in}
\begin{picture}(190,150)(395,660)
\thinlines
\put(450,787){\vector(-1,0){38}}
\put(450,767){\oval(40,40)[tr]}
\put(470,767){\line(0,-1){27}}
\put(402,727){\line(-1,0){36}}
\put(367,707){\oval(40,40)[tl]}
\put(347,707){\vector(0,-1){17}}
\put(558,727){\line(1,0){30}}
\put(588,707){\oval(40,40)[tr]}
\put(608,707){\vector(0,-1){16}}
\put(320,675){\fbox{({\bf 3}) {\sc anim}, def, sg, {\bf horse}}}
\put(352,785){\fbox{({\bf 2}) {\sc male}, sg}}
\put(402,730){\fbox{({\bf 1}) proposition, {\sc action}, past, {\bf feed}}}
\put(560,675){\fbox{({\bf 4}) {\sc time}, sg, {\bf today}}}
\put(422,790){agent}
\put(362,717){patient}
\put(565,717){mod}
\end{picture}
\end{center}


We are using here a relatively ``flat'' representation of the semantic
network, which allows us to focus on individual elements: events,
entities, states, propositions and so forth.  This will be important
when we consider how syntactic rules, specifying transitions between
such structures, are to be formulated.



\subsection{How to specify transition rules}

The first problem facing us in formulating transition rules is that
prefix meanings are (potentially vast) hierarchical structures.
Clearly we need some way to pick out from such structures a small
subset of salient information.  To this end, we assume that the
semantic constituents, in addition to being related by thematic
relations with other constituents, are at the same time subject to a
salience ordering, that is an ordering of constituents on what we will
term an {\it active stack}, which is employed in the following
way:\footnote{This has an obvious correlation with the parse stack of
familiar left-to-right parsing algorithms.  As discussed above, in the
present approach prefix meanings are objects of the grammar and not
relegated entirely to the processor.}
\begin{itemize}
\item 
Incomplete constituents are placed on the active stack.
\item 
Newly-completed constituents may be removed from this stack.
\item
The topmost constituent on the stack is termed the {\it active constituent}.
\end{itemize}

Syntactic transition rules will then add new structure ($\approx$ the
semantic content of the present word), conditional on the present
active constituent and the syntactic category of the word.  To
illustrate this, let us consider the word-by-word
derivation of our earlier example: {\it he fed
the horse today}.

\vspace{10pt}
\hspace{0.8in}\underline{{\bf Active stack}}\hspace{1.4in}\underline{{\bf Inactive constituents}}
 
\vspace{10pt}
\hspace{-2pt}{\normalsize {\bf M}$_{w_0}$}: \hspace{10pt}[1, proposition]

\vspace{5pt}
\hspace{-15pt}{\bf he}

\vspace{5pt}
\hspace{-2pt}{\normalsize {\bf M}$_{w_{0,1}}$}: \hspace{0.04in}\parbox{3.2in}{[1, proposition, [+2]]}   [2, {\sc male}, sg]

\vspace{5pt}
\hspace{-15pt}{\bf fed}

\vspace{5pt}
\hspace{-2pt}{\normalsize {\bf M}$_{w_{0..2}}$}: \parbox{3.2in}{[1, prop, {\bf feed}, past, agent:2, patient: , [+{\underline 2}]] }  \hspace{0in}[2, {\sc male}, sg]

\vspace{5pt}
\hspace{-15pt}{\bf the}

\vspace{5pt}
\hspace{-2pt}{\normalsize {\bf M}$_{w_{0..3}}$}: \parbox{3.2in}{[3, def]

[1, prop, {\bf feed}, past, agent:2, patient:3, [+\underline{2}]]}  \hspace{0in}[2, {\sc male}, sg]

\vspace{5pt}
\hspace{-15pt}{\bf horse}

\vspace{5pt}
\hspace{-2pt}{\normalsize {\bf M}$_{w_{0..4}}$}: \parbox{3.2in}{[1, prop, {\bf feed}, past, agent:2, patient:3, [+{\underline 2}]]}  \hspace{0in}\parbox{3in}{[3, def, sg, {\bf horse}] 

[2, {\sc male}, sg]}

\vspace{5pt}
\hspace{-15pt}{\bf today}

\vspace{5pt}
\hspace{-2pt}{\normalsize {\bf M}$_{w_{0..5}}$}: \parbox{3.2in}{[1, prop, {\bf feed}, past, agent:2, patient:3,  mod:4, [+{\underline 2}]]}
\hspace{0in}\parbox{3in}{ 
[4, {\sc time}, {\bf today}]

[3, def, sg, {\bf horse}] 

[2, {\sc male}, sg]}

It will be seen that the first transition (for {\it he}) adds a
constituent which cannot yet be related semantically to the active
constituent (the empty proposition).  Until such time as it can be
interpreted (in this case at the next word) the constituent address is
placed on the {\it store} of the proposition and marked with the {\it
syntactic relation} of subject (``+'').  The store will be used in
such a way for all temporarily uninterpretable items, not only
subjects, but also topics and {\it wh}-constituents.  

The actual transitions in the derivation may be seen to be instances
of particular transition rules, which are outlined in the following
table.  Here the top of the active stack is shown before and after the
transition: {\bf X} stands for the information in the old active
constituent and {\bf N} for the new information supplied by the
lexical entry for the current word.

\begin{center}
\begin{tabular}{|l|c|c|c|c|} \hline
rule & applies at & lexical entry  & top of stack (S$_n$) & top of stack (S$_{n+1}$) \\
\hline \hline
{\bf add-subject}  & {\it he}
 & \{nominative\}  &    & (N) \\  
  &   & & (X, prop)   & (X, prop, [+N]\\ \hline
{\bf finite-verb}   & {\it fed}  & \{verb, fin\}
 &  (X, prop, [+$\alpha$]) &  (X  $\cup$ N, prop, arg1: $\alpha$) \\ \hline  
{\bf add-arg}  & {\it the} & \{det\} &   &  (N) \\ 
  &  &  &(X, arg: )  &  (X, arg:N) \\  \hline 
{\bf add-head }  & {\it horse} & \{ noun\}
 & (X)  &  (X $\cup$ N)  \\ \hline
{\bf modify}  & {\it today} 
 &  \{adv\} &  & (N) \\ 
 & &  & (X) &   (X, mod:N) \\ \hline
\end{tabular}
\end{center}

A manageably small number of such transition rules may be produced to
cover a significantly large range of English constructions, including
{\it wh}-movement, coordination, raising and others.

\subsection{Does dynamic syntax fit the data?}

Another constraint on how useful a grammar is, and how interesting
from a theoretical point of view, is how faithfully it models the
data, here the relationship between strings of words and possible
meanings.  It has been extensively argued\footnote that the dynamic
approach offers clear advantages in a number of syntactic phenomena,
such as problems of non-constituent coordination, binding, scrambling
and many others.{See, for example, in \cite{hausser}, \cite{kempson},
\cite{milward}, \cite{philips} and \cite{tugwell}} From consideration
of this range of constructions, it will be seen that the key advantage
of the dynamic approach is that it avoids unnecessary problems
introduced by the supposition that there is some level of
representation (syntactic structure) relating the levels of form and
meaning and therefore containing elements of both. The dynamic
approach introduces no such level.\footnote{A thought-provoking modern
take on Occam's razor is given as: ``Whatever happens, try all
possible ways of explaining it in terms of things we already know
about, before introducing aliens or dark matter.''  Mike Holderness,
New Scientist 3rd June, 2000}



\section{Constructing a probabilistic language model} 

If we have a dynamic grammar of the type described with a reasonable
coverage of grammatical constructions, how can we extend this into a
language model?

The syntactic rules and the lexicon will provide us with possible
transitions \{$w_i,S_j,S_k$\}, but we need to estimate the probability
of such transitions occurring P($S_k|w_i,S_j$). The basic factors to be used in
such calculations will be collocations between the head of a constituent and the head of its arguments or modifiers.  So in the example {\it the stray dog was barking loudly}, we will need estimates for the collocations: {\it bark'(theme=dog')}, {\it bark'(manner=loudly')} and {\it dog'(quality=stray')}.

If we factor in estimates of the probability of such relations we are
then in the position to make predictions of the next word.  Luckily,
such counts can be obtained from large corpora to a usable degree of
accuracy with simple regular expression techniques.  To counter
problems of data sparseness there will be a need for smoothing,
possibly using similarity metrics.  

The final requirement for a processor is a suitable control structure,
determining which potential paths of the derivation to pursue and
which to reject.  The processor in \cite{chelba} employs the
beam search algorithm, where a number of paths are pursued in parallel
subject to them satisfying some threshold criteria.


\section{Conclusion}

This paper has outlined the architecture of a dynamic model of
syntax. Although very much in their infancy, such models offer the
enticing prospect of a useful approach being used both for the
practical task of language modelling for speech recognition, as well
as for addressing some outstanding problems in theoretical
linguistics.

%
% ---- Bibliography ----
%
\begin{thebibliography}{}

\bibitem[1]{chelba}
Chelba, Ciprian \& Frederick Jelinek: 
Exploiting syntactic structure for language modelling. 
COLING-ACL (1998) vol I 225--231

\bibitem[2]{wu}
Wu, Jun \& Sanjeev Khudanpur:
Combining nonlocal, syntactic and n-gram dependencies in language modelling. 
Proceedings of Eurospeech'99 vol 5 (1999) 2179--2182.

\bibitem[3]{hudson}
Hudson, Richard:
{\it English word grammar}.  
Oxford: Blackwell (1990)

\bibitem[4]{steedman}
Steedman, Mark:
{\it The syntactic process}.  
MIT Press/Bradford Books (2000)
 
\bibitem[5]{marcus}
Marcus, Mitchell P.:
{\it A theory of syntactic recognition for natural language}. 
MIT Press (1980)

\bibitem[6]{jackendoff}
Jackendoff, Ray:
{\it Semantic structures}.  
MIT Press (1990)

\bibitem[7]{hausser}
Hausser, Roland:
{\it Foundations of computational linguistics}. 
Berlin: Springer (1999)

\bibitem[8]{kempson}
Kempson, Ruth, Wilfried Meyer-Viol \& Dov Gabbay:
{\it Dynamic Syntax: The Flow of Language Understanding}. 
Oxford: Blackwell (to appear)

\bibitem[9]{milward}
Milward, David:
Dynamic Dependency Grammar. 
Linguistics and Philosophy {\bf 17} (1995) 561--615

\bibitem[10]{philips}
Philips, Colin:
Order and Structure. 
PhD thesis, MIT (1996)

\bibitem[11]{tugwell}
Tugwell, David:
Dynamic Syntax. 
PhD thesis, University of Edinburgh  (1999)

\end{thebibliography}

\end{document}
