Sprzężenie relewancyjne i

rozbudowa pytania

Relewancyjne sprzężenie
zwrotne



Relewancyjne sprzężenie zwrotne: użytkownik
podaje relewancję dla początkowego zbioru
wyników



Użytkownik dostarcza (krótkie, proste) pytanie



Użytkownik

pewne wyniki jako relewantne lub nie-relew.



System

oblicza lepszą reprezentację potrzeby

informacyjnej bazując na tym sprzężeniu zwrotnym.



Relewancyjne sprzężenie zwrotne może przejść przez
jedną lub wiele

iteracji

.



Idea: może być trudna sformułować dobre pytanie
nie znając dobrze kolekcji, więc stosujemy
iterację.

Sprzężenie relewancyjne



Będziemy stosować wyszukiwanie ad hoc
aby pokazać wyszukiwanie bez sprzężenia
relewancyjnego.



Najpierw jednak pokażemy cztery
przykłady ze sprzężeniem, aby naświetlić
różne aspekty.

Podobne strony

Sprzężenie relewancyjne:
przykład



Silnik wyszukiwawczy obrazów

http://nayana.ece.ucsb.edu/imsearch/imsearch.h
tml

Wyniki dla początkowego
pytania

Sprzężenie relewancyjne

Results after Relevance
Feedback

Wyniki ad hoc dla pytania

canine

source: Fernando Diaz

Wyniki ad hoc dla pytania

canine

source: Fernando Diaz

User feedback: Wybierz

relewantne

source: Fernando Diaz

Wyniki po sprzężeniu rel.

source: Fernando Diaz

Początkowe pytanie/wyniki



Początkowe pytanie: New space satellite
applications

1. 0.539, 08/13/91,

NASA Hasn’t Scrapped Imaging Spectrometer

2. 0.533, 07/09/91,

NASA Scratches Environment Gear From Satellite Plan

3. 0.528, 04/04/90,

Science Panel Backs NASA Satellite Plan, But Urges Launches

of Smaller Probes

4. 0.526, 09/09/91,

A NASA Satellite Project Accomplishes Incredible Feat: Staying

Within Budget

5. 0.525, 07/24/90,

Scientist Who Exposed Global Warming Proposes Satellites for

Climate Research

6. 0.524, 08/22/90,

Report Provides Support for the Critics Of Using Big Satellites to

Study Climate

7. 0.516, 04/13/87,

Arianespace Receives Satellite Launch Pact From Telesat

Canada

8. 0.509, 12/02/87,

Telecommunications Tale of Two Companies



Użytkownik zaznacza relewantne dokumenty
znakiem “+”.

+

+

+

Rozszerzone pytanie po sprzężeniu
relewancyjnym



2.074

(to jest waga termu)

new

15.106

space



30.816

satellite

5.660

application



5.991

nasa

5.196

eos



4.196

launch

3.972

aster



3.516

instrument

3.446

arianespace



3.004

bundespost

2.806

ss



2.790

rocket

2.053

scientist



2.003

broadcast

1.172

earth



0.836

oil

0.646

measure

Wyniki dla rozszerzonego
pytania

1. 0.513, 07/09/91,

NASA Scratches Environment Gear From Satellite

Plan

2. 0.500, 08/13/91,

NASA Hasn’t Scrapped Imaging Spectrometer

3. 0.493, 08/07/89,

When the Pentagon Launches a Secret Satellite,

Space Sleuths Do Some Spy Work of Their Own

4. 0.493, 07/31/89,

NASA Uses ‘Warm’ Superconductors For Fast

Circuit

5. 0.492, 12/02/87,

Telecommunications Tale of Two Companies

6. 0.491, 07/09/91,

Soviets May Adapt Parts of SS-20 Missile For

Commercial Use

7. 0.490, 07/12/88,

Gaping Gap: Pentagon Lags in Race To Match the

Soviets In Rocket Launchers

8. 0.490, 06/14/90,

Rescue of Satellite By Space Agency To Cost $90

Million

2
1

8

Główna koncepcja: Centroid



Centroid jest środkiem masy zbioru
punktów



Przypominamy, że reprezentujemy
dokumenty jako punkty w
wysokowymiarowej przestrzeni



Definicja: Centroid

gdzie: C jest zbiorem dokumentów.







C

d

d

C

C





|

|

1

)

(



Algorytm Rocchio



Algorytm Rocchio model przestrzeni wektorowej do
zwiększenia relewancji pytania po sprzężeniu relew.



Rocchio szuka pytania q

opt

, które maksymalizuje



Próbuje oddzielić docs zaznaczone relewantne od
nie



Problem: nie znamy rzeczywiście relewantnych docs

))]

(

,

cos(

))

(

,

[cos(

max

arg

nr

r

q

opt

C

q

C

q

q

































r

j

r

j

C

d

j

nr

C

d

j

r

opt

d

C

d

C

q











1

1

Teoretycznie najlepsze pytanie

x

x

x

x

o

o

o

Optymaln
e pytanie

x non-relevant
documents
o relevant
documents

o

o

o

x

x

x

x

x

x

x

x

x

x

x

x



x

x

Rocchio 1971 Algorytm (system
SMART)



Używany w praktyce:



D

r

= zbiór znanych wektorów relewantnych docs



D

nr

= zbiór znanych wektorów nierelewantnych docs



Różne od

C

r

i C

nr

!



q

m

= zmodyfikowany wektor pytania; q

0

= oryginalny

wektor pytania; α,β,γ: wagi (dobrane ręcznie lub

doświadczalnie)



Nowe pytania przesuwają się w kierunku

relewantnych dokumentów i oddalają od

nierelewantnych dokumentów















nr

j

r

j

D

d

j

nr

D

d

j

r

m

d

D

d

D

q

q













1

1

0







Subtelności



Kompromis α kontra β/γ : Jeśli mamy dużo

ocenionych dokumentów chcemy wyższe

β/γ.



Niektóre wagi w wektorze pytania mogą

stać się ujemne



Ujemne wagi termów są ignorowane

(zastąpione zerem)

Sprzężenie rel. dla pytania
początkowego

x

x

x

x

o

o

o

zmienion
e pytanie

x known non-relevant
documents
o known relevant
documents

o

o

o

x

x

x

x

x

x

x

x

x

x

x

x



x

x

Począ
t-
kowe
pytan
ie



Sprzężenie relewancyjne w
przestrzeni wektorowej



Możemy modyfikować pytanie sprzężeniem
rel. i stosować standardowy model
przestrzeni wektorowej.



Używamy tylko dokumentów zaznaczonych.



Sprzężenie relewancyjne może poprawić
kompletność i dokładność



Relewancyjne sprzężenie jest najbardziej
użyteczne do zwiększania kompletności w
sytuacjach gdzie kompletność jest ważna



Oczekuje się, że użytkownicy będą przeglądać i
poświęcać czas na kolejne iteracje

Dodatnie vs ujemne sprzężenie



Dodatnie sprzężenie lepsze niż ujemne
sprzężenie (więc, ustawienie  < ; np.:

 = 0.25,  = 0.75).



Wiele systemów pozwala tylko na
dodatnie sprzężenie (=0).

dla

cz

eg

o?

Dygresja: Przestrzeń
wektorowa może być
nieintuicyjna.

x

x

x

x

x

x

x

Pytanie

“cholera”

q1 pytanie “cholera”
o
www.ph.ucla.edu/epi/snow.ht
ml
x inne dokumenty

x

o

q1

x

x

x

x

x

x

x

x

x

x

x

x

x

x

Dokument

“J. Snow

& Cholera”

Wysoko – wymiarowa
przestrzeń wektorowa



Pytania “cholera” i “john snow” są bardzo
daleko od siebie w przestrzeni
wektorowej.



Jak może dokument “John Snow and
Cholera” być blisko obydwu z nich?



Nasze intuicje dla 2- i 3-wymiarowej
przestrzeni nie sprawdzają się w >10,000
wymiarach.



3 wymiary: jeśli dokument jest blisko do
wielu pytań, wtedy pewne z nich muszą
być blisko siebie.



Nie sprawdza się to dla wysoko –
wymiarowej przestrzeni.

Sprzężenie relewancyjne:
założenia



Zał.1: Użytkownik ma wystarczającą wiedzę
dla zadania początkowego pytania.



Zał.2: Relewancyjne prototypy “dobrze się
zachowują”.



Rozkład termów w relewantnych dokument. jest
podobny



Rozkład termów w nierelewantnych docs jest inny
niż w relewantnych



Albo: Wszystkie relewantne dokumenty są ściśle
zgrupowane wokół pojedynczego prototypu.



Lub: Są różne prototypy, ale duża część ich słowników się
pokrywa.



Podobieństwo między relewantnymi i nirelewantnymi
dokumentami jest małe

Niespełnianie Zał.1



Użytkownik nie ma wystarczającej wiedzy
początkowej.



Przykłady:



Literówki (Brittany Speers).



Wielojęzyczne wyszukiwanie (hígado).



Niedopasowanie słownika użytkownika vs.
Słownik kolekcji



Cosmonaut/astronaut

Niespełnianie Zał.2



Jest wiele relewantnych prototypów.



Przykłady:



Burma/Myanmar



Sprzeczne strategie rządowe



Pop stars that worked at Burger King



Często: instancje ogólnych koncepcji



Dobra edycja może takie problemy
wyjaśniać



Raport o sprzecznych strategiach rzadowych

Relewancyjne sprzężenie
zwrotne: Problemy



Długie pytania są nieefektywne dla
typowego silnika IR.



Długi czas odpowiedzi.



Wysoki koszt systemu IR.



Częściowe rozwiązanie:



Tylko nowe ważenie najważniejszych termów



Być może 20 wg częstości termów



Użytkownicy są często niechętni
dostarczaniu dokładnego sprzężenia rel.



Często trudno zrozumieć dlaczego pewien
dokument został wyszukany po
relewancyjnym sprzężeniu zwrotnym

Dla

cze

go

?

Ocena strategii relewancyjnego
sprzężenia zwrotnego



Użyj q

0

i oblicz wykres precyzji i kompletności



Użyj q

m

i oblicz wykres precyzji i kompletności



Oceń dla wszystkich dokumentów w kolekcji



Spektakularne polepszenie, ale … to oszustwo!



Częściowo dla znanych dokumentów relewantnych wysoko w
rankingu



Musisz oceniać uwzględniając dokumenty, których
użytkownik nie widział



Użyj dokumenty w pozostałej kolekcji (całość minus
dokumentu ocenione jako relewantne)



Miary zwykle mniejsze niż dla oryginalnych pytań



Ale bardziej realistyczna ocena



Względna efektywność może być właściwie porównana



Doświadczenie: jednorazowe rel. sprzężenie zwrotne jest
często bardzo użyteczne. Dwie rundy są czasami
marginalnie użyteczne.

Ocena strategii relewancyjnego
sprzężenia zwrotnego



Druga metoda – oceń tylko docs nie
oceniane przez użytkownika w pierwszym
kroku



Czy sprzężenie relewancyjne może pogorszyć
sytuację



Czy możemy dalej oceniać relatywną wydajność
algorytmów



Najbardziej satysfakcjonujące – użycie
dwóch kolekcji z ich własną oceną relewancji



Q

0

i sprzężenie użytkownika z pierwszej kolekcji



q

m

przetwarzaj dla drugiej kolekcji i mierz

Ocena: Ostrzeżenie



Prawdziwa ocena użyteczności musi być
porównana do innych metod wymagających
tyle samo czasu.



Alternatywa dla relewancyjnego sprzężenia
zwrotnego: Użytkownik poprawia i ponownie
zadaje pytanie.



Użytkownicy mogą woleć poprawiane/ponowne
zadawanie mając ocenioną relewancję
dokumentów.



Nie ma ewidentnych dowodów na to, że
sprzężenie relewancyjne jest „najlepszym
wykorzystaniem” czasu uzytkownika.

Sprzężenie relewancyjne w Webie



Pewne silniki wyszukiwawcze oferują podobne/powiązane
strony (jest to trywialna forma relewancyjnego sprzężenia
zwrotnego)



Google (oparte na linkach)



Altavista



Stanford WebBase



Ale niektóre nie używają ponieważ trudno to wytłumaczyć
przeciętnemu użytkownikowi:



Alltheweb



bing



Yahoo



Excite początkowo miał prawdziwe relewancyjne
sprzężenie zwrotne, usunął ze względu na brak
wykorzystywania przez użytkowników.

α/β/γ ??

Relewancyjne sprzężenie
zwrotne w Excite

Patrz: Spink et al. 2000



Tylko około 4% sesji zapytań z udziałem
użytkowników stosujących opcję
relewancyjnego sprzężenia



Przedstawione jako link “More like this” po każdym
wyniku



Ale około 70% użytkowników ogląda tylko
pierwszą stronę wyników i nic dalej nie robi



Więc 4% to około 1/8 ludzi przedłużających szukanie



Sprzężenie relewancyjne polepsza wyniki 2/3
razy

Pseudo – relewancyjne
sprzężenie zwrotne



Pseudo – relewancyjne sprzężenie zwrotne
automatyzuje “manualną” część prawdziwego
relewancyjnego sprzężenia zwrotnego.



Algorytm Pseudo-relewancji:



Przeszukaj rankingową listę trafień dla pytania
użytkownika



Przyjmij, że pierwszych k documents jest relewantnych.



Wykonaj sprzężenie relewancyjne (np.: Rocchio)



Pracuje bardzo dobrze wg średniej



Ale może być potwornie źle dla niektórych pytań



Kilka iteracji może spowodować dryfowanie
pytania.



Dlaczego?

Rozbudowa pytania



W sprzężeniu relewancyjnym użytkownicy
dodają dodatkowe wejście (relevant/non-
relevant) dla

dokumentów

, które jest

wykorzystane dla zmian wag termów w
dokumenctach



Rozbudowując pytanie, użytkownik dodaje
dodatkowe wejście (good/bad search
term) dla

słów lub fraz

Wspomaganie pytania

Czy możesz się spodziewać takiego sposobu wzrostu
objętości pytania w silniku wyszukiwawczym?

Jak rozszerzamy pytanie
użytkownika?



Manualne tezaurusy



Np.: MedLine: lekarz, synonimy: doc, doctor, MD,
medico



Dajemy raczej pytanie niż synonimy



Globalna Analiza:

(statyczna; wszystkich dokumentów

kolekcji)



Automatycznie budowany tezaurus



(statystyka współwystąpień)



Polepszanie oparte na miningu logu pytań



Popularne w web



Lokalna Analiza: (dynamiczna)



Analiza dokumentów ze

zbioru wynikowego

Przykład manualnego
tezaurusa

Przykład manualnego
tezaurusa

Przykład rozbudowy pytania z
wykorzystaniem tezaurusa



Dla każdego termu t, w pytaniu, poszerz pytanie
synonimami i słowami związanymi z t tezaurusa



feline → feline cat



Czy mogą dodane termy ważyć mniej niż oryginalne
termy pytania.



Generalnie rośnie kompletność



Szeroko używane wielu naukowych/inżynieryjnych
dziedzinach



Mogą znacząco zmniejszyć precyzję, szczególnie dla
dwuznacznych termów.



“interest rate”  “interest rate fascinate evaluate”



Manualna budowa tezaurusa jest bardzo kosztowna



Tak samo uaktualnianie go zgodnie ze zmianami wiedzy
naukowej

Automatyczne generowanie
tezaurusa



Próba generowania tezaurusa automatycznie
przez analizowanie kolekcji dokumentów



Fundamentalne pojęcie: podobieństwo między
dwoma słowami



Definicja 1: Dwa słowa są podobne jeśli występują z podobnymi
słowami.



Definicja 2: Dwa słowa są podobne jeśli występują w pewnej relacji z
tymi samymi słowami.



Możesz zbierać, obierać, jeść, suszyć, itd. jabłka i
gruszki, więc jabłka i gruszki muszą być
podobne.



Oparcie się na współwystąpieniach jest
mocniejsze, gramatyczne relacje są bardziej
precyzyjne.

Dlaczeg

o?

Tezaurus dla współwystąpień



Najprostszy sposób obliczenia to jest oparty na podobieństwie term-term w C = AA

T

gdzie A jest macierzą term-document.



w

i,j

= (znormalizowana) waga dla (t

i

,d

j

)



Dla każdego t

i

, wybierz termy z

wysokimi wartościami w C

t

i

d

j

N

M

Przykład automatycznej generacji
tezaurusa

Dyskusja: automatyczna generacja
tezaurusa



Jakość powiązań jest zwykle problemem.



Wieloznaczność termów może powodować
niewłaściwe statystyczne korelacje termów.



“Apple computer”  “Apple red fruit computer”



Problemy:



Fałszywe pozytywne: Słowa uznane za
podobne chociaż tak nie jest



Fałszywe negatywne: Słowa uznane za
niepodobne chociaż są podobne



Chociaż termy są mocno skorelowane to
poszerzenie może nie dać wielu
dodatkowych dokumentów.

Pośrednie relewancyjne
sprzężenie zwrotne



W web, DirectHit wprowadził formę

pośredniego

relewancyjnego sprzężenia zwrotnego.



DirectHit rankinguje dokumenty wyżej niż robią
to najczęściej użytkownicy.



Kliknięcia na linki zakładają relewantność



Zakłada, że wyświetlone podsumowania są dobre itd.



Globalnie: Nie koniecznie specyficzne dla
użytkownika lub pytania.



Jest ogólne podejście clickstream mining



Dzisiaj – stosowane jako część rankingu za
pomocą uczenia maszynowego