Fast and General Automatic Differentiation for Finite-State Methods

arXiv (Cornell University)

Abstract

We propose a new method, that we coined the ``morphism-trick'', to integrate custom implementations of vector-Jacobian products in automatic differentiation softwares, applicable to a wide range of semiring-based computations. Our approach leads to efficient and semiring-agnostic implementations of the backward pass of dynamic programming algorithms. For the particular case of finite-state methods, we introduce an algorithm that computes and differentiates the $\oplus$-sum of all paths' weight of a finite-state automaton. Results show that, with minimal effort from the user, our novel library allows computing the gradient of a function w.r.t. to the weights of a finite state automaton orders of magnitude faster than state-of-the-art automatic differentiation systems. Implementations are made available via an open-source library distributed under a permissive license.

Authors 5

1. Lucas Ondel Yang

   Centre National de la Recherche Scientifique · Laboratoire Interdisciplinaire des Sciences du Numérique

   Affiliation as printed

   LISN, CNRS

2. Tina Raissi Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen

3. Martin Kocour
   Affiliation as printed

   FIT / BUT, BUT

4. Pablo Riera
   Affiliation as printed

   ICC

5. Caio Corro

   Institut de Recherche en Informatique et Systèmes Aléatoires · Institut National des Sciences Appliquées de Rennes

   Affiliation as printed

   LinkMedia, INSA Rennes, IRISA