Ocena efektywności

wyszukiwania informacji



Jak możemy się dowiedzieć czy wyniki
wyszukiwania są dobre?



Ocena silnika wyszukiwawczego



Standardowe zbiory testowe



Precyzja i kompletność



Podsumowania wyników:



Prezentacja wyników w formie użytecznej dla
użytkownika

1

OCENA SILNIKÓW

WYSZUKIWAWCZYCH

3

Miary dla silników
wyszukiwawczych



Jak szybko budują indeks



Liczba dokumentów/godzina



(Średni rozmiar dokumentu)



Jak szybko wyszukują



Czas oczekiwania jako funkcja rozmiaru indeksu



Ekspresyjność języka zapytań



Możliwość wyrażania złożonych potrzeb
informacyjnych



Szybkość dla złożonych pytań



Odpowiedni UI



Czy bezpłatny dostęp?

4

Miary dla silników
wyszukiwawczych - cd



Wszystkie przedstawione kryteria są
mierzalne: możemy określać prędkość/rozmiar



Możemy przedstawić ekspresyjność precyzyjnie



Główna miara: satysfakcja użytkownika



Co to jest?



Szybkość odpowiedzi/rozmiar indeksu to
współczynniki



Ale oślepiająca prędkość, bezużyteczne odpowiedzi
nie spowodują satysfakcji użytkownika



Potrzebny jest sposób mierzenia satysfakcji
użytkownika

5

Mierzenie zadowolenia
użytkownika



Problem: kto jest użytkownikiem, którego

chcemy zadowolić?



To zależy od okoliczności



Web engine:



Użytkownik, który zalazł to czego szukał powraca



Możemy mierzyć stosunek powracających użytkowników



Użytkownik wykonuje swoje zadanie, ale nie kończy



Patrz Russell http://dmrussell.googlepages.com/JCDL-

talk-June-2007-short.pdf



Strona eCommerce: użytkownik znalazł co chciał

i kupił



Czy end-user, lub stron eCommerce site, są tym czyje

zadowolenie mierzymy?



Mierzymy czas zakupów, lub ułamek użytkowników kupujących?

6

Pomiar zadowolenia
użytkowników



Przedsiębiorstwo
(company/govt/academic): Dbają o “user
productivity”



Jak dużo czasu mój użytkownik oszczędza kiedy
szuka informacji?



Wiele innych kryteriów dotyczy szerokości
dostępu, bezpieczeństwa dostępu, etc.

7

Zadowolenie: trudne do
mierzenia



Najbliższe: relewancja wyników wyszukiwania



Ale jak mierzymy relewancję?



Pokażemy szczegóły a potem opiszemy
problemy



Pomiar relewancji wymaga 3 elementów:

1.

Testowej kolekcji dokumentów

2.

Odpowiedniego testowego zbioru pytań

3.

Zwykle binarnej oceny Relewantny lub
Nierelewantny dla każdego pytania i każdego
dokumentu



Niekiedy stosuje się nie binarne systemy, ale to nie jest
standard

8

Ocena systemu IR



Uwaga: potrzeba informacyjna jest
przekształcana w pytanie



Relewancja jest oceniana w odniesieniu do
potrzeby informacyjnej nie do pytania



Np.: Potrzeba informacyjna: I'm looking for
information on whether drinking red wine is
more effective at reducing your risk of heart
attacks than white wine.



Query: wine red white heart attack
effective



Oceniamy czy doc odpowiada potrzebie
informacyjnej, nie czy zawiera te słowa

9

Standardowe testy relewancji



TREC (Text REtrieval Conference) - National
Institute of Standards and Technology (NIST)
wykonuje testowanie dla dużych systemów IR
od wielu lat



Reuters i inne standardowe testowe kolekcje
dokumentów są używane



“Zadania wyszukiwawcze” są określone



Czasem jako pytania



Eksperci ludzie zaznaczają dla każdego pytania
i dla każdego doc, Relevant lub Nonrelevant



Lub co najmniej dla podzbioru docs, który system
zwraca dla pytania

10

Ocena wyszukiwania bez rankingu:
Precyzja i kompletność



Precyzja: ułamek wyszukanych docs które są
relewantne = P(relewantne|wyszukane)



Kompletność: ułamek relewantnych docs,
które są wyszukane = P(wyszukane|relewantne)



Precyzja P = tp/(tp + fp)



Kompletność R = tp/(tp + fn)

Relewantne

Nierelewantn
e

Wyszukane

tp

fp

Nie

wyszukane

fn

tn

11

Czy zamiast tego możemy użyć
miary dokładności do oceny?



Dla danego pytania, silnik klasyfikuje
każdy doc jako “Relevant” lub
“Nonrelevant”



Dokładność silnika: ułamek tych
zaklasyfikowanych, które są poprawne



(tp + tn) / ( tp + fp + fn + tn)



Dokładność jest zwykle używaną miarą
oceny w uczeniu maszynowym



Dlaczego nie jest to zbyt użyteczna miara
oceny w IR?

12

Dlaczego nie używamy
dokładności?



Jak zbudować silnik wyszukiwawczy o
dokładności 99.9999% z małym budżetem….



Ludzie wyszukujący informację chcą coś
znaleźć i mają pewną tolerancję dla śmieci.

Search for:

0 matching results found.

13

Precyzja/Kompletność



Można uzyskać wysoką kompletność (ale
małą precyzję) przez wyszukiwanie
wszystkich docs dla wszystkich pytań!



Kompletność jest niemalejącą funkcją
liczby wyszukanych docs



W dobrym systemie, precyzja spada jeśli
liczba wyszukanych dokumentów lub
kompletność wzrasta



Nie jest to twierdzenie, ale wynik z mocnym
potwierdzeniem empirycznym

14

Trudności w stosowaniu
precyzji/kompletności



Czy powinno się uśredniać dla dużych
kolekcji dokumentów/grup pytań



Potrzebujemy ludzką ocenę relewancji



Ludzie nie są niezawodnymi sędziami



Ocena powinna być binarna



Oceny niuansów?



Mocno zniekształcona przez
kolekcje/autorstwo



Wyniki mogą nie być przenoszone z jednej
domeny do innej

15

Łączna miara: F



Łączna miara, która ocenia kompromis
precyzja/kompletność to F miara (ważona
średnia harmoniczna):



Ludzie zwykle stosują zrównoważoną miarę F

1



tzn. z  = 1 or  = ½



Harmoniczna miara zachowuje średnią



Patrz CJ van Rijsbergen, Information Retrieval

R

P

PR

R

P

F













2

2

)

1

(

1

)

1

(

1

1









16

F

1

i inne średnie

17

Ocena wyników z rankingiem



Ocena uszeregowanych wyników:



System może zwrócić dowolną liczbę wyników



Przez wzięcie różnej liczby zwróconych
dokumentów (poziomów kompletności),
oceniający może wykreślić krzywą precyzja-
kompletność

18

Krzywa precyzja-kompletność

19

Uśrednianie po pytaniach



Wykres precyzja –kompletność dla jednego
pytania nie jest zbyt interesujący



Potrzebujemy średnią wydajność dla
całego pakietu pytań.



Ale jest problem techniczny:



Precyzja-kompletność oblicza pewne punkty na
wykresie



Jak określić (interpolować) wartości między
punktami?

20

Interpolacyjna precyzja



Zasada: Jeśli lokalnie precyzja rośnie ze
wzrostem kompletności, to bierzemy to
pod uwagę…



Więc podnosimy precyzje do prawej
wartości

21

Ocena



Wykresy są dobre, ale ludzie chcą sumaryczne miary!



Precyzja na ustalonym poziomie wyszukiwania



Precyzja-dla-k: Precyzja dla top k wyników



Być może właściwe dla większości wyszukiwań webowych:
wszyscy ludzie oczekują dobrego dopasowania na jednej lub
dwóch pierwszych stronach wyników



Ale: uśrednienie słabe i ma arbitralny parametr k



11-punktowa interpolowana średnia precyzja



Standardowa miara w początkach stosowania TREC:
bierzemy precyzję na 11 poziomach kompletności od 0 do 1
dla dziesiątek dokumentów, stosując interpolację

(wartość

dla 0 jest zawsze interpolowana!)

, i uśredniamy je



Oceniamy wydajność dla wszystkich poziomów
kompletności

22

Typowa (dobra) 11 punktowa
precyzja



SabIR/Cornell 8A1 11pt precyzja z TREC 8 (1999)

23

Jeszcze więcej miar oceny…



Średnia przeciętna precyzja (MAP)



Średnia precyzji uzyskana dla top k dokumentów za
każdym razem gdy relewantny doc jest wyszukany



Unikamy interpolacji, używając ustalone poziomy
kompletności



MAP dla zbioru pytań jest średnią arytmetyczną.



Macro-uśrednianie: każde pytanie wpływa jednakowo



R-precyzja



Jeśli znamy (chociaż być może niekompletnie) zbiór
relewantnych dokumentów o rozmiarze Rel, wtedy
obliczamy precyzję wyszukanych top Rel docs



Doskonały system powinien mieć wynik 1.0.

24

Wariancja



Dla kolekcji testowej, często system działa
bardzo źle dla pewnych potrzeb
informacyjnych (np.: MAP = 0.1) a
wspaniale dla innych (np.: MAP = 0.7)



Oczywiście, często wariancja wydajności
tego samego systemu dla różnych pytań
jest znacznie większa niż wariancja różnych
systemów dla tego samego pytania.



Wiec, są łatwe potrzeby informacyjne i
trudne!

BUDOWA KOLEKCJI

TESTOWYCH DLA OCENY IR

26

Kolekcje testowe

27

Od kolekcji dokumentów do
kolekcji testowych



Ciągle potrzebne



Pytania testowe



Ocena relewancji



Pytania testowe



Muszą być odpowiednie do dostępnych docs



Najlepiej zaprojektowane przez ekspertów
dziedzinowych



Losowe termy pytania ogólnie nie są dobrym
pomysłem



Ocena relewancji



Ocena przez człowieka wymaga dużo czasu



Czy grupy ludzkie są idelne?

28

Oceniane jednostki



Możemy obliczać precyzję, kompletność, F
oraz krzywe ROC dla różnych jednostek.



Możliwe jednostki



Dokumenty (najczęściej)



Fakty (używane dla pewnych ocen TREC)



Organizacje (np.: koncerny samochodowe)



Mogą dostarczać różnych wyników.
Dlaczego?

29

Miara Kappa dla niezgodności
między oceniającymi



Miara Kappa



Miara zgodności między oceniającymi



Zaprojektowana dla kategorycznych ocen



Koryguje przypadkowe zgodności



Kappa = [ P(A) – P(E) ] / [ 1 – P(E) ]



P(A) – część czasu, w której oceniający się
zgadzają



P(E) – jaka zgoda byłaby losowa



Kappa = 0 dla przypadkowej zgodności, 1 dla
całkowitej zgodności.

30

Miara kappa: przykład

Liczba docs

Oceniający 1

Oceniający 2

300

Relevant

Relevant

70

Nonrelevant

Nonrelevant

20

Relevant

Nonrelevant

10

Nonrelevant

Relevant

P(A)? P(E)?

31

Kappa - Przykład



P(A) = 370/400 = 0.925



P(nonrelevant) = (10+20+70+70)/800 = 0.2125



P(relevant) = (10+20+300+300)/800 = 0.7878



P(E) = 0.2125^2 + 0.7878^2 = 0.665



Kappa = (0.925 – 0.665)/(1-0.665) = 0.776



Kappa > 0.8 = dobra zgodność



0.67 < Kappa < 0.8 -> “tymczasowe wyniki”
(Carletta ’96)



Zależy od celu badań



Dla >2 oceniających: uśredniamy parami kappy

32

TREC



TREC Ad Hoc zadanie z pierwszych 8 TRECs jest
standardowym zadaniem IR



50 szczegółowych potrzeb informacyjnych na rok



Ocena przez człowieka wyników



Ostatnio inne rzeczy: Webowe ścieżki, HARD



A TREC query (TREC 5)

<top>
<num> Number: 225
<desc> Description:
What is the main function of the Federal Emergency

Management Agency (FEMA) and the funding level
provided to meet emergencies? Also, what resources are
available to FEMA such as people, equipment, facilities?

</top>

Standardowe zbiory do oceny
relewancji: Inne



GOV2



Inna kolekcja TREC/NIST



25 milionów stron webowych



To największa kolekcja łatwo dostępna



Ale ciągle 3 rzędy mniejsza niż Google/Yahoo/MSN



NTCIR



East Asian language and cross-language information

retrieval



Cross Language Evaluation Forum (CLEF) –

wyszukiwanie wielojęzyczne



Ta seria oceniająca koncentruje się na językach

europejskich i wyszukiwaniem dla wielojęzycznych

dokumentów.



Wiele innych

33

34

Porozumienie między
oceniającymi: TREC 3

35

Wpływ niezgodności między
oceniającymi



Wpływ na

całkowitą

miarę wydajności może być

znaczny (0.32 vs 0.39)



Mały wpływ na ranking różnych systemów lub

względną

wydajność



Przypuśćmy, że chcemy wiedzieć czy algorytm A
jest lepszy niż algorytm B



Standardowy eksperyment wyszukiwawczy da
nam pewną odpowiedź.

36

Krytyka czystej relewancji



Relewancja kontra

Relewancja Brzegowa



Dokument może być redundantny nawet jeśli
jest wysoce relewantny



Duplikaty



Te same informacje z różnych źródeł



Relewancja brzegowa jest lepszą miarą
użyteczności dla użytkownika.



Użycie faktów/jednostek jako elementów
lepiej mierzy prawdziwą relewancję.



Ale trudniej tworzyć zbiór do oceny



Patrz literatura Carbonell

37

Czy możemy uniknąć ludzkich
ocen?



Nie



Powoduje to trudności w eksperymentach



Szczególnie w dużej skali



W pewnych specyficznych warunkach można
stosować aproksymację



Np.: dla określonego wyszukiwania w przestrzeni
wektorowej, możemy porównać odległość
najbliższych dokumentów do tych znalezionych
przez przybliżony algorytm wyszukujący



Ale jeśli mamy już kolekcję testową, możemy
ją używać wielokrotnie (ale niezbyt długo)

Ocena dużych silników
wyszukiwawczych



Silniki wyszukiwawcze mają kolekcje testowe pytań i
ręcznie ustalany ranking wyników



Kompletność jest trudno zmierzyć w web



Search engines często używają precyzji dla top k, np.: k
= 10



. . . Lub miary, które zwracają więcej dając rangę 1 dla
początkowych 10 .



NDCG (Normalized Cumulative Discounted Gain)



Search engines stosują także miary nierelewancyjne.



Klikniecie na pierwszy wynik



Niezbyt pewne jeśli patrzymy na pojedyncze kliknięcie …
ale bardzo niezawodne po agregacji.



Studiowanie zachowania użytkowników



A/B testowanie

38

Testowanie A/B



Cel: Testowanie pojedynczej innowacji



Założenia: Mamy duży search engine działający.



Mamy b. dużo użytkowników w starym systemie



Kierujemy mały ułamek ruchu (np.: 1%) do

nowego systemu , który zawiera tę innowację



Oceniamy “automatyczną” miarą jak kliknięcie na

pierwszy wynik



Wtedy bezpośrednio widzimy czy wprowadzona

innowacja zwiększa zadowolenie użytkownika.



Prawdopodobnie jest to metodologia oceny, której

duże search engines ufają najbardziej



W zasadzie jest to słabsza metoda niż

wielowariantowa analiza regresji, ale łatwiejsze

do zrozumienia

39

PREZENTACJA WYNIKÓW

40

41

Podsumowania wyników



Mając ranking dokumentów pasujących do
pytania chcemy go zaprezentować jako
listę



Najczęściej jako listę tytułów dokumentów
plus krótkie podsumowania, znane jako
“10 blue links”

42

Podsumowania



Tytuł jest często automatycznie pobierany z
metadanych. Co z podsumowaniem?



Ten opis jest decydujący.



Użytkownik może identyfikować dobre/relewantne trafienia
bazując na opisach.



Dwa podstawowe rodzaje:



Statyczne



Dynamiczne



Statyczne podsumowanie dokumentu zawsze
pozostaje takie samo, niezależnie od pytania które
trafiło na dokument



Dynamiczne podsumowanie jest zależne od pytania
i próbuje wyjaśnić dlaczego dokument został
wyszukany dla pytania

43

Statyczne podsumowania



W typowych systemach statyczne podsumowanie

jest podzbiorem dokumentu



Najprostsza heurystyka: pierwsze 50 (lub podobnie –

bo to się może zmieniać) słowa dokumentu



Podsumowanie jest cachowane w czasie indeksowania



Bardziej skomplikowane: wybierz z każdego

dokumentu zbór zdań kluczowych



Proste NLP (natural language processing) heurytyki do

oceny każdego zdania



Podsumowania budujemy ze zdań z najwyższą oceną.



Najbardziej skomplikowane: NLP do budowy podsum



Rzadko stosowane w IR; porównaj: prace podsum tekstu

44

Posumowania dynamiczne



Prezentuj jedno lub więcej “okienek” w
dokumencie zawierających kilka termów z pytania



“KWIC” to snippets od: Keyword in Context presentation

Techniki dla dynamicznych
podsumowań



Znajdź małe okienka w dokumencie, które
zawierają



Wymaga szybkiego przeglądania okna w cache
dokumentu



Oceń każde okno dla pytania



Użyj różnych cech takich jak szerokość okna,
pozycja w dokumencie itd.



Połącz cechy w funkcji wynikowej



Wyzwania dla badania: ocena podsumowań



Łatwiejsze do porównania parami niż do binarnej
oceny relewancji

45

Szybkie linki



Dla nawigacyjnego pytania takiego jak united
airlines potrzeba użytkownika zaspokojona, gdy

www.united.com



Quicklinks ustawia wskaźnik na tę stronę
domową

46

47

Alternatywne prezentacje
wyników?



Aktywny obszar badań HCI (human computer
interactions)



Alternatywa:

http://www.searchme.com /

kopiuje idee Apple’s Cover Flow dla wyników
wyszukiwania



(searchme może być nieczynne)

48