\documentclass[11pt,nofrench]{thloria}
%\documentclass{foils}

%\usepackage{koweydoc}
\usepackage{url}
\usepackage{graphicx}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{color}

\usepackage[latin1]{inputenc}
%\usepackage{koweyslide}
\newcommand{\jargon}{\textbf}
\newcommand{\tuple}[1]{\langle #1 \rangle}
\newcommand{\set}[1]{\{#1\}}
\newcommand{\semexpr}{\texttt}
\newcommand{\semexprset}[1]{\semexpr{\set{#1}}}
\newcommand{\natlang}{\textit}
\newcommand{\tautree}[1] {$\tau_{#1}$}
\newcommand{\koweytree}{\texttt}
\newcommand{\FIXME}[1]{\textbf{\textit{(FIXME:#1)}}}
\newcommand{\CallFunction}[2]{\textproc{#1}({#2})}
\newcommand{\PolAutomaton}{\tuple{States,InitialState,FinalStates,Transitions}}
\setcounter{secnumdepth}{3}

% we use a more standard notation for comments
\renewcommand\algorithmiccomment[1]{\hfill\(\#\) #1}%

\begin{document}
\ThesisTitle{Optimising a Surface Realiser}
\ThesisAuthor{Eric Kow}
\ThesisNancyI
\ThesisDate{22 juin 2004}

\def\blanc{\hspace*{1cm}}
\NewJuryCategory{Encadrants}{\it Encadrante:}
                            {\it Encadrants:}

\Encadrants  = {C. Gardent}
\Rapporteurs  = {N. Carbonell\\
                 D. Méry\\
                 D. Galmiche\\
                 J.Y. Marion\\
                 J. Souquières}
%
\MakeThesisTitlePage

\tableofcontents

\begin{ThesisAcknowledgments}
I have had an immense amount of help on this DEA.
\\

\noindent
For starters, my supervisor Claire Gardent has gone out of her way
for this little first step of a thesis.  Working with Claire has been a
fun and instructive experience, as she has this uncanny ability to
always ask the right questions.  This results in an endless supply of
good ideas that are invariably of the simple and practical variety.  
\\

\noindent
Carlos Areces has also contributed his fair share of elegant ideas.  I
would like to thank him as well for help with Haskell, the surface
realiser GenI, and a million essential concepts. Carlos speaks with such
pedagogical clarity that it almost seems like a bad habit; I wonder if
he would even be capable of explaining anything poorly if he wanted to.
\\

\noindent
Many many thanks to Patrick Blackburn and Hélène Manuelian and 
especially Claire and Carlos for reading the many awkward drafts of 
this thesis and red-penning its way into passability.  I hope to 
someday master the basic respect and consideration they have for
their reader.
\\

\noindent
The good strangers who frequent the channel \#haskell on
irc.freenode.net deserve at least a grateful nod for their kindness to
newbies.  
\\

\noindent
Finally, the following people have helped in a more lateral fashion:
Hélène with her fine Franglais-French translation of my DEA letter of
motivation; office mates Yannick and Joseph for puttting up with much
whining, and the occasional, inexpliquable ``moo!''.  Thank-you all for
your friendship.  And now I restrain myself from tearful speeches of
friends and family, and hope to do these people justice at a later time.
\end{ThesisAcknowledgments}

\mainmatter

% -------------------------------------------------------------------------
\chapter{Introduction}
% -------------------------------------------------------------------------

The surface realisation task consists in using a grammar to produce the
sentence(s) associated by this grammar with some input meaning
representation.  The meaning representation is written using some
logical language. For example, a surface realiser might receive an
\jargon{input semantics} of \semexprset{loves(l,john,mary)}, for which
it outputs the \jargon{surface realisation} \natlang{John loves Mary}.  

Surface realisation, also referred to as \jargon{tactical generation},
is similar to the better known task of natural language parsing.  When
doing generation, we construct syntactic trees which are associated with
the input semantics by the language's grammar, and trivially read the
tree leaves to reconstruct the output string. Polynomial-time algorithms
for parsing have long been developed, so it would be tempting to assert
that generation is parsing in reverse and simply reuse these algorithms.
But \cite{koller02gen} demonstrates that the Hamiltonian Path problem
can be reduced to a surface realisation task and so the problem is
NP-complete.  The intuitions for this can be found in \cite{kay96chart}.
Both parsing and generation have the potential to be computationally
expensive because natural language has a great deal of lexical
ambiguity; however, parsers have the luxury of string positions.  Using
string positions, one can pack an arbitrary number of alternative
structures into a small and fixed number of edges, so that parsing can
be done in cubic time no matter what the ambiguity. The
situation for surface realisers is more delicate because the input
semantics have no natural order, and so there are as many potential
edges as there are subsets of literals. This number is exponential with
respect to input length, and as a result, we are forced to deal with the
full effect of lexical ambiguity.

This thesis explores the problem of optimisation for a TAG-based surface
realiser.  We begin in this chapter with the essentials of surface
realisation and continue in section \ref{sec:geni} with a description of
the realiser developed within the INRIA ARC GenI by Carlos Areces and
used here as an implementation platform \cite{areces03geni}.  In chapter
\ref{chp:optimisations}, we propose a set of optimisations, implement
them into the GenI realiser, and discuss their effectiveness.  We
conclude in chapter \ref{chp:conclusion} with proposals for further
optimisation and pointers for further research.

\section{Background}
\label{sec:background}

Building a surface realiser requires three ingredients: a semantic
representation, a formal grammar for natural language syntax augmented
with a semantic dimension, and an algorithm for building syntactic
structures. The GenI generator uses respectively a flat semantics, the
Tree Adjoining Grammar (TAG) formalism, and a bottom-up/head-driven
algorithm.

\subsection{Flat semantics}
\label{sec:flat_semantics}

The semantics of a natural language expression can be approximated by a
logical form.  In this thesis, we write the semantics as a conjunction
of \jargon{literals}, where each literal is a predicate with some
arguments.  The arguments may not themselves be literals, so there is no
recursion, and we call this a \jargon{flat semantic representation}
\cite{copestake95mrs}. For example, to represent the meaning of the
sentence \natlang{John loves Mary intensely} we could write
\semexprset{loves(l, j, m), intense(l), name(j, john), name(m, mary)},
meaning that there is an act of loving \semexpr{l} between the
individuals named \natlang{John} and \semexpr{Mary} and that this act is
intense.  For a more detailed introduction to flat semantics, we refer
the reader to \cite{copestake95mrs}.

The various approaches to surface realisation work by successively
combining expressions which verbalise different parts of the input
semantics.  This aspect is particularly well served by a flat
representation.  In particular, note that in order to compare recursive
semantic representations, something like higher order unification is
required, whereas by using a flat semantics, this comparison can be
carried out using set intersection. Similarly, we can combine two
semantic expressions by taking their union.

\subsection{Tree-Adjoining Grammar}
\label{sec:tag}

Tree-Adjoining Grammar (TAG) is a formalism that generates the ``mildly
context-sensitive'' class of languages.  As defined in
\cite{joshi97tag}, a tree-adjoining grammar consists of a quintuple
$\tuple{\Sigma,NT,I,A,S}$ where 

\begin{enumerate}
\item $\Sigma$ is a finite set of terminal symbols.
\item $NT$ is a finite set of non-terminal symbols: $\Sigma \cap NT =
\emptyset$.
\item $S$ is a distinguished non-terminal symbol: $S \in NT$ 
\item $I$ is a finite set of finite trees, called \jargon{initial
trees} where
\begin{itemize}
\item interior nodes are labeled by non-terminal symbols;
\item frontier nodes are labeled by terminals or non-terminals;
      non-terminal symbols on the frontier are called 
      \jargon{substitution sites} and are marked for substitution,
      by convention, annotated with a down arrow ($\downarrow$);
\end{itemize}
\item $A$ is a finite set of finite trees, called \jargon{auxiliary
trees} where
\begin{itemize}
\item interior nodes are labeled by non-terminal symbols;
\item frontier nodes are labeled by terminal or non-terminal symbols;
      non-terminal symbols on the frontier are marked for substitution 
      except for one node, called the \jargon{foot node}, by convention,
      annotated with an asterisk (*); the label of the foot node must
      be identical to the label of the root node.
\end{itemize}
\end{enumerate}

The trees in $I \cup A$ are called \jargon{elementary trees} and 
describe the syntactic structure of the basic components of
a language, namely words or collocations.  These trees can be
composed pairwise to build more complex structures, called
\jargon{derived trees}, through the operations of substitution and 
adjunction.  
 
The \jargon{substitution} operation (figure \ref{fig:substitution})
replaces one substitution site of one tree by the tree to be
substituted.  The tree to be substituted must be derived from an initial
tree. When a tree does not have substitution sites, we say that it is
\jargon{closed}.

\begin{figure}
\begin{center}
\includegraphics[scale=0.65]{images/substitution.pdf}
\caption{Substitution}
\label{fig:substitution}
\end{center}
\end{figure}

The \jargon{adjunction} operation can be understood as splicing
an auxiliary tree into another tree (which can be of any type, initial,
auxiliary or derived.)  Let $\alpha$ be a tree containing a
non-substitution node labeled by $X$, and $\beta$ be an auxiliary tree
whose root node is also labeled by $X$.  Adjoining $\beta$ into $\alpha$
is built by (1) excising the sub-tree of $\alpha$ dominated by $n$ (call
it $t$) (2) replacing the foot node of $\beta$ with $t$ to produce an
intermediary structure $\beta'$ and (3) replacing the excised tree in
$\alpha$ with the augmented auxiliary tree $\beta'$.  Nodes on which
adjunction may be performed are called \jargon{adjunction sites}.

\begin{figure}
\begin{center}
\includegraphics[scale=0.65]{images/adjunction.pdf}
\caption{Adjunction}
\label{fig:adjunction}
\end{center}
\end{figure}

\subsubsection{TAG with flat semantics}
\label{sec:tag_semantics}

We augment the TAG formalism by associating each tree in the grammar
with a semantics using the flat representation.  Whenever two trees are
combined (via substitution or adjunction), the semantics of the resulting
tree is calculated by taking the set union of the source tree semantics.
In figure \ref{fig:semantics}, we show the result of the substitution
and adjunction from figures \ref{fig:substitution} and
\ref{fig:adjunction} once semantics is taken into account.

\begin{figure}
\begin{center}
\includegraphics[scale=0.65]{images/semantics.pdf}
\caption{TAG with flat semantics}
\label{fig:semantics}
\end{center}
\end{figure}

Note that it is not realistically feasible to implement the
syntax-semantics interface without introducing a notion of variable
unification.  Without such a mechanism, we would have to create a
separate entry for every possible combination of tree semantic indices,
one for \semexpr{smells(s,j)}, for \semexpr{smells(s,k)}, for
\semexpr{smells(s,l)} and so forth.  Realistic grammars have tree
semantic literals where the arguments are not necessarily constants,
but variables, which simultaneously occur in the nodes of the tree.
Before they are used for generation, trees have to be
\jargon{instantiated}, meaning that unification must be
performed between these variables and the arguments contained in the
input semantics representation. Variable unification on node variables
also occurs during the substitution and adjunction operations, which
prevents incorrect realisations like \natlang{John hates Mary} when the
intended output was \natlang{Mary hates John}.  

Consider a grammar which has a tree \natlang{smells} with the semantics
\semexpr{smells(V,X)} (we indicate variables with capital letters).
Given the input semantics \semexprset{smells(s,j), name(j,john),
funny(s)}, we must first instantiate \natlang{smells} by unifying
\semexpr{V} with \semexpr{s} and \semexpr{X} with \semexpr{j}.  If the
generator were to use a different input semantics, like
\semexprset{smells(s,m), name(m,mary), nice(s)}, then \natlang{smells}
would be instantiated differently.

\subsection{Generation algorithms}
\label{sec:generation_algorithms}

We can see generation as the process of constructing a syntactic tree
\cite{shieber90shd}.  There are two basic approaches to this process,
building the tree from the top-down, or from the bottom-up.  There is
also a hybrid head-driven approach which combines the two basic
strategies.  

These approaches were originally developed in the framework of context
free grammars with recursive semantics.  For consistency with this
thesis, we will maintain a TAG perspective: context free rules are
viewed as shallow TAG trees, and non-terminal child nodes are
substitution sites.  The approaches also assume a recursive semantics,
but rather than risking errors by converting them to a flat
semantics, we will momentarily adopt a recursive semantics.  The
relationship between syntax and semantics is somewhat different here.
Instead of using the union operation to combine tree semantics, we allow
the use of complex variables and let unification do the work.  Grammars
in this section are presented as Prolog DCGs with the lexicon omitted.

\subsubsection{Top-down generation}
\label{sec:td_generation}

The top-down approach consists in working from the root to the leaves.
We select any tree from the grammar with root category \koweytree{s}
(for sentences) and perform unification between its and the input
semantics.  Then we loop around; if the tree has any substitution sites,
we select a tree with the same root as the site, perform substitution
(and unification).  Hopefully doing this closes off all the substitution
sites, but it may very well not, and worse, it may introduce its own
share of sites.  The loop continues until the tree is closed.

\paragraph{Non-termination} This approach can fail to terminate if it is
applied on the wrong grammar, namely, a left-recursive one.  For
instance, the following grammar should be able to produce \natlang{John
smells funny} as a realisation for the input semantics
\semexpr{funny(smell(john))}.  \footnote{In this grammar, categories
encode both syntactic and semantic information.  Specifically, a term of
the form \texttt{Synt(Sem)} denotes a category with syntactic category 
\texttt{Synt} and semantic information \texttt{Sem}.  Shared variables
are used to adequately bind semantic arguments.}

\begin{verbatim} 
s(S)                 --> np(NP), vp(NP,S).     % t1
vp(NP,S)             --> vp(NP,VP), adv(VP,S). % t2
vp(NP,S)             --> v(NP,S).              % t3
v(NP,smell(NP))      --> smells.               % t4 
adv(VP,funny(VP))    --> funny.                % t5
adv(VP,nice(VP))     --> nice.                 % t6
np(john)             --> john.                 % t7
\end{verbatim}

But top-down generation on this grammar might not terminate:

\begin{enumerate}
\item We begin with t1.  Ignoring semantic information, execution of t1
      yields a tree \koweytree{s(np$\downarrow$, vp$\downarrow$)} where,
      as noted above, the rule is represented by a local tree and the
      non-terminals by substitution sites labeled with the rule's
      right hand side syntactic categories.
\item We substitute t7 to produce \koweytree{s(np(john), vp$\downarrow$)}
\item The derived tree still has a substitution site to fill, this
      being \koweytree{vp$\downarrow$}, so we process t2.  
\item t2 introduces its own share of substitution sites.  If we attempt
      to fill the first one (\koweytree{vp$\downarrow$}) by substituting t2
      into it, this brings us back to the same problem and traps us
      in an infinite loop.
\end{enumerate}

\subsubsection{Bottom-up generation}
\label{sec:bu_generation}
\label{sec:intersective_modifiers}

Bottom-up generation builds trees from the lexical items to the root.
First, the \jargon{lexical selection step} selects from the grammar
the trees whose semantics subsumes part of the input semantics, and 
places them in a pool. Then the generator loops: it arbitrarily selects
a pair of trees from the pool and attempts substitution between the two
trees.  If the resulting derived tree is closed and if its semantics
matches the input semantics, then it is added to the output.  Otherwise,
it is put into the pool for future consideration. The loop continues in
this fashion until there are no new pairs to select.

Given the grammar from the previous section (\ref{sec:td_generation}),
a bottom-up generator would find the surface realisation \natlang{John
smells funny} from the input semantics \semexpr{funny(smell(john))}
as follows:

\begin{enumerate}
\item Every tree in the grammar except t5 is selected, resulting in
      a pool that consists of t1 \koweytree{s(np$\downarrow$,
      vp$\downarrow$)}, t2 \koweytree{vp(vp$\downarrow$, adv$\downarrow$)},
      t3 \koweytree{vp(v$\downarrow$)}, 
      t4 \koweytree{v(smells)}, 
      t5 \koweytree{adv(funny)} and t7 \koweytree{np(john)}. 
\item t4 is substituted into t3 and the resulting
      \koweytree{vp(v(smells))} is added to the pool.
\item This is substituted into t2, and the resulting
      \koweytree{vp(vp(v(smells)), adv$\downarrow$)} is added to the
      pool.
\item t5 is then substituted into this, and the resulting
      \koweytree{vp(vp(v(smells)), adv(funny))} is added to the pool.  
\item This is substituted into t1 to produce
      \koweytree{s(np$\downarrow$, vp(vp(v(smells)), adv(funny)))}
\item t7 is substituted into this and the resulting
      \koweytree{s(np(John), vp(vp(v(smells)), adv(funny)))}
      is added to the output. 
\item This tree is syntactically complete and matches the input
      semantics. If we read the leaves of this tree, we extract the
      output sentence \natlang{John smells funny} 
\end{enumerate}

\paragraph{Termination and non-determinism}

A useful constraint for bottom-up algorithms is to only allow trees to
be combined if they do not have any lexically selected trees in common.
This prevents infinitely long strings like \natlang{smells funny funny
funny...} from being generated.  

Once this filter is in place, bottom-up algorithms are guaranteed to
terminate, because the lexical selection step gives them a finite number
of trees to start with.  We can think of the algorithm loop as always
consuming a lexically selected tree until it eventually runs out and
has to stop.

This guarantee of termination comes at the price of highly
non-deterministic behaviour.  The generation loop selects at every
iteration, a pairs of trees to be combined.  If these choices do not
lead to a result, then the generator must make a new set of selections,
either by backtracking, or by having simultaneously considering the
different choices that it can make.

\paragraph{Semantic monotonicity}

One potential disadvantage of this approach is that it requires grammars
to be semantically monotonic.  A \jargon{semantically monotonic} grammar
only has rules in which the semantics of the daughter nodes is contained
in the semantics of the mother node.  For example, any grammar which
includes the following fragment is not semantically monotonic:

\begin{verbatim}
vp(X,Y,callup(X,Y)) --> v(X,Y,callup(X,Y)), np(Y), pp(up). 
v(X,Y,callup(X,Y))  --> call.
pp(up)              --> up.
\end{verbatim}

The intention behind these rules is to generate sentences like
\natlang{John calls Mary up} from the input semantics
\semexpr{callup(john,mary)}.  A top-down generator would simply
instantiate the rule, ignoring the semantics for \natlang{up}.  But a
bottom-up generator could never use this rule, because \verb$up$ is not
in the input semantics, so that there is no reason to select the 
\verb$pp(up)$ rule.

\paragraph{Intersective modifiers} 

Bottom-up generators are also affected with the non-determinism
triggered by \jargon{intersective modifiers}.  Consider the semantics
\semexpr{dirty(smelly(unpleasant(man(x))))}, whose predicates all modify
the individual \semexpr{x}.  This should be realised with the following
grammar as the fragment \natlang{dirty smelly unpleasant man}.  

\begin{verbatim}
n(N,dirty(N))       --> dirty, n(N). 
n(N,smelly(N))      --> smelly, n(N). 
n(N,unpleasant(N))  --> unpleasant, n(N). 
n(man)              --> man.
\end{verbatim}

To get the desired result, however, the generator will try out each and
every one of the following combinations:

\begin{quotation}
 \noindent
 \natlang{dirty smelly unpleasant man},\\
 \natlang{dirty smelly man}, 
 \natlang{dirty unpleasant man}, 
 \natlang{smelly unpleasant man}, \\
 \natlang{dirty man}, 
 \natlang{smelly man},
 \natlang{unpleasant man}, \\
 \natlang{man}
\end{quotation}

That is, it creates $n!$ possible sequences (where $n$ is the number of
modifiers) just to find a single correct answer.  We could even be
generous and impose a sort of word order constraint, so that
\natlang{smelly dirty man} would not be allowed, whereas \natlang{dirty
smelly man} would.  In this case, the number of possible substrings
drops to $2^n$.

\subsubsection{Head-driven generation}

Head-driven generators are based on the observation that every syntactic
tree necessarily has a \jargon{semantic head}, the lowest possible node 
whose semantics is that of the tree.  If we revisit the example in
section \ref{sec:td_generation} (repeated below), we can identify the
verb \natlang{smells} as the semantic head for the verb phrase
\natlang{smells funny} and consequently for the sentence \natlang{John
smells funny}.  The semantic head can be used to guide the generation
process.  In \cite{shieber90shd}, the grammar is preprocessed so that
trees are divided among \jargon{chain rules} whose semantic head is a
child node, and \jargon{non-chain rules} whose semantic head is its root
node. In the example, only t1, t2 and t3 are chain rules.  

\begin{verbatim} 
s(S)                 --> np(NP), vp(NP,S).     % t1
vp(NP,S)             --> vp(NP,VP), adv(VP,S). % t2
vp(NP,S)             --> v(NP,S).              % t3
v(NP,smell(NP))      --> smells.               % t4 
adv(VP,funny(VP))    --> funny.                % t5
adv(VP,nice(VP))     --> nice.                 % t6
np(john)             --> john.                 % t7
\end{verbatim}
% Note: we include t3 and t4 because we need to show how the bu
% part of the head-driven generator works when it encounters a
% chain rule in the middle... or something like that.

The generator works with what is called a \jargon{target node}.  The
first target node has category \koweytree{s} (for sentence) and the
semantics equal to the input semantics. The basic approach is to use
top-down processing of the non-chain rules to identify the semantic head
of the target and use bottom-up processing of the chain rules to connect
the two nodes. Any new substitution sites encountered along the way are
recursively processed as targets.  We can think of the generator as
cycling between three behaviours: leaping (top-down), connecting
(bottom-up) and recursion (top-down).  When tracing the algorithm, it is
useful to imagine a stack of target nodes.  The algorithm does not
actually use such a stack because it is implicit in the recursive
behaviour.

Given the example grammar above and the input semantics
\semexpr{funny(smell(john))}:

\begin{enumerate}
\item We push the desired result \semexpr{s(funny(smell(john)))} on
      the stack.
\item (td) We leap down to t5 \koweytree{adv(funny)} because its
      semantics unifies with \semexpr{funny(smell(john))}. There are no
      child nodes, so we try to connect upwards. 
\item (bu) t5 can serve as the semantic head of chain-rule t2,
      so we perform substitution to produce
      \koweytree{vp(vp$\downarrow$, adv(funny))}.
      We push the child node \semexpr{vp(NP,smell(john))} on the stack.
\begin{enumerate}
\item[a] (td) We leap down to t4 \koweytree{v(smells)} because its
         semantics unifies with \semexpr{smell(john)}.  There are no
         child nodes, so we try to connect upwards.
\item[b] (bu) t4 can serve as the semantic head of chain-rule t3,
         so we perform substitution to produce 
         \koweytree{vp(v(smells))}.  There are no child nodes to fill,
         so we try to connect upwards.
\item[c] (bu) The root node of the above tree unifies with the target
         \semexpr{vp(NP,smell(john))}, so we perform substitution 
         to produce \koweytree{vp(vp(v(smells)), adv(funny))}, and 
         bottom-up processing is complete.  We pop the stack and try to
         connect upwards to the new target.
\end{enumerate}
\item (bu) \koweytree{vp(vp(v(smells)), adv(funny))} can serve as the
      semantic head of chain-rule t1, so we perform substitution to
      produce \koweytree{s(np$\downarrow$, vp(vp(v(smells)),
      adv(funny)))}. We push the child node \semexpr{np(john)} on the
      stack.
\begin{enumerate}
\item[a] (td) we leap down to t7 because its semantics unifies
         with \semexpr{john}.  There are no child nodes, so we now try
         to connect upwards.
\item[b] (bu) The t7 root unifies with the target, so we perform
         substitution to produce \koweytree{s(np(John),
         vp(vp(v(smells)), adv(funny)))}.  We pop the stack and try to
         connect upwards.
\end{enumerate}
\item (bu) The t1 root unifies with the target, so bottom-up processing
      is complete. The stack is empty and we have a semantically
      complete result, from which we extract the sentence \natlang{John
      smells funny}.
\end{enumerate}

The head-driven approach combines the most attractive properties of
bottom-up and top-down processing, namely termination and efficiency.
Like bottom-up algorithms, the head driven algorithms lexically select
and then consume a finite set of trees on the basis of their semantics.
The main difference is that the lexical selection (leaping) is
interspersed with the generation loop as opposed to being set in the
very beginning, but the essential property of using the semantic
information is retained.  The efficiency of these approaches comes from
the top-down ability to guide the selection items by syntactic criteria.
This is most evident with intersective modifiers; given the semantics
\semexpr{dirty(smelly(unpleasant(man(x))))} and the grammar fragment in
section \ref{sec:intersective_modifiers}, the head-driven algorithm
would zip down the rules, \natlang{dirty}, \natlang{smelly},
\natlang{unpleasant} in a similar fashion to a top-down algorithm,
except that this zipping would consist of trivial leaping and connecting
steps.

\section{The GenI surface realiser}
\label{sec:geni}

Within the INRIA ARC GenI, Carlos Areces developed a TAG-based surface
realiser in Haskell. This is simultaneously a bottom-up and head-driven
generator, bottom-up in its basic tree-building strategy and head-driven
by virtue of TAG and the use of entire trees as basic linguistic units.  

The TAG formalism enjoys what \cite{gardent01gen} call an ``extended
domain of locality'' in that elementary trees can be of arbitrary depth.
This makes the requirement of semantic monotonicity much more palatable.
In the case of \natlang{John calls Mary up}, the word \natlang{up} would
simply be incorporated into an elementary tree
\koweytree{s(np$\downarrow$, v(calls), np$\downarrow$, pp(up))}.
Furthermore the trees with their extra depth and complexity contain
syntactic information that would normally be built in the top-down phase
of head-driven generation.  Using TAG thus allows us to imbue a
bottom-up generator with head-driven characteristics.

The GenI generator also includes a number of optimisations, including
chart generation, ordered substitution and delayed adjunction, which we
now discuss.

\subsection{Chart generation}
\label{sec:chart}

Some algorithms for natural language parsing use a tabulation method to
improve efficiency.  These \jargon{chart algorithms} can also be
adapted or generalised to do generation \cite{shieber88uap,kay96chart}.
We examine chart methods from the perspective of our thesis, namely,
with bottom-up processing and with trees as basic linguistic units.

\subsubsection{Basic architecture}

The essence of bottom-up processing is a loop that compares two trees
and when possible, combines them to make a new tree, until it runs out
of trees to compare.  Chart algorithms will modify this process by 
avoiding recomputation of redundant intermediate structures.

We introduce two data structures called an \jargon{agenda} and a
\jargon{chart}.  The agenda is a form of to-do list and it contains the
trees that need to be processed. The chart contains the trees that have
already been processed.  In the beginning of the processing, the agenda
is initialised with those trees whose semantics subsumes the input
semantics.  During the course of the processing, an item is removed from
the agenda, placed on the chart and combined with items from the chart.
Any tree that results from the combination is placed on the agenda,
unless it is syntactically complete (closed) and its semantics
exactly matches the input semantics, in which case it is added to the
results.  We loop in this fashion until the agenda is completely empty,
which means that all comparisons have been made.

\subsubsection{An example}
\label{sec:chart_example}

\begin{figure}
\begin{center}
\begin{tabular}{|ll|ll|} 
\hline
initial trees & & 
auxiliary trees & \\ 
\hline
\koweytree{np(John)}    & \semexprset{name(X,john)}
& \koweytree{v(v*,adv(funny))} & \semexprset{funny(X)} \\
\koweytree{s(np$\downarrow$, v(smells))} & \semexprset{smell(S,X)} && \\
\hline
\end{tabular}
\end{center}
\caption{TAG grammar for \natlang{John smells funny}}
\label{fig:smells_funny}
\end{figure}

Given the grammar in figure \ref{fig:smells_funny} and the input
semantics \semexprset{smell(s,x), funny(s), name(x,john)}:

\begin{enumerate}
\item We initialise the agenda with the trees \tautree{smells}~,
      \tautree{funny}~, and \tautree{John}~, as in figure
      \ref{fig:semantics} (items on agenda: 3, chart: 0).
\item Item \tautree{smells}~ is removed from the agenda.  There are no
      items to compare it with, so it is simply placed on the chart
      (items on agenda: 2, chart: 1).
\item Item \tautree{funny}~ is removed from the agenda.  It is compared with
      \tautree{smells}~ which results (by adjunction) in the tree
      \tautree{smells~funny}.  Item \tautree{funny} is placed on the
      chart, and \tautree{smells~funny} is placed on the agenda.  (items
      on agenda: 2, chart: 2).  
\item Item \tautree{smells~funny} is removed from the agenda.  It is
      unsuccessfully compared with \tautree{smells}~ and
      \tautree{funny}~ and is placed on the chart.  (items on agenda: 1,
      chart: 3).  
\item Item \tautree{John}~ is removed from the agenda.  It is
      unsuccessfully compared with \tautree{funny}~ and successfully
      compared with \tautree{smell}~ and with \tautree{smells~funny}.
      \tautree{John}~ is placed on the chart.  The result
      \tautree{John~smells}~ is placed on the agenda; on the other hand
      the other result \tautree{John~smells~funny}~ is both syntactically
      and semantically complete, so it is added to the output.
      (items on agenda: 1, chart: 4).  
\item Item \tautree{John~smells}~ is removed from the agenda.  It is
      unsuccessfully compared with \tautree{John}~, \tautree{smells}~,
      and \tautree{smells~funny}~; and successfully compared with
      \tautree{funny}. The resulting tree \tautree{John~smells~funny}~
      is syntactically and semantically complete, so it is added to the
      output.  Item \tautree{John~smells}~ is placed on the chart.
      (items on agenda: 0, chart: 5).  
\item Since the agenda is empty, the processing ends.
\end{enumerate}

We can observe that there are two distinct derivations for the derived
tree \tautree{John~smells~funny}~, one which begins by creating
\tautree{smells~funny}~ and the other by creating
\tautree{John~smells}~.  This is not an artifact of chart processing but
of using a naive bottom-up strategy. The GenI surface realiser employs a
number of mitigating tactics which we will discuss in sections
\ref{sec:ordered_substitution} and \ref{sec:delayed_adjunction}.  

\subsubsection{Intermediate storage}

The chart data structure acts as a form of storage for intermediate data
structures and thus eliminates a great number of redundant
recalculations.  For example, the trees for \natlang{unpleasant smelly
man} and \natlang{dirty smelly man} share the subtree for
\natlang{smelly man}. Using a chart algorithm means that the
latter subtree is only computed once and reused as many times as needed.

\subsubsection{Chart indexing}

The algorithm as we have presented it does not yet exploit the full
potential of tabulation.  Doing so would depend on the availability of a
good \jargon{indexing scheme} which would allow us to reduce the 
search space.

Indexing schemes are more evident for natural language parsing than for
generation; we assign every tree an index for its initial and final
string position. So, to parse \natlang{John saw Mary with Peter} the
agenda would be initialised with (0,1,\tautree{John}),
(1,2,\tautree{saw}), (2,3,\tautree{mary}), (3,4,\tautree{with}),
(4,5,\tautree{Peter}).  This prevents some clearly unnecessary
comparisons from taking place. The tree for (1,2,\tautree{saw}) is
compared with that for (2,3,\tautree{Mary}) because they articulate
around the common index 2.  But it is not compared with
(4,5,\tautree{Peter}) because their indices have nothing to do with each
other.  The use of indices partitions the search space between parts
that are clearly avoidable and those that need to be explored.  

%The latter can also be further consolidated to avoid redundant work
%from equivalent comparisons.  Trees which are equivalent for the
%purposes of comparison are grouped together into \jargon{edges}.  In
%chart algorithms, it is not the trees that get compared but their
%representative edges.  Note that the example above can be read in two
%ways: either John was with Peter when he saw Mary, or John saw Mary
%when she was with Peter.  This means that the verb phrase
%(1,5,\tautree{saw~mary~with~peter}) can either be formed by combining
%(1,3,saw mary) and \tautree{3,5,peter) or by combining (1,2,saw) with
%(2,5,mary with peter).  If we consider trees with the same indices and
%root category as belonging to the same edge, then we only need to make
%a single comparison between the edges for (1,5,saw mary with peter) and
%that for (0,1, john).  

Numerical indices serve as the ``natural points of articulation'' for a
parsing algorithm \cite{kay96chart}, but they cannot be used for
generation because linear order of literals is not natural to semantic
expression.  The semantics \semexprset{name(j,john),  smells(s,j)} is
equivalent to \semexprset{smells(s,j), name(j,john)}, whereas the
English phrases ``John smells'' and ``smells John'' are not.  Put
another way, the surface realisation task is equivalent to that of
parsing a completely free word order language. GenI does not implement
an indexing scheme, but we will propose one in section
\ref{sec:distinguished_chart}.

\subsection{Ordered substitution}
\label{sec:ordered_substitution}

\begin{figure}
\begin{center}
\begin{tabular}{|ll|}
\hline
initial trees & \\
\hline
\koweytree{s(np$\downarrow$, v(hates), np$\downarrow$)} &
\semexprset{hate(X,Y,Z)} \\
\koweytree{np(mary)} & \semexprset{name(X,mary)} \\ 
\koweytree{np(john)} & \semexprset{name(X,john)} \\
\hline
\end{tabular}
\end{center}
\caption{TAG grammar for \natlang{Mary hates John}}.
\label{fig:mary_hates_john}
\end{figure}

We observed in section \ref{sec:chart_example} that it is possible to
produce the same derived tree in different ways.  In the GenI generator,
some of these redundant derivations are prevented by using ordered
substitution.  Using the grammar in figure \ref{fig:mary_hates_john},
the derived tree \koweytree{s(np(Mary), v(hates), np(John))} can be built
either by first substituting \koweytree{np(Mary)} into the tree
\koweytree{s(np$\downarrow$, v(hates), np$\downarrow$)} to get
\koweytree{s(np(Mary), v(hates), np$\downarrow$)} and then substituting
\koweytree{np(John)} into that tree.  Alternatively, it can be built by
first substituting \koweytree{np(John)} to get
\koweytree{s(np$\downarrow$,v(hates), np(John))}, into which
\koweytree{np(Mary)} is substituted.  If we perform substitution in a
fixed order, for example left-to-right, then the second derivation is
eliminated.  Since the trees \koweytree{np(Mary)} and \koweytree{np(John)}
are inserted into two different substitution sites, we know that they
do not interact, and that rejecting the redundant derivation will not
prevent any legitimate results from being produced.

Ordered substitution has the secondary benefit of preventing certain
intermediary structures from being built.  Specifically, no derived tree
can be built in which a substitution site is filled whose predecessor
(in the chosen substitution order) is not. For instance assuming a left to
right substitution order, the tree \koweytree{s(np$\downarrow$,v(hates),
np(John))} in the above example will not be produced. 

\subsection{Delayed adjunction}
\label{sec:delayed_adjunction}

\begin{figure}
\begin{center}
\begin{tabular}{|ll|ll|} 
\hline
initial trees & & 
auxiliary trees & \\ 
\hline
\koweytree{np(man)} & \semexprset{man(X)} 
& \koweytree{np(det(the),np*)} & \semexprset{def(X)}\\          
\koweytree{s(np$\downarrow$, v(rejects), np$\downarrow$)} &
\semexprset{reject(X,Y,Z)} 
&
\koweytree{np(adj(beautiful),np*)} & \semexprset{beautiful(X)} \\
\koweytree{np(woman)} & \semexprset{woman(X)} &  
\koweytree{np(adj(heartless),np*)} & \semexprset{heartless(X)} \\    
&& \koweytree{np(adj(smelly),np*)}  & \semexprset{smelly(X)} \\
&& \koweytree{np(adj(dirty),np*)}   & \semexprset{dirty(X)} \\
\hline
\end{tabular}
\end{center}
\caption{TAG grammar for \natlang{the beautiful heartless woman rejects
the dirty smelly man}}
\label{fig:woman_rejects}
\end{figure}


TAG adjunction provides us with means for coping with the
problem of intersective modifiers (section
\ref{sec:intersective_modifiers}).  Following \cite{carroll99eff}, we
break generation into two phases.  In the first phase, we perform
generation but using only TAG substitution.  Then we discard any trees
which have substitution nodes that remain to be filled, because we know
that these could never lead to a result. Then we switch to the second
phase, which consists of generation using only adjunction.

We can examine the procedure in more detail in an example.  Consider the
target semantics \semexprset{def(m), dirty(m), smelly(m), man(m),
def(w), woman(w), beautiful(w), heartless(w), reject(r,w,m)}.  Using the
grammar in figure \ref{fig:woman_rejects}, this should be realised as
the sentence \natlang{the beautiful heartless woman rejects the dirty
smelly man}.  

\begin{enumerate}
\item In the first phase, TAG substitution is performed between
      \tautree{rejects} and \tautree{man} resulting in 
      \tautree{rejects~man}.  This derived tree is then substituted
      with \tautree{woman} to get the result
      \tautree{woman~rejects~man}.
\item Now trees that still have substitution sites, i.e.
      \tautree{rejects} are discarded. This leaves us with the trees
      \tautree{man}, \tautree{woman}, \tautree{woman~rejects~man}; and a
      chart containing \tautree{the}, \tautree{dirty}, \tautree{smelly},
      \tautree{beautiful} and \tautree{heartless}.
\item In the second phase, TAG adjunction is performed between the
      auxiliary and the non-auxiliary trees.  This eventually produces a
      derived tree that covers the input semantics, the leaf nodes of
      which can be read to produce the string \natlang{the beautiful
      heartless woman rejects the dirty smelly man}.
\end{enumerate}

Delayed adjunction does not solve the problem of intersective modifiers
but largely contains the number of intermediate structures being built.
The above example still produces an exponential number of redundant
substrings (such as \natlang{the beautiful woman rejects the man}).
However by getting substitution over with in the beginning,  we prevent
a large number of useless interactions such as trying to substitute
\tautree{dirty~man} into \tautree{woman~rejects}, or into
\tautree{the~woman~rejects}, or \tautree{beautiful~woman~rejects}, and
so forth.

\subsection{The GenI algorithm}

\begin{figure}
\begin{center}
\includegraphics[scale=1]{images/gen.pdf}
\caption{The GenI algorithm}
\label{fig:geni_algo}
\end{center}
\end{figure}

We present the basic GenI generator in figure \ref{fig:geni_algo}, as
well as algorithms \ref{alg:geni} and \ref{alg:geni_helper}.  This
includes a lexical selection step (section \ref{sec:bu_generation}),
delayed adjunction via separate substitution and adjunction phases, a
chart-processing algorithm (section \ref{sec:chart}) with a trivial
implementation of the chart data structure.  We assume that the
functions \textproc{Substitution} and \textproc{Adjunction} have already
been defined and that they return a set of trees (an empty set if the
operation fails).  Ordered substitution is assumed to be implemented in
the \textproc{Substitution} function.  For simplicity's sake, we
completely ignore variable unification.

Throughout this thesis, we assume a language and/or libraries with the
following features:

\begin{itemize}
\item complex assignments: $\tuple{foo,bar} \leftarrow baz$ which
      assumes that $baz$ is a tuple with compatible type, and $foo$ gets 
      assigned to the first value of the tuple, and $bar$ to the second.
\item lists: ``$:$'' indicates list concatenation, and ``$[]$''
      indicates the empty list. 
\item complex types with named components (indicated by the operator
      ``$.$''): for example, $tree.semantics$ should return the
      component $semantics$ of the complex object $tree$
\item associative arrays: If $arr$ is an associative array, then
      $arr[k]$ should retrieve the item associated with key $k$ or 
      return the value $NULL$ if there is none.  $arr.keys$ should
      always return the set of keys used in $arr$.  $\emptyset$ should
      be overloaded to also mean the empty associative array, and $foo
      \in bar$ to mean the item $foo$ in array $bar$, regardless of its
      key.
\end{itemize}

\begin{algorithm}
\caption{Basic GenI algorithm}
\label{alg:geni}
\begin{algorithmic}[1]
\Function{Generator}{$Grammar$,$InputSem$}
\State $Agenda \leftarrow$ \CallFunction{LexSelection}{$Grammar$,$InputSem$}
\State $Chart \leftarrow \emptyset$
\State $output \leftarrow \emptyset$
\State $step \leftarrow $ substitution
\While {$step \neq$ done}
  \State $aTree \leftarrow$ any tree $\in Agenda$
  \State $Agenda \leftarrow Agenda \setminus \set{aTree}$
  \State $Chart \leftarrow$ \CallFunction{ChartInsertion}{$Chart$,$aTree$}
  \ForAll {$cTree \in $ \CallFunction{ChartRetrieval}{$Chart$,$aTree$}}
    \If {$step =$ substitution}
      \State $derived \leftarrow$ \CallFunction{Substitution}{$cTree,aTree$} 
                           $\cup$ \CallFunction{Substitution}{$aTree,cTree$}
    \Else 
      \State $derived \leftarrow$
                   \CallFunction{Adjunction}{$cTree,aTree$} 
    \EndIf
    \State $\tuple{complete,incomplete} \leftarrow$
           \CallFunction{SuccessCheck}{$derived$,$InputSem$} 
    \State $Agenda \leftarrow Agenda \cup incomplete$
    \State $output \leftarrow output \cup complete$
  \EndFor \Comment{end $cTree$ loop}
  \If {$Agenda = \emptyset$}
     \If {$step =$ substitution}
       \State $step \leftarrow$ adjunction
       \State $\tuple{Chart,Agenda} \leftarrow$
              \CallFunction{PartitionTrees}{$Chart$}
     \Else
       \State $step \leftarrow$ done 
     \EndIf
  \EndIf
\EndWhile \Comment{end $step$ loop}
\State \Return $output$
\EndFunction
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Helper functions for GenI algorithm}
\label{alg:geni_helper}
\begin{algorithmic}[1]
\Function{LexSelection}{$Grammar$,$InputSem$}
\State $selected \leftarrow \emptyset$
\ForAll {$tree \in Grammar$}
  \If {$tree.semantics \subseteq InputSem$} 
      \State $selected \leftarrow selected \cup \set{tree}$
  \EndIf
\EndFor 
\State \Return ${selected}$
\EndFunction
\Statex
\Function{SuccessCheck}{$results$,$InputSem$}
\State $complete   \leftarrow \emptyset$
\State $incomplete \leftarrow \emptyset$
\ForAll {$tree \in results$}
  \If {$tree.substitutionSites = \emptyset$ and 
       $tree.semantics = InputSem$}
      \State $complete \leftarrow complete \cup \set{tree}$
  \Else
      \State $incomplete \leftarrow incomplete \cup \set{tree}$
  \EndIf
\EndFor 
\State \Return $\tuple{complete,incomplete}$
\EndFunction
\Statex
\Function{PartitionTrees}{$Chart$}
\State $initial   \leftarrow \emptyset$
\State $auxiliary \leftarrow \emptyset$
\ForAll {$tree \in Chart$}
\If {$tree.substitutionSites = \emptyset$}
  \Comment { only take complete trees }
  \If {$tree$ is an auxiliary tree}
    \State $auxiliary \leftarrow initial \cup \set{tree}$
  \Else
    \State $initial   \leftarrow initial \cup \set{tree}$
  \EndIf
\EndIf
\EndFor
\State \Return $\tuple{initial,auxiliary}$ 
\EndFunction
\Statex
\Function{ChartRetrieval}{$Chart$,$tree$}\Comment{these will be 
reimplemented in section \ref{sec:chart_sharing}}
\State \Return $Chart$ 
\EndFunction
\Statex
\Function{ChartInsertion}{$Chart$,$tree$}
\State \Return $Chart \cup \set{tree}$
\EndFunction
\end{algorithmic}
\end{algorithm}

% -------------------------------------------------------------------------
\chapter{Optimising the GenI surface realiser}
\label{chp:optimisations}
% -------------------------------------------------------------------------

This chapter presents the work carried out during the DEA stage.  In
section \ref{sec:optimisations} we describe four optimisations we
introduced in the GenI generator.  We detail in \ref{sec:implementation}
the implementation of these optimisations and various other extensions
to the generator.  Finally, section \ref{sec:results} discusses the
effect of the optimisations on the overall performance of the generator.

\section{Optimisations}
\label{sec:optimisations}

This thesis is mainly about four optimisations for the surface realiser
that we designed and implemented.  The two simplest deal with the
combinatorics of adjunction.  \jargon{Ordered adjunction} works
similarly to ordered substitution (section
\ref{sec:ordered_substitution}) and imposes an order on the evaluation
of adjunction sites in the tree.  \jargon{Semantic filtering} on the
other hand improves on the delayed adjunction mechanism by detecting and
removing intermediary structures that cannot lead to a semantically
complete result.  The next optimisation, \jargon{polarity automata},
represents the bulk of this thesis.  We use linguistic information
(which has to be added to grammars) to identify and filter out the
sequences of lexical items which cannot lead to a successful realisation.
Finally, we use \jargon{chart sharing} to refine the polarity automata,
thereby reducing the overhead it introduces.

\subsection{Ordered adjunction}
\label{sec:ordered_adjunction}

This optimisation has a similar effect to ordered substitution (section
\ref{sec:ordered_substitution}), that is, it prevents the generation of
certain redundant derivations and intermediate structures for the same
tree.  As with ordered substitution, the adjunction sites of a given
derived tree are tried in a given order.  Note that in contrast to
substitution sites, adjunction sites do not necessarily need to be used.
Therefore, once all auxiliary trees have been considered for a
given site, the next site will be considered for adjunction.  Another
difference with ordered substitution is that adjunction sites may
be used more than once.  To account for this, we repeat the adjunction 
attempts until no further adjunctions are possible.

\subsection{Semantic filtering}
\label{sec:sfilter}

One possible way to improve the delayed adjunction mechanism is to make
better use of the semantics.  As discussed in section
\ref{sec:delayed_adjunction}, delayed adjunction means using separate
substitution and adjunction phases, and only letting the trees without
any remaining substitution sites into the adjunction phase.  This
filtering criterion could benefit from further tightening. To see this,
consider again the example discussed in section
\ref{sec:delayed_adjunction}.  In this example, at the stage where
adjunction starts to apply, the trees available to the generator
are given in figure \ref{fig:semantic_filtering}.  Now note that of the
three non-auxiliary trees, only one can yield a sentence covering the
entire input semantics when combined with the auxiliary trees.
The optimisation we now introduce aims at
filtering the other two trees away; since their use cannot
possibly lead to a successful realisation, such trees can be safely ignored. 
Concretely, we modify the function \textproc{PartitionTrees}
in algorithm \ref{alg:geni_helper} to calculate the union of all
auxiliary tree semantics, which we call $\phi_A$, and delete from the
agenda, any derived tree with semantics $\phi_s$ if $\phi_A \cup \phi_s
\neq \phi_i$, where $\phi_i$ is the input semantics.  This leaves behind
only the trees which have a chance of fulfilling the input semantics via
adjunction, in this case \koweytree{s(np(woman), vp(rejects), np(man))},
as we see in figure \ref{fig:semantic_filtering2}.  When combined with
the auxiliary trees, this will indeed produce the sentence \natlang{the
beautiful heartless woman rejects the dirty smelly man}.


\begin{figure}
\begin{center}
\begin{tabular}{|l|l|} 
\hline
non-auxiliary trees & auxiliary trees \\
\hline
\koweytree{np(man)}   & \koweytree{np(det(the),np*)}           \\
\koweytree{np(woman)} & \koweytree{np(adj(beautiful),np*)}     \\ 
\koweytree{s(np(woman), v(rejects), np(man))}  
& \koweytree{np(adj(heartless),np*)} \\ 
& \koweytree{np(adj(smelly),np*)}    \\      
& \koweytree{np(adj(dirty),np*)}     \\    
\hline
\end{tabular}
\end{center}
\caption{After the substitution phase in delayed adjunction}
\label{fig:semantic_filtering}
\end{figure}

\begin{figure}
\begin{center}
\begin{tabular}{|l|l|} 
\hline
non-auxiliary trees & auxiliary trees \\
\hline
\koweytree{s(np(woman), v(rejects), np(man))}  
& \koweytree{np(det(the),np*)}           \\
& \koweytree{np(adj(beautiful),np*)}     \\ 
& \koweytree{np(adj(heartless),np*)} \\ 
& \koweytree{np(adj(smelly),np*)}    \\      
& \koweytree{np(adj(dirty),np*)}     \\    
\hline
\end{tabular}
\end{center}
\caption{Delayed adjunction with semantic filtering}
\label{fig:semantic_filtering2}
\end{figure}

\subsection{Polarities}
\label{sec:polarity_overview}

Natural language often permits many different ways to express the same
idea. For example, we can write in the following table some possible
expressions for the literals \semexpr{gift(g), cost(g,x)} and
\semexpr{high(x)}. \footnote{For simplicity reasons we here make the
simplifying assumption that determiner and noun form a single lexical
item.  Note also that lexical items in a TAG can have multiple anchors
so that for instance the initial tree for the predicative noun
\natlang{costs} is anchored with both the noun \natlang{costs} and the
preposition \natlang{of}.}

\begin{center}
\begin{tabular}{|c|c|c|}
\hline
\semexpr{gift(g)}  & \semexpr{cost(g,x)}    & \semexpr{high(x)} \\
\hline
\tautree{the~gift}    & \tautree{the~cost~of}  & \tautree{is~high} \\
\tautree{the~present} & \tautree{costs}        & \tautree{much}    \\
\hline
\end{tabular}\\
\end{center}

The table above shows some \jargon{lexical ambiguity} for each literal.
As in the table, ambiguity can come from the availability of different
lexical items to express the same literal, but it can also come from the
many uses of a single word.  In fact in a average-sized TAG, lexical
ambiguity is usually very high.  For instance, the core TAG for French
developed by Anne Abeille in Paris 7 counts an average of 150 lexical
items for verbs.

We can think of generation partly as selecting a combination of lexical
items, which when taken together, verbalise the entire input semantics.
The number of possible combinations is $\prod_{1 \leq i \leq n}{a_i}$
with $a_i$ the degree of lexical ambiguity for the $i$th literal, and
$n$, the number of literals in the input semantics.  So in the above
example, we need to explore $2 \times 2 \times 2=8$ combinations.  In
other words, the size of the search space is exponential with respect to
the number of literals.

The ``polarity optimisation'' we are now presenting is based on the
observation that a large number of the initially possible combinations
are syntactically invalid, i.e. cannot possibly lead to a successful
realisation.  For instance, although combinations like \natlang{the
gift}, \natlang{the cost of}, \natlang{a lot} cover the entire
semantics, they cannot be stitched together to form a complete
expression.  This leaves a considerable margin for an optimisation to
detect and filter out such combinations ahead of time.  Indeed, such
an optimisation has been successfully put to work in a parser developed
by Guillaume Bonfante, Bruno Guillaume and Guy Perrier for
interaction grammars \cite{perrier02ig,bonfante03leopar}.  The work we
present here investigates how this idea can be transposed to the
TAG-based surface realisation task.

The optimisation involves the addition to the grammar of some additional
linguistic knowledge, the so called ``polarities''; the construction and
the pruning of a finite state automaton on the basis of this
information; and the use of this automaton to filter out the necessarily 
invalid combinations.  We now discuss each of these in turn.

\subsubsection{Polarity keys}
\label{sec:polarity_keys}

We augment our grammars with some explicit combinatoric knowledge.  Each
lexical item is associated with a set of \jargon{polarity keys} where
each key is a label, and a positive or negative integer which we call a
\jargon{charge}.  Polarity keys allow trees to provide hints about which
other trees they may combine with.  Below, for instance, we assign to
the trees \tautree{costs} and \tautree{is~high} the keys $\set{-1np}$
meaning that these verb phrases ``require'' an $np$ tree.  To balance
these, we assign $\set{+1np}$ to the noun phrase trees.  

Any combination of lexical items which does not have a net charge of
zero is necessarily syntactically invalid. For instance, \natlang{the
cost of the gift much} has a charge of $+1np$, so it is clearly not a
solution.  In contrast, \natlang{the cost of the gift is high} has a
charge of $0np$, which does not \emph{guarantee} syntactic compatibility
but suggests that the combination is worth exploring.

\begin{center}
\begin{tabular}{|c|c|c|}
\hline
\semexpr{gift(g)}  & \semexpr{cost(g,x)}    & \semexpr{high(x)} \\
\hline
\tautree{the~gift} \color{blue}{+1np} & 
\tautree{the~cost~of}  &
\tautree{is~high} \color{red}{-1np}\\
%
\tautree{the~present} \color{blue}{+1np} & 
\tautree{costs} \color{red}{-1np}      & 
\tautree{much}   \\
\hline
\end{tabular}\\
\end{center}

\subsubsection{Automaton construction}

\paragraph{Construction for a single polarity key}

The construction and use of the automata fits in between the lexical
selection and the generation step.  It requires a table like that in
section \ref{sec:polarity_keys} where columns are indexed by the
literals of the input semantics, and rows contain the lexical items
whose semantics includes the column index. Given such a table, a 
combination of lexical items covering the input semantics corresponds to
a path across the table where we select exactly one row for every
column. The finite-state automata we build is a way to represent the
set of possible combinations and to associate with each of these
combinations the polarity charge assigned to it by the grammar.
We refer to these automata as \jargon{polarity automata}.

Algorithm \ref{alg:simpleaut} presents a simple version of the
automaton construction, in which we assume that we only have to deal
with a single polarity key.  Each state $\tuple{L,C}$ in the automaton
represents the set of paths up to the $L$th literal that have a net
charge of $C$.  Any transitions in the automaton are from some state
$\tuple{L,C_1}$ to $\tuple{L+1,C_2}$ and has as label, the name of one
of the lexical items verbalising the literal $L$.

We initialise the automaton with a state $\tuple{0,0}$ that does not
cover any literal.  Then we augment the automaton one literal at
time (lines \algref{alg:simpleaut}{alg:simpleaut:loopstart} to
\algref{alg:simpleaut}{alg:simpleaut:loopend}) until reaching the last
literal $N$.  If we declare the final state of the automaton to be
$\tuple{N,0}$, and prune it (algorithm \ref{alg:prune}), we are left
with a minimised automaton \cite{hopcroft79intro} that only represents
the combinations with zero net charge. The final state automaton for the
example discussed above (section \ref{sec:polarity_keys}) is given in
figure \ref{fig:polarity_automaton_pruned}.

\begin{figure}
\begin{center}
\includegraphics[scale=0.5]{images/basicaut-gpruned.pdf}
\caption{Simple polarity automaton (pruned)}
\label{fig:polarity_automaton_pruned}
\end{center}
\end{figure}

\begin{figure}
\begin{tabular}{|l|p{12.5cm}|} 
\hline
\textbf{name} & \textbf{type and use} \\
\hline
$N$ & the number of literals in the input semantics\\
$Labels$ & the set of integers from $1$ to $N$\\
$LE$ & ($Labels \rightarrow Lex$) a function mapping elements of 
$Labels$ to sets of lexical entries\\
$Pol'$ & ($Lex \rightarrow Integers$) a function mapping a
lexical entry to a charge\\
$Automaton$ & a polarity automaton $\tuple{
States,InitialState,FinalStates,Transitions }$\\
\hline
$PolKeys$ & a set of polarity keys\\
$Pol$ & ($Lex \times PolKeys \rightarrow Integers$) a function mapping a
lexical entry and a given polarity key to a charge \\
$LSem$ & ($Lex \rightarrow \set{Integers}$) a function mapping a
lexical entry to a subset of $Labels$\\
\hline
\end{tabular}
\caption{Special variables used in polarity automaton algorithms}
\label{fig:polarity_vars}
\end{figure}

\begin{algorithm}
\caption{Construction of a simple polarity automaton}
\label{alg:simpleaut}
\begin{algorithmic}[1]
\Function{SimpleAut}{$Key$,$LE$,$Pol$,$N$}
\Comment {$Key \in PolKeys$}
\State $InitialState \leftarrow \tuple{ 0,0 }$
\State $FinalStates   \leftarrow \set{\tuple{ N,0 }}$ 
\State $States \leftarrow \emptyset$
\State $curStates \leftarrow \set{InitialState}$
\For {$i,0 < i < N$}
  \label{alg:simpleaut:loopstart}
  \State $newStates \leftarrow \emptyset$
  \Comment{recently created items}
  \ForAll {$st \in newStates$}
    \State $\tuple{\_,\_,c} \leftarrow st$
    \ForAll {$lex \in LE(i)$} 
    \Comment{see figure \ref{fig:polarity_vars}}
      \State $newSt \leftarrow \tuple{ i,c + Pol'(lex) }$
      \State $newStates \leftarrow newStates \cup \set{newSt}$
      \State $States \leftarrow States \cup {newSt}$
      \State $Transitions \leftarrow Transitions \cup 
             \set{\tuple{ st,lex,newState }}$
    \EndFor
  \EndFor
  \State $curStates \leftarrow newStates$ 
  \label{alg:simpleaut:loopend}
\EndFor
\State $Automaton \leftarrow \PolAutomaton$
\State \Return \CallFunction{PruneAut}{$Automaton$} 
\EndFunction
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Automaton pruning}
\label{alg:prune}
\begin{algorithmic}[1]
\Function{PruneAut}{$Automaton$}
\State $\PolAutomaton \leftarrow Automaton$ 
\State $nonfinal \leftarrow States \setminus FinalStates$
\State $blacklist \leftarrow \{st \in nonfinal$ 
       s.t. \CallFunction{HasNoTrans}{$st$}$\}$
\While {$blacklist \neq \emptyset$}
  \State $newBlacklist \leftarrow \emptyset$
  \ForAll {$s \in blacklist$}
    \ForAll {$\tuple{ p,l,s } \in Transitions$}
      \State $States \leftarrow States \setminus {s}$
      \State $Transitions \leftarrow Transitions \setminus \set{\tuple{ p,l,s }}$
      \If {\textproc{HasNoTrans}(p)}
         \State $newBlacklist \leftarrow newBlacklist \cup \set{p}$
      \EndIf
    \EndFor
  \EndFor
  \State $blacklist \leftarrow newBlacklist$
\EndWhile
\State \Return $\tuple{ States,InitialState,FinalStates,Transitions }$
\EndFunction
\Statex
\Function{HasNoTrans}{st}
\State $trans \leftarrow \set{\tuple{ st,\_,\_ } \in Transitions}$
\State \Return $trans = \emptyset$
\EndFunction
\end{algorithmic}
\end{algorithm}

\paragraph{Generalisation for multiple polarity keys}

We can generalise the optimisation to the use of several polarity keys.
Each key acts as a linguistic filter, so the more keys we take into
account, the more filtering we accomplish.  One way to do this is to
construct a polarity automaton for each polarity key and then intersect
them.  For greater efficiency, we instead perform the intersection
incrementally, that is, we build each successive polarity automaton
using the previous one as a skeleton.

This requires us to change the definition of states to a tuple
$\tuple{L,C}$ where $C$ is no longer a single charge, but a list of
them.  (We actually augment it to the three-tuple $\tuple{L,V,C}$ but
this extra item can be ignored until section \ref{sec:multisem}).  The
general architecture (algorithms \ref{alg:polaut} and \ref{alg:seedaut})
begins with a \jargon{seed automaton} that does not account for any
polarity keys.  We then iterate through the polarity keys, each time
building an intersected automaton that accounts for every key up to the
current one.  Each iteration also includes a pruning step, which we saw
in algorithm \ref{alg:prune}.

\begin{algorithm}
\caption{Polarity automaton construction with incremental intersection}
\label{alg:polaut}
\begin{algorithmic}[1]
\Function{PolAut}{$PolKeys$,$Lex$,$Pol$,$N$,$LE$}
\State $Automaton \leftarrow$ \CallFunction{SeedAut}{$Lex$,$N$,$LE$}
\ForAll {$key \in PolKeys$}
  \State $Automaton \leftarrow$ 
         \CallFunction{BuildAut}{$Automaton$,$key$,$Pol$}
  \State $Automaton \leftarrow$ 
         \CallFunction{PruneAut}{$Automaton$}
\EndFor
\State \Return $Automaton$
\EndFunction
\Statex
\Function{BuildAut}{$Automaton$,$Key$,$Pol$}
\Comment {$Key \in PolKeys$}
\State ${\tuple{ \_,oldInitial,oldFinal,oldTrans }} \leftarrow Automaton$ 
\State ${\tuple{ \_,\_,p }} \leftarrow oldInitial$
\State $InitialState \leftarrow {\tuple{ 0,\emptyset,0:p }}$
\Comment {`:' is a list concatenation operator}
\State $FinalStates   \leftarrow \emptyset$
\ForAll {$oldst \in oldFinal$}
  \State $\tuple{ n,v,p } \leftarrow oldst$
  \State $FinalStates \leftarrow FinalStates \cup \set{\tuple{
  n,v,0:p }}$
\EndFor
\State $cross \leftarrow \set{\tuple{ InitialState,oldInitial,0 }}$
\While {$cross \neq \emptyset$}
  \State $newCross \leftarrow \emptyset$
  \Comment{recently created items}
  \ForAll {$\tuple{ ost_1,nst_1,np_1 } \in cross$}
    \ForAll {$\tuple{ ost_1,lex,ost_2 } \in oldTrans$}
      \State ${\tuple{ i,v,op_2 }} \leftarrow ost_2$
      \State $np_2 \leftarrow np_1 + Pol(lex,Key)$
      \Comment {calculate the polarity of the next state}
      \State $nst_2 \leftarrow {\tuple{ i,v,np_2:op_2 }}$
      \State $newCross \leftarrow newCross \cup 
             \set{ \tuple{ ost_2,nst_2,np_2 } }$
      \State $States \leftarrow States \cup \set{nst_2}$
      \State $Transitions \leftarrow Transitions \cup \set{\tuple{
      nst_1,lex,nst_2 }}$
    \EndFor \Comment{$oldTrans$ loop}
  \EndFor \Comment{$cross$ loop}
  \State $cross \leftarrow newCross$
\EndWhile
\State \Return $\PolAutomaton$
\EndFunction
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Seed automaton construction algorithm}
\label{alg:seedaut}
\begin{algorithmic}[1]
\Function{SeedAut}{$Lex$,$N$,$LE$,$LSem$}
\State $InitialState \leftarrow {\tuple{ 0,\emptyset,[] }}$
\Comment {`$[]$' indicates the empty list}
\State $FinalStates   \leftarrow \set{ {\tuple{ N,\emptyset,[] }} }$
\State $States \leftarrow \set{InitialState}$
\State $Transitions \leftarrow \emptyset$
\State $created \leftarrow \set{InitialState}$
\ForAll {$lit, 1 < lit < N$}
  \State $newCreated \leftarrow \emptyset$
  \ForAll {$current \in created$}
     \State ${\tuple{ newCreated,newTrans }} \leftarrow$ 
            \CallFunction{SeedAutHelper}{$current$,$Lex$,$LE$,$LSem$}
     \State $States \leftarrow States \cup newCreated$
     \State $Transitions \leftarrow Transitions \cup newTrans$
  \EndFor \Comment{$current$ loop}
  \State $created \leftarrow newCreated$
\EndFor \Comment{$lit$ loop}
\State \Return $\PolAutomaton$
\EndFunction
\Statex
\Function{SeedAutHelper}{$current$,$Lex$,$LE$,$LSem$} \Comment{Simple version}
\State ${\tuple{ lit_{cur},\_,\_ }} \leftarrow current$
\State $lit \leftarrow 1+lit_{cur}$
\State $next \leftarrow {\tuple{ lit,\emptyset,[] }}$
\State $newCreated \leftarrow \set{next}$
\State $newTrans \leftarrow \emptyset$
\ForAll {$lex \in LE(lit)$}
  \State $newTrans \leftarrow newTrans \cup 
           \set{\tuple{ current,lex,next }}$
\EndFor \Comment{$lex$ loop}
\State \Return {$\tuple{ newCreated,newTrans}$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsubsection{Multiple literals semantics}
\label{sec:multisem}

One potential complication is that trees in realistic grammars may 
span more than one literal (consider \tautree{is~expensive}, which
covers both \natlang{cost(g,x)} and \natlang{high(x)}).  Since these
trees do not fit neatly into a single column of the automaton
construction table, we repeat them for all the columns of the semantics
they represent.  But this introduces its own share of problems. Once we
use a \jargon{multiliteral tree} for a literal, we must make sure that
we use the same tree for the other literals that it covers, and make
sure that its polarity charge is only taken into account once.

We do this by augmenting the states in the polarity automaton to be a
three-tuple $\tuple{L,V,C}$ where $V$ contains any extra semantics
information which is contributed by a multiliteral tree.  Whenever we
encounter a literal which is in the extra semantics of the state, we can
remove that literal from the extra semantics and make an empty
transition $\epsilon$.  This modification only requires a change to the
construction of the seed automaton (algorithm \ref{alg:seedaut_multi})
and lookup function which assigns no polarity keys to the empty
transition.

\begin{algorithm}
\caption{Modified seed automaton construction algorithm}
\label{alg:seedaut_multi}
\begin{algorithmic}[1]
\Function{SeedAutHelper}{$current$,$Lex$,$LE$,$LSem$} \Comment{Enhanced version}
\State $newCreated \leftarrow \emptyset$
\State $newTrans \leftarrow \emptyset$
\State ${\tuple{ lit_{cur},v_{cur},\_ }} \leftarrow current$ 
\State $lit \leftarrow 1 + lit_{cur}$
\ForAll {$lex \in LE(lit)$}
  \State $v_{lex} \leftarrow LSem(lex)$
  \State $v \leftarrow v_{lex} \cup v_{cur}$
  \If {$lit \in v_{lex}$} \Comment{check extra semantics}
    \State $v \leftarrow v \setminus \set{lit}$
    \State $lex \leftarrow \epsilon$
  \EndIf
  \State $next \leftarrow {\tuple{ lit,v,[] }}$
  \State $newTrans \leftarrow newTrans \cup 
         \set{\tuple{ current,lex,next }}$
  \State $newCreated \leftarrow newCreated \cup \set{next}$
\EndFor 
\State \Return {$\tuple{ newCreated,newTrans}$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsection{Chart sharing}
\label{sec:chart_sharing}

The polarity automaton thus yields a compact representation of those
combinations of lexical items that potentially lead to a successful
realisation.  Next it must be used to guide the surface realisation
process. We explored two different ways to do this, which we now
discuss.

The simplest approach is to collect a set of paths by walking the
automaton, and to perform chart generation separately for each path, using
the lexical items along that path as a basis for generation.  The
motivation behind the separation is to prevent mutually incompatible
items from being compared with each other. However, this simple approach
does not account for the fact that different paths may often have
lexical items in common. 

The second, more sophisticated approach consists in factorising these
lexical items that are common to several paths.  To this end, we
annotate each tree with the set of paths on which it appears.  During
generation, we only compare trees if they have some paths in common,
that is if the intersection of their paths is non-empty.  Any resulting
derived tree is annotated with this intersection of paths.  Since the
number of paths is known, we can express these sets as bit vectors,
using the bitwise-and operation to calculate the intersection.  We can
further improve on this concept by introducing the bit vector as a chart
indexing scheme, where the chart is an associative array mapping a bit
vector to a set of trees (algorithm \ref{alg:polarity_chart}).
Retrieving trees from the chart consists of selecting the subset of keys
which intersect a given tree's path set, and taking the union over the
resulting sets of trees.

\begin{algorithm}
\caption{Chart operations with automaton path indexing}
\label{alg:polarity_chart}
\begin{algorithmic}[1]
\Function{ChartRetrieval}{$Chart$,$tree$}\Comment{returns a set of trees}
\State $selection \leftarrow \emptyset$
\ForAll{$k \in Chart.keys$} \Comment{$Chart$ is an associative array}
  \If {$k \cap tree.paths \neq \emptyset$}
     \State $selection \leftarrow selection \cup Chart[k]$
  \EndIf
\EndFor
\State \Return $selection$
\EndFunction
\Statex
\Function{ChartInsertion}{$Chart$,$tree$}\Comment{returns a chart}
\State $samePath \leftarrow Chart[tree.path]$
\If {$samePath = NULL$}
  \State $samePath \leftarrow \emptyset$
\EndIf
\State $Chart[tree.path] \leftarrow samePath \cup \set{tree}$
\State \Return $Chart$
\EndFunction
\end{algorithmic}
\end{algorithm}

\section{Implementation}
\label{sec:implementation}

The optimisations just described were implemented in Haskell.  Since we
did not know the potential effect of optimisations, we had to pay
particular attention to modularity, so that any or all of the
optimisations could be enabled, with special care to account for all
possible combinations of optimisations.  In addition to the
optimisations, we also implemented a few supporting features:

\begin{enumerate}
\item Corrections to the generator as bugs were revealed. This 
      included minor subtleties (havoc caused by neglecting to sort a
      list) and conceptual oversights (for example,
      it was not originally foreseen that auxiliary trees could have
      substitution sites, or that adjunction nodes could be used
      multiple times).
\item A rewritten graphical user interface (figures \ref{fig:geni_gui}
      and \ref{fig:geni_polaut}).  This was mainly motivated by a need
      to test the generator and to visualise the results (automata,
      trees, etc).  The visualisation of trees and automata was made
      possible by the open source Graphviz tool.
\item A graphical debugger (figure \ref{fig:geni_debugger}).  As
      grammars grew and optimisation work continued, it became apparent
      that some means of inspecting the intermediary structures built
      during generation would be necessary.  The graphical debugger
      allows the user to step through the generator, gaining an
      understanding of trees being built and their movement through the
      agenda, chart and results.
\item A batch-processing system.  This made it possible to run a set of
      examples over all possible combinations of optimisations and
      automatically tabulate the results.  
\end{enumerate}

\section{Results}
\label{sec:results}

\subsection{Methodology}

The criteria we used to measure performance were

\begin{description}
\item[agenda size] - the number of items that get added to agenda; note
                     that we do not decrement this counter when a tree
                     is removed from the agenda
\item[chart size]  - the number of items that get added to the chart
\item[comparisons] - the number of times any two trees are
                     compared for substitution or adjunction 
\item[time] - the time needed for generation, excluding the lexical
              selection phase but including the automaton construction
              time.  
\end{description}

The generator was compiled using the Glasgow Haskell Compiler (6.2) with 
-O2 level optimisation.  It was run on a single G4 866 Mhz processor
with Mac OS X as the operating system.  Timing results are averaged over
100 iterations of the generator.

The optimisations evaluated are abbreviated as follows: \jargon{oadj} -
orderded adjunction (section \ref{sec:ordered_adjunction});
\jargon{sfilt} - semantic filtering (section \ref{sec:sfilter});
\jargon{pol} - polarity automata (section \ref{sec:polarity_overview});
\jargon{c-shr} - chart sharing (section \ref{sec:chart_sharing}).  If
the polarity optimisation is used without chart sharing, we sum the
results over each generation subtask.

\subsection{Tests performed}

We evaluated the performance of the generator on two input semantics
with a different grammar for each input.  

\subsubsection{Lexical ambiguity}

The \jargon{promettre} example tests the usefulness of polarity automata
on a grammar with high lexical ambiguity.  The input semantics is
\semexprset{promise(e1, a, b, e2), jean(a), marie(b), convince(e2, a, d,
e3), give(e3, d, c, e), indef(c), book(c), paul(d), claire(e)}, which is
realised in the sentence \natlang{jean promettre a marie de persuader
paul de donner un livre a claire} (note: the generator does not perform
inflection, hence the infinitive \natlang{promettre} instead of
\natlang{promets}).  
%
For this example, the degree of lexical ambiguity in the grammar is as
follows: 14 lexical items for \natlang{promettre}, 6 for
\natlang{persuader}, and 8 for \natlang{donner}.  Thus, the number of 
possible combinations is 672.  With the polarity optimisation, the
number of combinations actually explored by the generator is brought
down to 3.

\begin{center}
\begin{tabular}{|r|r|r|r|r|}
\hline
   optimisations & agenda size & chart size & comparisons & time (ms) \\
\hline
\hline
                 none  &   \colorbox{green}{66} & \colorbox{yellow}{51} &     \colorbox{cyan}{2639} &    20.0\\
\hline
                  pol  &   \colorbox{green}{69} & \colorbox{yellow}{39} &      \colorbox{cyan}{585} &    30.0\\
            pol c-shr  &   \colorbox{green}{37} & \colorbox{yellow}{23} &      \colorbox{cyan}{447} &    30.0\\
\hline
                sfilt  &   53 &      51 &     2569 &    20.0\\
            sfilt pol  &   43 &      39 &      493 &    30.0\\
      sfilt pol c-shr  &   25 &      23 &      385 &    30.0\\
\hline
                 oadj  &  137 &      51 &     2635 &    20.0\\
             pol oadj  &  158 &      39 &      590 &    40.0\\
       pol c-shr oadj  &  100 &      23 &      442 &    30.0\\
\hline
           sfilt oadj  &   72 &      51 &     2570 &    20.0\\
       sfilt pol oadj  &   62 &      39 &      494 &    30.0\\
 sfilt pol c-shr oadj  &   44 &      23 &      386 &    30.0\\
\hline
\end{tabular}\\
\end{center}

Since this example is focused on lexical ambiguity, we only comment here
on the effect of the polarity and chart sharing optimisations.  Using
the polarity optimisation reduces the number of tree comparisons by
three quarters and the chart size by a quarter. Without chart
sharing, however, it increases the agenda size due to the lack of
factorisation.  This is remedied by adding chart sharing, in which case,
the agenda size also decreases by more than a quarter.

\subsubsection{Intersective modifiers}

The \jargon{chatnoir} example examines the generator's performance
against the problem of intersective modifiers.  It has an input
semantics \semexpr{\set{chase(e1,a,b), cat(a), black(a), fierce(a),
def(a), def(b), mouse(b)}} which is realised in the corresponding
grammar by the sentence \natlang{le mechant chat noir chasser le
souris}. 

In the grammar used for this example, the lexical items \natlang{le},
\natlang{noir}, \natlang{mechant} are all auxiliary trees adjoining on
to the trees they modify.   

\begin{center}
\begin{tabular}{|r|r|r|r|r|}
\hline
optimisations & agenda size & chart size & comparisons & time (ms) \\
\hline
\hline
                 none  &         \colorbox{magenta}{121} &      13 & \colorbox{green}{3660} &    50.0\\
\hline
                  pol  &          \colorbox{cyan}{87} &       5 & \colorbox{yellow}{2572} &    40.0\\
            pol c-shr  &          87 &       5 &     2572 &    40.0\\
\hline
                sfilt  &          \colorbox{magenta}{93} &      13 & \colorbox{red}{3076} &    40.0\\
            sfilt pol  &          \colorbox{cyan}{61} &       5 &     2020 &    30.0\\
      sfilt pol c-shr  &          61 &       5 &     2020 &    30.0\\
\hline
                 oadj  &         \colorbox{magenta}{472} &      13 & \colorbox{green}{1988} &    40.0\\
             pol oadj  &         \colorbox{cyan}{326} &       5 & \colorbox{yellow}{1300} &    30.0\\
       pol c-shr oadj  &         326 &       5 &     1300 &    40.0\\
\hline
           sfilt oadj  &         332 &      13 & \colorbox{red}{1428} &    50.0\\
       sfilt pol oadj  &         196 &       5 &      780 &    20.0\\
 sfilt pol c-shr oadj  &         196 &       5 &      780 &    20.0\\
\hline
\end{tabular}\\
\end{center}

This table shows the following results. 

First, we observe that semantic filtering 
has a strong decreasing impact on agenda size, chart size and
comparisons.  Specifically, it reduces agenda size and
chart size by a quarter with respect to the null optimisation baseline.
When combined with the polarity optimisation, it decreases the chart
size by 40\% with respect to the polarity optimisation baseline, and
when combined with polarity and chart sharing, it decreases it by the
same amount.  

Second, note that without ordered adjunction, there are 48 possible
derivations for the result \natlang{le mechant chat noir chasser le
souris}.  Ordered adjunction removes many of these redundant derivations
by bringing this number down to 10  (The 10 that remain represent
different orders for the auxiliary trees \tautree{mechant}, \tautree{le}
and \tautree{noir} to be adjoined at the node \natlang{chat}).

A secondary benefit of this reduction in spurious realisation is an
important decrease in the number of comparisons made.  In general, the
decreases is of approximately 50\% with respect to the corresponding
baseline (54\% with respect to the null optimisation baseline, 50\% with
respect to the polarity baseline and 46\% with respect to the semantic
filtering baseline).  Note further that combining all three
optimisations reduces the number of comparisons by 80\%.

Finally note that the increase in agenda size is misleadingly inflated
because we increment the counter for every adjunction site instead of
every tree. Future work on evaluation will include a better evaluation
criterion which accounts for this factor.

\chapter{Conclusion and future work}
\label{chp:conclusion}

We presented a series of optimisations for a natural language surface
realiser using a Tree Adjoining Grammar and a flat semantics.  These
optimisations dealt with two major sources of complexity for the
generation problem.  With polarity automata and chart sharing, we
provided a means for coping with lexical ambiguity.  With semantic
filtering and ordered adjunction, we reduced the number of intermediary
and final structures produced via adjunction.  A more general judgement
of how these optimisations affect the efficiency of the generator would
require a large-scale evaluation based on the use of a reasonable sized
TAG.

\section{Further optimisation}

\subsection{Polarity signatures}
\label{sec:polarity_signatures}

Constructing and walking a polarity automaton can involve a great deal
of overhead, especially considering that a realistic automaton would be
handling hundreds of trees at any time. One possible solution for
reducing the overhead would be to pre-process the lexically selected
trees, and group together trees with identical semantics and polarity
keys.  The groups are labeled with a tuple of $\tuple{S,K}$ where $S$ is
the tree semantics and $K$ is the set of polarity keys that the tree
holds.  These tuples, which we call \jargon{polarity signatures}, could
then be used instead of trees as the labels of the polarity automaton, the
reasoning being that though there maybe hundreds of trees for a given
lexical item, the number of distinct polarity signatures is likely to be
smaller. 

\subsection{Grouped adjunction}
\label{sec:grouped_adjunction}

Despite delayed adjunction, semantic filtering, and ordered adjunction,
the use of auxiliary trees remains a challenge for generation.  In the
\jargon{chatnoir} test, for example, the sentence \natlang{le mechant
chat noir chasser le souris} was derived in 10 different ways, each of
these representing different orders for the adjunction of auxiliary
trees.  

A possible option to deal directly with the intersective modifiers
problem is to identify auxiliary trees that adjoin to the same site,
then we can group them into sets and instead of performing adjunction
with these trees, we would use a placeholder that represents the entire
group.  When generation is complete, we can post-process the results to
properly insert the modifiers.  Even if the post-processing were to use
a bottom-up algorithm (like the rest of the generation), this
modification would still be useful because it would isolate the
generation of intermediate structures to a single item. In the case of
\natlang{The beautiful heartless woman rejects the dirty smelly man},
this would mean that \natlang{beautiful heartless woman} would be dealt
with separately from \natlang{dirty smelly man}.  Instead of $4! = 24$
intermediary structures, we would only be dealing with $2!  \times 2! =
4$.  It might be possible to use a post-processing strategy that
incorporates word-order constraints, so that \natlang{dirty smelly man}
is generated, but not \natlang{smelly dirty man} which is awkward to
native English speakers.  This would further reduce the number of
intermediate structures, and as an added bonus, produce higher quality
sentences.

\subsection{Distinguished chart indexing}
\label{sec:distinguished_chart}

\cite{kay96chart} proposes a scheme for using semantic indices as chart
indices.  Under this scheme, a \jargon{distinguished index} is
arbitrarily selected for every tree among the semantic indices of that
tree.  The distinguished index is propagated during generation: whenever
a tree is substituted or adjoined into another, the distinguished index
of the derived tree is that of latter tree.  If we consider a tree
\natlang{John} with distinguished index \semexpr{j} for semantics
\semexprset{name(j,john)} and a tree \natlang{smells} with the
distinguished index \semexpr{s} for semantics \semexprset{smells(s,j)}.
Substituting \natlang{John} into \natlang{smells} would result in the
derived tree \natlang{John smells} with the distinguished index
\semexpr{s}.

Kay uses the distinguished index as a chart index.  We had mentioned
in section \ref{sec:tag_semantics} that tree nodes are also associated
variables which are unified against the arguments in the input
semantics.  We call these variables (after unification is done)
\jargon{missing indices}.  Given an agenda tree with a substitution site
to fill, or an adjunction site to test, we only consider for combination
the chart trees whose distinguished index is the same as the missing
index of the agenda tree.  This idea is not yet integrated into the GenI
generator and would definitely be worth exploring.

\section{Large scale testing}
\label{sec:large_testing}

The generator has so far been tested on a small number of linguistic
phenomena with a small grammar.  For linguistic, applicative and
evaluation purposes, it would be necessary to link the generator with a
a full-sized grammar for French. Such a grammar can be produced with
the help of the metagrammar compiler developed by Denys Duchier, Benoit
Crabbe, Joseph Leroux and Yannick Parmentier. This metagrammar
facilitates the semi-automated modular development of grammars.  At
present it is used to develop a core grammar for French and a grammar is
already available which has a linguistic coverage comparable to Anne
Abeille's TAG.

To integrate the GenI algorithm with the metagrammar compiler, we have
developed a basic interface that reads the compiler output, but several
open issues still need to be resolved, so as to fully support generation
from the resulting grammars.  In particular, the unification mechanism
needs to be revised. 

Once this grammar can be used by the GenI generator, full scale
evaluation becomes possible.  This evaluation can be achieved on the
basis of a test suite, which can be written with the program
\textit{Annotator} developed by Marilisa Amoia.  \textit{Annotator}
provides an environment in which semantic expressions may be associated
with a set of natural language expressions.  These can then be saved in
a file, which could eventually be parsed and fed into the batch
processing system for the surface realiser.  This will require some
consideration into the most appropriate means of displaying the
test-suite results.  For example, does a test fail if the generator does
not produce all of the natural language expressions for an input
semantics?  What if it produces too many?  Another issue for
consideration is that the generator should identify the source of test
failures whenever possible, for example, that a certain word is not in
the grammar. Since GenI does not produce inflected forms, it would also
be necessary to either get test-writers in the habit of writing
uninflected expressions (\natlang{Marie detester Jean}), or more
usefully, to pre-process and de-inflect the Annotator files, or better
still for the generator to produce inflected output (\natlang{Marie
deteste Jean}).

\section{Generation system}

Once the generator reaches a satisfactory level of completeness and
efficiency, it would become interesting to integrate it into a wider
generation system. Such a system would perform not only surface
realisation, but a fuller range of generation tasks from content
planning (determining what the surface realiser should say), to applying
the morphological finishing touches.  

This system could itself be used and validated into user applications
such as question-answering systems and interactive dialogue systems, 
the integration of which brings up a host of questions on its own.  One
topic of interest is how a generator should behave when producing a full
text or a dialogue with the user. A sophisticated generator should be
able to produce referring expressions in order to create more economical
and natural sentences.  In other words, it should be able to produce
\natlang{Mary hates John. He smells funny.} instead of \natlang{Mary
hates John. John smells funny.}

In short the tactical generation task that we explored in this thesis 
is only a small part of a vast pool of topics to be explored in natural
language generation.

\Annex{GenI generator screenshots}

\begin{figure}
\begin{center}
\includegraphics[scale=0.50]{images/geni_gui.pdf}
\caption{Graphical interface for the GenI generator}
\label{fig:geni_gui}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics[scale=0.50]{images/geni_polaut.pdf}
\caption{Automaton visualisation}
\label{fig:geni_polaut}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics[scale=0.50]{images/geni_debugger.pdf}
\caption{Graphical debugger}
\label{fig:geni_debugger}
\end{center}
\end{figure}


\bibliographystyle{alpha}
\bibliography{deakowey}

\begin{ThesisAbstract}
\begin{EnglishAbstract}
The surface realisation task consists in using a grammar to produce the
sentence(s) associated by this grammar with some input meaning
representation.  This task is known to be NP-complete, so that
optimisation is an important aspect of any practical implementation.
Starting from an existing surface realiser, this thesis proposes and
implements four optimisation techniques, evaluates their effects and
identifies directions for further improvement.
\end{EnglishAbstract}
\end{ThesisAbstract}

\end{document}
