Endliche Automaten zur Erkennung von...

DFA zur Spracherkennung 2009 - Uni Heidelberg - Vortrag Stoppwörter 1

Endliche Automaten zur Erkennung von Stoppwörtern

Vortrag von Christian Schwarz & Andreas Beyer

im Seminar FSM zur Spracherkennung06.07.2009


Die Gliederung Erklärung der Begriffe des Vortrags

Was sind Stoppwörter und Schlüsselwörter Relevanz dieses Konzepts für die Praxis

Einige Motivationen für die Praxis Exemplarische Abarbeitung von Suchbegriffen

und Indexbildung Die Grenzen des Verfahrens bei

Doppeldeutigkeiten und Wie wird es umgesetzt

Einordnung in den Indizierungsablauf Einige kleine Demonstrationen


Gliederung

Begriffsklärung Stopp- / Schlüsselwörter

Praxisrelevanz Motivation Beispiele Grenzen

Umsetzung Demo


„Stop“ ist kein Stoppwort...


Stoppwort Definition

Aus der Literatur Ein Stoppwort ist ein Wort in einem Dokument

oder einer Anfrage, das den Retrievalprozess nicht beeinflusst.

Es hat die gleiche Wahrscheinlichkeit, in einem für eine Anfrage relevanten Dokument vorzukommen wie in einem nicht relevanten Text.

Stoppworte tragen keinerlei Wissen, sie sind inhaltslos.

Verschiedene Wortarten in einem Text tragen unterschiedlich viel zur inhaltlichen Bedeutung bei:

• Artikel: keine • Substantive: sehr vielVorverarbeitung des Textes sinnvoll, um die

„Sinn tragenden“ Wörter für spätere Verarbeitungsschritte (z.B. Indexerstellung) zu identifizieren

Quelle der Textstellen: Information Retrieval: Informationen suchen und finden von Wolfgang G. Stock


„Key“ ist ein Keyword...


Was sind Keywords

Gegenstück zu Stoppwörtern Schlüsselwörter / Keywords sind für

Textindizierung essentiell Haben hohe Aussagekraft über Textinhalt

Beispiel: Stichwortverzeichnis des Lexikons

Deskription des Textes


Key- und Stoppwörter im Text

Viele grundlegende Aufgaben der Sprachverarbeitung von der Zerlegung eines Textes in Wörter bis zur phonologischen und morphologischen Analyse, zur Rechtschreibkorrektur und zum flachem Parsing können mit endlichen Automaten und Transduktoren sehr effizient durchgeführt werden.

Schlüsselwörter

Stoppwörter

Üblicherweise handelt es sich bei zwischen 30% und 50% der Wörter eines Textes um Stopp-

Wörter [PC]:

[PC] Peters, Carol - Mehrsprachiger Zugang bei Informationssystemen,

http://www.ifla.org/IV/ifla67/papers/099-183g.pdf

Quelle der Textstelle: Inhaltsangabe des Hauptseminars Endliche Automaten für die Sprachverarbeitung von Dr.Karin Haenelt


Stoppwörter - Fazit werden bei Volltextindexierung nicht beachtet treten sehr häufig auf

gewöhnlich keine Relevanz für Dokumentinhalt Blähen somit Index ohne Nutzen auf

ihr Weglassen dient Steigerung der Effizienz Ansonsten würde Ergebnismenge nahezu jedes

Dokument des Bestandes enthalten Suchergebnis wäre unscharf, Nutzwert gering

Bsp: der, die, das, ein, eine, zu, bei, an, doch

Stoppwörter nennt man Wörter, die bei einer Volltextindexierung nicht beachtet werden, da sie sehr häufig auftreten und gewöhnlich keine Relevanz für die Erfassung des Dokumentinhalts besitzen.

Allgemein übliche Stoppwörter in deutschsprachigen Dokumenten sind bestimmte Artikel (der, die, das, unbestimmte Artikel (einer, eine, ein), Konjunktionen (z.B. und, oder, doch) und häufig gebrauchte Präpositionen (z.B. an, in, von), sowie die Negation „nicht“. Abhängig von den zu erschliessenden Dokumenten können Stoppwörter auch mehrsprachig vorliegen. Diesen Wörtern ist gemeinsam, dass sie vor allem grammatische/syntaktische Funktionen übernehmen und daher keine Rückschlüsse auf den Inhalt des Dokumentes zulassen. Eine weitere Gemeinsamkeit ist ihre grosse Zahl: Sie treten in jedem Dokument sehr zahlreich auf und kommen in sehr vielen Dokumenten vor.

Das Weglassen von Stoppwörtern dient der Steigerung der Effizienz von Suchmaschinen. Würde man Stoppwörter bei einem Suchauftrag beachten, würde die Ergebnismenge nahezu jedes Dokument des Bestandes enthalten. Das Suchergebnis wäre unscharf, sein Nutzwert gering.


Gliederung



Umsetzung Demo


Motivation

Aktuelle Forschungsthemen: Text classification Document clustering Ähnlichkeitsanalyse bei Dokumenten Web intelligence Web mining Suchmaschinen

Seminar CloudComputing - Uni Heidelberg - SoSe 2009 - Vortrag GoogleAppEngine 12

Einsatzgebiete

Indizierung großer Corpora Aufwändig Aufnahme von „ohne“, „bei“, „in“ nutzlos Nach Tokenisierung werden Stoppwörter

gelöscht Indexbildung beschleunigen / Index minimieren

Verkleinern des Anfrageterms Keine Suche nach Elementen die ohnehin nicht

im Index enthalten sind


Anwendung (1)

Durch den Treibhauseffekt ist auf den schönen Malediven wohl bald schon Land unter


IndizierungCorpus Index1


Treibhauseffekt Malediven Land

Index2

Indizierung

Stoppwort-entfernung

Stoppwörter aus Index entfernen Liste individuell erstellt Abhängig von Sprache und Themengebiet


Anwendung (2)

Durch den Treibhauseffekt ist auf den Malediven wohl bald schon Land unter

Index1 (mit SW)


Index2

Die Malediven und der Treibhauseffekt

Ist durch den Börsencrash bald schon mehr los unter der Brücke?


Anwendung (2)


Index1 (mit SW)


Index2


Relevant → Ausgabe





Anwendung (2)


Index1 (mit SW)


Index2 Anfrage2 → 16% Index1 66% Index2




Anfrage1 → 58% Treffer in Index1 0% in Index2Ist durch den Börsencrash bald schon mehr los unter der Brücke?


Anfrage an Index mit und ohne Stoppwörter Bei Anfrage1 100% Recall Bei Anfrage2 0% Recall & 100% Precision



Anwendung (3)


Index1

Index2





Anwendung (3)


Index1

Index2





Anfrage2 → 16% Index1 66% Index2

Anfrage1 → 0% in Index1 0% in Index2

Stoppwörter aus Index und Anfrage entfernt Nur „inhaltsvolle“ Terme werden berücksichtigt Insgesamt 100% Precision & 0% Recall


Wozu?

Stoppwörter sind „Hintergrundprozess“ Initial definiert (ein- oder mehrsprachig) Anwendung auf viele Corpora Index ändert sich dynamisch Stoppwortliste bleibt statisch

Minimieren Anfrage und Index um „Precision“ zu erhöhen

Keine Auswirkung auf „Fallout“ Ohnehin nicht Gefundenes kann man nicht

„herbei-löschen“


SEM – SEO – SERP

Große Bedeutung zB bei Internetwerbung SEM = Search Engine Marketing

ein Internetauftritt soll auch gefunden werden SEO = Search Engine Optimization

Durch geziehlte Formulierungen, unter Vermeidung von Stoppwörtern, erhöhen der Seitenrelevanz (Precision) für Suchmaschine

SERP = Search Engine Result Page Heiliger Gral des Marketing → Platz in Top10


Grenzen Google-Anfrage gut im Cache auf

Stoppwörter überprüfbar

im Cache (Suchwörter farbig markiert)

„auf“ wurde also als Stoppwort gelöscht Offensichtlich wird hierüber kein Index

gebildet


Grenzen (2) Was wenn die Anfrage „relevante

Stoppwörter“ enthält?

Im Cache sieht man:

„an der Oder“ wurde (leider) entfernt Treffer zu Frankfurt am Main erhöhen Recall


Grenzen (3) Anfragen komplett aus Stoppwörtern:

Im Cache

Sonderfälle:● Sein oder nicht Sein● Man ist was man isst● Stephen Kings „ES“● Finca auf Mallorca● Flug nach Berlin


Grenzen (4) Entfernung fördert Ambiguitäten

daher nicht erster Schritt der Tokenpipeline


Gliederung



Umsetzung Demo


Vorverarbeitungsschritte

1. lexikalische Analyse: Handhabung von Zahlen, Binde-strichen, Interpunktionszeichen und Groß-/Kleinschreibung

2. 2. Stoppwörter entfernenStoppwörter entfernen: Identifizieren von Wörtern, die : Identifizieren von Wörtern, die nur wenig zur Unterscheidung von Dokumenten für das nur wenig zur Unterscheidung von Dokumenten für das spätere Retrieval beitragenspätere Retrieval beitragen3. Wortreduktion: Abtrennen von Affixen, um syntaktische Varianten der Anfragewörter einfach handhaben zu können

4. Auswahl von Indextermen: Parameter für Aufbau und Struktur des Index festlegen

5. Konstruktion von zusätzlichen „Zugriffsstrukturen“: Klassifikation, Thesaurus, Textstruktur


Tokenpipeline

Dokument Struktur-Erkennung

Lexikalische Analyse

Stoppwort-Eliminierung

Stammwort-Reduzierung

Phrasen-Bildung

Thesaurus-Bildung

Auswahl der Index-Terme

SW-Löschung im Ablauf Lex.Ana. zur Bewahrung von Redewendungen

und Ausdrücken wie „Sein oder nicht Sein“

Das Prinzip des seriellen Aneinanderreihens von Token-Filtern nennt man Pipilining bzw. Tokenpipelines. Die einzelnen Filter werden in der Literatur auch als Normalisierungstechniken bezeichnet. Prinzipiell kann man die Filter in einer beliebigenReihenfolge verketten, doch gehen manche Verfahren von bestimmten Vorbedingungen aus, wie beispielsweise Porter-Algorithmus zur Stammwortreduktion eine einheitliche Kleinschreibung der Tokens voraussetzt.


Reduktion als Teil der Lex.Ana.

DFA erzeugen

Lexikalische AnalyseEingabedokument

Stoppwortliste

Eingabedokument schließen und Termrückgabe

Lese Stoppwortliste ein

Terme

Stoppwörter statische Liste

Bei dieser Filter-Methode wird der ankommende Token-Strom mit einer Liste von Stopp- bzw. Füllwörtern verglichen, und die dort enthaltenen Tokens dann entfernt. Eine geeignete Stoppwortliste sollte alle W drter ohne semantischen Wert, wie z.B. Artikel, Präpositionen und Konjunktionen,herausfiltern und nur solche belassen, welche eine Differenzierung bzw. eine Interpretation des Dokumenteninhalts zulassen. Stoppwortlisten sind sprachspezifisch.


Fox-Algorithmus

aanand

to

ininto

Ziel: minimaler DFA für LexikoneinträgeVoraussetzung: Lexikon liegt alphabetisch sortiert vorVorgehensweise: -Zeichenweise Überführung in Graphen-Zustände besitzen Labels

Menge von Zeichenketten die noch in den Graphen überzuführen sind.

Zustände mit gleichen Labels werden zu einem Zustand verschmolzen => minimaler Automat

1. Erzeuge Startzustand q0 mit Menge aller Eingabezeichenketten als Label L0.

2. Platziere q0 in einer leeren Warteschlange Q3. Solange Q ≠ ø 1. Entferne qi mit Label Li aus Q 2. Ermittle für jedes Anfangszeichen a aus Li ein Label mit den Restketten. Erzeuge eine neue Kante mit Übergang a zu dem Zustand mit diesem Label, falls Zustand nicht vorhanden, erzeuge diesen und füge ihn in Q ein.4. Alle Zustände die Lamda enthalten sind Endzustände.


Fox-Algorithmus

aanand

to

ininto q0







Fox-Algorithmus

aanand

to

ininto q0

q2

q3

a

i

t

q1







Fox-Algorithmus

aanand

to

ininto q0

q2

q3

a

i

t

λnnd

nnto

o

q1







Fox-Algorithmus

aanand

to

ininto q0

q2

q3

a

i

t

λnnd

nnto

o

q1







Fox-Algorithmus

aanand

to

ininto q0

q2 q6

q3

q4

a

i

t

λnnd

nnto

o

q1

q5

n

λd

n

λto

o

λ







Fox-Algorithmus

aanand

to

ininto q0

q2 q6

q3

q4

a

i

t

λnnd

nnto

o

q1

q5

n

λd

n

λto

o

λ







Fox-Algorithmus

aanand

to

ininto q0

q2 q6

q3

q4

a

i

t

λnnd

nnto

o

q1

q5

n

λd

n

λto

o

λ

t

d







Stoppwortgewinnung

3 Ansätze: Feststellung allgemeiner Stoppwörter in

einer Sprache Zum Beispiel Artikel und ähnliches

Feststellung der Stoppwörter in einer gegebenen Dokumentenmenge Für IT-Texte ist „Computer“ ein Stoppwort

Feststellung der Stoppwörter innerhalb genau eines Dokuments

Stopwortlisen sind nichts neues 75 van Rijsbergen und anfang der 60er Jahre wurde Brown Corpus aufgestellt

Allerdings fehlen neue spam-Worte wie „email“, „contact“, „mobil“,...


DEMO


Danke für die Aufmerksamkeit

Fragen?


Quellen Rachel Tsz-Wai Lo, Ben He, ladh Ounis (2005). Automatically Building a Stopword List for an

Information Retrieval System. Journal of Digital Information Management Vol 3 Nr 1, 2005

Mark P. Sinka, David W. Corne (2002). Evolving Better Stoplists for Document Clustering and Web Intelligence.

Tobias Hildenbrand (2003). Studienarbeit: Information Retrieval und Suchmaschinen.

Uni Mannheim.

Dr. Karin Haenelt (2005). RegEx – FSA: Algorithmus von Fox.

Uni Heidelberg.

Sven Meyer zu Eissen and Benno Stein (2006). Service-orientierte Architekturen für Information Retrieval. Uni Weimar.

Carola Kühnlein (2003). Eigennamenerkennung über Konzeptsensoren.

Uni Zürich.

Date post:	17-Sep-2018
Category:	Documents
Upload:	vomien
View:	216 times
Download:	0 times

Endliche Automaten zur Erkennung von...

Documents