Search Applications

The methods in this course were developed mostly for one task: given a query, rank the documents in a collection. The same methods support many other tasks. A spam filter scores incoming messages against a model of spam, using the term statistics of a ranking function. A news service groups articles about the same event with the similarity measures used to compare a query with a document. A question-answering system begins by retrieving passages that might contain the answer. The underlying operations are the same: representing text, comparing representations, and estimating relevance.

This article surveys these applications. It is organized by the dimensions along which they differ: whether there is a query at all, whether the information need is temporary or standing, and whether the output is a ranked list, a set of groups, an extracted fact, or a generated text. Later topics develop several of these applications in depth, and the next two articles examine how retrieval is adapted to professional domains and to enterprise, personal, and product collections.

Ad hoc search

The canonical task is ad hoc retrieval: a person with a temporary need submits a query against a relatively stable collection and receives a ranked list. The term "ad hoc" refers to the query, which is formed for the occasion and then discarded, while the collection persists. Most of this course concerns ad hoc retrieval, and two settings illustrate its range.

Web search operates over the largest and most heterogeneous collection: billions of pages of every quality, written in many languages, many of them designed to manipulate rankings. Its distinctive resources are the link graph and the behavior of very large numbers of users. Its distinctive problems are scale, spam, and freshness. The web search article covers it in detail.

Desktop and personal search operates over the opposite kind of collection: one person's files, email, and messages. The collection is small, private, and made up of many formats. It has no link graph and almost no shared behavioral data, since each collection has a single user. The searcher usually knows that the item exists and is trying to find it again, a task called known-item search, examined in enterprise, personal, and product search.

Between these extremes lie enterprise search, product search, digital libraries, and the specialized professional systems surveyed in the following two articles.

Standing needs: routing, filtering, and dissemination

Ad hoc search reverses when the need is persistent and the documents are new. A person interested in a subject over months does not want to search again each day. They want new documents on the subject delivered as they appear. Three related tasks serve this need.

Selective dissemination of information (SDI), proposed by Hans Peter Luhn (1958), stores each user's interests as a profile, effectively a standing query, and matches every incoming document against every profile. Documents that match are sent to the corresponding user. Alerting services for scientific literature, saved searches, and news alerts are its descendants.

Filtering makes a binary decision for each document in a stream: deliver it or discard it. Spam filtering is the most familiar case, with a single profile representing unwanted mail. Filtering differs from ranking in an important way. A ranking system can defer the decision, placing a borderline document in tenth place. In the classical streaming setting, a filter must commit to a decision for each document as it arrives, without knowing which documents will come later. TREC ran a filtering track from 1995 to 2002, evaluating adaptive filters that learn from the user's feedback on the documents they are shown (Robertson and Soboroff, 2002).

Routing directs each document to one or more destinations, such as sending a customer message to the right support team or a news story to the right desk. Routing can be framed as ranking the profiles for each document, the reverse of ranking the documents for a query.

Filtering as a decision: a worked example

Because a filter produces a set rather than an order, the ranking measures of ranked evaluation cannot score it. The TREC 2002 filtering track used a linear utility instead: a credit of 2 for each relevant document delivered and a debit of 1 for each non-relevant document delivered (Robertson and Soboroff, 2002, §2.3),

$$\text{T11U} = 2R^{+} - N^{+},$$

where $R^{+}$ is the number of relevant documents delivered and $N^{+}$ the number of non-relevant ones. A document that is discarded earns nothing either way.

The two weights determine the decision rule. Suppose the filter estimates that an arriving document is relevant with probability $p$. Delivering it earns 2 with probability $p$ and loses 1 with probability $1 - p$, so its expected contribution is

$$2p - (1 - p) = 3p - 1.$$

Discarding it contributes 0. Delivery is worthwhile exactly when $3p - 1 > 0$, that is, when $p > 1/3$, which is the rule the track report states for this measure. With a credit $a$ and a debit $b$ in general, the same argument gives the threshold $p > b / (a + b)$. A user who finds non-relevant documents more costly raises $b$, and the threshold rises with it.

Consider twelve documents arriving for one profile, five of them relevant. The filter's estimates, the judgments, and the decisions at the threshold $1/3$ are:

The filter delivers seven documents, four relevant and three not, for $\text{T11U} = 2 \times 4 - 3 = 5$. Document 11 shows what a filter gives up. It is relevant, but its estimate fell below the threshold when it arrived, and it is gone. A ranking system would have placed it ninth, where a persistent reader could still find it.

Utility is unbounded below and its scale depends on how many relevant documents a topic has, so the track normalized it before averaging over topics. The best possible utility is $\text{MaxU} = 2 \times 5 = 10$, delivering every relevant document and nothing else, and the normalized utility is $\text{T11NU} = 5 / 10 = 0.5$. The scaled utility clips it at a floor $\text{MinNU} = -0.5$, below which the user is assumed to have stopped reading, and rescales to the range 0 to 1:

$$\text{T11SU} = \frac{\max(\text{T11NU}, \text{MinNU}) - \text{MinNU}}{1 - \text{MinNU}} = \frac{0.5 + 0.5}{1.5} = 0.667.$$

A filter that delivers nothing scores $\text{T11SU} = 0.5 / 1.5 = 0.333$, a baseline that a poor filter can fall below.

Moving the threshold trades deliveries against mistakes. Expected utility is the sum of $3p - 1$ over the delivered documents; realized utility uses the judgments (values computed by tools/experiments/foundations/filtering_utility.py, expected utility rounded to two places and T11SU to three):

The expected utility is highest at $1/3$, as the derivation requires: every document above that threshold adds a positive expected gain and every document below it a negative one. On a finite stream the maximum is a plateau, here every threshold from 0.28 up to just below 0.37, the nearest estimates on either side of $1/3$. The realized utility on this stream peaks at other thresholds, because twelve documents are too few for chance to average out. The rule is right on average only if the estimates are calibrated, meaning that among documents given $p = 0.4$, about 40 percent are relevant. Early in a profile's life the filter has seen little feedback and its estimates are poor, which is why adaptive filtering systems spend much of their effort learning where to set the threshold.

Filtering and retrieval compared

Belkin and Croft (1992) argued that filtering and retrieval are "two sides of the same coin." The representations, matching functions, and term weights are the same, but the roles of the query and the collection are exchanged. The practical differences come from the time dimension. Profiles last long enough to learn from feedback, and collection statistics such as document frequency must be estimated from a stream that is still arriving. Filtering also leads naturally to classification, since a profile trained on labeled examples of wanted and unwanted documents is a classifier.

Organizing collections: classification and clustering

Some applications do not answer a query at all. They organize a collection so that people can browse it, or so that later retrieval works better.

Classification, also called categorization, assigns documents to predefined categories: a news article to sports or politics, an email to spam or not spam, a medical paper to its subject headings. The categories are fixed in advance, and a classifier learns to assign them from labeled examples. This is supervised learning, and its classic text methods are the subject of text classification: Naive Bayes, which makes the same kind of conditional independence assumption as the Binary Independence Model, with classes in place of relevance, and feature selection, which identifies the terms that best separate the classes. Sahami, Dumais, Heckerman, and Horvitz (1998) applied Naive Bayes to junk email, treating the loss of a legitimate message as far more costly than a missed piece of spam, an approach that became the basis of statistical spam filtering.

Clustering groups documents by similarity without predefined categories. The groups emerge from the data, which makes clustering unsupervised. It serves two purposes in retrieval. As a browsing interface, it shows the structure of a collection or a result set. The Scatter/Gather system clustered a collection so that users could browse it by choosing clusters and having the system re-cluster their choices (Cutting, Karger, Pedersen, and Tukey, 1992), and was later applied to clustering search results (Hearst and Pedersen, 1996). As a retrieval aid, it relies on the cluster hypothesis: documents that are similar to each other tend to be relevant to the same requests (van Rijsbergen, 1979). If that holds, retrieving a whole cluster can find relevant documents that share few words with the query. Clustering covers K-means, hierarchical methods, and how clusters are evaluated.

The distinction between them is the source of the categories. In the standard supervised setting, classification needs labeled training data and produces categories that people defined in advance. Clustering needs no labels and produces groups that people must then interpret. My Goodreads project used both: a classifier to predict a review's star rating from its text, and a clustering of reviewers by their reviewing behavior.

Condensing documents: summarization

Summarization produces a shorter version of a document or a set of documents. Luhn (1958) again supplied an early and influential method: score each sentence by the significant words it contains, and select the highest-scoring sentences. This is extractive summarization, which selects passages from the source. Abstractive summarization writes new text that paraphrases the source, which became practical with neural language models. Nenkova and McKeown (2011) survey the methods.

Summarization appears in retrieval in two places. The snippet shown for a search result is usually a query-biased summary, built by selecting the passages most related to the query (Tombros and Sanderson, 1998). Multi-document summarization condenses many retrieved documents into one overview. It is the task behind generated answers that cite several sources, and it has to avoid repeating what several sources say in common.

Extracting facts: information extraction

Information extraction (IE) fills structured records from unstructured text. From a news report of a corporate acquisition, an extractor identifies the acquiring company, the acquired company, the price, and the date. Its basic components are named entity recognition, which finds mentions of people, organizations, places, and dates, and relation extraction, which identifies how the entities are connected. The U.S. Message Understanding Conferences of the late 1980s and 1990s defined and evaluated these tasks (Grishman and Sundheim, 1996).

Retrieval and extraction support each other. Extraction improves retrieval by adding structure to the index, such as entity fields that allow a search for documents mentioning a particular company rather than any document containing the word. Retrieval makes extraction practical at scale by selecting the documents worth processing. Knowledge graphs, which answer factual questions directly on search results pages, combine curated structured sources with facts extracted from text.

Following events: topic detection and tracking

Topic detection and tracking (TDT) organizes a stream of news by event. A DARPA program in the late 1990s defined its tasks (Allan, 2002):

• segmentation: dividing a continuous stream, such as a transcribed broadcast, into separate stories;
• first story detection: recognizing the first story about an event not seen before;
• tracking: given a few stories about an event, finding the later stories about it;
• detection: grouping stories by event without any examples, a form of clustering in a stream.

TDT combines filtering, because the documents arrive over time, with clustering, because the groups are not known in advance. It also shows a difficulty that ad hoc retrieval does not have: an event is narrower than a topic. Two stories about two different earthquakes share most of their vocabulary but describe different events, and a tracker must tell them apart. First story detection proved especially hard, because a new event often looks very much like an old one of the same kind. News aggregators that group coverage of the same story descend from this work.

Finding people: expert search

Sometimes the answer to a need is a person, not a document. Expert finding ranks people by their expertise on a topic, using the documents associated with them: what they have written, the projects they have worked on, the messages they have sent. The TREC Enterprise track (2005–2008) evaluated expert finding on organizational collections. Balog, Azzopardi, and de Rijke (2006) formalized two approaches. A candidate model builds a profile of each person from their documents and ranks the profiles against the query. A document model first ranks documents, then credits each relevant document's associated people. The task matters most inside organizations, where knowing who to ask is often worth more than any document (Balog et al., 2012).

Answering questions

Question answering (QA) returns an answer rather than a document. For Who wrote the Federalist Papers? the ideal response is three names, not a ranked list of pages. The TREC QA track, starting in 1999, evaluated systems on short factual questions (Voorhees, 1999). The architecture that emerged has dominated open-domain question answering since: retrieve documents or passages likely to contain the answer, extract candidate answers from them, and rank the candidates. IBM's Watson, which won the quiz show Jeopardy! in 2011, was an elaborate version of that pipeline (Ferrucci et al., 2010). Neural reading-comprehension models replaced the extraction step with a model that reads a passage and identifies the answer span. Chen, Fisch, Weston, and Bordes (2017) combined such a reader with a TF-IDF retriever over Wikipedia.

Retrieval-augmented generation extends the same design: retrieve passages, then have a language model generate an answer from them. The retrieval step limits the quality of the answer, since a generator cannot use evidence it was never given, although good evidence does not guarantee that the generator uses it correctly. An answer that cites retrieved passages can at least be checked against them. Answering systems that cite their sources still begin with the ranked retrieval of passages.

Beyond text: multimedia retrieval

Images, audio, and video have no words to index directly, apart from any speech or visible text they contain, so multimedia retrieval must either find words for them or compare their content directly.

Text surrogates are the oldest approach and remain effective: captions, file names, surrounding page text, and the anchor text of links to an image. Spoken audio and video can be transcribed by speech recognition, and text in images and video frames can be read by optical character recognition, then indexed as text. In the early years of the TRECVID video retrieval evaluations, many of the strongest video search systems relied heavily on transcripts of the spoken soundtrack (Smeaton, Over, and Kraaij, 2006).

Content-based retrieval compares features computed from the media itself: color, texture, and shape for images, and spectral fingerprints for audio. Audio fingerprinting is a notable success. A recording can be identified from a few seconds of noisy audio by matching patterns of spectral peaks against an index of fingerprints (Wang, 2003). For general image retrieval, Smeulders and colleagues (2000) identified the semantic gap: low-level features capture what an image looks like, not what it depicts, so two images can look alike while showing different things, and the reverse.

Learned representations have narrowed that gap. Models trained on large collections of images with their captions map images and text into a shared vector space, so that a text query can be compared directly with images (Radford et al., 2021). Retrieval then becomes nearest-neighbor search in that space, the same operation as dense text retrieval, described in the history.

How the applications relate

The applications differ along a few dimensions:

The common elements explain why the course spends most of its time on ad hoc retrieval. The representations built in text processing, the weighting and similarity of the vector space model, the probability estimates of probabilistic retrieval, and the measures of evaluation transfer to nearly all of these tasks with modest changes. Classification and clustering get topics of their own because they introduce learning from labeled examples and from structure in unlabeled data, which the rest of the field has drawn on increasingly.

Ad hoc search across settings

Ad hoc search itself varies a great deal with the setting, and the variation follows from a few properties of the collection and the task. The two tables below summarize the settings examined in this topic. The first describes what the system searches and how people ask; the second, what success means and how it is measured. Each row condenses the article that treats the setting in detail: web search, enterprise, personal, and product search, and search in professional domains.

Read down the "Priority" column and the settings divide into two groups. Where one good answer satisfies the need (web, product) or the target is a single item (enterprise, personal), the measures concentrate on the top of the ranking. Where the task is to find everything (legal discovery, patents, systematic reviews), the measures are built on recall, and searchers accept long result lists and Boolean query languages to get it. The same split separates the evaluation measures of evaluation: precision at $k$ and nDCG for the first group, recall and recall-oriented measures for the second.

References

• Allan, J. (Ed.) (2002). Topic Detection and Tracking: Event-based Information Organization. Kluwer Academic Publishers.
• Balog, K., Azzopardi, L., and de Rijke, M. (2006). Formal models for expert finding in enterprise corpora. In Proceedings of SIGIR 2006, 43–50.
• Balog, K., Fang, Y., de Rijke, M., Serdyukov, P., and Si, L. (2012). Expertise retrieval. Foundations and Trends in Information Retrieval, 6(2–3), 127–256.
• Belkin, N. J., and Croft, W. B. (1992). Information filtering and information retrieval: Two sides of the same coin? Communications of the ACM, 35(12), 29–38.
• Chen, D., Fisch, A., Weston, J., and Bordes, A. (2017). Reading Wikipedia to answer open-domain questions. In Proceedings of ACL 2017, 1870–1879.
• Cutting, D. R., Karger, D. R., Pedersen, J. O., and Tukey, J. W. (1992). Scatter/Gather: A cluster-based approach to browsing large document collections. In Proceedings of SIGIR 1992, 318–329.
• Ferrucci, D., Brown, E., Chu-Carroll, J., et al. (2010). Building Watson: An overview of the DeepQA project. AI Magazine, 31(3), 59–79.
• Grishman, R., and Sundheim, B. (1996). Message Understanding Conference-6: A brief history. In Proceedings of COLING 1996, 466–471.
• Hearst, M. A., and Pedersen, J. O. (1996). Reexamining the cluster hypothesis: Scatter/Gather on retrieval results. In Proceedings of SIGIR 1996, 76–84.
• Luhn, H. P. (1958). A business intelligence system. IBM Journal of Research and Development, 2(4), 314–319.
• Luhn, H. P. (1958). The automatic creation of literature abstracts. IBM Journal of Research and Development, 2(2), 159–165.
• Nenkova, A., and McKeown, K. (2011). Automatic summarization. Foundations and Trends in Information Retrieval, 5(2–3), 103–233.
• Radford, A., Kim, J. W., Hallacy, C., et al. (2021). Learning transferable visual models from natural language supervision. In Proceedings of ICML 2021, 8748–8763.
• Robertson, S., and Soboroff, I. (2002). The TREC 2002 filtering track report. In Proceedings of the Eleventh Text REtrieval Conference (TREC 2002).
• Sahami, M., Dumais, S., Heckerman, D., and Horvitz, E. (1998). A Bayesian approach to filtering junk e-mail. In Learning for Text Categorization: Papers from the AAAI Workshop, Technical Report WS-98-05.
• Smeaton, A. F., Over, P., and Kraaij, W. (2006). Evaluation campaigns and TRECVid. In Proceedings of the 8th ACM International Workshop on Multimedia Information Retrieval, 321–330.
• Smeulders, A. W. M., Worring, M., Santini, S., Gupta, A., and Jain, R. (2000). Content-based image retrieval at the end of the early years. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(12), 1349–1380.
• Tombros, A., and Sanderson, M. (1998). Advantages of query biased summaries in information retrieval. In Proceedings of SIGIR 1998, 2–10.
• van Rijsbergen, C. J. (1979). Information Retrieval, 2nd edition, chapter 3. Butterworths.
• Voorhees, E. M. (1999). The TREC-8 question answering track report. In Proceedings of the Eighth Text REtrieval Conference (TREC-8), 77–82.
• Wang, A. (2003). An industrial-strength audio search algorithm. In Proceedings of the 4th International Conference on Music Information Retrieval (ISMIR 2003).