W4 Vector Space Model

Question 1

1. What is Ranked Retrieval?
2. Formalization Definition of Ranked Retrieval

Answer 1

1. Also called Relevance Ranking. The system returns an ordering of the (top) documents in the collection for a query.
2. For each query Qi and doc Dj, compute a score RSV(Qi, Dj)
   * RSV: Retrieval Status Value
   * RSV theory neural, could be distance based, probability based
   * Ordinal scale (supports > < =)
   * Value increase with relevance

Question 2

1 What’s set-based approach for Ranked Retrieval?

Answer 2

Query and doc are each a set of terms

Question 3

Give the calculation of Jaccard Coefficient

Answer 3

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

|A ∩ B|: Commonality
|A ∪ B|: Length Normalization
A and B don’t have to be the same size
We always assigns a number from [0, 1]

RSV(Q,D) = jaccard(terms(Q), terms(D))

Question 4

What’s the query-doc match score computed by jaccard coefficient for each of the 2 docs: (common stop words are removed):

Query: Ides of March -> {ide, march}
Doc 1: Caesar died in March -> {caesar, die, march}
Doc 2: the long march -> {long, march}

Answer 4

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

jaccard ({ide, march}, {caesar, dy, march}) = 1 / 4
jaccard ({ide, march}, {long, march}) = 1 / 3

Question 5

Give calculation of:
Jaccard Distance?
Dice coefficient?

Answer 5

Jaccard Distance = 1 - Jaccard Similarity

Dice(A, B) = 2x|A ∩ B| / (|A| + |B| )=2J/(J+1)

Question 6

What is a metric?

Answer 6

In fact a distance function.
* identity: d(x, y)=0 => x=y
* Symmetry: d(x, y) = d(y, x)
* Triangle inequality: d(x, z) <= d(x, y) + d(y, z)
* Non negativity: d(x, y) >= 0

Question 7

What are the issues with Jaccard for scoring?

Answer 7

1. we need to normalize for length (of the document or query)
2. Jaccard does not consider term frequency
3. Jaccard does not consider that rare tems in a collection are more informative than frequent terms

Question 8

2 What’s term-weighting approach for Ranked Retrieval?

Answer 8

Measure term importance in docs
Vector Space Model (VSM)

Question 9

What is bag of words model?

Answer 9

multiset of words, we don’t care the ordering in a doc.
john loves mary
mary loves john
they have the same vectors
The positional index can distinguish two docs

Question 10

What is term frequency (TF)?

Answer 10

The term frequency tf (t,d) of term t in document d is defined as
the number of times that t occurs in d.

raw term frequency is not what we want because (Relevance does not increase proportionally with term frequency) so we use log normalization:

The log frequency weight of term t in d is:
w_(t, d) = 1 + log(tf) if tf>0
= 0 else
w is the quantitative evidence of d being relevant for query t

score a doc for a query: sum the w

Question 11

What is document frequency (DF)? How do we interpret it?

Answer 11

df(t) is the document frequency of t: the number of
documents that contain t

Rare terms are more informative than frequent terms (eg. stop words and the word arachnocentric in a doc) A document containing arachnocentric is more likely to be relevant than a document that does not contain it

Question 12

1. What is Inverse Document Frequency (IDF)?
2. How to calculate TF-IDF?

Answer 12

1. idf = log (N/df)

N: number of docs in the collection
idf quantifies how surprised we are to see term t in a doc, again, logarithm is used for better approximation

2. TF-IDF = TF * IDF
   TF-IDF increases with number of occurances within the doc, and with rarity of the term in the collection.
   TF-IDF is evidence of d being relevant when looking for t

Question 13

Document ranking in VSM

Answer 13

Docs are vectors of term weights in the space

The vector space is |V|-dimensional (|V|: no. of terms in the vocabulary)
terms are axes of the space

***** Vectors are High-dimensional, sparse

Question 14

Queries as vectors too, how do we rank?

Answer 14

• represent them as vectos in space, rank docs according to their proximity to the query in the space = similarity of the vectors

The angle between vectors shows the similarity

Question 15

Give formula for cosine similarity (dot product) of two vectors

Answer 15

cos(q, d) = (q * d) /(|q|*|d|)
= \sum (qi * di) / \sqrt (\sum qi^2) * \sqrt (\sum di^2)

q, d: length-normalized: ||x|| = \sqrt (\sum xi^2)

Question 16

@#@ LET OP @#@

The calculation in this chapter is very important and will present in the exam therefore please refer to the slides for examples and do the calculations yourself

Answer 16

tf, df, idf, TF-IDF, length normalization, dot product, cosine similarity

Question 17

Summary: Vector Space ranking with term weighting

Answer 17

• represent each document and query as weighted tf-idf vector
• compute cosine similarity score for the query vector and each document vector
• rank documents with respect to the query by score
• return top K to the user

Question 18

scope vs. verbosity hypothesis

Answer 18

scope: a long document consists of a number of unrelated short documents concatenated together

verbosity: a long document covers a similar scope to a short document, but uses more words

Question 19

Criterias for comparing IR models/systems

Answer 19

effectiveness, efficiency, explainability, parsimony (Occam’s Razor)