Information Retrieval (SS 2011) - IR-Modellekberberi/teaching/... · Informaon#Retrieval#(SS#2011) 3.#IRModelle Rückblick Vielfaltund Vagheit#natürlicher#Sprache Tokenisierungund

3. IR-‐Modelle

Informa1on Retrieval (SS 2011) 3. IR-‐Modelle

Rückblick✦ Vielfalt und Vagheit natürlicher Sprache

✦ Tokenisierung und Normalisierung

✦ Stamm-‐ und Grundformreduk7on

✦ Komposita und Wortgruppen

✦ Synonyme und Polyseme

✦ Rechtschreibekorrektur und Edi7erdistanz nach Levenshtein

2


Mo1va1on

✦ IR-‐Modelle formalisieren den Vorgang gemäß dem ein Benutzer entscheidet, inwiefern ein Dokument zu einem Informa7onsbedürfnis relevant ist

✦ Dabei beantworten sie folgende elementare Fragestellungen✦ Wie werden Dokumente und Anfragen formal repräsen7ert?✦ Welche Dokumente sind zu einer Anfrage wie relevant?

3

All models are wrongbut some are useful

[George Box]


Inhalt

(1) Boolesches Retrieval

(2) Vektorraum-‐Modell

(3) Probabilis1sches IR

(4) Language Models

(5) Latent Seman1c Indexing

4


3.1 Boolesches Retrieval✦ Dokumente werden als Mengen von Termen repräsen1ert

✦ Anfragen werden als Boolesche Ausdrücke bestehend aus Termen und den Operatoren AND, OR und NOT formuliert

✦ Eindeu7ge Seman7k: Dokument erfüllt Anfrage oder nicht

✦ (Immer noch) verbreitet in der Praxis und häufig auch unterstützt von modernen Systemen (z.B. Google und Bing)

5

(george AND clooney) OR (danny AND ocean)


Anfragebearbeitung✦ Paarweises Zusammenführen von Indexlisten

✦ Effiziente Bearbeitung von (george AND clooney) auf nach Dokumenten sor1erten Indexlisten in Zeitkomplexität O(m + n)

6


clooney d4 d7 d8 d12 d20 …george d1 d7 d9 d12 d19 …




6






6






6






6






6






6






6






6






6






6






6




Anfrageop1mierung✦ Anfragen können durch Umformen und Klammern op1miert

werden (vgl. Op1mierung der Join-‐Reihenfolge in RDBMS)

✦ Kommt movie in 1,000, george in 100 und clooney in 10 Dokumenten vor, so gibt es u.a. folgende Op1onen

(movie AND george) AND clooney 1,210

movie AND (george AND clooney) 1,210

george AND (movie AND clooney) 1,120

mit jeweils maximaler Anzahl von Vergleichsopera1onen

7


Erweiterung & Kri1k✦ Boolesches Retrieval kann erweitert werden durch

✦ Zusätzliche Operatoren basierend auf Term-‐Posi1onen (z.B. NEAR)✦ Eliminieren von Stoppwörtern (z.B. a, the, this, of )✦ Reduk1on von Wörtern auf ihre Stammformen (Stemming)

(z.B. criminal → crimin, criminals → crimin)

✦ Keine Rangfolge (ranking) der Treffer

✦ Term-‐Häufigkeit und Term-‐Reihenfolge spielen keine Rolle

8


3.2 Vektorraum-‐Modell✦ Modell liefert Ergebnisse in einer Rangfolge (ranked retrieval)

✦ Dokumente und Anfragen werden als Mul7mengen von Termen (bag of words) betrachtet

✦ Dokumente und Anfragen werden auf Vektoren im einem hochdimensionalen Vektorraum abgebildet

✦ Eine Dimension pro Term in der Dokumentensammlung

✦ Wert einer Vektorkomponente gibt Gewicht des Terms an und wird, in der Regel, miiels einer Variante von \.idf bes1mmt

9


j.idf✦ Intui1on: Ein Term t

✦ soll mehr Gewicht haben, wenn er häufig in d vorkommt✦ soll weniger Gewicht haben, wenn er in vielen Dokumenten

vorkommt und damit wenig trennscharf (discrimina6ve) ist

✦ Term-‐Häufigkeit (term frequency) als Anzahl der Vorkommen von Term t im Dokument d

✦ Inverse Dokumenten-‐Häufigkeit (inverse document frequency) von Term t in den N Dokumenten der Kollek1on

10


j.idf✦ Term-‐Häufigkeit (j) und inverse Dokumenten-‐Häufigkeit (idf)

werden in einem Vektor V(d) für Dokument d kombiniert als

✦ Zahlreiche Varianten von j.idf exis1eren, z.B. mit✦ logarithmisch transformierter Term-‐Häufigkeit: 1 + log 2t,d

✦ rela1ver anstai absoluter Term-‐Häufigkeit: 2t,d / Ld✦ max-‐normalisierter Term-‐Häufigkeit: 2t,d / max-‐2d

✦ Manche weniger heuris7schen Modelle (z.B. Unigram Language Model) lassen sich in „\.idf-‐Variante“ umformen

11


Distanzen von Vektoren✦ Wie bringt man Dokumente in Rangfolge zu Anfrage q?

✦ Idee: Ordne Dokumente nach ihrer Nähe oder Distanz zu q

✦ Manha_an (L1) Distanz

✦ Euklidische (L2) Distanz

12

george

cloo

ney

V(q)

V(d1)

V(d2)


Kosinus-‐Ähnlichkeit✦ Manhaian Distanz und Euklidische Distanz ungeeignet, da sie

von der Länge der Vektoren (und damit der Länge der Dokumente) abhängig sind

✦ Kosinus-‐Ähnlichkeit (cosine similarity) als Kosinus des Winkels zwischen den Vektoren ist nur von ihrer Richtung abhängig

george

cloo

ney

V(q)

V(d1)

V(d2)

d1 d2 d3 d4 d5

car 10 2 5 2 0auto 2 0 0 0 5

insurance 10 0 5 0 5has 1 2 2 1 1


Beispiel zu Vektorraum-‐Modell

14

dft4235

d1 d2 d3 d4 d5

car 10 2 5 2 0auto 2 0 0 0 5

insurance 10 0 5 0 5has 1 2 2 1 1



14

dft4235

idft0.010.400.220.00

d1 d2 d3 d4 d5

car 10 2 5 2 0auto 2 0 0 0 5

insurance 10 0 5 0 5has 1 2 2 1 1



14

dft4235

idft0.010.400.220.00

d1 d2 d3 d4 d5

car 10 2 5 2 0auto 2 0 0 0 5

insurance 10 0 5 0 5has 1 2 2 1 1

V(d1) V(d2) V(d3) V(d4) V(d5)car 0.10 0.02 0.05 0.02 0.00

auto 0.80 0.00 0.00 0.00 2.00insurance 2.20 0.00 1.10 0.00 1.10

has 0.00 0.00 0.00 0.00 0.00



14

dft4235

idft0.010.400.220.00

d1 d2 d3 d4 d5

car 10 2 5 2 0auto 2 0 0 0 5

insurance 10 0 5 0 5has 1 2 2 1 1

V(d1) V(d2) V(d3) V(d4) V(d5)car 0.10 0.02 0.05 0.02 0.00

auto 0.80 0.00 0.00 0.00 2.00insurance 2.20 0.00 1.10 0.00 1.10

has 0.00 0.00 0.00 0.00 0.00



14

sim(q,d)d5 0.96d1 0.91d3 0.71d4 0.00d2 0.00

✦ Für die Anfrage auto insurance erhält man miiels Kosinus-‐Ähnlichkeitals Rangfolge


Anfragebearbeitung✦ Effiziente Anfragebearbeitung dank folgender Beobachtungen

✦ Kosinus-‐Ähnlichkeit lässt sich als Skalarprodukt von L2-‐normalisierten Vektoren darstellen

✦ Vektoren können bereits L2-‐normalisiert indexiert werden✦ Es reicht aus, nur Terme aus der Anfrage zu betrachten

15

sim(q, d) = v(q) · v(d)

sim(q, d) =�

t∈q

v(q)t v(d)t

v(d)t =V(d)t|V(d)|

=V(d)t��t V(d)t

2


Erweiterungen & Kri1k✦ Rocchios Algorithmus verwendet Feedback des Benutzers

über relevante und nicht-‐relevante Dokumente (relevance feedback), um den Anfragevektor anzupassen

✦ Varianten des Vektorraum-‐Modells finden sich in vielen exis7erenden Systemen (z.B. Apache Lucene) und liefern gute Ergebnisse auf verschiedensten Dokumentensammlungen

✦ Häufiger Kri1kpunkt am Vektorraum-‐Modell ist seine mangelnde theore7sche Fundierung – jedoch lassen sich einige der vorgeblich fundierteren Ansätze darauf abbilden

16


3.3 Probabilis7sches IR✦ Boolesches Retrieval und Vektorraum-‐Modell bes1mmen

heuris7sch ob/wie relevant ein Dokument d zur Anfrage q ist

✦ Wahrscheinlichkeitstheorie (probability theory) bietet ein theore1sches Fundament, um über die Wahrscheinlichkeiten von Ereignissen zu reden und damit umzugehen

✦ Probabilis7sches IR bes1mmt die Wahrscheinlichkeit des Ereignis “Dokument d ist zur Anfrage q relevant”

17


Wahrscheinlichkeitsrechnung✦ Gemeinsame Wahrscheinlichkeit der zwei Ereignisse A und B

✦ Bedingte Wahrscheinlichkeit für Ereignis A gegeben Ereignis B

✦ Für gemeinsame Wahrscheinlichkeit (joint probability) und bedingte Wahrscheinlichkeiten (condi6onal probability) gilt

18

P(A ∩ B) = P(A | B)P(B) = P(B |A)P(A) = P(B ∩A)

P(A ∩ B) = P(B ∩A)

P(A | B)


Wahrscheinlichkeitsrechnung✦ Sind zwei Ereignisse A und B voneinander unabhängig gilt

✦ Satz von Bayes zum Umkehren bedingter Wahrscheinlichkeiten

19

P(A | B) = P(A)

P(A ∩ B) = P(A)P(B)

P(B |A) = P(B)

P(A | B) =P(B |A)P(A)

P(B)


Probabilis1c Ranking Principle (PRP)✦ Probabilis1c Ranking Principle (PRP) schlägt vor, Dokumente in

absteigender Rangfolge ihrer Wahrscheinlichkeit zur Anfrage relevant zu sein zu ordnen

✦ Man kann zeigen, dass das PRP zu op7maler Precision führt, wenn man annimmt dass die Wahrscheinlichkeiten genau bekannt und unabhängig voneinander sind

✦ Beide Annahmen sind in der Realität fragwürdig z.B. aufgrund von Duplikaten in der Dokumentensammlung

20

P(R = 1 | d, q)


Binary Independence Model✦ Binary Independence Model (BIM) betrachtet Dokumente und

Anfragen als Mengen von Termen, d.h. es wird –binär– festgehalten, ob ein Term vorhanden ist oder nicht

✦ Eine grundlegende Annahme des BIM ist, dass Terme unabhängig voneinander in Dokumenten vorkommen

✦ Rangfolge der Dokumente gemäß des PRP nach ihrer Relevanz-‐Wahrscheinlichkeit P(R = 1 | d, q), für die gilt:

21

P(R = 1 | d, q) + P(R = 0 | d, q) = 1


Binary Independence Model✦ Die gleiche Rangfolge der Dokumente erhält man, wenn man

stai Wahrscheinlichkeiten deren Quoten (odds) betrachtet

✦ Durch Anwendung des Satz von Bayes erhält man

22

O(R | d, q) =P(R = 1 | d, q)

P(R = 0 | d, q)

O(R | d, q) =P(R = 1 | q)

P(R = 0 | q)· P(d | R = 1, q)

P(d | R = 0, q)

Kann ignoriert werden,da konstant für Anfrage q


Binary Independence Model✦ Die gleiche Rangfolge der Dokumente erhält man, wenn man

stai Wahrscheinlichkeiten deren Quoten (odds) betrachtet

✦ Durch Anwendung des Satz von Bayes erhält man

22

O(R | d, q) =P(R = 1 | d, q)

P(R = 0 | d, q)

O(R | d, q) =P(R = 1 | q)

P(R = 0 | q)· P(d | R = 1, q)

P(d | R = 0, q)


Binary Independence Model✦ Unter der Annahme unabhängiger Termvorkommen

✦ Unter der Annahme, dass nur Anfrageterme eine Rolle spielen

✦ Auseilung in vorhandene und fehlende Anfrageterme

23

P(d | R = 1, q)

P(d | R = 0, q)=

�

t∈V

P(t | R = 1, q)

P(t | R = 0, q)

P(d | R = 1, q)

P(d | R = 0, q)≈

�

t∈q

P(t | R = 1, q)

P(t | R = 0, q)

P(d | R = 1, q)

P(d | R = 0, q)≈

�

t∈qt∈d

P(t | R = 1, q)

P(t | R = 0, q)·�

t∈qt �∈d

P(t | R = 1, q)

P(t | R = 0, q)


Binary Independence Model✦ Definiere pt und ut als die Wahrscheinlichkeit, dass Term t in

einem relevanten bzw. nicht-‐relevanten Dokument vorkommt

✦ Durch einfaches Umformen erhält man

24

P(d | R = 1, q)

P(d | R = 0, q)≈

�

t∈qt∈d

pt

ut·�

t∈qt �∈d

1− pt

1− ut

P(d | R = 1, q)

P(d | R = 0, q)≈

�

t∈qt∈d

pt(1− ut)

ut(1− pt)·�

t∈q

1− pt

1− ut

Kann ignoriert werden,da konstant für Anfrage q


Binary Independence Model✦ Definiere pt und ut als die Wahrscheinlichkeit, dass Term t in

einem relevanten bzw. nicht-‐relevanten Dokument vorkommt

✦ Durch einfaches Umformen erhält man

24

P(d | R = 1, q)

P(d | R = 0, q)≈

�

t∈qt∈d

pt

ut·�

t∈qt �∈d

1− pt

1− ut

P(d | R = 1, q)

P(d | R = 0, q)≈

�

t∈qt∈d

pt(1− ut)

ut(1− pt)·�

t∈q

1− pt

1− ut


Binary Independence Model✦ Beim Mul1plizieren kleiner Wahrscheinlichkeiten ist es, um

numerische Ungenauigkeit zu vermeiden, os empfehlenswert staidessen die Summe ihrer Logarithmen zu betrachten

✦ Der sogenannte Retrieval-‐Status-‐Wert (retrieval status value) liefert die gleiche Rangfolge und ist definiert als

25

RSVd = log�

t∈qt∈d

pt(1− ut)

ut(1− pt)=

�

t∈qt∈d

logpt(1− ut)

ut(1− pt)


Schätzen der Wahrscheinlichkeiten pt und ut✦ Unter der Annahme, dass die Zahl der relevanten Dokumente

im Vergleich zur Dokumentensammlung klein ist, schätzt man

✦ Mangels Wissen über die Menge der zur Anfrage relevanten Dokumente schätzt man

✦ Damit entspricht das BIM folgender “\.idf-‐Variante”

26

ut =dftN

pt = 1− pt = 0.5

RSVd =�

t∈qt∈d

log(1− ut)

ut=

�

t∈qt∈d

logN− dft

dft≈

�

t∈qt∈d

logN

dft


Erweiterungen & Kri1k✦ Feedback des Benutzers über relevante und nicht-‐relevante

Dokumente (relevance feedback) kann bei Schätzung von pt und ut einfließen und direkt vom BIM verwendet werden

✦ BIM liefert tendenziell gute Ergebnisse auf Sammlungen von Dokumenten homogener Länge, überzeugt jedoch nicht bei heterogener Dokumentenlänge (z.B. World Wide Web)

✦ Theore7sch fundierter Ansatz, welcher jedoch einige in der Realität fragwürdige Annahmen triu (z.B. Unabhängigkeit)

27


Okapi BM25✦ Okapi BM25 ist ein probabilis1sches IR-‐Modell, welches auf

dem BIM auvaut, jedoch Term-‐Häufigkeiten berücksich1gt

✦ Für die Verteilung der Term-‐Häufigkeiten in relevanten und nicht-‐relevanten Dokumenten (analog zu pt und ut) wird angenommen, dass sie Poisson-‐verteilt sind

28

P(tft,d = k) =λk

k!e−λ


Okapi BM25

✦ Parameter k1 kontrolliert den Einfluss der Term-‐Häufigkeiten ✦ für k1 = 0.0 erhält man ein binäres Modell ähnlich dem BIM✦ in der Praxis liefert k1 = 1.2 gute Ergebnisse

✦ Parameter b kontrolliert Normalisierung der Term-‐Häufigkeiten anhand durchschniilicher Dokumentenlänge Lave

✦ für b = 0.0 spielt die Länge des Dokumentes keine Rolle✦ in der Praxis liefert b = 0.75 gute Ergebnisse

29

RSVd =�

t∈q

(k1 + 1) tft,dk1 ((1− b) + b (Ld/Lave)) + tft,d

· logN− dft + 0.5

dft + 0.5

~ \


Okapi BM25




29

RSVd =�

t∈q



dft + 0.5

~ \ ~ idf


Okapi BM25




29

RSVd =�

t∈q



dft + 0.5


Erweiterungen & Kri1k✦ Okapi BM25F (F steht für fields) als eine Erweiterung zur

separaten Betrachtung und Gewichtung unterschiedlicher Bereiche (fields) eines Dokumentes z.B. Titel (6tle), Inhalt (body) und Verweistexte (anchor texts)

✦ Okapi BM25 liefert sehr gute Ergebnisse auf verschiedensten Dokumentensammlungen und gilt als “Stand der Technik”

✦ Theore7sch fundierter Ansatz, welcher jedoch einige in der Realität fragwürdige Annahmen triu (z.B. Unabhängigkeit)

30


3.4 Language Models✦ Probabilis1c Language Models beschreiben die Generierung

einer (formalen) Sprache (z.B. Folge von Termen)

✦ Anwendungsbeispiele im Umgang mit natürlicher Sprache✦ Spracherkennung: Wähle sinnvolleren aus phone1sch ähnlichen

Sätzen (z.B. “get up at 8 o’clock” und “get a potato clock”)✦ Maschinelles Übersetzen: Wähle sinnvollere aus möglichen

Übersetzungen (z.B. “logic closing” und “logical reasoning”)✦ Informa7on Retrieval: Ordne Dokumente danach wie sinnvoll sie

für eine vorliegende Anfrage erscheinen

31

s t0.1

0.9

dog : 0.3 / cat : 0.3 / bird : 0.4 P(dog) = 0.3× 0.1 = 0.03

P(dog cat) = 0.3× 0.9× 0.3× 0.1 = 0.0081

P(cat bird) = 0.3× 0.9× 0.4× 0.1 = 0.0108


Query-‐Likelihood✦ Intui1on: Benutzer hat Vorstellung vom idealen Dokument d

und formuliert eine Anfrage q um genau dieses zu finden

✦ Modell beschreibt wie Benutzer eine Anfrage q anhand von Dokument d formuliert (z.B. zufällige Auswahl von Termen)

✦ Als Vorberechnung wird für jedes Dokument solch ein generierendes Modell u.a. anhand seines Inhalts geschätzt

✦ Zur Anfragezeit präsen1ert man Dokumente in der Reihenfolge von P(q|d) – der Wahrscheinlichkeit dass die Anfrage q anhand vom jeweiligen Dokument formuliert wurde

32


Unigram Language Models✦ Dokumente und Anfragen sind Mul7mengen von Termen

✦ Benutzer formuliert Anfrage durch Ziehen (mit Zurücklegen) einzelner Terme (Unigramme) aus dem Dokument

✦ Mögliche Erweiterung durch a-‐priori Wahrscheinlichkeit P(d) für Dokument d, die z.B. von dessen Popularität abhängt

33

P(q | d) =Lq!�

t∈q tft,q!

�

t∈q

tft,dLd

∝�

t∈q

tft,dLd


Smoothing✦ Bisher beschrieber Ansatz hat konjunk7ve Seman7k, d.h., nur

für Dokumente die alle Anfrageterme enthalten gilt P(q|d) > 0

✦ Smoothing (GläFen) eliminiert Nullwahrscheinlichkeiten durch Einbeziehen von Sta1s1ken über die Dokumentenkollek1on

✦ Jelinek-‐Mercer Smoothing (Lineare Interpola1on): Benutzer zieht Term mit Wahrscheinlichkeit α aus Dokument und mit Wahrscheinlichkeit (1 -‐ α) aus Dokumentenkollek1on

34

P(t | d) = αtft,dLd

+ (1− α)tft,DLD


Smoothing✦ Dirichlet Smoothing: Benutzer erweitert Dokument zuerst um

κ zufällig aus der Dokumentenkollek1on gezogene Terme

✦ Unigram Language Model mit Jelinek-‐Mercer Smoothing liefert Ergebnisse in gleicher Rangfolge wie folgende “\.idf-‐Variante”

35

sim(q, d) =�

t∈q

log

�1+

α

1− α

tft,dLd

LDtft,D

�

P(t | d) =tft,d + κ tft,D

LD

Ld + κ





35

~ \

sim(q, d) =�

t∈q

log

�1+

α

1− α

tft,dLd

LDtft,D

�


LD

Ld + κ





35

~ \ ~ idf

sim(q, d) =�

t∈q

log

�1+

α

1− α

tft,dLd

LDtft,D

�


LD

Ld + κ

d1 d2 d3 d4 d5

car 10 2 5 2 0auto 2 0 0 0 5

insurance 10 0 5 0 5has 1 2 2 1 1

P(t | d1) P(t | d2) P(t | d3) P(t | d4) P(t | d5) P(t |D)car 10 / 23 1 / 2 5 / 12 2 / 3 0 19 / 53

auto 2 / 23 0 0 0 5 / 11 7 / 53insurance 10 / 23 0 5 / 12 0 5 / 11 20 / 53

has 1 / 23 1 / 2 1 / 6 1 / 3 1/11 7 / 53


Beispiel Unigram LM mit JM Smoothing

36

P(q | d)d5 0.15d1 0.04d3 0.01d4 0.00d2 0.00

d1 d2 d3 d4 d5

car 10 2 5 2 0auto 2 0 0 0 5

insurance 10 0 5 0 5has 1 2 2 1 1

P(t | d1) P(t | d2) P(t | d3) P(t | d4) P(t | d5) P(t |D)car 10 / 23 1 / 2 5 / 12 2 / 3 0 19 / 53

auto 2 / 23 0 0 0 5 / 11 7 / 53insurance 10 / 23 0 5 / 12 0 5 / 11 20 / 53

has 1 / 23 1 / 2 1 / 6 1 / 3 1/11 7 / 53


Beispiel Unigram LM mit JM Smoothing

✦ Für die Anfrage auto insurance und α = 0.7 erhält manals Rangfolge

36

P(q | d)d5 0.15d1 0.04d3 0.01d4 0.00d2 0.00


n-‐Gram Language Models✦ Term-‐Reihenfolge wird ignoriert in Unigram Language Models

➔ Anfragen paris hilton und hilton paris nicht unterscheidbar

✦ n-‐Gramm ist eine Folge von n Termen

✦ Dokumente und Anfragen betrachtet als Folgen von Termen

✦ Benutzer formuliert seine Anfrage durch zufälliges Ziehen von Termen unter Berücksich1gung der bis zu (n-‐1) zuvor bereits gezogenen Terme

37

the hilton paris close to the eiffel tower

1-Gramme: 〈the〉〈hilton〉〈paris〉 …2-Gramme: 〈the, hilton〉〈hilton, paris〉 …3-Gramme: 〈the, hilton, paris〉〈hilton, paris, close〉 …


n-‐Gram Language Models✦ Für n = 3 erhalten wir folgendes Trigram Language Model

✦ Smoothing wird umso wich1ger je höher die Ordnung (d.h. der Wert von n) des verwendeten Language Models ist

✦ Language Models höherer Ordnung (d.h. n > 1) sind gängig für Spracherkennung und maschinelles Übersetzen; im Informa1on Retrieval werden sie meist nicht verwendet

38

P(�q1 . . . qm� | d) = P(q1)P(q2 | q1)m�

i=3

P(qi | qi−2 qi−1)


Transla1on Language Models✦ Umgang mit Synonymen (z.B. automobile und car) sowie

seman7sch ähnlichen Termen (z.B. tiger und lion)

✦ Wahrscheinlichkeit P(t|v) dass Term v aus Dokument in Anfrageterm t übersetzt wird geschätzt anhand von

✦ Thesaurus (z.B. WordNet)✦ Sta1s1ken über gemeinsam vorkommende Terme

(z.B. tiger und lion kommen beide os mit zoo und cat vor)✦ Query logs (d.h. von Benutzern formulierte Anfragen)

39

P(q | d) =�

t∈q

�

v∈d

P(t | v)P(v | d)


Erweiterungen & Kri1k✦ Zahlreiche Erweiterungen von Language Models fürs IR z.B.

✦ mit term-‐spezifischem Smoothing (d.h. wir haben αt und κt)✦ personalisiert durch Benutzerverhalten und -‐kontext (abgeleitet

aus Query-‐ oder Click-‐Logs)✦ cross-‐lingual um mit Anfrage in einer Sprache (z.B. Deutsch)

Dokumente in einer anderen Sprache (z.B. Englisch) zu finden✦ für Informa7onsbedürfnisse mit Zeitbezug durch Berücksich1gung

von Zeitreferenzen in Dokumenten (z.B. im Mai 2011)

✦ Rich1ge Wahl der Parameter ist essen1ell aber schwierig

✦ Unabhängigkeitsannahmen sind in der Realität fragwürdig

40


3.5 Latent Seman7c Indexing✦ Bisher besprochene IR-‐Modelle sind term-‐orien7ert und

betrachten bekannte Terme unabhängig voneinander

✦ Vektorraum-‐Modell z.B. betrachtet einen m-‐dimensionalen Vektorraum mit einer Dimension pro bekanntem Term

✦ Synonyme (z.B. car und automobile) und Polyseme (z.B. bank) führen zu einer Verringerung der Ergebnisgüte

✦ Latent Seman7c Indexing bildet Dokumente und Anfragen in einen k-‐dimensionalen Vektorraum (k << n) ab, dessen Dimensionen verborgenen (latent) Konzepten entsprechen

41


Lineare Unabhängigkeit und Rang einer Matrix✦ Defini1on: Die Vektoren v1 … vn sind linear unabhängig, wenn

sich kein vi als Linearkombina7on der anderen Vektoren darstellen lässt

✦ Defini1on: Der Rang rank(C) einer m x n Matrix C ist die maximale Anzahl ihrer linear unabhängigen Zeilen-‐ oder Spaltenvektoren

✦ Defini1on: Eine n x n Matrix C heisst Diagonalmatrix, wenn nur für i = j gilt Cij ≠ 0

42


Eigenvektoren und Eigenwerte✦ Defini1on: Gilt für eine reelle m x m Matrix C, einen Wert λ

und einen m x 1 Vektor x

so ist x ein (rechter) Eigenvektor und λ ein Eigenwert von C

✦ Intui1on: Eigenvektoren sind die Vektoren, deren Richtung bei der durch C beschriebenen Transforma1on erhalten bleibt

43

Cx = λ x


Beispiel Eigenvektoren und Eigenwerte✦ Die Matrix C beschreibt eine affine Transforma7on x → C x

✦ Eigenwert λ1 = 3.62 mit Eigenvektor

✦ Eigenwert λ2 = 1.38 mit Eigenvektor

44

C =

�2 11 3

�

IRDM WS 2009 4-70

Illustration of Eigenvectors

Matrix2 11 3

A

describesaffine transformationx Ax

Eigenvectorx1 = (0.52 0.85)T

for Eigenvalue 1=3.62

Eigenvectorx2 = (0.85 -0.52)T

for Eigenvalue 2=1.38

�0.62 1.00

�T

�−1.62 1.00

�T


Singulärwertzerlegung✦ Theorem: Für jede reelle m x n Matrix C mit Rang r gibt es eine

Singulärwertzerlegung (singular value decomposi6on) der Form

mit den Faktoren✦ U als eine m x r Matrix bestehend aus den Eigenvektoren

der Matrix CCT ✦ Σ als eine r x r Diagonalmatrix mit den Singulärwerten σi

der Matrix C auf der Diagonalen✦ V als eine n x r Matrix bestehend aus den Eigenvektoren

der Matrix CTC

✦ Singulärwertzerlegung (SVD) ist eindeu7g unter Voraussetzung dass Singulärwerte σi in Σ absteigend nach Größe geordnet sind

45

C = UΣVT

�3.00 0.00 1.000.00 2.00 3.00

�

�0.52 −0.850.85 0.53

�

�3.85 0.000.00 2.85

�

�0.41 0.44 0.80−0.89 0.37 0.25

�


Singulärwertzerlegung

46

=Cm

n

Um

r

ΣX

r

r V TX

r

n


Singulärwertzerlegung zur Approxima1on✦ Theorem: Für die m x n Matrix C mit Rang r sei Ck definiert als

mit den Faktoren✦ Σk als k x k Diagonalmatrix der k größten Singulärwerte von C✦ Uk als m x k Matrix der entsprechenden Eigenvektoren aus U✦ Vk als k x n Matrix der entsprechenden Eigenvektoren aus V

Unter allen m x n Matrizen mit einem Rang von höchstens k minimiert Ck die Frobenius-‐Norm

47

Ck = Uk Σk VkT

�C− Ck�F =

��m�

i=1

n�

j=1

�Cij − Ckij

�2

�0.41 0.44 0.80

�

�3.85

�

�0.520.85

�

�0.82 0.88 1.601.34 1.44 2.61

�


Singulärwertzerlegung zur Approxima1on

48

=Ckm

n

m

k

Uk X

k

k ΣkX

kn

Vk T


Latent Seman1c Indexing✦ Ausgangspunkt ist eine m x n Term-‐Dokumenten-‐Matrix C,

deren Komponente Cij das Gewicht (z.B. bes1mmtmiiels j.idf) des i-‐ten Terms im j-‐ten Dokument angibt

✦ Latent Seman1c Indexing (LSI) wendet SVD auf die Matrix C an und bes1mmt eine Approxima1on Ck vom Rang k als

✦ Anfrage q im m-‐dimensionalen Term-‐Vektorraum wird in k-‐dimensionalen Konzept-‐Vektorraum abgebildet als

und dort mit den k-‐dimensionalen Abbildungen der Dokumente verglichen (z.B. miiels Kosinus-‐Ähnlichkeit)

49

Ck = Uk Σk VkT

qk = Σk−1 Uk

T q


Latent Seman1c Indexing✦ Term-‐Dokument Matrix C

✦ Term-‐Term Matrix CCT Dokument-‐Dokument-‐Matrix CTC

50

10 2 5 2 02 0 0 0 510 0 5 0 51 2 2 1 1

d1 d2 d3 d4 d5

carauto

insurancehas

133 20 125 2620 29 45 7125 45 150 2526 7 25 11

205 22 102 21 6122 8 14 6 2102 14 54 12 2721 6 12 5 161 2 27 1 51


Beispiel Latent Seman1c Indexing

51

C =

10 2 5 2 02 0 0 0 510 0 5 0 51 2 2 1 1

Term-‐Dokument (m x n)



51

C =

10 2 5 2 02 0 0 0 510 0 5 0 51 2 2 1 1


U =

0.66 0.58 0.07 −0.480.18 −0.73 0.26 −0.600.72 −0.35 −0.30 0.520.13 0.05 0.91 0.38

Term-‐Konzept (m x r)



51

C =

10 2 5 2 02 0 0 0 510 0 5 0 51 2 2 1 1


U =

0.66 0.58 0.07 −0.480.18 −0.73 0.26 −0.600.72 −0.35 −0.30 0.520.13 0.05 0.91 0.38


Σ =

16.75 0 0 00 5.85 0 00 0 2.59 00 0 0 1.21

Konzept-‐Konzept (r x r)



51

C =

10 2 5 2 02 0 0 0 510 0 5 0 51 2 2 1 1


U =

0.66 0.58 0.07 −0.480.18 −0.73 0.26 −0.600.72 −0.35 −0.30 0.520.13 0.05 0.91 0.38


Σ =

16.75 0 0 00 5.85 0 00 0 2.59 00 0 0 1.21

Konzept-‐Konzept (r x r)

VT =

0.85 0.09 0.43 0.09 0.280.15 0.21 0.21 0.21 −0.92−0.34 0.76 0.26 0.41 0.27−0.33 −0.16 0.80 −0.47 −0.01

Konzept-‐Dokument (r x n)



52



52

Σ2 =

�16.75 00 5.85

�Konzept-‐Konzept (k x k)



52

U2 =

0.66 0.580.18 −0.730.72 −0.350.13 0.05

Term-‐Konzept (m x k)

Σ2 =

�16.75 00 5.85




52

U2 =

0.66 0.580.18 −0.730.72 −0.350.13 0.05


Σ2 =

�16.75 00 5.85


V2T =

�0.85 0.09 0.43 0.09 0.280.15 0.21 0.21 0.21 −0.92

�Konzept-‐Dokument (k x n)



52

C2 =

9.91 1.71 5.47 1.71 −0.031.92 −0.63 0.40 −0.63 4.779.94 0.66 4.76 0.66 5.261.90 0.26 1.00 0.26 0.34


U2 =

0.66 0.580.18 −0.730.72 −0.350.13 0.05


Σ2 =

�16.75 00 5.85


V2T =

�0.85 0.09 0.43 0.09 0.280.15 0.21 0.21 0.21 −0.92

�Konzept-‐Dokument (k x n)


Beispiel Latent Seman1c Indexing✦ Die Anfrage auto insurance wird abgebildet als

53

q2 =

�0.05−0.18

�= Σ2

−1 U2T

0.001.001.000.00

sim(q,d)d5 1.00d1 0.10d3 -0.18d2 -0.78d4 -0.78

✦ Bei Verwendung derKosinus-‐Ähnlichkeit erhält man die Rangfolge


Erweiterungen & Kri1k✦ Probabilis7c Latent Seman7c Indexing (pLSI) ist ein

verwandter probabilis1scher Ansatz, welcher jedoch auf nicht-‐nega7ver Matrixzerlegung (anstelle von SVD) basiert

✦ Latent Seman1c Indexing liefert tendenziell gute Ergebnisse auf homogenen Dokumentensammlungen (z.B. TREC); auf heterogenen (z.B. World Wide Web) überzeugt es nicht

✦ In der Praxis ist die Berechnung der Singulärwertzerlegung sehr rechenintensiv und die Wahl des Parameters k schwierig

✦ Theore7sch fundierter algebraischer Ansatz, der jedoch aufgrund seiner Einschränkungen wenig Anwendung findet

54


Zusammenfassung✦ IR-‐Modelle bieten formale Repräsenta7on von Anfragen und

Dokumenten und bes1mmen, welche Dokumente zu einer Anfrage in welcher Reihenfolge zurückgeliefert werden

✦ In der Praxis wird häufig eine Kombina7on von Booleschem Retrieval und einem weiteren IR-‐Modell zur Bes1mmung der Rangfolge (z.B. Okapi BM25) verwendet

Beispiel: Eine Anfrage wie george AND clooney AND NOT friends wird zuerst als Boolesche Anfrage interpre1ert; die Rangfolge der Treffer wird dann miiels Okapi BM25 für die Anfrage george clooney bes1mmt

55


Quellen & Literatur[1] K. Berberich, S. Bedathur, O. Alonso, G. Weikum: A Language Modeling Approach for Temporal Informa6on Needs, ECIR 2010.[2] W. B. Cros, D. Metzler and T. Strohman: Search Engines Informa6on Retrieval in Prac6ce Addison Wesley, 2010. (Kapitel 7)[3] A. Henrich: Informa6on Retrieval 1 Grundlagen, Modelle und Anwendungen, Oio-‐Friedrich-‐Universität Bamberg, 2008. (Kapitel 4 + 5 + 7)[4] T. Hoffmann: Probabilis6c Seman6c Indexing, SIGIR 1999[5] D. Hiemstra: Using Language Models for Informa6on Retrieval, Disserta1on, 2001[6] J. Luxenburger, S. Elbassuoni, G. Weikum: Matching Task Profiles and User Needs in Personalized Web Search, CIKM 2009.[7] C. D. Manning, P. Raghavan and H. Schütze: Introduc_on to Informa_on Retrieval, Cambridge University Press, 2008. (Kapitel 6 + 11 + 12 + 18)[8] S. E. Robertson, H. Zaragoza and M. J. Taylor: Simple BM25 extension to mul6ple weighted fields, CIKM 2004[9] C. Zhai and J. Lafferty: A Study of Smoothing Methods for Language Models Applied to Informa6on Retrieval, TOIS 22(2):179-‐214, 2004.[10] C. Zhai: Sta6s6cal Language Models for Informa6on Retrieval A Cri6cal Review,

Founda1ons and Trends in Informa1on Retrieval 2(3):137-‐213, 2008.

56

Documents

Information Retrieval (SS 2011) - IR-Modellekberberi/teaching/... · Informaon#Retrieval#(SS#2011) 3.#IRModelle Rückblick Vielfaltund Vagheit#natürlicher#Sprache Tokenisierungund