UNIT 1: Information Retrieval Fundamentals and Techniques

I. Introduction to Information Retrieval

Definition and Scope of IR

Information Retrieval (IR) is the process of searching, identifying, and retrieving relevant information resources (documents, videos, images) from large collections based on a user's query. Its scope encompasses:

• Text retrieval (web search, digital libraries)

• Multimedia retrieval (images, audio, video)

• Structured data retrieval (databases, XML)

• Personalized and context-aware retrieval

Core IR Process and Key Components

The standard IR process is a pipeline:

1. Query Formulation: User expresses information need as a query (keywords, natural language).

2. Document Representation: Documents are processed and indexed (see Section II).

3. Retrieval & Ranking: System matches query against index, computes a relevance score for each document using a ranking function.

4. Result Presentation: Top-ranked documents are presented, often with snippets and highlighting.

[!TIP] Exam Focus: Be prepared to draw and explain this 4-step pipeline. Questions often ask for "key components" – list these four.

Role of Artificial Intelligence in IR

AI enhances IR through:

• Query Understanding: NLP for query expansion, spelling correction, intent detection.

• Advanced Ranking: Machine Learning (Learning to Rank - LTR) models (e.g., LambdaMART, neural rankers) that go beyond simple term matching.

• Personalization: User modeling, click history analysis to re-rank results for individual users.

• Semantic Matching: Using embeddings (Word2Vec, BERT) to match query and document meaning, not just keywords.

Traditional IR Systems vs. Web Search

[!TIP] Common Pitfall: Do not just say "web search is bigger." Focus on architectural differences (centralized vs. distributed) and the introduction of link analysis as a core ranking signal unique to the web.

II. Document Processing and Indexing

Document Preprocessing Procedures

A sequence of steps to convert raw text into indexable terms:

1. Tokenization: Split text into tokens (words, numbers). Challenge: Handling punctuation, hyphens, email addresses.

2. Stop-word Removal: Filter out common, low-meaning words (the, is, in). Uses a stop-list. Reduces index size.

3. Stemming: Crudely chop word endings using heuristic rules (e.g., "computing", "computer" → "comput"). Fast but imprecise.

4. Lemmatization: Use vocabulary/morphology to return base lemma (e.g., "better" → "good"). More accurate but slower.

[!TIP] Exam Tip: Know the difference: Stemming is rule-based and aggressive; Lemmatization is dictionary-based and precise.

Term Weighting Schemes: TF-IDF

TF-IDF (Term Frequency-Inverse Document Frequency) weights a term's importance in a document relative to a collection.

• Term Frequency (TF): Frequency of term t in document d. Often log-scaled: tf(t,d) = 1 + log(freq(t,d)) if freq>0, else 0.

• Inverse Document Frequency (IDF): Measures term rarity across collection D. idf(t,D) = log(N / df(t)), where N = total docs, df(t) = docs containing t.

• TF-IDF Score: w(t,d) = tf(t,d) * idf(t,D)

Interpretation: High TF-IDF for a term in a document means the term is frequent in that document but not common across the collection → likely a good descriptor for that document.

Applications: Document ranking (vector space model), keyword extraction, feature representation.

[!BOX] TF-IDF Formula:

$$ \text{TF-IDF}(t, d, D) = \text{tf}(t,d) \times \text{idf}(t,D) = \left(1 + \log(\text{freq}(t,d))\right) \times \log\left(\frac{N}{\text{df}(t)}\right) $$

Index Compression

Benefits:

• Reduces disk/memory footprint → more indices fit in RAM → faster query processing.

• Reduces I/O operations (disk seeks, network transfer for distributed IR).

• Lowers storage costs.

Key Techniques:

1. Gap Encoding: Store differences (gaps) between sorted document IDs (e.g., store [105, 120, 150] as [105, 15, 30]). Gaps are smaller numbers, better for compression.

2. Variable-Byte (VB) Encoding: Uses one or more bytes. First byte's high bit indicates if more bytes follow. Simple, fast decoding.

3. Gamma Encoding ( Elias Gamma): For a gap g, write len(g) in unary, followed by g in binary without leading 1. Optimal for small, power-law distributed gaps.

Example (VB): Gap 300 (binary 100101100). Split into 7-bit chunks: 0010010 (18) and 1101100 (108). Prefix continuation bits: 0 for last byte, 1 for others. Bytes: [1|0010010] = 0xA2, [0|1101100] = 0x6C. Stored as A2 6C.

Web Crawling

A crawler (spider, bot) systematically browses the web to create a copy of pages for the search engine's index. Advantages & Needs:

• Freshness: Discover and update changed pages.

• Coverage: Find as many relevant pages as possible.

• Scalability: Must handle billions of pages efficiently (polite, distributed crawling).

• Importance: Discover new pages and sites.

Challenges: Politeness (robots.txt), avoiding traps (spider traps), managing URL frontier, handling duplicate content.

Focused Crawling

A focused crawler aims to download pages relevant to a predefined topic (e.g., "machine learning papers"), rather than the entire web.

• Algorithm: Uses a classifier to predict relevance of a page before downloading (based on URL, anchor text, parent page context). Prioritizes URLs with high predicted relevance.

• Relevance Prediction: Often uses a naïve Bayes or similar classifier trained on examples of relevant/non-relevant pages.

• Use Cases: Building vertical search engines, topic-specific corpora for research, monitoring specific domains.

[!TIP] Key Difference: General crawler → maximize coverage. Focused crawler → maximize relevant coverage.

Structured Data Retrieval: XML IR

Standard IR treats documents as "bags of words." XML IR must handle structure (tags, hierarchy). System Requirements:

1. Structural Queries: Support queries like //author[contains(., "Smith")] (XPath, XQuery).

2. Indexing: Index both text content and structural elements (tags, paths). Often uses inverted index augmented with structural information (e.g., term -> (docID, element, position)).

3. Ranking: Combine content relevance (TF-IDF on text) with structural relevance (how well the result's structure matches the query's desired structure). E.g., a match in a <title> tag may be weighted higher than in <footer>.

III. Retrieval Models and Ranking Techniques

Ranking and Relative Score Retrieval Procedure

1. Scoring Function: Compute a relevance score score(q, d) for each candidate document d against query q. Common models: Boolean, Vector Space (cosine similarity with TF-IDF), Probabilistic (BM25), Language Modeling.

2. Sorting: Rank documents in descending order of their scores.

3. Result Presentation: Return top-k documents (e.g., top 10) as the result set.

[!TIP] Core Idea: IR is fundamentally about producing a ranked list, not a binary yes/no decision.

Relevance Feedback

A technique to improve retrieval performance by using information about which retrieved documents are relevant to the original query.

• Probabilistic Relevance Feedback (Rocchio Algorithm):

  • Idea: Move the query vector towards the centroid of relevant documents and away from the centroid of non-relevant documents.

  • Formula (for vector space model):

$$ \vec{q}_{\text{new}} = \alpha \vec{q}_{\text{old}} + \beta \frac{1}{|D_r|} \sum_{\vec{d}_j \in D_r} \vec{d}_j - \gamma \frac{1}{|D_{nr}|} \sum_{\vec{d}_k \in D_{nr}} \vec{d}_k $$

    where `D_r` = set of relevant docs, `D_nr` = set of non-relevant docs, `α, β, γ` are weights.

-   **Application:** Reformulate query for a second-round retrieval.

• Probabilistic Models: Estimate probabilities P(R|d,q) (probability document d is relevant to query q) using Bayes' rule and relevance feedback to update term weights.

[!TIP] Rocchio: Remember the + for relevant, - for non-relevant vector movement.

Latent Semantic Indexing (LSI)

A technique to overcome synonymy (different words for same concept) and polysemy (same word, different meanings) by mapping terms and documents into a latent semantic space.

• Method: Singular Value Decomposition (SVD).

  1. Build term-document matrix A (rows=terms, cols=docs, values=TF-IDF).

  2. Perform SVD: A ≈ T * S * D^T, where:

     • T: Term-Concept matrix (orthogonal)

     • S: Diagonal matrix of singular values (sorted descending)

     • D: Document-Concept matrix (orthogonal)

  3. Reduce dimensionality: Keep only the top k singular values/vectors (columns of T & D). This captures the most important latent concepts, filtering noise.

  4. Queries and new documents are projected into this k-dimensional space for similarity comparison (cosine similarity).

Example: Query "car" might retrieve documents about "automobile" because both map strongly to the same latent concept dimension.

Advantages:

• Handles synonymy effectively.

• Reduces dimensionality, potentially improving efficiency and noise reduction.

Limitations:

• Computationally expensive SVD on large matrices.

• Lack of interpretability of latent dimensions.

• Poor handling of polysemy (a single term forced into one dimension).

• Static; doesn't adapt to new terms easily.

[!BOX] LSI Core: A ≈ T_k * S_k * D_k^T (Low-rank approximation via truncated SVD).

IV. Web-Scale IR and Distributed Processing

MapReduce and Hadoop for IR

MapReduce is a programming model for processing massive datasets in parallel across clusters. Hadoop is an open-source implementation (HDFS + MapReduce).

Architecture for IR (Indexing):

1. Map Phase: Input is raw documents (from crawler). Each mapper processes a split:

   • Parses document.

   • Emits (term, docID) pairs for each term in the document.

2. Shuffle & Sort: Framework groups all values (docIDs) for the same key (term).

3. Reduce Phase: Each reducer receives a term and list of docIDs:

   • Computes document frequencies (df).

   • May compute TF for each (docID, tf) pair.

   • Emits (term, [ (docID1, tf1), (docID2, tf2), ... ]) as the inverted index.

4. Output is written to HDFS, partitioned for distributed storage.

Effectiveness Analysis:

• Scalability: Linear scalability. Add more nodes → process more data. Handles petabytes.

• Fault Tolerance: If a node fails, its tasks are automatically reassigned. Data is replicated in HDFS.

• Effectiveness for IR: Perfectly suited for inverted index construction, which is embarrassingly parallel (each document/term independent).

• Drawbacks: High overhead for small jobs; not ideal for iterative algorithms (like some ML) without extensions (Spark).

[!TIP] Remember: Map = extract (term, docID). Reduce = aggregate (list all docIDs for a term).

V. IR Applications and Machine Learning Integration

Content-Based Recommendation Systems

Recommends items (documents, movies) similar to those a user liked in the past, based on item features.

• Mechanism:

  1. Profile Creation: Represent user u by the aggregate feature vector of items they interacted with (e.g., liked documents' TF-IDF vectors).

  2. Feature Extraction: Represent each item i by a feature vector (e.g., TF-IDF of its text, genre tags, director for movies).

  3. Similarity Matching: Compute similarity sim(u, i) between user profile and item vector (cosine similarity common).

  4. Recommendation: Rank all candidate items by similarity, recommend top-N.

• Advantage: No "cold start" for new items if features are available.

• Limitation: Overspecialization (filter bubble); cannot recommend items outside user's profile scope.

Clustering in IR

Unsupervised grouping of documents into clusters (topics) without labels.

Agglomerative Clustering (Bottom-up)

• Procedure:

  1. Start: each document is its own cluster.

  2. Iterate: Find two closest clusters using a linkage criterion and merge them.

  3. Stop: when desired number of clusters k is reached.

• Linkage Criteria (Distance between clusters C1, C2):

  • Single Link: min_{x∈C1, y∈C2} dist(x,y) (chaining effect).

  • Complete Link: max_{x∈C1, y∈C2} dist(x,y) (tight clusters).

  • Average Link: avg_{x∈C1, y∈C2} dist(x,y) (compromise).

  • Centroid Link: Distance between cluster centroids.

• Output: Dendrogram (tree diagram) showing merge history. Cut at level k to get k clusters.

Nearest Neighbor Clustering (e.g., K-Means)

• Procedure:

  1. Choose K initial centroids (randomly or via heuristics).

  2. Assign: Assign each document to nearest centroid (using Euclidean/cosine distance).

  3. Update: Recompute centroids as mean of assigned documents.

  4. Repeat steps 2-3 until convergence (centroids stable).

• Choosing K:

  • Elbow Method: Plot Within-Cluster Sum of Squares (WCSS) vs. K. Look for "elbow" where decrease slows.

  • Silhouette Score: Measures how similar an object is to its own cluster vs. other clusters. Range [-1,1]. Higher average score indicates better K.

[!TIP] Agglomerative vs. K-Means: Agglomerative is hierarchical (no need to pre-specify K initially, gives dendrogram). K-Means is partitional (needs K, faster for large N).

Classification in IR

Supervised learning: assign a document to a predefined category (e.g., Sports, Politics).

Naïve Bayesian Classification

• Principle: Based on Bayes' Theorem with strong independence assumption: features (words) are conditionally independent given the class.

$$ P(C|D) \propto P(C) \prod_{i=1}^{n} P(w_i|C) $$

where `C` = class, `D` = document (set of words `w_i`).

• Training:

  1. For each class c, compute prior P(c) = (# docs in c) / (total docs).

  2. For each term t and class c, compute likelihood P(t|c) = (count(t in c) + α) / (total terms in c + α*V) (Laplace smoothing, V=vocab size).

• Prediction: For a new document, compute P(c|D) for all classes (using log-prob to avoid underflow). Assign class with highest score.

• Application: Spam filtering, topic categorization, sentiment analysis.

• Limitations:

  • Independence assumption rarely holds (words are correlated).

  • Zero probability problem (solved by smoothing).

  • Can be outperformed by more complex models (SVMs, neural nets).

Result Presentation: Snippet Generation

A snippet is a short excerpt from a retrieved document, shown with the search results to help user judge relevance. Techniques:

1. Static Snippet: First N characters/words of document. Simple but often uninformative.

2. Query-Based Snippet (Most Common):

   • Excerpt Selection: Find a segment (sentence or fixed-length window) containing the maximum number of query terms.

   • Query Term Highlighting: Bold or color query terms within the snippet.

   • Heuristics: Prefer sentences with query terms near each other; avoid cutting in middle of phrase; prefer beginning of document.

3. Summarization-Based: Use text summarization algorithms (extractive) to generate a summary containing key concepts.

[!TIP] Goal: Snippet should be informative (contains query terms in context) and indicative (reflects document's main topic).