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