Maschinelles Übersetzen natürlicher Sprachen im Wintersemester 2014/2015

Inhalte

Beim maschinellen Übersetzen von Texten in einer natürlichen Sprache in eine andere kommen verschiedene Formalismen wie Grammatiken und Automaten zum Einsatz. Diese Vorlesung gibt einen Überblick, wie man solche Formalismen zur Modellierung von natürlichsprachlichen Übersetzungen nutzen kann und wie man ein so modelliertes Übersetzungssystem anhand von Beispielen trainiert.

Termine

Die Vorlesungen beginnen am 13. Oktober 2014 (siehe Stundenplan).

Am 27. November 2014 findet keine Vorlesung und keine Übung statt.

Übungsaufgaben

• 2014-10-16: 1. Übungsblatt
• 2014-10-23: 2. Übungsblatt
• 2014-10-30: 3. Übungsblatt
• 2014-11-06: 4. Übungsblatt
• 2014-11-13: 5. Übungsblatt
• 2014-11-20: 6. Übungsblatt (2014-11-18 korrigiert: Aufgabe 4 in zwei Aufgaben geteilt)
• 2014-11-27: Ausfall der Übung
• 2014-12-04: Erasmus teaching exchange with Mark-Jan Nederhof
• 2014-12-11: 7. Übungsblatt
• 2014-12-18, 12:35 Uhr, APB 1004 (Ratssaal): Verteidigung im Promotionsverfahren von Matthias Büchse (Teilnahme optional)
• 2015-01-08: 8. Übungsblatt
• 2015-01-22: 9. Übungsblatt
• 2015-01-29: 10. Übungsblatt

Materialien

Materialen werden im Laufe der Vorlesung zur Verfügung gestellt. Sie können sich vorab anhand des vorherigen Vorlesungsdurchlaufes einen Überblick verschaffen.

• 2014-10-13: Einführung
  • natürliche Sprache
  • Arcturan-Centauri-Beispiel von Kevin Knight [1]
  • weiterführende Literatur: [1, 2]
• 2014-10-16
  • allgemeiner Ansatz von Statistical Machine Translation: modelling, training, evaluation
  • Lexical Translation: IBM Modell 1 [3]
    • Spielregeln
• 2014-10-20 (Vertretung durch Toni Dietze)
  • Lexical Translation: IBM Model 1 [3] (Fortsetzung)
    • Herleitung des Modells aus Spielregeln
    • Training des Längenmodels
    • Training des Wörterbuches mit Instanz des Expectation-Maximization-Algorithmus
    • Beispiel für Wörterbuch-Training
• 2014-10-23
  • Language Model: Bigrams
    • Modelling
    • Training
  • n-Gram Models
• 2014-10-27
  • Source-Channel Model [3]
  • Decoding for Source-Channel Models [4]
    • Algorithmus in Pseudocode
    • Decoding-Beispiel
    • weiterführende Literatur: decoding of source-channel model with bigrams and IBM Model 1 is NP-hard [5]
• 2014-10-30
  • Syntax-based Translation: The Yamada-Knight Model
    • Yamada-Knight translation model [6]
    • Beispiel:
      • translation
      • operations performed
      • insertion probabilities
      • reordering probabilities
      • translation probabilities
• 2014-11-03
  • Syntax-based Translation: The Yamada-Knight Model (Fortsetzung)
    • Training [6] (Trainingsalgorithmus)
    • Decoding [7] (Beispielparsebaum (2014-11-06 korrigiert))
• 2014-11-06
  • Syntax-based Language Model: Probabilistic Context-Free Grammars
    • Context-Free Grammars
      • example productions
      • examples for derivation, abstract syntax tree, and parse tree
      • notational conventions
      • example ranks of pcfg productions
• 2014-11-10
  • Syntax-based Language Model: Probabilistic Context-Free Grammars (Fortsetzung)
    • Probabilistic Context-Free Grammars
    • Language Model
    • weiterführende Literatur: Consistency of Probabilistic Context-Free Grammars [8]
• 2014-11-13
  • Syntax-based Language Model: Probabilistic Context-Free Grammars (Fortsetzung)
    • Training (supervised)
      • example tree from Penn Treebank
• 2014-11-17
  • Syntax-based Language Model: Probabilistic Context-Free Grammars (Fortsetzung)
    • Evaluation and Parsing
      • Construction of the reduct e ⨞ G
      • Computing the probability of an English sentence
        • inside probability [9]
        • weiterführende Literatur: Fixpunktsemantik von EBNF-Definitionen [😉 [😉?]]
• 2014-11-20
  • Syntax-based Language Model: Probabilistic Context-Free Grammars (Fortsetzung)
    • Calculating the best derivation of a PCFG [vgl. 10]
      • An adaptation of Knuth’s algorithm
      • Example run of the adaptation of Knuth’s algorithm
    • Outlook: Calculating the n best derivations [11]
• 2014-11-24 (Vertretung durch Toni Dietze)
  • presentation of Berkeley Parser [12] in Vanda Studio
  • weiterführende Links: Stanford Parser (Webinterface), statmt.org – “dedicated to research in statistical machine translation” (Software, Korpora, Wettbewerbe etc.)
• 2014-12-01 und 2014-12-04: Erasmus teaching exchange with Mark-Jan Nederhof
  • Lecture 1 (handout) [13]
  • Lecture 2 (handout)
  • Lecture 3 (handout) [14]
  • weiterführende Literatur: [15]
• 2014-12-08
  • Translation based on Hierarchical Phrases
    • Modeling (Beispielgrammatik, Beispielableitung)
    • weiterführende Literatur: Hiero [16], Syntax-Directed Transduction [17]
• 2014-12-11
  • Translation based on Hierarchical Phrases (Fortsetzung)
    • Training [16]
      • A word-aligned sentence pair
      • Conditions for initial phrase pairs
      • Extraction of SCFG rules
      • extracted rules for the example sentence
    • weiterführende Literatur: alignment models [18]
• 2014-12-15
  • Translation based on Hierarchical Phrases (Fortsetzung)
    • Training (Fortsetzung)
  • Tree Transducers
    • Modeling
      • Probabilistic Extended Tree Transducers
• 2014-12-18
  • Tree Transducers (Fortsetzung)
    • Modeling (Fortsetzung)
      • Probabilistic Extended Tree Transducers (Fortsetzung)
      • Translation Model
      • Probabilistic Extended Tree-to-String Transducers
• 2015-01-05
  • Tree Transducers (Fortsetzung)
    • Modeling (Fortsetzung)
      • Example: Implementation of the Yamada-Knight translation model
        • Implementing reordering with tree transducers
        • Implementing insertion with tree transducers
        • Implementing translation with tree transducers
    • Training [20, 21]
      • Rule Extraction
        • How to obtain rules for a yXTT M
        • An example alignment graph G(ξ, f, A)
        • weiterführende Literatur: „GHKM“ [19]
• 2015-01-08
  • Tree Transducers (Fortsetzung)
    • Training [20, 21] (Fortsetzung)
      • Rule Extraction (Fortsetzung)
        • Alignment graph with frontier nodes (in circles) and its corresponding minimal frontier graph fragments
        • Computation of a node’s spans
        • Obtaining the yXTT’s left-hand sides
        • Obtaining the yXTT’s right-hand sides
        • All rules extracted from the alignment graph
• 2015-01-12, 2015-01-15, 2015-01-19, 2015-01-22
  • Tree Transducers (Fortsetzung)
    • Training [20, 21] (Fortsetzung)
      • Training of a Probability Assignment
        • EM algorithm for training tree transducers
        • Probabilistic Regular Tree Grammars
        • Input- and output-product of probabilistic tree transducers
          • Input- and output product
        • Inside- and outside-probabilities
• 2015-01-26
  • Exkurs: Expectation-Maximization-Algorithmus
    • The EM algorithm [22]
    • EM algorithm for unsupervised training of PCFG

Literatur

1. Kevin Knight, 1997. Automating Knowledge Acquisition for Machine Translation. In: AI Magazine 18.4. S. 81–96.
2. Adam Lopez, 2008. Statistical Machine Translation. In: ACM Computing Surveys 40.3. S. 1–49.
3. Peter F. Brown, Vincent J. Della Pietra, Stephen A. Della Pietra und Robert L. Mercer, 1993. The Mathematics of Statistical Machine Translation: Parameter Estimation. In: Computational Linguistics 19.2. S. 263–311.
4. Ye-Yi Wang und Alex Waibel, 1997. Decoding Algorithm in Statistical Machine Translation. In: Proceedings of the 35th Annual Meeting of the ACL. Association for Computational Linguistics. S. 366–372.
5. Kevin Knight, 1999. Squibs and Discussions: Decoding Complexity in Word-Replacement Translation Models. In: Computional Linguistics 25(4), S. 607–615.
6. Kenji Yamada und Kevin Knight, 2001. A Syntax-Based Statistical Translation Model. In: Proceedings of the 39th Annual Meeting of the ACL. Association for Computational Linguistics. S. 523–530.
7. Kenji Yamada und Kevin Knight, 2002. A Decoder for Syntax-Based Statistical MT. In: Proceedings of the 40th Annual Meeting of the ACL. Association for Computational Linguistics. S. 303–310.
8. Torsten Stüber, 2012. Consistency of Probabilistic Context-Free Grammars, Dresden, Germany, Technischer Bericht TUD-FI12-04-März 2012, Technische Universität Dresden.
9. Mark-Jan Nederhof und Giorgio Satta, 2008. Computing Partition Functions of PCFGs. In: Research on Language and Computation 2(6), S. 139–162.
10. Donald E. Knuth, 1977. A generalization of Dijkstra’s algorithm. In: Information Processing Letters 6(1), S. 1–5.
11. Liang Huang und David Chiang, 2005. Better k-best parsing. In: Proceedings of the Ninth International Workshop on Parsing Technology, S. 53–64.
12. Slav Petrov, Leon Barrett, Romain Thibaux und Dan Klein, 2006. Learning accurate, compact, and interpretable tree annotation. In: Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, Association for Computational Linguistics, S. 433–440
13. Mark-Jan Nederhof und Giorgio Satta, 2011. Splittability of Bilexical Context-free Grammars is Undecidable. In: Computational Linguistics 37(4), MIT Press, S. 867–879. DOI: 10.1162/COLI_a_00079.
14. Mark-Jan Nederhof, 2005. Nederhof A General Technique to Train Language Models on Language Models. In: Computational Linguistics 31(2), MIT Press, S. 173–186. DOI: 10.1162/0891201054223986.
15. Anna Corazza und Giorgio Satta, 2007. Probabilistic Context-Free Grammars Estimated from Infinite Distributions. In: IEEE Transactions on Pattern Analysis and Machine Intelligence 29(8), S. 1379–1393. DOI: 10.1109/TPAMI.2007.1065.
16. David Chiang, 2007. Hierarchical Phrase-Based Translation. In: Computational Linguistics 33(2), S. 201–228.
17. Philip M. Lewis II und Richard Edwin Stearns, 1968. Syntax-Directed Transduction. In: Journal of the ACM 15(3), S. 465–488. DOI: 10.1145/321466.321477.
18. Franz Josef Och und Hermann Ney, 2003. A systematic comparison of various statistical alignment models. Computational Linguistics 29(1), MIT Press, S. 19–51. DOI: 10.1162/089120103321337421.
19. Michel Galley, Mark Hopkins, Kevin Knight und Daniel Marcu, 2004. What’s in a translation rule? In: Proceedings of HLT-NAACL 2004. Association for Computational Linguistics. S. 273–280.
20. Jonathan Graehl und Kevin Knight, 2004. Training tree transducers. In: Proc. Human Language Technologies and North American ACL, Association for Computational Linguistics. S. 105–112.
21. Jonathan Graehl, Kevin Knight und Jonathan May, 2008. Training Tree Transducers. In: Computational Linguistics 34(3). S. 391–427.
22. Detlef Prescher, 2005. A Tutorial on the Expectation-Maximization Algorithm Including Maximum-Likelihood Estimation and EM Training of Probabilistic Context-Free Grammars. Technischer Bericht. 15th European Summer School in Logic, Language, und Information.

weiterführende Literatur: ACL Anthology – “over 21,200 papers on the study of computational linguistics and natural language processing”