Parsing

Kurs Mo,Mi: 1315-1445 (HS 20 M2.031)
Modul Computerlinguistik (04-006-1010)
Lehrer Greg Kobele (GWZ H1 5.11)
Tutoren Max Möller, Max Polter

Literatur

  • Das Lehrbuch [H16] für den Kurs ist hier zu finden. (Login: Parsing2017; Password: [fragen Sie mich])
  • Zur Ergänzung der Parsing werden wir das Lehrbuch (G15) verwenden.

Mögliche Hausarbeitsthemen

Es folgt einige Vorschläge, die mit dem Lauf des Semesters erweitert werden. Sie sollen eine für Sie passende Aufgabe aussuchen. Die Numerierung ist so gemeint, daß e.g. 1a eine Aufgabe ist, 1b eine andere, usw. Aber wenn Sie finden, daß etwas zu einfach war, können Sie gerne noch eine Aufgabe hinzufügen!

  1. Suchen Sie eine linguistische Phänome aus, und schrieben Sie eine (Bigram) Grammatik dafür.
    1. Machen Sie eine Test-suite, eine Menge von wichtigen grammatischen und auch ungrammatischen Sätze, und bestätigen Sie, daß Ihre Grammatik diese Test-suite korrekt behandelt!
    2. Machen Sie eine Trainings-suite, eine Menge von Strukturen, anhand dessen Sie Ihre Grammatik extrahieren können. Versuchen Sie sie so klein wie möglich zu halten; erklären Sie warum Sie diese Sätze brauchen.
    3. Identifizieren Sie eine systematische Mackel an Ihre Analyse, daß an dem Bigramgrammatikformalismus liegt (und nicht an eine schwache Analyse der Phänomen). Wie könnte man den Formalismus modifizieren, um die Schwäche zu lindern?
  2. Implementieren Sie ein Komplexitätsmessgerät; definieren Sie ein Komplexitätsmaßstab (so wie wir im Kurs besprochen haben, um Zentraleinbettung zu erklären), und erweitern Sie einen Parser um die Komplexitätsprofil eines jeden Items mitzurechnen. Passt Ihre Maßstab zu einem bestimmten Phänomen?

    Hier sind folgende Artikeln relevant; sie erläutern sehr unterschiedliche Ideen davon, wie Attribute des menschlichen Sprachverarbeitungsmechanismus anhand eines Parsers zu erklären sind.

  3. Suchen Sie einen Artikel aus der folgenden Liste aus:

    • Adam Pauls & Dan Klein (2009) Hierarchical Search for Parsing
    • ibd. (2009) k-best A-star Parsing
    • Dan Klein & Chris Manning (2001) Parsing and Hypergraphs
    • Mark Johnson (1998) PCFG Models of Lingusitic Tree Representations

    Als Aufgabe:

    1. Schreiben Sie eine kommentierte Fassung des Artikels
    2. Versuchen Sie, eine Idee aus dem Artikel zu implementieren

Course Log

<2017-12-18 Mon>

Die Parse-Geschichte unseres Left-Corner Parsers entspricht eine In-Order Überquerung des Parse-Trees. Wir wollen diese Überquerung umkehren; d.h. aus einer Kette in 'In-Order' Notation der entsprechende Parse-Tree erhalten.

Das machen wir anhand von Dijkstras 'Shunting Yard' (Rangierbahnhof) Algorithmus.

<2017-12-13 Wed>

Die Left-corner Transform kann man online machen, indem man neue Parsing Operationen definiert, die die Operationen des Top-Down Parsers auf der transformierten Grammatik simulieren.

<2017-12-11 Mon>

Links-Rekursion stellt ein Problem dar für ein Top-Down Parser, indem es einen unendlich großen Suchraum definiert. Da ein Suchraum von zwei Sachen bestimmt ist:

  1. Operationen des Parsers
  2. Regeln der Grammatik

Kann man einen ungünstigen Suchraum korrigieren indem man entweder das Parser order die Grammatik ändert.

Wir redeten heute von der Left-corner transform, die eine neue Grammatik anhand der alten definiert. Die Strukturen der transformierten Grammatik sehen so aus, als ob man die Strukturen der alten eine Viertelstunde im Uhrzeigersinn rotiert hätte.

Wichtig ist, daß der Top-Down Suchraum der neuen Grammatik endlich ist, da die Liks-Rekursion wegrotiert wurde.

<2017-12-06 Wed>

Wir sind heute das Code für den Bottom-up parser durchgegangen.

<2017-12-04 Mon>

fällt aus wegen Dies Academicus

<2017-11-29 Wed>

Wir besprachen heute Bottom-up parsing. Wir sahen, dass shift und reduce überlappende Domänen haben, und erwähnten Strategien, solche Konflikte zu lösen.

<2017-11-27 Mon>

Heute haben wir gesehen, wir wir anhand unseren Bigramgrammatiken doch hoch entwickelten syntaktischen Analysen implementieren können. Wir haben Generalized phrase structure grammars (GPSG) eingeführt, und haben besprochen, wie Beschränkungen auf Bewegung umformuliert werden können, damit sie Bezug auf den Pfad zwischen bewegten Element und sein Spur nehmen.

<2017-11-22 Wed>

fällt aus wegen Buß- und Bettag

<2017-11-20 Mon>

  • Wir besprachen wie wir unsere bisher nur abstrakt vorgestellten Parser und Erkenner implementieren könnten.
  • Für einen Parser bräuchten wir nur ein Art u Weise aus einer Parsegeschichte einen Baum zu konstruieren.
  • Für einen Erkenner haben wir vier Aufgaben, die wir von einander trennen können:

    1. Suchraum konstruieren
    2. Suchraum durchqueren
    3. nicht-Endzustände wegwerfen
    4. gucken, ob was übrig bleibt

    In Haskell, dank ihrer Lazy Evaluation, können wir diese Aufgaben getrennt implementieren, und eins nach dem anderen laufen lassen

<2017-11-15 Wed>

  • Um die Intuition hinter der Schwierigkeitsgrund bei den Holzwegsätze zu formalisieren, haben wir Parsing als eine Suchprobleme neukonzipiert
  • Auf einen Suchraum kann man der Struktur eines Baumes anordnen, wo die Töchter eines Knoten sind die Zustände die mit einer Operation erreicht werden können
  • Bäume können in verschiedener Weise exploriert werden
    • Tiefensuche (depth first)
    • Breitensuche (breadth first)
    • iterative Tiefensuche (depth first iterative deepening)
  • Mit zusätzlicher Information können wir eine informiertere Entscheidung zum nächsten Schritt machen
    • Bestensuche (best first)
  • Tiefensucharten (iterative oder auch nicht) bieten eine einfache Vereinbarung mit der Intuition hinter der Holzwegphänomen an

<2017-11-13 Mon>

  • wir möchten nicht nur ein Parser qua Werkzeug haben, sondern auch ein Parser qua Theorie des menschlichen Sprachverwendungsvermögen
  • wir haben zwei Phänomene betrachtet, die mit linguistischen Daten folgender Art was zu tun haben
    1. Holzwegsätze
    2. Einbettung
  • beim Anblick der Parses von Sätze mit Rechts- und mit Zentraleinbettung, haben wir gesehen, daß die interne Komplexität der Parsingzustände der beiden Sätze unterscheiden sich rasch:
    1. die Items bei Rechtseinbettung haben eine begrentzte Komplexität
    2. die Komplexität der Items bei Zentraleinbettung wächst ohne Grenze (mit der Länge des Satzes)
  • Die Übereinstimmung der Komplexitätsprofil des Top Down Parsers mit der menschlichen Schwierigkeitsempfindung bei der Verarbeitung von Sätze mit unterschiedlichen Einbettungstypen ist nicht komplett:

      Links Zentral Rechts
    Mensch ok * ok
    Maschine * * ok
  • Lektüre
    • Im Lehrbuch G15 Kapitel 4 lesen (Kapitel 4)

<2017-11-08 Wed>

  • Wir haben 'Parsing Schemata' definiert, und sie verwendet, um Top Down Recognition (Theorie getriebene Erkennung) zu formulieren.
  • Aus einem Erkenner kann ein Parser konstruiert werden, wenn man die Items mit Infos zur Geschichte des Erkennungsprozesses ergänzt.

<2017-11-06 Mon>

  • Wir fingen endlich an, uns direkt mit Parsing zu beschäftigen!
  • Eine korrekte Perspektiv zu haben, ist daß Parsing einfach die Umkehrung der Funktion ist, die Strukturen in Klangen verwandeln
    • ein Problem dabei ist, daß diese Perspektiv auf Parsing so allgemein ist, daß sie uns nicht dabei weiterhilft zu verstehen, in wie fern die Besonderheiten der menschlichen Sprache das Parsingproblem für die Sprache einschränken und beeinflüssen.
  • Einer hilfreicheren Perspektiv nach konstruiert ein Parser eine neue Grammatik, eine so-genannte 'Schnittgrammatik' (Intersection grammar), die nur den Eingabesatz generiert, und zwar mit genau den Strukturen, die ihm die ursprungliche Grammatik zuordnet.

<2017-11-01 Wed>

  • Wir haben bemerkt, dass Bigramme u.a. deswegen als Grammatikmodel nicht ausreichend sind weil sie keinen Kontext berücksichtigen können
  • Wir haben Bigramme in zwei Richtungen verallgemeinert
    1. dass sie mehr Generationen auf einmal betrachten (n-gramme)
    2. dass sie mehr Geschwister auf einmal betrachten (bi- und n-gramme auf Bäume)
  • Notizen
  • Hausaufgabe
    • Im Lehrbuch Kapitel 6 (6.1-6.3, 6.6) lesen.
    • Exercises 1, 5, 6, und 7 machen

<2017-10-30 Mon>

  • Wir versuchten die Bigram Operationen algorithmisch zu verstehen
  • Wir haben die Bigram Operationen in Haskell implementiert

<2017-10-25 Wed>

  • Ich habe von Typeclasses in Haskell gesprochen; als konkrete Beispiele das Eq Class und das Functor Class.
  • Wir haben den Maybe Datentyp als Darstellung eines vielleicht nicht definiterten Rechnens eingeführt.
  • Wir haben Bigramme (oder auch Digramme) definiert, und erklärt, wie sie als eine Art einfache Grammatiken dienen können
  • Hausaufgabe
    • Im Lehrbuch Kapitel 4 lesen.
    • Exercises 3 bis 7 machen

<2017-10-23 Mon>

  • Wir haben Ketten als ein eingeschraenktes art Baum betrachtet, und gesehen, dass viele bekannte Operationen auf Ketten als eingeschraenkte Baumoperationen verstanden werden koennen.
  • Wir haben verschiedene tree traversal strategies (Baumdurchquerstrategien) definiert, und sie als Veralgemeinerungen von Operationen auf Ketten

<2017-10-18 Wed>

  • Wir haben über Typen im allgemeinen und über Haskells Typensystem gesprochen, und viel geübt, Funktionen auszudenken, die bestimmte Haskelltypen besassen.
  • Wir definierten Bäumen (unranked trees), und haben zusammen Definitionen von der Größe und der Tiefe eines Baumes ausgedacht.
  • Notizen
  • Hausaufgabe
    • Im Lehrbuch Kapitel 3 fertig lesen.
    • Exercises 1,2,3 und 4 machen

<2017-10-16 Mon>

  • Wir haben von Räpresentationen gesprochen, und wie unterschiedliche Räpresentationen ein und dasselbe Operation entweder einfacher oder komplexer machen können
  • Als Beispiel, haben wir eine Kettenvarietät definiert, die Verkettung direkt darstellt (\((u+v)\) ist eine Kette die die Verkettung von u und v darstellt), und gesehen, daß in dieser Kettenräpresentation Identität von Ketten (intuitiv gesehen) nicht ein und dasselbe ist wie Identität von Räpresentationen
  • Wir haben Auswertungsstrategien besprochen, und die von Haskell (Bedarfsauswertung) mit anderen verglichen
  • Hausaufgabe
    • Im Lehrbuch Kapiteln 3.1, 3.2 und 3.3 lesen

<2017-10-11 Wed>

  • Wir haben einiges aus der Logik Vorlesung kurz wiederholt
  • Wir haben Monoide besprochen, einige Beispiele gegeben, und behauptet, die Menge aller Zeichenketten über eine Zeichenmenge Σ sei eine Monoid
  • Wir haben eine alternative Representation von Zeichenketten definiert (von rechts nach links), und versucht, alte Funktionen anhand dieser Representation zu definieren
  • Hausaufgabe
    • Im Lehrbuch [H16] Kapiteln 1 und 2 lesen
    • Über Exercises 1-4 im Abschnitt 1.7 nachdenken
    • Exercise 1 im Abschnitt 2.7 machen

<2017-10-09 Mon>

  • Wir haben die Kursplannung besprochen
  • … und sind Induktive Definitionen begegnet, anhand des Beispiels von Zeichenketten
  • Notizen
  • Hausaufgabe
    • Haskell installieren (Installationsanleitung hier)

    Falls Sie keine Administratorrechten auf Ihrem Rechner haben könnten Sie folgendes tun (und/oder mir einen Email schicken, dann würde ich versuchen, mich mit dem Uni Rechenzentrum auseinandersetzen):

    1. Ein Konto mit codenvy.io erstellen
    2. Ein neues Workspace beantragen
      • Bei Select Stack wähle 'Blank', dann ganz unten auf dem grünen Create clicken
    3. Am Prompt:

      > sudo apt-get update
      > sudo apt-get install haskell-platform
      
    4. Im Projects Explorer auf Create Project… clicken
      • Blank aussuchen
      • einen Projektname erfinden (vielleicht: Computerlinguistik)
      • Create File… clicken, und einen Filename aussuchen (vielleicht: test.hs)
        Wichtig!
        der Name soll mit ".hs" enden
    5. Die neue Datei clicken, und Haskell code reinschreiben
    6. Am Prompt:

      > cd Computerlinguistik
      > ghci
      > :load "test.hs"
      

Author: Greg Kobele

Created: 2018-10-16 Tue 01:04

Validate