Analyse en d�pendances � l'aide des grammaires d'interaction
Jonathan Marchand\fup{1} \quad Bruno Guillaume\fup{2} \quad Guy Perrier\fup{1}
(1) LORIA~/~Universit� Nancy~2
(2) LORIA~/~INRIA Nancy Grand-Est
This article proposes a method to extract dependency structures from phrase-structure level parsing with Interaction Grammars. Interaction Grammars are a formalism which expresses interactions among words using a polarity system. Syntactical composition is led by the saturation of polarities. Interactions take place between constituents, but as grammars are lexicalized, these interactions can be translated at the level of words. Dependency relations are extracted from the parsing process: every dependency is the consequence of a polarity saturation. The dependency relations we obtain can be seen as a refinement of the usual dependency tree. Generally speaking, this work sheds new light on links between phrase structure and dependency parsing.
taln09.tex
%%% Exemple de source LaTeX pour un article soumis � TALN
\documentclass[12pt,a4paper,twoside]{article}

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

\usepackage{graphicx}

% faire les \usepackage dont vous avez besoin avant le
% \usepackage{taln2009}

\usepackage{taln2009Poster} 
\usepackage{wrapfig}
%% \ExecuteOptions{french} 
%% \ProcessOptions 
\usepackage[frenchb]{babel}
\newcommand{\fup}[1]{\up{#1}}

%%\setlength{\headwidth}{\textwidth}
\fancyhead[LO]{Analyse en d�pendances � l'aide des grammaires
d'interaction}
\fancyhead[RE]{Jonathan Marchand, Bruno Guillaume, Guy Perrier} 

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

\newcommand{\french}[1]{{\emph{``#1''}}}

\newcommand{\node}[1]{\texttt{#1}}

\begin{document}

\title{Analyse en d�pendances � l'aide des grammaires d'interaction}

\author{Jonathan Marchand\fup{1} 
  \quad Bruno Guillaume\fup{2}
  \quad Guy Perrier\fup{1}\\
  (1) LORIA~/~Universit� Nancy~2\\ 
  (2) LORIA~/~INRIA Nancy Grand-Est \\ 
  pr�nom.nom@loria.fr\\ 
} 

\date{}

\maketitle

\resume{
Cet article propose une m�thode pour extraire une analyse en
d�pendances d'un �nonc� � partir de son analyse en constituants avec
les grammaires d'interaction. Les grammaires d'interaction sont un
formalisme grammatical qui exprime l'interaction entre les mots �
l'aide d'un syst�me de polarit�s. Le m�canisme de composition
syntaxique est r�gi par la saturation des polarit�s. Les interactions
s'effectuent entre les constituants, mais les grammaires �tant
lexicalis�es, ces interactions peuvent se traduire sur les mots. La
saturation des polarit�s lors de l'analyse syntaxique d'un �nonc�
permet d'extraire des relations de d�pendances entre les mots, chaque
d�pendance �tant r�alis�e par une saturation. Les structures de
d�pendances ainsi obtenues peuvent �tre vues comme un raffinement de
l'analyse habituellement effectu�e sous forme d'arbre de
d�pendance. Plus g�n�ralement, ce travail apporte un �clairage nouveau
sur les liens entre analyse en constituants et analyse en d�pendances.
}

\abstract{This article proposes a method to extract dependency
  structures from phrase-structure level parsing with Interaction
  Grammars. Interaction Grammars are a formalism which expresses
  interactions among words using a polarity system. Syntactical
  composition is led by the saturation of polarities. Interactions
  take place between constituents, but as grammars are lexicalized,
  these interactions can be translated at the level of words. Dependency
  relations are extracted from the parsing process: every dependency
  is the consequence of a polarity saturation.
  The dependency relations we obtain can be seen as a refinement of
  the usual dependency tree. Generally speaking, this work sheds new
  light on links between phrase structure and dependency parsing. 
 }



\motsClefs{Analyse syntaxique, grammaires de d�pendances, grammaires
d'interaction, polarit�}
{Syntactic analysis, dependency grammars, interaction grammars, polarity}

%% Aller � la page suivante si n�cessaire
\newpage
%%================================================================
\section{Introduction}
Les grammaires de constituants et les grammaires de d�pendances sont
souvent pr�sent�es comme orthogonales~: les premi�res organisent les
groupes de mots en syntagmes alors que les secondes mettent la
d�pendance entre mots au centre de la structure syntaxique. Avec les
grammaires de constituants lexicalis�es, telles que les grammaires
d'arbres adjoints (TAG) et les grammaires cat�gorielles (CG), o�
chaque �l�ment de la grammaire est associ� � un mot, la composition
syntaxique lors de l'analyse met en �vidence des liens entre les
mots. Ces liens pr�sentent des similitudes avec les relations de
d�pendances et ont fait l'objet de diff�rentes �tudes.

A.~Dikovsky et L.~Modina ont �tudi� du point de vue formel le passage
d'une analyse en constituants � une analyse en d�pendances et vice
versa~\cite{dikovsky00}. O.~Rambow et A.~Joshi ont expliqu� comment
retrouver une analyse en d�pendances � partir d'une analyse dans les
TAG o� les substitutions et les adjonctions sont vues comme des
relations de d�pendances entre les mots~\cite{rambow94}. Enfin,
l'article~\cite{Clark02} propose une m�thode similaire pour les grammaires
cat�gorielles combinatoires o� l'application des r�gles combinatoires
donne lieu � des relations de d�pendances entre les mots.

Les grammaires d'interaction (IG) sont des grammaires de constituants
lexicalis�es qui �tendent par un syst�me de polarit�s plus riche le
syst�me besoins/ressources employ� dans les grammaires cat�gorielles.
Dans cet article, nous g�n�ralisons, les r�sultats~\cite{Clark02}
cit�s plus haut pour les CG au cas des IG, en r�visant la m�thode~: en
effet, cette derni�re impose d'�tendre les entr�es lexicales avec des
marqueurs pour aider � la construction des d�pendances lors de
l'analyse, et produit trop de d�pendances, alors que notre m�thode
s'appuie plus simplement sur le lien entre polarit�s et d�pendances.

Dans la section~\ref{sec-gi}, les IG sont pr�sent�es et illustr�es par
un exemple. La section~\ref{sec-analyse} d�crit la m�thode
d'extraction des d�pendances � partir d'une analyse avec une IG. Finalement,
dans la section~\ref{sec-structures}, nous �tudions les structures de
d�pendances obtenues et nous mettons en perspective avec d'autres travaux.

%======================================================================
\section{Les grammaires d'interaction}
\label{sec-gi}
Les grammaires d'interaction \cite{Per2003} sont un formalisme
grammatical s'appuyant sur la notion de \textit{description
  d'arbres}. Cette notion a �t� introduite par M.~Marcus, D.~Hindle et
M.~Fleck en 1983 \cite{Marcus83}, et K.~Vijay-Shanker l'a utilis�e
pour repr�senter de fa�on monotone l'op�ration d'adjonction des
TAG \cite{Vij92}.

Une description d'arbres est d�finie par un ensemble de n\oe uds et de
relations d'ascendance, de parent� et de pr�c�dence entre ces n\oe
uds. Les n\oe uds repr�sentent des syntagmes (�ventuellement vides) et
les relations expriment les d�pendances entre ces syntagmes. Les
propri�t�s morpho-syntaxiques de ces syntagmes sont d�crites par des
structures de traits.

Cette approche flexible est bien adapt�e � l'ambigu�t� des langues
naturelles. Cependant, l'analyse syntaxique fond�e sur des
descriptions d'arbres est tr�s co�teuse \cite{KNR01}. En effet,
dans cette approche, l'analyse syntaxique consiste � chercher des
mod�les de descriptions d'arbres sous forme d'arbres syntaxiques
compl�tement sp�cifi�s, ce qui est un probl�me NP-complet.

Dans les formalismes op�rationnels fond�s sur les descriptions
d'arbres (comme les D-tree substitution grammars \cite{ROD01} ou les
TT-MCTAG \cite{Kallmeyer03}), cet ind�terminisme est limit� en
contraignant la syntaxe des descriptions et le m�canisme de
composition syntaxique.

L'originalit� des grammaires d'interaction est de proposer un
m�canisme de composition syntaxique tr�s souple qui consiste �
superposer les descriptions d'arbres mais qui est guid� par une
contrainte de saturation de \textit{polarit�s}.  Cette contrainte fait
r�f�rence � l'id�e de valence de Tesni�re \cite{Tesniere:1934} et est
essentielle dans les CG~: chaque mot est �quip� d'une valence
exprimant ses possibilit�s d'interaction avec les autres mots. La
composition syntaxique est contr�l�e pas une dualit�
besoins/ressources~: certaines ressources munies de polarit�s
n�gatives sont attendues alors que d'autres, munies de polarit�s
positives, sont disponibles. Dans les IG, cette id�e de valence est
reprise et g�n�ralis�e.

\subsection{Syst�me de polarit�s}

Contrairement aux CG, les IG attachent les polarit�s aux traits qui
d�corent les n\oe uds. Mais nous nous en tiendrons ici � une version
simplifi�e des IG o� les polarit�s sont accroch�es aux n\oe uds. Une
autre diff�rence avec les CG est que le syst�me de polarit�s est plus
riche. En effet, les IG proposent deux types d'interaction � base de
polarit�s:
\begin{itemize}
\item \textbf{les interactions lin�aires~:} chaque n\oe ud portant une
  polarit� positive (not�e $+$) doit fusionner avec exactement un n\oe
  ud portant une polarit� n�gative (not�e $-$) et r�ciproquement.
\item \textbf{les interactions non-lin�aires~:} chaque n\oe ud portant
  une polarit� virtuelle (not�e $\sim$) doit fusionner exactement,
  soit avec un n\oe ud positif et un n\oe ud n�gatif, soit avec un
  n\oe ud portant la polarit� satur�e (not�e $=$). En revanche, un
  nombre quelconque de noeuds virtuels peuvent fusionner avec le m�me
  couple positif/n�gatif ou avec le m�me n\oe ud satur�.


\end{itemize}


\begin{wraptable}{r}{10em}
\small{    \begin{tabular}{|c | c c c c |}
      \hline
      & $\sim$ & $-$ & $+$ & $=$  \\
      \hline
      $\sim$ & $\sim$ & $-$ & $+$ & $=$ \\
      $-$ & $-$ & & $=$ & \\
      $+$ & $+$ & $=$ & &  \\
      $=$ & $=$ & & &  \\
      \hline
    \end{tabular}}
% \caption{Composition de polarit�s\label{polarit�}}
\end{wraptable}
Lors de la fusion de deux n\oe uds, le n\oe ud r�sultant porte la
polarit� issue de la composition des polarit�s des n\oe uds
initiaux. La composition d'une polarit� positive et d'une polarit�
n�gative donne une polarit� satur�e alors que la polarit� virtuelle
est l'�l�ment neutre de cette op�ration.  Toute autre composition
provoque l'�chec de la fusion
(cf. tableau ci-contre). L'op�ration de composition est
associative et commutative, l'ordre de fusion des n\oe uds n'a donc
pas d'importance dans le processus de composition syntaxique.

\subsection{Analyse avec les IG}

La structure syntaxique �l�mentaire manipul�e dans les IG est appel�e
{\bf description d'arbre polaris�e} (DAP). Une IG particuli�re est
d�finie par un ensemble de DAP~; chaque DAP est associ�e � un
mot\footnote{Dans nos grammaires, il n'y a pas de co-ancre et donc un
  seul mot par DAP (l'usage de co-ancre peut-�tre simul� en utilisant
  des polarit�s).}. La grammaire est ainsi un lexique o� un mot peut
avoir plusieurs entr�es. Pour analyser une phrase, il faut choisir
pour chaque mot l'une des DAP associ�e � ce mot. Un tel choix est
appel�e une {\bf s�lection lexicale}. L'analyse consiste ensuite �
composer ces DAP pour obtenir un arbre d'analyse.


% Formellement, l'arbre d'analyse est d�crit comme un mod�le de
% l'ensemble des DAP d'une s�lection lexicale. Un mod�le d'un ensemble
% de DAP est un arbre o� chaque n\oe ud porte une polarit� satur�e et
% interpr�te un ensemble de n\oe uds des DAP qui ont fusionn�. Dans la
% pratique, la recherche de mod�le se fait pas � pas~:
L'op�ration atomique de composition syntaxique consiste � superposer
deux n\oe uds pour saturer leurs polarit�s. On it�re l'op�ration de
saturation de n\oe uds pour construire progressivement l'analyse de la
phrase sous forme d'un arbre.

Les DAP d'une s�lection lexicale pour la phrase \french{Jean en conna�t la
couleur} sont repr�sent�es sur la figure~\ref{selection}.

\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.32]{jean}
\includegraphics[scale=0.32]{en}
\includegraphics[scale=0.32]{connait}
\includegraphics[scale=0.32]{la}
\includegraphics[scale=0.32]{couleur}
\end{center}
\caption{DAP associ�es � la phrase \french{Jean en conna�t la
  couleur}\label{selection}}
\end{figure}

La DAP repr�sentant le mot \french{en} d�crit l'intuition
linguistique suivante~: le pronom \french{en} est utilis� comme compl�ment
du nom \french{couleur} mais il vient s'adjoindre devant le verbe
\french{conna�t} qui admet \french{la couleur} comme objet direct. La DAP montre
� droite du noyau verbal \node{C2} un syntagme objet \node{D2}
attendu comportant un compl�ment du nom \node{J2} qui est d�j�
compl�tement satur� mais sans r�alisation phonologique. Le n\oe ud
\node{I2} renseigne la positionnement du nom dans le syntagme
\node{H2}. Au niveau du noyau verbal \node{C2}, le pronom \french{en}
\node{E2} est positionn� � gauche du verbe \node{F2}.

� partir de l'ensemble des DAP de la figure~\ref{selection}, on peut
construire l'arbre syntaxique satur� repr�sent� sur la
figure~\ref{modele}. Sur chaque n\oe ud de l'arbre est indiqu�
l'ensemble des n\oe uds des DAP qui ont �t� superpos�s. Par exemple le
n\oe ud \node{A2-A3} repr�sente la superposition du n\oe ud \node{A2} de la
DAP de \french{en} et du n\oe ud \node{A3} de la DAP de
\french{conna�t}.
%
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.32]{jeanenconnaitlacouleur}
\end{center}
\caption{Arbre d'analyse de \french{Jean en conna�t la couleur}\label{modele}}
\end{figure}
%\vspace{-0.8cm}
 
% Pour r�sumer, l'analyse d'une phrase avec les IG consiste �:
% \begin{itemize}
% \item choisir une s�lection lexicale~;
% \item it�rer l'op�ration de saturation (jusqu'� obtention d'un arbre satur�)~:
%   \begin{itemize}
%   \item entre deux n\oe uds positif et n�gatif (interaction lin�aire)~;
%   \item entre un n\oe ud virtuel et un autre non-virtuel (interaction non-lin�aire).
%   \end{itemize}
% \end{itemize}


\subsection{Grammaire du fran�ais}
Pour valider le formalisme, nous avons d�velopp� une grammaire du
fran�ais~\cite{perrier07}. Cette grammaire a �t� �valu�e sur la
TSNLP~\cite{Lehmann96tsnlp} qui contient 1690 �nonc�s grammaticaux et
1935 �nonc�s agrammaticaux. Ce jeu de tests ne couvre pas toute la
langue fran�aise, il y a peu de phrases complexes mais il insiste sur
certains ph�nom�nes comme la coordination ou la position des
compl�ments adverbiaux. Cependant, notre grammaire couvre d'autres
ph�nom�nes dont la TSNLP ne tient pas compte, comme par exemple~: la
voix passive, la sous-cat�gorisation des noms et des adjectifs
pr�dicatifs, le contr�le du sujet des compl�ments infinitifs, les
propositions relatives et interrogatives. 88\% des 1690
phrases grammaticales sont mod�lis�es et 85\% des 1935 phrases
agrammaticales sont rejet�es. Les 15\% d'�nonc�s agrammaticaux sont
accept�s car la grammaire ne mod�lise pas les r�gles phonologiques et
la s�mantique. Les raisons pour lesquelles 12\% des �nonc�s
grammaticaux ne sont pas analys�s sont diverses (phrases
retranscrites de l'oral, expressions fig�es, causatifs, superlatifs).


%======================================================================
\section{Analyse en d�pendances}
\label{sec-analyse}
L'analyse syntaxique est obtenue par superposition des DAP d'une
s�lection lexicale. La superposition est guid�e par la fusion des n\oe
uds portant des polarit�s se saturant. Au niveau d'une DAP, ces
polarit�s repr�sentent les besoins/ressources du mot dans un �nonc�.
La saturation de ces derni�res peut alors se voir comme la r�solution
d'une d�pendance entre ces mots. On peut alors retrouver les relations
de d�pendances d'une phrase � partir de l'ensemble des DAP associ�es
aux mots de la phrase et de son analyse.

\subsection{D�pendances lin�aires}
Nous nous int�ressons dans un premier temps au cas simple de la
saturation lin�aire de deux polarit�s $+$ et $-$. Par exemple, dans la
phrase \french{Jean en conna�t la couleur} (Figure~\ref{modele}), la
DAP repr�sentant le d�terminant \french{la} poss�de un n\oe
ud~\node{G4} portant une polarit� positive et �tiquet� par la
cat�gorie syntaxique {\tt DET}.  La DAP du nom \french{couleur}
comporte quant � elle un n\oe ud~\node{G5} portant une polarit�
n�gative qui est aussi �tiquet� par {\tt DET}.

Lors de l'analyse, ces deux n\oe uds fusionnent pour obtenir un n\oe
ud satur�, la DAP r�sultante repr�sentant une analyse partielle de
\french{la couleur}. La saturation de ces deux n\oe uds peut �tre vue
comme la r�alisation d'une relation de d�pendances entre les deux mots
correspondants.

L'op�ration de saturation repr�sente la satisfaction d'une contrainte
de besoins/ressources. Un �l�ment qui se pr�sente comme n�cessitant une
ressource est consid�r� comme le gouverneur de la relation de d�pendances,
tandis qu'un �l�ment qui se pr�sente comme fournissant une ressource
se retrouve comme le d�pendant de cette relation. Ainsi,
en cas d'interaction lin�aire, le mot dont la DAP contient le n\oe ud
n�gatif est le \textit{gouverneur} et le mot dont la DAP contient le
n\oe ud positif est le \textit{d�pendant} de la relation de d�pendances.

Les relations de d�pendances engendr�es par la saturation des n\oe uds
portant des polarit�s oppos�es seront appel�es {\bf d�pendances
  lin�aires}. Dans la grammaire actuelle du fran�ais, elles
repr�sentent les relations t�te-compl�ment et t�te-sp�cifieur.
%
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=1.0]{dep_jeclc_lin}
\caption{Relations de d�pendances lin�aires dans la phrase \french{Jean en
conna�t la couleur} \label{enconnaitlin�aire}}
\end{center}
\end{figure}
%\vspace{-0.8cm}

Dans l'exemple \french{Jean en conna�t la couleur}, les d�pendances
lin�aires obtenues sont repr�sent�es sur la
figure~\ref{enconnaitlin�aire} (les arcs portent la cat�gorie qui a
fait l'objet d'une saturation\footnote{en pratique, il est possible
  d'utiliser d'autres �tiquettes sur les arcs comme les fonctions
  syntaxiques (elles sont indiqu�es dans les structures de traits).}).

Cette analyse poss�de un n\oe ud \french{en} isol�. La DAP du pronom
\french{en} ne porte en effet pas de polarit� positive ou n�gative et
ainsi ne produit pas de relation de d�pendances lin�aires avec le
reste de la phrase. La saturation des polarit�s positives et n�gatives
ne suffit donc pas pour exprimer toutes les relations de d�pendances
d'une phrase. Nous allons donc voir comment certaines relations de
d�pendances peuvent �tre produites pas des interactions non-lin�aires.

\subsection{D�pendances non-lin�aires}

% Nous nous int�ressons maintenant aux relations de d�pendances
% produites par la saturation non-lin�aire de polarit�s.

\begin{wrapfigure}{r}{25mm}
\begin{center}
\includegraphics[scale=0.36]{belle}
%\caption{DAP de l'adjectif \french{belle}\label{belle}}
\end{center}
\end{wrapfigure}
Dans la grammaire actuelle, la DAP pour l'adjectif \french{belle} dans
le groupe nominal \french{la belle couleur} est donn�e par la figure ci-contre.
De fa�on habituelle en d�pendances, on
consid�re qu'il y a une d�pendance de \french{belle} vis � vis de
\french{couleur}. Deux n\oe uds sont non-satur�s (\node{H6} et
\node{I6}) et ils portent tous les deux une polarit�s virtuelle,
c'est donc la saturation de l'une de ces deux polarit�s qui doit
induire la d�pendance. Dans ce cas, les deux polarit�s peuvent �tre �
l'origine de la d�pendance. Cependant, il ne doit �tre produit qu'une
seule relation de d�pendances, il faut choisir alors quelle polarit�
engendrera une d�pendance lors de sa saturation.

\begin{wrapfigure}{r}{35mm}
\begin{center}
\includegraphics[scale=0.36]{le}
%\caption{DAP du pronom \french{le}\label{le}}
\end{center}
\end{wrapfigure}
Un autre exemple d'usage des polarit�s virtuelles dans la grammaire du
fran�ais est illustr� par l'exemple \french{Jean le conna�t}. Dans
cette phrase, le pronom \french{le} (ci-contre) est l'objet
direct du verbe \french{conna�t}~: cette relation de d�pendances est
produite par la saturation lin�aire des polarit�s du n\oe ud \node{D7}
de la DAP du pronom \french{le} et du n\oe ud \node{D3} de la DAP du
mot \french{conna�t}. Mais la DAP du pronom \french{le} poss�de trois
n\oe uds \node{A7}, \node{C7}, \node{F7} portant une polarit�
virtuelle dont la saturation non-lin�aire n'apporte aucune information
de d�pendances entre les mots \french{le} et \french{conna�t}. Ces
polarit�s contr�lent simplement la place des syntagmes lors de la
superposition des deux DAP et g�rent le fait que le pronom \french{le}
se place avant le verbe alors que la place canonique du groupe nominal
objet dans la phrase est apr�s le verbe. Dans l'arbre d'analyse de
\french{Jean le conna�t} les trois n\oe uds virtuels \node{A7},
\node{C7}, \node{F7} sont satur�s, respectivement, par les trois n\oe
uds \node{A3}, \node{C3}, \node{F3} de la DAP du mot \french{conna�t}.

Les deux derniers exemples montrent bien qu'il y a deux usages
distincts des polarit�s virtuelles qui ne se comportent pas de la m�me
mani�re pour la production de relation de d�pendances~:
\begin{itemize}
\item les {\bf polarit�s virtuelles de d�pendances} qui portent une information
  sur les relations de d�pendances d'un mot avec son environnement~;
\item les {\bf polarit�s virtuelles de contexte} qui imposent des contraintes sur
  le contexte syntaxique d'un mot.
\end{itemize}

Il n'est pas possible de distinguer automatiquement, dans une
grammaire donn�e, les deux types de polarit�s virtuelles. C'est donc �
l'auteur de la grammaire de se baser sur des crit�res linguistiques
pour distinguer ces deux usages. Cependant, dans la pratique,
l'utilisation de m�tagrammaires (notre grammaire, par exemple, est
construite avec XMG~\cite{xmg}) permet de faire ce travail rapidement,
de fa�on coh�rente sur l'ensemble de la grammaire. Cela concerne
uniquement les mots jouant le r�le de modificateurs (adjectifs
�pith�tes, adverbes, pr�positions introduisant des compl�ments
adjoints, pronoms relatifs dans leur r�le par rapport � leur
ant�c�dent, pronom clitique "il" utilis� en redoublement du
sujet, etc.). Il s'agit, dans la DAP associ� au mot concern� de marquer le
n\oe ud consid�r� comme n\oe ud privil�gi� de rattachement au mot qui
est modifi�. Le travail a �t� effectu� sur notre grammaire du fran�ais �
large couverture en moins d'une heure.

Ainsi, dans la DAP de \french{en} (figure~\ref{selection}), toutes les
polarit�s virtuelles des n\oe uds \node{A2}, \node{C2},
\node{D2} et \node{F2} sont des polarit�s virtuelles de contexte
qui g�rent le positionnement de \french{en}. Pour rendre compte du
fait que \french{en} d�pend de \french{couleur}, il faut que l'une des
deux polarit�s virtuelles \node{H2} ou \node{I2} soit une polarit�
virtuelle de d�pendances. Dans notre cas, nous avons choisi
arbitrairement la polarit� \node{H2}.

Dans le cas o� une relation de d�pendances est produite, le
\textit{d�pendant} est le mot dont la DAP porte le n\oe ud virtuel de
d�pendances. La polarit� virtuelle peut �tre satur�~:
\begin{itemize}
\item soit par un n\oe ud portant la polarit� $=$, dans ce cas ce
  n\oe ud est le gouverneur~;
\item soit par un couple de n\oe ud (un positif et un n�gatif), dans
  ce cas le gouverneur est le n\oe ud portant la polarit� positive.
\end{itemize}

Les relations ainsi engendr�es sont appel�es {\bf d�pendances
  non-lin�aires}. En effet, un n\oe ud satur� pouvant se composer avec
z�ro ou plusieurs n\oe uds virtuels, plusieurs relations de d�pendances
peuvent avoir comme gouverneur le m�me mot. Ces relations de d�pendances
expriment g�n�ralement une relation modifieur-modifi�.

Dans les structures de d�pendances (figures~\ref{enconnait} ci-dessous
et~\ref{la_fille_que_} plus loin) les d�pendances lin�aires sont
repr�sent�es au-dessus de la phrase et les non-lin�aires au-dessous.

La proc�dure d'extraction des d�pendances se r�sume ainsi:

\begin{itemize}
\item La saturation de polarit�s oppos�es engendre une relation de
 d�pendances lin�aire entre les mots~; la relation va de la polarit�
 n�gative vers la polarit� positive.
\item La saturation d'une polarit� virtuelle de d�pendances avec une
  polarit� positive ou satur�e engendre une relation de d�pendances non
  lin�aire entre les mots~; la relation va de la polarit� satur�e ou
  positive vers la polarit� virtuelle de d�pendances.
\end{itemize}

Cette proc�dure permet d'obtenir l'analyse en d�pendances de
\french{Jean en conna�t la couleur} repr�sent�e figure~\ref{enconnait}.

\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=1.0]{dep_jeclc}
\caption{Relations de d�pendances dans la phrase \french{Jean en
 conna�t la couleur} \label{enconnait}}
\end{center}
\end{figure}
\vspace{0.8cm}

Pour garantir que les structures de d�pendances sont connexes (chaque
mot est en relation avec au moins un autre mot de l'�nonc�), il suffit
d'imposer que chaque DAP de la grammaire contienne au moins un n\oe ud
positif, un n\oe ud n�gatif ou un n\oe ud portant une polarit�
virtuelle de d�pendances. C'est la cas de la grammaire actuellement
implant�e pour le fran�ais.

%======================================================================
\section{Structures de d�pendances obtenues}
\label{sec-structures}

Le choix du type de structures pour repr�senter les d�pendances d'une
phrase est une question �pineuse qui divisent les linguistes. L'id�e
de d�part des grammaires de d�pendances est de consid�rer que chaque
mot de la phrase (sauf le verbe principal) est {\em gouvern�} par
exactement un autre mot de la m�me phrase. Cette hypoth�se conduit �
consid�rer que les bonnes structures de d�pendances sont les arbres,
nous allons voir ce qu'il en est avec notre m�thode qui permet
d'observer, sans a priori, les structures obtenues.



\subsection{Graphes orient�s}
De fa�on g�n�rale, la structure en d�pendances que l'on obtient est un
graphe orient�~; de plus, avec la restriction impos�e sur les DAP de
la grammaire, on sait que ce graphe est connexe.

L'analyse en d�pendances pour la phrase \french{Jean en conna�t la
  couleur} donn�e par la figure~\ref{enconnait} est un arbre~; en
effet, tous les mots, sauf \french{conna�t}, ont un et un seul
gouverneur.  Il existe cependant des exemples pour lesquels la
structure de d�pendances n'est pas un arbre. L'application de notre
m�thode � la phrase \french{la fille que Jean aime vient} produit
l'analyse de la figure~\ref{la_fille_que_}. Cette structure n'est pas
un arbre car elle contient un cycle\footnote{\french{aime} gouverne
  \french{que} car \french{que} est le compl�ment d'objet de
  \french{aime}~;\french{que} gouverne \french{aime} car c'est le
  pronom relatif qui introduit la relative o� \french{aime} est le
  verbe.}
et le pronom relatif \french{que} a
deux gouverneurs.
%
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=1.0]{dep_lfqjav}
\caption{Relations de d�pendances dans la phrase \french{la
fille que Jean aime vient} \label{la_fille_que_}}
\end{center}
\end{figure}
%\vspace{-0.8cm}

On retrouve ainsi avec notre m�thode le probl�me qui se pose
habituellement en grammaire de d�pendances pour g�rer les ph�nom�nes
d'extraction. % Dans le cas de notre exemple, l'analyse obtenue est
% similaire � celle que S.~Kahane propose dans~\cite{kahane00}.
Par exemple, si nous reprenons la phrase \french{la fille que Jean
  aime vient}, le mot \french{que} remplit ici deux r�les, il est
l'objet anaphorique de \french{aime} et subordonne la relative �
l'ant�c�dent.  Ce double r�le suppose naturellement deux relations de
d�pendances distinctes qui contredisent le principe de repr�sentation
en arbre, alors que l'analyse pr�sent�e figure~\ref{la_fille_que_}
rend bien compte de ce double emploi. D'autres approches d'analyses en
d�pendances utilise �galement des structures qui ne sont pas des
arbres~: S.~Kahane~\cite{kahane00} propose une analyse dans laquelle
un pronom relatif a deux gouverneurs~; R.~Hudson~\cite{hudson90}
utilise �galement souvent des structures dans lesquelles un mot peut
avoir plusieurs gouverneurs.

\subsection{Projectivit�}
Une autre question r�currente � propos des structures de d�pendances �
consid�rer pour la description de la langue est celle de la
projectivit�. En effet une structure projective induit que les
relations de d�pendances restent � un niveau local, ce qui permet une
analyse simple et efficace.

Cette notion initialement d�finie pour les arbres peut se transposer
sur les graphes~: une structure de d�pendances est dite projective si
pour tout mot donn�, l'ensemble des n\oe uds atteignables depuis ce
mot dans la structure de d�pendances (qu'on appellera {\bf emprise du
  mot}) correspond � un segment continu de l'�nonc�.  Par exemple la
structure de la figure~\ref{la_fille_que_} est projective alors que
celle de la figure~\ref{enconnait} ne l'est pas~: dans cette analyse,
l'emprise du mot \french{couleur} est form� de deux segments
\french{en} et \french{la couleur} s�par�s par le mot
\french{conna�t}.

\subsection{Classes de structures de d�pendances}
R.~Debusmann and M.~Kuhlmann proposent des crit�res qui permettent de
classer plus finement les analyses non-projectives. Il obtiennent
ainsi une hi�rarchisation en classes du pouvoir expressif que
permettent les diff�rentes structures de
d�pendances~\cite{debusmann08}. La notion de {\bf degr� de
discontinuit�} (block-degree) associe � une structure un entier qui
est le nombre maximum de segments continus disjoints dans l'emprise
d'un mot (un degr� de discontinuit� de $1$ correspond exactement � la
projectivit�).  Pour les structures dont le degr� de discontinuit� est
au moins $2$, ils distinguent celles qui sont {\bf bien imbriqu�es}
(well-nestedness) c'est-�-dire celle qui sont telles que les emprises
des deux mots ne se croisent pas (soit elles sont disjointes, soit
l'une est enti�rement incluse entre deux segments de l'autre). Sur le
Prague Dependency Treebank, les auteurs montrent que 99,5\% des
analyses sont bien imbriqu�es et de degr� de discontinuit� au plus
deux (ce qui est �quivalent � �tre dans la classe de langages des
TAG).

L'application de notre m�thode � cette grammaire du fran�ais sur la
TSNLP ne produit pas d'analyse mal imbriqu�es. On obtient dans la
plupart des cas des structures de d�pendances projectives. Les
exemples pour lesquels le degr� de discontinuit� est de $2$ sont d�s
principalement au placement de l'auxiliaire dans le noyau verbal. Les
mots \french{en} ou \french{y} ainsi que l'inversion sujet/verbe lors
de l'emploi de pronoms interrogatifs sont d'autres sources de
discontinuit�, mais nous n'avons pas trouv� d'exemple qui aille au-del�
d'un degr� de discontinuit� de $2$.

%======================================================================
\section{Conclusion}
Dans cet article, nous avons propos� une m�thode pour construire une
analyse en d�pendances d'un �nonc� � partir de son analyse en
constituants dans les IG. Cette m�thode, bas�e sur la saturation des
polarit�s, a mis en �vidence deux types de d�pendances~: les
d�pendances lin�aires qui repr�sentent les relations t�te-compl�ment ou
t�te-sp�cifieur et les d�pendances non-lin�aires qui repr�sentent
les relations modifieur-modifi�.

Les structures de d�pendances obtenues par cette m�thode sont des
graphes orient�s, elles sont plus riches que les structures obtenues
habituellement par des grammaires de d�pendances. Cette repr�sentation
permet de g�rer simplement les ph�nom�nes linguistiques posant
habituellement des difficult�s dans les grammaires de d�pendances.

Pour la suite du travail, nous souhaitons �tudier dans quelle mesure
il est possible de transposer les m�thodes d'analyses d'un formalisme
� l'autre. Par exemple, Nous avons remarqu� que tr�s peu d'analyses
sont non-projectives~; on pourrait donc isoler les cas non-projectifs et
adapter un algorithme d'analyse des grammaires de d�pendances qui
servirait de guide � l'analyse dans les IG. Il serait �galement
int�ressant d'�tudier l'application de nos m�thodes d'analyse
sp�cifiques aux IG � l'analyse pour des grammaires de d�pendances
lexicalis�es.  

\bibliographystyle{taln2002} 
\bibliography{taln09}

\end{document}


% LocalWords:  TALN Jonathan Bruno Guillaume Perrier LORIA Nancy Grand-Est TAG
% LocalWords:  polarit�s polarit� Dikovsky Modina Rambow Joshi Koller Kuhlmann
% LocalWords:  IG Marcus Hindle Fleck Vijay-Shanker uds pr�c�dence NP-complet
% LocalWords:  morpho-syntaxiques D-tree TT-MCTAG Tesni�re GC ud DAP co-ancre
% LocalWords:  i.e it�rer non-virtuel DET sp�cifieur t�te-compl�ment XMG Kahane
% LocalWords:  t�te-sp�cifieur anaphorique Hudson Projectivit� projectivit�
% LocalWords:  projective Debusmann non-projectives block-degree Prague taln
% LocalWords:  well-nestedness Dependency Treebank modifieur-modifi� TSNLP
% LocalWords:  agrammaticaux sous-cat�gorisation pr�dicatifs agrammaticales
% LocalWords:  clitique

taln09.bbl
\begin{thebibliography}{~~~}

\bibitem[\protect\citename{Clark {\em et~al.}, }2002]{Clark02}
{\sc Clark S., Hockenmaier J. \& Steedman M.} (2002).
\newblock Building deep dependency structures with a wide-coverage {CCG}
  parser.
\newblock In {\em In Proceedings of the 40th Meeting of the ACL}, p.\ 327--334.

\bibitem[\protect\citename{Debusmann \& Kuhlmann, }2009]{debusmann08}
{\sc Debusmann R. \& Kuhlmann M.} (2009).
\newblock Dependency grammar: Classification and exploration.
\newblock In {\em Resource-Adaptive Cognitive Processes}: Springer.

\bibitem[\protect\citename{Dikovsky \& Modina, }2000]{dikovsky00}
{\sc Dikovsky A. \& Modina L.} (2000).
\newblock Dependencies on the other {S}ide of the {C}urtain.
\newblock {\em T.A.L}, {\bf 1}, 79--111.

\bibitem[\protect\citename{Duchier {\em et~al.}, }2005]{xmg}
{\sc Duchier D., Le~Roux J. \& Parmentier Y.} (2005).
\newblock {XMG}~: {U}n {C}ompilateur de {M}�ta-{G}rammaires {E}xtensible.
\newblock In {\sc M. Jardino}, Ed., {\em Actes de TALN 2005 (Traitement
  automatique des langues naturelles)}, Dourdan: ATALA  LIMSI.

\bibitem[\protect\citename{Hudson, }1990]{hudson90}
{\sc Hudson R.~A.} (1990).
\newblock {\em English {W}ord {G}rammar}.
\newblock Blackwell.

\bibitem[\protect\citename{Kahane, }2000]{kahane00}
{\sc Kahane S.} (2000).
\newblock Extractions dans une grammaire de d�pendance � bulles.
\newblock {\em T.A.L.}, {\bf 41}(1), 187--216.

\bibitem[\protect\citename{Kallmeyer, }2005]{Kallmeyer03}
{\sc Kallmeyer L.} (2005).
\newblock Tree-local {M}ulticomponent {T}ree {A}djoining {G}rammars with
  {S}hared {N}odes.
\newblock {\em Computational Linguistics}, {\bf 31}(2), 187--225.

\bibitem[\protect\citename{Koller {\em et~al.}, }1998]{KNR01}
{\sc Koller A., Niehren J. \& Treinen R.} (1998).
\newblock Dominance constraints: Algorithms and complexity.
\newblock In {\em LACL'98}, p.\ 106--125, Heidelberg.

\bibitem[\protect\citename{Lehmann {\em et~al.}, }1996]{Lehmann96tsnlp}
{\sc Lehmann S., Oepen S., C I., Baur H.~H., Lbdkan O. \& Arnold D.} (1996).
\newblock tsnlp --- test suites for natural language processing.
\newblock In {\em In J. Nerbonne (Ed.), Linguistic Databases (pp. 13 - 36}, p.\
  711--716: CSLI Publications.

\bibitem[\protect\citename{Marcus {\em et~al.}, }1983]{Marcus83}
{\sc Marcus M.~P., Hindle D. \& Fleck M.~M.} (1983).
\newblock D-theory: talking about talking about trees.
\newblock In {\em Proceedings of the 21st annual meeting on Association for
  Computational Linguistics}, p.\ 129--136, Morristown, NJ, USA: Association
  for Computational Linguistics.

\bibitem[\protect\citename{Perrier, }2003]{Per2003}
{\sc Perrier G.} (2003).
\newblock {\em Les grammaires d'interaction}.
\newblock Habilitation � diriger les recherches, Universit\'e Nancy~2.

\bibitem[\protect\citename{{P}errier, }2007]{perrier07}
{\sc {P}errier G.} (2007).
\newblock {A} {F}rench {I}nteraction {G}rammar.
\newblock In {\em {RANLP} 2007}, p.\ 463--467, {B}orovets {B}ulgarie.

\bibitem[\protect\citename{Rambow \& Joshi, }1997]{rambow94}
{\sc Rambow O. \& Joshi A.} (1997).
\newblock A {F}ormal {L}ook at {D}ependency {G}rammars and {P}hrase-{S}tructure
  {G}rammars, with {S}pecial {C}onsideration of {W}ord-{O}rder {P}henomena.
\newblock In {\em Current Issues in Meaning-Text Theory}, London: Pinter.

\bibitem[\protect\citename{Rambow {\em et~al.}, }2001]{ROD01}
{\sc Rambow O., Weir D. \& Vijay-Shanker K.} (2001).
\newblock D-tree substitution grammars.
\newblock {\em Comput. Linguist.}, {\bf 27}(1), 89--121.

\bibitem[\protect\citename{Tesni{\`e}re, }1934]{Tesniere:1934}
{\sc Tesni{\`e}re L.} (1934).
\newblock Comment construire une syntaxe.
\newblock {\em Bulletin de la Facult{\'e} des Lettres de Strasbourg}, {\bf
  12}(7), 219--229.

\bibitem[\protect\citename{Vijay-Shanker, }1992]{Vij92}
{\sc Vijay-Shanker K.} (1992).
\newblock {U}sing {D}escription of {T}rees in {T}ree {A}djoining {G}rammar
  framework.
\newblock {\em Computational Linguistics}, {\bf 18}(4), 481--518.

\end{thebibliography}
