Pushdown Automata in Statistical Machine Translation

Download: Presentation.

Pushdown Automata in Statistical Machine Translation” by W. Byrne, International Conference on Finite-State Methods and Natural Language Processing, FSMNLP. July 2013. Keynote lecture.


This talk will present some recent work investigating pushdown automata (PDA) in the context of statistical machine translation and alignment under synchronous context-free grammars (SCFGs). PDAs can be used to compactly represent the space of candidate translations generated by the grammar when applied to an input sentence, and this presentation will give an overview of general-purpose PDA algorithms for replacement, composition, shortest path, and expansion. HiPDT, a hierarchical phrase-based decoder using the PDA representation and these algorithms will be described and the complexity of the HiPDT decoder operations will be compared to decoders based on finite state automata and the widely used hypergraph representations. PDAs have strengths in a particular translation scenario: exact decoding with large SCFGs and relatively smaller language models. This talk is based on recent work with Adrià de Gispert and Gonzalo Iglesias at University of Cambridge, and Michael Riley and Cyril Allauzen at Google Research.

Download: Presentation.

BibTeX entry:

   author = {W. Byrne},
   title = {Pushdown Automata in Statistical Machine Translation},
   publisher = {International Conference on Finite-State Methods and
	Natural Language Processing, FSMNLP},
   month = jul,
   year = {2013},
   note = {Keynote lecture},
   url = {http://fsmnlp2013.cs.st-andrews.ac.uk/abstracts.html#byrne}

Back to Bill Byrne publications.