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
Quicklinks ustawia wskaźnik na tę stronę
domową
46
47
Alternatywne prezentacje
wyników?
Aktywny obszar badań HCI (human computer
interactions)
Alternatywa:
kopiuje idee Apple’s Cover Flow dla wyników
wyszukiwania
(searchme może być nieczynne)
48