Title

Introduction to Information
Retrieval

Wyszukiwanie z rankingiem



Dotąd wszystkie pytania były boolowskie.



Dokumenty albo pasowały albo nie.



To jest dobre dla użytkowników-ekspertów którzy
precyzyjnie znają swoje potrzeby i kolekcję.



Dobre także dla aplikacji: aplikacje mogą łatwo
przetworzyć tysiące wyników.



Nie dobre dla większości użytkowników.



Większość użytkowników nie potrafi pisać pytań
boolowskich (albo potrafią, ale myślą że to za dużo
roboty).

 Większość użytkowników nie chce przedzierać się

przez tysiące wyników.



Jest to prawdą szczególnie dla wyszukiwań webowych.

Introduction to Information
Retrieval

Problem z wyszukiwaniem
boolowskim: wszystko albo nic



Boolowskie pytania często dają za mało
wyników (=0) or lub za dużo (tysiące)
wyników.



Query 1: “zjadacz” → 225 000 trafień



Query 2: “mały podziemny zjadacz
kamyczków” : 0 trafień



Wymaga dużej wprawy zadanie pytania na
które będzie odpowiednia liczba trafień.



AND daje za mało; OR daje zbyt dużo

Introduction to Information
Retrieval

Modele wyszukiwania z
rankingiem



Modele wyszukiwania z rankingiem

zwracają

listę dokumentów z kolekcji najlepiej
pasujących do pytania, a nie zbiór pasujący
do pytania



Pytania tekstowe

: zamiast pytań złożonych

wyrażeń języka i operatorów - jedno lub
więcej słów w języku naturalnym



W zasadzie, są to dwa oddzielne modele, ale
w praktyce rankingowe modele
wyszukiwania są używane razem z pytaniami
tekstowymi i odwrotnie

Introduction to Information
Retrieval

Wszystko albo nic: nie ma
problemu w wyszukiwaniu
rankingowym



Kiedy system produkuje uporządkowany
zbiór wyników to duże zbiory wyników nie
są problemem



Oczywiście, rozmiar zbioru wyników nie
stwarza problemów



Pokazujemy zwykle pierwsze k ( ≈ 10) wyników



Nie przytłaczamy użytkownika



Przesłanka: algorytm rankingu działa

Introduction to Information
Retrieval

Dopasowanie jako podstawa
wyszukiwania z rankingiem



Mamy nadzieję, że zwracamy
uporządkowane dokumenty w porządku
najbardziej prawdopodobnej użyteczności
dla użytkownika



Jak możemy uporządkować dokumenty w
kolekcji ze względu na pytanie?



Przypisać dopasowanie – powiedzmy [0, 1]
– do każdego dokumentu



To jest dopasowanie mierzące jak dobrze
dokument i pytanie są „dopasowane”.

Introduction to Information
Retrieval

Wartość dopasowania pytanie-
dokument



Potrzebujemy metodę przypisywania
wartości dla pary pytanie/dokument



Zacznijmy od jedno-termowego pytania



Jeśli term pytania nie wystąpi w
dokumencie: wynik ma być 0



Tim częstszy jest term w dokumencie tym
wyższe dopasowanie (powinno być)



Obejrzymy kilka alternatywnych podejść.

Introduction to Information
Retrieval

Ujęcie 1: miara Jaccarda



Przypomnienie: Powszechnie stosowana
miara nakładania się dwóch zbiorów A i B



jaccard(A,B) = |A ∩ B| / |A ∪ B|



jaccard(A,A) = 1



jaccard(A,B) = 0 if A ∩ B = 0



A i B nie muszą być takich samych
rozmiarów.



Zawsze przypisuje między 0 i 1.

Introduction to Information
Retrieval

Miara Jaccarda: przykład
dopasowania



Jaka jest miara podobieństwa Jaccarda dla
poniższych dokumentów?



Pytanie: ides of march (idy
marcowe)



Dokument 1: caesar died in march



Dokument 2: the long march

Introduction to Information
Retrieval

Problemy z miarą Jaccarda dla
dopasowania



Miara nie uwzględnia

częstości termów

(ile

razy term wystąpił w dokumencie)



Rzadkie termy w kolekcji niosą więcej
informacji niż częste termy. Jaccard nie
uwzględnia tej informacji



Potrzebujemy bardziej złożonego sposobu
normalizacji dla długości



Później użyjemy



. . . zamiast |A ∩ B|/|A ∪ B| (Jaccard) do
normalizacji lub normalizacji długości.





Introduction to Information
Retrieval

Macierze licznikoweTerm-
dokument



Rozpatrzmy liczbę wystąpień termu w
dokumencie:



Każdy dokument jest wektorem licznikowym w ℕ

kolumna poniżej

Introduction to Information
Retrieval

Model worka słów



Reprezentacja wektorowa nie uwzględnia
porządku słów w dokumencie



John is quicker than Mary

Mary is quicker

than John

mają takie same wektory



Nazywamy to modelem worka słów.



W pewnym sensie jest to krok wstecz:
Indeks pozycyjny był w stanie rozróżnić te
dwa dokumenty.



Wrócimy do tego później.



Obecnie: model worka słów

Introduction to Information
Retrieval

Częstość termów tf



Częstość termów tf

t,d

termu t w dokumencie d

definiujemy jako liczbę wystąpień t w d.



Chcemy wykorzystać tf do obliczania wartości
dopasowania pytanie-dokument. Ale jak?



Częstość termów w najprostszej postaci nie
wystarcza:



Dokument z 10 wystąpieniami jest bardziej
relewantny niż dokument z 1 wystąpieniem termu.



Ale nie dziesięć razy bardziej relewantny.



Relewancja nie rośnie proporcjonalnie ze
wzrostem częstości termów.

Uwaga: częstość =

liczność w IR

Uwaga: częstość =

liczność w IR

Introduction to Information
Retrieval

Waga logarytmiczna częstości



Waga logarytmiczna częstości termu to



0 → 0, 1 → 1, 2 → 1.3, 10 → 2, 1000 → 4, etc.



Wynik dla pary dokument-pytanie: suma po
termach t w q i d:



wynik



Wynik jest 0 jeśli nie ma termów pytania w
dokumencie.









otherwise

log

t,d











)

log

Introduction to Information
Retrieval

Częstość dokumentów



Rzadkie termy niosą więcej informacji niż
częste



Przypomnijmy stop słowa



Rozpatrzmy term w pytaniu, który jest rzadki
w kolekcji (np.: arachnocentric)



Dokument zawierający ten term jest
najprawdopodobniej relewantny do pytania
arachnocentric



→ Potrzebujemy duże wagi dla rzadkich
termów takich jak arachnocentric.

Introduction to Information
Retrieval

Częstość dokumentów - cd



Częste termy są mniej informacyjne niż rzadkie



Rozpatrzmy term pytania częsty w kolekcji (np.:
high, increase, line)



Jest bardziej prawdopodobne, że dokument z tym
termem jest relewantny niż bez tego termu



Ale nie jest on pewnym wskaźnikiem relewancji.



→ Dla częstych termów, potrzebujemy duże
dodatnie wagi dla słów takich jak like high,
increase, and line



Ale niższe wagi niż dla rzadkich termów.



Użyjemy w tym celu częstości dokumentów (df) .

Introduction to Information
Retrieval

Waga idf



to częstość dokumentów dla t: liczba

dokumentów zawierających t



jest odwrotną miarą informacyjności t



 N



Definiujemy idf (odwrotność częstości
dokumentów) dla t jako



Używamy log (N/df

) zamiast N/df

aby “tłumić”

efekt idf.

)

/df

(

log

idf



usuwamy podstawę logarytmu jako nieistotną.

Introduction to Information
Retrieval

Przykład idf dla N = 1 million

term

idf

calpurnia

1 6

animal

100 4

sunday

1,000 3

fly

10,000 2

under

100,000 1

the

1,000,000 0

Jest jedna wartość idf dla każdego termu t w kolekcji.

)

/df

(

log

idf



Introduction to Information
Retrieval

Wpływ idf na ranking



Czy idf wpływa na ranking pytań jedno-
termowych jak



iPhone



idf nie wpływa na ranking pytań z jednym
termem



idf wpływa na ranking pytań co najmniej dwu -
termowych



Dla pytania

capricious person

, waga idf

spowoduje wystąpień

capricious

będzie się

liczyć znacznie bardziej w końcowym rankingu
dokumentów niż wystąpienia

person

Introduction to Information
Retrieval

Częstość kolekcji vs. Częstość
dokumentu



Częstość kolekcji t to liczba wystąpień t w
kolekcji, licząc wystąpienia wielokrotne.



Przykład:



Which word is a better search term (and
should Które słowo jest lepszym terminem
wyszukiwawczym (czy ma mieć wyższą
wagę)?

Słowo

Częstość kolekcji

- cf

Częstość dokumentu -

insurance

10440

3997

try

10422

8760

Introduction to Information
Retrieval

Ważenie tf-idf



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



Jest to najlepszy znany schemat ważenia w
wyszukiwaniu informacji



Uwaga: to “-” w tf-idf jest myślnikiem, a nie
minusem!



Inne nazwy: tf.idf, tf x idf



Wzrasta z liczbą wystąpień w dokumencie



Wzrasta z rzadkością termu w kolekcji

)

(

log

)

log

(







Introduction to Information
Retrieval

Ostateczny ranking
dokumentów dla pytania



Score

(q,d) 

tf.idf

t,d

tqd



Introduction to Information
Retrieval

Dokumenty jako wektory



Więc mamy |V|-wymiarową przestrzeń
wektorową



Termy są osiami tej przestrzeni



Dokumenty są punktami lub wektorami w
tej przestrzeni



Bardzo wiele wymiarów: dziesiątki
milionów wymiarów jeśli zastosować to do
webowych silników wyszukiwawczych



To są bardzo rzadkie wektory – większość
składowych to zera.

Introduction to Information
Retrieval

Pytania jako wektory



Kluczowa idea 1:

wykonać to samo dla pytań:

przedstaw je jako wektory w przestrzeni



Kluczowa idea 2:

utwórz ranking dokumentów

zgodnie z ich bliskością do pytania w tej
przestrzeni



Bliskość = podobieństwo wektorów



Bliskość ≈ odwrotność odległości



Przypomnienie: robimy to ponieważ chcemy
odejść od 0 lub 1 modelu boolowskiego.



Zamiast tego: rankinguj bardziej relewantne
dokumenty wyżej niż mniej relewantne
dokumenty

Introduction to Information
Retrieval

Formalizacja bliskości w
przestrzeni wektorowej



Pierwsza myśl: odległość między dwoma
punktami



( = odległość między końcami dwóch
wektorów)



Odległość euklidesowa?



Odległość euklidesowa jest złym
pomysłem . . .



. . . Ponieważ odległość euklidesowa jest

większa

dla wektorów

o różnych

długościach

Introduction to Information
Retrieval

Dlaczego odległość jest
złym pomysłem

Odległość
euklidesowa
między

jest

większa nawet jeśli
rozkład termów w
pytaniu i

rozkład termów w
dokumencie

są

bardzo podobne.

Introduction to Information
Retrieval

Użyj kąta zamiast odległości



Eksperyment myślowy: weź dokument d i
doklej go do niego. Nazwij go d′.



“Semantycznie” d i d′ mają taką samą
zawartość



Odległość euklidesowa między tymi
dokumentami będzie jednak duża



Kąt między tymi dokumentami jest 0, i
odpowiada maksymalnemu podobieństwu.



Główna zasada: porządkuj dokumenty według
ich kąta z pytaniem.

Introduction to Information
Retrieval

Od kątów do kosinusów



Następujące dwa zapisy są równoważne.



Ranking dokumentów w porządku malejącym
kąta między pytaniem i dokumentem



Ranking dokumentów w rosnącym porządku
kosinusa (pytanie, dokument)



Kosinus jest funkcją malejącą
monotonicznie dla przedziału [0

, 180

]

Introduction to Information
Retrieval

Normalizacja długości



A vector can be (length-) normalized by dividing
each of its components by its length – for this we
use the L

norm:



Dividing a vector by its L

norm makes it a unit

(length) vector (on surface of unit hypersphere)



Effect on the two documents d and d′ (d
appended to itself) from earlier slide: they have
identical vectors after length-normalization.



Long and short documents now have comparable
weights





i i



Introduction to Information
Retrieval

cosine(query,document)













)

cos(



Dot product

Unit vectors

is the tf-idf weight of term i in the query

is the tf-idf weight of term i in the document

cos(q,d) is the cosine similarity of q and d … or,
equivalently, the cosine of the angle between q and d.

Introduction to Information
Retrieval

Cosine for length-normalized
vectors



For length-normalized vectors, cosine
similarity is simply the dot product (or
scalar product):

for q, d length-

normalized.



cos(

q ,

d ) 

q 

d 

i1



Introduction to Information
Retrieval

Cosine similarity amongst 3
documents

term

SaS

PaP

affection

115

jealous

gossip

wuthering

How similar are
the novels

SaS

: Sense and

Sensibility

PaP

: Pride and

Prejudice, and

: Wuthering

Heights?

Term frequencies (counts)

Note: To simplify this example, we don’t do idf weighting.

Introduction to Information
Retrieval

3 documents example contd.

Log frequency weighting

term

SaS

PaP

affection

3.06

2.76

2.30

jealous

2.00

1.85

2.04

gossip

1.30

1.78

wutheri

2.58

After length normalization

term

SaS

PaP

affection

0.789

0.832

0.524

jealous

0.515

0.555

0.465

gossip

0.335

0.405

wutherin

0.588

cos(SaS,PaP)

≈

0.789 × 0.832 + 0.515 × 0.555 + 0.335 × 0.0 + 0.0 × 0.0
≈

0.94

cos(SaS,WH)

≈

0.79

cos(PaP,WH)

≈

0.69

Why do we have cos(SaS,PaP) > cos(SAS,WH)?

Introduction to Information
Retrieval

Weighting may differ in queries
vs documents



Many search engines allow for different
weightings for queries vs. documents



SMART Notation: denotes the combination in
use in an engine, with the notation ddd.qqq,
using the acronyms from the previous table



A very standard weighting scheme is: lnc.ltc



Document: logarithmic tf

(l as first

character)

, no idf and cosine normalization



Query: logarithmic tf (l in leftmost column),
idf (t in second column), no normalization …

A bad idea?

Introduction to Information
Retrieval

tf-idf example: lnc.ltc

Term

Query

Document

Pro

tf-

raw

tf-

idf

n’liz

tf-

raw

tf-wt

n’liz

auto

0 5000 2.3

1 0.52

best

1 5000

1.3 1.3 0.34

car

1 1000

2.0 2.0 0.52

1 0.52 0.27

insuranc

1 1000 3.0 3.0 0.78

1.3

1.3 0.68 0.53

Document: car insurance auto insurance
Query: best car insurance

Exercise: what is N, the number of docs?

Score = 0+0+0.27+0.53 = 0.8

Doc length =



 0

1

1.3

1.92

Introduction to Information
Retrieval

Summary – vector space
ranking



Represent the query as a weighted tf-idf
vector



Represent each document as a weighted tf-
idf vector



Compute the cosine similarity score for the
query vector and each document vector



Rank documents with respect to the query
by score



Return the top K (e.g., K = 10) to the user

Document Outline