Archiv der Kategorie: Computerlinguistik

Café Cartese

Während meiner Studienzeit folgte ich auf digitalen wie analogen Ordnern strikt einem genau definierten System von Kurzbezeichnungen für Lehrveranstaltungen. Sie setzten sich aus den Anfangsbuchstaben aller Wörter im offiziellen Titel der jeweiligen Lehrveranstaltung zusammen, mit Ausnahme von Präpositionen, Artikeln, Relativpronomen und Konjunktionen.1 Das hässlichste so entstandene Kürzel ist UNLPFLASLL (Using Natural Language Processing to Foster Language Awareness in Second Language Learning), das schönste CAFE (Computational Approaches to Functional Elements). Auch hübsch: CARTESE (Computational Approaches to Recognizing Textual Entailment and Semantic Equivalence).

  1. Das sind auch die Wörter, die ich in englischen Titeln nicht großschreibe, seit mir eine befreundete Anglistin diese Liste zu meiner großen Freude einmal lieferte. Ich nenne es die PARK-Regel. []

Wrong Independence Assumptions

When you build probabilistic models of something (say natural language grammars), you always fall prey, to some degree or other, to wrong independence assumptions. For example, a model might capture the fact that two events are each very probable to occur, but fail to capture the fact that they are quite improbable to occur together. Since it’s always nice to have examples from everday life or popular culture for scientific concepts, I’m referring the following dialogue from The Big Bang Theory, in which Sheldon quite conspicuously makes a wrong independence assumption:

HOWARD: Someone has to go up with the telescope as a payload specialist, and guess who that someone is.
SHELDON: Muhammad Li.
HOWARD: Who’s Muhammad Li?
SHELDON: Muhammad is the most common first name in the world, Li, the most common surname. As I didn’t know the answer, I thought that gave me a mathematical edge.

Plagiatsapologie ohne Sinn und Bedeutung

Selten las ich solchen Schwachsinn wie die „sprachphilosophische Spurensuche“ zu Plagiatsvorwürfen, die Rafael Wawer gestern in das Redaktionssystem von Zeit Online gerotzt hat:

[A]ngenommen, Google oder Stephan Wolfram [sic] brächten demnächst eine öffentliche Plagiatssuchmaschine heraus, die das heutige Internet als „text corpus“-Basis (Fachbegriff der Computerlinguistik) verwendet.

Man nehme amüsiert zur Kenntnis, dass er das wahrscheinlich den meisten seiner Leser unbekannte Wort Computerlinguistik verwendet und großspurig darauf hinweist, dass Textkorpus (aus irgendwelchen Gründen als englisches Wort geschrieben) ein Fachbegriff dieser Disziplin sei, ohne sich damit aufzuhalten, ihn zu erklären. Geschenkt. Weiter:

Diese Maschine könnte Abermillionen Bücher anhand eines Buches vergleichen wie das bereits „text merge“-tools (Textvergleiche) im kleinen Rahmen tun.

Kann diesen Noob bitte mal jemand LARTen? Weder ist ein Merge-Tool ein Vergleichs-Tool noch ist eins dieser beiden Werkzeuge allein zur Plagiatssuche geeignet. Und so viel kleiner ist der Rahmen gar nicht, gängige Plagiatsdetektorsoftware benutzt doch Google und damit das Internet als Textkorpus.

Jede Suchabfrage hätte als Ergebnis den prozentualen Anteil der Plagiate am Gesamttext. Ganz oben rangierte vermutlich Guttenberg, gefolgt von – vielleicht Journalisten, Schriftstellern, Herausgebern, Nobelpreisträgern? Es gäbe einen Aufschrei.

Was wäre daran vorschnell? Plagiate kommen nicht einfach durch buchstabengetreue Übereinstimmung zustande.

Dieser Satz hat es in sich. Ich werde darauf zurückkommen, wie er das meint.

In Rom galt nicht die unerlaubte Vervielfältigung als moralisch verwerflich, sondern die Bereicherung daran. Noch zu Zeiten Shakespeares galt das originalgetreue Plagiat als Zeichen der Verehrung.

Beim Plagiat im wissenschaftlichen Sinne geht es weder um den Aspekt der Vervielfältigung noch um den der Bereicherung noch um den der Originalgetreuheit, also dient diese Ausführung nur der Verwirrung.

Im Allgemeinen verstehen wir aber unter Plagiat, von lateinisch plagium, so viel wie „Raub der Seele“. Dieb ist, wer fremde Gedanken stiehlt, seins nennt oder verkauft.

Das Stehlen fremder Gedanken ist also schlimm, das Stehlen fremder Wortlaute nicht so sehr? Aber stiehlt, wer fremde Wortlaute stiehlt, damit nicht automatisch auch fremde Gedanken? ACH, HÄTTE ICH DOCH NICHT GEFRAGT! Wawer holt Luft und doziert:

Nun beziehen sich die meisten Plagiatsvorwürfe auf Platon (428-328 v. Chr.) und erben damit seine Fehler. Platon hat die Seele mit Wachs verglichen. Eindrücke der Wirklichkeit würden zu Abdrücken auf der Seele. Erkennen wir etwas, das uns bekannt scheint, suchen wir im Schrank der Seele nach genau diesem Eindruck. Wir legen Eindruck und Abdruck übereinander. Passt etwas, rufen wir: Ah! Viele aktuelle technische Erkenntnistheorien gehen nach diesem Muster vor, ebenso neuronale Netzwerke.

Strukturen werden miteinander verglichen, indem man nach identischen Unterstrukturen sucht, ja. Man kann nicht nur zwischen identisch und nicht identisch unterscheiden, sondern in einem gewissen Maße auch ähnliche Eindrücke zueinander in Beziehung setzen. So konkret hat Platon sich das vielleicht noch nicht vorgestellt, aber er war nicht so sehr auf dem Holzweg, wie Wawer es klingen lässt:

Aber dann kam Gottlob Frege (1848-1925) und erinnerte an den „Morgenstern“. Wie sieht der Abdruck eines Morgensterns schon aus, wenn wir darunter den Planeten Venus, eine Waffe, selbst Jesus Christus und vieles weitere verstehen? Hiermit war die moderne Formalisierung von Sinn, Bedeutung und Referenz geboren – und damit die moderne Logik, die Computerwelt, das Internet. Mit Ludwig Wittgenstein (1889-1951), Bertrand Russell (1872-1970) und Jan Łukasiewicz (1878-1956) wurde sie erweitert und formalisiert. Łukasiewicz haben die Unix-Anhänger zum Beispiel zu verdanken, dass sie anstatt „8 + 5“ eher „+ 8 5“ schreiben.

Uuuffff!!! Was war das denn für ein Stunt? Einmal von Frege über das Internet zu polnischer Notation wie mit dem Dirtbike durch einen Supermarkt, viele Kenntnisse, null Zusammenhang und kaum Relevanz.

Kennte Wawer Frege, wüsste er, dass ihm das Wort Morgenstern als Beispiel für den Unterschied zwischen Sinn und Bedeutung diente – Morgenstern und Abendstern haben nämlich laut Frege verschiedene Sinne, aber dieselbe Bedeutung (den Planeten Venus). Darin steckt unter anderem das Phänomen der Synonymie, verschiedener Wörter mit gleicher Bedeutung, und das hätte Wawer brauchen können, um richtig darauf hinzuweisen, dass man ungekennzeichnete fremde Gedanken auch so umformulieren kann, dass die oben erwähnten, Wörter vergleichenden Suchmaschinen das Plagiat nicht entdecken, wie er es an anderer Stelle am Beispiel einer möglichen Umformulierung von Einsteins Relativitätstheorie auch kurz tut. Hier hebt er stattdessen auf das Phänomen der Homonymie ab, dass nämlich ein Wort – wie Morgenstern – verschiedene Bedeutungen haben kann: Venus, Waffe, Jesus usw.

Was will er uns bezüglich der Plagiatsvorwürfe damit sagen? Dass die folgende Passage, von Silvana Koch-Mehrin laut VroniPlag ungekennzeichnet und wörtlich aus Lothar Galls Buch Europa auf dem Weg in die Moderne 1850-1890 in ihre Dissertation übernommen, vielleicht gar kein Plagiat darstellt, weil sie dank der Homonymie der darin vorkommenden Wörter ja etwas ganz anderes bedeuten könnte?

„Konkret hieß das, daß sich nach England und Frankreich nun auch die meisten Staaten Mittel- und Südeuropas entschlossen, alle noch bestehenden Hindernisse für die Entfaltung des Handels und der gewerblichen Wirtschaft auf rechtlichem, finanz- und handelspolitischem Gebiet mehr und mehr abzubauen und sich künftig auch in ordnungspolitischer Hinsicht ganz auf den Markt und die Initiative des einzelnen zu verlassen.“

Natürlich nicht, eine solches Argument wäre selbst Wawer zu albern. Stattdessen schließt er aus seinem sprachphilosophischen Mäander pauschal, „dass man mit einfachen Abdruckvergleichen nicht weiterkommt“, weil menschliche Sprache „zu variationsreich“ für eine Entscheidung durch „crowd-Tribunale“ sei.

Er impliziert damit, die Bemühungen von GuttenPlag, VroniPlag und Co. hätten keine Gültigkeit. Natürlich können sie nicht alle Plagiate aufspüren. Aber wenn sie denn eine schlichte wörtliche Übernahme wie oben aufspüren, ist das dann nicht ein über jeden Zweifel erhabener Nachweis eines Plagiats, um meine schnell bereute Frage von oben zu wiederholen?

Wawer sagt nein. Er behauptet allen Ernstes, die oben zitierte Passage bedeute nichts weiter als „Mittel- und Südeuropa orientieren sich an der Marktwirtschaft“ und dass das eine Trivialität sei. Wortlaute ungekennzeichnet zu übernehmen, die Gemeinplätze formulieren, ist für Wawer noch kein Plagiat (und diese bornierte Privatmeinung erhebt er Ursula-März-mäßig zur „Regel“):

Die Regel lautet: Wer neuartige Bedeutungen und Sinnzusammenhänge stiehlt, der ist ein Dieb, also wer zum Beispiel dem nächsten Einstein beim Reden im Schlaf zuhört. Denn die Wissenschaft lebt vom Neuen. (…) Wer Allgemeines wörtlich kopiert, ist doof, aber kein Verbrecher. Dass Regen vom Himmel fällt, braucht nicht bewiesen zu werden.

Damit verkennt er total, was den Guttenbergs und Koch-Mehrins dieser Welt eigentlich vorzuwerfen ist. Das Stehlen von neuen Ideen wäre an sich ja gerade kein Problem, denn insofern die Wissenschaft vom Neuen lebt, ist es wichtig, dass, aber nicht, von wem es unters Volk gebracht wird. Plagiate sind hingegen deswegen schlimm, weil sie erstens das Urheberrecht der Autorinnen verletzen, zweitens (wichtiger) das wissenschaftliche Arbeiten der gesamten Disziplin sabotieren, indem Quellen verschwiegen werden und dadurch das Nachvollziehen von Entwicklungen und Zusammenhängen erschwert wird, drittens und wichtigstens jedoch zum Erwerb eines Titels eine Leistung vorgetäuscht wird, die nicht erbracht wurde, nämlich eine ganze Dissertation nach den Regeln des wissenschaftlichen Arbeitens zu schreiben. Dazu gehört nicht zuletzt, alles genau zu durchdenken und mit eigenen Worten zu formulieren bzw. korrekt als Zitat zu kennzeichnen, um eine klare, lesbare und nachvollziehbare Darstellung zu erhalten. Neue Ideen hat man oder hat man nicht, das ist keine Frage des Anstandes und nur begrenzt eine des Fleißes. Die Knochenarbeit, an der sich das wissenschaftliche Ethos meiner Ansicht nach erweist, steckt im korrekten Aufschreiben und in der Literaturrecherche – hierzu gehört auch, nach Kräften zu versuchen, herauszufinden, ob eine Idee, die man selbst hat, nicht jemand anders schon vorher veröffentlicht hat.

Ich werde den Verdacht nicht los, dass Wawer das deshalb nicht weiß, weil er in seinem eigenen Philosophiestudium nie so gearbeitet, sondern sich immer nur Wissensbrocken angelesen und zu irgendwelchem zusammenhanglosen Rhabarber verleimt hat. Nur so eine Vermutung.

Zwischen Kontextfreiheit und Kontextsensitivität, Teil 3: Nicht kontextfreie Grammatiken für Fragmente natürlicher Sprachen

Kontextfreie Grammatiken sind sehr beliebt für die Beschreibung natürlicher Sprachen. Zumindest in der Theorie und solange es nicht zu kompliziert wird, eignen sie sich gut dafür, Syntax in den Griff zu kriegen. Warum interessieren sich manche Computerlinguistien dann so für nicht kontextfreie Grammatikformalismen wie SRCG, das ich in Teil 1 vorgestellt und in Teil 2 in die Chomsky-Hierarchie eingeordnet habe?

Schauen wir uns ein Fragment der deutschen Sprache an, das aus Nebensätzen wie diesen besteht:

(1.1) dass wir das Haus anstreichen
(1.2) dass wir dem Hans das Haus anstreichen helfen
(1.3) dass wir die Kinder dem Hans das Haus anstreichen helfen lassen

Es wird z.B. durch die folgende kleine kontextfreie Grammatik mit Startsymbol S‘ beschrieben. Von Finitheit, Numerus und Genus sehen wir mal großzügig ab und beachten nur Kasus (n für Nominativ, d für Dativ, a für Akkusativ):

(2.1) S‘ → C S
(2.2) S → NPn VP
(2.3) VP → NPa Va
(2.4) VP → NPd VP Vdv
(2.5) VP → NPa VP Vav
(2.6) NPn → PRPn
(2.7) NPa → Da N
(2.8) NPd → Dd N
(2.9) C → dass
(2.10) PRPn → wir
(2.11) Da → das
(2.12) Dd → dem
(2.13) N → Haus
(2.14) N → Hans
(2.15) N → Kinder
(2.16) Va → anstreichen
(2.17) Vdv → helfen
(2.18) Vav → lassen

Die Grammatik beschreibt Sätze wie in (1.1-3) nicht nur, sie liefert auch linguistisch plausible Strukturen dafür. Erstens trägt sie der Beobachtung Rechnung, dass Sprache wie Lego ist: Sätze sind aus Teilen (Phrasen oder Konstituenten) zusammengesetzt, die ihrerseits wiederum aus Phrasen bestehen, bis man bei den kleinsten Bausteinen anlangt, den Wörtern. Phrasen gleicher Kategorie sind untereinander austauschbar. Z.B. sind sowohl das Haus anstreichen als auch dem Hans das Haus anstreichen helfen Verbalphrasen (VP) und können daher beide auf dass wir folgen und einen Satz bilden (1.1, 1.2), auch wenn sie in sich unterschiedlich aufgebaut sind, einmal nach Regel (2.3) und einmal nach Regel (2.4). Umgekehrt kann dieselbe Konstituente, z.B. das Haus anstreichen in verschiedenartigen Kontexten auftauchen (1.1, 1.2., 1.3), weil sowohl (2.2) als auch (2.4) als auch (2.5) das VP-Symbol auf der rechten Seite haben.

Zweitens modellieren die Regeln die lokalen Abhängigkeiten zwischen Verben und ihren Argumenten: helfen ist zum Beispiel ein Verb, das eine Nominalphrase im Dativ als Argument nehmen kann (wem man hilft) sowie eine Verbalphrase (wobei man hilft). Ich habe das in der Grammatik mal so kodiert, dass helfen die Kategorie Vdv hat (Verb mit Dativ-Nominalphrase und Verbalphrase). Analog ist lassen Vav (Akkusativ-Nominalphrase, wen oder was man lässt; Verbalphrase, was man ihn, sie oder es tun lässt) und streichen nur Va (Akkusativ-Nominalphrase, was man streicht). Regeln 2.3-5 sorgen dafür, dass jede Verbalphrase mit einem Verb (dem Kopf der Phrase) und dazu passenden Argumenten aufgebaut wird.

Ein Ableitungsbaum veranschaulicht die syntaktische Struktur eines Satzes, hier die von (1.3):

Kontextfreier Ableitungsbaum für den Satz „dass wir die Kinder dem Hans das Haus anstreichen helfen lassen“

Übersetzen wir nun unsere drei Beispielsätze ins Zürichdeutsche nach Shieber (1985):

(3.1) das mer es huus aastriche
(3.3) das mer em Hans es huus hälfe aastriche
(3.3) das mer d’chind em Hans es huus lönd hälfe aastriche

Es fällt auf, dass die Verben am Ende in der umgekehrten Reihenfolge stehen. Wenn wir weiterhin davon ausgehen, dass z.B. in (3.3) d’chind direkt mit lönd zusammenhängt, em Hans direkt mit hälfe und es huus direkt mit aastriche, was zweifellos sinnvoll ist, dann stellen wir fest, dass unsere Verbalphrasen nicht mehr verschachtelt sind wie im Hochdeutschen, sondern sich „überkreuzen“. Ein Baumdiagramm zu (3.3) sieht dann so aus:

Ableitungsbaum mit kreuzenden Kanten zu dem Satz „das mer d’chind em Hans es huus lönd hälfe aastriche“

Man spricht auch von unterbrochenen Konstituenten, weil zwischen den Wörtern, die zu den niedrigeren beiden VPs gehören, Wörter auftauchen, die nicht dazu gehören.

Es ist einigermaßen offensichtlich, dass das keine kontextfreie Ableitung mehr ist. Eine 2-SRCG dazu indes gibt es:

(4.1) S’(XY) → C(X) S(Y)
(4.2) S(XYZ) → NPn(X) VP(Y,Z)
(4.3) VP(XY,ZU) → NPa(X) VP(Y,U) Vav(Z)
(4.4) VP(XY,ZU) → NPd(X) VP(Y,U) Vdv(Z)
(4.5) VP(X,Y) → NPa(X) Va(Y)
(4.6) NPn(X) → PRPn(X)
(4.7) NPd(XY) → Dd(X) N(Y)
(4.8) NPa(XY) → Da(X) N(Y)
(4.9) C(das) → ε
(4.11) PRPn(mer) → ε
(4.12) Dn(d’) → ε
(4.13) Dd(em) → ε
(4.13) N(huus) → ε
(4.14) N(Hans) → ε
(4.15) N(chind) → ε
(4.16) Va(aastriche) → ε
(4.17) Vdv(hälfe) → ε
(4.18) Vav(lönd) → ε

Die Idee ist, VPs zwei Argumente zu geben, das erste für die Argumente der Verben, das zweite für die Verben selbst. Hängt von einer Verbalphrase VP1 eine zweite Verbalphrase VP2 ab, bilden die Argumente von VP2 die Basis, VP1 hängt ihr NP-Argument und ihr Verb jeweils vorne an, wie in Regeln (4.3-4) zu sehen.

Eine VP in dieser Grammatik ist auch nicht nur einfach eine Aneinanderreihung von Nominalphrasen, gefolgt von einer gleich langen Aneinanderreihung von Verben – das würde man zur Not auch noch mit einer kontextfreien Grammatik hinkriegen, wenn auch mit einer anderen Struktur (vgl. die erste Beispielgrammatik in Teil 1). Nein, die Regeln „checken“ ja, ob eine Nominalphrase zum Verb passt (z.B. Dativ für helfen, aber Akkusativ für lassen). Falsche Sätze wie dieser sind nicht ableitbar (lönd verlangt Akkusativ, nicht Dativ):

(5.1) *das mer em chind em Hans es huus lönd hälfe aastriche

Das ist der Kern des Arguments von Shieber (1985) dafür, dass natürliche Sprachen im Allgemeinen nicht kontextfrei sind.

In Teil 4: Was man dagegen einwenden kann und warum es so oder so nützlich sein kann, unterbrochene Konstituenten (also ein wenig Kontextfreiheit) bei der Analyse natürlicher Sprachen zuzulassen.

Sehr konkrete Pläne habe ich für Teil 4 noch nicht. Erst mal bin ich gespannt, ob meine werten Leser Fragen und Kommentare hierzu haben und wenn ja, welche. Daraus ergibt sich dann vielleicht eine klarere Vision für Teil 4.

Literatur

Marcus Kracht: The Mathematics of Language. Gruyter, 2003.

Stuart M. Shieber: Evidence against the Context-freeness of Natural Language. In: Linguistics and Philosophy 8, 1985.

s.a. Literatur zu Teil 1 und Teil 2.

Zwischen Kontextfreiheit und Kontextsensitivität, Teil 2: Eine erweiterte Chomsky-Hierarchie

Ausgelöst durch Prüfungsvorbereitung und Schreiben an der Masterarbeit habe ich mich in letzter Zeit viel mit Typen formaler Grammatiken beschäftigt, die alle kontextfreien Sprachen beschreiben können und darüber hinaus einige, aber nicht alle kontextsensitiven Sprachen. Einen solchen Grammatikformalismus, nämlich Simple Range Concatenation Grammars (SRCG), habe ich in Teil 1 dieser Serie vorgestellt. In Teil 3 werde ich Anwendungen auf natürliche Sprache skizzieren.

Heute ist Teil 2 dran und damit die Vogelperspektive: Wo stehen wir auf der Chomsky-Hierarchie der formalen Sprachen? Ich kopiere dazu einfach Herrn Raus Übersicht über die Chomksy-Hierarchie, füge aber zwei weitere Stufen, also zwei weitere Klassen von Sprachen ein.

  • Chomsky 0: Alle Sprachen, die sich überhaupt durch eine Grammatik beschreiben lassen.
  • Chomsky 1: Eine Teilmenge davon, nämlich die Sprachen, die sich durch eine kontextsensitive Grammatik beschreiben lassen.
  • PTIME aka P: Die Sprachen, bei denen das Wortproblem in Polynomialzeit entscheidbar ist. Range Concatenation Grammars (RCG) können genau diese Sprachen beschreiben. PTIME ist eine Teilmenge von Chomsky 0; ist es auch eine Teilmenge von Chomsky 1? Ich weiß es nicht, vielleicht weiß es auch niemand, aus dieser Übersicht geht es jedenfalls nicht hervor. Für Aufklärung bin ich dankbar.
  • Eine Teilmenge sowohl von Chomksy 1 als auch von PTIME sind die Sprachen, die sich durch Simple Range Concatenation Grammars (SRCG) beschreiben lassen. So weit ich weiß, hat diese Klasse von Sprachen keinen einschlägigen Namen. SRCG ist eine eingeschränkte Variante von RCG, aber immer noch deutlich mächtiger als kontextfreie Grammatiken (CFG). Es gehört zu den so genannten „schwach kontextsensitiven“ (mildly context-sensitive) Grammatikformalismen, die vor allem im Zusammenhang mit natürlicher Sprache interessant sind – wo kontextfreie Grammatiken für eine adäquate Beschreibung nicht mehr ausreichen, man aber wegen Effizienz und Theoriedesign auch nicht zu weit darüber hinausgehen will. Dieselbe Klasse von Sprachen lässt sich durch die mit SRCG auch sonst so gut wie identischen Formalismen Linear Context-free Rewriting Systems (LCFRS) und Multiple Context-free Grammars (MCFG) beschreiben.
  • Chomsky 2: Eine Teilmenge davon, nämlich die Sprachen, die sich durch eine kontextfreie Grammatik beschreiben lassen.
  • Chomsky 3: Eine Teilmenge davon, nämlich die Sprachen, die sich durch eine reguläre Grammatik beschreiben lassen.

Die originale vierstufige Chomksy-Hierarchie bietet ein schönes Zwiebelschalenmodell, bei dem jede Sprachenmenge die nächste strikt einschließt:

A graphical representation of the sets of languages included in the Chomsky hierarchy.Diese Schönheit habe ich durch mein Unwissen, ob PTIME eine Teilmenge von Chomsky 1 ist, zerstört. Bedenkt man aber, dass Chomsky 1, also die Klasse der kontextsensitiven Sprachen, meines Wissens weder theoretisch noch praktisch besonders interessante Eigenschaften hat, kann man sie rausschmeißen und aus der obigen Auflistung durchaus wieder eine schöne Zwiebel basteln:

A graphical representation of five sets of languages: recursively enumerable, PTIME, SRCG, context-free and regularDoch Vorsicht: In einem Vortrag habe ich einmal ein entsprechendes Diagramm für die verschiedenen schwach kontextsensitiven Grammatikformalismen gesehen, die es heute so gibt. Es sah ungefähr so aus:

Einander wirr überschneidende Ellipsen

In Teil 3: Warum man arguably schwach kontextsensitive Grammatikformalismen braucht, um natürliche Sprache zu beschreiben.

Nachbemerkung 1: mildly context-sensitive klingt schwammig, ist aber relativ präzise definiert. Der Begriff bezieht sich im Gegensatz z.B. zu context-sensitive und context-free nicht auf Sprachen, sondern auf Mengen von Sprachen. Eine Menge von Sprachen ist schwach kontextsensitiv genau dann, wenn sie einerseits alle kontextfreien Sprachen enthält und überdies kreuzende Abhängigkeiten beschreiben kann (siehe dazu Teil 3), andererseits aber nur Sprachen enthält, die in polynomieller Zeit parsbar sind (also eine Teilmenge von PTIME ist) und überdies konstantes Wachstum aufweisen. Für Details siehe Joshi (1985) oder Kallmeyer (2010). Trotz dieser präzisen Definition gibt es noch keinen Grammatikformalismus, von dem man wüsste, dass er die größtmögliche schwach kontextsensitive Menge von Sprachen beschreibt. Obwohl SRCG nach heutigem Kenntnisstand der mächtigste schwach kontextsensitive Formalismus ist, kann es also gut sein, dass es eine schwach kontextsensitive Menge von Sprachen gibt, die Sprachen enthält, die SRCG nicht beschreiben kann.

Nachbemerkung 2: Joshi (1985) hat mildly context-sensitive als terminus technicus eingeführt und, so bilde ich mir ein, extra nicht weakly genommen, weil dieses Wort im Zusammenhang mit formalen Grammatiken schon eine ganz andere Bedeutung hat, nämlich bei schwacher Äquivalenz. Deswegen finde ich die deutsche Übersetzung schwach kontextsensitiv etwas unglücklich. Hätte man nicht gelinde kontextsensitiv nehmen können?

Nachbemerkung 3: Wo wir schon bei Terminologiekritik sind. Das Begriffspaar kontextfrei und kontextsensitiv hat mich schon immer geärgert. Das klingt so komplementär. Tatsächlich ist aber jede kontextfreie Grammatik auch eine kontextsensitive Grammatik, siehe Zwiebel. Diese begriffliche Verwirrung ist ein Grund mehr, sich mit der Klasse der kontextsensitiven Sprachen überhaupt nicht mehr zu beschäftigen. *g*

Literatur

Aravind K. Joshi: Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions? In: D. Dowty, L. Karttunen und A. Zwicky (Hrsg.), Natural Language Parsing, Cambridge University Press, 1985.

s.a. Literatur zu Teil 1

Zwischen Kontextfreiheit und Kontextsensitivität, Teil 1: Crashkurs Simple Range Concatenation Grammars (SRCG)

In Herrn Raus Blog gibt es eine schöne mehrteilige Einführung in formale Sprachen, formale Grammatiken und die Chomksy-Hierarchie. Unter anderem werden dort reguläre Grammatiken, kontextfreie Grammatiken und kontextsensitive Grammatiken vorgestellt. Ich will heute einen weniger bekannten Grammatikformalismus vorstellen: Simple Range Concatenation Grammars (SRCG) (zu deutsch etwa: einfache Intervallverkettungsgrammatiken).

SRCGs können alle kontextfreien Sprachen beschreiben und darüber hinaus einige, aber nicht alle kontextsensitiven Sprachen. Genaueres dazu sage ich in Teil 2 dieser Serie, bevor ich in Teil 3 andeute, wozu das speziell bei natürlichen Sprachen (also so etwas wie Englisch, Deutsch, Niederländisch oder Zürichdeutsch) und damit für die Computerlinguistik von Nutzen sein kann.

Fangen wir mit einer guten alten kontextfreien Grammatik an. Hier sind die Regeln einer kontextfreien Grammatik, die die Sprache {anbn|n≥0} erzeugt, also die Sprache, die aus den Wörtern ε (das leere Wort), ab, aabb, aaabbb usw. besteht.

(1.1) S → aSb
(1.2) S → ε

Wenn wir diese Grammatik als SRCG schreiben, sehen die Regeln so aus:

(2.1) S(aXb) → S(X)
(2.2) S(ε) → ε

Vergleichen wir Regeln (1.1) und (2.1): Beide Regeln besagen, dass man aus dem Symbol S alle Wörter ableiten kann, die mit a losgehen, in der Mitte aus etwas bestehen, das man wiederum aus S ableiten kann, und mit b enden. Die Beschreibung „dessen, was man ableiten kann“, steht bei SRCG nicht auf der rechten Seite des Pfeils, sondern in Klammern neben dem Symbol der linken Seite. Es wird die Variable X verwendet, die auf der rechten Seite in dem Ausdruck S(X) wieder auftaucht: Der sagt, dass X etwas sein muss, das man aus S ableiten kann.

Regel (2.2) besagt wie Regel (1.2), dass man aus S den leeren String ableiten kann, und zwar bedingungslos – es tauchen keine weiteren Symbole auf, deswegen ist auch die rechte Seite leer (geschrieben wie der leere String als ε).

Eine andere SRCG für dieselbe Sprache wäre die hier:

(3.1) S(XY) → A(X, Y)
(3.2) A(aX, bY) → A(X, Y)
(3.3) A(ε, ε) → ε

Hier taucht ein neues Nichtterminal auf, A. Was hinter A in Klammern steht, besteht aus zwei Teilen, man sagt: A ist zweistellig oder: A hat zwei Argumente. Eins für den a-Teil der Wörter und eins für den b-Teil.

Damit sind wir beim wesentlichen Unterschied zwischen SRCG und CFG: In CFGs kann man aus einem Nichtterminal einen Teilstring des Wortes ableiten, in SRCGs auch mehrere Teilstrings, technisch ausgedrückt: Tupel von Teilstrings.

Die Grammatik im Beispiel funktioniert so: Regel (3.3) sagt, dass aus A das Tupel ⟨ε, ε⟩ ableitbar ist, also zweimal der leere String. Regel (3.2) sagt: Wenn aus A das Tupel ⟨X, Y⟩ ableitbar ist (rechte Seite), dann ist aus A auch das Tupel ⟨aX, bY⟩ ableitbar (linke Seite). Generativ, prozedural und salopp ausgedrückt klatscht diese Regel vorne an das erste Argument von A ein a und an das zweite ein b. Diesen Prozess kann man beliebig oft wiederholen, bis man so viele a’s und b’s hat, wie man will – aber immer für beide Argumente gleichzeitig, sodass die Anzahl der a’s und b’s gleich bleibt. Schließlich kommt Regel (3.1) zum Zuge, die die beiden Argumente von A in das einzige Argument von S konkateniert (verkettet).

Man kann diesen Prozess auch in der umgekehrten Reihenfolge schreiben, als Ableitung. Eine Ableitung beginnt mit dem Startsymbol und dem Wort, das man ableiten will, und gelangt über die Anwendung von Regeln zu ε. Hier eine beispielhafte Ableitung für das Wort aabb:

S(aabb)  ⇒(3.1) A(aa, bb)  ⇒(3.2) A(a, b)  ⇒(3.2) A(ε, ε)  ⇒(3.3) ε

Weil jede Ableitung mit genau einem String beginnt (eben dem Wort, das man ableiten will), muss das Startsymbol immer einstellig sein. Die Stelligkeit ist für jedes Nichtterminal festgelegt, d.h. innerhalb einer Grammatik kann A z.B. nicht einmal mit zwei und einmal mit drei Argumenten auftauchen.

Während sich bei jeder Anwendung einer CFG-Regel an einer Stelle im abzuleitenden Wort etwas ändert – ein Nichtterminal wird durch etwas ersetzt – kann sich bei der Anwendung einer SRCG-Regel an mehreren Stellen etwas ändern. So ändert sich bei jeder Anwendung unserer Regel (3.2) sowohl vorne etwas (ein a wird hinzugefügt) als auch in der Mitte (ein b wird hinzugefügt). Leicht lässt sich das auf drei Stellen ausdehnen, sodass die Grammatik die Sprache {anbncn|n≥1} beschreibt, für die es schon keine CFG mehr gibt. Man gibt A einfach ein drittes Argument:

(4.1) S(XYZ) → A(X, Y, Z)
(4.2) A(aX, bY, cZ) → A(X, Y, Z)
(4.3) A(ε, ε, ε) → ε

Das ist jetzt eine so genannte 3-SRCG, d.h. eine SRCG, wo die Nichtterminale maximal 3 Argumente haben. Die Zeitkomplexität des Wortproblems (algorithmisch zu bestimmen, ob ein gegebenes Wort zu der von der Grammatik erzeugten Sprache gehört) nimmt für k-SRCGs mit steigendem k exponenziell zu (übrigens auch mit der maximalen Länge der rechten Regelseite, die bisher in allen Beispielen 0 oder 1 war). CFGs entsprechen 1-SRCGs, wie ganz oben illustriert, wo wir eine CFG direkt in eine 1-SRCG übersetzt haben.

Für die Form der Regeln einer SRCG gibt es zwei wichtige Einschränkungen: Auf der rechten Seite muss jedes Argument nicht mehr und nicht weniger als eine Variable enthalten (während auf der linken Seite Folgen von Terminalen, Variablen oder auch ganz leere Argumente erlaubt sind). Außerdem muss jede Variable, die in einer Regel vorkommt, auf der linken und auf der rechten Seite der Regel je genau einmal vorkommen. Ohne diese Einschränkungen hätte man die noch einmal deutlich mächtigeren und komplexeren Range Concatenation Grammars (RCG) (Boullier 1998).

In Teil 2 schauen wir uns etwas genauer an, welche Klassen von Sprachen SRCG und RCG beschreiben und wo man diese auf der Chomksy-Hierarchie einordnen kann.

Nachbemerkung 1: Aus pädagogischen Gründen habe ich immer „Regel“ und „Nichtterminal“ geschrieben, im RCG-Jargon sagt man eigentlich „Klausel“ und „Prädikat“ dazu. Wer schon einmal in Prolog programmiert hat, bei der klingt jetzt vielleicht ein Glöcklein. Ja, eine (S)RCG lässt sich mit trivialen Änderungen in der Syntax als Logikprogramm lesen. Leider ist das dann noch lange kein praxistauglicher Parser, wie ja auch Prologs im Kern kontextfreie Definite Clause Grammars (DCG) gewissen Beschränkungen unterworfen sind. Parsing-Algorithmen für RCG, SRCG und weitere Formalismen gibt’s in Kallmeyer (2010).

Nachbemerkung 2: Das war jetzt gewissermaßen auch eine Einführung in Linear Context-free Rewriting Systems (LCFRS) (Vijay-Shanker et al. 1987, Weir 1988) und Multiple Context-free Grammars (MCFG) (Seki et al. 1991). Diese beiden Grammatiktypen beschreiben dieselbe Klasse von Sprachen wie SRCG und unterscheiden sich auch sonst nur minimal davon.

Literatur

Pierre Boullier: A Generalization of Mildly Context-Sensitive Formalisms. In: Proceedings of the Fourth International Workshop on Tree-Adjoining Grammars and Related Formalisms (TAG+4), University of Pennsylvania, 1998.

Laura Kallmeyer: Parsing beyond Context-Free Grammars. Springer, 2010.

Hiroyuki Seki, Ryuichi Nakanishi, Yuichi Kaji, Sachiko Ando und Tadao Kasami: On Multiple Context-Free Grammars. In: Theoretical Computer Science 88(2), 1991.

K. Vijay-Shanker, David J. Weir und Aravind K. Joshi: Characterizing Structural Descriptions Produced by Various Grammar Formalisms. In: Proceedings of ACL, Stanford, 1987.

David J. Weir: Characterizing Mildly Context-Sensitive Grammar Formalisms. Dissertation, University of Pennsylvania, 1988.

diff für Juristen

$ diff -j ThüFischG-20060628.txt ThüFischG-20080630.txt | head -n 7
1. § 4 wird wie folgt geändert:
a) In Absatz 1 werden das Wort ", Wasserbuch," durch das Wort "oder" ersetzt und
die Worte "oder Fischereikataster" gestrichen.
b) Absatz 2 Satz 3 wird aufgehoben.
2. In § 5 Abs. 2 werden das Komma nach dem Wort "Grundbuch" und die Worte
"Wasserbuch, Fischereikataster" gestrichen.

Ob es eine solche Software bereits gibt?

(Quelle, Hintergrund)