Linear Transduction Grammars and Zipper Finite-State Transducers

Proceedings of Recent Advances in Natural Language Processing, pages 640–647, Hissar, Bulgaria, 12-14 September 2011. Linear Transduction Grammars and Zipper Finite-State Transducers Markus Saers and Dekai Wu Human Language Technology Center Dept. of Computer Science and Engineering Hong Kong University of Science and Technology Hong Kong {masaers|dekai}@cs.ust.hk Abstract We examine how the recently explored class of linear transductions relates to finite-state models. Linear transductions have been neglected historically, but gain- ined recent interest in statistical machine translation modeling, due to empirical studies demonstrating that their attractive balance of generative capacity and com- plexity characteristics lead to improved accuracy and speed in learning alignment and translation models. Such work has until now characterized the class of linear transductions in terms of either (a) linear inversion transduction grammars (LITGs) which are linearized restrictions of inver- sion transduction grammars or (b) lin- ear transduction grammars (LTGs) which are bilingualized generalizations of lin- ear grammars. In this paper, we offer a new alternative characterization of linear transductions, as relating four finite-state languages to each other. We introduce the devices of zipper finite-state automata (ZFSAs) and zipper finite-state transducers (ZFSTs) in order to construct the bridge be- tween linear transductions and finite-state models. 1 Introduction Linear transductions are a long overlooked class of transductions positioned between finite-state transductions and inversion transductions in terms of complexity. In the Aho–Ullman hierarchy, lin- ear transductions are those that can be generated by SDTGs1 of rank 1, but that is about all that is said about them. 1Syntax-directed transduction grammars or SDTGs (Lewis and Stearns, 1968; Aho and Ullman, 1972) have also been referred to recently in the statistical machine translation sub- community as synchronous context-free grammars. Recently, however, linear transduction gram- mars (LTGs) have been shown to be both effective and efficient for learning word alignments in sta- tistical machine translation models (Saers et al., 2010b; Saers et al., 2010a). LTGs can align words more accurately than FSTs since they allow words to be reordered, and yet alignment and training complexity is two orders of magnitude lower than with ITGs (Wu, 1997). The added efficiency means that LTGs can be learned directly from parallel corpora rather than relying on external word alignment tools for a pri- ori annotation. The added efficiency does, how- ever, come at a price in expressivity, and it is vital to understand the nature of this trade-off. The au- tomaton/transducer perspective of linear transduc- tions described in this paper offers another vec- tor towards understanding the properties of linear transductions. Thus far, such work has not characterized the class of linear transductions in terms of finite-state models. Saers et al. (2010b) define linear trans- ductions in terms of linear inversion transduction grammars (LITGs), which are inversion transduc- tion grammars with a linear restriction. Alterna- tively, Saers et al. (2010a) introduce linear trans- duction grammars (LTGs), which are the natural bilingual generalization of linear grammars, and show that they define the same class of linear transductions as LITGs. In this paper, we offer a new …

Content truncated to 500 words