Computing the Expected Edit Distance from a String to a Probabilistic Finite-State Automaton
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/10045/74051
Título: | Computing the Expected Edit Distance from a String to a Probabilistic Finite-State Automaton |
---|---|
Autor/es: | Calvo-Zaragoza, Jorge | Oncina, Jose | Higuera, Colin de la |
Grupo/s de investigación o GITE: | Reconocimiento de Formas e Inteligencia Artificial |
Centro, Departamento o Servicio: | Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos |
Palabras clave: | Edit distance | Probabilistic finite state automata | Median string |
Área/s de conocimiento: | Lenguajes y Sistemas Informáticos |
Fecha de publicación: | ago-2017 |
Editor: | World Scientific Publishing |
Cita bibliográfica: | International Journal of Foundations of Computer Science. 2017, 28(5): 603-621. doi:10.1142/S0129054117400093 |
Resumen: | In a number of fields, it is necessary to compare a witness string with a distribution. One possibility is to compute the probability of the string for that distribution. Another, giving a more global view, is to compute the expected edit distance from a string randomly drawn to the witness string. This number is often used to measure the performance of a prediction, the goal then being to return the median string, or the string with smallest expected distance. To be able to measure this, computing the distance between a hypothesis and that distribution is necessary. This paper proposes two solutions for computing this value, when the distribution is defined with a probabilistic finite state automaton. The first is exact but has a cost which can be exponential in the length of the input string, whereas the second is a fully polynomial-time randomized schema. |
Patrocinador/es: | This work was partially supported by the Spanish Ministerio de Educación, Cultura y Deporte through a FPU grant (Ref. AP2012-0939) and the Spanish Ministerio de Economía y Competitividad through Project No. TIN2013-48152-C2-1-R (supported by UE FEDER funds). This work was partly done while the third author was supported by the University of Kyoto. |
URI: | http://hdl.handle.net/10045/74051 |
ISSN: | 0129-0541 (Print) | 1793-6373 (Online) |
DOI: | 10.1142/S0129054117400093 |
Idioma: | eng |
Tipo: | info:eu-repo/semantics/article |
Derechos: | © World Scientific Publishing |
Revisión científica: | si |
Versión del editor: | http://dx.doi.org/10.1142/S0129054117400093 |
Aparece en las colecciones: | INV - GRFIA - Artículos de Revistas |
Archivos en este ítem:
Archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
2017_Calvo-Zaragoza_etal_IJFCS_preprint.pdf | Preprint (acceso abierto) | 1,28 MB | Adobe PDF | Abrir Vista previa |
Todos los documentos en RUA están protegidos por derechos de autor. Algunos derechos reservados.