Eric Laporte Institut Gaspard-Monge Université Paris-Est Marne-la-Vallée France laporte/ Syntaxe...

Eric LaporteInstitut Gaspard-Monge

Université Paris-Est Marne-la-ValléeFrance

http://igm.univ-mlv.fr/~laporte/

Syntaxe et analyse syntaxiqueRéseaux sémantiques

Syntaxe et analyse syntaxiqueRéseaux sémantiques

UnificationAnalyse syntaxique par l'algorithme

d'EarleyRéseaux sémantiquesRelations sémantiquesWordNet

Accord grammatical (1/4)

P --> GN attend Le public attendLe GN est obligatoirement au singulier :

* Les spectateurs attend

P --> GN attendent Les spectateurs attendent

Le GN est obligatoirement au pluriel :* Le public attendent

On veut éviter d'avoir deux symboles distincts pour les GN au singulier et les GN au pluriel

Accord grammatical (2/4)

P --> GN attend { GN.nombre = "singulier" }P --> GN attendent { GN.nombre = "pluriel" }

On considère les traits du GN comme des attributs du symbole GN

On ajoute des attributs aux symboles et des équations aux règles

On veut éviter d'avoir deux règles distinctes

Accord grammatical (3/4)

P --> GN <attendre> {GN.nombre = <attendre>.nombre ;GN.personne =

<attendre>.personne ; }Le public attend - Les spectateurs attendent -

Vous attendezOn considère les traits de attendre comme des

attributs aussi

Accord grammatical (4/4)

Vérification des équationsP --> GN <attendre> {

GN.nombre = <attendre>.nombre ;GN.personne =

<attendre>.personne ; }On ne sait pas si on connaîtra la valeur de

GN.nombre avant celle de<attendre>.nombre ou le contraire

On veut pouvoir vérifier l'équation avant de connaître aucun des deux attributs

On vérifie les équations par unification

Unification (1/7)

Unification entre GN.nombre et<attendre>.nombre

Avant :GN.nombre = x <attendre>.nombre = "singulier"

Après :GN.nombre = "singulier" <attendre>.nombre = "singulier"

Les valeurs à unifier peuvent être des constantes ou des variables

Unification (2/7)

Avant :GN.nombre = x <attendre>.nombre = yAprès :GN.nombre = x <attendre>.nombre = xEn fait, après unification, les deux valeurs sont

représentées par des objets distincts mais équivalents

Plus tard, si une autre unification précise l'une des deux, cela changera automatiquement l'autre aussi

Avant unification, chaque valeur n'est équivalente qu'à elle-même

Unification (3/7)

Formalisation de l'équivalenceChaque valeur a un champ "ensemble" qui contient un

pointeurGN.nombre.ensemble := 0<attendre>.nombre.ensemble := GN.nombre

Dans chaque classe d'équivalence, une seule des valeurs est choisie comme élément canonique

Pour la valeur canonique, le champ ensemble est le pointeur nul

Pour toutes les autres valeurs, le champ ensemble pointe directement ou indirectement sur la valeur canonique

Unification (4/7)

Unification entre GN.nombre et<attendre>.nombre

Avant :GN.nombre = "pluriel" <attendre>.nombre = "singulier"

Après :GN.nombre = "pluriel" <attendre>.nombre = "singulier"

L'unification peut échouerL'algorithme d'unification renvoie un booléenL'unification est destructrice : elle peut changer les

deux valeurs à unifier, même si l'unification échoue

Unification (5/7)

Unifier deux valeurs a et b, c'est construire une valeur qui contient toutes les restrictions de a et de b en vérifiant qu'elles sont compatibles

Unification (version 1)

booléen unifier(valeur a, valeur b) { A := trouver-canonique(a) ; B := trouver-canonique(b) ; si (A = B) { renvoyer vrai ; } sinon si (A et B sont la même constante) { renvoyer vrai ; } sinon si (A ou B est une variable) { unir(A, B) ; renvoyer vrai

; } sinon { renvoyer faux ; }}

unir(valeur A, valeur B) { si A n'est pas une variable { B.ensemble := A ; } sinon { A.ensemble := B ; }}

Unification (7/7)

trouver-canonique(valeur a)Renvoie l'élément canonique de la classe d'équivalence de a

unir(valeur A, valeur B)Fusionne les classes d'équivalence de A et BPréconditions :- A et B sont les éléments canoniques de leurs classes

d'équivalence- L'unification entre A et B réussitSi l'une des deux valeurs est une constante, c'est elle qui doit

être devenir l'élément canonique de l'autreCela revient à remplacer la variable par la constante

Accord grammatical (1/2)

P --> GN <attendre> {GN.nombre = <attendre>.nombre ;GN.personne =

<attendre>.personne ; }

si (unifier(GN.nombre, <attendre>.nombre)et unifier (GN.personne, <attendre>.personne)) { l'analyse syntaxique peut continuer }

Accord grammatical (2/2)

GN --> Dét N { Dét.nombre = N.nombre ;GN.nombre = N.nombre ;GN.personne = "3" ; }

si (unifier(Dét.nombre, N.nombre)et unifier(GN.nombre, N.nombre)et unifier(GN.personne, "3")) { l'analyse syntaxique peut continuer }

On a l'impression que GN.personne = "3" est une simple affectation

Si on connaît GN.personne par une autre équation avant de traiter cette règle, c'est bien une équation à vérifier

Avec des RTN

On attache les attributs- à des noeuds du graphe : $$.nombre- au graphe : nombre, personne

Fonctionnalité disponible avec Outilex, pas encore avec Unitex

Unification d'arbres (1/3)

P --> GN <attendre> {GN.nombre = <attendre>.nombre ;GN.personne = <attendre>.personne ; }

On veut regrouper les deux attributs en un seul

P --> GN <attendre> {GN.accord = <attendre>.accord ; }

La valeur de l'attribut est maintenant un arbre

Unification d'arbres (2/3)

P --> GN <attendre> {GN.accord = <attendre>.accord ; }

GN.accord=

structure de traits

nombre=

x

personne=

"3"

<attendre>.accord=

structure de traits

nombre=

"singulier"

personne=

y

Unification d'arbres (3/3)

GN.accord=structure de traits

nombre=x

personne="3"

<attendre>.accord=structure de traits

nombre="singulier"

personne=y

Avant

GN.accord=structure de traits

nombre="singulier"

personne="3"

<attendre>.accord=structure de traits

nombre="singulier"

personne="3"

Après

Formalisation des arbres

Un noeud peut être :- une constante ("singulier")- une variable- une structure de traits (feature structure) qui a 0, 1

ou plusieurs attributs dont les valeurs sont des noeuds

GN.accord=structure de traits

nombre=x

personne="3"

Unification (version 2)

booléen unifier(noeud a, noeud b) { A := trouver-canonique(a) ; B := trouver-canonique(b) ; si (A = B) { renvoyer vrai ; } sinon si (A et B sont la même constante) { renvoyer vrai ; } sinon si (A et B sont des structures de traits) {

unir(A, B) ;pour chaque trait t de A ou de B {

si (unifier(A.t, B.t) = faux) { renvoyer faux ; } } renvoyer vrai ; } sinon si (A ou B est une variable) { unir(A, B) ; renvoyer vrai

; } sinon { renvoyer faux ; }}

Résultat de l'unification

Les pointillés représentent les équivalences et pointent vers le membre canonique

GN.accord=

structure de traits

nombre=

x

personne=

"3"

<attendre>.accord=

structure de traits

nombre=

"singulier"

personne=

y

Subsomption (1/2)

x subsume "singulier" x "singulier""3" subsume "3" "3" "3"Le cas général subsume le cas particulier

GN.accord=structure de traits

nombre=x

personne="3"

GN.accord=structure de traits

nombre="singulier"

personne="3"

Subsomption (2/2)

Si S1 est une constante :

S1 S2 si et seulement si S1 = S2

Si S1 est une variable : S2 S1 S2 Si S1 est une structure de traits :

S1 S2 si et seulement si pour tout trait t de S1 ou de S2, S1.t S2.t

Les restrictions précisées dans S1 doivent être précisées aussi dans S2 sans contradiction

S2 peut préciser des restrictions supplémentaires

Subsomption et unification

S1 S2 est l'arbre le plus général S3 telle que S1 S3 et S2 S3

S1 S2 contient toutes les informations de S1 et de S2

Têtes des constituants

Le mot le plus important de chaque constituant est appelé sa tête P

(préfère)

GN(Luc)

préfère

GN(compagnie)

N(compagnie)

Det(cette)

cetteLuc compagnie

Grammaires de dépendanceOn remplace chaque symbole non terminal par

la tête correspondante, puis on supprime le noeud redondant

Arbre de dépendancepréfère

Luccompagnie

cette

préfère

Luc

préfère

compagnie

compagniecette

cetteLuc

compagnie

Grammaires de dépendance

Informations perdues- étiquettes des constituants (on compense

en ajoutant des étiquettes aux arêtes)- ordre des mots (on compense si

nécessaire en ajoutant des contraintes sur l'ordre des mots)

préfère

Luccompagnie

cette

sujetobjet

déterminant

LexicalisationLorsqu'un mot a des compléments, la forme des

compléments dépend du motP --> GN <préférer> GN à GN

Luc préfère cette compagnie à la concurrenceP --> GN <quitter> GN Luc quitte ParisP --> GN <partir> Prép GN Luc part pour Toulouse

Nombre de complémentsPrépositions devant les complémentsGrammaire lexicaliséeChaque règle comporte au moins un mot du lexique (la

tête en général)Nombre de règles = nombre de mots x nombre de

constructions

Grammaires non lexicaliséesOn regroupe tous les mots qui entrent dans une

même constructionOn fait une règle commune

P --> GN V GN à GN{ V.N1àN2 = "+" ; }Luc préfère cette compagnie à la

concurrenceP --> GN V GN { V.N1 = "+" ; }

Luc quitte ParisLuc préfère cette compagnie

P --> GN V Prép GN {V.PrépN1 = "+" ; V.Prép = Prép ; }Luc part pour Toulouse

Analyse syntaxiqueParsingEntrées : une phrase étiquetée et une grammaire

algébriqueSorties : le ou les arbres de dérivation de la phrase

AlgorithmesAscendantsDescendantsProgrammation dynamiqueCascade de transducteurs

L'algorithme d'Earley (1970)

Analyse descendanteSauvegarde dans un tableau tous les résultats intermédiaires

réutilisables (programmation dynamique)

Tableau indicé par les tokens de la phrasePhrase : Les orchestres aimentcette mélodieIndices : 0 1 2 3 4

5Pour chaque indice, le tableau contient un ensemble de sous-

arbres correspondant à des analyses partiellesOn remplit le tableau de gauche à droite, sans retours en arrièreOn ne détruit jamais des sous-arbres déjà créésPour construire les arbres de dérivation, on combine les sous-

arbres du tableau

Les sous-arbresUn sous-arbre est représenté par- une règle pointée (le point indique jusqu'où on a

analysé)- deux positions dans la phrase, correspondant :

- au début de la règle- et au point jusqu'où on a analysé

Exemple 1P --> GN <aimer> . GN0-3

<le> <orchestre> <aimer> <ce> <mélodie>

Det N Det N

GN GN

P

0 1 2 3 4 5

Les sous-arbresExemple 2GN --> Det N .0-2

Exemple 3GN --> . Det N3-3

Si la 2e position d'un sous-arbre est j, ce sous-arbre est rangé à l'indice j dans le tableau

Exemple 2 : rangé à l'indice 2 Exemple 3 : rangé à l'indice 3

<le> <orchestre> <aimer> <ce> <mélodie>

Det N Det N

GN GN

P

0 1 2 3 4 5

L'algorithmeOn parcourt le tableau de gauche à droiteQuand on est à l'indice i, on parcourt les sous-arbres et on

crée de nouveaux sous-arbres à l'indice i (queue FIFO) et à l'indice i + 1

On suppose que l'axiome de la grammaire apparaît une seule fois, dans une règle P0 --> P

Début P0 --> . P0-0

Fin P0 --> P .0-n (n = nombre de tokens dans la phrase)

Règle pointée complétée : règle dont le point est à la fin

L'algorithme

analyseur.table[0].enfiler(P0 --> . P, 0, 0)pour i de 0 à n

pour chaque sousArbre dans table[i]si sousArbre.complétée() analyseur.compléter(sousArbre)sinon si sousArbre.prochainSymbole() est

terminal analyseur.vérifier(sousArbre)sinon analyseur.prédire(sousArbre)

si analyseur.table[n].contient(P0 --> P ., 0, n)analyseur.construireArbres(n)

L'algorithme

compléter(B --> w ., j, k) :pour chaque (A --> u . B v, i, j) dans table[j]

table[k].enfiler(A --> u B . v, i, k)

vérifier(A --> u . t v, i, j) :si t correspond à token[j]

table[j + 1].enfiler(A --> u t . v, i, j + 1)

prédire(A --> u . B v, i, j) :pour chaque (B --> w) dans règles(B)

table[j].enfiler(B --> . w, j, j)

Synonymes

C'est un gros avion C'est un grand avionC'est un gros achat ?C'est un grand achatLuc est trop gros Luc est trop grand

CritèrePossibilité de remplacer un mot par l'autre dans

au moins un contexte sans "trop" changer le sens

Réseau sémantiqueComme un lexique mais- plusieurs entrées différentes pour un mot ambigu- une seule entrée pour plusieurs synonymes

Exemples d'entrées1. couillon - gogo - naïf - pigeon2. bar - loup - loup de mer - perche de mer3. bar - bistro - brasserie - café - estaminetUne entrée = un ensemble de synonymes (synset)Membres d'un synset- lemmes et non formes fléchies- mots et non tokens (loup de mer : mot composé)

Relations sémantiquesRelations entre synsets

X est une sorte de Ybar - loup - loup de mer - perche de mer X

poisson - poiscaille Yanimal - bête Z

Y est une sorte de Xbar - bistro - brasserie - café - estaminet X

bar à vins Y

Hyponyme - hyperonyme

Relations sémantiquesX est une partie de Ymets - plat

repas

Y est une partie de Xpoiscaille - poisson

écaillenageoireligne latéraleouïe

Méronyme - holonyme

Relations sémantiques

contrairegagnant - vainqueur

perdant

Antonyme

WordNet

AnglaisVersion 3.0 : 120 000 synsetsMiller, 1995 - Fellbaum, 1998Le réseau sémantique le plus utilisé au mondeDéveloppement à partir de 1985 - Première

version 19914 sous-réseaux : noms, verbes, adjectifs,

adverbes

WordNet

Principales relations entre synsets

est un V/V exhale/breathe; inhale/breathe

est un N/N cat/felineinstance N/N Eiffel Tower/towerpartie N/N France/Europemembre N/N France/European Unionsimilaire A/A dying/moribund

WordNet

Principales relations entre lemmes

contraire A/A good/badappartenance A/N academic/academiaappartenance Adv/Aboastfully/boastfuldérivé N/V killing/killdérivé A/N dark/darkness

Hyperonymes

Le synset de breathe est un hyperonyme de ceux de exhale et inhale

Le synset de feline est un hyperonyme de celui de cat Un synset a souvent un seul synset hyperonyme,

mais peut en avoir plusieursExempleeat "manger" a deux hyperonymes :

eat "prendre un repas" (contestable)et consume/ingest/take in/take/have

Le synset de cat est un hyponyme de celui de feline

Hyperonymestimepiece/timekeeper/horologe

atomic clock

clock

sandglasssundial

timer

watch/ticker

ammonia clock

caesium clock

alarm clock/alarmegg timer

hourglass

chronograph

parking meter

stopwatch/stopo watch

...

...

Coordonnés

Coordonnés d'un synset : les synsets qui ont un même hyperonyme

Coordonnés de watch/tickeratomic clockclocksandglasssundialtimerLes coordonnés d'un synset ne sont pas directement

accessibles par les fonctions NLTK d'accès à WordNetRechercher les hyperonymes puis les hyponymes

Autres WordNets

• EuroWordNetFrançais (23 000 synsets), anglais, néerlandais,

italien, espagnol, allemand, tchèque, estonienLiens entre langues et avec l'anglais• BalkaNetTchèque, roumain, grec, turc, bulgare, serbe