\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}