Paper: Efficient Inference through Cascades of Weighted Tree Transducers

ACL ID P10-1108
Title Efficient Inference through Cascades of Weighted Tree Transducers
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2010
Authors

Weighted tree transducers have been pro- posed as useful formal models for rep- resenting syntactic natural language pro- cessing applications, but there has been little description of inference algorithms for these automata beyond formal founda- tions. We give a detailed description of algorithms for application of cascades of weighted tree transducers to weighted tree acceptors, connecting formal theory with actual practice. Additionally, we present novel on-the-fly variants of these algo- rithms, and compare their performance on a syntax machine translation cascade based on (Yamada and Knight, 2001). 1 Motivation Weighted finite-state transducers have found re- cent favor as models of natural language (Mohri, 1997). In order to make actual use of systems built with these formalisms we m...