{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T08:02:14Z","timestamp":1777449734791,"version":"3.51.4"},"reference-count":23,"publisher":"MIT Press","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2018,3]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1162\/coli_a_00306","type":"journal-article","created":{"date-parts":[[2017,12,14]],"date-time":"2017-12-14T20:23:10Z","timestamp":1513282990000},"page":"17-37","source":"Crossref","is-referenced-by-count":3,"title":["On the Derivational Entropy of Left-to-Right Probabilistic Finite-State Automata and Hidden Markov Models"],"prefix":"10.1162","volume":"44","author":[{"given":"Joan Andreu","family":"S\u00e1nchez","sequence":"first","affiliation":[{"name":"Universitat Polit\u00e8cnica de Val\u00e8ncia"}]},{"given":"Martha Alicia","family":"Rocha","sequence":"additional","affiliation":[{"name":"Instituto Tecnol\u00f3gico de Le\u00f3n"}]},{"given":"Ver\u00f3nica","family":"Romero","sequence":"additional","affiliation":[{"name":"Universitat Polit\u00e8cnica de Val\u00e8ncia"}]},{"given":"Mauricio","family":"Villegas","sequence":"additional","affiliation":[{"name":"SearchInk"}]}],"member":"281","reference":[{"key":"bib1","doi-asserted-by":"publisher","DOI":"10.3115\/1034678.1034759"},{"key":"bib2","doi-asserted-by":"publisher","DOI":"10.1121\/1.2003011"},{"key":"bib3","doi-asserted-by":"publisher","DOI":"10.1109\/TASL.2011.2134087"},{"key":"bib4","unstructured":"Chi, Z. 1999. Statistical properties of probabilistic context-free grammar. Computational Linguistics, 25(1):131\u2013160."},{"key":"bib5","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1065"},{"key":"bib6","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2004.03.020"},{"key":"bib8","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850223"},{"key":"bib9","doi-asserted-by":"crossref","unstructured":"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\u2013188, Seoul.","DOI":"10.1109\/MFI.2008.4648062"},{"key":"bib10","unstructured":"Ilic, V. M. 2011. Entropy semiring forward-backward algorithm for HMM entropy computation. CoRR., abs\/1108.0347."},{"key":"bib11","doi-asserted-by":"crossref","unstructured":"Kemp, T. and T. Schaaf. 1997. Estimating confidence using word lattices. Eurospeech, pages 827\u2013830, Rhodes.","DOI":"10.21437\/Eurospeech.1997-281"},{"key":"bib12","unstructured":"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\u2013112."},{"key":"bib14","doi-asserted-by":"publisher","DOI":"10.1006\/csla.2001.0184"},{"key":"bib15","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.01.010"},{"key":"bib16","doi-asserted-by":"publisher","DOI":"10.1006\/csla.1996.0022"},{"key":"bib17","doi-asserted-by":"crossref","unstructured":"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\u2013186, Crete.","DOI":"10.1109\/ICFHR.2014.38"},{"key":"bib19","unstructured":"Sanchis, A., A. Juan, and E. Vidal. 2012. A word-based na\u00efve Bayes classifier for confidence estimation in speech recognition. IEEE Transactions on Audio, Speech, and Language Processing, 20(2):565\u2013574."},{"key":"bib20","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(74)90799-2"},{"key":"bib21","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1974.224001"},{"key":"bib22","doi-asserted-by":"crossref","unstructured":"Tomita, M. 1986. An efficient word lattice parsing algorithm for continuous speech recognition. In Proceedings of ICASSP, pages 1569\u20131572, Tokyo.","DOI":"10.1109\/ICASSP.1986.1168663"},{"key":"bib24","doi-asserted-by":"crossref","unstructured":"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\u2013163, Philadelphia, PA.","DOI":"10.3115\/1118693.1118714"},{"key":"bib25","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2005.147"},{"key":"bib26","doi-asserted-by":"publisher","DOI":"10.1109\/89.906002"},{"key":"bib27","doi-asserted-by":"publisher","DOI":"10.1145\/356827.356829"}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/COLI_a_00306","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,28]],"date-time":"2025-06-28T20:21:32Z","timestamp":1751142092000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/44\/1\/17-37\/1589"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["10.1162\/COLI_a_00306"],"URL":"https:\/\/doi.org\/10.1162\/coli_a_00306","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3]]}}}