Ergänzungen zum maschinellen Übersetzen natürlicher Sprachen im Sommersemester 2016

Viele Ansätze der maschinellen Verarbeitung natürlicher Sprachen (natural language processing; nlp) basieren auf Wahrscheinlichkeiten, die anhand von Beispieldaten geschätzt werden. Ein wichtiges Schätzverfahren dafür ist der Expectation-Maximization-Algorithmus (EM-Algorithmus) [DLR77]. Mit ihm ist es möglich, Wahrscheinlichkeiten anhand von unvollständigen Daten zu trainieren.

Im Rahmen von nlp ist es beispielsweise wichtig, Regelwahrscheinlichkeiten probabilistischer kontextfreier Grammatiken (probabilistic context-free grammars; pcfg) anhand von Daten, die lediglich Terminal-Strings enthalten, bestimmen zu können. Die Ableitungen, mit denen die Terminal-Strings erzeugt wurden, sind allerdings unbekannt, sodass die Regelwahrscheinlichkeiten nicht direkt berechnet werden können; die Daten sind in diesem Sinne also unvollständig. Mit Hilfe des EM-Algorithmus können trotzdem sinnvolle Regelwahrscheinlichkeiten geschätzt werden.

Der EM-Algorithmus ist ein sehr allgemeines Verfahren und auf viele weitere Probleme anwendbar. So können verschiedene konkrete Instanzen des EM-Algorithmus aus der allgemeinen Version hergeleitet, z.B. Trainingsverfahren für

probabilistic context-free grammars [LY90; NS08] (weiterführend: [Bak79; Pre01a; Pre01b]),
tree transducers [GK04; GKM08],
IBM Model 1 [Bro+93],
synchronous tree-adjoining grammars [BVN14],
Yamada-Knight model [YK01],
extended multi bottom-up tree transducers [ELM09],
interpreted regular tree grammars [KK11],
synchronous context-free grammars [Chi07].

In der Vorlesung werden einige dieser Instanzen hergeleitet.

Termine

Donnerstags, 5. DS (14:50–16:20 Uhr), APB/E009: Vorlesung
Dienstags, 1. DS (7:30–9:00 Uhr), APB/E010: Übung

Vorlesungsmaterial

Überblicksartikel zu Statistischer Maschineller Übersetzung [Lop08].
EM Algorithmen in der Literatur Folien
⦇p⦈_cb is nondecreasing Beweis
Algorithmic skeleton for EM, Comparison and Relationship of EM algorithms Folien
⦇κ⦈_sc = ⦇p⦈_cb Beweis
Overview on EM algorithms
⦇μ⦈_io = ⦇μ^♭⦈_sc Beweis
Generic inside-outside EM algorithm Folie
Training of PCFG

Übungsaufgaben

2016-04-12: 1. Übungsblatt
2016-04-19: 2. Übungsblatt
2016-05-10: 3. Übungsblatt
2016-05-24: 4. Übungsblatt
2016-06-07: 5. Übungsblatt
2016-06-28: 6. Übungsblatt

Literatur

[Bak79]: J. K. Baker. Trainable grammars for speech recognition. The Journal of the Acoustical Society of America 65.S1 (1979), S132–S132. doi: 10.1121/1.2017061.
[Bro+93]: Peter F. Brown, Vincent J. Della Pietra, Stephen A. Della Pietra und Robert L. Mercer. The mathematics of statistical machine translation: parameter estimation. Comput. Linguist. 19.2 (Juni 1993), 263–311. issn: 0891-2017.
[BVN14]: Matthias Büchse, Heiko Vogler und Mark-Jan Nederhof. Tree parsing for tree-adjoining machine translation. Journal of Logic and Computation 24.2 (2014), 351–373. doi: 10.1093/logcom/exs050.
[Chi07]: David Chiang. Hierarchical Phrase-Based Translation. Computational Linguistics 33.2 (Juni 2007), 201–228. issn: 0891-2017. doi: 10.1162/coli.2007.33.2.201.
[DLR77]: A. P. Dempster, N. M. Laird und D. B. Rubin. Maximum Likelihood from Incomplete Data via the EM Algorithm. Journal of the Royal Statistical Society. Series B (Methodological) 39.1 (1977), 1–38. issn: 00359246.
[ELM09]: Joost Engelfriet, Eric Lilin und Andreas Maletti. Extended multi bottom-up tree transducers. Acta Informatica 46.8 (2009), 561–590. issn: 0001-5903. doi: 10.1007/s00236-009-0105-8.
[GK04]: Jonathan Graehl und Kevin Knight. Training Tree Transducers. HLT-NAACL 2004: Main Proceedings. Hrsg. von Susan Dumais, Daniel Marcu und Salim Roukos. Boston, Massachusetts, USA: Association for Computational Linguistics, Mai 2004, 105–112.
[GKM08]: Jonathan Graehl, Kevin Knight und Jonathan May. Training Tree Transducers. Computational Linguistics 34.3 (Juni 2008), 391–427. issn: 0891-2017. doi: 10.1162/coli.2008.07-051-R2-03-57.
[KK11]: Alexander Koller und Marco Kuhlmann. A generalized view on parsing and translation. Proceedings of the 12th International Conference on Parsing Technologies. IWPT ’11. Dublin, Ireland: Association for Computational Linguistics, 2011, 2–13. isbn: 9781932432046.
[Lop08]: Adam Lopez. Statistical Machine Translation. ACM Comput. Surv. 40.3 (Aug. 2008), 8:1–8:49. issn: 0360-0300. doi: 10.1145/1380584.1380586.
[LY90]: Karim Lari und Steve J. Young. The estimation of stochastic context-free grammars using the Inside-Outside algorithm. Computer Speech & Language 4.1 (Jan. 1990), 35–56. issn: 0885-2308. doi: 10.1016/0885-2308(90)90022-X.
[NS08]: Mark-Jan Nederhof und Giorgio Satta. Probabilistic Parsing. New Developments in Formal Languages and Applications. Hrsg. von Gemma Bel-Enguix, M.Dolores Jiménez-López und Carlos Martín-Vide. Bd. 113. Studies in Computational Intelligence. Springer Berlin Heidelberg, 2008, 229–258. isbn: 9783540782902. doi: 10.1007/978-3-540-78291-9_7.
[Pre01a]: Detlef Prescher. Inside-Outside Estimation Meets Dynamic EM. Proceedings of the Seventh International Workshop on Parsing Technologies (IWPT-2001), 17-19 October 2001, Beijing, China. Tsinghua University Press, 2001. isbn: 7302049254.
[Pre01b]: Detlef Prescher. Inside-outside estimation meets dynamic EM : gold. Techn. Ber. Postfach 151141, 66041 Saarbrücken: Saarländische Universitäts- und Landesbibliothek, 2001.
[YK01]: Kenji Yamada und Kevin Knight. A Syntax-based Statistical Translation Model. Proceedings of the 39th Annual Meeting on Association for Computational Linguistics. ACL ’01. Toulouse, France: Association for Computational Linguistics, 2001, 523–530. doi: 10.3115/1073012.1073079.

Stand: 30.08.2017 12:34 Uhr