Histoire de transducteurs - Inria

Histoire de transducteursles charmes des transducteurs multibandes clos sous intersection

François Barthélemy

Alpage

15-16 novembre 2007

François Barthélemy (Alpage) Histoire de transducteurs 15-16 novembre 2007 1 / 29

Avant-propos

Maître de Conférences au Conservatoire National des Arts etMétiers.


Avant-propos

Maître de Conférences au Conservatoire National des Arts etMétiers.ne pas confondre :

Conservatoire National des Arts et Métiers (CNAM)Métro Arts et Métiers (Paris 3)Formation professionnelle d’adultes en cours du soir(DUT, Licence Générale, Diplôme Bac+4, Ingénieur)Ecole Nationale Supérieure des Arts et Métiers (ENSAM)Métro place d’Italie (Paris 13)Ecole d’ingénieur après prépas et concours (Gadz’Arts)


Avant-propos

Maître de Conférences au Conservatoire National des Arts etMétiers.ne pas confondre :

Conservatoire National des Arts et Métiers (CNAM)Métro Arts et Métiers (Paris 3)Formation professionnelle d’adultes en cours du soir(DUT, Licence Générale, Diplôme Bac+4, Ingénieur)Ecole Nationale Supérieure des Arts et Métiers (ENSAM)Métro place d’Italie (Paris 13)Ecole d’ingénieur après prépas et concours (Gadz’Arts)

membre de Atoll (Croap, Chloe) depuis 1989


La morphologie à états finis

Machines à états finismachines déterministes efficaces

représentation optimale obtenue automatiquement

opérations ensemblistes permettant la modularité (union,intersection) et la définition d’exceptions (différence).


La morphologie à états finis

Machines à états finismachines déterministes efficaces

représentation optimale obtenue automatiquement

opérations ensemblistes permettant la modularité (union,intersection) et la définition d’exceptions (différence).

Usage en morphologie informatiquetechnologie du milieu des années 80

utilisation de transducteurs pour mettre en relation des formes desurface avec des formes plus ou moins profondes.

morphologie à deux niveaux (Kimmo Koskenniemi) ex : PC-kimmo

règles de réécriture (Kaplan, Kay, Karttunnen) ex : XFST

nombreuses implémentations

nombreuses morphologies décrites.


Règles de réécriture

Mise en relation de formes complètes :(iN+manG+able, immangeable)

Formalisme sous-jacent : relations rationnelles

opération-clé : la composition (transformations successives)limitations :

homogénéïté des niveaux concret et abstraitpas de minimisation, déterminisation, intersection,complémentation, différence.


Morphologie à deux niveaux

Mise en relation de formes caractère par caractèrei :i N :m + :0 m :m a :a n :n G :g 0 :e + :0 a :a b :b l :l e :e(iN+manG0+able, im0mange0able)

Formalisme sous-jacent : relations rationnelles préservant lalongueur

Toutes opérations possibles, intersection privilégiéelimites

règles difficiles à comprendre et à mettre au pointhomogénéïté des niveaux concret et abstraitsimplémentations vieillotes


Propriété d’un bon modèle

pouvoir mettre en relation des représentations différentes.Exemple :([racine=mang,cat=V,temps=pres,num=sg,pers=1],mange)




pouvoir mettre en relation des sous-chaînes de longueur variable.Exemple : (e:e)(x:gs)(em:ã)(p:p)(l:l)(es:ǫ)





pouvoir mettre en relation plus de deux représentations.Exemple : graphie SMS, graphie standard, représentationphonétique, forme profonde.






pouvoir aligner de façon fine : plusieurs niveaux de granularité.graphie SMS t r a K C

graphie standard t r a c a ss erforme phonétique t R a k a s e






pouvoir aligner de façon fine : plusieurs niveaux de granularité.graphie SMS t r a K C

graphie standard t r a c a ss erforme phonétique t R a k a s e

pouvoir utiliser l’intersection et la différence ensembliste.


Plan de l’exposé

1 Introduction

2 Automates et transducteurs

3 Structures de traits

4 Implémentation

5 Conclusion


Rappels

un automate

0 1a

3

b

a

2c

ab


Rappels

un automate

0 1a

3

b

a

2c

ab

un transducteur

0 1a:x

3

b:y

a:x

2c:y

a:xb:x


Intersection

Propriétéles transducteurs ne sont pas clos sous intersection

(a : x)∗(b : ǫ)∗ ∩ (a : ǫ)∗(b : x)∗ = (a : x)n(b : ǫ)n


Intersection

Propriétéles transducteurs ne sont pas clos sous intersection

(a : x)∗(b : ǫ)∗ ∩ (a : ǫ)∗(b : x)∗ = (a : x)n(b : ǫ)n

Sous-classescertaines sous-classes sont closes sous intersection

Exemple 1 : transducteurs de lettre : chaque transition estétiquetée par exactement un symbole.

Exemple 2 : relation reconnaissable : il n’y a pas de boucle qui lisedes symboles des deux niveaux (produit cartésien de deuxlangage réguliers).

Ces transducteurs sont moins puissants : ils peuvent être vuscomme des automates déguisés en transducteurs.


Alignement, synchronisation et intersection

Idée : représenter la synchronisation de plusieurs représentationsau moyen de symboles spéciaux.




Exemple : alignement forme écrite-forme phonétique pour thigh(th,θ)(i,aI)(gh, )





Dans chacune des représentations, il y a un ordre total entresymboles :t < h < i < g < h θ < a < I





Dans chacune des représentations, il y a un ordre total entresymboles :t < h < i < g < h θ < a < IY a-t-il un ordre entre symboles de deux représentationsdifférentes ? Oui, mais un ordre partiel.

θ < imais i n’est ni avant ni après a et I


Représentation graphique de l’ordre

Ordre partiel :

t // h

��===

====

=// i // g // h

θ //

55jjjjjjjjjjjjjjjjjjjjj a // I

@@��


Représentation graphique de l’ordre

Ordre partiel :

t // h

��===

====

=// i // g // h

θ //

55jjjjjjjjjjjjjjjjjjjjj a // I

@@��

Insertion de points de synchronisation pour obtenir un treilli.

t // h

��???

????

? i

''NNNNNNNNNNNNNN g // h

��???

????

?

ω

??��

��???

????

? ω

��???

????

?

??��ω

??��ω

θ

77oooooooooooooo a // I

??��


De l’ordre partiel à une chaîneUn automate (resp. transducteur) reconnaît une chaîne desymboles.

De l’ordre partiel à une chaîneUn automate (resp. transducteur) reconnaît une chaîne desymboles.Etant donné un ordre partiel, plusieurs chaînes respectent cetordre partiel.

t // h

��???

????

? i


��???

????

?

ω

??��

��???

????

? ω

��???

????

?

??��ω

??��ω

θ


??��

ωthθωiaIωghω

ωtθhωiaIωghω

ωtθhωiIaωghω

ωtθhωIiaωghω

. . .


t // h

��???

????

? i


��???

????

?

ω

??��

��???

????

? ω

��???

????

?

??��ω

??��ω

θ


??��

ωthθωiaIωghω

ωtθhωiaIωghω

ωtθhωiIaωghω

ωtθhωIiaωghω

. . .Considérer toutes ces chaînes comme équivalentes.


t // h

��???

????

? i


��???

????

?

ω

??��

��???

????

? ω

��???

????

?

??��ω

??��ω

θ


??��

ωthθωiaIωghω

ωtθhωiaIωghω

ωtθhωiIaωghω

ωtθhωIiaωghω

. . .Considérer toutes ces chaînes comme équivalentes.⇒ langage de Trace de Mazurkiewicz

Langage de Trace de Mazurkiewicz

Monoïde partiellement commutatif :un alphabet finicertains symboles de l’alphabet peuvent commuter deux à deux(symboles indépendants) alors que d’autres non (symbolesdépendants).




trace : ensemble de chaînes équivalentes modulo commutation desymboles indépendants.





langage de trace : ensemble de trace





langage de trace : ensemble de trace

hiérarchie pour les langages de trace :reconnaissables ⊆ rationels ⊆ quelconques


Langage de trace et niveaux

Dans le cas de descriptions alignées, on appelera niveau oubande chacune des représentations.



Dans le cas de descriptions alignées, on appelera niveau oubande chacune des représentations.Relation de dépendance :

deux symboles du même niveau sont dépendant (commutationinterdite)deux symboles de deux niveaux différents sont indépendantsune symbole d’un niveau et ω sont dépendants



Dans le cas de descriptions alignées, on appelera niveau oubande chacune des représentations.Relation de dépendance :

deux symboles du même niveau sont dépendant (commutationinterdite)deux symboles de deux niveaux différents sont indépendantsune symbole d’un niveau et ω sont dépendants

Pour représenter plusieurs niveau de granularité, on utilise autantde symboles de synchronisation (ω) différents.


Langage de trace et niveaux (2)

Exemple :morph. desc. [type=root][cat=nom] [type=suffix][cat=adv]graphemes s h y l yphonemes

∫a I l I




∫a I l I

[type=root][cat=noun] ω2 [type=suffix][cat=adv] ω2

s h ω1 y ω1 ω2 l ω1 y ω1 ω2∫ω1 a I ω1 ω2 l ω1 I ω1 ω2




∫a I l I

[type=root][cat=noun] ω2 [type=suffix][cat=adv] ω2

s h ω1 y ω1 ω2 l ω1 y ω1 ω2∫ω1 a I ω1 ω2 l ω1 I ω1 ω2


Langage de trace reconnaissable

Si on écrit une expression régulière, cela définit un langage detrace rationnel.




Si l’on impose la restriction suivante : l’étoile de kleene (librerépétition) n’est permise que sur une chaîne contenant au moinsun point de synchronisation, on assure que le langage de traceobtenu est reconnaissable.





les langages de trace reconnaissables sont clos sous intersection.






un représentant canonique de chaque trace est sa forme normalelexicographique







pour un langage de trace reconnaissable, l’ensemble de seséléments en forme normale lexicographique est un langagerationnel.







pour un langage de trace reconnaissable, l’ensemble de seséléments en forme normale lexicographique est un langagerationnel.

il faut quelques précautions pour assurer le maintient de lapropriété de forme normale lexicographique à travers certainesopérations, notamment la concaténation et l’étoile.


Résumé sur les langages de trace

notion de niveau décrite par la relation d’indépendance




une propriété syntaxique sur l’étoile pour assurer la cloture sousintersection (et complémentation, différence)





la compilation en automate finis (possibilité de minimisation,déterminisation, etc)





la compilation en automate finis (possibilité de minimisation,déterminisation, etc)

décrit dans un article ACL 2007


Vision transducteur

langage de trace ≡ vision automate d’une description à plusieursniveaux.

une autre vision (ou interprétation) du même objet est utile pourdéfinir des opérations.


Vision transducteur : un exemple

Deux niveaux : graphémique, phonétique.



Deux niveaux : graphémique, phonétique.Forme normale lexicographique : les symboles de la formegraphémique sont plus petits que ceux de la forme phonétique.



Deux niveaux : graphémique, phonétique.Forme normale lexicographique : les symboles de la formegraphémique sont plus petits que ceux de la forme phonétique.Vision automate/langage de trace :

///.-,()*+tgraph

///.-,()*+hgraph

///.-,()*+φphon

///.-,()*+ω

///.-,()*+igraph

///.-,()*+

aphon��

/.-,()*+�� /.-,()*+

ωoo /.-,()*+

hgraph

oo /.-,()*+

ggraph

oo /.-,()*+

ωoo /.-,()*+

Iphon

oo



Deux niveaux : graphémique, phonétique.Forme normale lexicographique : les symboles de la formegraphémique sont plus petits que ceux de la forme phonétique.Vision automate/langage de trace :

///.-,()*+tgraph

///.-,()*+hgraph

///.-,()*+φphon

///.-,()*+ω

///.-,()*+igraph

///.-,()*+

aphon��

/.-,()*+�� /.-,()*+

ωoo /.-,()*+

hgraph

oo /.-,()*+

ggraph

oo /.-,()*+

ωoo /.-,()*+

Iphon

oo

Vision transducteur :

///.-,()*+t : ǫ

///.-,()*+h : ǫ

///.-,()*+ǫ : φ

///.-,()*+ω : ω

///.-,()*+i : ǫ

///.-,()*+

ǫ : a��

/.-,()*+�� /.-,()*+

ω : ωoo /.-,()*+

h : ǫ

oo /.-,()*+

g : ǫoo /.-,()*+

ω : ωoo /.-,()*+

ǫ : Ioo


Opérations sur les transducteurs

la projection : supression d’un ou plusieurs niveaux




la jointure relationnelle : deux machines ayant certains niveauxcommuns mais pas tous, intersection sur ces niveaux communs.





la même opération que la jointure naturelle dans les BDrelationnelles.





la même opération que la jointure naturelle dans les BDrelationnelles.

jointure implémentée par une variante de l’algorithmed’intersection d’automates.


Exemple de calcul

Système à trois niveaux : graphie SMS, graphie standard, phonétique.

un lexique à deux niveaux alignés (graphie standard etphonétique)


Exemple de calcul



un inventaire de tous les usages possibles d’une lettre ou d’uneséquence figée (exemple : ch, lol) dans une graphie SMS.

(k,<lettre>*,ka)|(k,k,<phoneme>)|...


Exemple de calcul





calculer les suites de signes en graphie SMS en appliquantl’opérateur * sur l’inventaire


Exemple de calcul






faire la jointure du résultat avec le lexique


Exemple de calcul






faire la jointure du résultat avec le lexique

cela donne un lexique de toutes les graphies SMS


Structures de traits et morphologie à états finis

Pratiquement tous les systèmes de description morphologiqueintégrent des structures de traits sous une forme ou une autre.



Pratiquement tous les systèmes de description morphologiqueintégrent des structures de traits sous une forme ou une autre.première approche : machine finie+traits évalués dynamiquement

machines finies : calculées statiquement, très efficace, partageoptimalstructures de traits : calculées dynamiquement, calcul couteux,aucun partagemariage de la carpe et du lapin



Pratiquement tous les systèmes de description morphologiqueintégrent des structures de traits sous une forme ou une autre.première approche : machine finie+traits évalués dynamiquement

machines finies : calculées statiquement, très efficace, partageoptimalstructures de traits : calculées dynamiquement, calcul couteux,aucun partagemariage de la carpe et du lapin

seconde approche : compiler les traits dans la machine finiesous forme de poids (Amtrup 2005)dans les chaînes version XFST : l’utilisateur écrit les opérations debas niveau sur les traitsdans les chaînes version Kiraz : usage stéréotypé des traitsmes travaux : formalisme de haut niveau, souple d’emploi


Structures de trait et alignement

proposition : mettre les structures de traits sur un ou plusieursniveaux spécifiques.




sur un niveau donné, possibilité de mettre plusieurs structuresconcaténées, alignées avec des portions de la forme graphique.Exemple : ([cat=adj], dur)([cat=adv/adj], ement)





Possibilité d’avoir plusieurs structures de traits avec des portéesdifférentes.






Possibilité de représenter des “grammaires d’unification” àstructure linéaire.







chaque couple chemin-valeur représenté par un symbolespécifique








précalcul du type de chaque structure









représentation des valeurs inconnues par des disjonctions depossibilités.









représentation des valeurs inconnues par des disjonctions depossibilités.

unification de structures = intersection de machine finie


Structures de trait : exemple

[nterm :pos=N]hhhhhhhhh

(((((((((

[nterm :pos=V]``````̀

[nterm :pos=Adj]

[term :pos=Adj,from=none]

real

[term :pos=V,from=Adj]

ize

[term :pos=N,from=V]

ation


Structures de trait : exemple

[nterm :pos=N]hhhhhhhhh

(((((((((

[nterm :pos=V]``````̀

[nterm :pos=Adj]

[term :pos=Adj,from=none]

real

[term :pos=V,from=Adj]

ize

[term :pos=N,from=V]

ation

Trois niveaux : structure de traits de forme, structure de trait de mor-phème, graphèmes.

([nterm :pos=Adj],[term :pos=Adj,from=none],real)(nterm :pos=V],[term :pos=V,from=Adj], ize)([nterm :pos=N],[term :pos=N,from=V], ation)


Paresse

travaux sur la compilation statique de structure de traits (TALN2007, FSMNLP 2007)


Paresse


problème : risque d’explosion de la taille des machines finies.


Paresse



notamment lorsque les trits expriment des dépendances à longuedistance.


Paresse




exemple : conjugaison de l’arabe, notation du nombre et de lapersonne dans un préfixe et un suffixe. Duplication des racines en9 exemplaires (un pour chaque valeur de nombre et personne).


Paresse





solution : retarder l’unification (paresse)


Paresse






mécanisme mis en place dans XFST avec les diacritiques


Paresse






mécanisme mis en place dans XFST avec les diacritiques

travail futur : définir un calcul paresseux des structures de traits


Prototype

prototype développé en Perl


Prototype

prototype développé en Perlutilisant des librairies de ATT

FSM (automates finis) : Riley, Mohry, PereiraLextools (expressions régulières) : Sproat


Prototype



quelques gros exemples et plus de petits (machines jusqu’à unmillion d’états environ).


Prototype




prototype non diffusé


Prototype





compilation en langage de trace implémentée


Prototype






structure de traits implémentées (avec quelques restrictions)


Prototype






structure de traits implémentées (avec quelques restrictions)

règles de réécriture contextuelle imparfaitement implémentées


Conclusion 1 : les apports

une formalisation de relations rationnelles permettant d’alignerdes représentations différentes




une bonne assise théorique





un calcul homogène (algèbre relationnel) qui unifie automates ettransducteurs à plusieurs bandes






les opérations (algèbre relationnelle) privilégiées au détriment dupouvoir expressif







motivée par des applications en linguistique







motivée par des applications en linguistique

implémentée


Conclusion 2 : travail théorique

meilleure formalisation des relations




formalisation de la paresse pour certaines opérations, notammentl’unification de structure de traits





permettre des structures de synchronisation non imbriquées (ex :syllabes et morphèmes)





permettre des structures de synchronisation non imbriquées (ex :syllabes et morphèmes)

définir un cadre de test des machines finies inspiré de ce quiexiste pour les langages de programmation


Conclusion 3 : travail pratique

Développement d’applicationsmorphologie flexionnelle du français : adapter une descriptiondéveloppée par Pierrette Bouillon sous Mmorph.




traducteur de nombre en toutes lettres français/finlandais sur labase de descriptions du finlandais (XFST, Karttunnen) et duFrançais (FSM, Sproat)





analyseur morphologique de néologismes en français(morphologie dérivationnelle productive)






Implémentationfixer une syntaxe







rendre le prototype suffisamment robuste pour commencer à lemontrer (démos)








réaliser un embryon d’environnement de développement








réaliser un embryon d’environnement de développement

passer de FSM à OpenFSTFrançois Barthélemy (Alpage) Histoire de transducteurs 15-16 novembre 2007 29 / 29

Documents

Histoire de transducteurs - Inria