Die Anwendung von Morphologieanalyse in Information Retrieval-Systemen

Morphologieanalyse und Lexikonaufbau (8. Vorlesung)

Übersicht

• Was ist Informationslinguistik?
• Masszahlen des Information Retrieval
• Informationslinguistik
• Graphematisch-phonologische Verfahren
• Schreibfehlerkorrektur
• Morphologische Verfahren
• Syntaktische Verfahren
• Semantische Verfahren
• Linguistische Probleme in Information Retrieval Systemen

nach [Hahn und Sonnenberger 91]: Einführung in die Informationslinguistik. Uni Konstanz.

Was ist Informationslinguistik?

Informationslinguistik untersucht sprachliche Probleme der Textanalyse, wie sie typischerweise im Kontext von Information Retrieval (IR)-Systemen auftreten.

Was ist Information Retrieval?

Informationsgewinnung aus textuellen Datenbanken. Man klassifiziert IR-Systeme nach:

• Art der zur Verfügung stehenden Information: (Volltexte, Zusammenfassungen)
• Format der Texte (strukturiert: z.B. Bibliographieeinträge; unstrukturiert: z.B. Volltexte)
• nach der Art der Bestimmung der Deskriptoren (von Hand, automatisch)
• nach der Art der Speicherung der Deskriptoren (flache, hierarchische, netzwerkartige Systeme)
• nach der Art des Retrievals (linguistisch basiert, statistisch basiert)

Was ist Indexierung?

Die Abbildung des Inhaltes eines Dokumentes auf eine Menge von relevanten Begriffen.

Genauer: Die Zuordnung von Deskriptoren und Notationen zu Dokumenten zwecks ihrer inhaltlichen Erschliessung und gezielten Wiederauffindung (vgl. DIN 31 623).

Vgl. Heinz-Dirk Luckhardt (Universität des Saarlandes): Automatische und intellektuelle Indexierung

Masszahlen des Information Retrieval

Die Qualität eines Information Retrieval Vorgangs wird durch zwei Masszahlen (Recall und Precision) beschrieben, die auf folgenden Parametern beruhen:

1. Anzahl der gefundenen relevanten Dokumente: F
2. Anzahl aller relevanten Dokumente: R
3. Anzahl aller gefundenen Dokumente: A

Recall (Vollständigkeit der Suche)

V = F/R

Precision (Genauigkeit der Suche)

G = F/A

Merke: 'Relevanz' ist das Mass der Übereinstimmung zwischen einem Dokument und der Suchanfrage aus der Sicht eines Experten.

Informationslinguistik

Die sprachlichen Probleme der Informationslinguistik betreffen sämtliche Ebenen der sprachwissenschaftlichen Betrachtung.

1. Graphematisch-phonologische Verfahren

1.1 Erkennung von lautlichen oder Schreibvarianten

• Personennamen in Presse-Datenbanken, Personal-, Patienten- oder Kunden-Dateien

  MEIER <=> MEYER <=> MAIER <=> MAYER <=> MAYR 
  GORBACHOW <=> GORBACHEV <=> ... 
  GHADDAFY <=> KHADAFY

• geographischer Name

  MUENCHEN <=> MUNICH <=> MONACO DI BAVIERA <=> ...

• Produktnamen in Patentämtern

  CRONAT <=> SOMAT

• Abkürzungen / Akronyme

  CO2 <=> Kohlenstoffdioxyd 
  NATO <=> North Atlantic Treaty Organisation

Erkennung von Namensvarianten:

KODENAMEN-Verfahren; SOUNDEX-Verfahren

1.2 Schreibfehler-Erkennung und -Korrektur

Untersuchungen (in den 80er Jahren) haben ergeben, dass in On-line Datenbanken teilweise mehr als 10% Schreibfehler vorkommen (d.h. jedes 10. Wort ist falsch geschrieben).

80% der Schreibfehler lassen sich auf die folgenden 4 Fehlertypen zurückführen:

 Auslassung			CHMICAL 
 Einfügung			CHEMEICAL 
 Substitution			CHEMECAL 
 Vertauschung			CHMEICAL 
				==> CHEMICAL

Anzahl der möglichen Schreibfehler (Einfachfehler) in einem Wort der Länge n (Ausgangsbasis 26 Buchstaben, Bindestrich, Hochkomma)

 Auslassung		n 
 Einfügung		28 * (n + 1) 
 Substitution		27 * n 
 Vertauschung		n - 1

Wortlistenabhängige Verfahren zur Schreibfehlererkennung:

Abgleich mit einer Wortliste (mit oder ohne Lemmatisierung)

Problem: Wenn der Schreibfehler ein anderes korrektes Wort ergibt, wird er nicht erkannt.

Wortlistenunabhängiges Verfahren zur Schreibfehlererkennung:

N-Gramm-Analyse: basiert auf der Untersuchung der Häufigkeit von Buchstabenfolgen einer bestimmten Länge (meist Länge n=2 oder n=3).

Anzahl möglicher n-Gramme: (angenommen 28 Zeichen im Alphabet)

Bigramme:

28² = 784

Trigramme:

28³ = 21'952

In einem grösseren Textkorpus treten ca. 70% der möglichen Digramme und ca. 25% der möglichen Trigramme auf.

Bsp.: Cmputer wird als Fehler erkannt, da Trigramm cmp im Deutschen nicht vorkommt.

Schreibfehlerkorrektur

1. Identifikation über Kodenamen
2. Berechnung eines Ähnlichkeitsmasses (Gewichtung von Umstellungs-, Tilgungs- oder Einfügungsoperationen; oder auch über gemeinsame Digramme oder Trigramme)

Was leisten kommerziell erhältliche Schreibfehlererkenner bzgl. Korrekturvorschlägen?

Ein Experiment mit: WordPerfect 2.1.0 für MacIntosh; USA-English

Korrigiert nicht:

• Auslassung eines Konsonanten: coputer
• Auslassung eines Vokals vor dem letzten: compter
• Einfügung eines Konsonanten (ausser Verdopplung): combputer
• Substitution eines Konsonanten: combuter
• Substitution eines Vokals durch einen Konsonanten: compkter
• Vertauschung: Vokal-Konsonant: comupter

Korrigiert:

• Auslassung des letzten Vokals: computr
• Substitution eines Vokals: compoter, campiter
• Einfügung von Vokalen: coomputer, coaomputer
• Verdopplung von Konsonanten: commpputter, ccuouoampauter

WordPerfect 5.1 für DOS; Deutsch

Korrigiert auch:

• Auslassung eines Buchstaben: coputer, cmputer
• Einfügung eines Konsonanten: computrer

Eine kleine Testdatei im Word-Format und als Text-Datei.

Ein Prolog-Programm, das Korrekturvorschläge für die obigen Fehlertypen berechnet.

2. Morphologische Verfahren

1. Erkennung und Reduktion von Flexionsvarianten einer Grundform

   COMPUTER 
   COMPUTER'S 
   COMPUTERS 
   COMPUTERS' 
   ==> COMPUTER

2. Erkennung und Reduktion von Derivationsvarianten einer Stammform

   COMPUTER 
   COMPUTATIONAL 
   COMPUTED 
   ==> COMPUT(E)

3. Erkennung von Bestandteilen eines Kompositums (bes. bei Fugenlaut und Ellision eines Konsonanten)

   Zeitungsartikel
   ==>  Zeitung + Artikel

   Schrittempo
   ==>  Schritt + Tempo

3. Syntaktische Verfahren

3.1 Erkennung von komplexen (mehrgliedrigen) Nominalphrasen

Beispiel:

EIGENVALUE PROBLEM
INFORMATION THEORY
DEDUCTIVE DATA BASE

Im Information Retrieval werden dafür besonders Abstandsoperatoren (`Adjacency') verwendet.

Als informationslinguistische Lösungsansätze kommen folgende Verfahren in Betracht:

• vollständige Sytaxanalyse (Parsing)
• partielle Syntaxanalyse
  • wörterbuchunabhängig (Begrenzerverfahren)
  • wörterbuchabhängig (Bottom-Up Chart-Parsing, Island Parsing)

Wörterbuchunabhängige Syntaxanalyse basiert auf der Segmentierung eines Textes über die Funktionswörter (Artikel, Präpositionen, Konjunktionen, Determiner-Pronomen) und Interpunktion. Diese werden interpretiert als Begrenzer, die eine Nominalgruppe einleiten oder abschliessen. Eine Verfeinerung des Verfahrens ist möglich über die Ermittlung der statistischen Relevanz von Begrenzerpaaren.

Beispiele:

was generally controlled by 
the porosity formed by

Beispiel für Begrenzerverfahren: FIPRAN-System [Volk et al. 1991]

3.2 Erkennung von nominalen syntaktischen Paraphrasen

WATER TREATMENT  <=> TREATMENT WITH WATER 
NEUTRON EXCHANGE <=> EXCHANGE OF NEUTRONS 

3.3 Erkennung und Auflösung von Nominalkomposita

EIGENWERTBERECHNUNG  ==> BERECHNUNG, EIGENWERT  
PROGRAMMENTWURF  ==> PROGRAMM, ENTWURF 

3.4 Erkennung von attributiv expandierten Varianten von Nominalphrasen

BERECHNUNG VON EIGENWERTEN 
BERECHNUNG EINFACHER EIGENWERTE 
BERECHNUNG DICHT BENACHBARTER EIGENWERTE 
BERECHNUNG ZWEIER ISOLIERTER EINFACHER EIGENWERTE 
==> BERECHNUNG, EIGENWERT

4. Semantische Verfahren

1. Extraktion inhaltlich signifikanter Terme durch Abgleich mit Stoppwort- oder Positiv-Listen
2. Bestimmung inhaltlich signifikanter Terme für Indexing und Retrieval durch Berechnung von einfachen Termgewichten
3. Thesaurus-basierte Verfahren

Linguistische Probleme in Information Retrieval Systemen

(nach [Kuhlen 86]: Informationslinguistik.)

1. Eliminierung von bedeutungslosen Wörtern (Stoppwortlisten)
2. Reduktion von Wortformen auf Grund- oder Stammformen (Lemmatisierung)
3. Wortzerlegung in kleinere semantische Einheiten (z.B. in Morpheme)
4. Bestimmung der Wortart (Tagging)
5. Partielles Parsing, um relevante Nominalphrasen und Präpositionalphrasen zu erkennen
6. Paraphrasen für komplexe Nominalphrasen
7. Partielles Parsing, um einfache syntaktische Relationen zu erkennen (Subjekt, Objekt, Präpositionalobjekt)
8. Erkennung von Topik (Thema) und Comment (Rhema)
9. Disambiguierung von Homographen mit Hilfe von Kontext oder Parsing

   Wald+Bäume+Kiefer  => Baum
   Zahnarzt+Schmerzen+Kiefer  => Kopfteil

10. Elementares Parsing zur Erkennung von syntaktischen Einheiten (Teilsätze; z.B. Relativsätze oder elliptische Koordination abgrenzen und auflösen)
11. Zusammenstellung von Wortgruppen über assoziative Relationen (-> z.B. über einen Thesaurus)
12. Zusammenstellung von Verbrahmen (aufgrund von Valenzangaben)
13. Erzeugung von Prädikat-Argument Strukturen (Prädikatenlogik)
14. Integration von gewichteten semantischen Relationen