GPU-Accelerated Forward-Backward algorithm with Application to Lattice-Free MMI

2021/10/22 by Lucas Ondel, Léa-Marie Lam-Yee-Mui, Ondel, Lucas +8 · 2 citations
Computer Science · Medicine · Physics and Astronomy · #Computation and Language (cs.CL) #Distributed #FOS: Computer and information sciences #Matrix Theory and Algorithms #Medical Imaging Techniques and Applications #Model Reduction and Neural Networks #Parallel #and Cluster Computing (cs.DC) #cs.CL #cs.DC

paper · pdf · doi:10.48550/arxiv.2112.00709

Submitted to ICASSP 2022

arxiv created 2021/10/22 · openalex publication_date 2021/10/22 · arxiv updated 2021/12/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We propose to express the forward-backward algorithm in terms of operations between sparse matrices in a specific semiring. This new perspective naturally leads to a GPU-friendly algorithm which is easy to implement in Julia or any programming languages with native support of semiring algebra. We use this new implementation to train a TDNN with the LF-MMI objective function and we compare the training time of our system with PyChain - a recently introduced C++/CUDA implementation of the LF-MMI loss. Our implementation is about two times faster while not having to use any approximation such as the "leaky-HMM".

Cited by

• Bregman Conditional Random Fields: Sequence Labeling with Parallelizable Inference Algorithms
• Fast and General Automatic Differentiation for Finite-State Methods

Related

• Learning representations by forward-propagating errors
• cuHALLaR: A GPU Accelerated Low-Rank Augmented Lagrangian Method for Large-Scale Semidefinite Programming
• Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices
• GPU Semiring Primitives for Sparse Neighborhood Methods
• Accelerating the solution of families of shifted linear systems with CUDA