Parsing
PD Dr. Karin Haenelt Hauptseminar Computerlinguistik Universität Heidelberg Sommersemester 2003	Kursbeschreibung

Teil 1: Vorlesung

Teil 2: Seminarprojekte

Beschreibung der Themen

1. Übersicht und Kurskonzept

Beschreibung:

1.1 Traditionelles Parsing

"Traditional parsers - including standard stochastic parsers - aim to recover complete, exact parses. They make a closed-world assumption, to wit, that the grammar they have is complete, and search through the entire space of parses defined by that grammar, seeking the globally best parse. As a result, and notwithstanding 'clean-up' strategies that are sometimes applied to salvage failed parses, they do not well at identifying good phrases in noisy surroundings." (Abney, Part-of-Speech Tagging and Partial Parsing, 1996)

1.2 Partielles Parsing

"Unrestricted text is noisy, both because of errors and because of the unavoidable incompleteness of lexicon and grammar. It is also difficult to do a global search efficiently with unrestricted text, because of the length of sentences and the ambiguity of grammars. Partial parsing is a response to these difficulties. Partial parsing techniques aim to recover syntactic information efficiently and reliably from unrestricted text, by sacrificing completeness and depth of analysis." (Abney, Part-of-Speech Tagging and Partial Parsing, 1996)

Die Standardoperationen im partiellen Parsing sind:

Darüberhinaus sind weitere interpretierende Operationen vorgestellt worden:

1.3 Implementierungsmethoden des partiellen Parsing

Grundlegende Techniken des partiellen Parsings sind endliche Automaten und stochastische Verfahren. Diese werden in unterschiedlichen Architekturen in unterschiedlichen Kombinationen verwendet.

Literatur:

Abney, Steven (1996)

Part-of-Speech Tagging and Partial Parsing. In: Church, Ken; Young, Steve; Bloothooft, Gerrit(eds.) Corpus-Based Methods in Language and Speech. Dordrecht: Kluwer Academic Publishers. http://citeseer.nj.nec.com/abney96partspeech.html

Vergne, Jacques (2000)

Tutorial: Trends in Robust Parsing. Coling 2000.

2. Flaches Parsing mit endlichen Automaten

Literatur:

Abney, Steven (1996)

Partial Parsing via Finite-State Cascades. In: Workshop on Robust parsing, 8th European Summer School in Logic, Language and Information (ESSLLI). Prag, 1996, S. 8-15. http://citeseer.nj.nec.com/abney96partial.html und Web-Seite: Steven Abney: Papers

Ait-Mokhtar, Salah; Chanod, Jean-Pierre (1997)

Incremental Finite State Parsing. In: ANLP'97 citeseer.nj.nec.com/ait-mokhtar97incremental.html

Grefenstette, Gregory (1999)

Light Parsing as Finite State Filtering. In: Kornai 1999, S. 86-94. frühere Version: In: Workshop on Extended finite state models of language, Budapest, Hungary, Aug 11--12, 1996. ECAI'96." http://citeseer.nj.nec.com/grefenstette96light.html

Kornai, András (Hrsg.) (1999)

Extended Finite State Models of Language. (Studies in Natural Language Processing). Cambridge: Cambridge University Press.

3. Endliche Automaten: deterministische Automaten, nicht-deterministische Automaten und Automaten mit Epsilon-Übergängen

Literatur:

Hopcroft, John E. und Jeffrey D. Ullman (1988)

Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Bonn u. a. : Addison-Wesley, 1988 (engl. Original Introduction to automata theory, languages and computation). [Anm.: Diese Fassung enthält die Beweise, die zugleich die Algorithmen zur Transformation der Automaten sind]

Hopcroft, John E. Rajeev Motwani und Jeffrey D. Ullman (2001)

Introduction to Automata Theory, Languages and Computation. Addison-Wesley. www-db.stanford.edu/~ullman/ialc.html [modernisierte Ausgabe, aber ohne Beweise]

4. Endliche Automaten: Transduktoren

Literatur:

Mohri, Mehryar (1997)

Finite State Transducers in Language and Speech Processing. In: Computational Linguistics, 23, 2, 1997, S. 269-311. citeseer.nj.nec.com/mohri97finitestate.html

XEROX Finite State Compiler

www.xrce.xerox.com/competencies/content-analysis/fsCompiler/fsnetwork.html

Xerox Finite State Compiler

http://www.xrce.xerox.com/competencies/content-analysis/fsCompiler/fsinput.html

5. Endliche Automaten: Datenstrukturen und Algorithmen

Literatur:

vgl. 3. und 4.

C. Fox (1992)

Lexical Analysis and Stoplists. In: Bill Frakes und Ricardo Baeza-Yates (eds.): Information Retrieval. Data Structures and Algorithms. Englewood Cliffs, N.J.: Prentice Hall. Site.es: Table of Contents and Source Code, Site.cl: Table of Contents and Source Code

6. Implementierung endlicher Automaten und Transducer in Java

Literatur:

Haenelt, Karin (2002)

Java & Sprachtechnologie. Kursentwurf. kontext.fraunhofer.de/haenelt/kurs/Java/

Ladd, Scott Robert (1997)

Java Algorithms. New York etc.: McGraw-Hill. (Chapter 7: Finite State Machines and Evolving Software) + CD-ROM.

7. Grundlagen der Wahrscheinlichkeitstheorie

Literatur:

Schickinger, Thomas und Angelika Steger (2001)

Diskrete Strukturen. Band 2: Wahrscheinlichkeitstheorie und Statistik. Heidelberg: Springer.

8. Hidden Markov Models

Literatur:

Manning, Christopher; Schütze, Hinrich (1999)

Foundations of Statistical Natural Language Processing. Cambridge, Mass., London: The MIT Press, Kap. 9: Markov Models. vgl.: http://www-nlp.stanford.edu/fsnlp/promo und http://www-nlp.stanford.edu/fsnlp/hmm-chap

9. Forward-Algorithmus

Literatur:

Manning, Christopher; Schütze, Hinrich (1999)

Foundations of Statistical Natural Language Processing. Cambridge, Mass., London: The MIT Press, Kap. 9: Markov Models, Kap. 10: Part-of-Speech Tagging. vgl.: http://www-nlp.stanford.edu/fsnlp/promo und http://www-nlp.stanford.edu/fsnlp/hmm-chap, http://www-nlp.stanford.edu/fsnlp/tagging

10. Viterbi-Algorithmus

Literatur:

Allen, James (1995)

Natural Language Understanding. 2nd edition. Addison-Wesley Publishing Co. Kap. 7 S. 189ff

Manning, Christopher; Schütze, Hinrich (1999)

Foundations of Statistical Natural Language Processing. Cambridge, Mass., London: The MIT Press, Kap. 10: Part-of-Speech Tagging. vgl.: http://www-nlp.stanford.edu/fsnlp/promo und http://www-nlp.stanford.edu/fsnlp/tagging

Viterbi, Andrew J. (1967)

Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. In: IEEE Transactions on Information Theory IT-13, S. 1260-1269.

11. Komplexität menschlicher Sprache

• long distance dependencies
• Mehrdeutigkeiten/Ambiguitäten
• morphologisch
• semantisch (Subjekt/trans. Objekt, PP-Zuordnung, Relativsatz, ..)
• Sprachwandel (Neubildungen, Veränderungen, Veralterungen)
• Vagheiten, Fehler, Varietäten

12. Ansätze des Tagging (Part-of-Speech und Konstituenten)

Beschreibung:

Die Funktion eines linguistischen Taggers ist es, Wörtern oder Wortfolgen eines Textes linguistische Information zuzuordnen, durch Tags zu repräsentieren und diese in den Text einzufügen. Meist handelt es sich um die Zuordnung von Wortart-Information (Parts-of-Speech) zu einzelnen Wörtern. Es gibt aber auch Zuordnungen syntaktischer und semantischer Auszeichnungen oder kombinierte Zuordnungen.

Bei der Verarbeitung werden meist statistische Verfahren und endliche Automaten je einzeln oder in Kombination (z.B. Hidden Markov Models) eingesetzt. Dabei wird in gewissem Maße Kontextinformation berücksichtigt.

Das Part-of-Speech Tagging ist nach der Zerlegung in Token meist die zweite Aufgabeneinheit des robusten Parsens. Das Ergebnis kann entweder zum regelbasierten Parsen (an Stelle oder zusammen mit einer morphologischen Analyse) oder als Vorstufe des Chunking und für weitere Aufgaben verwendet werden. Tagging-Verfahren werden in sequentiellen und in integrierten Architekturen verwendet.

Zur Zeit werden für verschiedene Corpora und Sprachen noch sehr unterschiedliche Tag-Sets verwendet.

Die Unterscheidung von Aufgaben, Ansätzen und die Betrachtung als abgegrenzte Teilaufgabe sind nicht strikt zu verstehen.

Ansätze:

• HMM-Ansätze: Extraktion von Wahrscheinlichkeiten aus manuell getaggten Corpora
  • Bahl, Mercer 1976
  • Church 1988, 1993
  • Cutting, Kupiec, Pedersen, Sibun (1992)
  • Merialdo 1994
  • Robert 1995
  • Derouault, Merialdo 1984
• Regelbasierte Ansätze
  • Karlsson, Voutilainen, Heikkila, Anttila, Jarvinen
• Regelbasierte Ansätze und Lernverfahren
  • Brill
  • Ramshaw, Marcus (chunking als tagging-Aufgabe)

Tagger:

Literatur:

Abney, Steven (1996)

Part-of-Speech Tagging and Partial Parsing. In: Church, Ken; Young, Steve; Bloothooft, Gerrit(eds.) Corpus-Based Methods in Language and Speech. Dordrecht: Kluwer Academic Publishers. http://citeseer.nj.nec.com/abney96partspeech.html

Bahl, L.R. und R. Mercer (1976)

Part-of-Speech Assignment by a Statistical Decision Algorithm. In: International Symposium on Information Theory. Ronneby, Schweden.

Brants, Thorsten

TnT - A Statistical Part-of-Speech Tagger ps, pdf

Brants, Thorsten, Wojiciech Skut und Brigitte Krenn (1997)

Tagging Grammatical Functions. In: Proceedings of the Second Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, Somerset, New Jersey. ed. by Claire Cardie und Ralph Weischedel, S. 64--74. http://citeseer.nj.nec.com/brants97tagging.html

Brill, Eric

Artikel

Brill, Eric (1995)

Transformation-Based Error-Driven Learning and Natural Language Processing: A Case Study in Part of Speech Tagging. In: Computational Linguistics volume 21, 4, 543-565. http://citeseer.nj.nec.com/brill95transformationbased.html

Brill, Eric (1993)

Automatic Grammar Induction and Parsing Free Text: A Transformation-Based Approach. In: Meeting of the Association for Computational Linguistics http://citeseer.nj.nec.com/brill93automatic.html

Brill, Eric (1992)

A Simple Rule-Based Part Of Speech Tagger. In: Proceedings of ANLP-92, 3rd Conference on Applied Natural Language Processing. http://citeseer.nj.nec.com/brill92simple.html

Church, Kenneth W. (1993)

Introduction to the Special Issue on Computational Linguistics using Large Corpora. In: Computational Linguistics, 19(1):1-24.

Church, Kenneth W. (1988)

A Stochastic Parts Program and Noun Phrase Parser for Unrestricted Text. In: Proceedings of the Second Conference on Applied Natural Language Processing. Austin, Texas.

Derouault, A.M. und Merialdo, Bernard (1984)

Language Modelling at the Syntactic Level. In: Proceedings of the 7th International Conference on Pattern Recognition.

Karlsson, Fred; Voutilainen, Atro; Heikkila, Juha; Anttila, Arto (1995) (eds.):

Constraint Grammar. Berlin: Mouton de Gruyter.

Karlsson Fred (1990)

Constraint Grammar as a Framework for Parsing Running Text. In: COLING, 168-173.

Merialdo, Bernard (1994)

Tagging English Text with a Probabilistic Model. In: Computational Linguistics, 20 (2): 155-172.

Ramshaw, Lance A.; Marcus, Mitchell, P. (1995)

Text Chunking Using Transformation-Based Learning. In: Proceedings of the Third Annual ACL-Workshop on Very Large Corpora, Cambridge MA, USA S. 82-94. ftp://ftp.cis.upenn.edu/pub/chunker/wvlcbook.ps.gz, http://citeseer.nj.nec.com/ramshaw95text.html

Schmid, Helmut (1995)

Improvements in part-of-speech tagging with an application to German. In: Feldweg and Hinrichs, eds., Lexikon und Text, pp. 47-50." citeseer.nj.nec.com/schmid95improvement.html

Voutilainen, Atro (1995)

A syntax-based Part-of-Speech Analyser. In: EACL 1995

Voutilainen, Atro; Heikkila, Juha; Anttila, Arto (1992)

Constraint Grammar of English. A performance-oriented Introduction. Technical Report Publication No 21. University of Helsinki, Department of General Linguistics. Helsinki.

13. Grammatikstrukturen und Tag-Sets

Beschreibung:

Unterschiedliche Ansätze arbeiten zur Zeit noch mit unterschiedlichen Tagsets für unterschiedliche Aufgaben, Corpora und Sprachen. Das Problem der Kategorisierung ist noch nicht gelöst.

• Grammatikalische Kategorien und Strukturen
• Part-of-Speech Tags
• Chunk-Tags

Literatur:

Abney, Steven (1996)

Chunk Stylebook. Working Draft. http://www.sfs.nphil.uni-tuebingen.de/~abney/96i.ps.gz

Bies, Ann; Ferguson, Mark; Katz, Karen and Robert MacIntyre (1995) with contributions from Victoria Tredlinnick, Grace Kim, Mary Ann Marcinkiewicz, Britta Schæberger

Bracketing Guidelines for the Treebank II Style. ftp://ftp.cis.upenn.edu/pub/treebank/doc/manual/root.ps.gz

Marcus, Mitchell P. und Beatrice Santorini (1993)

Building a large annotated corpus of English: the Penn Treebank. In: Computational Linguistics 19, 2, 313-330. http://citeseer.nj.nec.com/marcus93building.html

Ramshaw, Lance A. and Mitchell P. Marcus(1995)

Text Chunking Using Transformation-Based Learning. In: Proceedings of the Third ACL Workshop on Very Large Corpora, Cambridge MA, USA, 1995.
ftp://ftp.cis.upenn.edu/pub/chunker/wvlcbook.ps.gz, http://citeseer.nj.nec.com/ramshaw95text.html

Santorini, Beatrice (1991)

Bracketing Guidelines for the Penn Treebank Project. (used until 12/92) ftp://ftp.cis.upenn.edu/pub/treebank/doc/old-bktguide.ps.gz

Santorini, Beatrice (1990)

Part-of-Speech Tagging Guidelines for the Penn Treebank Project. ftp://ftp.cis.upenn.edu/pub/treebank/doc/tagguide.ps.gz

Schiller, A.; Teufel, S.; Thielen, C. (1995)

Guidelines für das Tagging deutscher Textcorpora mit STTS. http://www.sfs.nphil.uni-tuebingen.de/Elwis/stts/stts-guide.ps.gz

Voutilainen, Atro; Jarvinen, Timo (1995)

Specifying a Shallow Grammatical Representation for Parsing Purposes. In: EACL 1995.

14. Chunking

Beschreibung:

Chunks sind die syntaktischen Grund-Einheiten mit denen im robusten partiellen Parsing großer Textcorpora gearbeitet wird. Die Einheiten werden im Detail je nach Ansatz unterschiedlich definiert. Gemeinsam ist den computerlinguistischen Definitionen die Anforderung der zuverlässigen und rein syntaktischen Erkennbarkeit. Psycholinguistische Definitionen nehmen chunks als kognitiv relevante Verarbeitungseinheiten an.

Literatur:

Abney, Steven (1996)

Partial Parsing via Finite-State Cascades. In: Workshop on Robust parsing, 8th European Summer School in Logic, Language and Information (ESSLLI). Prag, 1996, S. 8-15. http://citeseer.nj.nec.com/abney96partial.html und Web-Seite: Steven Abney: Papers

Abney, Steven (1991)

Parsing By Chunks. In: Robert Berwick and Steven Abney and Carol Tenny, Principle-Based Parsing, Kluwer Academic Publishers, 1991.
http://whorf.sfs.nphil.uni-tuebingen.de/~abney/Abney_90e.ps.gz

Abney, Steven (1996)

Chunk Stylebook. Working Draft. http://www.sfs.nphil.uni-tuebingen.de/~abney/96i.ps.gz

Church, Kenneth W. (1988)

A Stochastic Parts Program and Noun Phrase Parser for Unrestricted Text. In: Proceedings of the Second Conference on Applied Natural Language Processing. Austin, Texas.

Dreyer, Markus

Syntaktisches Parsing zur prosodischen Merkmalsgenerierung. Magisterarbeit. Universität Heidelberg. Februar 2002. http://www.coling.de/markus/thesis/

Gee, James Paul; Grosjean, Francois (1983)

Performance Structures: A Psycholinguistic and Linguistic Appraisal. In: Cognitive Psychology 15, S. 411-485.

Ramshaw, Lance A. and Mitchell P. Marcus(1995)

Text Chunking Using Transformation-Based Learning. In: Proceedings of the Third ACL Workshop on Very Large Corpora, Cambridge MA, USA, 1995.
ftp://ftp.cis.upenn.edu/pub/chunker/wvlcbook.ps.gz, http://citeseer.nj.nec.com/ramshaw95text.html

Skut, Wojciech und Thorsten Brants (1998)

A Maximum-Entropy Partial Parser for Unrestricted Text. In Proceedings of the 6th ACL Workshop on Very Large Corpora (WVLC), pages 143--151, Montr'eal, Canada. http://citeseer.nj.nec.com/skut98maximumentropy.html

Tjong Kim Sang, Erik F. und Sabine Buchholz (2000)

Introduction to the CoNLL-2000 Shared Task: Chunking. In: Proceedings of the Fourth Conference on Computational Language Learning (CoNLL 2000)and the Second Learning Language in Logic Workshop (LLL 2000). 13 und 14 September 2000 in Lissabon, Portugal. http://lcg-www.uia.ac.be/conll2000/ps/12732tjo.ps, http://lcg-www.uia.ac.be/conll2000/pdf/12732tjo.pdf

Tjong Kim Sang, Erik F. (2000)

Chunking. http://lcg-www.uia.ac.be/conll2000/chunking/

Tjong Kim Sang, Erik F. (2000)

NP Chunking. http://lcg-www.uia.ac.be/~erikt/research/np-chunking.html

CoNLL-2000 & LLL-2000,
Claire Cardie (CoNLL), Walter Daelemans (CoNLL), Claire Nédellec (LLL) and Erik Tjong Kim Sang (CoNLL) (eds).

Proceedings of the Fourth Conference on Computational Language Learning (CoNLL-2000) and the Second Learning Language in Logic Workshop were held on 13 and 14 September 2000 in Lisbon, Portugal. http://lcg-www.uia.ac.be/conll2000/proceedings.html

Voutilainen, Atro (1993)

NPtool, a detector of English noun phrases. In: Proceedings of the Workshop on Very Large Corpora 48-57.

15. Chunk Attachment und Chunk Linking

Beschreibung:

Chunk Attachment und Chunk Linking sind interpretierende Operationen, die Zusammenhänge zwischen Chunks ermitteln und die Ergebnisstruktur weiter anreichern:

Literatur:

Abney, Steven (1991)

Parsing By Chunks. In: Robert Berwick and Steven Abney and Carol Tenny, Principle-Based Parsing, Kluwer Academic Publishers, 1991.
http://whorf.sfs.nphil.uni-tuebingen.de/~abney/Abney_90e.ps.gz

Dreyer, Markus

Syntaktisches Parsing zur prosodischen Merkmalsgenerierung. Magisterarbeit. Universität Heidelberg. Februar 2002. http://www.coling.de/markus/thesis/

Grefenstette, Gregory

Light Parsing as Finite State Filtering. In: Kornai 1999, S. 86-94

Vergne, Jacques (2000)

Tutorial: Trends in Robust Parsing. Coling 2000.

16. Clause Bracketing

Beschreibung:

Clause Bracketing ist die Ermittlung von Teilsätzen und Sätzen und die entsprechende Auszeichnung des Corpus. Je nach Ansatz wird diese Operation vor dem Chunking, zusammen mit dem Chunking oder nach dem Chunking durchgeführt.

Literatur:

Ejerhed, Eva (1999) (1996)

Finite State Segmentation of Discourse into Clauses. In: Proceedings of the Ecai '96 Workshop on Extended finite state models of language http://www.metacarta.com/kornai/ECAI/ejerhed.html
auch in: Kornai, András (Ed.) (1999) Extended Finite State Models of Language. (Studies in Natural Language Processing). Cambridge: Cambridge University Press.

Ejerhed, Eva (1998)

Finding Clauses in Unrestricted Text by Finitary and Stochastic Methods . In: Proceedings of Second Conference on Applied Natural Language Processing, S. 219-227.

17. Earley-Algorithmus

Literatur:

Earley, Jay (1970)

An Efficient Context-Free Parsing Algorithm. In: Communications of the ACM, 6 (8), 451-455

Haenelt, Karin (2001)

Der Earley-Algorithmus. Eine Erläuterung der formalen Spezifikation mit linguistischen Beispielen. Kursskript. 25.07.2001. 15 S. pdf, pdf:2, ps:1 ps:2 doc

18. Cocke-Kasami-Younger-Algorithmus

Literatur:

Hopcroft, John E. und Jeffrey D. Ullman (1988)

Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Bonn u. a. : Addison-Wesley, 1988 (engl. Original Introduction to automata theory, languages and computation).

Hopcroft, John E. Rajeev Motwani und Jeffrey D. Ullman (2001)

Introduction to Automata Theory, Languages and Computation. Addison-Wesley. www-db.stanford.edu/~ullman/ialc.html

19. Robustes Parsing mit Algorithmen für kontextfreie Grammatiken

Literatur:

Stolcke, Andreas

An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities. Computational Linguistics, 21, 2, S. 165-201.

Woods, William A. (1985)

Language Processing for Speech Understanding. In: Woods, William A.; Fallside, Frank (eds.): Computer Speech Processing. Prentice-Hall International (UK) Ltd.
auch in: Waibel, Alex; Lee, Kai-Fu (1990) (Hrsg.): Readings in Speech Recognition. San Mateo, Ca.: Morgan Kaufmann. S.519-533.

20. Probabilistische kontextfreie Grammatiken

Literatur:

Charniak, Eugene (1997)

Statistical Techniques for Natural Language Parsing. In: AI Magazine (cf. http://www.cs.brown.edu/people/ec/papers/aimag97.ps)

Charniak, Eugene (1993)

Statistical Language Learning.MIT Press.

Manning, Christopher; Schütze, Hinrich (1999)

Foundations of Statistical Natural Language Processing. Cambridge, Mass., London: The MIT Press, Kap. 11: Probabilistic Context Free Grammars und Kap. 12: Probabilistic Parsing. vgl.: http://www-nlp.stanford.edu/fsnlp/promo http://www-nlp.stanford.edu/fsnlp/pcfg, http://www-nlp.stanford.edu/fsnlp/probparse und

21. Probabilistisches Parsing mit kontextfreien Grammatiken

vgl. 20

22. Die O-Notation

Literatur:

Barton Jr., G. Edward; Berwick, Robert, C. und Eric Sven Ristad (1987)

Computational Complexity and Natural Language. MIT Press.

Standish, Thomas A.(1998)

Data Structures in Java. Addison Wesley Longman. Appendix B: The Language of Efficiency.

23. Komplexität des Earley-Algorithmus

Literatur:

Earley, Jay (1970)

An Efficient Context-Free Parsing Algorithm. In: Communications of the ACM, 6 (8), 451-455

Beschreibung der Seminarprojekte

P01. Morphologie mit endlichen Automaten

Aufgabe:

Es soll die Modellierung einer morphologischen Analyse (und ggf. Generierung) mit endlichen Automaten prototypisch erarbeitet und vorgestellt werden. Die Bearbeitung kann je nach Schwerpunkt durch konzeptuelle Erarbeitung und/oder Implementierung erfolgen.

Literatur:

Jurafsky, Daniel; Martin James H. (2000)

Speech and Language Processing. An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition Upper Saddle River, N.J.: Prentice Hall. Kap. 3 Morphology and Finite-State Transducers.

GERTWOL

http://www.lingsoft.fi/cgi-bin/gertwol

Koskenniemi, Kimmo (1983)

Two-level morphology: A general computational model of word-form recognition and production. Technical Report. Publication No. 11. Department of General Linguistics. University of Helsinki.

Weinrich, Harald; unter Mitarb. v. Maria Thurmair, Eva Breindl, Eva-Maria Willkop (1993)

Textgrammatik der deutschen Sprache. Mannheim, Leipzig, Wien, Zürich: Duden Verlag.

P02. Flaches Parsing mit endlichen Automaten

Aufgabe:

Entwicklung regulärer Ausdrücke und Implementierung eines endlichen Automaten zur Wortklassenauszeichnung, zur Markierung von Nominal- und Verbal-Gruppen, zur Markierung der Köpfe phrasaler Einheiten, zum Filtern syntaktischer Funktionen. Diese Aufgabe entspricht der Variante der Implementierung flachen Parsings durch endliche Automaten (mit einer Kaskade, die dem Tokenizing, Chunking und Chunk-Linking entspricht). Die Implementierung kann mit Flex, JLex, Perl oder mit einem eigenen Automaten(generator) erfolgen.

Literatur:

Grefenstette, Gregory (1999)

Light Parsing as Finite State Filtering. In: Kornai 1999, S. 86-94. frühere Version: In: Workshop on Extended finite state models of language, Budapest, Hungary, Aug 11--12, 1996. ECAI'96." http://citeseer.nj.nec.com/grefenstette96light.html

P03. Java-Werkzeuge zur Entwicklung endlicher Automaten

Aufgabe:

Für das Arbeiten mit endlichen Automaten / Transducern sind mehrere Werkzeug-Systeme entwickelt und im Internet bereitgestellt worden. Solche Systeme transformieren z.B. reguläre Ausdrücke in Automaten, oder Automaten mit Epsilon-Übergängen in epsilonfreie Automaten, nicht-deterministische Automaten in deterministische Automaten, erzeugen minimale Automaten etc. Im Projekt sollen solche Werkzeuge ermittelt werden (vorzugsweise in Java). Sie sollen installiert und getestet werden. Die Algorithmen (soweit möglich) und die Testergebnisse sollen vorgestellt werden. Es soll eine Web-Seite mit Links erstellt werden.

P04. Implementierung und experimentelle Anwendung endlicher Automaten

Aufgabe:

Es sollen Formalismen und/oder Werkzeuge für endliche Automaten (z.B. Java-Klassen) entwickelt und prototypisch für linguistische Aufgaben angewendet werden.

P05. Aufbau und Training von Hidden Markov Models

Aufgabe:

Es soll ein Prototyp entwickelt werden, der aus einem annotierten Corpus ein Hidden Markov Model aufbaut. Dieser Prototyp soll ggf. als Komponente des Viterbi-Systems in Projekt P06 verwendet werden.

Literatur:

Manning, Christopher; Schütze, Hinrich (1999)

Foundations of Statistical Natural Language Processing. Cambridge, Mass., London: The MIT Press, Kap. 9: Markov Models, Kap. 10: Part-of-Speech Tagging. vgl.: http://www-nlp.stanford.edu/fsnlp/promo http://www-nlp.stanford.edu/fsnlp/hmm-chap, http://www-nlp.stanford.edu/fsnlp/tagging und

P06. Implementierung und Test des Viterbi-Algorithmus

Aufgabe:

ggf. in Zusammenarbeit mit Projekt P05

• Implementierung des Viterbi-Algorithmus zur Verwendung im Tagging (Part-of-Speech oder andere Einheiten)
• ggf. Installation und Test vorhandener Komponenten
• Test und Evaluierung der Implementierung am Datenmaterial

Literatur:

Manning, Christopher; Schütze, Hinrich (1999)

Foundations of Statistical Natural Language Processing. Cambridge, Mass., London: The MIT Press, Kap. 9: Markov Models, Kap. 10: Part-of-Speech Tagging. vgl.: http://www-nlp.stanford.edu/fsnlp/promo und http://www-nlp.stanford.edu/fsnlp/tagging

vgl. 10. Der Viterbi-Algorithmus

P07. Ansätze des Tagging

Aufgabe

• Vorstellung eines ausgewählten Taggers (Komponenten und Algorithmen)
• Installation und Test vorhandener Komponenten
• experimentelle (partielle) Implementierung von Komponenten des vorgestellten Ansatzes
• Test und Evaluierung der Implementierung am Datenmaterial

Literatur und Systeme:

vgl. 12. Tagging

P08. Fallstudie: Anwendung von TagSets

Aufgabe

Es sollen Untersuchungen zur Corpusannotation angestellt werden. Dabei sollen Beispieltexte ausgewählt und mit verschiedenen Attributen annotiert werden. Es soll z.B. untersucht werden, ob eine bestimmte Menge von Attributen zur Abdeckung des Corpus hinreichend ist (oder gibt es Phänome, für die kein echtes Attribut vorgesehen ist), ob diese Menge voll- oder teilautomatisch zugeordnet werden kann und welche intellektuelle Bearbeitung erforderlich ist, und für welche Anwendungen die Auszeichnungen von Nutzen sein könnten. Es können verschiedene Attributmengen, die speziell für die Corpusannotation entwickelt wurden, und auch traditionelle Grammatikauszeichnungen (z.B. HPSG) untersucht werden. Für die Untersuchung können vorhandene Werkzeuge verwendet werden.

Literatur:

vgl. 13. Grammatikstrukturen und Tag-Sets

P09. Chunking

Aufgabe:

• Vorstellung eines ausgewählten Chunkers (Komponenten und Algorithmen)
• ggf. Installation und Test vorhandener Komponenten
• experimentelle (partielle) Implementierung von Komponenten des vorgestellten Ansatzes
• Test und Evaluierung der Implementierung am Datenmaterial

Literatur und Systeme:

vgl. 14. Chunking

P10. Chunk Linking und Chunk Attachment

Diese Aufgaben sind sehr eng mit den Aufgaben aus P09 verknüpft und sind ggf. mit diesen zusammen zu lösen. Hier ist insbesondere zu untersuchen, nach welchen Regeln (Formulierung z.B. mit regulären Ausdrücken) Folgen von Chunks zu umfassenderen Strukturen (z.B. konventionelle Konstituenten oder andere Sinneinheiten) verbunden werden können bzw. wie auf der Basis von Chunks semantische/syntaktische/pragmatische Funktionen der Chunks oder ihrer Verbindungen definiert werden können.

Aufgabe:

• Vorstellung eines ausgewählten Chunk Attachment oder Chunk Linking Verfahrens (Komponenten und Algorithmen)
• ggf. Installation und Test vorhandener Komponenten
• experimentelle (partielle) Implementierung von Komponenten des vorgestellten Ansatzes
• Test und Evaluierung der Implementierung am Datenmaterial

Literatur und Systeme:

vgl. 14. Chunking
vgl. 15. Chunk Attachment und Chunk Linking

P11. Clause Bracketing

Diese Aufgaben können - je nach Ansatz - sehr eng mit den Aufgaben aus P09 und P10 verknüpft sein und sind ggf. mit diesen zusammen zu lösen.

Aufgabe:

• Vorstellung eines ausgewählten Bracketing Verfahrens (Komponenten und Algorithmen)
• ggf. Installation und Test vorhandener Komponenten
• experimentelle (partielle) Implementierung von Komponenten des vorgestellten Ansatzes
• Test und Evaluierung der Implementierung am Datenmaterial

Literatur und Systeme:

vgl. 14. Chunking
vgl. 15. Chunk Attachment und Chunk Linking
vgl. 16. Bracketing

P12. Robustes Parsing mit Parsing-Algorithmen für kontextfreie Grammatiken

Aufgabe Typ A (Theorie):

Vorstellung der Methoden und Algorithmen des robusten Parsing.

Aufgabe Typ B (Implementierung):

Erweiterung eines (Standard-)Parsers (z.B. Earley, CKY, ..) um Eigenschaften der Robustheit und Test am Datenmaterial.

Literatur:

vgl. 19. Robustes Parsing

P13. Probabilistische kontextfreie Grammatiken

Aufgabe Typ A (Theorie):

Vorstellung der Methoden und Algorithmen zum Aufbau probabilistischer kontextfreier Grammatiken.

Aufgabe Typ B (Implementierung):

Prototypische Implementierung von Komponenten zum Aufbau probabilistischer kontextfreier Grammatiken.

Literatur:

vgl. 20. Probabilistische kontextfreie Grammatiken

P14. Parsing mit probabilistischen kontextfreien Grammatiken

Aufgabe Typ A (Theorie):

Vorstellung der Methoden und Algorithmen des probabilistischen Parsing.

Aufgabe Typ B (Implementierung):

Erweiterung eines (Standard-)Parsers (z.B. Earley, CKY, ..) um probabilistische Komponenten und Test am Datenmaterial.

Literatur:

vgl. 21. Probabilistisches Parsing