Parsing von natürlichen Sprachen

Parsing

Der Begriff Parsing beschreibt das Zerlegen eines Objektes in seine Einzelteile. Sogenannte Parser sind aus der Informatik nicht wegzudenken – sie kommen in jedem Compiler vor und für viele Programmiersprachen gibt es Parser-Generatoren, die Programmcode zur Zerlegung von Nutzereingaben erzeugen. Als theoretischer Hintergrund dieser Parser dienen oft reguläre oder kontextfreie Sprachen, welche in der Disziplin der theoretischen Informatik untersucht wurden und werden.

Ihren Ursprung haben diese Klassen von formalen Sprachen in der Linguistik. Sie wurden von Noam Chomsky mit dem Ziel eingeführt, einen geeigneten Formalismus für die Beschreibung von natürlichen Sprachen zu finden, also solchen Sprachen die von Menschen gesprochen und geschrieben werden. Auch wenn eine solche Formalisierung nach wie vor unerreicht ist, haben Parser bis heute eine Bedeutung im Bereich der Computerlinguistik und der maschinellen Verarbeitung von natürlichen Sprachen. Das Ziel ist die automatisierte Verarbeitung von natürlichen Sprachen mit Hilfe des Computers. Mögliche Anwendungen sind beispielsweise die Übersetzung und das Zusammenfassen von Texten oder Chatbots, welche zu verschiedensten Themen mit Menschen kommunizieren können. Parser unterstützen diese Anwendungen, indem sie eine syntaktische Analyse (also eine Analyse der grammatikalischen Struktur) der natürlichsprachigen Eingabe bereitstellen.

Mild kontext-sensitive Sprachen

Da sich natürliche Sprachen recht bald als nicht regulär bzw. kontextfrei herausgestellt haben, die Klasse der mächtigeren kontextsensitiven Sprachen aber eine zu hohe Komplexität für praktische Anwendungen hat, wurden sogenannte mild kontext-sensitive Sprachen untersucht. Ein Vertreter dieser Klasse sind die Linear Context-free Rewriting Systems (LCFRS) bzw. die syntaktisch ähnlichen und semantisch äquivalenten Multiple Context-free Grammars (MCFG). Hier können insbesondere diskontinuierliche Phrasen modeliert werden, also Satzteile, welche eine logische Einheit bilden aber keine Menge von aufeinanderfolgenden Wörtern im Satz. Dieses Phänomen tritt unter anderem in Sprachen mit freier Wortnung wie Deutsch, Schweitzer-Deutsch und Niederländisch aber auch im Englischen auf.

Theoretische Beiträge

Ein Teil unserer Arbeitsgruppe widmet sich der Erforschung von solchen mild-kontextsensitiven Grammatiken. Dies umfasst einerseits theoretische Arbeiten, wie eine Chomsky-Schützenberger-Charakterisierung von gewichteten MCFG und eine Automaten-Charakterisierung. Da der Grad an Diskontinuität, welchen eine MCFG darstellen kann, Einfluss auf ihre Verarbeitungskomplexität hat, untersuchen wir Approximationstechniken. Diese sollen weniger ausdrucksstarke Grammatiken mit einer geringeren Verarbeitungskomplexität liefern, aber die Sprache der gegebenen Grammatik möglichst beibehalten. In diesem Zuge haben wir auch sogenannte Hybridgrammatiken eingeführt, welche z.B. LCFRS mit einer Baum-generierenden Grammatik synchronisieren. Hybridgrammatiken erlauben auf geschickte Weise einen Teil der Komplexität in die Baum-generierende Grammatik zu verlagern, wodurch die Verarbeitungskomplexität für praktische Anwendungen reduziert wird. Eine weiterer Beitrag in diesem Bereich ist die Entwicklung einer umkehrbaren Lexikalisierungsmethode für MCFG.

Praktische Beiträge

Basierend auf unserer theoretischen Forschung implementieren wir Parsingalgorithmen und evaluieren sie auf linguistischen Datensätzen, sogenannten Korpora. Dabei sind u.a. die Anwendungen rustomata und panda-parser entstanden. Weiterhin untersuchen wir Grammatik-basierte Parser welche von neuronalen Modellen gesteuert werden.

Vortragsfolien zum Thema

• Folien präsentiert von Heiko Vogler auf der CAI 2017

Kontakt

• Prof. Dr.-Ing. habil. Dr. h.c./Univ. Szeged
  Heiko Vogler
  Tel.: +49 (0) 351 463-38232