Obliczenia dla kompletnego

systemu wyszukiwania



Przypomnienie: wagi tf-idf



Waga tf-idf termu jest iloczynem jego wagi tf
i wagi idf.



To najlepszy znany system ważenia w IR



Rośnie ze wzrostem wystąpień w dokumencie



Rośnie ze wzrostem rzadkości termu w
kolekcji

)

df

/

(

log

)

tf

log

1

(

w

10

,

,

t

d

t

N

d

t







1

Przypomnienie: Pytania jako
wektory



Zasada 1:

Zrób to samo z pytaniami:

przedstaw je jako wektory w przestrzeni



Zasada 2:

Rankinguj dokumenty wg ich

odległości od pytania w tej przestrzeni



odległość = podobieństwo wektorów

2

Powtórzenie: kosinus(pytanie
dokument)























V

i

i

V

i

i

V

i

i

i

d

q

d

q

d

d

q

q

d

q

d

q

d

q

1

2

1

2

1

)

,

cos(





















iloczyn

Wektory jednostkowe

cos(q,d) to podobieństwo kosinusowe q i d … lub,
równoważnie, kosinus kąta między q i d.

3

Nowe: obliczanie wartości
kosinusa

4

Efektywny ranking kosinusowy



Znajdź K docs w kolekcji “najbliższych”
do pytania  K największych query-doc

kosinusów.



Efektywny ranking:



Obliczanie efektywne pojedynczego
kosinusa.



Efektywne wybranie K największych
wartości kosinusa.



Czy możemy to wykonać bez obliczania
wszystkich N kosinusów?

5

Efektywny ranking kosinusowy



Co robimy w efekcie: rozwiązujemy
problem K-najbliższych sąsiadów dla
wektora pytania



W ogólności, nie wiemy jak to wykonać
efektywnie dla przestrzeni o dużym
wymiarze



Ale jest to rozwiązane dla krótkich i
standardowe indeksy tu pomagają

6

Specjalny przypadek – pytania
bez wag



Nie ma ważenia termów pytania



Zakładamy, że każdy term pytania
występuje tylko raz



Wtedy dla rankingu nie musimy
normalizować wektora pytania



Lekkie uproszczenie algorytmu z w_06

7

Szybszy kosinus: pytanie bez
wag

8

Obliczanie K największych
kosinusów: wybór kontra
sortowanie



Zwykle potrzebujemy znaleźć K
najwyższych docs (w rankingu
kosinusowym dla pytania)



Nie szukamy uporządkowania
wszystkich dokumentów w kolekcji



Czy możemy wybrać docs z K
największymi kosinusami?



Niech J = liczba docs z niezerowymi
kosinusami



Szukamy K najlepszych wśród tych J

9

Użycie sterty do znalezienia K
największych



Drzewo binarne, w którym każda wartość
węzła > wartości dzieci



Wymaga 2J operacji dla budowy, wtedy
każdy z K “zwycięzców” jest odczytany w
2log J krokach.



Dla J=1M, K=100, jest to około 10% kosztu
sortowania.

1

.9

.3

.8

.3

.1

.1

10

Wąskie gardła



Pierwsze obliczeniowe: obliczenie kosinusa



Czy możemy uniknąć tych wszystkich
obliczeń?



Tak, ale czasami złe wyniki



Dokumenty spoza najlepszych K mogą
wejść na listę K wyjściowych docs



Czy to taka zła sytuacja?

11

Kosinusowe podobieństwo jest
tylko przybliżeniem



Użytkownik ma zadanie i sformułowanie
pytania



Cosinus dopasowuje dokumenty do
pytania



Więc kosinus jest jedynie przybliżeniem
dla satysfakcji użytkownika



Jeśli dostaniemy listę K docs “bliskich” do
najlepszych K wg miary kosinusowej –
będzie dobrze

12

Ogólne podejście



Znajdź zbiór składników z K < |A| << N



A nie koniecznie zawiera najlepsze K, ale ma
wiele docs bliskich najlepszemu K



Zwróć najlepsze K docs do A



Przyjmij A jako pruning (przycinanie) nie
kandydujące



To samo podejście jest także stosowane dla
innych (nie-kosinusowych) funkcji
obliczających



Pokażemy kilka schematów zgodnych z tym
podejściem

13

Eliminacja indeksowa



Podstawowy algorytm z Rys 7.1
rozpatrywał tylko dokumenty zawierające
co najmniej jeden term pytania



Idźmy dalej:



Rozpatrzmy tylko termy pytania z wysokim idf



Rozpatrzmy tylko dokumenty zawierające wiele
termów pytania

14

Tylko termy pytania z wysokim
idf



Dla takiego pytania jak catcher in the rye



Pamiętamy wyniki dla catcher i rye



Intuicja: in i the mają mały wpływ na
wyniki więc nie zmieniają dużo w rankingu



Korzyść:



Wystąpienia termów z małym idf mają wiele
docs  te (wiele) docs jest eliminowanych ze

zbioru kandydatów A

15

Dokumenty zawierające kilka
termów pytania



Każdy dokument z co najmniej jednym
termem pytania jest kandydatem do K
wyjściowej listy



Dla wielotermowych pytań, obliczenia
tylko dla docs kilka termów pytania



Powiedzmy, co najmniej 3 z 4



Powoduje “soft conjunction” dla pytań
obserwowaną dla silników wyszukiwawczych
(wczesne Google)



Łatwa implementacja przy przechodzeniu
przez listy wystąpień

16

3 z 4 termów pytania

Brutus

Caesar

Calpurnia

1

2

3

5

8

13 21 34

2

4

8 16 32 64128

13 16

Antony

3 4

8 16 32 64128

32

Wyniki obliczane tylko dla docs 8, 16 and 32.

17

Listy czempionów



Oblicz wstępnie dla każdego termu t ze słownika,
r docs z najwyższymi wagami dla wystąpień t



Nazwij champion list dla t



(znane też jako fancy list lub top docs dla t)



Zauważmy, że r musi być wybierane w czasie
budowy indeksu



Więc jest możliwe, że r < K



W czasie obsługi pytania, obliczaj wyniki tylko
dla docs na champion list dla pewnych termów
pytania



Wybierz K docs z najwyższymi wynikami ze
wszystkich list

18

Quantitative

Quantitative

Statyczne wyniki jakości



Chcemy aby dokumenty top-ranking były
relewantne i wiarygodne



Relewancja jest modelowana przez wynik
kosinusa



Wiarygodność jest zwykle niezależną od pytania
własnością dokumentu



Przykłady oznak wiarygodności



Wikipedia w porównaniu z innymi websites



Artykuły z pewnych gazet



Artykuł z wieloma cytowaniami



Wiele diggs, Y!buzzes or del.icio.us znaków



(Pagerank)

19

Modelowanie wiarygodności



Przypisz do każdego dokumentu d
niezależny od pytania wskaźnik jakości w
[0,1]



Oznacz go przez g(d)



Więc, wielkość jak liczba cytowań jest
skalowana do [0,1]

20

Wynik netto



Rozpatrzmy prosty wynik wiążący
kosinusową relewancję i wiarygodność



net-score(q,d) = g(d) + cosine(q,d)



Możemy użyć jakąś inną kombinację liniowa
zamiast powyższej



Oczywiście chodzi o jakąś funkcję tych dwóch
sygnałów zadowolenia użytkownika – później



Teraz szukamy top K docs wg net score

21

Top K wg net score – szybkie
metody



Pierwsza zasada: Porządkuj wszystkie
wystąpienia wg g(d)



Ważne: to jest wspólne uporządkowanie
dla wszystkich wystąpień



Więc możemy współbieżnie przechodzić
wystąpienia termów pytania dla



Przecięcia wystąpień



Obliczenia wyniku kosinusa

22

Dlaczego porządkowanie
wystąpień wg g(d)?



Dla uporządkowania wg g(d), top docs
najprawdopodobniej wcześnie pokażą się
w wynikach przeglądania list



Dla aplikacji ograniczonych czasowo
(powiedzmy, musimy zwrócić jakieś wyniki
wyszukiwania w 50 ms), to pozwala nam
przerwać przeszukiwanie wcześnie



Krótkie wyniki dla wszystkich wystąpień
dokumentów

23

Listy czempionów w
uporządkowaniu g(d)



Możemy złożyć listy czempionów
uporządkowaniem g(d)



Utrzymuj dla każdego termu listę
czempionów r docs z najwyższymi g(d) +
tf-idf

td



Szukaj top-K wyników wśród dokumentów
tylko z list czempionów

24

Listy high i low



Dla każdego termu utrzymujemy dwie listy
odwołań zwane high i low



Przyjmijmy, że high jest listą czempionów



Gdy przechodzimy wystąpienia dla pytania – na
początku przemierzamy tylko listy high



Jeśli otrzymamy więcej niż K docs, wybieramy top K i
stop



W przeciwnym przypadku szukamy dokumentów z list
low



Czy możemy użyć podobieństwa kosinusowego
bez globalnego g(d)



Metody podziału indeksu na dwa poziomy (tiers)

25

Uporządkowanie wystąpień wg
wpływu (impact)



Chcemy obliczać wyniki tylko dla
dokumentów , które mają odpowiednio
wysoki wf

t,d



Sortujemy każdą listę wystąpień wg wf

t,d



Teraz: nie wszystkie wystąpienia są we
właściwym porządku!



Jak możemy wyliczyć wyniki aby
wyciągnąć top K?



Dwa pomysły poniżej

26

1. Szybkie kończenie



Jeśli przechodzisz wystąpienia dla termu t ,
skończ po



Ustalonej liczbie r docs



lub



wf

t,d

spadnie poniżej pewnego progu



Wykonaj unie wynikowych zbiorów
wyników



Po jednym z wystąpieniu dla każdego termu z
pytania



Oblicz wyniki tylko dla dokumentów z tej
unii

27

2. Termy uporządkowane wg idf



Gdy rozpatrujemy wystąpienia termów
pytania



Przeglądaj wg malejącego idf



Termy o wysokim idf prawdopodobnie
najbardziej wpływają na wynik



Podczas uaktualniania wyniku dla każdego
termu



Zakończ jeśli wynik dla doc jest relatywnie
niezmieniony



Można zastosować kosinus lub inne wyniki
netto

28

Przycinanie klastrów:
preprocessing



Wybierz losowo N docs: nazwij je

liderami



Dla każdego innego dokumentu,
oblicz najbliższego lidera



Docs dołączone do lidera: to jego
następniki;



Prawdopodobnie: każdy lider ma ~
N następników.

29

Przycinanie klastrów:
przetwarzanie pytań



Przetwarzaj pytania w następujący
sposób:



Dla danego pytania Q, znajdź
najbliższego lidera L.



Wyszukaj K najbliższych docs z
nastepników tego L.

30

Wizualizacja

Query

Leader

Follower

31

Dlaczego używamy losowe
próbkowanie



Jest szybkie



Liderzy odwzorowują rozkład danych

32

Podejście ogólne



Utrzymuj każdy następnik dołączony do
b1=3 (powiedzmy) najbliższych liderów.



Z pytania, znaleźć b2=4 (powiedzmy)
najbliższych liderów i ich następniki.



Możesz powtarzać konstrukcję
lider/następnik.

33

Parametryczne i strefowe
indeksy



Do tej pory dokument był sekwencją
termów



W praktyce dokumenty mają wiele części –
niektóre o specjalnym znaczeniu:



Autor



Tytuł



Data publikacji



Język



Format



etc.



Tworzą one metadane dla dokumentu

34

Pola



Czasami chcemy wyszukiwać wg metadanych



Np.: znajdź docs autorstwa Williama Shakespeare
w roku 1601, zawierające alas poor Yorick



Rok = 1601 jest przykładem pola



Tak samo, nazwisko autora = shakespeare, itd



Indeks dla pól lub parametrów: wystąpienia
dla dla każdej wartości pola



Czasami tworzą drzewa zakresowe (np.: dla dat)



Pytania o pola zwykle są traktowane jako
koniunkcje



(doc musi być autorstwa shakespeare)

35

Strefa



Strefa jest częścią dokumentu zawierającą
określony tekst np.:



Tytuł



Abstrakt



Literatura …



Budowane są indeksy odwrotne
pozwalające na przetwarzanie pytań



Np.: “znajdź dokumenty z merchant w
strefie tytuł i dla pytania gentle rain”

36

Przykładowe indeksy strefowe

Kodowanie stref w słowniku vs. wystąpienia.

37

Indeksy poziomowe



Podziel wystąpienia na hierarchię list



Najważniejsze



…



Najmniej ważne



Podział może być wg g(d) lub innej miary



Indeks odwrotny jest dzielony na warstwy
wg malejącej ważności



W czasie przetwarzania pytania używamy
najwyższą warstwę chyba, że nie uzyskamy
K docs



Jeśli tak przechodzimy do niższych warstw

38

Przykład indeksu warstwowego

39

Bliskość termów pytania



Pytania tekstowe: to zbiór termów wpisanych
do okienka pytania – typowe dla web



Użytkownicy wolą dokumenty, w których
termy z pytania są blisko siebie



Niech w będzie najmniejszym oknem w doc
zawierającym wszystkie termy pytania np.:



Dla pytania strained mercy najmniejsze okno
w doc The quality of

mercy is not strained

jest 4 (słowa)



Czy chcecie funkcję wynikową
uwzględniającą to – jak?

40

Parsery pytań



Pytania tekstowe mogą tworzyć jedno lub wiecej
pytań do indeksów, np.: pytanie

rising interest

rates



Przetwarzaj pytanie jako pytanie o frazę



Jeśli <K docs zawierających frazę rising interest rates,
przetwarzaj dwa pytania o frazę rising interest i
interest rates



Jeśli ciągle mamy <K docs, przetwarzaj pytanie w
przestrzeni wektorowej rising interest rates



Rankinguj dopasowanie docs wg wyników dla
przestrzeni wektorowej



Ta sekwencja została wytworzona przez parser
pytania

41

Agregacja wyników
dopasowania



Widzieliśmy, że funkcje dopasowania
mogą łączyć kosinus, statyczną jakość,
bliskość itd



Jak stwierdzić, która kombinacja jest
najlepsza?



W wielu aplikacjach – dobierane przez
ekspertów



Coraz powszechniejsze: uczenie
maszynowe

42

Złożenie w całość omawianych
części

43