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

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

In der Vorlesung werden einige dieser Instanzen hergeleitet.

Termine

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

Die erste Lehrveranstaltung findet am 16. April 2015 statt.

Am 23. Juli 2015 9:20–12:40 Uhr (2. & 3. DS) im Raum APB/3027 finden die studentischen Vorträge statt.

Eine klassische Übung wird es nur sporadisch geben.

Vorlesungsmaterial

• Polylux-Folien

Übungsaufgaben

• 2015-04-28: 1. Übungsblatt
• 2015-05-12: 2. Übungsblatt
• 2015-06-09: 3. Übungsblatt
• 2015-06-16 8:15 Uhr: Fortsetzung von Übungsblatt 3

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: 978-1-932432-04-6.

[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: 978-3-540-78290-2. 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: 7-302-04925-4.

[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.