Relevance Scoring

The previous lesson always computed score with a placeholder formula: first satisfied-condition count, then term frequency divided by field length. Both produced an ordering, but both skipped half the question. A term occurring in a document carries no meaning without knowing how rare that term is across the corpus: the word “and” occurs in every one of the catalog’s 6,000 summaries and distinguishes nothing, “astronomy” occurs in about two hundred summaries and nearly determines the document by itself.

Relevance score is built from three components. Term frequency is how many times the term occurs in the document, and it saturates — a fifth occurrence says less than the first. Inverse document frequency is the term’s rarity across the corpus; a rare term carries much weight, a common term carries little. Field length normalization distinguishes a match in a three-word title from a match in a fourteen-word summary. This lesson builds the scorer, shows which component a document’s position comes from, and defines two measures for how correct the result is.

Corpus, Model, and Requirement

The corpus is the previous lessons’ module: 6,000 book records, seed 271828, deterministic generation. QR8 (assumption): the scored fields are title and summary; there is no field weight, the two are summed one-to-one. The term frequency saturation constant is 1.2, the field length normalization constant is 0.75; inverse document frequency is found from the logarithm of the ratio between corpus size and document frequency. QR9 (assumption): the reader’s requirement is broader than the query — they are looking for “a children’s book tagged story, in english”, but type only “children story” into the search box. The tag, language, and year fields are not indexed in this lesson; the scorer cannot see the requirement’s language criterion. This is the ordinary state of affairs in a real catalog.

// corpus.mjs — library catalog corpus and position-aware inverted index.
// Seed 271828, 6000 documents; every measurement in the topic shares this module.
export const SEED = 271828, N = 6000;
let c = SEED;                                        // visible seed, deterministic generator
const r = () => { c = (c + 0x6d2b79f5) | 0; let t = Math.imul(c ^ (c >>> 15), 1 | c);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
const pick = (d, e = 1) => d[Math.floor(r() ** e * d.length)];  // e>1: early items frequent, late items sparse

const ADJECTIVE = ["critical", "short", "illustrated", "selected", "comparative"];
const GENRE = ["essay", "story", "novel", "study", "anthology"];
const CATEGORY = ["children", "history", "science", "philosophy", "society"];
const SUFFIX = ["selection", "book", "compilation", "series"];
const QUALIFIER = ["comprehensive", "concise", "introductory", "contentious"];
const SUBJECT = ["education", "migration", "city", "memory", "nature", "music", "law", "identity", "labor", "family",
  "war", "tradition", "health", "travel", "architecture", "archaeology", "seafaring", "astronomy"];
const AUTHOR = ["James Miller", "Anna Clarke", "Peter Brooks", "Laura Bennett", "Henry Cole"];
const LANGUAGE = ["english", "german", "french"];

export const CATALOG = [];
for (let i = 1; i <= N; i += 1) {
  const s = pick(ADJECTIVE, 1.5), t = pick(GENRE, 1.5), a = pick(CATEGORY, 2), k = r();
  const pattern = k < 0.18 ? `${s} ${t}` : k < 0.30 ? `${s} meets ${t}`
    : k < 0.40 ? `${s} and theoretical ${t}` : k < 0.50 ? `${t} and ${s} study`
    : k < 0.70 ? `${s} narrative piece` : k < 0.88 ? `a contemporary ${t}` : "review of literature";
  CATALOG.push({ id: `K-${String(i).padStart(4, "0")}`, title: `${a} ${t} ${pick(SUFFIX)}`,
    summary: `${a} field: ${pattern}; readable on ${pick(SUBJECT, 3)} and ${pick(SUBJECT, 3)} as ` +
      `a ${pick(QUALIFIER)} ${pick(GENRE, 1.5)}.`,
    tag: [a, t], author: pick(AUTHOR), year: 1990 + Math.floor(r() * 35), language: pick(LANGUAGE, 2) });
}

export const tokenize = (m) => m.toLocaleLowerCase("en-US").split(/[^\p{L}\p{N}]+/u).filter(Boolean);

// Inverted index: "field|term" -> Map(document index -> positions); length: token count per document field.
export function invertedIndex(fields) {
  const postings = new Map(), length = new Map();
  CATALOG.forEach((b, i) => {
    for (const field of fields) {
      const tk = tokenize(String(b[field]));
      length.set(`${field}|${i}`, tk.length);
      tk.forEach((t, p) => {
        let list = postings.get(`${field}|${t}`); if (!list) postings.set(`${field}|${t}`, (list = new Map()));
        let positions = list.get(i); if (!positions) list.set(i, (positions = [])); positions.push(p);
      });
    }
  });
  return { postings, length };
}

Scorer

// score.mjs — relevance scorer. corpus.mjs is in the same directory.
// Score comes from three components: term frequency (which saturates), inverse document
// frequency, and field length normalization.
import { CATALOG, SEED, invertedIndex } from "./corpus.mjs";
const { postings, length } = invertedIndex(["title", "summary"]);          // tag, language, and year are not indexed
const N = CATALOG.length, FIELDS = ["title", "summary"], K = 1.2, B = 0.75;
const list = (field, term) => postings.get(`${field}|${term}`) ?? new Map();
const avgLength = Object.fromEntries(FIELDS.map((f) => {
  let t = 0; for (let d = 0; d < N; d += 1) t += length.get(`${f}|${d}`); return [f, t / N];
}));
const idf = (field, term) => { const df = list(field, term).size; return Math.log(1 + (N - df + 0.5) / (df + 0.5)); };

function component(field, term, d, mode) {
  const tf = (list(field, term).get(d) ?? []).length;
  if (tf === 0) return 0;
  if (mode === "term frequency only") return tf;
  if (mode === "term x inverse document frequency") return tf * idf(field, term);
  const len = length.get(`${field}|${d}`) / avgLength[field];      // field length normalization
  return idf(field, term) * (tf * (K + 1)) / (tf + K * (1 - B + B * len));
}
const scoreDoc = (d, mode) => TERM.reduce((p, t) => p + FIELDS.reduce((q, f) => q + component(f, t, d, mode), 0), 0);
const TERM = ["children", "story"], MODES = ["term frequency only", "term x inverse document frequency", "full model"];

const candidate = [...Array(N).keys()].filter((d) => TERM.every((t) => FIELDS.some((f) => list(f, t).has(d))));
const relevant = new Set(candidate.filter((d) => CATALOG[d].tag.includes("children")
  && CATALOG[d].tag.includes("story") && CATALOG[d].language === "english"));
console.log(`corpus ${N} documents, seed ${SEED};  question "children story"`);
console.log(`candidate set ${candidate.length} documents;  requirement: tagged children+story and english -> ${relevant.size} documents relevant`);
for (const t of TERM) for (const f of FIELDS)
  console.log(`  ${f}|${t}`.padEnd(21) + `document frequency ${String(list(f, t).size).padStart(4)}   ` +
    `inverse document frequency ${idf(f, t).toFixed(3)}   average field length ${avgLength[f].toFixed(2)}`);

const rankedBy = (mode) => [...candidate].sort((x, y) => scoreDoc(y, mode) - scoreDoc(x, mode) || x - y);
const full = rankedBy("full model");
console.log("score components: first and five-hundredth position");
for (const d of [full[0], full[499]]) {
  const parts = [];
  for (const t of TERM) for (const f of FIELDS) {
    const k = component(f, t, d, "full model");
    if (k > 0) parts.push(`${f}|${t} ${k.toFixed(2)} (frequency ${(list(f, t).get(d) ?? []).length}, length ${length.get(`${f}|${d}`)})`);
  }
  console.log(`  ${String(full.indexOf(d) + 1).padStart(3)}. ${CATALOG[d].id} score ${scoreDoc(d, "full model").toFixed(2)} = ${parts.join(" + ")}`);
}

const precision = (l, k) => l.slice(0, k).filter((d) => relevant.has(d)).length / Math.min(k, l.length);
const recall = (l, k) => l.slice(0, k).filter((d) => relevant.has(d)).length / relevant.size;
console.log("ranking model".padEnd(36) + "distinct scores  top ten shared  largest movement  precision@10  precision@50");
for (const mode of MODES) {
  const l = rankedBy(mode);
  const values = new Set(candidate.map((d) => scoreDoc(d, mode).toFixed(6))).size;
  const shared = l.slice(0, 10).filter((d) => full.slice(0, 10).includes(d)).length;
  const movement = Math.max(...candidate.map((d) => Math.abs(l.indexOf(d) - full.indexOf(d))));
  console.log(mode.padEnd(36) + String(values).padStart(11) + String(shared).padStart(14) +
    String(movement).padStart(17) + precision(l, 10).toFixed(3).padStart(13) + precision(l, 50).toFixed(3).padStart(13));
}
console.log(`unranked set: precision ${(relevant.size / candidate.length).toFixed(3)}, recall 1.000`);
for (const k of [10, 50, 200, 567, 984])
  console.log(`  top ${String(k).padStart(3)} results: precision ${precision(full, k).toFixed(3)}  recall ${recall(full, k).toFixed(3)}`);
const wrong = full.slice(0, 50).filter((d) => !relevant.has(d));
console.log(`the first of the ${wrong.length} wrong documents in the top 50 is ${CATALOG[wrong[0]].id}: ` +
  `${CATALOG[wrong[0]].title}, language ${CATALOG[wrong[0]].language}, tag ${CATALOG[wrong[0]].tag.join("+")}`);

corpus 6000 documents, seed 271828;  question "children story"
candidate set 984 documents;  requirement: tagged children+story and english -> 347 documents relevant
  title|children     document frequency 2678   inverse document frequency 0.807   average field length 3.00
  summary|children   document frequency 2678   inverse document frequency 0.807   average field length 14.02
  title|story        document frequency 1271   inverse document frequency 1.552   average field length 3.00
  summary|story      document frequency 1869   inverse document frequency 1.166   average field length 14.02
score components: first and five-hundredth position
    1. K-0078 score 4.83 = title|children 0.81 (frequency 1, length 3) + summary|children 0.83 (frequency 1, length 13) + title|story 1.55 (frequency 1, length 3) + summary|story 1.64 (frequency 2, length 13)
  500. K-3736 score 3.17 = title|children 0.81 (frequency 1, length 3) + summary|children 0.81 (frequency 1, length 14) + title|story 1.55 (frequency 1, length 3)
ranking model                       distinct scores  top ten shared  largest movement  precision@10  precision@50
term frequency only                           3             3              468        0.700        0.640
term x inverse document frequency             4             3              342        0.700        0.640
full model                                   10            10                0        0.600        0.640
unranked set: precision 0.353, recall 1.000
  top  10 results: precision 0.600  recall 0.017
  top  50 results: precision 0.640  recall 0.092
  top 200 results: precision 0.615  recall 0.354
  top 567 results: precision 0.612  recall 1.000
  top 984 results: precision 0.353  recall 1.000
the first of the 18 wrong documents in the top 50 is K-0171: children story selection, language french, tag children+story

Where a Position Comes From

The first table gives the source of the components. “Children” occurs in 2,678 documents and its inverse document frequency is 0.807; “story” occurs in 1,271 book titles and carries 1.552. The same term occurs in 1,869 summaries, and there it is only 1.166 — the same word’s weight changes from field to field, because rarity is measured within the field.

The first-position document, K-0078, has a score of 4.83 and is the sum of four components, each greater than zero. Of that score, 3.19 — 66% — comes from the term “story”; “children” contributes 1.64. What determines order is the query’s rare term. The five-hundredth-position document, K-3736, has the same three components and its only difference is that the fourth component is missing: “story” never occurs in its summary. The absence of one component costs 1.66 points and 499 positions. Both are children’s story books in the catalog; the only difference is that one’s summary mentions the genre twice.

Field length’s contribution is smaller but visible. K-0078’s summary is 13 tokens, K-3736’s is 14; the average is 14.02. This one-token difference lowers the summary|children component from 0.83 to 0.81. In the title field, average length is exactly 3.00, because every title is three words, so the normalization has no effect there, so field length distinguishes nothing where every title is the same length; normalization only works where length varies.

Three Models, Three Orders

The model table measures what the components do to order. With term frequency alone, the 984 candidate documents take only 3 distinct score values: the list splits into three piles and order within a pile falls to document number. Once inverse document frequency is added, the value count rises to 4; once field length normalization is also added, it rises to 10. As resolution rises, ties get broken and the list is reshuffled. Against the full model, the largest position movement is 468 in the term-frequency-only model, 342 in the intermediate model — in a 984-document list, this means a document moves from the middle to the front.

In the top ten results, the three models share only 3 documents; the full model’s top-ten precision is 0.600, below the other two models’ 0.700. This does not show the full model is worse: in the top fifty all three models come to 0.640, and the difference is noise from a measure the model cannot see. Choosing a model from a ten-result sample misuses the measure itself.

Precision and Recall

Two measures ask how correct the result is from different directions. Precision is how much of the returned result is relevant: it penalizes a document wrongly returned. Recall is how much of the relevant documents were returned: it penalizes a document missed. The same pair goes by other names in the same field elsewhere in this platform: in the Non-Functional Testing curriculum’s Static Application Security Testing lesson, a finding wrongly reported is a false positive, a real vulnerability never reported is a miss; precision measures false positives, recall measures misses.

The unranked set is 984 documents and holds 347 relevant documents: precision 0.353, recall 1.000. This is the typical balance of a Boolean query — no relevant document is missed, but two-thirds are unneeded. Ranking ties this balance to the cutoff point. In the top 50 results precision rises to 0.640, recall falls to 0.092. In the top 200, precision is 0.615, recall 0.354. At the top 567, recall reaches 1.000: all 347 relevant documents sit within the first 58% of the list, meaning the scorer has never pushed a relevant document to the bottom of the list.

Precision sticking around 0.64 is this lesson’s final finding. The first of the 18 wrong documents in the top 50 is K-0171, and its title is “children story selection” — exactly the kind of book the reader is looking for, only it is in French. The scorer has ranked it high correctly, since it is a textually flawless match; what fails the requirement sits in a field the scorer never sees. The rule is this: when a criterion sits in a field the scorer cannot see, no weight adjustment raises precision. The right tool is the previous lesson’s filter; a score adjustment only works in fields the model can see.

Summary

• Relevance score comes from three components: saturating term frequency, inverse document frequency, and field length normalization; the same term carries 1.552 weight in a book title, 1.166 in a summary.
• 66% of the first-position document’s 4.83 score comes from the query’s rare term; the absence of one component costs 1.66 points and 499 positions.
• Resolution rises as components are added: the 984 candidate documents take 3, 4, and 10 distinct score values; the largest position movement is 468.
• Precision is how much of the returned result is relevant, recall is how much of the relevant documents were returned; in the unranked set precision is 0.353 and recall is 1.000.
• Ranking raises precision to 0.640 in the top 50 results and carries recall to 1.000 by the top 567; but because the requirement’s language criterion is not indexed, precision hits a ceiling around 0.64.

Next Step

The scorer works, and which component a produced order comes from can now be seen. This does not mean the order is the wanted order. For a library, a match in a book’s title is a stronger signal than a match in its summary, yet in the current model the two are just summed one-to-one. Newer printings might be wanted to rank ahead of older ones, but publication year does not enter the score at all. Loan count, a quantity unrelated to the text, might enter the ranking too. All of these are outside interventions on the score’s components, each changing order without changing the set — like the should condition, but now with a measured coefficient. The next lesson builds these adjustments and counts how many documents each adjustment moves in the top ten results and by how many points it shifts precision.