Transducteur à l'état fini - Finite-state transducer

Un transducteur à états finis ( FST ) est une machine à états finis avec deux bandes mémoire , suivant la terminologie des machines de Turing : une bande d'entrée et une bande de sortie. Cela contraste avec un automate à états finis ordinaire , qui a une seule bande. Un FST est un type d'automate à états finis (FSA) qui établit une correspondance entre deux ensembles de symboles. Un FST est plus général qu'un FSA. Un FSA définit un langage formel en définissant un ensemble de chaînes acceptées, tandis qu'un FST définit des relations entre des ensembles de chaînes.

Un FST lira un ensemble de chaînes sur la bande d'entrée et générera un ensemble de relations sur la bande de sortie. Un FST peut être considéré comme un traducteur ou un lien entre les chaînes d'un ensemble.

Dans l'analyse morphologique, un exemple serait d'entrer une chaîne de lettres dans le FST, le FST produirait alors une chaîne de morphèmes .

Aperçu

Vidéo externe
Transducteurs à états finis // Karlsruhe Institute of Technology , vidéo YouTube

On peut dire qu'un automate reconnaît une chaîne si nous considérons le contenu de sa bande comme entrée. En d'autres termes, l'automate calcule une fonction qui mappe les chaînes dans l'ensemble {0,1}. Alternativement, on peut dire qu'un automate génère des chaînes, ce qui revient à considérer sa bande comme une bande de sortie. Sur cette vue, l'automate génère un langage formel , qui est un ensemble de chaînes. Les deux vues des automates sont équivalentes : la fonction que l'automate calcule est précisément la fonction indicatrice de l'ensemble des chaînes qu'il génère. La classe des langages générés par les automates finis est connue sous le nom de classe des langages réguliers .

Les deux bandes d'un transducteur sont généralement considérées comme une bande d'entrée et une bande de sortie. De ce point de vue, un transducteur est censé transduire (c'est-à-dire traduire) le contenu de sa bande d'entrée vers sa bande de sortie, en acceptant une chaîne sur sa bande d'entrée et en générant une autre chaîne sur sa bande de sortie. Il peut le faire de manière non déterministe et il peut produire plus d'une sortie pour chaque chaîne d'entrée. Un transducteur peut également ne produire aucune sortie pour une chaîne d'entrée donnée, auquel cas il est dit qu'il rejette l'entrée. En général, un transducteur calcule une relation entre deux langages formels.

Chaque transducteur à états finis chaîne à chaîne relie l'alphabet d'entrée à l'alphabet de sortie . Les relations R sur Σ*×Γ* qui peuvent être implémentées comme des transducteurs à états finis sont appelées relations rationnelles . Les relations rationnelles qui sont des fonctions partielles , c'est-à-dire qui relient chaque chaîne d'entrée de Σ* à au plus un Γ*, sont appelées fonctions rationnelles .

Les transducteurs à états finis sont souvent utilisés pour l' analyse phonologique et morphologique dans la recherche et les applications en traitement du langage naturel . Parmi les pionniers dans ce domaine figurent Ronald Kaplan , Lauri Karttunen , Martin Kay et Kimmo Koskenniemi . Une manière courante d'utiliser des transducteurs est ce qu'on appelle une « cascade », où les transducteurs pour diverses opérations sont combinés en un seul transducteur par application répétée de l'opérateur de composition (défini ci-dessous).

Construction formelle

Formellement, un transducteur fini T est un 6-uplet ( Q , Σ, Γ, I , F , δ ) tel que :

• Q est un ensemble fini , l'ensemble des états ;
• Σ est un ensemble fini, appelé alphabet d'entrée ;
• Γ est un ensemble fini, appelé alphabet de sortie ;
• I est un sous - ensemble de Q , l'ensemble des états initiaux ;
• F est un sous-ensemble de Q , l'ensemble des états finaux ; et
• ${\displaystyle \delta \subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q}$(où ε est la chaîne vide ) est la relation de transition .

On peut voir ( Q , δ ) comme marqué graphe orienté , connu sous le graphe de transition de T : l'ensemble des sommets est Q , et signifie qu'il y a un avantage marqué allant de sommet q à sommet r . On dit aussi que a est l' étiquette d'entrée et b l' étiquette de sortie de cette arête. ${\style d'affichage (q,a,b,r)\in \delta }$

REMARQUE : Cette définition de transducteur fini est également appelée transducteur de lettres (Roche et Schabes 1997) ; des définitions alternatives sont possibles, mais peuvent toutes être converties en transducteurs suivant celle-ci.

Définissez la relation de transition étendue comme le plus petit ensemble tel que : ${\displaystyle \delta ^{*}}$

• ${\displaystyle \delta \subseteq \delta ^{*}}$;
• ${\displaystyle (q,\epsilon ,\epsilon ,q)\in \delta ^{*}}$pour tous ; et${\style d'affichage q\dans Q}$
• quand et puis .${\style d'affichage (q,x,y,r)\in \delta ^{*}}$${\style d'affichage (r,a,b,s)\in \delta }$${\displaystyle (q,xa,yb,s)\in \delta ^{*}}$

La relation de transition étendue est essentiellement la fermeture transitive réflexive du graphe de transition qui a été augmentée pour prendre en compte les étiquettes d'arêtes. Les éléments de sont appelés chemins . Les étiquettes de bord d'un chemin sont obtenues en concaténant les étiquettes de bord de ses transitions constitutives dans l'ordre. ${\displaystyle \delta ^{*}}$

Le comportement du transducteur T est la relation rationnelle [ T ] définie comme suit : si et seulement s'il existe et tel que . C'est-à-dire que T transduit une chaîne en une chaîne s'il existe un chemin d'un état initial à un état final dont l'étiquette d'entrée est x et dont l'étiquette de sortie est y . ${\style d'affichage x[T]y}$ ${\displaystyle i\in I}$${\style d'affichage f\dans F}$${\style d'affichage (i,x,y,f)\in \delta ^{*}}$${\displaystyle x\in \Sigma ^{*}}$${\displaystyle y\in \Gamma ^{*}}$

Automates pondérés

Les transducteurs à états finis peuvent être pondérés, chaque transition étant étiquetée avec un poids en plus des étiquettes d'entrée et de sortie. A pondéré Finite State Transducteur (WFST) sur un ensemble K de poids peut être définie de manière similaire à une quelconque non pondérée en tant que 8-uplet T = ( Q , Σ, Γ, I , F , E , λ , ρ ) , où:

• Q , , , I , F sont définis comme ci-dessus;
• ${\displaystyle E\subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q\times K}$(où ε est la chaîne vide ) est l'ensemble fini de transitions ;
• ${\displaystyle \lambda :I\rightarrow K}$ mappe les états initiaux aux poids ;
• ${\displaystyle \rho :F\rightarrow K}$ mappe les états finaux aux poids.

Afin de bien définir certaines opérations sur les WFST, il est pratique d'exiger que l'ensemble de poids forme un demi - anneau . Deux semi-anneaux typiques utilisés dans la pratique sont le semi - anneau log et le semi - anneau tropical : les automates non déterministes peuvent être considérés comme ayant des poids dans le semi-anneau booléen .

FST stochastique

Les FST stochastiques (également appelés FST probabilistes ou FST statistiques) sont vraisemblablement une forme de FST pondérée.

Opérations sur les transducteurs à états finis

Les opérations suivantes définies sur les automates finis s'appliquent également aux transducteurs finis :

• Syndicat . Etant donné les transducteurs T et S , il existe un transducteur tel que si et seulement si ou .${\displaystyle T\cup S}$${\displaystyle x[T\cup S]y}$${\style d'affichage x[T]y}$${\style d'affichage x[S]y}$
• Concaténation . Etant donné les transducteurs T et S , il existe un transducteur tel que si et seulement s'il existe avec et${\displaystyle T\cdot S}$${\displaystyle x[T\cdot S]y}$${\style d'affichage x_{1},x_{2},y_{1},y_{2}}$${\displaystyle x=x_{1}x_{2},y=y_{1}y_{2},x_{1}[T]y_{1}}$${\displaystyle x_{2}[S]y_{2}.}$
• Fermeture Kleene . Etant donné un transducteur T , il existe un transducteur ayant les propriétés suivantes :${\displaystyle T^{*}}$

${\displaystyle \epsilon [T^{*}]\epsilon }$;

( k1 )

si et , alors ;${\displaystyle w[T^{*}]y}$${\style d'affichage x[T]z}$${\displaystyle wx[T^{*}]yz}$

( k2 )

et ne tient pas sauf si mandaté par ( k1 ) ou ( k2 ).${\style d'affichage x[T^{*}]y}$

• Compositions . Etant donné un transducteur T sur les alphabets Σ et Γ et un transducteur S sur les alphabets Γ et Δ, il existe un transducteur sur Σ et tel que si et seulement s'il existe une chaîne telle que et . Cette opération s'étend au cas pondéré.${\displaystyle T\circ S}$${\style d'affichage x[T\circ S]z}$${\displaystyle y\in \Gamma ^{*}}$${\style d'affichage x[T]y}$${\style d'affichage y[S]z}$

Cette définition utilise la même notation utilisée en mathématiques pour la composition des relations . Cependant, la lecture conventionnelle de la composition des relations est l'inverse : étant donné deux relations T et S , lorsqu'il existe un y tel que et${\style d'affichage (x,z)\in T\circ S}$${\style d'affichage (x,y)\dans S}$${\style d'affichage (y,z)\dans T.}$

• Projection sur un automate. Il existe deux fonctions de projection : conserve la bande d'entrée et conserve la bande de sortie. La première projection, est définie comme suit :${\style d'affichage \pi _{1}}$${\style d'affichage \pi _{2}}$${\style d'affichage \pi _{1}}$

Etant donné un transducteur T , il existe un automate fini tel qu'il accepte x si et seulement s'il existe une chaîne y pour laquelle${\displaystyle \pi _{1}T}$${\displaystyle \pi _{1}T}$${\style d'affichage x[T]y.}$

La deuxième projection est définie de la même manière.${\style d'affichage \pi _{2}}$

• Détermination . Étant donné un transducteur T , nous voulons construire un transducteur équivalent qui a un état initial unique et tel que deux transitions quittant un état ne partagent pas la même étiquette d'entrée. La construction du powerset peut être étendue aux transducteurs, ou même aux transducteurs pondérés, mais ne parvient parfois pas à s'arrêter ; en effet, certains transducteurs non déterministes n'admettent pas de transducteurs déterministes équivalents. Des caractérisations de transducteurs déterminables ont été proposées ainsi que des algorithmes efficaces pour les tester : elles reposent sur le semi - anneau utilisé dans le cas pondéré ainsi qu'une propriété générale sur la structure du transducteur (la propriété des jumeaux ).
• Poids poussant pour le cas lesté.
• Minimisation pour le cas pondéré.
• Suppression des transitions epsilon .

Propriétés supplémentaires des transducteurs à états finis

• Il est décidable si la relation [ T ] d'un transducteur T est vide.
• On peut décider s'il existe une chaîne y telle que x [ T ] y pour une chaîne donnée x .
• Il est indécidable si deux transducteurs sont équivalents. L'équivalence est cependant décidable dans le cas particulier où la relation [ T ] d'un transducteur T est une fonction (partielle).
• Si l'on définit l'alphabet des étiquettes , les transducteurs à états finis sont isomorphes à NDFA sur l'alphabet , et peuvent donc être déterminés (transformés en automates finis déterministes sur l'alphabet ) et par la suite minimisés afin qu'ils aient le nombre minimum d'états.${\displaystyle L=(\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})}$${\style d'affichage L}$${\displaystyle L=[(\Sigma \cup \{\epsilon \})\times \Gamma ]\cup [\Sigma \times (\Gamma \cup \{\epsilon \})]}$

Applications

Les règles de réécriture contextuelles de la forme a → b / c _ d , utilisées en linguistique pour modéliser les règles phonologiques et le changement de son , sont équivalentes en calcul aux transducteurs à états finis, à condition que l'application soit non récursive, c'est-à-dire que la règle ne soit pas autorisée à réécrire la même sous-chaîne deux fois.

Les FST pondérés ont trouvé des applications dans le traitement du langage naturel , y compris la traduction automatique , et dans l'apprentissage automatique . Une implémentation pour le balisage des parties du discours peut être trouvée en tant que composant de la bibliothèque OpenGrm.

Voir également

• Machine à farine
• Machine de Moore
• Dictionnaire morphologique
• foma (logiciel)
• Arbre transducteur

Remarques

Les références

Liens externes

• OpenFst , une bibliothèque open source pour les opérations FST.
• Outils de transducteur à état fini de Stuttgart , une autre boîte à outils FST open source
• java FST Framework , un framework java FST open source capable de gérer le format de texte OpenFst.
• Vcsn , une plate-forme open-source (C++ & IPython) pour les automates pondérés et les expressions rationnelles.
• Morphologie à états finis--Le livre XFST/LEXC, une description de la mise en œuvre par Xerox de transducteurs à états finis destinés à des applications linguistiques.
• FOMA , une implémentation open source de la plupart des fonctionnalités de l'implémentation Xerox XFST/LEXC.

Lectures complémentaires

• Jurafsky, Daniel ; James H. Martin (2000). Traitement de la parole et du langage . Prentice Hall. pp.  71 -83. ISBN 0-13-095069-6.
• Kornaï, Andras (1999). Modèles de langage à états finis étendus . La presse de l'Universite de Cambridge. ISBN 0-521-63198-X.
• Roche, Emmanuel; Yves Schabès (1997). Traitement du langage à l'état fini . Presse MIT. p.  1 –65. ISBN 0-262-18182-7.
• Beesley, Kenneth R.; Lauri Karttunen (2003). Morphologie des états finis . Centre d'étude du langage et de l'information. ISBN 1-57586-434-7.
• Roark, Brian ; Richard Sproat (2007). Approches computationnelles de la morphologie et de la syntaxe . Presses de l'Université d'Oxford. ISBN 978-0-19-927478-9.
• Berstel, Jean (1979). Transductions et langages sans contexte . Teubner Verlag.. Version PDF gratuite