Introduction to Information Retrieval

Introduction to Information Retrieval What is Information Retrieval? Information Retrieval (IR) is the field that studies how to find relevant information from large collections of unstructured data, typically text. When you use a search engine or look through a library database, you're interacting with an information retrieval system. The core challenge is efficiency: systems must search through thousands or millions of documents and return the most relevant results in seconds. The goal of information retrieval is to design methods that can store, organize, and retrieve documents efficiently (quickly) and accurately (returning relevant results). These two objectives are sometimes in tension with each other, as we'll see later. The IR Workflow: Three Essential Steps All information retrieval systems follow the same basic workflow: Indexing: Before any search can happen, documents must be processed and organized. This step extracts useful information from documents and builds data structures that enable fast searching. Retrieval and Ranking: When a user submits a search query, the system matches it against the index, finds candidate documents, assigns relevance scores to each, and displays results in order from most to least relevant. Evaluation: Finally, the system must be tested against known benchmarks. We measure how well the system performs by comparing its results to a set of documents that experts have marked as relevant. This cycle repeats as systems are refined and improved. Key Terminology You Need to Know Before we dive deeper, let's establish some essential terms you'll encounter throughout information retrieval: Query: The search terms a user enters to express their information need. For example, "best restaurants near me" is a query. Document: Any unit of data that can be retrieved—a web page, a research paper, an email, a product listing. Collection: The entire set of documents available to search. A search engine's collection is billions of web pages; a university library system's collection is its catalog of books and articles. Relevance: Whether a document satisfies the user's information need. This is the fundamental concept in IR—a document is relevant if it actually helps answer the user's question. Indexing and Data Structures How Documents Are Processed The first step in building an information retrieval system is processing documents into a searchable format. Documents start as unstructured text—they're just long strings of characters. To make them searchable, they must be broken down into individual terms through tokenization: splitting the text into words or meaningful units. But tokenization alone isn't enough. Words have different forms that mean essentially the same thing: "running," "runs," and "run" are all related to the concept of running. To handle this, IR systems often apply stemming, which reduces words to their root form. With stemming, all three forms above would be treated as the same term, improving matching between queries and documents. During processing, the system also records term frequency (TF)—how many times each term appears in a document. A term appearing 10 times is probably more important to that document's topic than a term appearing once. Building the Inverted Index The heart of any IR system is the inverted index. Unlike a normal index (like the index of a book, which maps page numbers to topics), an inverted index maps terms to the documents containing them. Think of it this way: a normal index says "Chapter 3 is about information retrieval." An inverted index says "The term 'information retrieval' appears in documents 3, 7, and 42." Here's why this structure is powerful: when a user searches for "information retrieval," the system can instantly look up that term in the inverted index and retrieve documents 3, 7, and 42 without scanning every document in the collection. For large collections, this speed advantage is enormous. What Information is Stored? Inverted indexes store more than just document IDs. They maintain several statistics that enable sophisticated ranking: Term frequency (TF): How many times the term appears in each document Document frequency (DF): How many documents in the entire collection contain this term Document length: The total number of terms in each document These statistics serve different purposes. Document frequency is useful because it tells us how common or rare a term is. If a term appears in 99% of the collection, it's probably not useful for distinguishing relevant documents. If it appears in only 0.1% of documents, it's very specific and potentially very informative. Document length is stored so the system can apply length normalization—long documents naturally contain more terms, which could unfairly boost their relevance scores. Why Indexing Matters The inverted index is built once, before any queries arrive. This upfront investment pays dividends: Fast retrieval: At query time, the system can instantly find all documents containing a query term by looking it up in the index. Reduced computation: Pre-processing documents and computing statistics during indexing means the system doesn't have to do this work for every query—it's already done. Retrieval and Scoring Models How Queries Are Processed When a user submits a query, it undergoes the same processing as documents did during indexing. The query is tokenized and stemmed using identical methods. This consistency is crucial: if documents are stemmed to their root forms, queries must be too, or the matching won't work properly. Three Major Retrieval Models Information retrieval systems rely on different mathematical models to decide which documents are relevant. Think of these as different philosophies for answering the question: "How relevant is this document to this query?" The Boolean Model The Boolean model is the simplest retrieval approach. It treats relevance as binary: a document either satisfies the query or it doesn't. The query is expressed as a logical statement using AND, OR, and NOT operators. For example: (python OR java) AND programming returns documents containing (python or java) AND the word programming search NOT engine returns documents with "search" but not "engine" The Boolean model is fast and exact, which made it popular in early database systems. However, it's all-or-nothing: a document that contains most of the query terms ranks the same as a document containing exactly the query terms. Modern systems rarely use pure Boolean retrieval because it doesn't capture degrees of relevance. The Vector-Space Model The vector-space model treats documents and queries as vectors in a high-dimensional space, where each dimension represents a term in the vocabulary. Imagine a simple example with just three terms: {python, java, programming}. We could represent the query "python programming" as the vector $[1, 0, 1]$ (contains python, doesn't contain java, contains programming). A document might be represented as $[3, 1, 5]$ (contains python 3 times, java once, programming 5 times). The system then computes cosine similarity—the cosine of the angle between the query and document vectors. Documents with higher cosine similarity are ranked higher. The formula is: $$\text{Cosine Similarity} = \frac{\vec{d} \cdot \vec{q}}{|\vec{d}| \cdot |\vec{q}|}$$ where $\vec{d}$ is the document vector and $\vec{q}$ is the query vector. The beauty of this approach is that it produces a continuous relevance score (not just relevant/not relevant), allowing documents to be ranked by degree of relevance. It also naturally incorporates term weights: terms that appear frequently are weighted more heavily. The Probabilistic Model The probabilistic model approaches retrieval from a statistical perspective: given a query and a document, what is the probability that this document is relevant to the user? Rather than geometric similarity like the vector-space model, probabilistic models estimate relevance from statistics about term distributions. BM25 is the most widely used probabilistic scoring function in modern IR systems. BM25 combines: How frequently the query term appears in the document How frequently the term appears across the collection (rarity) The document's length BM25 has proven effective across many domains and is used by Elasticsearch, Solr, and other production systems. The image above shows how these models relate to each other. Notice how the probabilistic and vector-space models represent different mathematical foundations, while BM25 sits at the intersection of probabilistic thinking with practical effectiveness. Evaluation Metrics and Trade-offs Measuring Precision: What Fraction of Results Are Correct? To evaluate an IR system, we need quantitative metrics. Precision measures how many of the results returned to the user are actually relevant: $$\text{Precision} = \frac{\text{Number of relevant retrieved documents}}{\text{Number of retrieved documents}}$$ If a system retrieves 10 documents and 7 of them are relevant, the precision is 7/10 = 0.7 or 70%. Precision answers the question: "When the system returns a result, how trustworthy is it?" High precision is important when users want accuracy. A search for "how to treat a broken arm" should return trustworthy medical information, not random pages that happen to mention the words. Measuring Recall: What Fraction of All Relevant Documents Were Found? Recall measures something different: of all the relevant documents that exist in the collection, how many did the system find? $$\text{Recall} = \frac{\text{Number of relevant retrieved documents}}{\text{Number of relevant documents in the collection}}$$ If there are 100 relevant documents total and the system finds 30 of them, recall is 30/100 = 0.3 or 30%. Recall answers: "Did I find everything I needed?" High recall is important when users want comprehensive results. A researcher looking for all papers about a topic wants to ensure they found most of the relevant work, not just a few high-quality results. The Precision-Recall Trade-off Here's the key insight: precision and recall are in tension. To understand why, consider how a ranking system works. It returns results in order, with the most relevant documents first. If the system is conservative and only returns documents it's very confident are relevant, precision will be high but recall will be low (many relevant documents are never shown). If the system is liberal and returns many documents hoping to include all relevant ones, recall improves but precision drops (many irrelevant documents clutter the results). The Precision-Recall curve visualizes this trade-off by plotting recall (x-axis) against precision (y-axis) as the ranking threshold varies. An ideal system would have a curve hugging the top-right corner (high precision and high recall at all thresholds). Real systems show a downward-sloping curve: as you demand higher recall, precision inevitably drops. Balancing the Trade-off in Practice Different applications require different balances: Search engines often optimize for precision over recall—users rarely look beyond the first page of results, so high accuracy is critical. Medical literature searches prioritize recall—researchers need to find all relevant papers on a topic, even at the cost of seeing some irrelevant results. Legal discovery systems also emphasize recall—missing a relevant document could have serious consequences. The choice depends on the cost of false positives (irrelevant results) versus false negatives (missed relevant results) in your specific application. <extrainfo> Applications and Modern Extensions Incorporating Language Models Modern IR systems extend the classical models discussed above by incorporating language models—statistical models of how language is used. These models help the system better understand what a user is searching for, not just match keywords. For example, understanding that "automobiles" and "cars" are related terms even if they don't share words. Learning-to-Rank Techniques Rather than relying on a single scoring formula like BM25, learning-to-rank approaches train machine learning models to predict document relevance. These models learn from examples of queries and documents that experts have marked as relevant or irrelevant. The machine learning model learns to combine many different features (term frequency, document length, freshness, authority, etc.) to predict relevance scores. Using User Behavior to Improve Results Production systems collect data about how users interact with results. If users frequently click on a particular document when searching for a specific query, that's evidence the document is relevant. Over time, IR systems use this click-through data to refine ranking functions and personalize results for different users. </extrainfo>