Hauptregion der Seite anspringen
TU Dresden — Fakultät Informatik — Institut für Theoretische Informatik

Einführung in das Parsing natürlicher Sprachen im Wintersemester 2020/21

Aktuelle Hinweise: Aufgrund von SARS-CoV-2 und dem damit verbundenen eingeschränkten Präsenzbetrieb an der TU Dresden verfahren wir wie folgt:

  • Die Vorlesungen und Übungen beginnen mit dem verschobenen Semesterstart zum 26.10. und finden virtuell statt.
  • Bitte schreiben Sie sich in den zugehörigen OPAL-Kurs ein.
  • Wöchentlich werden Folien mit Sprachaufzeichnungen online zur Verfügung gestellt.
  • Parallel dazu werden Übungsaufgaben zur Verfügung gestellt. Lösungen können digital abgegeben werden und werden von uns kommentiert. Zusätzlich werden auch Musterlösungen veröffentlicht.
  • Vorlesungs- und Übungsinhalte können im Forum des OPAL-Kurses diskutiert werden.
  • Zweiwöchentlich wird eine virtuelle Konsultation zur Klärung offener Fragen angeboten.
  • Weitere Maßnahmen und Anpassungen erfolgen entsprechend den Empfehlungen der Universitätsleitung.

Einführung

Um einen Satz in einer natürlichen Sprache maschinell zu verarbeiten, muss dieser in einer geeigneten Form im Computer repräsentiert werden. Diese Vorlesung befasst sich mit der Darstellung von natürlichsprachlichen Sätzen als sogenannte Hybridbäume. Es wird gezeigt, warum ein Hybridbaum eine geeignete Datenstruktur darstellt und mit welchen formalen Modellen ein Satz automatisch in einen Hybridbaum überführt werden kann. Zudem behandelt die Vorlesung, wie verschiedene Grammatikformalismen aus einer repräsentativen Menge von Hybridbäumen gewonnen werden können.

Vorlesungsmaterialien

Hinweis: Der Inhalt der Vorlesung ist identisch zum Sommersemester 2020.

Audioaufzeichnungen zur Vorlesung

Den Foliensatz zur Vorlesung finden Sie hier. Die vertonten Folien sind urheberrechtlich geschützt und dürfen nur für das persönliche Studium verwendet werden, die Verbreitung ist untersagt. Die Aufzeichnungen sind nur aus dem Netz der TU abrufbar, nutzen Sie gegebenenfalls VPN.

Vorlesungsskript

Die im Skript referenzierte Literatur ist am Ende dieser Seite aufgelistet. Das Skript ist urheberrechtlich geschützt und darf nur für das persönliche Studium verwendet werden, die Verbreitung ist untersagt. Die Materialien sind nur aus dem Netz der TU abrufbar, nutzen Sie gegebenenfalls VPN.

  • 44. KW (Introduction): Auszug 1, Auszug 2
  • 45. KW (Preliminaries and Hybrid trees): Auszug 3
  • 46. KW (Quality measures for parsers): Auszug 4
  • 47. KW (Transition-based parsing): Auszug 5
  • 48.+49. KW (RTG-based language models and translation models): Auszug 6
  • 50. KW (Derivation trees of LCFRS and their hybrid tree languages): Auszug 7
  • 51. KW (Grammar induction of LCFRS): Auszug 8
  • 1. KW: (Training of probabilistic RTG-based models): Auszug 9
  • 2.+3. KW: (Parsing for LCFRS): Auszug 10

Übungen

Übungsaufgaben werden wöchentlich (jeweils freitags) an dieser Stelle veröffentlich. Sie haben die Möglichkeit, im OPAL-Kurs eigene Lösungen (bis zum darauffolgenden Freitag) einzureichen. Diese werden kommentiert und sind dann ebenfalls in OPAL abrufbar. Außerdem werden dort nach jedem Übungszyklus Musterlösungen veröffentlich.

Alle zwei bis drei Übungsblätter wird eine Konsultation über BigBlueButton angeboten. Die Terminfindung erfolgt via E-Mail.

Literatur

  1. Abeillé, A., Schabes, Y., and Joshi, A.K. 1990. Using lexicalized TAGs for machine translation. Proc. 13th CoLing, University of Helsinki, Finland, 1–6.
  2. Arnold, A. and Dauchet, M. 1976. Bi-transductions de forêts. Proc. 3rd Int. Coll. Automata, Languages and Programming, Edinburgh University Press, 74–86.
  3. Büchse, M., Nederhof, M.-J., and Vogler, H. 2011. Tree parsing with synchronous tree-adjoining grammars. Proc. 12th Int. Conf. on Parsing Technologies (IWPT 2011), Association for Computational Linguistics, 14–25.
  4. Büchse, M., Geisler, D., Stüber, T., and Vogler, H. 2010. N-best Parsing Revisited. Proceedings of the 2010 Workshop on Applications of Tree Automata in Natural Language Processing, Association for Computational Linguistics, 46–54. [url]
  5. Birkhoff, G. and Lipson, J.D. 1970. Heterogeneous Algebras. Journal of Combinatorial Theory 8(1), 115–133. [doi]
  6. Black, E., Abney, S.P., Flickinger, D., et al. 1991. A Procedure for Quantitatively Comparing the Syntactic Coverage of English Grammars. Proceedings of the Workshop on Speech and Natural Language, Association for Computational Linguistics, 306–311. [doi, url]
  7. Boullier, P. 2000. Range concatenation grammars. Proc. of 6th Int. Workshop on Parsing Technologies (IWPT 2000). [url]
  8. Brainerd, W.S. 1969. Tree generating regular systems. Inform. and Control 14, 217–231. [doi]
  9. Brants, S., Dipper, S., Eisenberg, P., et al. 2004. TIGER: Linguistic Interpretation of a German Corpus. Res. Lang. Comput. 2(4). [doi]
  10. Buchholz, S. and Marsi, E. 2006. CoNLL-X Shared Task on Multilingual Dependency Parsing. Proceedings of the Tenth Conference on Computational Natural Language Learning, Association for Computational Linguistics, 149–164. [url]
  11. Chiang, D. 2007. Hierarchical phrase-based translation. Computational Linguistics 33(2), 201–228.
  12. Deransart, P. and Maluszynski, J. 1985. Relating logic programs and attribute grammars. J. Logic Programming 2, 119–155.
  13. Drewes, F., Gebhardt, K., and Vogler, H. 2016. EM-Training for Weighted Aligned Hypergraph Bimorphisms. Proceedings of the SIGFSM Workshop on Statistical NLP and Weighted Automata, Association for Computational Linguistics, 60–69. [url]
  14. Engelfriet, J. and Schmidt, E.M. 1978. IO and OI.II. J. Comput. System Sci. 16, 1, 67–99.
  15. Fischer, M.J. 1968. Grammars with macro–like productions. .
  16. Forst, M., Bertomeu, N., Crysmann, B., Fouvry, F., Hansen-Schirra, S., and Kordoni, V. 2004. Towards a dependency-based gold standard for German parsers. Proceedings of the 5th Workshop on Linguistically Interpreted Corpora.
  17. Gebhardt, K., Nederhof, M.-J., and Vogler, H. 2017. Hybrid grammars for parsing of discontinuous phrase structures and non-projective dependency structures. Computational Linguistics. [doi]
  18. Gebhardt, K. 2018. Generic refinement of expressive grammar formalisms with an application to discontinuous constituent parsing. Proceedings of the 27th International Conference on Computational Linguistics (COLING 2018). [url]
  19. Giegerich, R. 1988. Composition and evaluation of attribute coupled grammars. Acta Inform. 25, 355–423.
  20. Goguen, J.A., Thatcher, J.W., Wagner, E.G., and Wright, J.B. 1977. Initial algebra semantics and continuous algebras. J. ACM 24, 68–95. [doi]
  21. Graehl, J., Knight, K., and May, J. 2008. Training tree transducers. Computational Linguistics 34, 3, 391–427.
  22. Huang, L. and Chiang, D. 2005. Better K-best Parsing. Proceedings of the Ninth International Workshop on Parsing Technology, Association for Computational Linguistics, 53–64. [url]
  23. Joshi, A.K. and Schabes, Y. 1997. Tree-adjoining grammars. In: G. Rozenberg and A. Salomaa, eds., Handbook of Formal Languages. Springer-Verlag, 69–123.
  24. Kübler, S., McDonald, R., and Nivre, J. 2009. Dependency parsing. Morgan and Claypool Publishers. [doi]
  25. Kallmeyer, L. 2010. Parsing beyond context-free grammars. Springer. [doi]
  26. Kallmeyer, L. and Maier, W. 2010. Data-driven parsing with probabilistic linear context-free rewriting systems. 23rd International Conference on Computational Linguistics, Beijing, China, 537–545. [url]
  27. Kallmeyer, L. and Maier, W. 2013. Data-driven parsing using probabilistic linear context-free rewriting systems. Computational Linguistics 39(1), 87–119. [doi]
  28. Knuth, D.E. 1968. Semantics of context–free languages. Math. Systems Theory 2, 127–145.
  29. Koller, A. and Kuhlmann, M. 2011. A Generalized View on Parsing and Translation. Proceedings IWPT 2011. [url]
  30. Kuhlmann, M. and Satta, G. 2009. Treebank Grammar Techniques for Non-projective Dependency Parsing. Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics, Association for Computational Linguistics, 478–486. [url]
  31. Kuhlmann, M., Gómez-Rodríguez, C., and Satta, G. 2011. Dynamic Programming Algorithms for Transition-based Dependency Parsers. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 1, Association for Computational Linguistics, 673–682. [url]
  32. Lewis, P.M. and Stearns, R.E. 1968. Syntax-directed transduction. J. ACM 15, 3, 465–488.
  33. Maier, W. and Søgaard, A. 2008. Tree-banks and mildly context-sensitivity. Proc. of Formal Grammar 2008, 61–76. [url]
  34. Maletti, A., Graehl, J., Hopkins, M., and Knight, K. 2009. The Power of Extended Top-down Tree Transducers. SIAM J. Comput. 39, 2, 410–430.
  35. Marcus, M.P., Santorini, B., and Marcinkiewicz, M.A. 1994. Building a Large Annotated Corpus of English: The Penn Treebank. Computational Linguistics 19, 2, 313–330. [url]
  36. Matsuzaki, T., Miyao, Y., and Tsujii, J. 2005. Probabilistic CFG with Latent Annotations. Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, Association for Computational Linguistics, 75–82. [doi, url]
  37. Nederhof, M.-J. 2003. Weighted deductive parsing and Knuth’s algorithm. Computational Linguistics 29(1), 135–143.
  38. Nederhof, M.-J. and Vogler, H. 2014. Hybrid Grammars for Discontinuous Parsing. Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers, Dublin City University and Association for Computational Linguistics, 1370–1381. [url]
  39. Nivre, J. 2008. Algorithms for Deterministic Incremental Dependency Parsing. Computational Linguistics 34(4), 513–553. [doi]
  40. Nivre, J. 2009. Non-Projective Dependency Parsing in Expected Linear Time. Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, Association for Computational Linguistics, 351–359. [url]
  41. Petrov, S., Barrett, L., Thibaux, R., and Klein, D. 2006. Learning Accurate, Compact, and Interpretable Tree Annotation. Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, Association for Computational Linguistics, 433–440. [url]
  42. Rounds, W.C. 1970. Mappings and grammars on trees. Math. Systems Theory 4, 3, 257–287.
  43. Schabes, Y. 1990. Mathematical and computational aspects of lexicalized grammars. .
  44. Seki, H., Matsumura, T., Fujii, M., and Kasami, T. 1991. On multiple context-free grammars. Theoretical Computer Science 88, 191–229.
  45. Shieber, S.M. and Schabes, Y. 1990. Synchronous tree-adjoining grammars. Proc. 13th CoLing, ACL, 253–258.
  46. Skut, W., Krenn, B., Brants, T., and Uszkoreit, H. 1997. An annotation scheme for free word order languages. Fifth Conference on Applied Natural Language Processing, 88–95. [doi]
  47. Marneffe, M.-C. de and Manning, C.D. 2008. Stanford typed dependencies manual. Stanford University. [url]
  48. Bar–Hillel, Y., Perles, M., and Shamir, E. 1961. On formal properties of simple phrase structure grammars. Z. Phonetik. Sprach. Komm. 14, 143–172.
  49. Vijay-Shanker, K., Weir, D.J., and Joshi, A.K. 1987. Charaterizing structural descriptions produced by various grammatical formalisms. Proceedings of the 25th Annual Meeting of the Association for Computational Linguistics, Association for Computational Linguistics, 104–111. [doi]

Kontakt

  • Prof. Dr.-Ing. habil. Dr. h.c./Univ. Szeged
    Heiko Vogler
    Tel.: +49 (0) 351 463-38232
  • Dipl.-Inf. Richard Mörbitz
    Tel.: +49 (0) 351 463-38487
Stand: 16.04.2021 18:19 Uhr