Post on 19-Oct-2020
transcript
Textmining – Wissensrohstoff Text
Wintersemester 2008/09Teil 4
Uwe QuasthoffUniversität Leipzig
Institut für Informatikquasthoff@informatik.uni-leipzig.de
U. Quasthoff Textmining – Wissensrohstoff Text 2
Wörter in Teile zerlegenAufgabe 1: Grundformreduktion• Reduziere schönste auf schön, Boote auf Boot.• Nützlich für IR, aber auch sonst eine der Standardaufgaben der
Computerlinguistik.• Intuitiver Algorithmus: Endungen abschneiden.• Bekannt: Porter-Algorithmus für‘s Englische: Regelbasiert, nicht
perfekt, kann nicht mit Ausnahmen umgehen.
Aufgabe 2: Kompositazerlegung• Zerlege Hausboot in Haus und Boot.• Ähnliche Trennungsaufgabe wie oben: Im Normalfall muss ein
vorhandenes Wort abgeschnitten werden, so dass ein Wort übrig bleibt.
U. Quasthoff Textmining – Wissensrohstoff Text 3
Gemeinsame Aufgabenstellung
Zerlege Worte so in Teile, dass die Teile bekannt sind (hier: Wörter, Endungen).
Wir können dabei • Ähnlichkeiten der Wörter vom Wortende her (bei
Grundformreduktion und Kompositazerlegung) und • Ähnlichkeiten der Wörter vom Wortanfang her (bei
Kompositazerlegung)Verwenden.
Problem: Unregelmäßigkeiten in der Sprache.
U. Quasthoff Textmining – Wissensrohstoff Text 4
GrundformreduktionIm Normalfall (für Wörter mit normalem Verhalten aus den Wortarten N,A,V)
gibt es ein Flexionsschema, ein ausgezeichnetes Element wird als Grundform ausgewählt, und zwar
• Nominativ Singular im Falle N. Bei Pluralis tantum , wie z.B. "Eltern" gilt Nominativ Plural.
• Positiv im Falle A. Dies gilt auch für Komparation• Infinitiv im Falle V
Im regelmäßigen Falle wird bei N und A hinten abgeschnitten, bei V zusätzlich ein en angefügt.
Beispiele:N: Schulen → Schule, Teppichen → TeppichA: schönster → schön, grünen → grünV: lernte → lernen
U. Quasthoff Textmining – Wissensrohstoff Text 5
Unregelmäßigkeiten bei der GrundformreduktionAusnahmen mit Regelhaftigkeit:• N: Umlaute: Häuser → Haus• N: unregelmäßige Flexion: Extrema → Extremum, ? ? ? → Bronchitis• A: Umlaute: jünger → jung• V: unregelmäßige Flexion: singen, sang, gesungen• V: ge- und zu-: gelaufen → laufen, fortgelaufen → fortlaufen, fortzulaufen →
fortlaufen, zugelaufen → ????
Totale Ausnahmen:• N: Säle → Saal, Feuerwehrleute → Feuerwehrmann
U. Quasthoff Textmining – Wissensrohstoff Text 6
Unregelmäßigkeiten bei der GrundformreduktionAusnahmen mit Regelhaftigkeit:• N: Umlaute: Häuser → Haus• N: unregelmäßige Flexion: Extrema → Extremum, Brochitiden → Bronchitis• A: Umlaute: jünger → jung• V: unregelmäßige Flexion: singen, sang, gesungen• V: ge- und zu-: gelaufen → laufen, fortgelaufen → fortlaufen, fortzulaufen →
fortlaufen, zugelaufen → ????
Totale Ausnahmen:• N: Säle → Saal, Feuerwehrleute → Feuerwehrmann
U. Quasthoff Textmining – Wissensrohstoff Text 7
Mehr Probleme bei der Grundformreduktion• Nicht existierende Grundformen für Wörter wie Eltern oder
allerschönste. • Mehrere alternative Möglichkeiten für einzelne flektierte
Formen wie Dativ Tisch(e) oder Plural von Klima. • Bei Substantiven mit adjektivischer Flexion (z.B. Angestellte)
gibt es die männliche und weibliche Grundform. • Großschreibung am Satzanfang: Was ist die Grundform von
Exakte? Falls es exakt sein soll, verdoppelt sich die Anzahl der flektierten Formen bei V und A potenziell. Es könnte auch Exakt sein, und wir definieren Großschreibung als eine Art von Derivation. Wenn wir hier konsequent sind, müssen wir eigentlich auch andere erlaubte oder nicht erlaubte Schreibweisen berücksichtigen und BERLIN auf die Grundform Berlin und nähmlich auf nämlich abbilden.
U. Quasthoff Textmining – Wissensrohstoff Text 8
Kuriosa bei der Grundformreduktion• Es gibt Wörter, die flektieren in der Mitte statt hinten, z.B.
weitestgehend als Superlativ von weitgehend.• Es gibt Wörter, die flektieren in der Mitte und hinten, z.B.
Landesinnenminister mit Genitiv Landesinnenministers und Plural Länderinnenminister.
• Manchmal funktionieren Komposita anders als das Grundwort. Z.B. hat Waren die Grundform Ware, nicht aber Schreibwaren.
U. Quasthoff Textmining – Wissensrohstoff Text 9
Algorithmische Bearbeitung
Wir benutzen die Eigenschaft, dass Wortanfang und/oder Wortende viel Informationen zur Lösung unserer Probleme beitragen.
Deshalb: Interesse für Datenstrukturen, die Wortanfang oder Wortende „benutzen“.
U. Quasthoff Textmining – Wissensrohstoff Text 10
Problemstellung• Lange Listen von Wörtern müssen für die Verarbeitung
verfügbar sein• Speicherung muß kurze Zugriffszeiten erlauben• Hauptspeicher reicht für plain text-Format mitunter nicht aus
Beispiel: Wortliste für Deutsch hat 9 Millionen Einträge, durchschnittliche Wortlänge 8 Zeichen, dies ergibt über 70MB allein für die Wörter, ohne weitere Eigenschaften und Offset-Informationen.
U. Quasthoff Textmining – Wissensrohstoff Text 11
Speicherung in relationaler Datenbank• Vorteile
- fast unbegrenzter Speicherplatz- Speicherung von Zusatzinformationen möglich- Elementaroperationen wie Einfügen, Löschen und Sortieren von DB implementiert
• Nachteile- langsamer Zugriff- komplexere Operationen wie partial match extrem langsam
Speicherung in DB ist die einfachste Möglichkeit. Für zeitkritische Implementierungen sollten jedoch wenn möglich spezielle Datenstrukturen verwendet werden.
U. Quasthoff Textmining – Wissensrohstoff Text 12
Eigenschaften von Wortlisten
Wortliste: Wurstbrot Wursttheke Käsebrot ...• Reihenfolge unwichtig• Strukturelle Redundanzen: Gleiche Präfixe/Suffixe• Eingeschränktes Alphabet: 26 Buchstaben + Sonderzeichen,
gegenüber 255 ASCII-Characters
U. Quasthoff Textmining – Wissensrohstoff Text 13
Tries: Ausnutzen gleicher Präfixe• Ein Trie ist ein Baum, die Knoten haben 0 bis N
Töchter (N Anzahl möglicher Characters).• Beispiel für Markus, Maria, Jutta, Malte
(root)
Ma
l
t
e
r
u
ik
a
t
t
u
J
sa
17 Knoten mit 16 Characters, 16 Kanten.
U. Quasthoff Textmining – Wissensrohstoff Text 14
Eigenschaften von Tries• Name abgeleitet von Information Retrieval• Spezielle m-Wege Bäume, m ist Kardinalität des
Alphabets • Knoten ist Vektor mit m Zeigern auf Töchterknoten,
implizite Zuordnung Alphabetzeichen und Position• Baumhöhe: Länge des längsten gespeicherten
Wortes -> Suchzeit linear in Wortlänge• Gestalt des Baumes ist unabhängig von
Einfügereihenfolge• Schlechte Speicherplatzausnutzung (viele leere
Pointer) kann vermieden werden durch- Zusammenfassen von Unterbäumen, falls diese nicht verzweigen- Nur Abspeichern der besetzten Zeiger, Angabe über Position erforderlich
U. Quasthoff Textmining – Wissensrohstoff Text 15
Compact Patricia Trie (CPT)• Reduzieren der Kanten durch Speicherung von
mehreren Characters in einen Knoten• Beispiel für Markus, Maria, Jutta, Malte
(root)
Ma
lte< r
ia<kus<
Jutta<
7 Knoten mit 16 Characters, 6 Kanten.
"<" ist Wortendezeichen
U. Quasthoff Textmining – Wissensrohstoff Text 16
Suchen in CPTs
Suche im CPT:• Rekursives Absteigen, Suchwort von vorn verkleinern• Zurückliefern des letzten erreichten Knotens.• Falls restliches Suchwort leer: exact match, sonst partial match
(root)
Ma
lte< r
ia<kus<
Jutta<
Maria<
ria<
ia<
Julia<
lia<
exact match
partial match
U. Quasthoff Textmining – Wissensrohstoff Text 17
Einfügen in CPTsEinfügen von w:• Suche nach w liefert den Zielknoten k• falls exact match: Wort schon vorhanden• falls partial match: Inhalt des Zielknotens k aufteilen,
Töchterknoten einfügen. Es gilt im Zielknoten k: w=uv, k.inhalt=ux
(root)
Ma
lte< r
ia<kus<
Jutta<
Manuela<
nuela<
nuela<
Johannes<
ohannes<J
utta< ohannes<
Fall 1: k.inhalt=u, |x|=0
Einfügen von einem Knoten mit Inhalt v unter k
Fall 2: k.inhalt=ux,|x|>0
Einfügen von zwei Knoten mit Inhalt v und Inhalt x unter k
U. Quasthoff Textmining – Wissensrohstoff Text 18
Speicherung von Zusatzinformationen in CPTs• Knoten werden um Feld erweitert, das die Zusatzinformation
aufnimmt• Beispiel: Speicherung des Geschlechts (w,m) für Namen.
(root)m(3), w(2)
Mam(3), w(1)
lte<m(1)
rm(2),w(1)
ia<m(1), w(1)
kus<m(1)
Jutta<w(1)
In den Blättern stehen die Klassifizierungen.
In den Zwischenknoten befinden sich die zusammengezählten Klassifizierungen der Unterbäume
U. Quasthoff Textmining – Wissensrohstoff Text 19
Anwendung: Grundformreduktion
• Gegeben: Liste von Wörtern mit ReduktionsregelnHaus 0Hauses 2Häuser 5ausMaus 0Mäuse 4ausBau 0Baus 1Aus 0
• Reduktionsregel besteht aus Zahl N und evtl. String x.• lies: Schneide N Characters von hinten ab und füge x an.
U. Quasthoff Textmining – Wissensrohstoff Text 20
Grundformreduktion IICPT wird aus den rückwärts gelesenen Wörtern aufgebaut, in den
Knoten werden die Reduktionsregeln gespeichert. "<" ist Wortanfang-Zeichen.
(root)5aus(1), 4aus(1), 2(1),1(1),0(4)
uab<0(1)
s2(1),1(1),0(3)
resuäh<5aus(1)
esuäm<4aus(1)
ua1(1),0(3)
esuah<2(1)
h<0(1)
m<0(1)
b<1(1)
<0(1)
Haus 0Hauses 2Häuser 5ausMaus 0Mäuse 4ausBau 0Baus 1Aus 0
U. Quasthoff Textmining – Wissensrohstoff Text 21
Grundformreduktion III• Zur Ermittlung der Reduktionsregel eines Wortes wird
der Baum gemäß dem rückwärts gelesenen Wort durchlaufen, bis kein weiterer Knoten mehr matcht (Blatt oder Zwischenknoten).
• Die in diesem Knoten stehende Reduktionsregel wird angewendet.
• Für unbekannte Wörter wird die Regel aufgrund morphologischer Eigenschaften der Trainingsbeispiele geraten
s2(1),1(1),0(3)
ua1(1),0(3)
h<0(1)
m<0(1)
b<1(1)
<0(1)
Hochhaus 0
Spass 0
Unterbaus 1
esuah<2(1)
U. Quasthoff Textmining – Wissensrohstoff Text 22
Pruning: SpeicherplatzreduktionWenn der CPT nur zum Klassifizieren und nicht zum
Speichern von Wörtern verwendet wird, können redundante Teilbäume abgeschnitten werden sowie Strings in den Blättern ohne Änderung des Verhaltens auf Länge 1 verkürzt werden.
(root)5aus(1), 4aus(1), 2(1),1(1),0(4)
uab<0(1)
s2(1),1(1),0(3)
resuäh<5aus(1)
esuäm<4aus(1)
ua1(1),0(3)
esuah<2(1)
h<0(1)
m<0(1)
b<1(1)
<0(1)
(root)5aus(1), 4aus(1), 2(1),1(1),0(4)
s2(1),1(1),0(3)
r5aus(1)
e4aus(1)
ua1(1),0(3)
e2(1)
b<1(1)
Pruning
U. Quasthoff Textmining – Wissensrohstoff Text 23
Weitere Anwendungen von CPTs• Kompositazerlegung:
2 CPTs, Schnittstellen von vorn und hintenWort vorn hintenHochgebirge 4 7Hochzeit 0 0Prüfungszeit 7s 4
• Morphologieklasse• Geschlechter von Namen• Wortarterkennung• Terminologie• ......
U. Quasthoff Textmining – Wissensrohstoff Text 24
Eigenschaften des Verfahrens
Vorteile• Alle Trainingsdaten werden im Test reproduziert• Damit sind beliebige Sonderfälle trainierbar
Nachteile• Trainingsmenge muss eine gewisse Größe haben• Ohne Trainingsmenge ist der Algorithmus völlig hilflos.
Deshalb weiteres Verfahren ohne Training.
U. Quasthoff Textmining – Wissensrohstoff Text 25
Kazakovs Genetische Algorithmen zur morphologischen ZerlegungDer erste Ansatz erschien um das Jahr 1997 herum• (Kazakov 97) und (Kazakov 00), sowie (Kazakov 01)
– Genetischer Algorithmus, welcher versucht zu einer gegebenen Liste von Wörtern herauszufinden, wie jedes Wort so getrennt werden kann, damit möglichst viele Teile wiederverwendet werden
witz|ig, witz|ige, witz|iger, traur|ige, traur|iger, traur|igoptimal, da nur 6 Elemente zu speichern → witz, traur, ig, ige, iger
– Später wurde induktive logische Programmierung verwendet, um aus gewonnen Erstdaten neue Regeln zu lernen, die dann wiederum auf alle Wörter angewendet für mehr Trennungen und bessere Performanz sorgen sollten.
U. Quasthoff Textmining – Wissensrohstoff Text 26
Beispiel Kazakovs Algorithmus0. Iteration, zufällige Initialisierung: Fitness
w|itzig, witz|ige, witzige|r, tr|aurige, trauri|ger, tr|aurig 1/12witz|ig, wit|zige, witz|iger, tra|urige, tra|uriger, tra|urig 1/11witz|ig, w|itzige, wit|ziger, trau|rige, tr|auriger, trau|rig 1/11
1. Iteration, beibehalten der besten Exemplare, Generierung neuer, Mutation:witz|ig, wit|zige, witz|iger, tra|urige, tra|uriger, tra|urig 1/11witz|ig, w|itzige, wit|ziger, trau|rige, tr|auriger, trau|rig 1/11witz|ig, w|itzige, witz|iger, trau|rige, tra|uriger, trau|rig 1/10witz|ig, wit|zige, wit|ziger, tra|urige, tr|auriger, trauri|g 1/10
2. Iteration, beibehalten der besten Exemplare, Generierung neuer, Mutation:… bis maximale Fitness 1/6
U. Quasthoff Textmining – Wissensrohstoff Text 27
Anpassung des Algorithmus zur GrundformreduktionFolgende zusätzliche Regeln:• N und A: Es wird davon ausgegangen, dass die Grundform
durch Abtrennen eines Suffixes entsteht und dass diese Grundform auch in der Wortliste ist: Nach dem Abtrennen muss ein Wort aus der Liste übrig bleiben.
• V: Analog, nur wird zusätzlich noch ein en angefügt.