11-731 Machine Translation Syntax-Based Translation Models – Principles, Approaches, AcquisitionOutlineSyntax-based Models: RationaleSyntax-based Statistical MTSyntax-based Resources vs. ModelsSyntax-based Translation ModelsSlide 7Slide 8Structure Available During AcquisitionHierarchical Phrase-Based ModelsSlide 11Slide 12Syntax-Augmented Hierarchical ModelSlide 14Slide 15Tree-to-Tree: Stat-XFERTransfer Rule FormalismTranslation Lexicon: French-to-English ExamplesFrench-English Transfer Grammar Example Rules (Automatically-acquired)Syntax-driven Acquisition ProcessPFA Constituent Node AlignerPFA Node Alignment Algorithm ExampleSlide 23Slide 24Slide 25Further ImprovementsExtracted Syntactic PhrasesComparative Results: French-to-EnglishTransfer Rule AcquisitionRule Extraction AlgorithmSlide 31Slide 32Slide 33Slide 34Some Chinese XFER RulesDCU Tree-bank Alignment methodString-to-Tree: Galley et al. (GHKM)Slide 38Tree Transduction ModelsSlide 40SummaryMajor ChallengesSlide 43References11-731 Machine TranslationSyntax-Based Translation Models – Principles, Approaches, AcquisitionAlon Lavie16 March 201111-731 Machine Translation (2011) 2OutlineSyntax-based Translation Models: Rationale and MotivationResource Scenarios and Model DefinitionsString-to-Tree, Tree-to-String and Tree-to-TreeHierarchical Phrase-based Models (Chiang’s Hiero)Syntax-Augmented Hierarchical Models (Venugopal and Zollmann)String-to-Tree Models Phrase-Structure-based Model (Galley et al., 2004, 2006)Tree-to-Tree ModelsPhrase-Structure-based Stat-XFER Model (Lavie et al., 2008)DCU Tree-bank Alignment method (Zhachev, Tinsley et. al.)Tree-to-String ModelsTree Transduction Models (Yamada and Knight, Gildea et al.)11-731 Machine Translation (2011) 3Syntax-based Models: RationalePhrase-based models model translation at very shallow levels:Translation equivalence modeled at the multi-word lexical levelPhrases capture some cross-language local reordering, but only for phrases that were seen in training – No effective generalizationNon-local cross-language reordering is modeled only by permuting order of phrases during decodingNo explicit modeling of syntax, structural divergences or syntax-to-semantic mapping differencesGoal: Improve translation quality using syntax-based modelsCapture generalizations, reorderings and divergences at appropriate levels of abstractionModels direct the search during decoding to more accurate translationsStill Statistical MT: Acquire translation models automatically from (annotated) parallel-data and model them statistically!11-731 Machine Translation (2011) 4Syntax-based Statistical MTBuilding a syntax-based Statistical MT system:Similar in concept to simpler phrase-based SMT methods:Model Acquisition from bilingual sentence-parallel corporaDecoders that given an input string can find the best translation according to the modelsOur focus today will be on the models and their acquisitionNext week: Chris Dyer will cover decoding for hierarchical and syntax-based MT11-731 Machine Translation (2011) 5Syntax-based Resources vs. ModelsImportant Distinction:1. What structural information for the parallel-data is available during model acquisition and training?2. What type of translation models are we acquiring from the annotated parallel data?Structure available during Acquisition – Main Distinctions:Syntactic/structural information for the parallel training data:Given by external components (parsers) or inferred from the data?Syntax/Structure available for one language or for both?Phrase-Structure or Dependency-Structure?What do we extract from parallel-sentences?Sub-sentential units of translation equivalence annotated with structureRules/structures that determine how these units combine into full transductions11-731 Machine Translation (2011) 6Syntax-based Translation ModelsString-to-Tree:Models explain how to transduce a string in the source language into a structural representation in the target languageDuring decoding: No separate parsing on source sideDecoding results in set of possible translations, each annotated with syntactic structureThe best-scoring string+structure can be selected as the translationExample:ne VB pas  (VP (AUX (does) RB (not) x211-731 Machine Translation (2011) 7Syntax-based Translation ModelsTree-to-String:Models explain how to transduce a structural representation of the source language input into a string in the target languageDuring decoding: Parse the source string to derive its structureDecoding explores various ways of decomposing the parse tree into a sequence of composable models, each generating a translation string on the target sideThe best-scoring string can be selected as the translationExamples:11-731 Machine Translation (2011) 8Syntax-based Translation ModelsTree-to-Tree:Models explain how to transduce a structural representation of the source language input into a structural representation in the target languageDuring decoding: Decoder synchronously explores alternative ways of parsing the source-language input string and transduce it into corresponding target-language structural output.The best-scoring structure+string can be selected as the translationExample:NP::NP [VP 北 CD 北 北北 ]  [one of the CD countries that VP](;; Alignments(X1::Y7)(X3::Y4))11-731 Machine Translation (2011) 9Structure Available During AcquisitionWhat information/annotations are available for the bilingual sentence-parallel training data?(Symerticized) Viterbi Word Alignments (i.e. from GIZA++)(Non-syntactic) extracted phrases for each parallel sentenceParse-trees/dependencies for “source” languageParse-trees/dependencies for “target” languageSome major potential issues and problems:GIZA++ word alignments are not aware of syntax – word-alignment errors can have bad consequences on the extracted syntactic modelsUsing external monolingual parsers is also problematic:Using single-best parse for each sentence introduces parsing errorsParsers were designed for monolingual parsing, not translationParser design decisions for each language may be very different: •Different notions of constituency and structure•Different sets of POS and constituent labels11-731 Machine Translation (2011) 10Hierarchical Phrase-Based ModelsProposed by David Chiang