learn.ifs.name

Information Retrieval and Retrieval-Augmented Generation

Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 11

19 cards in “11.1 Information retrieval” · whole deck

11.1 Information retrieval

  1. What is ad hoc retrieval?
    A user poses a query to a retrieval system, which returns an ordered set of documents from some collection.
  2. Define document, collection, term and query in IR.
    A document is whatever unit of text is indexed and retrieved (web page, paper, passage). A collection is the set of documents used to satisfy requests (possibly the whole web). A term is a word (or phrase) in the collection. A query is a user’s information need expressed as a set of terms.
  3. What are the two classes of IR systems?
    Sparse retrieval, representing queries and documents as word-count vectors weighted by tf-idf or BM25, and dense retrieval, representing them as embeddings computed by language models.
  4. What is the vector space model of IR, and what is the bag-of-words assumption?
    A document is represented as a vector of counts of the words it contains (Salton, 1971). Bag of words: treat the document as an unordered set of words, ignoring positions and keeping only frequencies.
  5. What is a term-document matrix?
    A matrix with a row per vocabulary word and a column per document; each cell counts how often the word occurs in the document. Each document is a column vector.
  6. What does a term-document matrix reveal about similar documents?
    Similar documents have similar words, so their column vectors are similar: Shakespeare’s comedies have many fool and wit, few battle, unlike the histories.
  7. Why do IR systems use term weights instead of raw counts?
    Raw counts overweight frequent words and ignore how discriminative a word is; tf-idf and BM25 weight terms by frequency in the document and rarity across the collection.
  8. Define the term frequency used in tf-idf.
    Log-scaled count: \(\text{tf}_{t,d} = 1 + \log_{10}\text{count}(t, d)\) if the count is positive, else 0. A word occurring 100 times isn’t 100 times more relevant (tf goes 1, 2, 3, 4 for counts 1, 10, 100, 1000).
  9. Define document frequency and inverse document frequency.
    \(\text{df}_t\) is the number of documents containing term \(t\). \(\text{idf}_t = \log_{10}\frac{N}{\text{df}_t}\) for \(N\) documents: high for terms in few documents, 0 for terms in every document.
  10. Why is idf useful?
    Terms that occur in only a few documents discriminate those documents from the rest; terms that occur everywhere (good, sweet in Shakespeare) aren’t helpful.
  11. Define tf-idf.
    \(\text{tf-idf}(t, d) = \text{tf}_{t,d} \cdot \text{idf}_t\).
  12. How does the classic tf-idf model score a document against a query?
    By the cosine between their tf-idf vectors, \(\text{score}(q, d) = \frac{q \cdot d}{|q||d|}\), assuming documents with words similar to the query are more relevant. Only terms in both contribute to the dot product.
  13. For the query “sweet love”, why does “Sweet sweet nurse! Love?” outscore “Sweet sorrow”?
    The first document contains both query terms (sweet twice), while the second lacks love, which has the higher idf; its tf-idf cosine is much higher (≈ .75 vs ≈ .08).
  14. What is a common simplification of tf-idf cosine scoring?
    Dropping the idf term for the document (keeping it only for the query), which sometimes performs better.
  15. What is BM25?
    A tf-idf variant (Okapi BM25): \(\sum_{t \in q}\log\frac{N}{\text{df}_t}\cdot\frac{\text{tf}_{t,d}}{k\big(1 - b + b\frac{|d|}{|d_{avg}|}\big) + \text{tf}_{t,d}}\). Parameter \(k\) balances term frequency against idf; \(b\) controls document-length normalization.
  16. What do the BM25 parameters \(k\) and \(b\) do at their extremes?
    \(k = 0\): no term frequency, just binary presence (plus idf); large \(k\): raw term frequency. \(b = 1\): full scaling by document length; \(b = 0\): no length scaling. Typical: \(k\) in [1.2, 2], \(b = 0.75\).
  17. What is a stop list, and why is it less used now?
    A list of high-frequency (mostly function) words removed from queries and documents. It makes phrase search hard (“to be or not to be” → “not”), and idf already downweights such words, so modern IR rarely uses it.
  18. What is an inverted index?
    The data structure for finding documents containing query terms: a dictionary of terms (with document frequencies) each pointing to a postings list of document IDs, optionally with counts or positions. 
    love  {2} → 1 [1] → 3 [1]
nurse {2} → 1 [1] → 4 [1]
sweet {3} → 1 [2] → 2 [1] → 3 [1]
    Format: term {document frequency} → doc id [count in doc] → …
  19. Summarize how a ranked retrieval system works.
    Indexing: build an inverted index over the collection. Retrieval: use it to find candidate documents containing query terms, score each by tf-idf or BM25 cosine with the query, sort by score, and return the top N.

Source