12.06.2002 Niko Zenker 1
Besondere Aspekte in Multimedia-Datenbanken
Methoden zur iterativen Anfrageverfeinerung (Relevanz Feedback)
12.06.2002 Niko Zenker 2
GliederungI. MotivationII. Methoden zur
AnfrageverfeinerungIII. Auswertungen der
Verfeinerungs-mechanismenIV. Zusammenfassung
12.06.2002 Niko Zenker 3
Motivation keine genauen Kenntnisse über den
Aufbau der DB und Retrieval-Umgebung Anfragen beruhen auf dem Prinzip
„Glück“ Verfeinerungen können per Hand
realisiert werden durch Einführung von Relevanz-Feedback
Methoden wird dieser Prozess teilautomatisiert
12.06.2002 Niko Zenker 4
Grundidee Auswählen von wichtigen Termen
oder Ausdrücken, die an bestimmte vorherige Dokumente gebunden sind
Dokumente, die der Benutzer vorher schon nicht sehen wollte, scheinen auch nicht von Interesse zu sein
Ziel: gute Ergebnisse bei vagen Anfrangen
12.06.2002 Niko Zenker 5
Information RetrievalAnfrage Dokumente
Verarbeitung Verarbeitung
Anfrage-darstellung
Dokument-darstellung
Verlgeich (Ähnlichkeitsberechnun
g)Ergebnisdokumente
Relevanzbewertung und Feedback
12.06.2002 Niko Zenker 6
Vektor-Modell Anfragen werden mittels Vektor an
die entspr. Daten gestellt mit und
Relevanz Feedback Methode(n) generiert neuen Anfragevektor
),...,,( 21 in qqqQ
Ni 10 iq
),...,,( 21 iqqqQ
12.06.2002 Niko Zenker 7
AnfrageverfeinerungVektor Abgleich Ide dec-hi(Vector Adjustment)
Fügt die Gewichte der Terme, der Dokumente direkt zu den Anfragetermen hinzu. Benutzt alle relevanten, aber nur die höchst unrelevanten zurückgelieferten Terme.
relvantall
tnonrelevanone
iioldnew DDQQ
12.06.2002 Niko Zenker 8
Anfrageverfeinerung (II)Vektor Abgleich Ide regular(Vector Adjustment)
Fügt die aktuellen Gewichte der Terme, der Dokumente direkt zu den Anfragetermen hinzu. Benutzt alle relevanten, und alle unrelevanten zurückgelieferten Terme.
relvantall
tnonrelevanall
iioldnew DDQQ
12.06.2002 Niko Zenker 9
Anfrageverfeinerung (III)Vektor Abgleich Standard nach Rocchio(Vector Adjustment)
Reduziert die Termgewichte durch Division mit der Anzahl der entsprechenden Dokumente.
1
1 2 21
docreln
docnonreln
iioldnew n
DnDQQ
12.06.2002 Niko Zenker 10
Wahrscheinlichkeitsfeedback Ziel ist es, die Dokumente nach
ihrer Wahrscheinlichkeit zu ordnen, die vom Benutzer als relevant in Bezug auf die Query eingestuft wurden
)|Pr()|Pr(log
nonrelxrelx
12.06.2002 Niko Zenker 11
Anfrageverfeinerung (IV)konventionelles Wkt.-feedback (Probabilistic conventional)
Verhältnis, der Wahrscheinlichkeiten der relevanten zu den nichtrelevanten Termen der Retrieval-Ergebnisses.
)1()1(logii
iii pu
upqnew
0,15,0)|(
0,15,0)|(
RNrnnonrelxPu
RrrelxPp
iiii
iii
12.06.2002 Niko Zenker 12
Anfrageverfeinerung (V)angepassetes Wkt.-feedback bzgl. der Herkunft(Probabilistic adjusted derivation)
Verallgemeinerung des konventionellen Modells, im Bezug auf das Auftreten bestimmter Dokumente.
)1()1(logii
iii pu
upqnew
1)|(
1)|(
RNNnrn
nonrelxPu
RNnr
relxPp
iii
ii
ii
ii
12.06.2002 Niko Zenker 13
Beispiel 500 Dokumente in der DB (N) 100 mit den gewünschten
Informationen (ni) 25 werden als relevant markiert (R) nur 10 dieser als relevant
markierten Dokumente enthalten die gewünschte Information (ri)
12.06.2002 Niko Zenker 14
Beispiel (II)
44109877,012550050010010100
12550010010
48536662,01255005,010100
0,1255,010
new
new
i
ii
i
ii
q
up
q
up
12.06.2002 Niko Zenker 15
Anfrageverfeinerung (VI)angepassetes Wkt.-feedback bzgl. der Herkunft (verbessert)(Probabilistic adjusted derivation revised)
selbe Prinzip wie zuvor, nur mit anderen Werten für R‘ = R+3 und ri‘=ri+3
)1()1(logii
iii pu
upqnew
1)|(
1)|(
RNNnrn
nonrelxPu
RNnr
relxPp
iii
ii
ii
ii
12.06.2002 Niko Zenker 16
Auswertung der Methoden die Effizienz der Methoden,
errechnet man durch einen Vergleich der ersten Iteration des Feedback-Verfahrens und der Initiationssuche
normalerweise benutzt man Recall und Precision Messungen um dieses Ergebnis zu errechnen
12.06.2002 Niko Zenker 17
Precision & Recall Precision
gefundene relevante Dokumente alle gefundenen Dokumente
Recall gefundene relevante Dokumente__ gespeicherte relevante Dokumente
Menge aller Dokumente
relvante Dokumente
gefundene relevante Dokumente
12.06.2002 Niko Zenker 18
Auswertung der Methoden (II) die Auswertung der Feedback-
Dokumente wird erschwert weil sich die Ergebnisse teils deutlich vom
echten Feedback-Ergebnis unterscheiden der User will nicht zweimal das selbe
Dokument sehen die Relevanz-Feedback Operation muss
entscheiden, ob sie neue Dokumente anzeigt, die nicht ursprünglich vom User gesehen wurden
12.06.2002 Niko Zenker 19
Partial Query Expansion vs. Full Query Expansion FQE:
alle Anfragevektoren haben die selbe Länge wie der Ursprung
Gewichtungen werden verändert PQE:
reduzieren auf durchschnittliche Länge der Anfragevektoren
Terme mit hoher Frequenz werden übernommen
12.06.2002 Niko Zenker 20
Ergebnisse aus der Forschung gewichtete Terme produzieren bessere
Ergebnisse beim Feedback-Prozess full expansion erweist sich als besser als
partial expansion die beste Feedback-Methode ist: „Ide dec
hi“ Wahrscheinlichkeits-Feedback ist im
Allgemeinen schlechter als Vektor-Feedback
12.06.2002 Niko Zenker 21
Optimierung des Feedbacks die durchschnittliche Länge der
Anfrage ist von besonderem Interesse schlechte Initial-Ergebnisse iterieren
meist mit guten Ergebnissen präzise gestellte Anfragen werden
vom Feedback-Prozess besser adaptiert
12.06.2002 Niko Zenker 22
Zusammenfassung Relevanz-Feedback ist eine „billige“
Methode für die Neuformulierung von Anfragen mit Bezug auf die vorherigen Ergebnisse
wegen der Einfachheit der Veränderungen der Anfragen, sollten Relevanz-Feedback-Systeme in jedes Text-Retrieval-System eingebunden werden