Query Expansion, Relevance Feedback and Language Models

The vocabulary mismatch problem

A person immediately sees the relation between a query and a document that use different words. A purely lexical system sees only whether the strings match.

TF-IDF and BM25 are powerful, but fundamentally rely on lexical evidence. They do not inherently know that car ≈ automobile, doctor ≈ physician, cheap ≈ inexpensive. For both pairs above the TF-IDF cosine and the BM25 score are exactly 0. This motivates techniques that alter or reinterpret the query.

Language models

• Applications: whenever there are several options and we must choose the most likely, based on the context words:
  • compare sentences to tell which are the "good" ones;
  • spell-checking (Lab 03): for "I want some cugar in my coffee", cougar or sugar?
  • automatic speech recognition: the most likely sequence of words; machine translation, question answering, summarization;
  • information retrieval: a document is likely to answer a query well if it is likely to generate the query (Part VII).
• Language models can score and sort sentences: P(I like apples) ≫ P(I lick apples). They encode some grammaticality: P(I was going to call) ≫ P(I will going to call).

First shot: the chain rule of probability

P(I, want, some, sugar, in, my, coffee) = P(I) · P(want | I) · P(some | I, want) · … · P(coffee | I, want, some, sugar, in, my). Estimate each factor by counting in a corpus, e.g. Jane Austen's Emma (192,427 tokens in NLTK's Gutenberg collection):

# import nltk; nltk.download("gutenberg")
import nltk

emma_words = list(nltk.corpus.gutenberg.words("austen-emma.txt"))
N = len(emma_words)

def count(seq):                        # how often the exact token sequence occurs
    n = len(seq)
    return sum(emma_words[i:i + n] == seq for i in range(N - n + 1))

for sentence in [["She", "was", "the", "youngest"],
                 ["I", "want", "some", "sugar", "in", "my", "coffee"]]:
    prob = count(sentence[:1]) / N                      # P(w1)
    for i in range(1, len(sentence)):
        num, den = count(sentence[:i + 1]), count(sentence[:i])
        print(f"P({sentence[i]} | {' '.join(sentence[:i])}) = {num}/{den}")
        prob *= num / den if den else 0.0
        if prob == 0: break
    print("Sentence probability:", prob)
# P(was | She) = 110/562
# P(the | She was) = 3/110
# P(youngest | She was the) = 1/3
# Sentence probability: 5.196775920219095e-06
# P(want | I) = 12/3178
# P(some | I want) = 0/12
# Sentence probability: 0.0

Problem: "I want some sugar in my coffee" is a perfectly good sentence, but "I want some" never occurs in Emma, so its probability is 0. We would need an enormous corpus to see all possible sentences often enough, and the possible sentences are too many: we will never see enough of them.

💡 Corrected from the notebook: it counted with " ".join(words).count(...), which also matches inside longer words (570 matches for "She" instead of its 562 tokens), and it skipped factors with a zero count, reporting 0.0045 for the sugar sentence instead of 0. It also left out \(P(w_1)\).

The Markov assumption: n-grams

Take only the \(l\) words before the given one: \(P(w_1, \ldots, w_n) \approx \prod_i P(w_i \mid w_{i-l}, \ldots, w_{i-1})\).

• Unigram model: \(P(w_i \mid w_1, \ldots, w_{i-1}) \approx P(w_i)\). P(coffee | I, want, some, sugar, in, my) ≈ P(coffee).
• Bigram model: condition only on the previous word, \(P(w_i \mid w_{i-1})\). P(coffee | I, want, some, sugar, in, my) ≈ P(coffee | my).
• For more context, and more dependence between words: trigram, 4-gram, … models.

Try it: a bigram model

Trained on the notebook's five sentences (edit them if you like). Click a word in the table to see what follows it; type a sentence to score it. The smoothing options are explained in Part VI.

A bigram model of Emma

import math, random
from collections import Counter, defaultdict
import nltk

emma_words = nltk.corpus.gutenberg.words("austen-emma.txt")
unigrams = Counter(emma_words)
bigrams = Counter(zip(emma_words, emma_words[1:]))      # exact token pairs

def p_bigram(prev, word):                                # MLE: c(prev, word) / c(prev)
    return bigrams[(prev, word)] / unigrams[prev]

sentence = ["she", "was", "to", "the"]
log_p = 0.0
for w1, w2 in zip(sentence, sentence[1:]):
    p = p_bigram(w1, w2)
    print(f"P({w2}|{w1}) = {bigrams[(w1, w2)]}/{unigrams[w1]} = {p:.4f}")
    log_p += math.log(p)                                 # add logs, do not multiply
print(f"log P = {log_p:.4f}, P = {math.exp(log_p):.3e}")
# P(was|she) = 218/1778 = 0.1226
# P(to|was) = 80/2385 = 0.0335
# P(the|to) = 236/5183 = 0.0455
# log P = -8.5830, P = 1.873e-04

following = defaultdict(Counter)
for (w1, w2), c in bigrams.items():
    following[w1][w2] = c

def generate_text(start_word, num_words=10, sample=True):
    sentence = [start_word]
    for _ in range(num_words):
        nxt = following[sentence[-1]]
        if not nxt:
            break
        words, counts = zip(*nxt.items())
        sentence.append(random.choices(words, weights=counts)[0] if sample
                        else max(nxt, key=nxt.get))
    return " ".join(sentence)

random.seed(0)
print(generate_text("I"))
print(generate_text("She"))
print(generate_text("She", sample=False))
# I was every thing in return of ." " You will
# She comforted away . Perry ," said Frank cut back earlier
# She was not be a very much to be a very

Try it: generate from Emma

The full bigram model of Emma (7,811 word types, 66,579 distinct bigrams) in your browser. Greedy always takes the most probable next word and soon loops; sampling draws the next word in proportion to its count.

💡 Corrected from the notebook: it built the bigram table with the same substring counting, so "a s" was counted 394 times (every "a s…" such as "a short", "a sort"), although the token pair (a, s) never occurs in Emma. That is why its greedy text read "She was a s a s a s". Its scoring cell also looked the table up the wrong way round, printing \(P(she \mid was) \approx 0.0029\) where \(P(was \mid she) = 0.1226\) was meant.

Problem 1: underflow

Multiplying many probabilities gives very small numbers, with a risk of underflow (the product rounds to 0). Work with logarithms: \(\log(p_1 p_2 p_3 p_4) = \log p_1 + \log p_2 + \log p_3 + \log p_4\). (The notebook's cell added the probabilities themselves, \(p_1 + p_2 + \ldots\), which is not a log-probability.)

Problem 2: zero counts, even in enormous corpora

• Google Web 1T 5-gram (2006): 1,024,908,267,229 tokens of web text, 314,843,401 distinct bigrams, and it still keeps only n-grams seen at least 40 times.
• Shakespeare: 884,647 tokens and 29,066 word types; he produced about 300,000 bigram types out of \(29{,}066^2 \approx 844\) million possible bigrams. Most possible bigrams were never seen (99.96%).

Evaluating a language model

• Extrinsic: with respect to some task, e.g. how often it picks the correct spelling in a spell-checking task.
• Intrinsic: how much probability the model gives to sentences from a test corpus (which should have the same distribution of words as the training data). The Shannon game: how well do we predict the next word, given some context?

Query likelihood on Cranfield

The same Cranfield collection as in the previous labs, tokenized as for BM25 in Lab 04: f"{doc.title} {doc.text}".lower().split(). The collection has 247,273 tokens and 12,246 distinct ones.

# pip install ir_datasets numpy scikit-learn
import ir_datasets
from collections import Counter

dataset = ir_datasets.load("cranfield")
docs = list(dataset.docs_iter())
queries = list(dataset.queries_iter())

texts = [f"{doc.title} {doc.text}".lower().split() for doc in docs]
doc_ids = [doc.doc_id for doc in docs]
titles = [doc.title for doc in docs]

collection_counts = Counter()
for tokens in texts:
    collection_counts.update(tokens)
collection_length = sum(collection_counts.values())
collection_length, len(collection_counts)
# (247273, 12246)

import math
from collections import Counter

def collection_prob(term):
    return collection_counts[term] / collection_length

def query_likelihood_score(query, doc_tokens, lam=0.2):
    doc_counts = Counter(doc_tokens)
    doc_len = len(doc_tokens)
    score = 0.0
    for term in query.lower().split():
        p_doc = doc_counts[term] / doc_len if doc_len > 0 else 0.0
        p_collection = collection_prob(term)
        p = (1 - lam) * p_doc + lam * p_collection
        if p > 0:
            score += math.log(p)
        else:
            return float("-inf")
    return score

def search_ql(query, k=5):
    scored = []
    for i, tokens in enumerate(texts):
        scored.append((query_likelihood_score(query, tokens, lam=0.2), i))
    top = sorted(scored, reverse=True)[:k]
    return [(doc_ids[i], titles[i], score) for score, i in top]

q = queries[0].text
print(q)
for result in search_ql(q):
    print(result)
# what similarity laws must be obeyed when constructing aeroelastic models
# of heated high speed aircraft .
# ('1400', 'the buckling shear stress of simply-supported infinitely\nlong plates ...', -inf)
# ('1399', 'buckling of transverse stiffened plates under shear .', -inf)
# ('1398', 'stability of rectangular plates under shear and bending\nforces .', -inf)
# ('1397', 'critical shear stress of an infinitely long simply\nsupported plate ...', -inf)
# ('1396', 'shear buckling of clamped and simply-supported infinitely\nlong plates ...', -inf)

❗ Something went wrong: all five scores are \(-\infty\) and the "results" are simply the last documents. The word obeyed occurs nowhere in Cranfield, so \(P(obeyed \mid C) = 0\): smoothing with the collection cannot help a word the collection has never seen, every document gets \(-\infty\), and sorted breaks the tie by document position. This happens for 69 of the 225 queries (e.g. obeyed, guides, and tokens with punctuation attached such as attack. or analytical,).

The fix: a term with \(P(w \mid C) = 0\) would multiply every document's score by the same factor, so it cannot change the ranking: skip it.

def query_likelihood_score(query, doc_tokens, lam=0.2):
    doc_counts = Counter(doc_tokens)
    doc_len = len(doc_tokens)
    score = 0.0
    for term in query.lower().split():
        p_collection = collection_prob(term)
        if p_collection == 0:        # not in the collection: same for every document, skip it
            continue
        p_doc = doc_counts[term] / doc_len if doc_len > 0 else 0.0
        score += math.log((1 - lam) * p_doc + lam * p_collection)
    return score

for result in search_ql(queries[0].text):
    print(result)
# ('486', 'similarity laws for aerothermoelastic testing .', -109.74176354210674)
# ('13', 'similarity laws for stressing heated wings .', -110.76355526688077)
# ('1268', 'stable combustion of a high-velocity gas in a heated\nboundary layer .', -111.8573212457509)
# ('184', 'scale models for thermo-aeroelastic research .', -111.89052019470697)
# ('51', 'theory of aircraft structural models subjected to aerodynamic\nheating and external loads .', -112.01345789126577)

What to take from the demo is the pipeline, not the implementation: document → term distribution → smoothed document language model; query → probability under each document model → ranking.

Try it: query likelihood vs BM25 on Cranfield

The fixed query likelihood, computed in your browser. Change \(\lambda\) and the query; compare the top 10 with BM25's, with Cranfield's relevance grades. The plot shows MAP over all 225 queries as a function of \(\lambda\) (computed when you open it), against BM25 and TF-IDF.

💡 Checked against ir_measures (top 100 per query): the outline's query likelihood (\(\lambda = 0.2\), ranked as search_ql ranks) reaches MAP 0.1517, the fixed one 0.2127, and the best \(\lambda\) on the grid above (0.80) 0.2286. On Cranfield with these simple whitespace tokens, query likelihood stays below BM25 (0.2406) and TF-IDF (0.2737); do not conclude that one paradigm is better from one collection and one tokenization (Lab 05).