Endliche Automaten für die Sprachverarbeitung
PD Dr. Karin Haenelt
Hauptseminar Computerlinguistik
Universität Heidelberg
Sommersemester 2009
Projektthemen
 


Teil 2: Seminarprojekte: Anwendungen, Implementierungen und Experimente

Ziel der Seminarprojekte ist es, Modellierungsprinzipien und Algorithmen für Zwecke der Sprachverarbeitung einzusetzen und zu testen. Jedes Projekt bearbeitet eine bestimmte Aufgabe. Hierfür sind die jeweils benötigten Modellierungsprinzipien und Algorithmen anwendungsspezifisch zusammenzustellen und zur Modellierung und Verarbeitung sprachlicher Gegebenheiten anzuwenden. Der Schwerpunkt kann je nach Thema auf der Modellierung oder Implementierung liegen. Die Algorithmen zur Verarbeitung sind je nach Aufgabenstellung zu installieren, partiell oder vollständig zu implementieren und an Beispielmaterial zu testen.
Über die angegebenen Themen hinaus sind auch eigene Vorschläge möglich.

*Thema allgemein empfohlen
(*)Thema bei entsprechendem Interesse und/oder Vorkenntnissen empfohlen

Modellierung von Lexika und Regeln und ihre Verarbeitung mit endlichen Automaten und Transduktoren

(MOD 01) Entwurf eines Prototyps zur Verarbeitung einer Morphologie des Deutschen / Englischen / ..
(MOD 02) Mechanismen zur Modellierung morphologischer Phänomene
(MOD 03) * Der lexc-Kompiler
 

Installation und Test ausgewählter Werkzeuge und Programmbibliotheken

(LIB 01) Programmbibliotheken
(LIB 02) * XEROX-Compiler für endliche Automaten
(LIB 03) * OpenFST
(LIB 04) (*) OpenKernel Library: Gewichtete Transduktoren und maschinelles Lernen
(LIB 05) * Helsinki Finite-State Transducer Technology (HFST)
 

Implementierung und Test ausgewählter Algorithmen

(ALG 02) Nicht-deterministische Traversion eines endlichen Automaten
(ALG 03) Generierung von Automaten aus regulären Ausdrücken
(ALG 04) Erzeugung minimaler endlicher Automaten
(ALG 05) Determinisierung von Transduktoren
(ALG 06) Komposition von Transduktoren
 

Endliche Automaten und Transduktoren

(FSA 01) * Filtern von Stoppwörtern mit endlichen Automaten
(FSA 02) * Flaches Parsing mit endlichen Automaten
(FSA 03) * Partielles Parsing mit kaskadierten endlichen Automaten / Transduktoren
(FSA 04) (*) Parsing mit Transduktoren
(FSA 05) (*) Parsing: Konstruktion lokaler Grammatiken
(FSA 06) * Informationsextraktion mit endlichen Automaten
(FSA 08) (*) Extraktion von Head-Modifier-Paaren aus Texten
(FSA 07) * Informationsextraktion mit Transduktoren
(FSA 09) (*) Part-of-Speech-Tagging mit Transduktoren
(FSA 10) (*) Verarbeitung gesprochener Sprache mit gewichteten Transduktoren
(FSA 11) (*) Maschinelle Übersetzung mit gewichteten Transduktoren
(FSA 12) (*) Maschinelle Übersetzung mit stochastischen Transduktoren
 

Hidden Markov Models

(HMM 01) (*) Part-of-Speech-Tagging mit dem Viterbi-Algorithmus
(HMM 02) (*) Hidden Markov Models in der Verarbeitung gesprochener Sprache
(HMM 03) (*) Konversion von Hidden Markov Models in Finite State Transducers
 

Anwendungssysteme

(HLT-IE-Systeme) * Informationsextraktion: Systeme

Beschreibung der Projekte

Entwurf eines Prototyps zur Verarbeitung ausgewählter Phänomene der Morphologie des Deutschen / Englischen / ...

Ziel des Projekt ist der Entwurf eines Systems zur morphologischen Analyse oder Generierung morphologischer Phänomene. Kern des Projekts ist der ausgewählte Modellierungsgegenstand. Beispiele möglicher Phänomenbereiche sind: Flexion und Derivationen der Verben, Flexion und Komposition der Substantive, Flexion und Derivation der Adjektive. Der ausgewählte Modellierungsgegenstand ist linguistisch zu beschreiben und es ist eine möglichst günstige Darstellung als Automat zu entwickeln. Projektgegenstand sollen sein:

  • Analyse der Anforderungen (welche Erscheinungen gibt es?)
  • Entwurf der Systemarchitektur (welche Beschreibungen (Lexika) werden gebraucht (Stämme, Flexionen, ..))
  • Entwurf der Teilautomaten
  • exemplarische Modellierung ausgewählter Einträge
  • Beschreibung des Analyse oder Generierungsverfahrens, ggf. durch exemplarische Implementierung ausgewählter Komponenten (in Python, Perl, Flex, Java, C, C++, ..)
  • Es könnte beispielsweise eine morphologische Analyse modelliert werden mit dem Werkzeug FLEX. Stichworte sind: Modellierung von Stamm- und Endungslexika, Verwendung der Startbedingungen in FLEX zur Modellierung der Teillexika und der Verbindungen zwischen den Teillexika. vgl. Kurs Flex, dort unter "Flex" das Beispiel "Test von Startbedingungen".

    Literatur zu morphologischen Phänomenen:

    canoo-net
    Wortgrammatik
    Kunze, Jürgen (2000)
    Morphologie Vorlesungsskript. Humboldt-Universität zu Berlin.
    Weinrich, Harald; unter Mitarb. v. Maria Thurmair, Eva Breindl, Eva-Maria Willkop (1993)
    Textgrammatik der deutschen Sprache. Mannheim, Leipzig, Wien, Zürich: Duden Verlag.

    Literatur zu morphologischen Systemen:

    Beesley Kenneth R. und Lauri Karttunen (2003)
    Finite-State Morphology. Distributed for the Center for the Study of Language and Information. 696 p. (est.). 2003 Series: (CSLI-SCL) Studies in Computational Linguistics
    Lauri Karttunen, Ronald M. Kaplan, und Annie Zaenen (1992)
    Two-Level Morphology with Composition. In: proceedings of Coling 92. International Conference on Computational Linguistics, Vol. I 141-148. July 25-28, 1992. Nantes, France. Online

    morphologische Systeme:

    Mechanismen zur Modellierung morphologischer Phänomene

    Ziel des Projektes ist es, besondere Ausdrucksmittel zur Modellierung sprachlicher Phänomene mit endlichen Automaten vorzustellen, ihre Funktionsweise und Anwendungsgebiete zu erläutern und ggf. exemplarische Implementierungen vorzustellen. Solche Ausdrucksmittel sind z.B.

    Literatur:

    Beesley Kenneth R. und Lauri Karttunen (2003)
    Finite-State Morphology. Distributed for the Center for the Study of Language and Information. 696 p. (est.). 2003 Series: (CSLI-SCL) Studies in Computational Linguistics
    Jurafsky, Daniel; Martin James H. (2007, ¹2000) mit Beiträgen von Andrew Kehler, Keith Vander Linden, Nigel Ward
    Speech and Language Processing. An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition Upper Saddle River, N.J.: Prentice Hall.
    Karttunen, Lauri (1995)
    The Replace Operator. In: Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics. ACL-95, S. 16-23, Boston, Massachusetts. mltt-95-03.pdf

    Der Lexikon-Compiler Lexc

    Der Lexc-Lexikon-Compiler ist ein Werkzeug zur Erstellung von Lexika und zur Kompilation dieser Lexika in endliche Transduktoren. Es handelt sich um eine Entwicklung von XEROX. Inzwischen ensteht eine open source version im Rahmen der Helsinki Finite-State Transducer Technology (HFST).

    Literatur und Links

    Programmbibliotheken

    Für einige Programmiersprachen gibt es Bibliotheken (Klassen bzw. Funktionen) unterschiedlichen Umfangs und unterschiedlicher Granularität für das Arbeiten mit endlichen Automaten. Im Projekt sollen für jeweils ausgewählte Programmiersprachen (z.B. Java, C, C++) solche Bibliotheken ermittelt, installiert und evaluiert (z.B. Funktionsumfang, Effizienz) werden. Die Ergebnisse sollen vorgestellt werden.

    Finite State Manipulation Software (Liste aus FSMNLP 2008, Call for Papers)

    XEROX-Compiler für endliche Automaten

    Der Xerox-Compiler für endliche Automaten ermöglicht die Eingabe eines regulären Ausdrucks in einem Textfenster (Web-Appliaktion) und dessen Compilation zu einem endlichen Automaten. Je nach eingegebenem Ausdruck ist das Ergebnis entweder ein einfacher Automat oder ein Transduktor.

    Im Referat soll die Web-Applikation und die theoretische Basis dieser Web-Applikation vorgestellt werden.

    frühere Webseite: http://www.xrce.xerox.com/competencies/content-analysis/fsCompiler/

    nicht mehr online, download: http://www.fsmbook.com; auch enthalten auf CD in Beesley/Karttunen 2003, Finite State Morphology (CLSI Publications 2003)

    OpenFST

    "OpenFst is a library for constructing, combining, optimizing, and searching weighted finite-state transducers (FSTs). Weighted finite-state transducers are automata where each transition has an input label, an output label, and a weight. The more familiar finite-state acceptor is represented as a transducer with each transition's input and output label equal. Finite-state acceptors are used to represent sets of strings (specifically, regular or rational sets); finite-state transducers are used to represent binary relations between pairs of strings (specifically, rational transductions). The weights can be used to represent the cost of taking a particular transition."

    OpenKernel Libray

    "OpenKernel is a library for creating, combining and using kernels for machine learning applications. The current focus of library is on rational kernels. It is based on the OpenFst library. This library was developed by C. Allauzen and M. Mohri. It is intended to be comprehensive, flexible, efficient and scale well to large-scale problems. It is an open source project distributed under the Apache license external. This work has been partially supported by Google Inc." OpenKernel Library

    Helsinki Finite-State Transducer Technology (HFST)

    "The goal is to create a high-performing, maintainable and modifiable set of tools for morphological analysis and generation according to the principles of open source software." Helsinki Finite-State Transducer Technology (HFST)

    Nicht-deterministische Traversion eines endlichen Automaten

    Ziel des Projekts ist die Implementierung und experimentelle Anwendung eines Algorithmus zur nicht-deterministischen Traversion eines endlichen Automaten. Der Algorithmus kann eine Agenda oder ein Backtracking-Verfahren verwenden. Sofern die Daten für den Automaten nicht von Projekt ALG01 zur Verfügung gestellt werden, können handkodierte Testdaten geringen Umfangs verwendet werden.

    Literatur:

    Karin Haenelt (2009)
    Endliche Automaten: Akzeptoren. 21.04.2009 (erste Version 15.01.2003) 51 S. pdf, ppt
    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]
    Jurafsky, Daniel; Martin James H. (2007, ¹2000)
    Regular Expressions and Automata. In: Jurafsky, Daniel; Martin James H. (2007, ¹2000) mit Beiträgen von Andrew Kehler, Keith Vander Linden, Nigel Ward Speech and Language Processing. An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition Upper Saddle River, N.J.: Prentice Hall.

    Generierung von Automaten aus regulären Ausdrücken

    Ziel des Projekts ist die Implementierung von Algorithmen zur Umsetzung regulärer Ausdrücke in endliche Automaten.

    Für alle Algorithmen gibt es Folien (s. Literatur), die die meist sehr knappen Spezifikationen in der Literatur mit Beispielen erläutern. Im Projekt ist folgendes zu erarbeiten:

    Literatur:

    Karin Haenelt (2006)
    Endliche Automaten: Äquivalenz regulärer Ausdrücke und endlicher Automaten. Kursfolien. 19.05.2006 (¹ 15.01.2003) 12 S. [pdf] [pdf:2] [pdf:6] ppt
    Karin Haenelt (2009)
    Parsing regulärer Ausdrücke. Kursfolien 25.04.2009 17 S. [pdf] ppt
    Karin Haenelt (2007)
    Überführung regulärer Ausdrücke in endliche Automaten. Der Algorithmus von Thompson. Kursfolien 05.05.2007 (¹27.05.2005). 21 S. [pdf] [ppt]
    Karin Haenelt (2007)
    Überführung regulärer Ausdrücke in endliche Automaten. Der Algorithmus von Glushkov und McNaughton/Yamada. Kursfolien 14.09.2007 (¹ 20.03.2005). 35 S. [pdf] [ppt]
    Karin Haenelt (2005)
    Überführung regulärer Ausdrücke in endliche Automaten. Der Algorithmus von Fox. Kursfolien 20.03.2005. 10 S. [pdf] [pdf:2] [pdf:6] ppt
    Aho, Alfred V.; Sethi, Ravi und Jeffrey D. Ullman (1986)
    Compilers. Principles, Techniques and Tools. Addison-Wesley Publishing Company.
    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]

    Minimalisierung endlicher Automaten

    Ziel des Projekts ist es, den Minimalisierungsalgorithmus nach Myhill bzw. Nerod zu implementieren und zur Minimalisierung eines endlichen Automaten anzuwenden. Sofern die Daten für den Automaten nicht von Projekt ALG01 zur Verfügung gestellt werden, können handkodierte Testdaten geringen Umfangs verwendet werden.

    Literatur:

    Karin Haenelt (2004)
    Minimierung endlicher Automaten. 15.04.2004. 19 S. pdf, pdf:2, pdf:6, ppt
    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]

    Determinisierung von Transduktoren

    Ziel des Projekts ist es, den Determinisierungsalgorithmus nach Mohri zu implementieren und zur Determinisierung eines Transduktors anzuwenden. Sofern die Daten für den Automaten nicht von Projekt ALG01 zur Verfügung gestellt werden, können handkodierte Testdaten geringen Umfangs verwendet werden.

    Literatur:

    Karin Haenelt (2005)
    Transduktoren für die Sprachverarbeitung. Determinisierung. 23.06.2005 (¹ 15.01.2003). 36 S. pdf, pdf:2, pdf:6, ppt
    Karin Haenelt (2004)
    Determinisierung von Transducern. Eine Erläuterung des Algorithmus von Mohri. 15.02.2004. 7 Seiten.
    pdf, html
    Mohri, Mehryar (2009)
    Weighted automata algorithms. In Werner Kuich, Heiko Vogler, and Manfred Dorste, editors, Handbook of weighted automata. Springer (to appear), 2009.
    Mohri, Mehryar (1996)
    On some Applications of Finite-state Automata Theory to Natural Language Processing. In: Journal of Natural Language Engineering, Bd. 2, S. 1- 20.

    Komposition von Transduktoren

    Ziel des Projekts ist die Implementierung und experimentelle Anwendung eines Algorithmus zur Komposition zweier Transduktoren (Algorithmus nach Mohri). Die Komposition zweier Transduktoren ermöglicht es, zwei Transduktoren, die in Serie hintereinander laufen, durch einen komplexeren Transduktor zu ersetzen. Die Komposition erfolgt durch Schnittbildung der Ausgaben von T1 mit den Eingaben von T2. Sofern die Daten für den Automaten nicht von Projekt ALG01 zur Verfügung gestellt werden, können handkodierte Testdaten geringen Umfangs verwendet werden.

    Literatur:

    Karin Haenelt (2005)
    Transduktoren für die Sprachverarbeitung. Komposition. 05.06.2005 (¹ 15.01.2003). 29 S. pdf, pdf:2, pdf:6, ppt
    Mohri, Mehryar (2009)
    Weighted automata algorithms. In Werner Kuich, Heiko Vogler, and Manfred Dorste, editors, Handbook of weighted automata. Springer (to appear), 2009.
    Mohri, Mehryar (1997)
    Finite State Transducers in Language and Speech Processing. In: Computational Linguistics, 23, 2, 1997, S. 269-311.

    Filtern von Stoppwörtern mit endlichen Automaten

    Für viele Anwendungen wird das Textmaterial, das durch die Analyseverfahren läuft, zunächst erst einmal "vorbereitet". Dazu wird mit Hilfe von Filtern das Material aussortiert, das in der Verarbeitung nicht betrachtet werden soll. Zur effizienten Verarbeitung werden hierzu endliche Automaten verwendet. Im Projekt soll exemplarisch das Filtern von "Stoppwörtern" mit diesem Verfahren gezeigt werden. Als Grundlage kann ein Artikel verwendet werden, der die Konstruktion und Anwendung eines solchen Automaten beschreibt und den Quellcode in C angibt.

    Literatur:

    Fox, C. (1992)
    Lexical Analysis and Stoplists. In: Frakes, William; Baeza-Yates, Ricardo (eds.): Information Retrieval. Data Structures and Algorithms. Prentice Hall: New Jersey, 1992, Kap. 7 (S.102-130) Site.es: Table of Contents and Source Code
    Site.cl: Table of Contents and Source Code
    Karin Haenelt (2005)
    Überführung regulärer Ausdrücke in endliche Automaten. Der Algorithmus von Fox. Kursfolien 20.03.2005. 10 S. [pdf] [pdf:2] [pdf:6] ppt

    Flaches Parsing mit endlichen Automaten

    Ziel des Projekts ist die Duchführung eines robusten massendatentauglichen flachen Parsingverfahrens. Dabei sollen Wortklassen ausgezeichnet werden, Nominal- und Verbalgruppen markiert werden, Köpfe phrasaler Einheiten gekennzeichnet und syntaktische Funktionen gefiltert werden. Das Verfahren ist in dem angegebenen Artikel beschrieben. Im Projekt müssen die regulären Ausdrücke spezifiziert werden, die zur Auszeichnung der genannten Information geeignet sind. Zur Erzeugung der Automaten und zur Filterung der Information kann ein Automatengenerator oder ein Interpreter regulärer Ausdrücke verwendet werden ((F)Lex, JLex, Perl).

    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.ist.psu.edu/grefenstette96light.html

    Partielles Parsing mit kaskadierten endlichen Automaten

    Massendatentaugliche Parsingverfahren müssen robust sein. Zu diesem Zweck bestimmen solche Verfahren die Information, die mit rein formalen Erkennungsverfahren zuverlässig erkannt werden kann, und beschränken sich auf die Erkennung dieser Information. Im partiellen Parsing mit kaskadierten Automaten wird die jeweils gewonnene Information stufenweise weiterverarbeitet: Die Ausgabe eines Automaten dient als Eingabe des nächsten Automaten. Die Ebenen, die dabei bearbeitet werden, umfassen: Worte, Chunks, Phrasen und Sätze. Chunks sind die nicht-rekursiven Kerne der Konstituenten, die syntaktisch zuverlässig erkannt werden können.
    Ziel des Projektes ist es, einen Ansatz des partiellen Parsing mit kaskadierten endlichen Automaten zumindest teilweise zu implementieren und vorzustellen. Zur Implementierung kann entweder eine eigene Automatenkaskade entwickelt werden, oder es können Generatoren endlicher Automaten ((F)Lex, JLex) oder Interpreter regulärer Ausdrücke verwendet werden.

    Abney, Steven (1996)
    Partial Parsing via Finite State Cascades. In: Journal of Natural Language Engineering 2(4): 337-344. pdf ps
    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. pdf ps
    Abney, Steven (1996)
    Tagging and Partial Parsing. In: Ken Chruch, Steve Young und Gerrit Bloothooft (Hgg.) Corpus-Based Methods in Language and Speech. Kluwer Academic Publishers, Dordrecht. (hier Abschnitt 2.5) pdf ps
    Abney, Steven (1997)
    The SCOL Manual, April 28, 1997. tar.gz

    Parsing mit Transduktoren (1)

    Der Artikel von Emmanuel Roche präsentiertAnsätze des robusten und effizienten Parsens mit Transduktoren, und zwar: einen top-down-Parser für kontextfreie Grammatiken, eine Behandlung der Morphologie, ein Parser für Transformationsgrammatiken mit der Vorstellung der Behandlung der Phänomene: Modalverben, Satzkomplemente, Hilfsverbkonstruktionen, und einen Parser für tree adjoining Grammatiken. Ziel des Projektes ist es, diese Ansätze vorzustellen und/oder partiell zu implementieren. (z.B. auch durch Nachbildung mit FLex/JLex, Perl, ...).

    Literatur:

    Roche, Emmanuel(1997)
    Parsing with Finite State Transducers. In: Roche, Emmanuel und Yves Schabes (Eds.) (1997) Finite-State Language Processing. Cambridge (Mass.) und London: MIT Press. S. 241-282.

    Parsing mit Transduktoren (2)

    Der Artikel von Maurice Gross präsentiert den Aufbau lokaler lexikalisierter Grammatiken, mit denen die Satzmuster einer Sprache als lexikalische Muster beschrieben werden. Diese Grammatiken werden als Transducer repräsentiert und stufenweise zum Parsing eingesetzt. Ziel des Projektes ist es, den Ansätz vorzustellen und/oder partiell zu implementieren und/oder durch Nachbildung mit FLex/JLex, Perl, ... an einem Corpus zu evaluieren.

    Literatur:

    Maurice Gross(1997)
    The Construction of Local Grammars. In: Roche, Emmanuel und Yves Schabes (Eds.) (1997) Finite-State Language Processing. Cambridge (Mass.) und London: MIT Press. S. 329-354.
    Mehryar Mohri (2005)
    Local Grammar Algorithms In: Antti Arppe, Lauri Carlson, Krister Lindn, Jussi Piitulainen, Mickael Suominen, Martti Vainio, Hanna Westerlund, and Anssi Yli-Jyr, editor, Inquiries into Words, Constraints, and Contexts. Festschrift in Honour of Kimmo Koskenniemi on his 60th Birthday. pages 84-93. CSLI Publications, Stanford University, 2005.

    Informationsextraktion mit endlichen Automaten

    Manche Informationseinheiten lassen sich mit regulären Ausdrücken bereits relativ treffend beschreiben, z.B.

    Robustheit in der Verarbeitung großer Corpora und Schnelligkeit sind wesentliche Ziele, die den Einsatz endlicher Automaten und die Beschreibung von Informationseinheiten mit regulären Ausdrücken motivieren.
    In Seminarprojekten sollen die vorgestellten Methoden z.B. mit Flex oder Perl oder ... implementiert und experimentell angewendet werden. Ein Projekt sollte folgende Aufgaben umfassen:

    Literatur

    Programmdokumentation. Flex
    (Bestandteil der gnu-Tools, verfügbar unter Unix, Linux, Windows: Flex-Homepage)
    Appelt, Douglas E. und Israel, David J. (1999):
    Introduction to Information Extraction Technology. A Tutorial prepared for IJCAI-99.
    Berk, Elliot (1997ff)
    JLex - A lexical analyzer generator for Java. Department of Computer Science, Princeton University. (Dokumentation, Benutzungsanleitung und Quellcode)
    Dreyer, Markus (2001)
    Informationsextraktion mit endlichen Automaten.
    http://www.coling.de/markus// [mail]
    Dreyer, Markus (2001)
    Eigennamen extrahieren - Try it online!
    http://www.coling.de/markus/ [mail]
    Grefenstette, Gregory (1999)
    Light Parsing as Finite State Filtering. In: Kornai 1999, S. 86-94
    Hopcroft, John E. Rajeev Motwani und Jeffrey D. Ullman (2001)
    Einführung in die Automatentheorie, Formale Sprachen und Komplexität. S. 118-124. Pearson Studium
    engl. Original: Introduction to Automata Theory, Languages and Computation. Addison-Wesley. www-db.stanford.edu/~ullman/ialc.html
    Jurafsky, Daniel; Martin James H. (2007, ¹2000)
    Regular Expressions and Automata. In: Jurafsky, Daniel; Martin James H. (2007, ¹2000) mit Beiträgen von Andrew Kehler, Keith Vander Linden, Nigel Ward Speech and Language Processing. An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition Upper Saddle River, N.J.: Prentice Hall.
    Kornai, András (Hrsg.) (1999):
    Extended Finite State Models of Language. (Studies in Natural Language Processing). Cambridge: Cambridge University Press.
    Neumann, Günter (2001):
    Informationsextraktion. In: Klabunde et al. (eds.): Computerlinguistik und Sprachtechnologie - Eine Einführung. Heidelberg: Spektrum Akademischer Verlag.
    Richter, Helmut (2004)
    Reguläre Sprachen, reguläre Ausdrücke. München: Leibniz Rechenzentrum der Bayerischen Akademie der Wissenschaften. 08.07.2004.

    Informationsextraktion mit Transduktoren

    Der unten genannte Artikel präsentiert ein System zur Extraktion von Information mit Transducern. Ziel des Projektes ist es, den Ansätz vorzustellen und/oder partiell zu implementieren und/oder durch Nachbildung mit FLex/JLex, Perl, ... an einem Corpus zu evaluieren.

    Literatur:

    Jerry R. Hobbs, Douglas Appelt, John Bear, David Israel, Megumi Kameyama, Mark Stickel und Mabry Tyson(1997)
    FASTUS: A Cascaded Finite-State-Transducer for Extracting Information from Natural Language Text.. In: Roche, Emmanuel und Yves Schabes (Eds.) (1997) Finite-State Language Processing. Cambridge (Mass.) und London: MIT Press. S. 383-406.

    Extraktion von Head-Modifier-Paaren aus Texten

    Zur Approximation semantischer Analysen dient die Bestimmung von sogenannten Head-Modfier-Paaren in Textsätzen. Head-Modifier-Paare sollen näherungsweise semantische Prädikationen darstellen. Beispiel: zu "Das Architektenteam entwirft ein Sportzentrum" sollen die HM-Paare [H:entwerfen M: Architektenteam] und [H: entwerfen M: Sportzentrum] gebildet werden. Für die Gewinnung von HM-Paaren können beispielsweise Transduktoren verwendet werden.

    Zur Realisierung können beispielsweise verwendet werden: Lex/Flex oder der Ansatz von Grefenstette oder AGFL-Tools(erhältlich bei den Autoren, ggf. Nachbesserungen zur Installation von System und Grammatiken erforderlich)

    Grefenstette, Gregory (1999)
    Light Parsing as Finite State Filtering. In: Kornai 1999, S. 86-94
    Kornai, András (Hrsg.) (1999):
    Extended Finite State Models of Language. (Studies in Natural Language Processing). Cambridge: Cambridge University Press.
    AGFL Grammar Work Lab
    nijmeegs instituut voor informarica en informatiekunde. Natural Language Processing Tools under GNU public licence (u.a. Transducer: Text -> head-modifier-pairs (englisch). http://www.cs.kun.nl/agfl/

    Part-of-Speech-Tagging mit Transduktoren

    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.
    Ziel dieses Projekts ist es, einen deterministischen Tagger mit Finite-State-Transducers zu implementieren.

    Literatur:

    Roche, Emmanuel und Schabes, Ives (1995)
    Deterministic Part-of-Speech Tagging with Finite-State Transducers. In: Computational Linguistics. Bd. 21, Nr. 2, S. 227-253. auch in: Roche, Emmanuel und Yves Schabes (Eds.) (1997) Finite-State Language Processing. Cambridge (Mass.) und London: MIT Press. S. 241-282.

    Hinweis auf Druckfehler: in der Fassung von 1995 fehlt dem Transduktor T5 (figure 19), der die lokale Extension von Transduktor T4 darstellen soll, die Kante ({0,1},b,d,{2}). Die Fassung von 1997 enthält diese Kante.

    Verarbeitung gesprochener Sprache mit gewichteten Transduktoren

    Ziel dieses Projekts ist die Vorstellung und ggf. partielle Implementierung von Verfahren zur Verarbeitung gesprochener Sprache (Analyse oder Generierung) mit Transduktoren.

    Literatur:

    Mohri, Mehryar (1997)
    On the use of sequential transducers in natural language processing. In: Roche, Emmanuel und Yves Schabes (Eds.) (1997) Finite-State Language Processing. Cambridge (Mass.) und London: MIT Press.
    Pereira, Fernando C. N. & Riley, Michael D. (1997)
    Speech recognition by composition of weighted finite automata. Roche, Emmanuel und Yves Schabes (Eds.) (1997) Finite-State Language Processing. Cambridge (Mass.) und London: MIT Press.
    Sproat, Richard (1995)
    A finite-state architecture for tokenization and grapheme-to-phoneme conversion in multi-lingual text analysis. In: Proceedings of the ACL SIGDAT Workshop, Dublin, Ireland.

    Maschinelle Übersetzung mit gewichteten Transduktoren

    Ziel dieses Projekts ist die Vorstellung und ggf. partielle Implementierung von Verfahren zur Maschinellen Übersetzung mit Transduktoren.
    Ein Artikel ist unten als Beispiel genannt. Über die Eingabe von Stichworten wie "finite transducer machine translation" findet man auch andere Artikel zum Thema. Ein Artikel soll ausgewählt und als Basis für das Projekt verwendet werden.

    Meist werden für die maschinelle Übersetzung Transduktoren mit probabilistischen Verfahren verbunden. Themen der Literatur sind die Form der Transduktoren, die probabilistischen Modelle und Lernverfahren.

    Literatur:

    Vilar, Juan Miguel & Jiménez, Victor Manual & Amengual, Juan Carlos & Castellanos, Antonio & LLorens, David & Vidal, Enrique (1999)
    Text and speech translation by means ob subsequential transducers. In: Kornai, András (Ed.) (1999) Extended Finite State Models of Language. (Studies in Natural Language Processing). Cambridge: Cambridge University Press.

    Maschinelle Übersetzung mit stochastischen Transduktoren

    Ziel dieses Projekts ist ein Referat über den angegebenen Artikel. Der Artikel führt stochastische Transduktoren ein und zeigt wie Modelle automatisch aus Daten gewonnen werden knnen. Die Anwendung in der Maschinellen Übersetzung wird erlätert.

    Literatur

    Part-of-Speech-Tagging mit dem Viterbi-Algorithmus

    Der Viterbi-Algortihmus ist ein Klassiker aus dem Kanon computerlinguistisch relevanter Algorithmen. Er ist das Standardverfahren zur Analyse mit Hidden Markov Modellen. Einsatzbereiche sind z.B. die Erkennung gesprochener Sprache und die Auszeichnung von Texten mit Wortartmarkierungen (part-of-speech tagging).

    Aufgabe:

    Literatur:

    Allen, James (1995)
    Natural Language Understanding. 2nd edition. Addison-Wesley Publishing Co. Kap. 7 S. 189ff
    Haenelt, Karin (2002)
    Der Viterbi-Algorithmus im Part-of-Speech Tagging. Kursfolien. 11. Mai 2002. 31 S. (letzte Änderung 18.07.2002) html, pdf, pdf:2, pdf:6, ps:2, ps:6, ppt
    Haenelt, Karin (2003)
    Der Viterbi-Algorithmus. Eine Erläuterung der formalen Spezifikation am Beispiel des Part-of-Speech Tagging. Kursskript. 11.05.2002 (letzte Änderung 25.06.2003). 22 S. html, pdf, doc, ps
    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.

    Hidden Markov Models in der Verarbeitung gesprochener Sprache

    Jurafsky, Daniel; Martin James H. (2007, ¹2000)
    Automatic Speech Recognition. In: Jurafsky, Daniel; Martin James H. (2007, ¹2000) mit Beiträgen von Andrew Kehler, Keith Vander Linden, Nigel Ward Speech and Language Processing. An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition Upper Saddle River, N.J.: Prentice Hall.

    Konversion von Hidden Markov Models in Finite State Transducers

    Hidden Markov Models und gewichtete Finite State Transducers sind einander sehr ähnlich. Allerdings haben Finite State Transducers in der Regel in der Verarbeitung das bessere Laufzeitverhalten. In einigen Fällen können Hidden Markov Models in äquivalente Transduktoren überführt werden, in anderen Fällen ist zumindest ein angenähertes Verhalten zu erreichen. Im Projekt sind die Methoden der Überführung vorzustellen und exemplarisch zu implementieren.

    Literatur:
    Kempe, André (1998)
    Look-Back and Look-Ahead in the Conversion of Hidden Markov Models into Finite State Transducers. in: D.M.W. Powers (Hg.): New Methods in Language Processing and Computational Language Learning. Proceedings of the Second Conference on Computational Language Learning (CoNLL-98), 22-24 Januar, Sydney, Australien.
    Kempe, André (1997)
    Finite State Transducers approximating Hidden Markov Models. In: Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics. S. 460-467. Madrid, Spanien.

    Informationsextraktion: Programmbibliotheken und Systeme

    Es gibt inzwischen eine Reihe von Programmbibliotheken und Systemen für die Informationsextraktion. In der Regel basieren sie auf endlichen Transduktoren. Ziel der Seminarprojekte ist es, eine Bibliothek bzw. ein System zu installieren, zu testen und vorzustellen (mit dem Schwerpunkt auf der Finite State Technologie).

    Literatur:

    Douglas E. Appelt (1998)
    The Common Pattern Specification Language In: TIPSTER TEXT PROGRAM PHASE III: Proceedings of a Workshop held at Baltimore, Maryland, October 13-15, 1998

    Bibliotheken und Systeme: