Un transductor de estado finito ( FST ) es una máquina de estado finito 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 estado finito ordinario , que tiene una sola cinta. Un FST es un tipo de autómata de estado finito que se asigna entre dos conjuntos de símbolos. [1] Un FST es más general que un autómata de estado finito (FSA). Una FSA define un lenguaje formal mediante la definición de un conjunto de cadenas aceptadas, mientras que una FST define las relaciones entre conjuntos de cadenas.
Un FST leerá un conjunto de cadenas en la cinta de entrada y generará un conjunto de relaciones en la cinta de salida. Se puede pensar en un FST como un traductor o un relator entre cadenas de un conjunto.
En el análisis morfológico, un ejemplo sería ingresar una cadena de letras en el FST, el FST luego generaría una cadena de morfemas .
Descripción general
Video externo | |
---|---|
Transductores de estado finito // Instituto de Tecnología de Karlsruhe , video de YouTube |
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 mapea cadenas en el conjunto {0,1}. Alternativamente, podemos decir que un autómata genera cadenas, lo que significa ver su cinta como una cinta de salida. Desde este punto de vista, el autómata genera un lenguaje formal , que es un conjunto de cadenas. Las dos vistas 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 ven típicamente como una cinta de entrada y una cinta de salida. En esta vista, se dice que un transductor transduce (es decir, traduce) el contenido de su cinta de entrada a su cinta de salida, aceptando una cadena en su cinta de entrada y generando otra cadena en su cinta de salida. Puede hacerlo de forma 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 estado finito 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 estado finito se denominan relaciones racionales . Las relaciones racionales que son funciones parciales , es decir, que relacionan cada cadena de entrada desde Σ * hasta como máximo una Γ *, se denominan funciones racionales .
Los transductores de estado finito se utilizan a menudo para análisis fonológico y morfológico en la investigación y aplicaciones del procesamiento del lenguaje natural . Los pioneros en este campo incluyen a Ronald Kaplan , Lauri Karttunen , Martin Kay y Kimmo Koskenniemi . [2] [se necesita fuente no primaria ] Una forma común de usar transductores es en una llamada "cascada", donde los transductores para varias operaciones se combinan en un solo 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 tupla de 6 ( Q , Σ, Γ, I , F , δ ) tal que:
- Q es un conjunto finito , el conjunto de estados ;
- Σ es un conjunto finito, llamado alfabeto de entrada ;
- Γ es un conjunto finito, llamado alfabeto de salida ;
- I es un subconjunto de Q , el conjunto de estados iniciales ;
- F es un subconjunto de Q , el conjunto de estados finales ; y
- (donde ε es la cadena vacía ) es la relación de transición .
Podemos ver ( Q , δ ) como un gráfico dirigido etiquetado , conocido como el gráfico de transición de T : el conjunto de vértices es Q , ysignifica que hay una arista etiquetada que va del vértice q al vértice r . También se dice que una es la etiqueta de entrada y b la etiqueta de salida de ese borde.
NOTA: Esta definición de transductor finito también se denomina transductor de letras (Roche y Schabes 1997); Son posibles definiciones alternativas, pero todas se pueden convertir en transductores siguiendo esta.
Definir la relación de transición extendida como el conjunto más pequeño tal que:
- ;
- para todos ; y
- cuando sea y luego .
La relación de transición extendida es esencialmente el cierre transitivo reflexivo del gráfico de transición que se ha aumentado para tener en cuenta las etiquetas de los bordes. Los elementos dese conocen como caminos . Las etiquetas de borde de una ruta se obtienen concatenando las etiquetas de borde de sus transiciones constituyentes en orden.
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 que T transduce una cuerda en una cuerda si existe una ruta 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 estado finito se pueden ponderar, donde cada transición está etiquetada con un peso además de las etiquetas de entrada y salida. Un transductor de estado finito 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:
- Q , Σ, Γ, I , F se definen como antes;
- (donde ε es la cadena vacía ) es el conjunto finito de transiciones;
- asigna estados iniciales a pesos;
- asigna los estados finales a los pesos.
Para que ciertas operaciones en WFST estén bien definidas, es conveniente requerir el conjunto de pesos para formar un semiring . [3] Dos semireados típicos que se utilizan en la práctica son el semirrígido logarítmico y el semirrígido tropical : se puede considerar que los autómatas no deterministas tienen pesos en el semirrígido booleano . [4]
FST estocástico
Los FST estocásticos (también conocidos como FST probabilísticos o FST estadísticos) son presumiblemente una forma de FST ponderada. [ cita requerida ]
Operaciones en transductores de estado finito
Las siguientes operaciones definidas en autómatas finitos también se aplican a transductores finitos:
- Unión . Dados los transductores T y S , existe un transductor tal que si y solo si o .
- Concatenación . Dados los transductores T y S , existe un transductor tal que si y solo si existen con y
- Cierre de Kleene . Dado un transductor T , existe un transductor con las siguientes propiedades:
- ;
( k1 )
- Si y , luego ;
( k2 )
- Composición . Dado un transductor T en los alfabetos Σ y Γ y un transductor S en los alfabetos Γ y Δ, existe un transductor en Σ y Δ tal que si y solo si existe una cadena tal que y . Esta operación se extiende al caso ponderado. [5]
- Esta definición utiliza la misma notación utilizada 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 exista alguna y tal que y
- Proyección a un autómata. Hay dos funciones de proyección: conserva la cinta de entrada, y conserva la cinta de salida. La primera proyección, se define de la siguiente manera:
- Dado un transductor T , existe un autómata finito tal que acepta x si y solo si existe una cadena y para la cual
- La segunda proyección, se define de manera similar.
- Determinación . Dado un transductor T , queremos construir un transductor equivalente que tenga un estado inicial único y tal que no haya dos transiciones que salgan de cualquier estado y compartan la misma etiqueta de entrada. La construcción del conjunto de energía puede extenderse a transductores, o incluso a transductores ponderados, pero a veces no se detiene; de hecho, algunos transductores no deterministas no admiten transductores deterministas equivalentes. [6] Se han propuesto caracterizaciones de transductores determinizables [7] junto con algoritmos eficientes para probarlos: [8] se basan en el semiringuito utilizado en el caso ponderado, así como en una propiedad general sobre la estructura del transductor (la propiedad de los gemelos ).
- Peso empujando para la caja ponderada. [9]
- Minimización para el caso ponderado. [10]
- Eliminación de transiciones épsilon .
Propiedades adicionales de los transductores de estado finito
- Es decidible si la relación [ T ] de un transductor T está vacía.
- Es decidible si existe una cadena y tal que x [ T ] y para una cadena x dada .
- Es indecidible si dos transductores son equivalentes. [11] Sin embargo, la equivalencia es decidible en el caso especial en el que la relación [ T ] de un transductor T es una función (parcial).
- Si uno define el alfabeto de las etiquetas , los transductores de estado finito son isomorfos a NDFA sobre el alfabeto, y por lo tanto puede determinarse (convertirse en autómatas finitos deterministas sobre el alfabeto) y posteriormente minimizados para que tengan el número mínimo de estados. [ cita requerida ]
Aplicaciones
Las reglas de reescritura sensibles al contexto de la forma a → b / c _ d , utilizadas en lingüística para modelar las reglas fonológicas y el cambio de sonido , son computacionalmente equivalentes a los transductores de estado finito, siempre que la aplicación no sea recursiva, es decir, no se permite la reescritura de la regla. la misma subcadena dos veces. [12]
Los FST ponderados encontraron aplicaciones en el procesamiento del lenguaje natural , incluida la traducción automática , y en el aprendizaje automático . [13] [14] Se puede encontrar una implementación para el etiquetado de parte del discurso como un componente de la biblioteca OpenGrm [15] .
Ver también
- Máquina harinosa
- Máquina de moore
- Diccionario morfológico
- foma (software)
- Transductor de árbol
Notas
- ^ Jurafsky, Daniel (2009). Procesamiento del habla y el lenguaje . Pearson. ISBN 9789332518414.
- ^ Koskenniemi 1983
- ^ Berstel, Jean; Reutenauer, Christophe (2011). Serie racional no conmutativa con aplicaciones . Enciclopedia de las matemáticas y sus aplicaciones. 137 . Cambridge: Cambridge University Press . pag. 16. ISBN 978-0-521-19022-0. Zbl 1250.68007 .
- ^ Lothaire, M. (2005). Combinatoria aplicada sobre palabras . Enciclopedia de las matemáticas y sus aplicaciones. 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: Cambridge University Press . pag. 211 . ISBN 0-521-84802-4. Zbl 1133.68067 .
- ^ Mohri 2004 , págs. 3-5
- ^ "Determinación de transductores" .
- ^ Mohri 2004 , págs. 5-6
- ^ Allauzen 2003
- ^ Mohri 2004 , págs. 7-9
- ^ Mohri 2004 , págs. 9-11
- ^ Griffiths 1968
- ^ "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 .
- ^ Kevin Knight y 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.Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ "Aprendizaje con transductores ponderados" (PDF) . Consultado el 29 de abril de 2017 .
- ^ OpenGrm
Referencias
- Allauzen, Cyril; Mohri, Mehryar (2003). "Algoritmos eficientes para probar la propiedad de los gemelos" (PDF) . Revista de Autómatas, Idiomas y Combinatoria . 8 (2): 117-144.
- Koskenniemi, Kimmo (1983), Morfología de dos niveles: un modelo computacional general de reconocimiento y producción de formas de palabras (PDF) , Departamento de Lingüística General, Universidad de Helsinki
- Mohri, Mehryar (2004). "Algoritmos de transductor de estado finito ponderado: una descripción general" (PDF) . Idiomas y aplicaciones formales . Estudios en Fuzziness y Soft Computing. 148 (620): 551–564. doi : 10.1007 / 978-3-540-39886-8_29 . ISBN 978-3-642-53554-3.
- Griffiths, TV (1968). "La insolubilidad del problema de equivalencia para máquinas generalizadas no deterministas libres de Λ". 15 (3). ACM: 409–413. Cite journal requiere
|journal=
( ayuda )
enlaces externos
- OpenFst , una biblioteca de código abierto para operaciones FST.
- Stuttgart Finite State Transducer Tools , otro conjunto de herramientas FST de código abierto
- java FST Framework , un Java FST Framework de código abierto capaz de manejar el formato de texto OpenFst.
- Vcsn , una plataforma de código abierto (C ++ e IPython) para autómatas ponderados y expresiones racionales.
- Morfología de estado finito: el libro XFST / LEXC, una descripción de la implementación de Xerox de transductores de estado finito destinados a aplicaciones lingüísticas.
- FOMA , una implementación de código abierto de la mayoría de las capacidades de la implementación Xerox XFST / LEXC.
Otras lecturas
- Jurafsky, Daniel ; James H. Martin (2000). Procesamiento del habla y el lenguaje . Prentice Hall. págs. 71 –83. ISBN 0-13-095069-6.
- Kornai, Andras (1999). Modelos de lenguaje de estados finitos extendidos . Prensa de la Universidad de Cambridge. ISBN 0-521-63198-X.
- Roche, Emmanuel; Yves Schabes (1997). Procesamiento del lenguaje de estados finitos . Prensa del MIT. pp. 1 -65. ISBN 0-262-18182-7.
- Beesley, Kenneth R .; Lauri Karttunen (2003). Morfología de estados finitos . Centro de Estudios del Lenguaje y la Información. ISBN 1-57586-434-7.
- Roark, Brian; Richard Sproat (2007). Enfoques computacionales de la morfología y la sintaxis . Prensa de la Universidad de Oxford. ISBN 978-0-19-927478-9.
- Berstel, Jean (1979). Transducciones y lenguajes libres de contexto . Teubner Verlag.. Versión PDF gratuita