stringtranslate.com

Transductor de estados finitos

Un transductor de estados finitos ( FST ) es una máquina de estados finitos con dos cintas de memoria , siguiendo la terminología de las máquinas de Turing : una cinta de entrada y una cinta de salida. Esto contrasta con un autómata de estados finitos ordinario , que tiene una sola cinta. Un FST es un tipo de autómata de estados finitos (FSA) que se asigna entre dos conjuntos de símbolos. [1] Un FST es más general que un FSA. Un FSA define un lenguaje formal al definir un conjunto de cadenas aceptadas, mientras que un FST define una relación entre conjuntos de cadenas.

Una FST leerá un conjunto de cadenas en la cinta de entrada y generará un conjunto de relaciones en la cinta de salida. Una FST puede considerarse como un traductor o un relacionador entre cadenas en un conjunto.

En el análisis morfológico , un ejemplo sería ingresar una cadena de letras en la FST, que luego generaría una cadena de morfemas .

Descripción general

Se puede decir que un autómata reconoce una cadena si vemos el contenido de su cinta como entrada. En otras palabras, el autómata calcula una función que asigna cadenas al conjunto {0,1}. Alternativamente, podemos decir que un autómata genera cadenas, lo que significa ver su cinta como una cinta de salida. En esta visión, el autómata genera un lenguaje formal , que es un conjunto de cadenas. Las dos visiones de los autómatas son equivalentes: la función que calcula el autómata es precisamente la función indicadora del conjunto de cadenas que genera. La clase de lenguajes generados por autómatas finitos se conoce como la clase de lenguajes regulares .

Las dos cintas de un transductor se consideran típicamente como una cinta de entrada y una cinta de salida. Desde este punto de vista, se dice que un transductor transduce (es decir, traduce) el contenido de su cinta de entrada a su cinta de salida, al aceptar una cadena en su cinta de entrada y generar otra cadena en su cinta de salida. Puede hacerlo de manera no determinista y puede producir más de una salida para cada cadena de entrada. Un transductor también puede no producir salida para una cadena de entrada dada, en cuyo caso se dice que rechaza la entrada. En general, un transductor calcula una relación entre dos lenguajes formales.

Cada transductor de estados finitos de cadena a cadena relaciona el alfabeto de entrada Σ con el alfabeto de salida Γ. Las relaciones R en Σ*×Γ* que se pueden implementar como transductores de estados finitos se denominan relaciones racionales . Las relaciones racionales que son funciones parciales , es decir, que relacionan cada cadena de entrada de Σ* con como máximo un Γ*, se denominan funciones racionales .

Los transductores de estados finitos se utilizan a menudo para el análisis fonológico y morfológico en la investigación y las aplicaciones del procesamiento del lenguaje natural . Entre los pioneros en este campo se incluyen Ronald Kaplan , Lauri Karttunen , Martin Kay y Kimmo Koskenniemi . [2] [ Se necesita una fuente no primaria ] Una forma común de utilizar transductores es en una denominada "cascada", donde los transductores para varias operaciones se combinan en un único transductor mediante la aplicación repetida del operador de composición (definido a continuación).

Construcción formal

Formalmente, un transductor finito T es una 6-tupla ( Q , Σ, Γ, I , F , δ ) tal que:

Podemos ver ( Q , δ ) como un grafo dirigido etiquetado , conocido como el grafo de transición de T : el conjunto de vértices es Q , y significa que hay una arista etiquetada que va del vértice q al vértice r . También decimos que a es la etiqueta de entrada y b la etiqueta de salida de esa arista.

NOTA: Esta definición de transductor finito también se denomina transductor de letras (Roche y Schabes 1997); son posibles definiciones alternativas, pero todas pueden convertirse en transductores siguiendo ésta.

Defina la relación de transición extendida como el conjunto más pequeño tal que:

La relación de transición extendida es esencialmente el cierre transitivo reflexivo del gráfico de transición que se ha ampliado para tener en cuenta las etiquetas de los bordes. Los elementos de se conocen como caminos . Las etiquetas de los bordes de un camino se obtienen concatenando en orden las etiquetas de los bordes de las transiciones que lo constituyen.

El comportamiento del transductor T es la relación racional [ T ] definida de la siguiente manera: si y solo si existe y tal que . Es decir, T transduce una cadena en una cadena si existe un camino desde un estado inicial a un estado final cuya etiqueta de entrada es x y cuya etiqueta de salida es y .

Autómatas ponderados

Los transductores de estados finitos pueden ser ponderados, donde cada transición se etiqueta con un peso además de las etiquetas de entrada y salida. Un transductor de estados finitos ponderado (WFST) sobre un conjunto K de pesos se puede definir de manera similar a uno no ponderado como una tupla de 8 T = ( Q , Σ, Γ, I , F , E , λ , ρ ) , donde:

Para que ciertas operaciones en WFST estén bien definidas, es conveniente exigir que el conjunto de pesos forme un semianillo . [3] Dos semianillos típicos utilizados en la práctica son el semianillo logarítmico y el semianillo tropical : los autómatas no deterministas pueden considerarse como si tuvieran pesos en el semianillo booleano . [4]

FST estocástico

Las FST estocásticas (también conocidas como FST probabilísticas o FST estadísticas) son presumiblemente una forma de FST ponderada. [ cita requerida ]

Operaciones en transductores de estados finitos

Las siguientes operaciones definidas en autómatas finitos también se aplican a los transductores finitos:

y no se cumple a menos que lo exijan ( k1 ) o ( k2 ).
Esta definición utiliza la misma notación que se utiliza en matemáticas para la composición de relaciones . Sin embargo, la lectura convencional para la composición de relaciones es al revés: dadas dos relaciones T y S , cuando existen algunas y tales que y
Dado un transductor T , existe un autómata finito tal que acepta x si y sólo si existe una cadena y para la cual
La segunda proyección se define de manera similar.

Propiedades adicionales de los transductores de estados finitos

Aplicaciones

Las FST se utilizan en la fase de análisis léxico de los compiladores para asociar el valor semántico con los tokens descubiertos. [13]

Las reglas de reescritura sensibles al contexto de la forma ab / c _ d , utilizadas en lingüística para modelar reglas fonológicas y cambios de sonido , son computacionalmente equivalentes a los transductores de estados finitos, siempre que la aplicación no sea recursiva, es decir, no se permite que la regla reescriba la misma subcadena dos veces. [14]

Las FST ponderadas encontraron aplicaciones en el procesamiento del lenguaje natural , incluida la traducción automática , y en el aprendizaje automático . [15] [16] Una implementación para el etiquetado de partes del discurso se puede encontrar como un componente de la biblioteca OpenGrm [17] .

Véase también

Notas

  1. ^ Jurafsky, Daniel (2009). Procesamiento del habla y del lenguaje . Pearson. ISBN 9789332518414.
  2. ^ Koskenniemi 1983
  3. ^ Berstel, Jean; Reutenauer, Christophe (2011). Series racionales no conmutativas con aplicaciones . Enciclopedia de matemáticas y sus aplicaciones. Vol. 137. Cambridge: Cambridge University Press . pág. 16. ISBN. 978-0-521-19022-0.Zbl 1250.68007  .
  4. ^ Lotario, M. (2005). Combinatoria aplicada a las palabras. Enciclopedia de Matemáticas y sus aplicaciones. vol. 105. Una obra colectiva de Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert , Sophie Schbath , Michael Waterman, Philippe Jacquet, Wojciech Szpankowski , Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche y Valérie Berthé . Cambridge: Prensa de la Universidad de Cambridge . pag. 211.ISBN 0-521-84802-4.Zbl 1133.68067  .
  5. ^ Boigelot, Bernard; Legay, Axel; Wolper, Pierre (2003). "Iteración de transductores en el gran formato". Verificación asistida por ordenador . Apuntes de clase sobre informática. Vol. 2725. Springer Berlin Heidelberg. págs. 223–235. doi :10.1007/978-3-540-45069-6_24. eISSN  1611-3349. ISBN 978-3-540-40524-5. ISSN  0302-9743.
  6. ^ Mohri 2004, págs. 3-5
  7. ^ "Determinación de transductores".
  8. ^ Mohri 2004, págs. 5-6
  9. ^ Allauzen y Mohri 2003
  10. ^ Mohri 2004, págs. 7-9
  11. ^ Mohri 2004, págs. 9-11
  12. ^ Griffiths 1968
  13. ^ Charles N. Fischer; Ron K. Cytron; Richard J. LeBlanc, Jr. (2010). "Escaneo: teoría y práctica". Elaboración de un compilador . Addison-Wesley. ISBN 978-0-13-606705-4.
  14. ^ "Modelos regulares de sistemas de reglas fonológicas" (PDF) . Archivado desde el original (PDF) el 11 de octubre de 2010 . Consultado el 25 de agosto de 2012 .
  15. ^ Kevin Knight; Jonathan May (2009). "Aplicaciones de los autómatas ponderados en el procesamiento del lenguaje natural". En Manfred Droste; Werner Kuich; Heiko Vogler (eds.). Manual de autómatas ponderados . Springer Science & Business Media. ISBN 978-3-642-01492-5.
  16. ^ "Aprendizaje con transductores ponderados" (PDF) . Consultado el 29 de abril de 2017 .
  17. ^ OpenGrm

Referencias

Enlaces externos

Lectura adicional