The recording

Index construction and probabilistic ranking

Information Retrieval for AI

Session 3 - Mon 07 Sep 2026

KAIST AI - Seong Joon Oh

Announcements

Groups. Propose your own on the first-day survey by Mon 14 Sep. Remaining places are filled at random after that.
Discussion sessions begin Wed 30 Sep. The first review is due Tue 29 Sep, 18:00.
Recording. Lectures are recorded. Discussion sessions and project workshops are not.

Course syllabus

The roadmap

Building the index - carried over
Derive BM25 from Bayesian probability
- Relevance odds and term likelihoods
- IDF from Bayesian estimates
- Saturation from a hidden term model
- Length normalisation and the final formula
Predict what a BM25 parameter changes
Query likelihood and feedback

We stop where we stop. The rest opens next time.

One assumption left

The construction so far assumed the term-docID pairs fit in memory.

A larger collection or a smaller memory budget breaks that assumption.

How do we build the same index in blocks?

Introduction to Information RetrievalIntroduction to Information RetrievalManning, Raghavan & Schutze - 2008 - Cambridge University Pressalso session 2, 4, 5, section 4.2, pp. 69-71.

BSBI - blocked sort-based indexing

Blocked sort-based indexing (BSBI) groups by sorting.

Fill memory with (termID, docID) pairs
Sort them
Collapse the runs into postings lists
Write the result out as one sorted block

Keep the global term-to-termID map, clear the block workspace, and continue with the next block. The map is what makes the sort key mean the same term in every block: if one block assigns caesar -> 17 and the next assigns it 4001, the merge emits two entries for one term.

Introduction to Information RetrievalIntroduction to Information RetrievalManning, Raghavan & Schutze - 2008 - Cambridge University Pressalso session 2, 4, 5, section 4.2, pp. 69-71.

Ten blocks

Merging ten sorted indexes. The merge opens ten read buffers and one write buffer.

SPIMI - group by hashing

Process documents in increasing docID order. Use a per-block dictionary from term string to a growing postings list.

caesar,d1  ->  {caesar: [d1]}
brutus,d1  ->  {caesar: [d1], brutus: [d1]}
caesar,d2  ->  {caesar: [d1,d2], brutus: [d1]}

Append a docID once per term-document pair. For repeated occurrences in that document, keep the same posting and increment its count if frequencies are stored.

Token occurrences need no sort. Distinct dictionary terms are sorted at the flush.

IIR §4.3, pp. 73-74; posting deduplication and optional frequency accumulation made explicit.

Stop at the end of block ingestion

	After ingestion, before block finalisation
BSBI	Unsorted termID-docID pairs. The postings lists for this block still need the sort and a collapsing pass.
SPIMI	`caesar -> [d1, d2, d4]`. The docIDs are already grouped by term.

The block still has to be written and merged with the others.

Two decisions

The key representation and the grouping method can be chosen separately.

	Group by sorting	Group by hashing
Key is a termID	BSBI	Another coherent combination
Key is the term string	Another coherent combination	SPIMI

The textbook algorithms occupy two of the four combinations.

The shape in Lucene

Lucene’s IndexWriter buffers changes in memory, flushes segments, and merges segments.

This is the buffering-and-merge shape we saw in SPIMI.

The connection is about the structure of the work, not an identity between implementations.

What transfers from BSBI

Create sorted runs that fit in memory. Merge them through forward cursors.

External merge sort also serves grouping and sorting in database systems.

The technique applies beyond inverted-index construction.

Where it sits

The knowledge-location spectrum:

Non-parametric
Sparse, exact term matching
No learned encoder
Updated by indexing changed documents

What matching has not answered

A document either satisfies the Boolean query or it does not.

The matching set can be large.

Which document should we show first?

Derive the score

TF-IDF gives us a scoring rule to question.

Start with joint and conditional probability in Introduction to Information RetrievalIntroduction to Information RetrievalManning, Raghavan & Schutze - 2008 - Cambridge University Pressalso session 2, 4, 5, section 11.1.

Follow The Probabilistic Relevance FrameworkThe Probabilistic Relevance Framework: BM25 and BeyondRobertson & Zaragoza - 2009 - FnTIRalso session 4 from relevance odds through term likelihoods, saturation and length normalisation.

Two counts, two kinds of evidence

Quantity	What it counts	In our ten-document example
tf(t, d)	Occurrences of t in d	`term` occurs 4 times in d7
df(t)	Documents that contain t	4 documents contain `term`
N	Documents in the collection	10 documents

Repeating a word changes tf. Adding another document that contains it changes df.

IIR §6.2, pp. 117-118; counts computed from the course demo corpus.

Combine repetition with rarity

One TF-IDF weighting scheme is

v_{t, d} = tf (t, d) \log \frac{N}{df (t)} .

For term in d7, using natural logarithms,

v_{t e r m, d 7} = 4 \log \frac{10}{4} \approx 3.665 .

At fixed rarity, this weight is proportional to frequency. If df(t) = N, the IDF and the term weight are zero. Other TF-IDF schemes transform tf before multiplication.

IIR §6.2.2, pp. 118-119

Build document and query vectors

Fix vocabulary V. Give both vectors one coordinate per term, in the same order.

v_{d} = {[t f (t, d) \log \frac{N}{d f (t)}]}_{t \in V}

v_{q} = {[t f (t, q) \log \frac{N}{d f (t)}]}_{t \in V}

Use the same collection IDF for both. An absent term has weight 0.

N = 10; q = term frequency. Three course-corpus coordinates:

Term	Document d₇ coordinate	Query coordinate
term	4 log(10/4) ≈ 3.665	1 log(10/4) ≈ 0.916
frequency	2 log(10/2) ≈ 3.219	1 log(10/2) ≈ 1.609
vector	1 log(10/1) ≈ 2.303	0 log(10/1) = 0

Natural logs; full vectors span V. The live demo counts each distinct query term once.

Compute relevance with cosine similarity between the two vectors.

IIR §6.2.2 and §6.3.1-6.3.2, pp. 120-124

What would justify the score?

TF-IDF chooses a function of repetition and rarity. Cosine chooses a comparison between vectors.

What quantity should a ranking estimate?

Start with the probability that a document is relevant. Derive a score from that target, then inspect the choices needed to make it usable.

Live demo - repeat a keyword

IIR §11.1-11.2, pp. 220-222

Define the relevance we want to predict

Hold the query q fixed throughout the derivation.

Symbol	Meaning
R ∈ {0, 1}	Non-relevant or relevant to the information need
d	The document’s observed word representation
P(R = 1 ∣ d, q)	Relevance probability given that evidence

We observe the words and infer relevance. We will first use term presence, then account for frequency and document length.

IIR §11.1, pp. 220-221

Put more relevant documents near the top

At a cutoff k, choose the results with the largest expected total relevance. Give each relevant result value 1 and each non-relevant result value 0; values add.

𝔼 [\sum_{d \in S} R_{d} | q, 𝒟] = \sum_{d \in S} P (R_{d} = 1 ∣ q, 𝒟)

Here 𝒟 is the observed collection. In our document model, each posterior uses the evidence in d and q.

Swap an included document for one with a larger posterior: the expected total increases. Apply this at each cutoff to obtain descending probability order.

Target: compute a score with the same ordering as P(R = 1 ∣ d, q).

IIR §11.2, pp. 221-222; exchange argument shown here

Use word evidence to infer relevance

The target P(R = 1 ∣ d, q) is unknown. We can build models of how the document’s words occur within each relevance class.

Bayes’ rule connects those models to our target. For r ∈ {0, 1}:

P (R = r ∣ d, q) = \frac{P (d ∣ R = r, q) P (R = r ∣ q)}{P (d ∣ q)}

P(d ∣ R = r, q) is the word evidence under class r; P(R = r ∣ q) is its prior.

The denominator still depends on the document. We cannot drop it when ranking. We need a way to preserve the order without estimating it.

IIR §11.1, pp. 220-221

Cancel the denominator without changing the order

We need an ordering. For 0 < p < 1, p/(1 − p) increases with p, so odds give the same ranking.

Divide the two Bayes expressions. Their shared P(d ∣ q) cancels:

\frac{P (R = 1 ∣ d, q)}{P (R = 0 ∣ d, q)} = \frac{P (R = 1 ∣ q)}{P (R = 0 ∣ q)} \frac{P (d ∣ R = 1, q)}{P (d ∣ R = 0, q)}

The prior odds are the same for every document at this fixed q. Rank by the remaining likelihood ratio.

It compares how well the relevant and non-relevant word models explain this document. Those word models are the next quantity we must specify.

IIR §11.3.1, p. 224; positive likelihoods and non-degenerate prior assumed

Estimate term presence instead of whole documents

Whole-document patterns are too numerous to estimate separately. Start with xₜ = 1 if term t is present, and 0 otherwise.

Let pₜ be its presence probability in relevant documents and uₜ its presence probability in non-relevant documents, at this q.

Model choices: presence variables are independent given R and q; pₜ = uₜ for non-query terms. Those non-query factors cancel.

\frac{P (x ∣ R = 1, q)}{P (x ∣ R = 0, q)} = \prod_{t \in q} \frac{p_{t}^{x_{t}} (1 - p_{t})^{1 - x_{t}}}{u_{t}^{x_{t}} (1 - u_{t})^{1 - x_{t}}}

The binary representation is a modelling choice. q denotes distinct query terms in the product.

IIR §11.3-11.3.1, pp. 223-225

Add the evidence from the query terms

The model gives a product of term factors. We want a score we can accumulate one term at a time.

Log is strictly increasing on positive values. It preserves the ranking and turns the product into a sum:

s (q, d) = \sum_{t \in q} [x_{t} \log \frac{p_{t}}{u_{t}} + (1 - x_{t}) \log \frac{1 - p_{t}}{1 - u_{t}}]

A present term selects the first contribution; an absent term selects the second.

The score still includes missing query terms. The index gives us the documents that match each term. We need to express the score through those matches.

IIR §11.3.1, pp. 224-225

Use absence as a shared reference

Start with the score for absence of every query term. It depends on q and the term probabilities, not on which document we rank:

C (q) = \sum_{t \in q} \log \frac{1 - p_{t}}{1 - u_{t}}

Subtract that same reference from every score:

s (q, d) - C (q) = \sum_{t \in q : x_{t} = 1} [\log \frac{p_{t}}{u_{t}} - \log \frac{1 - p_{t}}{1 - u_{t}}]

The ordering is unchanged. Each match replaces its absence contribution; each absent term now contributes zero.

IIR §11.3.1, p. 225

Obtain one weight for each matching term

The contribution of a match is the difference we just obtained. Combine the logarithms:

w_{t} = \log \frac{p_{t}}{u_{t}} - \log \frac{1 - p_{t}}{1 - u_{t}} = \log \frac{p_{t} (1 - u_{t})}{u_{t} (1 - p_{t})}

The log odds ratio is the result of that subtraction: presence evidence relative to absence.

{score}_{B I M} (q, d) = \sum_{t \in q : x_{t} = 1} w_{t}

This is the binary independence model (BIM). The score is specified once we estimate pₜ and uₜ.

IIR §11.3.1, pp. 225-226

Estimate the probabilities without relevance labels

We have document frequencies but no relevance labels. A Beta(½, ½) prior for the presence probability θ keeps predictive estimates strictly between 0 and 1, so log weights stay finite.

For n Bernoulli observations independent given θ, with c presences, the posterior predictive probability is

\hat{θ} = 𝔼 [θ ∣ c, n] = \frac{c + \frac{1}{2}}{n + 1}

Needed estimate	Evidence, choice and result
Relevant presence pₜ	No observations, n = c = 0: pₜ = 0.5
Non-relevant presence uₜ	Collection proxy, n = N and c = df(t): uₜ = (df(t) + 0.5)/(N + 1)

The half-count prior and background proxy are estimation choices. The collection has not been labelled non-relevant.

IIR §11.3.2-11.3.3, pp. 226-227; Beta predictive rule made explicit here

Substitute the estimates to obtain IDF

The relevant-class presence odds are pₜ/(1 − pₜ) = 1. Substitute uₜ into the weight:

w_{t} = \log \frac{1 - u_{t}}{u_{t}} = \log \frac{N - d f (t) + 0.5}{d f (t) + 0.5} \equiv {i d f}_{R S J} (t)

This is the probabilistic IDF form of the Robertson-Sparck Jones weight. Document frequency now determines the contribution of a match.

For 1 ≪ df(t) ≪ N, neglect the half counts and use N − df(t) ≈ N:

{i d f}_{R S J} (t) \approx \log \frac{N}{d f (t)}

We have a rarity weight. Term repetition has not entered the score yet.

IIR §11.3.3, p. 227