- -

On the Derivational Entropy of Left-to-Right Probabilistic Finite-State Automata and Hidden Markov Models

RiuNet: Repositorio Institucional de la Universidad Politécnica de Valencia

Compartir/Enviar a

Citas

Estadísticas

  • Estadisticas de Uso

On the Derivational Entropy of Left-to-Right Probabilistic Finite-State Automata and Hidden Markov Models

Mostrar el registro sencillo del ítem

Ficheros en el ítem

Thumbnail
Nombre: Sánchez;Rocha;Romero ...
Tamaño: 266.7Kb
Formato: PDF
Descripción: Versión editorial
Abrir
dc.contributor.author Sánchez Peiró, Joan Andreu es_ES
dc.contributor.author Rocha, M. A. es_ES
dc.contributor.author Romero, Verónica es_ES
dc.contributor.author Villegas, Mauricio es_ES
dc.date.accessioned 2019-12-22T21:01:04Z
dc.date.available 2019-12-22T21:01:04Z
dc.date.issued 2018 es_ES
dc.identifier.issn 0891-2017 es_ES
dc.identifier.uri http://hdl.handle.net/10251/133558
dc.description.abstract [EN] Probabilistic finite-state automata are a formalism that is widely used in many problems of automatic speech recognition and natural language processing. Probabilistic finite-state automata are closely related to other finite-state models as weighted finite-state automata, word lattices, and hidden Markov models. Therefore, they share many similar properties and problems. Entropy measures of finite-state models have been investigated in the past in order to study the information capacity of these models. The derivational entropy quantifies the uncertainty that the model has about the probability distribution it represents. The derivational entropy in a finite-state automaton is computed from the probability that is accumulated in all of its individual state sequences. The computation of the entropy from a weighted finite-state automaton requires a normalized model. This article studies an efficient computation of the derivational entropy of left-to-right probabilistic finite-state automata, and it introduces an efficient algorithm for normalizing weighted finite-state automata. The efficient computation of the derivational entropy is also extended to continuous hidden Markov models. es_ES
dc.description.sponsorship This work has been partially supported through the European Union's H2020 grant READ (Recognition and Enrichment of Archival Documents) (Ref: 674943) and the MINECO/FEDER-UE project TIN2015-70924-C2-1-R. The second author was supported by the "Division de Estudios de Posgrado e Investigacion" of Instituto Tecnologico de Leon. es_ES
dc.language Inglés es_ES
dc.publisher MIT Press es_ES
dc.relation.ispartof Computational Linguistics es_ES
dc.rights Reconocimiento - No comercial - Sin obra derivada (by-nc-nd) es_ES
dc.subject.classification LENGUAJES Y SISTEMAS INFORMATICOS es_ES
dc.subject.classification ESTADISTICA E INVESTIGACION OPERATIVA es_ES
dc.title On the Derivational Entropy of Left-to-Right Probabilistic Finite-State Automata and Hidden Markov Models es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1162/COLI_a_00306 es_ES
dc.relation.projectID info:eu-repo/grantAgreement/EC/H2020/674943/EU/Recognition and Enrichment of Archival Documents/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MINECO//TIN2012-37475-C02-01/ES/SEARCH IN TRANSCRIBED MANUSCRIPTS AND DOCUMENT AUGMENTATION/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/EC/FP7/600707/EU/tranScriptorium/
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació es_ES
dc.description.bibliographicCitation Sánchez Peiró, JA.; Rocha, MA.; Romero, V.; Villegas, M. (2018). On the Derivational Entropy of Left-to-Right Probabilistic Finite-State Automata and Hidden Markov Models. Computational Linguistics. 44(1):17-37. https://doi.org/10.1162/COLI_a_00306 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1162/COLI_a_00306 es_ES
dc.description.upvformatpinicio 17 es_ES
dc.description.upvformatpfin 37 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 44 es_ES
dc.description.issue 1 es_ES
dc.relation.pasarela S\356465 es_ES
dc.contributor.funder European Commission es_ES
dc.contributor.funder Ministerio de Economía, Industria y Competitividad es_ES
dc.description.references Abney, S., McAllester, D., & Pereira, F. (1999). Relating probabilistic grammars and automata. Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics -. doi:10.3115/1034678.1034759 es_ES
dc.description.references Bakis, R. (1976). Continuous speech recognition via centisecond acoustic states. The Journal of the Acoustical Society of America, 59(S1), S97-S97. doi:10.1121/1.2003011 es_ES
dc.description.references Can, D., & Saraclar, M. (2011). Lattice Indexing for Spoken Term Detection. IEEE Transactions on Audio, Speech, and Language Processing, 19(8), 2338-2347. doi:10.1109/tasl.2011.2134087 es_ES
dc.description.references Chi, Z. 1999. Statistical properties of probabilistic context-free grammar. Computational Linguistics, 25(1):131–160. es_ES
dc.description.references Corazza, A., & Satta, G. (2007). Probabilistic Context-Free Grammars Estimated from Infinite Distributions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(8), 1379-1393. doi:10.1109/tpami.2007.1065 es_ES
dc.description.references Dupont, P., Denis, F., & Esposito, Y. (2005). Links between probabilistic automata and hidden Markov models: probability distributions, learning models and induction algorithms. Pattern Recognition, 38(9), 1349-1371. doi:10.1016/j.patcog.2004.03.020 es_ES
dc.description.references Hernando, D., Crespi, V., & Cybenko, G. (2005). Efficient Computation of the Hidden Markov Model Entropy for a Given Observation Sequence. IEEE Transactions on Information Theory, 51(7), 2681-2685. doi:10.1109/tit.2005.850223 es_ES
dc.description.references Huber, M. F., T. Bailey, H. Durrant-Whyte, and U. D. Hanebeck. 2008. On entropy approximation for Gaussian mixture random vectors. In IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems (MFI), pages 181–188, Seoul. es_ES
dc.description.references Ilic, V. M. 2011. Entropy semiring forward-backward algorithm for HMM entropy computation. CoRR., abs/1108.0347. es_ES
dc.description.references Kemp, T. and T. Schaaf. 1997. Estimating confidence using word lattices. Eurospeech, pages 827–830, Rhodes. es_ES
dc.description.references Mann, G. S. and A. McCallum. 2007. Efficient computation of entropy gradient for semi-supervised conditional random fields. In Proceedings of HLT-NAACL, Companion Volume, Short Papers, pages 109–112. es_ES
dc.description.references Mohri, M., Pereira, F., & Riley, M. (2002). Weighted finite-state transducers in speech recognition. Computer Speech & Language, 16(1), 69-88. doi:10.1006/csla.2001.0184 es_ES
dc.description.references Nederhof, M.-J., & Satta, G. (2008). Computation of distances for regular and context-free probabilistic languages. Theoretical Computer Science, 395(2-3), 235-254. doi:10.1016/j.tcs.2008.01.010 es_ES
dc.description.references Puigcerver, J., A. H. Toselli, and E. Vidal. 2014. Word-graph and character-lattice combination for KWS in handwritten documents. In International Conference on Frontiers in Handwriting Recognition (ICFHR), pages 181–186, Crete. es_ES
dc.description.references Sanchis, A., A. Juan, and E. Vidal. 2012. A word-based naïve Bayes classifier for confidence estimation in speech recognition. IEEE Transactions on Audio, Speech, and Language Processing, 20(2):565–574. es_ES
dc.description.references Soule, S. (1974). Entropies of probabilistic grammars. Information and Control, 25(1), 57-74. doi:10.1016/s0019-9958(74)90799-2 es_ES
dc.description.references Thompson, R. A. (1974). Determination of Probabilistic Grammars for Functionally Specified Probability-Measure Languages. IEEE Transactions on Computers, C-23(6), 603-614. doi:10.1109/t-c.1974.224001 es_ES
dc.description.references Tomita, M. 1986. An efficient word lattice parsing algorithm for continuous speech recognition. In Proceedings of ICASSP, pages 1569–1572, Tokyo. es_ES
dc.description.references Ueffing, N., F. J. Och, and H. Ney. 2002. Generation of word graphs in statistical machine translation. In Proceedings on Empirical Method for Natural Language Processing, pages 156–163, Philadelphia, PA. es_ES
dc.description.references Vidal, E., Thollard, F., de la Higuera, C., Casacuberta, F., & Carrasco, R. C. (2005). Probabilistic finite-state machines - part I. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(7), 1013-1025. doi:10.1109/tpami.2005.147 es_ES
dc.description.references Wessel, F., Schluter, R., Macherey, K., & Ney, H. (2001). Confidence measures for large vocabulary continuous speech recognition. IEEE Transactions on Speech and Audio Processing, 9(3), 288-298. doi:10.1109/89.906002 es_ES
dc.description.references Wetherell, C. S. (1980). Probabilistic Languages: A Review and Some Open Questions. ACM Computing Surveys, 12(4), 361-379. doi:10.1145/356827.356829 es_ES


Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem