Information Retrieval Overview

Information Retrieval

• Information retrieval (IR) is finding material, usually documents of an unstructured nature (like text), to meet an information need within large collections (often stored on computers).

Goals of Information Retrieval

• Efficient and effective access to relevant information from a large unstructured dataset.
• Scalability to handle large and growing datasets.
• Retrieving documents that match a user's information need (a query).
• Understanding and processing natural language queries and documents.
• Ranking retrieved results based on relevance to the user's query.

IR Evolution

Early Developments (1950s-1960s)

• The birth of IR: indexing and retrieving information from text.
• Boolean model for exact matching.
• Cranfield reference collection (evaluation metrics) and first versions of SMART (System for the Mechanical Analysis and Retrieval of Text), by G. Salton.

Probabilistic Models (1970s-1980s)

• Probabilistic models for IR (term probabilities → doc. relevance and ranking).
• Vector Space Model (VSM) representing documents and queries as vectors.
• TF-IDF weighting scheme, Okapi BM25 ranking function (by Karen Spark-Jones, S. Robertson, and others).

Digital Libraries and Web Search (1990s-2000s)

• Digital libraries (PubMed Central) and first Web search engines (Yahoo, AltaVista).
• Dominance of Google's PageRank algorithm (exploits link-based information).
• Web-scale indexing, search personalization, recommendation systems.

Modern Information Retrieval (2010s-Present)

• Deep learning neural networks for semantic understanding.
• AI-powered search engines and chatbots.

Typical Architecture and Components

• Indexing: creates a data structure mapping terms (words, phrases) in documents to their locations in the collection, enabling faster retrieval.
• Query Processing: analyzing user queries and formatting them for document retrieval, transforming queries for efficient comparisons with indexed documents.
• Search and Ranking: ranks the set of candidate documents that match the user's query based on relevance, with scoring and ranking algorithms available.
• Relevance feedback: allows users to provide feedback on retrieved results, enabling iterative adjustment of ranking and retrieval strategies.
• Query expansion: expands user queries by adding synonyms, hypernyms (IS-A relationships), related terms, or conceptually similar words, improving retrieval of additional relevant documents.

Document Analysis and Indexing

Goals/Subtasks: Document Representation

• Extracting informative content from documents.
• Sparse representations: representing documents as sets of discrete index terms (e.g. after tokenization, normalization and stop-word removal).
• Dense representations: representing documents as dense semantic vectors (using Deep Learning language models).

Goals/Subtasks: Indexing

• Creating a machine-processable representation from analyzed document contents.
• Sparse representations → inverted indices (mapping index terms to documents and additional information, like term frequencies).
• Dense representations → vector stores (arranging dense vectors to facilitate similarity comparisons).

IR with Sparse Representations

Document Processing

• Manually assigned index terms (by human annotators): e.g. controlled vocabularies (like MeSH).
• Automatic indexing (with NLP techniques): tokenization, stop-word removal and normalization.

Inverted Indices

• Data structure allowing fast retrieval of documents.
• Associates index terms with the documents in which they appear, and records various statistics about the occurrences.
• Primary components: Term Dictionary, and Posting Lists (info about documents containing the term, additional information like frequencies, and positions within documents).

Retrieval Models

• Mathematical models/frameworks to determine how well documents are scored and ranked by relevance.

Boolean Models:

• Based on Boolean algebra using AND, OR, NOT operators to match terms with documents in inverted indices.
• No document ranking → documents are either relevant (1) or non-relevant (0).

Vector Space Models (VSM):

• Represent documents and queries as vectors in a multi-dimensional space.
• Similarity measures (cosine) are used to compare query vectors with document vectors, used to rank documents.

Probabilistic Models:

• Building on vector space models.
• Rank documents based on their likelihood of being relevant to a query using probabilistic principles.

Vector Space Models (More Detail)

• Documents and queries as high-dimensional sparse vectors.
• Vector Dimension → total number of index terms in the collection.
• Sparse Vectors → very few non-zero elements.
• Vector Similarity between d_i and q → relevance of document d_i to query.
• Key points: (1) how index terms are weighted, (2) how vector similarities are computed.

TF-IDF Weighting

• Calculates weights for index terms (TF-IDF = Term Frequency-Inverse Document Frequency).
• TF(t_i, d_j): number of times term t_i appears in document d_j divided by the total number of terms in d_j.
• IDF(t_i): logarithmic value related to how frequently the term appears across all documents in the collection.

Okapi BM25

• A family of probabilistic ranking functions in IR.
• Adapts TF-IDF to address some of its limitations (e.g. robustness in ranking).
• Aspects of the BM25 ranking score: modified TF weighting, modified IDF, and document length normalization, and a term saturation function.

Vector Similarity (More Detail)

• Euclidean Distance (not recommended): Sensitive to scaling differences, less effective with sparse data, affected by the "curse of dimensionality" where distances aren't accurately reflected by similarity.
• Cosine Similarity: Scale-invariant, measures the angle between vectors (how much they overlap), robust in high-dimensional spaces and with sparse vectors, and efficiently computable.

IR Libraries and Frameworks

• Apache Lucene: Open source IR library and search engine.
• Apache SOLR: Indexing/search engine server based on Lucene.
• ElasticSearch: Similar to SOLR, focussed on log storage and analysis.
• Anserini and PySerini: Toolkits for reproducible IR research (sparse and dense).
• Whoosh: Python clone of Lucene.
• Terrier: Open source search engine for research and experimentation.

Sparse IR Improvements (specific techniques for enhancing recall and addressing vocabulary issues)

• Query Term Expansion: adding synonyms, hypernyms (hierarchical relationships), and related concepts to queries.
• Pseudo-Relevance Feedback: iteratively adjust queries with new terms based on user feedback.
• Learning to Rank: ML techniques to learn complex ranking models.

This quiz explores the fundamentals of Information Retrieval (IR), including its goals, evolution, and key models. Learn about the history and techniques that allow efficient access to relevant information within large datasets. Test your knowledge on early developments and probabilistic models in the field of IR.