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

On the Derivational Entropy of Left-to-Right Probabilistic Finite-State Automata and Hidden Markov Models Joan Andreu Sánchez∗ Universitat Politècnica de València Martha Alicia Rocha∗∗ Instituto Tecnológico de León Verónica Romero∗ Universitat Politècnica de València Mauricio Villegas† SearchInk 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. ∗ Camí de Vera, s/n, 46022 València, Spain. E-mail: {jandreu, vromero}@prhlt.upv.es. ∗∗ mrocha@dsic.upv.es. † mauricio@searchink.com. Submission received: 11 May 2016, revised version received: 15 July 2017, accepted for publication: 28 August 2017. doi:10.1162/COLI_a_00306 © 2017 Association for Computational Linguistics Published under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) license Computational Linguistics Volume 44, Number 1 1. Introduction Probabilistic Finite-State Automata (PFA) and hidden Markov models (HMM) are well-known formalisms that have been widely used in automatic speech recognition (Ortmanns and Ney 1997), machine translation (Ueffing, Och, and Ney 2002), natural language processing (Mohri, Pereira, and Riley 2002), and, more recently, in hand- written text recognition (Romero, Toselli, and Vidal 2012). PFA and HMM can be con- sidered special cases of weighted finite-state automata (WFA) (Mohri, Pereira, and Riley 2002; Dupont, Denis, and Esposito 2005). PFA and HMM were extensively researched in Vidal et al. (2005) and interesting probabilistic properties were demonstrated. In formal language theory, automata are considered as string acceptors, but PFA may be considered as generative processes (see Section 2.2 in Vidal et al. [2005]). We have followed the point of view of Vidal et al. (2005) in this article about this issue. PFA are closely related to word lattices (WL) (Tomita 1986), which are currently a fundamental tool for many applications because WL convey most of the hypotheses produced by a decoder. WL have also been used for parsing (Tomita 1986), for computing confidence measures in speech recognition (Kemp and Schaaf 1997; Ortmanns and Ney 1997; Sanchis, Juan, and Vidal 2012), machine translation (Ueffing, Och, and Ney 2002), and handwritten text recognition (Puigcerver, Toselli, and Vidal 2014) for interactive tran- scription (Toselli, Vidal, and Casacuberta 2011) and term detection (Can and Saraçlar 2011). All of these applications require the WL to be correctly defined, and …

Content truncated to 500 words