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