Information Retrieval (AD-603 (C)) Unit 2 Notes

How unit 2 is examined

This unit covers the classic retrieval models (Boolean, vector space, probabilistic and language model, LSI), the weighting and similarity used to rank, the pre-processing and inverted index that make search fast, and query improvement by feedback. No question from this unit appeared in the supplied papers, so every topic is short but complete.

Boolean and Vector space retrieval models

Not asked since 2022

Definition. The Boolean model retrieves documents that exactly satisfy a query built from terms joined by AND, OR and NOT, while the vector space model represents documents and queries as weighted term vectors and ranks documents by their similarity to the query.

Key points.

The Boolean model gives an exact-match result set with no ranking, so a document either matches or it does not.
It is precise and easy to implement, but users find complex Boolean queries hard to write, and it often returns too many or too few documents.
In the vector space model each term is a dimension, and a document or query is a vector of term weights such as TF-IDF.
Vector space ranking gives partial matching and a ranked list, but it assumes terms are independent of each other.

Term weighting - TF-IDF weighting

Definition. TF-IDF weights a term by how often it occurs in a document (term frequency) multiplied by how rare it is across the collection (inverse document frequency).

Formula. $w_{t,d} = tf_{t,d} \times \log\frac{N}{df_t}$, where $N$ is the number of documents and $df_t$ the number containing $t$.

Key points.

A high term frequency shows that the term is important inside that document.
A rare term has a high IDF, so it discriminates well, while a word in almost every document gets a weight near zero.
The weight is highest for a term that is frequent in one document and rare elsewhere.
Raw $tf$ is often damped as $1+\log tf$ so that repetition does not dominate.

Cosine similarity

Definition. Cosine similarity is the cosine of the angle between the query vector and the document vector, so it measures direction rather than length.

Formula. $\cos(q,d)=\dfrac{\vec q\cdot\vec d}{|\vec q|\,|\vec d|}=\dfrac{\sum_i q_i d_i}{\sqrt{\sum_i q_i^2}\sqrt{\sum_i d_i^2}}$

Key points.

The value lies between 0 and 1 for non-negative weights, where 1 means identical direction.
Dividing by the vector lengths normalises for document length, so a long document is not favoured only for its size.
Documents are ranked in decreasing order of cosine score with the query.

Pre-processing

Definition. Pre-processing converts raw text into index terms through tokenization, stop-word removal, normalization and stemming.

Key points.

Tokenization splits the text into tokens at spaces and punctuation and usually lowercases them.
Stop-word removal drops very common words such as "the" and "is", which saves index space and carries little meaning.
Stemming reduces words to a root form, for example "connected" and "connection" to "connect", so that variants match.
The same pre-processing must be applied to both documents and queries.

Inverted indices - efficient processing with sparse vectors

Definition. An inverted index maps each term to a postings list of the documents (with frequencies and positions) that contain it.

Key points.

Document vectors are sparse because each document uses only a tiny part of the vocabulary, so storing only non-zero entries saves space.
A query reads only the postings lists of its own terms instead of scanning every document.
The index has a dictionary of terms and postings sorted by document ID, which lets AND queries merge two lists in linear time.
Scores are accumulated per document while walking the lists, then the top results are returned.

Language Model based IR - Probabilistic IR

Definition. Probabilistic IR ranks documents by their probability of relevance to the query, and language model IR ranks them by the probability $P(q\mid M_d)$ that the document's language model generates the query.

Formula. $P(q\mid M_d)=\prod_{t\in q}P(t\mid M_d)$, with $P(t\mid M_d)=\dfrac{tf_{t,d}}{L_d}$ smoothed to avoid zeros.

Key points.

The probability ranking principle says documents should be ranked by decreasing probability of relevance to give the best results.
Each document has its own unigram language model estimated from its own text.
Smoothing, for example mixing with the collection model, stops one missing query term from making the score zero.

Latent Semantic indexing

Definition. Latent Semantic Indexing applies singular value decomposition to the term-document matrix to keep only the top $k$ concepts, so that documents and queries are compared in a reduced semantic space.

Formula. $A \approx U_k \Sigma_k V_k^{T}$

Key points.

It handles synonymy, because terms that occur in similar contexts end up close together in the reduced space.
It reduces the noise and dimension of the sparse term-document matrix.
A query can match a document that shares no words with it if the concepts are alike.
The SVD is costly to compute and the choice of $k$ is difficult.

Relevance feedback and query expansion

Definition. Relevance feedback uses the documents the user marks as relevant or non-relevant to reformulate the query, while query expansion adds related terms to the original query.

Formula. Rocchio: $\vec q_m=\alpha\vec q_0+\beta\frac{1}{|D_r|}\sum_{d\in D_r}\vec d-\gamma\frac{1}{|D_{nr}|}\sum_{d\in D_{nr}}\vec d$

Key points.

Rocchio moves the query vector toward the centroid of relevant documents and away from the non-relevant ones.
Pseudo-relevance feedback assumes the top-ranked documents are relevant, so no user effort is needed.
Query expansion adds synonyms or thesaurus terms to improve recall, at some cost in precision.

Last-minute revision

Boolean model: exact match with AND, OR, NOT and no ranking.
Vector space model: documents and queries as weighted term vectors, ranked by similarity.
TF-IDF: $tf \times \log(N/df)$.
Cosine: $\dfrac{q\cdot d}{|q||d|}$, ranges 0 to 1.
Pre-processing order: tokenize, remove stop words, normalize, stem.
Inverted index: term to postings list, best suited to sparse vectors.
Language model IR: $P(q\mid M_d)$ with smoothing.
LSI: SVD of the term-document matrix, keep the top $k$ concepts.
Rocchio: $\alpha q_0+\beta$ (relevant centroid) $-\gamma$ (non-relevant centroid).
Query expansion improves recall.

Memory hooks

TF-IDF: "frequent here, rare there".
Cosine looks at the angle, not the length.
Inverted index works like a book's back-of-the-book index.
Rocchio: pull toward the good, push from the bad.
LSI: SVD squeezes words into concepts.

Coverage checklist

Boolean and Vector space retrieval models: no past questions, definition and points covered.
Term weighting - TF-IDF weighting: no past questions, formula covered.
cosine similarity: no past questions, formula covered.
Pre-processing: no past questions, covered.
Inverted indices - efficient processing with sparse vectors: no past questions, covered.
Language Model based IR - Probabilistic IR: no past questions, formula covered.
Latent Semantic indexing: no past questions, formula covered.
Relevance feedback and query expansion: no past questions, Rocchio covered.

Account

Information Retrieval (AD-603 (C)) - Unit 2 Short Notes

How unit 2 is examined

Boolean and Vector space retrieval models

Term weighting - TF-IDF weighting

Cosine similarity

Pre-processing

Inverted indices - efficient processing with sparse vectors

Language Model based IR - Probabilistic IR

Latent Semantic indexing

Relevance feedback and query expansion

Last-minute revision

Memory hooks

Coverage checklist