Higher-order Derivatives of Weighted Finite-state Machines (2021)

Abstract: Weighted finite-state machines are a fundamental building block of NLP systems. They have withstood the test of time—from their early use in noisy channel models in the 1990s up to modern-day neurally parameterized conditional random fields. This work examines the computation of higher-order derivatives with respect to the normalization constant for weighted finite-state machines. We provide a general algorithm for evaluating derivatives of all orders, which has not been previously described in the literature. In the case of second-order derivatives, our scheme runs in the optimal O(Aˆ2 Nˆ4) time where A is the alphabet size and N is the number of states. Our algorithm is significantly faster than prior algorithms. Additionally, our approach leads to a significantly faster algorithm for computing second-order expectations, such as covariance matrices and gradients of first-order expectations.

## introduction weighted finite-state machines (wfsms) have a storied role in nlp. they are a useful formalism for speech recognition @xcite , machine transliteration @xcite , morphology @xcite and phonology @xcite inter alia. indeed, wfsms have been "neuralized" @xcite @xcite and are still of practical use to the nlp modeler. moreover, many popular sequence models, e.g., conditional random fields for part-ofspeech tagging @xcite , are naturally viewed as special cases of wfsms. for this reason, we consider the study of algorithms for the wfsms of interest in se for the nlp community. this paper considers inference algorithms for wsfms. when wfsms are acyclic, there exist simple linear-time dynamic programs, e.g., the forward algorithm @xcite , for inference. however, in general, wfsms may contain cycles and such approaches are not applicable. our work considers this general case and provides a method for efficient computation of m th -order derivatives over a cyclic wfsm. to the best of our knowledge, no algorithm for higher-order derivatives has been presented in the literature beyond a generalpurpose method from automatic differentiation. in contrast to many presentations of wfsms @xcite , our work provides a purely linear-algebraic take on them. and, indeed, it is this connection that allows us to develop our general algorithm. we provide a thorough analysis of the soundness, runtime, and space complexity of our algorithm. in the special case of second-order derivatives, our algorithm runs optimally in o(a 2 n 4 ) time and space where a is the size of the alphabet, and n is the number of states. foot_0 in contrast, the second-order expectation semiring of @xcite provides an o(a foot_1 n 7 ) solution and automatic differentiation @xcite ) yields a slightly faster o(an 5 +a 2 n 4 ) solution. additionally, we provide a speed-up for the general family of second-order expectations. indeed, we believe our algorithm is the fastest known for computing common quantities, e.g., a covariance matrix. 2 ## weighted finite-state machines in this section we briefly provide important notation for wfsms and a classic result that efficiently finds the normalization constant for the probability distribution of a wfsm. definition 1. a weighted finite-state machine m is a tuple α, {w (a) } @xmath0, ω where a is an alphabet of size a, a @xmath1, each @xmath2 n ×n where n is the number of states, and α, ω ∈ @xmath3 n are column vectors of start and end weights, respectively. we define the matrix w @xmath4. definition 2. a trajectory τ i ℓ is an ordered sequence of transitions from state i to state ℓ. visually, we can represent a trajectory by we denote the (possibly infinite) set of trajectories from i to ℓ by t iℓ and the set of all trajectories by t @xmath5,ℓ∈[n ] t iℓ . 3 consequently, when we say τ i ℓ ∈ t , we make i and ℓ implicit arguments to which t iℓ we are accessing. of course, p is only well-defined when 0 < @xmath6. 4 intuitively, α w k ω is the total weight of all trajectories of length k. thus, z is the total weight of all possible trajectories as it sums over the total weight for each possible trajectory length. thus, we can solve the infinite summation that defines w by matrix inversion in o(n 3 ) time. 5 corollary 1. proof. follows from (4) in theorem 1. by corollary 1, we can find z in o(n 3 + an 2 ). foot_5 strings versus trajectories. importantly, wf-sms can be regarded as weighted finite-state acceptors (wfsas) which accept strings as their input. each trajectory τ i ℓ ∈ t has a yield γ(τ i ℓ ) which is the concatenation of the alphabet symbols of the trajectory. the yield of a trajectory ignores any ε symbols, a discussion regarding the semantics of ε is given in @xcite . as we focus on distributions over trajectories, we do not need special considerations for ε transitions. we do not consider distributions over yields in this work as such a distribution requires constructing a latent-variable model ## computing the hessian (and beyond) in this section, we explore algorithms for efficiently computing the hessian matrix ∇ 2 z. we briefly describe two inefficient algorithms, which are derived by forward-mode and reverse-mode automatic differentiation. next, we propose an efficient algorithm which is based on a key differential identity. ## second-order expectations in this section, we leverage the algorithms of the previous section to efficiently compute a family expectations, known as a second-order expectations. to begin, we define an additively decomposable function r: @xmath7 examples of second-order expectations include the fisher information matrix and the gradients of firstorder expectations (e.g., expected cost, entropy, and the kullback-leibler divergence). our algorithm is based on two fundamental concepts. firstly, expectations for probability distributions as described in (1), can be decomposed as expectations over transitions @xcite . secondly, the marginal probabilities of transitions are connected to derivatives of z. foot_8 lemma 2. for @xmath8 proof. see app. a.2. we formalize our algorithm as e 2 in fig. 1 . note that we achieve an additional speed-up by exploiting associativity (see app. a.3). theorem 4. algorithm e 2 computes the secondorder expectation of additively decomposable functions r: @xmath9: @xmath10: ## conclusion we have presented efficient methods that exploit properties of the derivative of a matrix inverse to find m-order derivatives for wfsms. additionally, we provided an explicit, novel, algorithm for materializing the hessian in its optimal complexity, o(a 2 n 4 ). we also showed how this could be utilized to efficiently compute second-order expectations of distributions under wfsms, such as covariance matrices and the gradient of entropy. we hope that our paper encourages future research to use the hessian and second-order expectations of wfsm systems, which have previously been disadvantaged by inefficient algorithms.