\documentclass[11pt]{article}
\usepackage{acl07}
\usepackage{times}
\usepackage{latexsym}
\setlength\titlebox{6.5cm}    % yes this is part of the standard style

\usepackage{tree-dvips}
\usepackage{amsmath,amstext}
\usepackage{graphicx}
\usepackage{url}
\usepackage{color}
\usepackage{amssymb}
\usepackage{mylingmacros}
\usepackage{xspace}

\newcommand{\todo}[1]{{\bf ** #1 **}}
\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{\surge}{{\sc Surge}\xspace}
\newcommand{\nitrogen}{{\sc Nitrogen}\xspace}
\newcommand{\halogen}{{\sc Halogen}\xspace}
\newcommand{\mumble}{{\sc Mumble}\xspace}
\newcommand{\realpro}{{\sc realpro}\xspace}
\newcommand{\kpml}{{\sc KPML}\xspace}
\newcommand{\geni}{{\sc GenI}\xspace}

%\setlength{\unitlength}{0.3cm}
\newcommand{\dotted}[0]{\makedash{2pt}}

\title{A Symbolic Approach to Near-Deterministic Surface Realisation using Tree Adjoining Grammar}


\author{Claire Gardent\\
  CNRS/LORIA\\
  Nancy, France\\
  {\tt claire.gardent@loria.fr} \And
  Eric Kow\\
  INRIA/LORIA/UHP\\
  Nancy, France\\
  {\tt eric.kow@loria.fr}}
\date{}

\begin{document}
\maketitle
\begin{abstract}
Surface realisers divide into those used in generation (NLG geared
realisers) and those mirroring the parsing process (Reversible
realisers). While the first rely on grammars not easily usable for
parsing, it is unclear how the second type of realisers could be
parameterised to yield from among the set of possible paraphrases, the
paraphrase appropriate to a given generation context. In this paper,
we present a surface realiser which combines a reversible grammar
(used for parsing and doing semantic construction) with a symbolic
means of selecting paraphrases.

\end{abstract}

\section{Introduction}
In generation, the {\it surface realisation} task consists in mapping a
semantic representation into a grammatical sentence.

Depending on their use, on their degree of non-determinism and on the
type of grammar they assume, existing surface realisers can be divided
into two main categories namely, {\it NLG (Natural Language
Generation) geared realisers} and {\it reversible
realisers}.

NLG geared realisers are meant as modules in a full-blown generation
system and as such, they are constrained to be deterministic: a
generation system must output exactly one text, no less, no more. In
order to ensure this determinism, NLG geared realisers generally rely
on theories of grammar which systematically link form to function such
as systemic functional grammar (SFG, \cite{matthiessen1991tga}) and, to a lesser
extent, Meaning Text Theory (MTT, \cite{melcuk1988dst}). In these theories, a
sentence is associated not just with a semantic representation but
with a semantic representation enriched with additional syntactic,
pragmatic and/or discourse information. This additional information is
then used to constrain the realiser output.\footnote{On the other hand,
one of our reviewers noted that ``determinism'' often comes more from
defaults when input constraints are not supplied.  One might see these
realisers as being less deterministic than advertised; however, the
point is that it is possible to supply the constraints that ensure
determinism.} One drawback of these NLG geared realisers however, is that the grammar
used is not usually
reversible i.e., cannot be used both for parsing and for
generation. Given the time and expertise involved in developing a
grammar, this is a non-trivial drawback.

Reversible realisers on the other hand, are meant to mirror
the parsing process. They are used on a grammar developed for parsing
and equipped with a compositional semantics. Given a string and such a
grammar, a parser will assign the input string all the semantic
representations associated with that string by the grammar. Conversely,
given a semantic representation and the same grammar, a realiser will
assign the input semantics all the strings associated with that
semantics by the grammar. In such approaches, non-determinism is
usually handled by statistical filtering: treebank induced
probabilities are used to select from among the possible paraphrases,
the most probable one. Since the most probable paraphrase is not necessarily
the most appropriate one in a given context, it is unclear however,
how such realisers could be integrated into a generation system.

In this paper, we present a surface realiser which combines
reversibility with a symbolic approach to determinism. The grammar
used is fully reversible (it is used for parsing) and the realisation
algorithm can be constrained by the input so as to ensure a unique
output conforming to the requirement of a given (generation)
context. We show both that the grammar used has a good paraphrastic
power (it is designed in such a way that grammatical paraphrases are
assigned the same semantic representations) and that the realisation
algorithm can be used either to generate all the grammatical
paraphrases of a given input or just one provided the input is adequately
constrained.

The paper is structured as follows. Section \ref{sec:grammar}
introduces the grammar used namely, a Feature Based Lexicalised Tree
Adjoining Grammar enriched with a compositional
semantics. Importantly, this grammar is compiled from a more abstract
specification (a so-called ``meta-grammar'') and as we shall see, it
is this feature which permits a natural and systematic coupling of semantic
literals with syntactic annotations. Section
\ref{sec:algo} defines the surface realisation algorithm used to
generate sentences from semantic formulae. This algorithm is
non-deterministic and produces all paraphrases associated by the grammar
with the input semantics. We then go on to show (section
\ref{sec:selection}) how this algorithm can be used on a semantic
input enriched with syntactic or more abstract control annotations and
further, how these annotations can be used to select from among the
set of admissible paraphrases precisely these which obey the constraints
expressed in the added annotations. Section \ref{sec:evaluation} reports on a
quantitative evaluation based on the use of a core tree adjoining
grammar for French. The evaluation gives an indication of the
paraphrasing power of the grammar used as well as some evidence of the
deterministic nature of the realiser. Section \ref{sec:comparison}
relates the proposed approach to existing work and section
\ref{sec:conclusion} concludes with pointers for further research.

\section{The grammar}
\label{sec:grammar}

We use a unification based version of LTAG namely, Feature-based
TAG. A Feature-based TAG (FTAG, \cite{vijayshanker1988fsb}) consists
of a set of (auxiliary or initial) elementary trees and of two tree
composition operations: substitution and adjunction. Initial trees are
trees whose leaves are labelled with substitution nodes (marked with a
downarrow) or terminal categories. Auxiliary trees are distinguished
by a foot node (marked with a star) whose category must be the same as
that of the root node. Substitution inserts a tree onto a substitution
node of some other tree while adjunction inserts an auxiliary tree
into a tree. In an FTAG, the tree nodes are furthermore decorated with
two feature structures (called {\bf top} and {\bf bottom}) which are
unified during derivation as follows. On substitution, the top of the
substitution node is unified with the top of the root node of the tree
being substituted in. On adjunction, the top of the root of the
auxiliary tree is unified with the top of the node where adjunction
takes place; and the bottom features of the foot node are unified with
the bottom features of this node. At the end of a derivation, the top
and bottom of all nodes in the derived tree are unified.

To associate semantic representations with natural language
expressions, the FTAG is modified as proposed in \cite{gardent2003scf}.


\begin{figure}[htbp]
\begin{center}
{\small
% ------------------------------------------ john
\vspace{-1em}
\begin{tabular}{c}
$\,$\\[1.5ex]
\node{np3}{NP$_{j}$}\\[1.5ex]
\node{jon}{John}\\[1ex]
{\tiny {\it name(j,john)}}
\end{tabular}
\nodeconnect{np3}{jon}
% ------------------------------------------ runs
\hspace{-2em}
\begin{tabular}{cc}
\multicolumn{2}{c}{\node{r1}{S}} \\[1.5ex]
\node{r1.1}{NP$\downarrow^{s}$} &
\node{r1.2}{VP$^{r}$} \\[1.5ex]
&
\node{r1.2.1}{V} \\[1.5ex]
&
\node{r1.2.1.1}{runs} \\
\\
&
{\tiny {\it run(r,s)}} \\
\end{tabular}
\nodeconnect{r1}{r1.1}
\nodeconnect{r1}{r1.2}
\nodeconnect{r1.2}{r1.2.1}
\nodeconnect{r1.2.1}{r1.2.1.1}
% ------------------------------------------ often
\begin{tabular}{cc}
\multicolumn{2}{c}{\node{f1}{VP$^{x}$}} \\[1.5ex]
\node{f1.1}{often} &
\node{f1.2}{VP*}\\
&
{\tiny {\it often(x)}}
\end{tabular}
\nodeconnect{f1}{f1.1}
\nodeconnect{f1}{f1.2}
% ---------------------------------------------
}
{\dotted
\anodecurve[br]{np3}[b]{r1.1}{0.3in}
\anodecurve[tl]{f1}[tr]{r1.2}{0.3in}
\anodecurve[bl]{f1.1}[br]{r1.2}{0.3in}
%\anodecurve[r]{np4}[tr]{np2}{0.3in}
}
\vspace{0.5em}

$\Rightarrow$ {\small {\it  name(j,john), run(r,j), often(r)}}
%\vspace{-1em}

\caption{\label{fig:flat} Flat Semantics for ``John often runs''}
\end{center} 
\end{figure} 

Each elementary tree is associated with a flat semantic
representation. For instance, in
Figure~\ref{fig:flat},\footnote{C$^{x}$/C$_{x}$ abbreviate a node with
category C and a top/bottom feature structure including the
feature-value pair $\{$ \textbf{index :} $x \}$.} the trees for
\natlang{John, runs} and \natlang{often} are associated with the
semantics {\it name(j,john)}, {\it run(r,s)} and {\it
often(x)} respectively.

Importantly, the arguments of a semantic functor are represented by
unification variables which occur both in the semantic representation
of this functor and on some nodes of the associated syntactic
tree. For instance in Figure~\ref{fig:flat}, the semantic index
$s$ occurring in the semantic representation of \natlang{runs}
also occurs on the subject substitution node of the
associated elementary tree.

The value of semantic arguments is determined by the unifications
 resulting from adjunction and substitution.  For instance, the
 semantic index $s$ in the tree for \natlang{runs} is unified during
 substitution with the semantic indices labelling the root nodes of
 the tree for \natlang{John}.  As a result, the semantics of
 \natlang{John often runs} is 

\enumsentence{\label{ex:sem}
{\footnotesize $\semexpr{\{name(j,john),run(r,j),often(r)\}}$}
} 

The grammar used describes a core fragment of French and contains
around 6 000 elementary trees. It covers some 35 basic
subcategorisation frames and for each of these frames, the set of
argument redistributions (active, passive, middle, neuter,
reflexivisation, impersonal, passive impersonal) and of argument
realisations (cliticisation, extraction, omission, permutations, etc.)
possible for this frame. As a result, it captures most grammatical
paraphrases that is, paraphrases due to diverging argument
realisations or to different meaning preserving alternation (e.g.,
active/passive or clefted/non-clefted sentence).

\section{The surface realiser, GenI}
\label{sec:algo}

The basic surface realisation algorithm used is a bottom up, tabular
realisation algorithm \cite{kay1996cg} optimised for TAGs. It follows
a three step strategy which can be summarised as follows. Given an
empty agenda, an empty chart and an input semantics $\phi$:

\begin{description}
\item[Lexical selection.] Select all elementary trees whose semantics
  subsumes (part of) $\phi$. Store these trees in the
  agenda.  Auxiliary trees devoid of substitution nodes are stored in a
  separate agenda called the auxiliary agenda.
\item[Substitution phase.] Retrieve a tree from the agenda, add it to
  the chart and try to
  combine it by substitution with trees present in the chart. Add any
  resulting derived tree to the agenda. Stop when the agenda is empty. 
\item[Adjunction phase.] Move the chart trees to the agenda and the
  auxiliary agenda trees to the chart. Retrieve a tree from the
  agenda, add it to the chart and try to combine it by adjunction with
  trees present in the chart. Add any resulting derived tree to the
  agenda. Stop when the agenda is empty.
\end{description}

When processing stops, the yield of any syntactically complete tree whose
semantics is $\phi$ yields an output i.e., a sentence. 

The workings of this algorithm can be illustrated by the following
example. Suppose that the input semantics is  (\ref{ex:sem}).  In a
first step ({\bf lexical selection}), the elementary trees selected are
the ones for \natlang{John, runs, often}.  Their semantics subsumes
part of the input semantics.  The trees for \natlang{John} and
\natlang{runs} are placed on the agenda, the one for \natlang{often}
is placed on the auxiliary agenda.

The second step (the {\bf substitution phase}) consists in
systematically exploring the possibility of combining two trees by
substitution.  Here, the tree for \natlang{John} is substituted into
the one for \natlang{runs}, and the resulting derived tree for
\natlang{John runs} is placed on the agenda.  Trees on the agenda
are processed one by one in this fashion.  When the agenda is empty,
indicating that all combinations have been tried, we prepare for the
next phase.

All items containing an empty substitution node are erased from the
chart (here, the tree anchored by \natlang{runs}).  The agenda
is then reinitialised to the content of the chart and the chart to the
content of the auxiliary agenda (here \natlang{often}).
The {\bf adjunction phase} proceeds much like the previous phase,
except that now all possible adjunctions are performed.  When
the agenda is empty once more, the items in the chart whose semantics
matches the input semantics are selected, and their strings printed
out, yielding in this case the sentence \natlang{John often runs}.

\section{Paraphrase selection}
\label{sec:selection}

The surface realisation algorithm just sketched is non-deterministic.
Given a semantic formula, it might produce several outputs. For
instance, given the appropriate grammar for French, the input in
(\ref{ex:input1}) will generate the set of paraphrases partly given
in (\ref{ex:output1}-\ref{ex:output18}).

\eenumsentence{
\small
\addtolength{\itemsep}{-0.75em}
\item {\it l$_j$:jean(j) l$_a$:aime(e,j,m) l$_m$:marie(m)} \label{ex:input1}
\item Jean aime Marie \label{ex:output1}
\item Marie est aim\'ee par Jean \label{ex:output2}
%\item Marie est aim\'ee de Jean \label{ex:output3}
\item C'est Jean qui aime Marie \label{ex:output4}
%\item C'est Jean de qui Marie est aim\'ee \label{ex:output5}
%\item C'est Jean de qui est aim\'ee Marie \label{ex:output6}
\item C'est Jean par qui Marie est aim\'ee \label{ex:output7}
%\item C'est Jean par qui est aim\'ee Marie \label{ex:output8}
%\item C'est par  Jean que Marie est aim\'ee \label{ex:output9}
\item C'est par Jean qu'est aim\'ee Marie \label{ex:output10}
\item C'est Jean dont est aim\'ee Marie \label{ex:output11}
\item C'est Jean dont  Marie est aim\'ee \label{ex:output12}
%\item C'est de Jean qu'est aim\'ee Marie \label{ex:output13}
%\item C'est de Jean que Marie est aim\'ee \label{ex:output14}
\item C'est Marie qui est aim\'ee par Jean \label{ex:output15}
%\item C'est Marie qui est aim\'ee de Jean \label{ex:output16}
\item C'est Marie qu'aime Jean \label{ex:output17}
\item C'est Marie que Jean aime \label{ex:output18}
\addtolength{\itemsep}{-0.75em}
}

To select from among all possible paraphrases of a given input,
exactly one paraphrase, NLG geared realisers use symbolic information
to encode syntactic, stylistic or pragmatic constraints on the
output. Thus for instance, both \realpro\ \cite{lavoie1997rfp} and
\surge\ \cite{elhadad1999scp} assume that the input associates
semantic literals with low level syntactic and lexical information
mostly leaving the realiser to just handle inflection, word order,
insertion of grammatical words and agreement. Similarly, \kpml\
\cite{matthiessen1991tga} assumes access to ideational,
interpersonal and textual information which roughly corresponds to
semantic, mood/voice, theme/rheme and focus/ground information.

In what follows, we first show that the semantic input assumed by the
realiser sketched in the previous section can be systematically
enriched with syntactic information so as to ensure determinism. We
then indicate how the satisfiability of this enriched input could be
controlled.

\subsection{At most one realisation}
\label{subsec:atmostone}

In the realisation algorithm sketched in Section \ref{sec:algo},
non-determinism stems from lexical ambiguity:\footnote{Given two TAG
trees, there might also be several ways of combining them thereby
inducing more non-determinism. However in practice we found that most
of this non-determinism is due either to over-generation (cases where
the grammar is not sufficiently constrained and allows for one tree to
adjoin to another tree in several places) or to spurious derivation
(distinct derivations with identical semantics). The few remaining
cases that are linguistically correct are due to varying modifier
positions and could be constrained by a sophisticated feature
decorations in the elementary tree. } for each
(combination of) literal(s) $l$ in the input there usually is more
than one TAG elementary tree whose semantics subsumes $l$. Thus each
(combination of) literal(s) in the input selects a set of elementary
trees and the realiser output is the set of combinations of selected lexical
trees which are licensed by the grammar operations (substitution and
adjunction) and whose semantics is the input.

One way to enforce determinism consists in ensuring that each literal
in the input selects exactly one elementary tree. For instance,
suppose we want to generate (\ref{ex:output1}), repeated here as
(\ref{ex:jam}), rather than any of the paraphrases listed in 
(\ref{ex:output2}-\ref{ex:output18}). Intuitively, the syntactic
constraints to be expressed are those given in
(\ref{ex:jam-constraints}).

\eenumsentence{
\small
\addtolength{\itemsep}{-0.75em}
\item Jean aime Marie \label{ex:jam}
\item Canonical Nominal Subject, Active verb form, Canonical Nominal Object \label{ex:jam-constraints}
\item {\it l$_j$:jean(j) l$_a$:aime(e,j,m) l$_m$:marie(m)}
  \label{ex:jam-sem}
\addtolength{\itemsep}{0.75em}
}

The question is how precisely to formulate these constraints, how
to associate them with the semantic input assumed in Section
\ref{sec:algo} and how to ensure that the constraints used do enforce
uniqueness of selection (i.e., that for each input literal, exactly one
elementary tree is selected)? 
To answer this, we rely on a feature of the grammar used, namely that
\textit{each elementary tree is associated with a
linguistically meaningful unique identifier.}

The reason for this is that the grammar is compiled from a higher
level description where tree fragments are first encapsulated into
so-called classes and then explicitly combined (by inheritance,
conjunction and disjunction) to produce the grammar elementary trees
(cf. \cite{crabbe2004mr}).

More generally, each elementary tree in the grammar is associated with
the set of classes used to produce that tree and importantly, this set
of classes (we will call this the {\it tree identifier}) provides a
distinguishing description (a unique identifier) for that tree: a tree
is defined by a specific combination of classes and conversely, a
specific combination of classes yields a unique
tree.\footnote{\label{fn}This is not absolutely true as a tree identifier
only reflects part of the compilation process. In practice, they are
few exceptions though so that distinct trees whose tree identifiers
are identical can be manually distinguished.} Thus the set of
classes associated by the compilation process with a given elementary
tree can be used to uniquely identify that tree.

Given this, surface realisation is constrained as follows. 

\begin{enumerate}
\item Each tree identifier {\it Id(tree)} is mapped into a simplified
  set of tree properties {\it TP$_t$}. There are two reasons for this
  simplification. First, some classes are irrelevant. For instance,
  the class used to enforce subject-verb agreement is needed to ensure
  this agreement but does not help in selecting among competing
  trees. Second, a given class $C$ can be defined to be equivalent to
  the combination of other classes $C_1 \ldots C_n$ and consequently a
  tree identifier containing $C, C_1 \ldots C_n$ can be reduced to
  include either $C$ or $C_1 \ldots C_n$.
\item Each literal $l_i$ in the input is associated with a tree
  property set $TP_i$ (i.e., the input we generate from is enriched
  with syntactic information)
\item During realisation, for each literal/tree property pair
$\langle l_{i}:TP_i \rangle$ in the enriched input semantics, lexical
selection is constrained to retrieve only those trees (i) whose
semantics subsumes $l_i$ and (ii) whose tree properties are $TP_i$
\end{enumerate}

Since each literal is associated with a (simplified) tree identifier
and each tree identifier uniquely identifies an elementary tree,
realisation produces at most one realisation.

Examples \ref{ex:enriched-input1}-\ref{ex:enriched-input3}
illustrates the kind of constraints used by the realiser.

\eenumsentence{
\footnotesize
\item
{\it l$_j$:jean(j)/ProperName
l$_a$:aime(e,j,m)/[CanonicalNominalSubject,\\ ActiveVerbForm, CanonicalNominalObject]\\
l$_m$:marie(m)/ProperName}
\label{ex:enriched-input1}
\\
Jean aime Marie
\\
* Jean est aim\'e de Marie
\item
{\it l$_c$:le(c)/Det\\
l$_c$:chien(c)/Noun\\
l$_d$:dort(e1,c)/RelativeSubject\\
l$_r$:ronfle(e2,c)/CanonicalSubject}
\label{ex:enriched-input2}
\\
Le chien qui dort ronfle
\\
* Le chien qui ronfle dort
\item
{\it l$_j$:jean(j)/ProperName\\
l$_p$:promise(e1,j,m,e2)/[CanonicalNominalSubject, ActiveVerbForm,
CompletiveObject]\\
l$_m$:marie(m)/ProperName\\
l$_{e2}$:partir(e2,j)/InfinitivalVerb}
\label{ex:enriched-input3}
\\
Jean promet \`a marie de partir
\\
* Jean promet \`a marie qu'il partira
}

\subsection{At least one realisation}

For a realiser to be usable by a generation system, there must be some
means to ensure that its input is satisfiable i.e., that
it can be realised.
How can this be done without actually carrying out realisation i.e.,
without checking that the input is satisfiable? Existing realisers
indicate two types of answers to that dilemma. 

A first possibility would be to draw on \cite{yangEtAl91}'s proposal
and compute the enriched input based on the traversal of a systemic
network. More specifically, one possibility would be to consider a
systemic network such as NIGEL, precompile all the functional features
associated with each possible traversal of the network, map them onto
the corresponding tree properties and use the resulting set of tree
properties to ensure the satisfiability of the enriched input.

Another option would be to check the well formedness of the input at
some level of the linguistic theory on which the realiser is
based. Thus for instance, \realpro\ assumes as input a well formed
deep syntactic structure (DSyntS) as defined by Meaning Text Theory
(MTT) and similarly, \surge\ takes as input a functional description
(FD) which in essence is an underspecified grammatical structure
within the SURGE grammar. In both cases, there is no guarantee that
the input be satisfiable since all the other levels of the linguistic
theory must be verified for this to be true. In MTT, the DSyntS must
first be mapped onto a surface syntactic structure and then
successively onto the other levels of the theory while in SURGE, the
input FD can be realised only if it provides consistent information
for a complete top-down traversal of the grammar right down to the
lexical level. In short, in both cases, the well formedness of the
input can be checked with respect to some criteria (e.g., well
formedness of a deep syntactic structure in MTT, well formedness of a
FD in SURGE) but this well formedness does not guarantee
satisfiability. Nonetheless this basic well formedness check is
important as it provides some guidance as to what an acceptable input
to the realiser should look like.

We adopt a similar strategy and resort to the notion of {\it polarity
neutral input} to control the well formedness of the enriched
input. The proposal draws on ideas from
\cite{koller2002gdp,gardent2005gas} and aims to determine whether
for a given input (a set of TAG elementary trees whose semantics
equate the input semantics), syntactic requirements and resources cancel
out. More specifically, the aim is to determine whether given the
input set of elementary trees, each substitution and each adjunction
requirement is satisfied by exactly one elementary tree of the
appropriate syntactic category and semantic index.

Roughly,\footnote{Lack of space prevents us from giving much details
  here. We refer the reader to \cite{koller2002gdp,gardent2005gas} for
  more details.} the technique consists in (automatically)
  associating with each elementary tree a polarity signature
  reflecting its substitution/adjunction requirements and resources
  and in computing the grand polarity of each possible combination of
  trees covering the input semantics. Each such combination whose
  total polarity is non-null is then filtered out (not considered for
  realisation) as it cannot possibly lead to a valid derivation
  (either a requirement cannot be satisfied or a resource cannot be
  used).

In the context of a generation system, polarity checking can be used
to check the satisfiability of the input or more interestingly, to
correct an ill formed input i.e., an input which can be detected as
being unsatisfiable. 

To check a given input, it suffices to compute its polarity count. If it
is non-null, the input is unsatisfiable and should be revised. This is
not very useful however, as the enriched input ensures determinism and
thereby make realisation very easy, indeed almost as easy as polarity
checking. 

More interestingly, polarity checking can be used to suggest
ways of fixing an ill formed input. In such a case, the enriched input
is stripped of its control annotations, realisation proceeds on the
basis of this simplified input and polarity checking is used to preselect all
polarity neutral combinations of elementary trees. A closest match
(i.e. the polarity neutral combination with the greatest number of
control annotations in common with the ill formed input) 
to the ill formed input is then proposed as a probably satisfiable
alternative. 

\section{Evaluation}
\label{sec:evaluation}

To evaluate both the paraphrastic power of the realiser and the impact
of the control annotations on non-determinism, we used a graduated
test-suite which was built by (i) parsing a set of sentences, (ii)
selecting the correct meaning representations from the parser output
and (iii) generating from these meaning representations. The gradation
in the test suite complexity was obtained by partitioning the input
into sentences containing one, two or three finite verbs and by
choosing cases allowing for different paraphrasing patterns. More
specifically, the test suite includes cases involving the following types
of paraphrases:

\begin{itemize}
\addtolength{\itemsep}{-0.5em}
\item Grammatical variations in the realisations of the arguments
  (cleft, cliticisation, question, relativisation, subject-inversion,
  etc.) or of the verb (active/passive, impersonal)
\item Variations in the realisation of modifiers (e.g., relative
  clause vs adjective, predicative vs non-predicative adjective)
\item Variations in the position of modifiers (e.g., pre- vs
  post-nominal adjective)
\item Variations licensed by a morpho-derivational link (e.g., to
  arrive/arrival)
\addtolength{\itemsep}{0.5em}
\end{itemize}

On a test set of 80 cases, the paraphrastic level varies between 1 and
over 50 with an average of 18 paraphrases per input (taking 36 as
upper cut off point in the paraphrases count). 
Figure \ref{fig:paraphrases} gives a more detailed description of the
distribution of the paraphrastic variation. In essence, 42\% of the
sentences with one finite verb accept 1 to 3 paraphrases (cases of
intransitive verbs), 44\% accept 4 to 28 paraphrases (verbs of arity
2) and 13\% yield more than 29 paraphrases (ditransitives). For
sentences containing two finite verbs, the ratio is 5\% for 1 to 3
paraphrases, 36\% for 4 to 14 paraphrases and 59\% for more than 14
paraphrases. Finally, sentences containing 3 finite verbs all accept
more than 29 paraphrases.

Two things are worth noting here.
First, the paraphrase figures might seem low wrt to e.g., work by
\cite{VelOep06} which mentions several thousand outputs for one given
input and an average number of realisations per input varying between
85.7 and 102.2. Admittedly, the French grammar we are using has a much
more limited coverage than the ERG (the grammar used by
\cite{VelOep06}) and it is possible that its paraphrastic power is
lower. However, the counts we give only take into account {\it valid
paraphrases of the input}. In other words, overgeneration and spurious
derivations are excluded from the toll. This does not seem to be the
case in \cite{VelOep06}'s approach where the count seems to include {\it
all} sentences associated by the grammar with the input semantics.

Second, although the test set may seem small it is important to keep in
mind that it represents 80 inputs with distinct grammatical and
paraphrastic properties. In effect, these 80 test cases yields 1 528
distinct well-formed sentences. This figure compares favourably with
the size of the largest regression test suite used by a symbolic NLG
realiser namely, the SURGE test suite which contains 500 input each
corresponding to a single sentence. It also compares reasonably with
other more recent evaluations
\cite{Callaway-Eval-IJCAI-03,Langkilde02} which derive their input
data from the Penn Treebank by transforming each sentence tree into a
format suitable for the realiser \cite{Callaway-Eval-IJCAI-03}. For
these approaches, the test set size varies between roughly 1 000 and
almost 3 000 sentences. But again, it is worth stressing that these
evaluations aim at assessing coverage and correctness (does the
realiser find the sentence used to derive the input by parsing it?)
rather than the paraphrastic power of the grammar. They fail to
provide a systematic assessment of how many distinct grammatical
paraphrases are associated with each given input. 

\begin{figure}\label{fig:paraphrases}
\includegraphics[angle=90,height=5cm,width=0.5\textwidth]{graphs/everything-num-paraphrases}
\end{figure}
 
To verify the claim that tree properties can be used to ensure
determinism (cf. footnote \ref{fn}), we started by
eliminating from the output all ill-formed sentences.  We then
automatically associated each well-formed output with its set of tree
properties. Finally, for each input semantics, we did a systematic
pairwise comparison of the tree property sets associated with the
input realisations and we checked whether for any given input, there
were two (or more) distinct paraphrases whose tree properties were the
same. We found that such cases represented slightly over 2\% of the
total number of (input,realisations) pairs. Closer investigation of
the faulty data indicates two main reasons for non-determinism namely,
trees with alternating order of arguments and derivations with
distinct modifier adjunctions. Both cases can be handled by modifying
the grammar in such a way that those differences are reflected in the
tree properties.

\section{Related work}
\label{sec:comparison}

The approach presented here combines a reversible grammar realiser
with a symbolic approach to paraphrase selection. We now compare it to
existing surfaces realisers. 

{\bf NLG geared realisers.} Prominent general purpose NLG geared
realisers include \realpro, \surge, \kpml, \nitrogen\ and \halogen
. Furthermore, \halogen\ has been shown to achieve broad coverage and
high quality output on a set of 2 400 input automatically derived from
the Penn treebank.

The main difference between these and the present approach is that our
approach is based on a reversible grammar whilst NLG geared realisers
are not. This has several important consequences.

First, it means that one and {\it the same grammar and lexicon can be used
both for parsing and for generation}. Given the complexity involved in
developing such resources, this is an important feature. 

Second, as demonstrated in the Redwood Lingo Treebank, reversibility
makes it easy to {\it rapidly create very large evaluation suites}: it
suffices to parse a set of sentences and select from the parser output
the correct semantics. In contrast, NLG geared realisers either work
on evaluation sets of restricted size (500 input for \surge, 210 for
\kpml ) or require the time expensive implementation of a preprocessor
transforming e.g., Penn Treebank trees into a format suitable for the
realisers. For instance, \cite{Callaway-Eval-IJCAI-03} reports that the
implementation of such a processor for \surge\ was the most time
consuming part of the evaluation with the resulting component
containing 4000 lines of code and 900 rules.

Third, a reversible grammar can be exploited to {\it support not only
realisation but also its reverse, namely semantic
construction}. Indeed, reversibility is ensured through a
compositional semantics that is, through a tight coupling between
syntax and semantics. In contrast, NLG geared realisers often have to
reconstruct this association in rather ad hoc ways. Thus for instance,
\cite{yangEtAl91} resorts to ad hoc ``mapping tables'' to associate
substitution nodes with semantic indices and ``fr-nodes'' to constrain
adjunction to the correct nodes. More generally, the lack of a
clearly defined compositional semantics in NLG geared realisers
makes it difficult to see how the grammar they use could be exploited
to also support semantic construction.

Fourth, the {\it grammar can be used both to generate and to detect
paraphrases}. It could be used for instance, in combination with the
parser and the semantic construction module described in
\cite{gardent2005lss}, to support textual entailment recognition
or answer detection in question answering.

{\bf Reversible realisers.} The realiser presented here differs in mainly two ways from existing reversible realisers such as \cite{white2004rcc}'s CCG system or the
HPSG ERG based realiser \cite{carroll2005her}. 

First, it permits a symbolic selection of the output paraphrase. In
contrast, existing reversible realisers use statistical information to
select from the produced output the most plausible paraphrase. 

Second, particular attention has been paid to the treatment of
paraphrases in the grammar. Recall that TAG elementary trees are
grouped into families and further, that the specific TAG we use is
compiled from a highly factorised description. We rely on these
features to associate one and the same semantic to large sets of trees
denoting semantically equivalent but syntactically distinct
configurations (cf. \cite{gardent2006iud}).

\section{Conclusion}
\label{sec:conclusion}

The realiser presented here, \geni, exploits a grammar which is produced
semi-automatically by compiling a high level grammar description into
a Tree Adjoining Grammar. We have argued that a side-effect of this
compilation process -- namely, the association with each elementary
tree of a set of tree properties -- can be used to constrain the
realiser output.  The resulting system combines the advantages of two
orthogonal approaches. From the reversible approach, it takes the
reusability, the ability to rapidly create very large test suites and
the capacity to both generate and detect paraphrases. From the NLG
geared paradigm, it takes the ability to symbolically constrain the
realiser output to a given generation context.

\geni is free (GPL) software and is available at
\url{http://trac.loria.fr/~geni}.

{\small
\bibliographystyle{acl}
\bibliography{acl07-garkow}
}

\end{document}
