Computing the Expected Edit Distance from a String to a Probabilistic Finite-State Automaton
Empreu sempre aquest identificador per citar o enllaçar aquest ítem
http://hdl.handle.net/10045/74051
Títol: | Computing the Expected Edit Distance from a String to a Probabilistic Finite-State Automaton |
---|---|
Autors: | Calvo-Zaragoza, Jorge | Oncina, Jose | Higuera, Colin de la |
Grups d'investigació o GITE: | Reconocimiento de Formas e Inteligencia Artificial |
Centre, Departament o Servei: | Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos |
Paraules clau: | Edit distance | Probabilistic finite state automata | Median string |
Àrees de coneixement: | Lenguajes y Sistemas Informáticos |
Data de publicació: | d’agost-2017 |
Editor: | World Scientific Publishing |
Citació bibliogràfica: | International Journal of Foundations of Computer Science. 2017, 28(5): 603-621. doi:10.1142/S0129054117400093 |
Resum: | 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. |
Patrocinadors: | 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 |
Tipus: | info:eu-repo/semantics/article |
Drets: | © World Scientific Publishing |
Revisió científica: | si |
Versió de l'editor: | http://dx.doi.org/10.1142/S0129054117400093 |
Apareix a la col·lecció: | INV - GRFIA - Artículos de Revistas |
Arxius per aquest ítem:
Arxiu | Descripció | Tamany | Format | |
---|---|---|---|---|
2017_Calvo-Zaragoza_etal_IJFCS_preprint.pdf | Preprint (acceso abierto) | 1,28 MB | Adobe PDF | Obrir Vista prèvia |
Tots els documents dipositats a RUA estan protegits per drets d'autors. Alguns drets reservats.