Kurs:Natürliche Sprachverarbeitung

Hier entsteht ein Kurs über natürliche Sprachverarbeitung. Der Kurs wird bis Ende 2014 geplant, um anschliessend 2015 im Sommer im Rahmen einer deutschen Schülerakademie gehalten werden zu können.

Teilnehmer

Die 16 Teilnehmer müssen in den vorletzten 2 Jahrgangsstufen sein. Da das Gymnasium inzwischen nur noch 8 Jahre dauert, ist also von 16-18 jährigen Teilnehmern auszugehen.

Vermutlich haben zumindest ein paar noch nichts in Richtung Wahrscheinlichkeitstheorie gemacht. Begriffe wie "bedingte Wahrscheinlichkeit" werden eventuell komplett unbekannt sein.

Voraussetzungen

• Englischkenntnisse (B1): Paper / Dokumentation lesen
• Laptop zum Programmieren

Lernziele

Das wichtigste bei einem Kurs sind immer die Lernziele. Bei der Definition von Referatsthemen und beim Auswählen der Kursinhalte sollte stets geprüft werden, ob diese zu den Lernzielen passen.

Themenspezifisch

• Problembewusstsein für die Herausforderungen im Gebiet der natürlichen Sprachverarbeitung
• Akurates arbeiten mit Wahrscheinlichkeitsfunktionen und Statistik.
• Wissenschaftliches Arbeiten und evaluieren von Experimenten (Hypothese, Versuchsaufbau, Durchführung, Diskussion)
• Nützliche Toolkits zum effizienten Arbeiten auf dem Gebiet der Natürlichen Sprachverarbeitung.
• Stärkung der Programmierkenntnisse

Allgemein

• Teamarbeit (Kommunikation, Dokumentation, git,...)
• Arbeiten mit Wikis
• Präsentationstechniken (Es sollte wieder eine Posterpräsentation geben, bei der man hoffentlich aus den Fehlern von 2013 gelernt hat)
• Feedbackkultur
• Wissenschaftliches schreiben

Mathematik

Ohne Mathematik wird es in dem Kurs nicht funktionieren. Im Folgenden sind die Themen und Konzepte genannt, die vermutlich unverzichtbar sein werden.

Grundlagen

• Wahrscheinlichkeitsräume
• Wahrscheinlichkeitsfunktionen
• bedingte Wahrscheinlichkeiten
• Satz von Bayes
• Satz der totalen Wahrscheinlichkeit

Fortgeschrittenere Konzepte

• Entropie / Kreuzentropie
• Perplexität
• Transinformation - Mutual Information
• Kullback-Leibler-Divergenz

Expertenwissen

• Shannon paper
• Noisy channel model
• Markov Modelle / Markov-Annahme (Dieses Thema erscheint mir in Wirklichkeit viel komplexer und subtiler als es meistens gedacht ist.)

Grundlagen der Informatik

• Ubuntu / Linux: sicherer Umgang mit der Konsole
• Sicheres Beherrschen eines Editors z.B. Emacs oder aber eine Entwicklungsumgebung wie z.B. eclipse
• Sicherer Umgang mit einer Programmiersprache z.B. Java oder Python

Sprachmodelle

• Korrektes Zählen
• Maximum likelihood Verteilung
• Geskipte n-gram Verteilungen
• Fortsetzungshäufigkeit.
• Smoothing-Techniken (falls überhaupt)
• Klassenbasierte / POS-Modelle (?)

Algorithmen, Programmiertechniken und Datenstrukturen

• Beam search
• Caching
• Dynamische Programmierung
• MapReduce-artige Ansätze
• Hashmaps, FST, Trie, Listen, …

Anwendungen und Ausblick

Fast sämtliche Anwendungen ließen sich mit Machine Learning anreichern und auch implementieren.

Rechtschreibkorrektur

• Problemdefinition (Erkenntnis, dass Tippfehler die zu korrekten Worten führen schwierig zu erkennen sind.)
  • Levenshtein-Distanz
  • Auch interessant: How to Write a Spelling Corrector
• Implementierung

Autovervollständigung

• Evaluations settings: Precision Recall, MRR, Normalized Key Stroke Savings
• Effiziente Indexstrukturen (Tries und FST)

Handschrifterkennung

Ursprünglich ein Machine Learning Problem. Es lässt sich doch mit Hilfe von Sprachmodellen als Noisy channel Problem verstehen und passt daher thematisch gut in den Kurs.

Maschinelles Übersetzen

• Einführung in MOSES
• Kombination mit Machine Learning

Spracherkennung

• Einführung in CMU Sphinx
• Kombination mit Machine Learning

Entity Recognition

• Freebase-Konzepte in der Wikipedia erkennen?
• Part of speech tagging
• Lassen sich die Links in der Wikipedia automatisch generieren?

Question Answering

• Einführung in die Problemstellung
• Problembewusstsein schaffen.

Standard Software

• Python / Java?
• NLP toolkits: NLTK
• Corpora parsen
• Verwenden wir nur Standard-Toolkits oder implementieren wir bestimmte Sachen auch selbst?

Wissenschaftliche Methoden

• Dataset split
• Cross corpus Evaluation
• Statistische Methoden (AUC, ROC, Precision, Recall, …)
• 10-fache Kreuzvalidierung
• Reproduzierbarkeit / Dokumentation
• Experiment design

Zeitplan

Es gibt 17 Tage. Vor dem Mittagessen stehen ca. 3 Stunden zur Verfügung; Nachmittags nochmals ca. 2 Stunden.

Vorbereitung: Die Teilnehmer sollten versuchen die benötigte Software bereits vor der Akademie zu installieren. Dabei können wir per Email / Wiki Hilfestellung geben

• Tag 1:
  • Vormittags: Vorstellen (ca. 2h?); git; Programmiersprache
  • Nachmittags: Dynamische Programmierung+Levenshtein-Distanz
• Tag 2:
  • Vormittags: Akkuratheit der Korrektur durch Kreuzvalidierung feststellen(?)
  • Nachmittags: N-Gram Modell als zusätzliche Möglichkeit der Bewertung der besten Hypothese(?)
• Tag 3:
  • Vormittags: Programmieren eines Online-Spellcheckers für Englisch (da scheint es tatsächlich noch nichts gutes zu geben!)
  • Nachmittags: "
• Tag 4:
  • Vormittags: Programmieren eines Chatbots (see StackOverflow)
  • Nachmittags:
• Tag 5:
  • Vormittags: Grammatik-Prüfung mit Word-Embeddings
  • Nachmittags: Grammatik-Prüfung mit Word-Embeddings
• Tag 6:
  • Vormittags:
  • Nachmittags:
• Tag 7:
  • Vormittags:
  • Nachmittags:
• Tag 8:
  • Vormittags:
  • Nachmittags:
• Tag 9:
  • Vormittags:
  • Nachmittags:
• Tag 10:
  • Vormittags:
  • Nachmittags:
• Tag 11:
  • Vormittags:
  • Nachmittags:
• Tag 12:
  • Vormittags:
  • Nachmittags:
• Tag 13:
  • Vormittags:
  • Nachmittags:
• Tag 14:
  • Vormittags:
  • Nachmittags:
• Tag 15:
  • Vormittags:
  • Nachmittags:
• Tag 16:
  • Vormittags:
  • Nachmittags:
• Tag 17:
  • Vormittags:
  • Nachmittags:

Materialien

Folgende Materialien sollten von den Kursleitern in einem vernünftigem Format bereitgestellt werden:

• Wörterbücher
• N-Gramme

Quellen

• https://github.com/renepickhardt/phd-thesis
• https://kheafield.com/code/kenlm/
• NLTK Documentation
• Combining Scikit-Learn and NTLK

MOOCs:

• Natural Language Processing (Coursera, Stanford)
• Neural networks (Université de Sherbrooke): The NLP part is the last, chapter 10. I have not watched them so far, but the lecture about pre-training (ANNs) is very good.

Artikel

• Deep Learning, NLP, and Representations: Short section about word embeddings

Bücher

• Dan Jurafsky, James Martin: Speech and language processing
• Schuetze, Manning: Statistical foundations of NLP
• Koehn: Machine translation