Instructors: Christian Wurm and Younes Samih
Overview
Inhalt dieses Kurses ist die Theorie und Anwendung von gewichteten Automaten.
Gewichtete Automaten sind eine Generalisierung von normalen Automaten, die auf der algebraischen Theorie der Halbringe beruht.
Wir führen zunächst die wichtigsten Konzepte aus der Theorie der Automaten und Halbringe ein,
und stellen dann die Bibliothek OpenFST vor, in der wir mittels Python gewichtete Automaten erstellen und manipulieren.
Wir werden dann verschiedene Anwendungen entwickeln, etwa eine Rechtschreibkontrolle, einen Tokenizer sowie evtl.
ein System zur automatischen Alinierung zweisprachiger Korpora.
Gleichzeitig sollen aber auch die theoretischen Aspekte besprochen werden, die diese Anwendungen möglich machen.
Courses
Here are some of the topics covered by this course.
- The Course Script
- Lecture 01: Automaten, Sprachen, Transduktoren und Relationen; Rationale Ausdrücke.
- Lecture 02: Halbringe: Wahrscheinlichkeiten, Gewichte, Tropischer und Arktischer Halbring. Eigenschaften und Anwendungen.
- Lecture 03: Gewichtete Automaten: Abbildungen von Sprachen/Relationen in Halbringe. Grundlegende Eigenschaften von gewichteten Automaten
- Lecture 04: Eigenschaften von WFST I: Komposition, Shortest distance, shortest path
- Lecture 05: Anwendungsbeispiel I: Part of speech Tagging and WFST
- Lecture 06: Einfhrung in OpenFST
- Lecture 07: Eigenschaften von Gewichteten Automaten II: Boolesche Hülle, Kleene Hülle, Determinisierung, Minimisierung
- Lecture 08: Anwendungsbeispiel II: Tokenisierung
- Lecture 09:Anwendungsbeispiel III: Spell-checking mit gewichteten Automaten
Software
- OpenFst Library (Finite-State Transducer Library).
- PyFst(A Python interface to OpenFst) Thanks to Victor
Chahuneau! .
- graphviz(Graphviz is open source graph visualization software).
- Ipython Notebook(The IPython Notebook is a web-based interactive computational environment where you can combine code execution, text, mathematics, plots and rich media into a single document).
Location and Time
Room: 2321.01.41, or
Room: CIP 04.87
Fridays 16:30 - 18:00.
Homework assignments