%% Exemple de source LaTeX pour un article soumis à TALN
\documentclass[12pt,a4paper,twoside]{article}

\usepackage{times}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}

% faire les \usepackage dont vous avez besoin avant le
% ``\usepackage{taln2006}''... (Je ne sais pas pourquoi, mais c'est comme ça !)

\usepackage{latexsym}
\usepackage{url}
\usepackage{lingmacros,pstricks,pst-tree,pst-node}
\usepackage{tree-dvips}
\usepackage{algorithme}
\usepackage{genistuff}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage[normalem]{ulem}
\usepackage{taln2007}
%% \ExecuteOptions{french}
%% \ProcessOptions
\usepackage[frenchb]{babel}
\newcommand{\fup}[1]{\up{#1}}

%%\setlength{\headwidth}{\textwidth}
\fancyhead[LO]{GenI, un réalisateur basé sur une grammaire réversible}
\fancyhead[RE]{C. Gardent, E. Kow}

%%================
%% pages numérotées : laisser dans la soumission initiale,
%% supprimer pour la version finale
\fancyfoot[C]{\thepage}
%%================

\renewcommand\sectionmark[1]{}
\renewcommand\subsectionmark[1]{}
\renewcommand\refname{}

\newcommand\nb[1]{\{#1\}}


% dotted lines in pstricks 
\newcommand{\dotted}[0]{\makedash{2pt}}

\newcommand{\todo}[1]{{\bf ** #1 **}}
\newcommand{\geni}{{\sc GenI}}
\newcommand{\kpml}{{\sc kpml}}
\newcommand{\realpro}{{\sc realpro}}
\newcommand{\mumble}{{\sc mumble}}
\newcommand{\gtag}{{\sc gtag}}
\newcommand{\stag}{{\sc stag}}
\newcommand{\surge}{{\sc surge}}
\newcommand{\mathweb}{{\sc MathWeb}}
\newcommand{\clef}{{\sc CleF}}
\newcommand{\indigen}{{\sc InDiGen}}
\newcommand{\lattice}{{\sc Lattice}}
\newcommand{\spass}{{\sc Spass}}
\newcommand{\otter}{{\sc otter}}
\newcommand{\race}{{\sc race}}
\newcommand{\dlp}{{\sc dlp}}
\newcommand{\fact}{{\sc fact}}

\def\pr#1{\mbox{\textit{\textsf{#1}}}}

\makeatletter


\begin{document}

\title{Une réalisateur de surface basé sur une grammaire réversible}

\author{Claire Gardent\fup{1}\quad Eric Kow\fup{2}\\
  (1) CNRS/LORIA, Nancy\\
  (2) INRIA/LORIA, Nancy\\
  Claire.Gardent@loria.fr, Eric.Kow@loria.fr\\
}

\date{}

\maketitle

\resume{
En génération, un réalisateur de surface a pour fonction de
produire, à partir d'une représentation conceptuelle donnée, une phrase
grammaticale. Les réalisateur existants soit utilisent une grammaire
réversible et des méthodes statistiques pour déterminer parmi
l'ensemble des sorties produites la plus plausible; soit utilisent des
grammaires spécialisées pour la génération et des méthodes symboliques
pour déterminer la paraphrase la plus appropriée à un contexte de
génération donné. 
Dans cet article, nous présentons \geni , un réalisateur de surface
basé sur une grammaire d'arbres adjoints pour le français qui
réconcilie les deux approches en combinant une grammaire
réversible avec une sélection symbolique des paraphrases.
}

\abstract{
In  generation, a surface realiser takes as input a conceptual
representation and outputs a grammatical sentence.
Existing realisers fall into two camps. Either they are based on a reversible
grammar and use statistical filtering to determine among the several
outputs the most plausible one. Or they combine a grammar tailored for
generation and a symbolic means of choosing the paraphrase most
appropriate to a given generation context. 
In this paper, we present \geni , a surface realiser based on a Tree
Adjoining Grammar for French which reconciles both approaches in that
(i) the grammar used is 
réversible and (ii) paraphrase selection is based on symbolic means. }

\motsClefs{Réalisation de surface, Grammaire d'arbres adjoints, Réversibilité}
{Surface realisation, Tree Adjoining Grammar, Reversibility}

%% Aller à la page suivante si nécessaire
\newpage
%%================================================================

\section{Introduction}


En génération, le module de {\it réalisation de surface} a pour fonction de
produire, à partir d'une représentation conceptuelle donnée, une phrase
grammaticale. Par exemple, à partir de l'entrée donnée en
(\ref{ex:entree-jam}), un réalisateur de surface pourra produire l'une  
des variantes listée en (\ref{ex:sortie-jam1}-\ref{ex:sortie-jam10}).

{\small
\begin{tabular}{ll}
\begin{minipage}{7cm}
\eenumsentence{
\item {\it jean(j) aimer(e,j,m) marie(m)} \label{ex:entree-jam}
\item Jean aime Marie \label{ex:sortie-jam1}
\item Marie est aim\'ee par Jean \label{ex:sortie-jam2}
\item Marie est aim\'ee de Jean \label{ex:sortie-jam3}
\item C'est Marie que Jean aime \label{ex:sortie-jam4}
\item C'est Jean qui aime Marie \label{ex:sortie-jam5}
}
\end{minipage} &
\begin{minipage}{7cm}
\addtocounter{enums}{-1}
\eenumsentence{
\addtocounter{enumsi}{6}
\item C'est Marie qui est aim\'ee par Jean \label{ex:sortie-jam6}
\item C'est Marie qui est aim\'ee de Jean \label{ex:sortie-jam7}
\item Marie, Jean l'aime \label{ex:sortie-jam8}
\item Marie, c'est Jean qui l'aime \label{ex:sortie-jam9}
\item Jean, c'est Marie qu'il aime \label{ex:sortie-jam10}
}
\end{minipage}
\end{tabular}
}

Dans cet article, nous présentons un réalisateur de surface (\geni )
qui combine une méthode symbolique de sélection de paraphrases avec
une grammaire réversible. En outre, le réalisateur est paramétrable et
peut être utilisé soit en mode déterministe (une seule solution
produite), soit en mode non déterministe (toutes les paraphrases
associées par la grammaire à la sémantique d'entrée sont produites). 

L'utilisation de méthodes symboliques pour guider le choix de la
paraphrase permet de prendre en compte les facteurs contextuels
imposés par un système de génération : la réalisation produite est une
réalisation {\it appropriée} pour un contexte donné plutôt que la
réalisation la plus fréquente dans l'usage général représenté par un
corpus d'apprentissage. 

L'utilisation d'une grammaire réversible a plusieurs
avantages. 

Premièrement, elle permet d'utiliser le même lexique et la même
grammaire pour l'analyse et pour la réalisation. Etant donnée la
difficulté de développer de telles ressources, la question de la
réutilisabilité est un point non trivial.

Deuxièmement, comme l'illustre la Redwood Lingo Treebank \cite{VelOep06}, la
réversibilité permet de créer rapidement de très grandes suites de
tests pour la réalisation: il suffit pour ce faire d'analyser des
phrases, de sélectionner parmi les sorties produites l'analyse
correspondant à l'interprétation de l'entrée et d'utiliser la
représentation sémantique associée comme entrée pour le réalisateur.
Par comparaison, les plus grandes suites de tests distribuées
actuellement avec les réalisateurs existants soit sont de taille
restreinte (500 phrases distinces pour \surge , 210 pour \kpml ), soit
exigent de développer un module de transformation permettant de créer
à partir d'un corpus arboré un format d'entrée adapté à la réalisation
\cite{Callaway-Eval-IJCAI-03}.

Troisièmement, la réversibilité permet de mieux mesurer la couverture
et le pouvoir paraphrastique du réalisateur. La couverture est testée
par une analyse doublée d'une phase de réalisation (la phrase d'entrée
peut-elle être à la fois analysée et réalisée par le système?). Le
pouvoir paraphrastique pourra être mesuré en utilisant le réalisateur
en mode non déterministe (toutes les paraphrases possibles sont
produites) et en identifiant les sorties correctes produites par le
réalisateur pour une entrée donnée.

Quatrièmement, une grammaire réversible peut être utilisée à la fois
pour la réalisation et pour son inverse à savoir, la construction
sémantique (i.e., la construction pour une phrase de sa ou ses
représentations sémantique(s)). Si, comme nous cherchons à le garantir
dans \geni , le réalisateur a un bon pouvoir paraphrastique, cela a
pour effet que la grammaire peut être utilisée à la fois pour générer
et pour détecter les paraphrases.

L'article est structuré de la façon suivante. Nous commençons par
présenter la grammaire (section \ref{sec:grammaire}) et l'algorithme
de base (section \ref{subsec:algobase}). Ce premier algorithme est un
algorithme non déterministe qui produit l'ensemble des paraphrases
associées par la grammaire à une représentation sémantique
donnée. Nous montrons ensuite comment une méthode de paramétrisation
des entrées permet de restreindre la réalisation aux seules paraphrases
respectant les critères syntaxico-sémantiques spécifiés par les
paramètres donnés en entrée (section \ref{subsec:selection}).  La section
\ref{sec:evaluation} présente des résultats chiffrés donnant une
indication de la couverture et du pouvoir paraphrastique de \geni\
et la section \ref{sec:comparaison} compare l'approche proposée
avec les travaux connexes. La section \ref{sec:conclusion} conclut
avec des pointeurs pour des recherches futures.

\section{La grammaire} 
\label{sec:grammaire}

\paragraph{Formalisme.} La grammaire utilisée est une grammaire d'arbres adjoints
lexicalisée basée sur l'unification (FLTAG, \cite{vijayshanker1988fsb}). Une
FLTAG comprend un ensemble d'arbres élémentaires et deux opérations
permettant de combiner ces arbres entre eux, l'opération de
substitution et l'opération d'adjonction. Les arbres résultant d'une
de ces opérations sont appelés <<arbres dérivés>>.

Les arbres élémentaires sont lexicalisés, c'est-à-dire qu'ils sont
explicitement associés avec un lemme ou une forme fléchie. Leurs
noeuds sont étiquetés par deux structures de traits appelées {\sc Top}
et {\sc Bottom}. Un arbre élémentaire est soit initial, soit
auxiliaire. Un arbre initial est un arbre dont les noeuds feuilles
sont soit des noeuds terminaux, soit des noeuds dit de substitution
(marqués par $\downarrow$). Un arbre auxiliaire est un arbre dont l'un
des noeuds feuilles est un noeud <<pied>> (marqué par $\star$)
étiqueté par la même catégorie que le noeud racine.

L'opération de substitution permet d'insérer un arbre élémentaire ou
dérivé $\tau_\delta$ dans un arbre initial $\tau_{\alpha}$ : le noeud
racine de $\tau_\delta$ est alors identifié avec un noeud de
substitution dans $\tau_{\alpha}$ et les traits {\sc Top} sont unifiés
({\it Top$_{\tau_{\alpha}}$ = Top$_{\tau_{\delta}}$}). L'opération
d'adjonction permet d'insérer un arbre auxiliaire $\tau_\beta$ dans un
arbre quelconque $\tau_\alpha$ à un noeud $n$ : les traits {\sc
Top$_n$} et {\sc Bottom$_n$} du noeud $n$ où se fait l'adjonction sont
alors unifiés avec les traits {\sc Top} du noeud racine de l'arbre
auxiliaire et les traits {\sc Bottom} de son noeud pied respectivement
({\it Top$_n$ = Top$_{Root_{\tau_\beta}}$} et {\it Bottom$_n$ =
Bottom$_{Foot_{\tau_\beta}}$}). En fin de dérivation, les traits {\sc
Top} et {\sc Bottom} de chaque noeud de l'arbre dérivé produit sont
unifiés.

\paragraph{Grammaire et méta-grammaire.} La grammaire TAG utilisée est
une grammaire produite par compilation à partir d'une spécification
plus abstraite appelée, {\it metagrammaire}. Dans cette métagrammaire,
un arbre élémentaire est défini par la combinaison d'un ou de
plusieurs fragments d'arbres et chaque fragment d'arbre encapsule une
caractérisque linguistique spécifique. Par exemple, tout arbre verbal
dont le sujet est un sujet nominal canonique fera intervenir le
fragment d'arbre {\sc SujetCanonique}. Plus généralement, chaque arbre
élémentaire est associé par le processus de compilation à un {\it
profil} listant l'ensemble des noms de fragments d'arbres ayant
participé à sa construction. Comme l'illustre le profil de l'arbre
donné en Figure \ref{fig:profil}, le profil de chaque arbre donne
ainsi des informations sur ses caractéristiques linguistiques. Or les
réalisateurs TAG utilisent souvent ce type d'information pour guider
la réalisation (cf. \cite{yangEtAl91,danlos1998gtf}) mais
l'association est faite de manière manuelle; Dans \geni , ces
informations sont automatiquement associés avec chaque arbre
élémentaire par le compilateur de métagrammaire.

\begin{figure}[htbp]
%\begin{figure}[ht]
\begin{center}
{\footnotesize
\vspace{-1em}
\begin{tabular}{cc}
% --------------------------------------------- dort
\hspace{-0.25em}
\begin{tabular}{ccc}
\multicolumn{2}{c}{\node{s}{S}}&\\[1.5ex]
% -----
\node{np1}{N$\downarrow^{x_1}$}
&\node{v1}{V} \\[1.5ex]
% -----
&\node{sleep}{dort} &\\
% -----
&\multicolumn{2}{l}{\footnotesize \it dort(x$_1$)}
\end{tabular}
\nodeconnect{s}{np1} \nodeconnect{s}{v1}
\nodeconnect{v1}{sleep}
% ---------------------------------------------
&
\begin{minipage}{3cm}
{\sc SujetCanonique}\\
{\sc VerbeActif}
\end{minipage}
\end{tabular}
}
\caption{\label{fig:profil} Profil d'un arbre}
\label{fig:profil}
\end{center}
\end{figure}

\paragraph{Interface Syntaxe/Sémantique.} Dans la grammaire d'arbres adjoints utilisée, le lien entre structure syntaxique et représentation sémantique se fait de la façon illustrée 
par la figure \ref{fig:jeancourtsouvent}. Chaque arbre élémentaire est
associé avec une représentation sémantique où les arguments manquants
sont des variables d'unification. Ces variables apparaissent en outre
sur certains noeuds de l'arbre et sont instantiées par le biais des
substitutions et des adjonctions\footnote{Pour plus de détails sur le
calcul sémantique utilisé, cf. \cite{gardent2003scf}.}. Ainsi, dans la
dérivation de {\it Jean court souvent} illustré ci-dessous, $j$ unifie
avec $s$ et $r$ avec $x$ si bien que la représentation sémantique
finale est {\small {\it nom(j,jean), courir(r,j), souvent(r)}}.

%\begin{wrapfigure}[8]{r}{5.5cm}
%\vspace*{-.3cm}

\begin{figure}[htbp]
\begin{center}
{\small
% ------------------------------------------ john
\begin{tabular}{c}
$\,$\\[1.5ex]
\node{np3}{N$_{j}$}\\[1.5ex]
\node{jon}{Jean}\\[1ex]
{\footnotesize {\it nom(j,jean)}}
\end{tabular}
\nodeconnect{np3}{jon}
% ------------------------------------------ runs
\hspace{-2em}
\begin{tabular}{cc}
\multicolumn{2}{c}{\node{r1}{S}} \\[1.5ex]
\node{r1.1}{N$\downarrow^{s}$} &
\node{r1.2}{V$^{r}$} \\[1.5ex]
&
\node{r1.2.1}{court} \\ [1ex]
&
{\footnotesize {\it courir(r,s)}} \\
\end{tabular}
\nodeconnect{r1}{r1.1}
\nodeconnect{r1}{r1.2}
\nodeconnect{r1.2}{r1.2.1}
% ------------------------------------------ often
\begin{tabular}{cc}
\multicolumn{2}{c}{\node{f1}{V$^{x}$}} \\[1.5ex]
\node{f1.1}{V*} &
\node{f1.2}{Adv}\\[1.5ex]
& \node{f1.2.1}{souvent} \\[1ex]
&
{\footnotesize {\it souvent(x)}}
\end{tabular}
\nodeconnect{f1}{f1.1}
\nodeconnect{f1}{f1.2}
\nodeconnect{f1.2}{f1.2.1}
% ---------------------------------------------
}
{\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  nom(j,jean), courir(r,j), souvent(r)}}
%\vspace{-1em}

\caption{\label{fig:flat} ``Jean court souvent''}
\label{fig:jeancourtsouvent}
\end{center} 
\end{figure} 

\paragraph{Couverture.} La grammaire \cite{crabbe2004mr} couvre la
grammaire noyau du français décrite dans \cite{abeille2002ged} c'est-à-dire,
l'ensemble des cadres syntaxiques de base qui y sont listés
et pour chacun de ces cadres, l'ensemble des redistributions (actif,
passif, moyen, neutre, réflexivisation, impersonnel,
passif-impersonnel) et des réalisations d'arguments permises
(cliticisation, extraction, ommission, variations d'ordre).

%Au plan sémantique, le calcul des représentations sémantiques suit les
%principes énoncés dans \cite{gardent2003scf} La grammaire a en
%outre la particularité d'être paraphrastique \cite{gardent2004pg}
%au sens où elle associe à deux paraphrases la même représentation
%sémantique. Elle diffère ainsi de grammaires sémantiques existantes
%qui ne prennent pas en compte les phénomènes
%paraphrastiques (même grammaticaux) et pourront associer à deux
%paraphrases très "proches" des représentations sémantiques très
%différentes. La grammaire HPSG de \cite{copestakeFlickinger00} par
%exemple associe aux paraphrases <<The person who drives the car is
%mad.>> et <<The driver of the car is mad.>> les représentations
%sémantiques divergentes suivantes :

%\enumsentence{\label{e1}
%a. the(x, person(x) $\wedge$ the(y, car(y) $\wedge$ drive(e,x,y)
%$\wedge$ mad(x)))\\
%b. the(y, car(y) $\wedge$ the(x, driver(x,y) $\wedge$ of(x,y))
%$\wedge$ mad(x))}

%Parce qu'elle prête attention aux phénomènes paraphrastiques, la
%grammaire utilisée par GenI engendre pour chaque représentation
%sémantique un ensemble maximal de paraphrases : alors que la grammaire
%HPSG ne pourra générer à partir d'une des deux représentations
%sémantiques ci-dessus que la réalisation correspondante, GenI
%engendrera à partir d'une représentation unique, les deux
%réalisations. Les variations possibles de la représentation sémantique
%(le choix entre \ref{e1}a et \ref{e1}b par exemple) sont traités
%pendant la lexicalisation par un mécanisme d'inférence.

\section{Le réalisateur \geni }
\label{sec:algo}

Nous commençons par décrire l'algorithme de base utilisé par \geni
. Cet algorithme est un algorithme non déterministe permettant de
générer l'ensemble des paraphrases associées par la grammaire à une
entrée sémantique telle que celle donnée en
(\ref{ex:entree-jam}). Nous montrons ensuite comment cet algorithme
peut être modifié pour assurer le déterminisme et générer parmi
l'ensemble des paraphrases possibles, la paraphrase respectant les
contraintes placées sur une verbalisation par un contexte de
génération donné.

\subsection{Générer toutes les paraphrases} 
\label{subsec:algobase}

L'algorithme de base est un algorithme tabulaire \cite{kay1996cg}
ascendant optimisé pour les grammaires d'arbres adjoints. Une
spécification détaillée de l'algorithme et des optimisations déployées
est donnée dans \cite{gardent2005gas}. Par manque de place, nous nous
contentons ici d'illustrer son fonctionnement par un exemple.

Supposons que la sémantique donnée en entrée soit $
 \semexpr{courir(r,j),nom(j,jean),souvent(r)}$.  L'algorithme procède
 de la façon suivante. Dans un premier temps ({\bf phase de sélection
 lexicale}), les arbres élémentaires dont la sémantique subsume une
 partie de l'entrée sont sélectionnés. Pour notre exemple, les arbres
 sélectionnés seront (entre autre) les arbres de {\it Jean, court} et
 {\it souvent} (cf. Figure \ref{fig:jeancourtsouvent}). 
La deuxième étape ({\bf phase de substitution}) consiste à explorer
systématiquement les possibilités de combinaisons par
substitution. Pour l'exemple considéré, cette exploration permettra de
substituer l'arbre pour {\it Jean} dans l'arbre pour {\it court}
(cf. Figure \ref{fig:jeancourtsouvent}). 
La troisième étape ({\bf phase d'adjonction})
permet de combiner les arbres produits par adjonction. C'est à ce
stade que l'arbre pour {\it souvent} sera adjoint à l'arbre dérivé
pour {\it Jean court}.
En dernier ressort ({\bf phase d'extraction}), les chaînes étiquettant
les items couvrant la sémantique donnée en entrée sont produites en
l'occurrence : {\it Jean court souvent}.


\subsection{Générer une seule paraphrase} 
\label{subsec:selection}

L'algorithme présenté dans la section précédente est non déterministe
et produit, pour une entrée sémantique donnée, l'ensemble des
paraphrases associées par la grammaire à cette entrée. L'entrée
(\ref{ex:entree-jam}) par exemple, permet la réalisation de l'ensemble
des paraphrases listées en
(\ref{ex:sortie-jam1}-\ref{ex:sortie-jam10}).

Pour une utilisation au sein d'un système de génération, il est
nécessaire de pouvoir contraindre l'algorithme de facon à pouvoir
sélectionner, parmi l'ensemble des paraphrases possibles, la
paraphrase appropriée au contexte considéré.  Nous montrons maintenant
comment l'entrée sémantique de \geni\ peut être enrichie pour guider
l'algorithme dans ses choix et assurer le déterminisme.

\paragraph{Au plus une verbalisation.}

Dans l'algorithme présenté en section \ref{sec:algo}, le non
déterminisme provient principalement\footnote{Une seconde source de
non déterminisme provient des modificateurs qui peuvent souvent
s'adjoindre dans des ordres différents ({\it l'homme jeune et grand,
l'homme grand et jeune}). Ce type de non déterminisme est traité dans
la phase d'adjonction en regroupant les modificateurs d'une même
entité et en imposant un ordre unique d'adjonction en cas
d'ambiguité.} de l'ambiguité lexicale : pour chaque litéral $l$ dans
l'entrée, il y a généralement plus d'un arbre élémentaire sélectionné
par la phase de sélection lexicale. Ainsi pour chaque entrée
sémantique, la sortie de \geni\ est donnée par l'ensemble des
combinaisons d'arbres élémentaires couvrant la sémantique d'entrée et
dont la combinaison par substitution ou adjonction est permise par la
grammaire.

Pour permettre le déterminisme, nous associons à chaque littéral un
{\it identifiant d'arbre}. Comme nous l'avons vu en section
\ref{sec:grammaire}, la grammaire utilisée est produite par un
processus de compilation qui associe à chaque arbre élémentaire un
profil résumant ses caractéristiques linguistiques. Parce que ce
profil recense l'ensemble des fragments d'arbres utilisés pour
construire un arbre donné et parce que chaque arbre diffère d'un autre
par au moins un fragment d'arbre dans son profil, le profil de chaque
arbre élémentaire est un identifiant pour cet arbre\footnote{Il s'agit
là d'une simplification. Dans certains cas (peu nombreux), deux arbres
élémentaires distincts ont le même profil. Nous revenons sur ce point
en section \ref{sec:evaluation}.}. Nous utilisons cette caractéristique de la
grammaire pour guider la réalisation et assurer son déterminisme de la
facon suivante :

{\small
\begin{enumerate} 
\item Chaque litéral $l_i$ dans l'entrée est associée avec un identifiant
  d'arbre $A_i$. Cet identifiant est un profil simplifié ne prenant en
  compte que les informations utiles pour la génération et préservant
  l'unicité de l'arbre identifié.
\item Pendant la réalisation, pour chaque paire $l_i : A_i$ dans
  l'entrée enrichie, la sélection lexicale est restreinte aux arbres
  dont la sémantique subsume $l_i$ {\it et dont le profil simplifié
  est }$A_i$. 
\end{enumerate}}

Puisque chaque litéral est associé avec un identifiant d'arbre et
chaque identifiant d'arbre identifie un arbre unique, le réalisateur
produira {\it au plus} une phrase. Les exemples
(\ref{ex:enriched-input1}-\ref{ex:enriched-input3})
illustrent le type de contraintes mises en jeu par \geni .

{\small
\eenumsentence{
\item
{\it l$_j$:jean(j)/NomPropre l$_a$:aimer(e,j,m)/[SujetCanoniqueNominal,
    VerbeActif, ObjetCanoniqueNominal] l$_m$:marie(m)/NomPropre}
\label{ex:enriched-input1}
\\
Jean aime Marie
\\
\sout{Marie est aim\'ee de Jean, C'est Jean qui aime Marie, etc. }
\item
{\it l$_c$:le(c)/Det l$_c$:chien(c)/NomCommun
  l$_d$:dormir(e1,c)/SujetRelatif \\
l$_r$:ronfler(e2,c)/SujetCanoniqueNominal}
\label{ex:enriched-input2}
\\
Le chien qui dort ronfle
\\
\sout{Le chien qui ronfle dort}
\item
{\it l$_j$:jean(j)/ProperName
  l$_p$:promettre(e1,j,m,e2)/[SujetCanoniqueNominal, VerbeActif,
    ObjetCompletive] l$_m$:marie(m)/ProperName l$_{e2}$:partir(e2,j)/VerbeInfinitif}
\label{ex:enriched-input3}
\\
Jean promet \`a Marie de partir
\\
\sout{Jean promet \`a Marie qu'il partira}
}}

\paragraph{Au moins une verbalisation.}
Si une entrée enrichie permet de limiter la réalisation à une
verbalisation maximum, elle ne garantit pas une solution au sens où la
combinaison d'identifiants d'arbres choisie peut ne pas être
réalisable. Mais comment vérifier la satisfiabilité d'une entrée sans
pour autant tenter de la réaliser?  Les systèmes existants donnent
trois grands types de réponses à cette question.

Une première possibilité est de construire simultanément entrée
enrichie et verbalisation. C'est le cas en particulier, des
réalisateurs basés sur les grammaires systémiques (\kpml
\cite{matthiessen1991tga}) où la réalisation coincide avec la traversée d'un
réseau systémique permettant d'associer à un contenu sémantique
(dimension idéationnelle dans la terminologie systémique), une
description syntaxique et fonctionnelle. 

Une deuxième possibilité consiste à vérifier la validité de l'entrée
sur un critère partiel de bonne formation. Par exemple, \realpro\
\cite{lavoie1997rfp} prend pour entrée un structure syntaxique profonde de
la théorie Sens-Texte \cite{melvcuk1970tfm} et \surge\ \cite{elhadad1999scp} une
description fonctionnelle des grammaires fonctionnelles
d'unification. Dans les deux cas, l'entrée n'est pas nécessairement
satisfiable puisqu'elle doit être validée par l'ensemble de la
théorie. Dans la théorie sens-texte, la structure syntaxique profonde
doit, pour être réalisable, pouvoir être projetée successivement en
une structure syntactique de surface, une structure morphologique et
une structure phonétique. Dans \surge , l'entrée n'est réalisable que
si elle permet une traversée complete de la grammaire du noeud racine
aux noeuds lexicaux instanciant la sémantique d'entrée. 

Une troisième possibilité consiste à procéder de façon incrémentale et
à faire des choix locaux (algorithme gourmand) guidés par les
contraintes introduites par les choix faits. C'est le cas en
particulier de l'algorithme semi-récursif basé sur les grammaires
d'arbres adjoints décrit dans \cite{danlos1998gtf} : à chaque étape de la
réalisation, un arbre unique est sélectionné et les contraintes
introduites par cet arbre sont utilisées pour contraindre le choix
des arbres restant à sélectionner. En cas d'échec, l'algorithme fait
un retour arrière.

Nous adoptons une stratégie mixte où la technique dite de {\it filtrage par
  polarités} est utilisée pour :

\begin{enumerate}
\item effectuer une vérification de la validité de l'entrée enrichie 
\item proposer une alternative en cas d'échec de cette vérification
\item proposer une entrée enrichie par défaut en cas d´échec de
  réalisation
\end{enumerate}

Le filtrage par polarités s'inspire des travaux de
\cite{bonfante2003ase,koller2002gdp} et vise à détecter les
combinaisons d'arbres élémentaires où besoins et ressources
syntaxico-sémantiques échouent à s'annuler. 
Plus spécifiquement, l'idée est de vérifier si pour une entrée donnée,
l'ensemble d'arbres sélectionnés est tel que {\it
chaque noeud de substitution et chaque noeud pied peut être associé
avec exactement un arbre de la catégorie syntaxique et de l'index
sémantique approprié.}\footnote{Les restrictions d'espace nous empêche
  d'expliciter ici la méthode de filtrage par polarité. Celle ci est
  cependant détaillée dans \cite{gardent2005gas}.}

Nous utilisons le filtrage par polarité pour filtrer les entrées
enrichies non satisfiables (i.e., des entrées dont la polarité est non
nulle) mais également pour proposer une entrée alternative en cas de
détection d'entrée non satisfiable. Dans ce cas, l'entrée enrichie est
dépouillée de ses identifiants d'arbre et l'algorithme non
déterministe est utilisé avec additionellement une étape de filtrage
par polarité (introduite entre la phase de sélection lexicale et celle
de substitution). Les combinaisons d'arbres à polarités neutres (i.e.,
les combinaisons d'arbres où besoins et ressources
syntaxico-sémantiques s'annulent) sont ensuite comparées à l'entrée
enrichie initiale et la combinaison la plus similaire à cette entrée
est alors proposée en alternative. La similarité entre deux
combinaisons d'arbres est mesurée par le nombre d'identifiant communs
entre ces deux combinaisons : plus le nombre d'identifiants commun aux
deux sélections est grand, plus les sélections sont similaires. Si
plusieurs sélections sont également similaires, un choix non
déterministe est fait.

Enfin il est malgré tout possible qu'un ensemble d'arbres à polarité neutre
soit non satisfiable\footnote{Le filtrage par polarité permet de
  détecter la non satisfiabilité d'une combinaisons d'arbres pas d'assurer
  sa satisfiabilité.}. Dans ce cas, l'algorithme utilise un
enrichissement de la sémantique d'entrée par défaut qui permet de
générer une verbalisation <<canonique>> de cette sémantique.

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

Afin d'évaluer d'une part, le pouvoir paraphrastique du réalisateur et
d'autre part, l'impact des annotations de contrôle sur le
non-déterminisme, nous avons utilisé une suite de tests
graduée. Cette suite a été construite en (i) analysant un ensemble de
phrases et (ii) sélectionnant pour chaque phrase la représentation
sémantique correcte\footnote{L'analyseur peut donner plusieurs
analyses et donc souvent plusieurs représentations sémantiques dont
certaines représentent correctement le sens de la phrase analysée ,
d'autres non.}. Le résultat est une suite de 80 représentations
sémantiques choisies pour illustrer les différents types de
paraphrases grammaticales décrites par la grammaire utilisée c-à-d,

\begin{itemize}
\item les variations grammaticales dans la réalisation des arguments
  (clivés, cliticisation, extraction, inversion du sujet, etc.) et la
  forme du verbe (passive/active, impersonnal, etc.)
\item les variations dans la réalisation des modificateurs (anté- vs
  post-posés, adjectif vs subordonnée relative, épithète vs. attribut,
  etc.)
\item les variations permises par une équivalence
  morpho-dérivationnelle (Ex. arrivée/arriver)
\end{itemize}

\begin{figure}
\begin{center}
\includegraphics[angle=90,height=5cm,width=0.5\textwidth]{everything-num-paraphrases}
\caption{Distribution du taux de variation paraphrastique}
\label{fig:paraphrases}
\end{center}
\end{figure}

Les 80 cas sélectionnés donnent lieu à la génération par \geni\ de 1 528 phrases
distinctes soit un taux de paraphrases moyen par entrée de 18 avec une
variation allant de 1 à plus de 50 paraphrases par représentation
sémantique. La Figure \ref{fig:paraphrases} donne une description plus
détaillée de la distribution du taux de variation
paraphrastique. Plus généralement, 42\% des phrases avec un verbe fini ont
une à 3 paraphrases (cas des verbes intransitifs), 44\% 4 à 28
paraphrases (verbes prenant deux arguments) et 13\% acceptent plus de
30 paraphrases (verbes à trois arguments). Pour les phrases contenant
deux verbes finis, le ratio est de 5\% des cas ayant 1 à 3
paraphrases, 36\% des cas ayant entre 4 et 14 paraphrases et 59\% plus
de 14 paraphrases. Enfin les phrases contenant plus de 3 verbes finis
acceptent toutes plus de 20 paraphrases.

Afin de vérifier que l'utilisation des profils suffit à assurer le
déterminisme (cf. section \ref{subsec:selection}), nous avons calculé
le nombre de cas où deux paraphrases d'un même contenu partagent le
même profil. Pour ce faire, nous avons étiqueté de façon automatique
les 1 528 paraphrases produites par \geni\ à partir de la suite de
test, avec leur profils (le profil d'une paraphrase est l'ensemble des
profils associés aux arbres élémentaires utilisés pour construire
l'arbre dérivé de cette paraphrase). Nous avons ensuite comparé, pour
chaque entrée de la suite de tests, les profils de toutes les paires
de paraphrases correspondantes et compté le nombre de fois où une
paire de paraphrases partage le même profil.

Cette manipulation montre que pour les 1 528 paraphrases considérées,
le profil échoue à refléter la différence entre deux paraphrases dans
moins de 1\% des cas. L'analyse des données fautives révèle que les
cas posant problème sont les paires paraphrastiques impliquant
uniquement (i) une variation d'ordre des arguments (Ex. {\it Jean
donne une pomme à Marie / Jean donne à Marie une pomme }) ou (2) une
variation de position pour un modificateur (Ex. {\it Jean donne ce
soir une pomme à Marie /Jean donne une pomme ce soir à Marie / Jean
donne une pomme à Marie ce soir}). Le premier cas peut être résolu en
modifiant la grammaire de façon à expliciter la différence dans le
profil des arbres élémentaires correspondant, le second en imposant un
ordre canonique sur l'adjonction des modificateurs.

\section{Discussion et comparaison avec travaux connexes}
\label{sec:comparaison}

\geni\ diffère des réalisateurs existants en ce qu'il combine
l'utilisation d'une grammaire réversible avec un mécanisme symbolique
de sélection des paraphrases.

Ainsi, les réalisateurs utilisant une grammaire réversible utilisent
généralement des méthodes statistiques pour choisir parmi l'ensemble
des paraphrases associées à un sens par la grammaire, la paraphrase la
plus fréquente plutôt que la paraphrase appropriée à un contexte de
génération donné. Ils sont de ce fait mal adaptés à une utilisation
dans des scénarios de génération exigeant un bon pouvoir
paraphrastique et sont plutôt mis en jeu soit dans des systèmes de
traduction \cite{carroll2005her} soit dans des scénarios de génération
où les textes à produire sont fortement stéréotypés et où la
paraphrase la plus fréquente est aussi la paraphrase la plus
appropriée dans une majorité des cas \cite{white2004rcc}.

Par ailleurs, les réalisateurs utilisant un mécanisme symbolique de
sélection des paraphrases
\cite{danlos1998gtf,matthiessen1991tga,elhadad1999scp,lavoie1997rfp}
mettent habituellement en jeu des grammaires qui ne sont pas
réversibles c'est-à-dire des grammaires qui ne peuvent pas être
exploitées à la fois pour associer un sens à un texte (analyse) et
pour verbaliser un sens donné (réalisation). Or comme nous l'avons
mentionné dans l'introduction, l'utilisation de la grammaire en
analyse comme en réalisation est un point important. Outre qu'elle
permet de minimiser l'effort de développement sur la grammaire (chaque
modification apportée à la grammaire ou au lexique bénéficie à la fois
à l'analyse et à la génération), cette dualité permet un meilleur
contrôle de la qualité et de la couverture de la grammaire puisque
l'analyseur permet de détecter la sous-génération (i.e., la non
génération de phrases grammaticales) et le réalisateur la
sur-génération (i.e., la génération de phrases agrammaticales). Enfin,
l'utilisation en mode double de la grammaire permet de produire
automatiquement des quantités arbitraires d'entrées pour le
réalisateur et ainsi de mieux tester son pouvoir paraphrastique. Par
comparaison, l'entrée des réalisateurs non réversibles est
généralement produite soit par un système de génération, soit
manuellement ce qui rend difficile une évaluation précise de leur
couverture et pouvoir paraphrastique.

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

En résumé, \geni\ est un réalisateur de surface basé sur une grammaire
d'arbres adjoints pour le français qui présente les propriétés
suivantes :

\begin{itemize}
\small
\item \geni\ peut être utilisé en mode déterministe (une paraphrase)
  ou non-déterministe (toutes les paraphrases)
\item \geni\ utilise une grammaire et un lexique réversible
\item \geni\ utilise une grammaire qui associe aux paraphrases
  grammaticales une même sémantique -- ceci permet, grâce à la
  réversibilité, à la fois un bon pouvoir paraphrastique
  %(production de nombreuses paraphrases)
  et la détection de paraphrases
  %(par l'analyse et la construction sémantique)
\item \geni\ est disponible en libre source
(\url{http://trac.loria.fr/~geni}).
\end{itemize}


Outre les phénomènes décrits en section \ref{sec:evaluation}, la
grammaire utilisée par \geni\ est essentiellement la grammaire
spécifiée par \cite{crabbe05} augmentée avec une dimension sémantique
\cite{gardent06a}. Elle couvre donc l'essentiel de la TSNLP et des
phénomènes décrit dans \cite{abeille2002ged}.
Le travail futur inclut (i) un passage à grande échelle par
l'extension de la grammaire et du lexique et (ii) l'utilisation du
réalisateur pour réduire la sur-génération.

%%================================================================


%%================================================================
%\section*{Remerciements}


%%================================================================
%% Note : si l'on préfère éviter de factoriser les crossrefs :
%% bibtex -min-crossrefs 99 taln-exemple
%%================================================================

\bibliographystyle{taln2002}
\bibliography{taln07-geni}

%%================================================================


\end{document}
