Decoding with Finite-State Transducers on GPUs

Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pages 1044–1052, Valencia, Spain, April 3-7, 2017. c⃝2017 Association for Computational Linguistics Decoding with Finite-State Transducers on GPUs Arturo Argueta and David Chiang Department of Computer Science and Engineering University of Notre Dame aargueta,dchiang@nd.edu Abstract Weighted finite automata and transduc- ers (including hidden Markov models and conditional random fields) are widely used in natural language processing (NLP) to perform tasks such as morphological anal- ysis, part-of-speech tagging, chunking, named entity recognition, speech recog- nition, and others. Parallelizing finite state algorithms on graphics processing units (GPUs) would benefit many areas of NLP. Although researchers have imple- mented GPU versions of basic graph al- gorithms, limited previous work, to our knowledge, has been done on GPU algo- rithms for weighted finite automata. We introduce a GPU implementation of the Viterbi and forward-backward algorithm, achieving decoding speedups of up to 5.2x over our serial implementation running on different computer architectures and 6093x over OpenFST. 1 Introduction Weighted finite automata (Mohri, 2009), includ- ing hidden Markov models and conditional ran- dom fields (Lafferty et al., 2001), are used to solve a wide range of natural language processing (NLP) problems, including phonology and morphology, part-of-speech tagging, chunking, named entity recognition, and others. Even models for speech recognition and phrase-based translation can be thought of as extensions of finite automata (Mohri et al., 2002; Kumar et al., 2005). Although the use of graphics processing units (GPUs) is now de rigeur in applications of neu- ral networks and made easy through toolkits like Theano (Theano Development Team, 2016), there has been little previous work, to our knowledge, on acceleration of weighted finite-state compu- tations on GPUs (Narasiman et al., 2011; Li et al., 2014; Peng et al., 2016; Chong et al., 2009). In this paper, we consider the operations that are most likely to have high speed require- ments: decoding using the Viterbi algorithm, and training using the forward-backward algorithm. We present an implementation of the Viterbi and forward-backward algorithms for CUDA GPUs. We release it as open-source software, with the hope of expanding in the future to a toolkit includ- ing other operations like composition. Most previous work on parallel processing of finite automata (Ladner and Fischer, 1980; Hillis and Steele, 1986; Mytkowicz et al., 2014) uses dense representations of finite automata, which is only appropriate if the automata are not too sparse (that is, most states can transition to most other states). But the automata used for natural language tend to be extremely large and sparse. In addition, the more recent work in this line assumes deter- ministic automata, but automata that model natural language ambiguity are generally nondeterminis- tic. Previous work has been done on accelerating particular NLP tasks on GPUs: in machine trans- lation, phrase-pair retrieval (He et al., 2013) and language model querying (Bogoychev and Lopez, 2016); parsing (Hall et al., 2014; Canny et al., 2013); and speech recognition (Kim et al., 2012). …

Content truncated to 500 words