Implicitly Intersecting Weighted Automata using Dual Decomposition

2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 232–242, Montr´eal, Canada, June 3-8, 2012. c⃝2012 Association for Computational Linguistics Implicitly Intersecting Weighted Automata using Dual Decomposition∗ Michael J. Paul and Jason Eisner Department of Computer Science / Johns Hopkins University Baltimore, MD 21218, USA {mpaul,jason}@cs.jhu.edu Abstract We propose an algorithm to find the best path through an intersection of arbitrarily many weighted automata, without actually perform- ing the intersection. The algorithm is based on dual decomposition: the automata attempt to agree on a string by communicating about fea- tures of the string. We demonstrate the algo- rithm on the Steiner consensus string problem, both on synthetic data and on consensus de- coding for speech recognition. This involves implicitly intersecting up to 100 automata. 1 Introduction Many tasks in natural language processing in- volve functions that assign scores—such as log- probabilities—to candidate strings or sequences. Often such a function can be represented compactly as a weighted finite state automaton (WFSA). Find- ing the best-scoring string according to a WFSA is straightforward using standard best-path algorithms. It is common to construct a scoring WFSA by combining two or more simpler WFSAs, taking ad- vantage of the closure properties of WFSAs. For ex- ample, consider noisy channel approaches to speech recognition (Pereira and Riley, 1997) or machine translation (Knight and Al-Onaizan, 1998). Given an input f, the score of a possible English tran- scription or translation e is the sum of its language model score log p(e) and its channel model score log p(f | e). If each of these functions of e is repre- sented as a WFSA, then their sum is represented as the intersection of those two WFSAs. WFSA intersection corresponds to constraint con- junction, and hence is often a mathematically natu- ral way to specify a solution to a problem involving ∗The authors are grateful to Damianos Karakos for provid- ing tools and data for the ASR experiments. This work was supported in part by an NSF Graduate Research Fellowship. multiple soft constraints on a desired string. Unfor- tunately, the intersection may be computationally in- efficient in practice. The intersection of K WFSAs having n1, n2, . . . , nK states may have n1·n2 · · · nK states in the worst case.1 In this paper, we propose a more efficient method for finding the best path in an intersection without actually computing the full intersection. Our ap- proach is based on dual decomposition, a combina- torial optimization technique that was recently intro- duced to the vision (Komodakis et al., 2007) and lan- guage processing communities (Rush et al., 2010; Koo et al., 2010). Our idea is to interrogate the several WFSAs separately, repeatedly visiting each WFSA to seek a high-scoring path in each WFSA that agrees with the current paths found in the other WSFAs. This iterative negotiation is reminiscent of message-passing algorithms (Sontag et al., 2008), while the queries to the WFSAs are reminiscent of loss-augmented inference …

Content truncated to 500 words