[PDF] Etiquetage grammatical et analyse syntaxique par programmation

View - Download Etiquetage grammatical et analyse syntaxique par programmation

Previous PDF

Next PDF

Etiquetage grammatical et analyse syntaxique

par programmation dynamique

Matthieu Constant

Université Paris-Est Marne-la-Vallée, LIGM

EtiquetageAnalyse

Plan

Etiquetage grammatical

Analyse syntaxique

EtiquetageAnalyse

Plan

Etiquetage grammatical

Analyse syntaxique

EtiquetageAnalyse

Etiquetage grammatical

But Associer à une séquencew=w1...wkde mots, une séquencet =t1...tkd'étiquettes appartenant à un jeu d'étiquettesJ.

Point de vue probabiliste

Trouver la séquence la séquence d'étiquettesˆt qui maximise P(t|w)parmi l'ensemble des séquences d'étiquettes possibles. t =argmaxtP(t|w) =argmaxtP(w|t).P(t)

EtiquetageAnalyse

Modèle de Markov caché d'ordreN

Principe

Symbole visible : mot

Symbole caché à découvrir : étiquette

Hypothèses d'indépendance

Hypothèses de Markov pour le calcul deP(w|t).P(t) P(w|t)? un symbole observé (mot) ne dépend que dusymbole caché associé (étiquette) P(t)? un symbole caché (étiquette) ne dépend que de sesNprécédents

EtiquetageAnalyse

Modèle de Markov caché d'ordreN

Calcul deP(w|t)

P(w|t) =P(w1|t1).P(w2|t2).....P(wn|tn)

Calcul deP(t)pourN=1

P(t) =P(t1).P(t2|t1).P(t3|t2).....P(tn|tn-1)

Calcul deP(t)pourN=2

P(t) =P(t1).P(t2|t1).P(t3|t1t2).....P(tn|tn-2tn-1)

EtiquetageAnalyse

Estimation des probabilités

Corpus d'apprentissage

Le corpus utilisé pour l'apprentissage des probabilités debase est un corpus annoté : chaque token est associé à une catégorie grammaticale.

Calcul des probabilités d'émissionP(wi|ti)

P(wi|ti) =#occ(wi,ti)#occ(ti)

Calcul des probabilités de transitionsP(ti|ti-1)

P(ti|ti-1) =#occ(ti-1ti)#occ(ti-1)

EtiquetageAnalyse

Exemple (N=2)

On suppose queJ={X,Y} et que notre vocabulaire est {a,b,c}.

Probabilités d'émission

XY a1/106/10 b4/103/10 c5/101/10

Probabilités de transitions

XY

X7/104/10

Y3/106/10

EtiquetageAnalyse

Décodage : trouver la séquence d'étiquettes la plus probable

Première solution (naïve)

Calculer la probabilité de chacune des séquences d'étiquettes possibles.

Seconde solution

Application de l'algorithme de Viterbi (programmation dynamique)

EtiquetageAnalyse

Treillis de la phrase

Principe

Le treillis de la phrase représente sous la forme de graphe toutes les séquences d'étiquettes possibles, pour une séquence donnée de mots. Un noeud correspond à une

étiquette possible.

Noeud initial :

start

Exemple pour la séquence de motsacba

acba XX YY X Y X Y start

EtiquetageAnalyse

Pondération du treillis

On pondère respectivement les noeuds et les arcs par lesprobabilités d'émission et de transition

cas particulier : P(start) = 1, les arcs (start,x) sontpondérés par P(x); ex. P(X)=0.6 et P(Y)=0.4

acba

X/0.1X/0.5

0.7 Y/0.1 0.3

Y/0.60.4

0.6 X/0.4 0.7 Y/0.3 0.3 0.4 0.6

X/0.10.7

Y/0.6 0.3 0.4 0.6 start 0.6 0.4

EtiquetageAnalyse

Décodage par programmation dynamique

Trouver la séquence d'étiquettes la plus probable La probabilité d'un chemin du treillis est le produit despoids du chemin

Trouver le chemin le plus probable

Algorithme de Viterbi

Algorithme itératif

A chaque étape (mot i), on se sert des calculs faits àl'étape précédente (moti-1)

Remplissage itératif d'une matrice (ligne=étiquette;colonne=mot) colonne par colonne en partant de lapremière et en terminant par la dernière

EtiquetageAnalyse

Algorithme de Viterbi

Notations

wimot à l'indicei(colonnei) tjétiquette à la lignej Proba[j,i] : probabilité maximale d'accéder au noeud (j,i)du treillis en partant du noeud start

Récurrence pouri>1

Proba[j,i] =maxk(Proba[k,i-1].P(tj|tk).P(wi|tj))

On garde en mémoire (dansBack[j,i]) l'étiquettetkqui a permis de maximiserProba[j,i].

EtiquetageAnalyse

Algorithme de Viterbi (suite)

Initialisation (i=1)

Proba[1,j]= P(tj).P(w1|tj)

Procédure finale

Une fois la matrice remplie, on retrouve le chemin qui a donné la probabilité maximale dans la dernière colonne deProbaet on en déduit le chemin de l'automate des transitions correspondant grâce à la matriceBack.

EtiquetageAnalyse

Exercice : trouver la séquence d'étiquettes la plus probable pouracbaavecP(X) =0.6etP(Y) =0.4.

Probabilités d'émission

XY a1/106/10 b4/103/10 c5/101/10

Probabilités de transitions

XY

X7/104/10

Y3/106/10

EtiquetageAnalyse

Plan

Etiquetage grammatical

Analyse syntaxique

EtiquetageAnalyse

Analyse syntaxique

Parsing

Entrées : une phrase étiquetée et une grammairealgébrique Sorties : les ou les arbres de dérivation de la phrase

Algorithmes

Descendants

Ascendants

Programmation dynamique (aujourd'hui)

EtiquetageAnalyse

Exemple de grammaire

P→GN Det→tous les

P→GN Det→toutes les

P→GN GN N→

P→GN GN N→

GN→Det N N→

GN→Npr N→

Det→ Npr→Luc

Det→ Npr→Anne

Det→

Exercice :Donner les arbres dérivés de l'application de cette grammaire sur les phrases : (1)La corruption empire; (2)Luc aime toutes les mélodies

EtiquetageAnalyse

Algorithme d'Earley (1970)

Programmation dynamique

On sauvegarde dans un tableau tous les résultats intermédiaires réutilisables

Principe

Analyse descendante

On a un tableau indicé par les tokens de la phrase

Pour chaque indice, le tableau contient un ensemble desous-arbres correspondant à des analyses partielles

On remplit le tableau de gauche à droite, sans retours enarrière On ne détruit jamais les sous-arbres déjà créés Pour contruire les arbres de dérivation, on combine lessous-arbres du tableau

EtiquetageAnalyse

Les sous-arbres

Définition

Un sous-arbre est représenté par un triplet : une règle pointée (le point indique jusqu'où on a analysédans la règle)

deux positions dans la phrase, correspondant au début del'application de la règle et au point jusqu'où on a analysédans la phrase

Règle pointée complétée

Règle dont le point est à la fin

EtiquetageAnalyse

Algorithme

Principe

Parcours du tableau de gauche à droite

Pour chaque indicei, on parcourt les sous-arbres et on crée de nouveaux sous-arbres à l'indicei(queue FIFO) et

à l'indicei+1

Initialisation

On suppose que l'axiome de la grammaire apparaît une seule fois, dans une règle P0→P A l'indice 0, on met le sous-arbre (P0→.P,0,0)

Terminaison

On vérifie qu'à l'indicen(nombre de tokens de la phrase), on a le sous-arbre (P0→P.,0,n)

EtiquetageAnalyse

Trois opérations

Vérifier : scan(A→u.tv,i,j)

ift correspond à token[j]then table[j+1].enqueue(A→ut.v,i,j+1) end if

Prédire : predict(A→u.Bv,i,j)

for all(B→w) in rules(B)do table[j].enqueue(B→.w,j,j) end for

Compléter : complete(B→w.,j,k)

for all(A→u.Bv,i,j) in table[j]do table[k].enqueue(A→uB.v,i,k) end for

EtiquetageAnalyse

Algorithme

table[0].enqueue(P0→.P,0,0) for alli from 0 to ndo for allsubTree in table[i]do ifsubTree.isComplete()then complete(subTree) else ifsubTree.nextSymbol() is terminalthen scan(subTree) else predict(subTree) end if end if end for end for iftable[n].contains(P0→P.,0,n)then constructTrees(n) end if

EtiquetageAnalyse

Exercice

Soit la grammaire

P→XY

Y→WZ

Z→VY

V→a

W→b

X→c

Y→d

Dérouler l'algorithme de Earley pour l'application de cette grammaire sur la séquencecaadbb.quotesdbs_dbs43.pdfusesText_43

[PDF] taylor xcas

[PDF] les indices de l'énonciation dans un texte pdf

[PDF] outils grammaticaux et lexicaux

[PDF] total en pourcentage excel

[PDF] outils grammaticaux français

[PDF] la répartition des hommes et des femmes par métiers

[PDF] les outils grammaticaux

[PDF] métiers hommes femmes

[PDF] outils grammaticaux definition

[PDF] indice textuel definition

[PDF] insee observatoire des inégalités

[PDF] grille horaire bac pro

[PDF] grille horaire hebdomadaire bac pro 3 ans

[PDF] grille horaire bac pro commerce

[PDF] grille horaire bac pro cuisine