Information Retrieval (SS 2011) - Natürliche Sprache
Transcrição
Information Retrieval (SS 2011) - Natürliche Sprache
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. Natürliche Sprache 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) Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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 Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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 Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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” Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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 Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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 Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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) 2. Natürliche Sprache 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) Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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 Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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) Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 12 Gesetz von Zipf Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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 Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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 Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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 Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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) ✦ Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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 Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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 Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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 Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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} Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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) 2. Natürliche Sprache 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 Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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) 2. Natürliche Sprache 24 WordNet ✦ WordNet ist eine lexikalische Datenbank in Englisch hgp://wordnet.princeton.edu/ Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 25 GermaNet ✦ GermaNet ist eine lexikalische Datenbank in Deutsch hgp://www.sfs.uni-‐tuebingen.de/GermaNet/ Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 26 UWN ✦ UWN ist eine mul5-‐linguale lexikalische Wissenbasis hgp://www.mpi-‐inf.mpg.de/yago-‐naga/uwn/ Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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) | Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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 Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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 ➔ Informa5on Retrieval (SS 2011) { car automobile insurance car motor vehicle insurance car convertible insurance 2. Natürliche Sprache 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) Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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|) Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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) Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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) Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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 ) | Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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) 2. Natürliche Sprache 36 Soundex ✦ ✦ Beispiel: lightening ➔ L0g0t0n0ng ➔ L020t0n0n2 ➔ L02030n0n2 ➔ L020305052 ➔ L23552000 ➔ L235 Beispiel: lightning ➔ L0g0tn0ng ➔ L020tn0n2 ➔ L0203n0n2 ➔ L02035052 ➔ L23552000 ➔ L235 Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 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/ Informa5on Retrieval (SS 2011) 2. Natürliche Sprache 38