Information Retrieval (SS 2011) - Natürliche Sprache

Transcrição

2. Natürliche Sprache
Rückblick
✦
Übersicht über die Inhalte der Vorlesung
✦
Defini3on und Geschichte des Begriffs “Informa5on Retrieval”
✦
Boolesches Retrieval und Vektorraum-‐Modell
✦
Inver3erter Index
✦
Precision und Recall als Maße der Ergebnisgüte
Informa5on Retrieval (SS 2011)
2
Mo5va5on
IR betrachtet meist natürlichsprachliche Inhalte
✦
Vielfalt und Vagheit natürlicher Sprache werfen zahlreiche Herausforderungen und Fragestellungen auf z.B.
✦
✦
Wie teilt man einen Text in zu indexierende Dokumente auf?
✦
Wie teilt man ein Dokument in zu indexierende Wörter auf?
✦
Welche Wörter sollen in welcher Form indexiert werden?
✦
✦
✦
Mehrwortgruppen und Komposita
(z.B. informa5on retrieval und bundeskanzleramt)
Unterschiedliche Formen des gleichen Wortes
(z.B. house/houses und laufen/laufe/lief)
Polyseme und Synonyme
(z.B. bank, present, automobile/car, und sick/ill)
3
Inhalt
(1) AuWeilung in Dokumente
(2) AuWeilung von Dokumenten
(3) Normalisierung
(4) Eliminierung von Stoppwörtern
(5) Reduk5on auf Grund-‐ oder Stammformen
(6) Komposita und Wortgruppen
(7) Synonyme und Polyseme
(8) Rechtschreibung
4
2.1 AuNeilung in Dokumente
Granularität von Dokumenten hängt von der Anwendung ab und muss vor der Indexierung festgelegt werden z.B. als
✦
✦
✦
✦
✦
✦
✦
✦
Webseite
Office-‐Datei
E-‐Mail mit Anhängen
Veröffentlichung (z.B. Buch oder Ar5kel)
Kapitel
Abschnig / Passage
Satz
5
2.2 AuNeilung von Dokumenten
✦
Prinzipielles Vorgehen um vom Inhalt der Dokumente zu einem suchbaren Index zu gelangen
Zeichen
O|’|N|e|i|l|_|m|a|d|e|_|t|h|e|_|b|o|o|k|’|s|_|c|o|v|e|r
Tokenisierung
Tokens
O’Neil
made
the
book’s
cover
Sprachabhängige Transforma3onen
Terme
oneil
made
book
cover
Indexierung
✦
Die resul5erenden Terme werden, meist in inver5erten Listen, indexiert und bes5mmen “wonach man suchen kann”
6
Tokenisierung
Tokenisierung (tokeniza)on) durch AuWeilen an Leerzeichen (white spaces) und Eniernen von Satzzeichen (z.B. . ? !) als Ausgangspunkt für Sprachen wie Englisch und Deutsch
✦
Ein alterna3ver aggressiverer Ansatz teilt die Zeichenkege an allen nicht-‐alphanumerischen Zeichen auf
✦
Sprach-‐ und anwendungsabhängige Feinheiten z.B. für
✦
✦
✦
Apostroph
l’âme, coup d’état
peter’s, Johnsons’, he’ll, ain’t, o’neil
Bindestriche
bread-‐and-‐buger, brick-‐and-‐mortor
donne-‐moi, ving-‐et-‐un
7
2.3 Normalisierung
Groß-‐ und Kleinschreibung wird häufig vollständig verworfen und alle Tokens in Kleinbuchstaben konver5ert (case folding)
✦
Beibehalten von Groß-‐ und Kleinschreibung sinnvoll für
✦
✦
✦
✦
Akronyme (z.B. CAT, SIAM, MIT)
✦
Familiennamen (z.B. Bush, Black)
✦
Markennamen (z.B. General Motors, Apple, The Associated Press)
Solche Ausnahmen können manuell über Wortlisten definiert werden oder miWels Lernverfahren erkannt werden Benutzer formulieren Anfragen meist in Kleinbuchstaben
8
Normalisierung
Akzente und Umlaute werden auf kanonische Form abgebildet
✦
✦
école ➔ ecole, résumé ➔ resume
✦
Saarbrücken ➔ Saarbruecken, Dächer ➔ Daecher
Bindestriche (hypen) werden für bes5mmte Präfixe eniernt
✦
✦
an5-‐discriminatory ➔ an5discriminatory, de-‐bug ➔ debug
Akronyme werden auf kanonische Form abgebildet
✦
✦
C.I.A. ➔ CIA, U.S.A. ➔ USA
Datums-‐ und Zeitangaben werden in ein Format konver5ert
✦
✦
2011/04/14 ➔ 2011/04/14, 14.04.2011 ➔ 2011/04/14 Informa5on Retrieval (SS 2011)
9
2.4 Eliminierung von Stoppwörtern
Stoppwörter sind Wörter, die wenig Informa3on beinhalten, da sie z.B. in sehr vielen Dokumenten auWreten und somit von geringem Nutzen für die Beantwortung von Anfragen sind ✦
Durch Eliminierung von Stoppwörtern kann man erreichen
✦
✦
Reduzierung des zur Indexierung benö5gten Speicherplatzes
✦
Verbesserung der Antwortzeiten
✦
✦
Verbesserung von Precision und Recall
(z.B. für Anfragen wie a movie that clint eastwood has directed)
Verschlechterung von Precision und Recall
(z.B. für Anfragen wie the who und let it be)
10
Eliminierung von Stoppwörtern
Eine Stoppwortliste wird typischerweise manuell definiert evtl. basierend auf vorheriger Analyse von Term-‐Häufigkeiten
✦
a for of will Alterna5v kann eine Stoppwortliste automa3sch festgelegt werden z.B. als Liste aller Wörter, die ✦
✦
an and are as at be by has has he in is it its on that the to was were with
✦
in mehr als k% der Dokumente vorkommen
✦
in weniger als m% der Dokumente vorkommen
Eliminierung von Stoppwörtern heutzutage eher unüblich
11
Gesetz von Zipf
✦
Die Häufigkeit cfi des i-‐häufigsten Worts ist propor5onal zu i
1
cfi ∝
i
✦
Für die rela5ve Häufigkeit cfi / LD mit sprachabhängiger Konstante c (für Englisch c ≈ 0.1) gilt
cfi / LD = c · i−1
✦
Die Verteilung der Worthäufigkeiten ist also schief (skewed)
12
Gesetz von Zipf
13
Gesetz von Heaps
✦
Größe des Vokabulars |V| in einer Dokumentenkollek5on verhält sich zur Anzahl der Wortvorkommen LD als
|V| = k · LD b
mit kollek5onsabhängigen Konstanten k und b
✦
Größe des Vokabular stagniert also nicht, sondern wächst mit der Dokumentenkollek3on – eine wich5ge Beobachtung u.a. für die Implemen5erung von IR-‐Systemen
14
Gesetz von Heaps
1e+07
The New York Times
log10 |V|
Heaps’ Law (k = 35, b = 0.5)
1e+06
100000
1e+07
1e+08
1e+09
log10 LD
15
2.5 Reduk3on auf Grund-‐ oder Stammformen
Wörter in verschiedenen Beugungsformen (Flexionsformen)
✦
✦
✦
✦
✦
Konjuga3on bei Verben
gehen – ging – gegangen, go – went – gone
Deklina3on bei Substan5ven und Adjek5ven
Boot – Bootes – Boote, boat – boats
billig – billige – billiges – billigen – billigem
Kompara3on bei Adjek5ven
billig – billiger – billigsten, cheap – cheaper – cheapest
Wörter mit gleichem Wortstamm
Fahrt – Fahrer – fahren, house – houses – housing
Arbeit – Arbeiter – arbeiten, work – worker – working
16
Grundformreduk5on
Reduk5on auf Grundform (auch: Lemma5sierung) (lemma)za)on) erfolgt immer auf ein exis3erendes Wort
✦
✦
✦
Nomina3v Singular bei Substan5ven und Adjek5ven
Boot – Bootes – Boote ➔ Boot, boat – boats ➔ boat
Infini3v bei Verben
gehen – ging – gegangen ➔ gehen, go – went – gone ➔ go
Bes5mmung der korrekten Grundform eines Tokens ist oW schwierig und bedarf zusätzlicher Informa5on in Form von
✦
✦
Kontext
Wortart (part of speech)
Bowling/NNP is/VBZ her/PRP$ favorite/JJ hobby/NN
✦
Wörterbuch (z.B. um mice auf mouse abzubilden)
✦
17
Stammformreduk5on
Reduk5on auf Stammform (stemming) erfolgt auf den Wortstamm, der kein exis3erendes Wort sein muss
Boat ➔ Boat, Boats ➔ Boat
go ➔ go, went ➔ went, gone ➔ gone
✦
vegeta5on ➔ veget, vegetables ➔ veget
Für schwach flek5erte Sprachen wie Englisch funk5onieren regelbasierte Ansätze zur sukzessiven Suffixeniernung
✦
Bekannte Verfahren zur Stammformreduk5on in Englisch
✦
✦
✦
✦
Lovins (1968) : Regeln
Porter (1980) : Regeln
Krovetz (1993) : Regeln und Wörterbuch
18
Porters Algorithmus zur Stammformreduk5on
✦
Fünf Schrige zur sukzessiven Suffixeniernung (suffix stripping)
SchriW 1a: Wende Regel für längstmögliches Suffix an
sses ➔ ss caresses ➔ caress
ies ➔ i ponies ➔ poni
ss ➔ ss caress ➔ caress
s ➔ cats ➔ cat
…
SchriW 2: Falls Token aus zwei oder mehr Silben besteht
a5onal ➔ ate rela5onal ➔ relate
5onal ➔ 5on condi5onal ➔ condi5on
enci ➔ ence valenci ➔ valence
izer ➔ ize digi5zer ➔ digi5ze
…
✦
Algorithmus wird auf jedes Token separat angewendet
19
Reduk5on auf Grund-‐ oder Stammformen
Durch Reduk3on von Wörtern auf ihre Grund-‐ oder Stammform kann man erreichen ✦
✦
✦
✦
✦
✦
✦
toleranteres Matching von Dokumenten (im Booleschen Retrieval), das nicht mehr von spezifischer Woriorm abhängt
keine exakte Suche nach spezifischer Woriorm mehr möglich
geringere Anzahl indexierter Terme und kleineres Wörterbuch
Verbesserung von Recall
(z.B. für Anfragen wie working conditions chinese factories)
Verschlechterung von Precision (z.B. für Anfragen wie marine vegetation oder housing costs)
Nutzen von Grund-‐ und Stammformreduk5on für IR ist umstriWen aber tendenziell höher für stark flek5erte Sprachen
20
2.6 Komposita und Wortgruppen
✦
✦
Komposita (compounds) sind ein wesentlicher Bestandteil der deutschen Sprache (z.B. Donaudampfschiff, Dachlawine oder Bundespräsidentenwahl)
Zerlegung in Bestandteile (compound spliEng) mit Hilfe eines Wörterbuchs als ein möglicher Ansatz zum Umgang mit Komposita im IR
Donaudampfschiff ➔ {Donau, dampf, schiff}
Bundespräsidentenwahl ➔ {Bundes, präsidenten, wahl}
Dachlawine ➔ {Dach, lawine}
21
Komposita und Wortgruppen
In der englischen Sprache hat man das entgegengesetzte Problem von Wortgruppen (z.B. united states, hewleg packard, new york university, web-‐search engine)
✦
Mögliche Ansätze zum Umgang mit Wortgruppen im IR sind
✦
✦
✦
Iden3fika3on von Wortgruppen mit Hilfe eines Wörterbuchs united states ➔ united_states
hewleg packard ➔ hewleg_packard
new york university ➔ new_york_university Ausnutzen von Posi3onsinforma3on z.B. in Form von expliziten Phrasen-‐Anfragen (phrase queries) oder Ordnung von Ergebnissen unter Einbeziehung der Termnähe (proximity ranking) Informa5on Retrieval (SS 2011)
22
2.7 Synonyme und Polyseme
Synonyme (z.B. car/automobile, buy/purchase, sick/ill) sind Wörter mit gleicher oder sehr ähnlicher Bedeutung
✦
✦
Polyseme (z.B. bank, present, bed) sind Wörter, die verschiedene Bedeutungen haben können
✦
✦
✦
wirken sich nega5v auf Recall aus
wirken sich nega5v auf Precision aus
Ein tradi3oneller Ansatz zum Umgang mit Synonymen und Polysemen ist die manuelle Verschlagwortung von Dokumenten mit einem standardisierten Wortschatz
23
Thesaurus
Thesaurus (wörtlich: Wortschatz) ist eine Sammlung von Begriffen, die zueinander in Beziehung gesetzt sind z.B. als
✦
✦
✦
✦
✦
✦
Synonyme (Gleiche Bedeutung)
car – automobile, holidays – vaca5on, crowd – herd
Antonyme (Gegensätzliche Bedeutung)
lucky – unlucky, expensive – cheap
Hypernyme (Oberbegriffe)
mammal – rodent, machine – computer
Hyponyme (Unterbegriffe)
rat – rodent, rodent – mammal
Meronyme (Teil-‐von-‐Beziehung)
tree – forest, board – computer Informa5on Retrieval (SS 2011)
24
WordNet
✦
WordNet ist eine lexikalische Datenbank in Englisch
hgp://wordnet.princeton.edu/
25
GermaNet
✦
GermaNet ist eine lexikalische Datenbank in Deutsch
hgp://www.sfs.uni-‐tuebingen.de/GermaNet/
26
UWN
✦
UWN ist eine mul5-‐linguale lexikalische Wissenbasis
hgp://www.mpi-‐inf.mpg.de/yago-‐naga/uwn/
27
Automa5sches Erkennen von Synonymen
✦
✦
✦
✦
Wenn kein geeigneter Thesaurus verfügbar ist, kann man versuchen, Synonyme automa5sch zu iden5fizieren
Grundlegende Beobachtung hierbei ist, dass Wörter mit ähnlicher Bedeutung in ähnlichem Kontext vorkommen
Definiere den Kontext c(w) als Menge jener Wörter mit denen das Wort w gemeinsam vorkommt (z.B. im selben Dokument)
Betrachte zwei Wörter w und v als Synonyme, wenn die Jaccard-‐Ähnlichkeit ihrer Kontexte über Schwellwert γ liegt
| c(v) ∩ c(w) |
J( c(v), c(w) ) =
≥γ
| c(v) ∪ c(w) |
28
Automa5sches Erkennen von Synonymen
car
tire
insurance
garage
hifi
automobile
d1
1
1
0
0
0
0
d2
1
0
1
0
0
0
d3
1
0
0
1
0
0
d4
1
0
0
0
1
0
d5
0
0
0
0
1
1
d6
0
0
0
1
0
1
J( c(car), c(automobile) )
= 2/3
J( c(car), c(hifi) )
= 2/5
J( c(hifi), c(tire) )
= 1/2
d7
0
0
1
0
0
1
d8
0
1
0
0
0
1
γ = 0.6
Verfahren kann erweitert/verbessert werden z.B. durch
✦
✦
engere Wahl des Kontexts (z.B. gleicher Absatz oder Satz)
✦
Einbeziehung von Worthäufigkeiten
29
Synonyme und Polyseme
Moderne Ansätze zum automa5schen Umgang mit Synonymen und Polysemen migels eines Thesaurus sind
✦
✦
✦
Abbildung von Tokens auf Synsets zur Indexierungszeit
…a loan from the bank… S7618:(depository financial ins5tu5on)
…the bank of the river… S9912:(sloping land)
Erweiterung von Anfragen (query expansion) um Synonyme, Hypernyme und Hyponyme zur Anfragezeit
car insurance ➔
{
car automobile insurance
car motor vehicle insurance
car convertible insurance
30
2.8 Rechtschreibung
✦
✦
Rechtschreibfehler sowie unterschiedliche Schreibweisen in Anfragen und Dokumenten wirken sich nega5v auf Precision und Recall aus britnie spears, britany speers, britnee speers
aple ipod, apple ifone, apple iped
neighbor, neighbour
prolog, prologue
muhammad, muhammed, mohammed
Enthält eine Anfrage ein unbekanntes Wort (z.B. ifone), so kann man versuchen, dies durch ein ähnliches bekanntes Wort zu ersetzen (z.B. iphone)
31
Edi5erdistanz nach Levenshtein
Levenshtein-‐Distanz zwischen Zeichenkegen s1 und s2 ist die minimal benö5gte Anzahl folgender Edi3er-‐Opera3onen zur Umwandlung von s1 in s2
✦
✦
✦
✦
✦
✦
Einfügen eines Zeichens (Insert)
Löschen eines Zeichens (Delete)
Ersetzen eines Zeichens (Replace)
Beispiel: Distanz zwischen ifone und iphone beträgt 2
✦ Ersetze f durch p (d.h. ifone ➔ ipone)
✦ Füge h ein (d.h. ipone ➔ iphone)
Berechnung der Levenshtein-‐Distanz migels dynamischer Programmierung in Zeit-‐ und Platzkomplexität O(|s1| x |s2|)
32
Edi5erdistanz nach Levenshtein
Minimale Anzahl m[i, j] von Edi5er-‐Opera5onen um s1[1..i] in s2[1..j] umzuwandeln wird ermigelt als Minimum von
✦
✦
✦
✦
✦
m[i-‐1, j-‐1] + (s1[i] == s2[j] ? 0 : 1) (Ersetzen von s1[i] wenn nö5g)
m[i, j-‐1] + 1 (Einfügen von s2[j])
m[i-‐1, j] + 1 (Löschen von s1[i])
s2
Beispiel: s1 = car s2 = cure
m[1,1] + 1 (C ➔ C + Ersetze A durch U)
m[2,1] + 1 (CA ➔ C + Füge U an)
m[1,2] + 1 (C ➔ CU + Lösche A)
s1
_
C
U
R
E
0
1
2
3
4
_
0
0
1
2
3
4
C
1
1
0
1
2
3
A
2
2
1
1
2
3
R
3
3
2
2
1
2
33
Rechtschreibekorrektur zur Anfragezeit
Wie findet man zur Anfragezeit zu einem unbekannten Wort ein bekanntes Wort mit minimaler Levenshtein-‐Distanz?
✦
Naïver Ansatz: Berechne Distanz zu allen bekannten Wörtern
✦
Heuris3sche Ansätze zur Beschleunigung dieses Prozesses betrachten z.B. nur bekannte Wörter, welche
✦
✦
✦
den gleichen Anfangsbuchstaben haben
ähnliche Länge haben
✦
viele k-‐Gramme gemeinsam haben
✦
phone3sch ähnlich sind (d.h. ähnlich klingen)
34
k-‐Gramme
✦
✦
✦
Die in einer Zeichenkege s enthaltenen k-‐Gramme sind alle enthaltenen Zeichenkegen s[i..i+(k-‐1)] der Länge k
Beispiel: Die Zeichenkege boarding enthält die 3-‐Gramme
boa, oar, ard, rdi, din, ing
Jaccard-‐Ähnlichkeit zweier Zeichenkegen s1 und s2 basierend auf enthaltenen k-‐Grammen kgrams(s1) und kgrams(s2)
| kgrams(s1 ) ∩ kgrams(s2 ) |
| kgrams(s1 ) ∪ kgrams(s2 ) |
35
Soundex
Abbildung ähnlich klingender Wörter auf kanonische Form durch die schrigweise Anwendung folgender Regeln
✦
✦
✦
✦
✦
✦
✦
Behalte ersten Buchstaben bei
Ersetze A, E, I, O, U, H, W und Y durch die Zahl 0
Ersetze B, F, P und V durch die Zahl 1 Ersetze C, G, J, K, Q, S, X und Z durch die Zahl 2
Ersetze D und T durch die Zahl 3
Ersetze L durch die Zahl 4
✦
Ersetze M und N durch die Zahl 5
✦
Ersetze R durch die Zahl 6
✦
✦
✦
Verschmelze Folgen der gleichen Zahl (z.B. 33311 ➔ 31)
Enierne die Zahl 0 und füge 000 am Ende an
Kanonische Form sind die ersten vier Zeichen Informa5on Retrieval (SS 2011)
36
Soundex
✦
✦
Beispiel: lightening ➔ L0g0t0n0ng ➔ L020t0n0n2
➔ L02030n0n2 ➔ L020305052 ➔ L23552000 ➔ L235
Beispiel: lightning ➔ L0g0tn0ng ➔ L020tn0n2
➔ L0203n0n2 ➔ L02035052 ➔ L23552000 ➔ L235
37
Quellen & Literatur
[1] [2] [3] [4] [5] [6] [7] [8] [9] S. Bügcher, C. L. A. Clarke and G. V. Cormack: Informa)on Retrieval
MIT Press, 2010.
W. B. CroW, D. Metzler and T. Strohman: Search Engines
Addison-‐Wesley, 2010.
G. de Melo and G. Weikum: Towards A Universal WordNet by Learning from Combined Evidence, CIKM 2009.
R. Ferber: Informa)on Retrieval,
dpunkt.verlag, 2003. (Kapitel 3.2)
A. Henrich: Informa)on Retrieval 1 Grundlagen, Modelle und Anwendungen,
Ogo-‐Friedrich-‐Universität Bamberg, 2008. (Kapitel 3)
C. D. Manning, P. Raghavan and H. Schütze: IntroducFon to InformaFon Retrieval, Cambridge University Press, 2008. (Kapitel 2 + 3)
C. Manning und H. Schütze: Founda)ons of Sta)s)cal Natural Language Processing
MIT Press, 2003.
G. A. Miller: WordNet: A Lexical Database for English
Communica5ons of the ACM 38(11):39-‐41, 1995.
M. F. Porter: An algorithm for suffix stripping,
Program 14(3):130-‐137, 1980.
Referenzimplemen5erung: hgp://tartarus.org/~mar5n/PorterStemmer/
38

Information Retrieval (SS 2011) - Natürliche Sprache

Transcrição

Documentos relacionados

kein Eintrag vorhanden

PR(A) = 0,15 + 0,85*(1/1)

MEMOSE. Spezialsuchmaschine für emotional geladene Dokumente

Die Hamburger Schreibprobe

10 Lösungen bei chronischer Müdigkeit - drschindler

Dokument_1.

Viele tz–Wörter

Schnell schlank Die neue, leichte

Bezugsrahmen für die Evaluation von Information Retrieval

Wörterbücher öffnen Welten

4D Wording Optimizer

steyr puch 650 tr