Transducer Disambiguation with Sparse Topological Features

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 2275–2280, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. Transducer Disambiguation with Sparse Topological Features Gonzalo Iglesias† Adri`a de Gispert†‡ Bill Byrne†‡ †SDL Research, Cambridge, U.K. {giglesias|agispert|bbyrne}@sdl.com ‡Department of Engineering, University of Cambridge, U.K. Abstract We describe a simple and efficient al- gorithm to disambiguate non-functional weighted finite state transducers (WFSTs), i.e. to generate a new WFST that con- tains a unique, best-scoring path for each hypothesis in the input labels along with the best output labels. The algorithm uses topological features combined with a trop- ical sparse tuple vector semiring. We em- pirically show that our algorithm is more efficient than previous work in a PoS- tagging disambiguation task. We use our method to rescore very large translation lattices with a bilingual neural network language model, obtaining gains in line with the literature. 1 Introduction Weighted finite-state transducers (WFSTs), or lat- tices, are used in speech and language process- ing to compactly represent and manipulate a large number of strings. Applying a finite-state opera- tion (eg. PoS tagging) to a lattice via composition produces a WFST that maps input (eg. words) onto output strings (eg. PoS tags) and preserves the arc-level alignment between each input and output symbol (eg. each arc is labeled with a word-tag pair and has a weight). Typically, the result of such operation is a WFST that is am- biguous because it contains multiple paths with the same input string, and non-functional because it contains multiple output strings for a given input string (Mohri, 2009). Disambiguating such WFSTs is the task of cre- ating a WFST that encodes only the best-scoring path of each input string, while still maintaining the arc-level mapping between input and output symbols. This is a non-trivial task1, and so far only 1Unless one enumerates all the possible input strings in one algorithm has been described (Shafran et al., 2011); the main steps are: (a) Map the WFST into an equivalent weighted finite-state automata (WFSA) using weights that contain both the WFST weight and out- put symbols (using a special semiring) (b) Apply WFSA determinization under this semiring to ensure that only one unique path per input string survives (c) Expand the result back to an WFST that pre- serves arc-level alignments We present a new disambiguation algorithm that can efficiently accomplish this. In Section 2 we describe how the tropical sparse tuple vec- tor semiring can keep track of individual arcs in the original WFST as topological features during the mapping step (a). This allows us to describe in Section 3 an efficient expansion algorithm for step (c). We show in Section 4 empirical evidence that our algorithm is more efficient than Shafran et al. (2011) in their same PoS-tagging task. We also show how our method can be applied in rescor- ing translation lattices under a bilingual neural- network model (Devlin et al., 2014), obtaining BLEU score gains consistent with the literature. Section 5 …

Content truncated to 500 words