FINDING NEEDLES · CHAPTER 02
Boolean search can tell you that a note contains the words. It cannot tell you which note to open first. A score can.
Chapter 1 ended with a list of document ids. Every id on that list was equally a hit. A person scanning results wants the best note at the top, not the first id that happened to contain both words.
Give each note a vector. One axis per word. The number on an axis says how much that word matters in that note. The query is a vector in the same space. Closeness is the score.
A word that shows up often in one note should count. A word that shows up in every note should not, because it does not pick a note out of the drawer. TF-IDF is those two ideas multiplied.
Four notes. The query is “cumin jar”.
match · TF/IDF · score · BoW
| Note | Text | Raw counts |
|---|---|---|
| 1 | cumin cumin clove | cumin 2, clove 1 |
| 2 | clove jar | clove 1, jar 1 |
| 3 | cumin jar jar | cumin 1, jar 2 |
| 4 | saffron | saffron 1 |
Raw count is the simplest term frequency. Note 1 says cumin twice, so its cumin coordinate starts at 2. That is fair inside one note. It is unfair across notes of different lengths: a long page can mention a word more often without being more about it. The fix used later, in BM25, is to let extra mentions matter less. This chapter keeps the raw count so the arithmetic stays exact.
Document frequency is the number of notes that contain the word at least once. “jar jar” is still one note. With N = 4:
| Term | df | idf = log2(N / df) |
|---|---|---|
| cumin, clove, jar | 2 | log2(4/2) = 1 |
| saffron | 1 | log2(4/1) = 2 |
Saffron is the rare word, so it carries twice the weight of cumin. That weight only helps a query that asks for saffron. Ours does not.
count the word in this note, then multiply by how surprising the word is in the whole drawer.
Every vector uses the axis order cumin, clove, jar, saffron. The query “cumin jar” has tf 1 and 1, and both idf weights are 1, so the query vector is (1, 0, 1, 0).
| Note | TF-IDF vector | Cosine | Distance |
|---|---|---|---|
| 1 | (2, 1, 0, 0) | 0.632 | 1.732 |
| 2 | (0, 1, 1, 0) | 0.500 | 1.414 |
| 3 | (1, 0, 2, 0) | 0.949 | 1.000 |
| 4 | (0, 0, 0, 2) | 0 | 2.449 |
Cosine uses the angle, so a longer vector is not punished for being longer. It ranks note 3, then 1, then 2, then 4. The scores are 0.949, 0.632, 0.500, and 0.
Straight-line distance uses the length as well. It ranks note 3, then 2, then 1, then 4, at 1.000, 1.414, 1.732, and 2.449. Note 1 loses to note 2 under distance because the extra cumin and the clove push it farther from the query, even though its direction is closer.
shared weight, divided by the two lengths. The lengths cancel the “this note is just longer” effect.
Interactive · Two ways to sort the same vectors
Cosine wants a high score. Distance wants a low one. Watch notes 1 and 2 trade places.
Note 4 scores 0 on cosine. Its only word is saffron, and the query never says saffron. A large idf cannot rescue a word the question did not ask.
"""TF-IDF on a four-note spice drawer.
Raw term count times log2(N / df). Cosine ranks the query
"cumin jar". Euclidean distance ranks two of the notes differently.
"""
import math
# Four notes. Ids match the table on the page.
DOCS = {
1: "cumin cumin clove",
2: "clove jar",
3: "cumin jar jar",
4: "saffron",
}
QUERY = "cumin jar"
# Axis order for every vector: cumin, clove, jar, saffron.
VOCAB = ["cumin", "clove", "jar", "saffron"]
def tokenize(text):
"""Lowercase words, split on spaces. This chapter keeps every word."""
return text.lower().split()
def counts(tokens):
"""How many times each term appears. That count is raw tf."""
tally = {}
for term in tokens:
tally[term] = tally.get(term, 0) + 1
return tally
def document_frequency(docs=None):
"""How many documents contain the term at least once.
Repeats inside one note do not raise df. "jar jar" is still one document.
"""
docs = DOCS if docs is None else docs
df = {term: 0 for term in VOCAB}
for text in docs.values():
seen = set(tokenize(text))
for term in VOCAB:
if term in seen:
df[term] += 1
return df
def idf_weights(docs=None):
"""log2(N / df). A term in every note would score 0. A term in one note scores 2 when N is 4."""
docs = DOCS if docs is None else docs
n = len(docs)
df = document_frequency(docs)
return {term: math.log2(n / df[term]) for term in VOCAB}
def vector(text, idf):
"""One weight per vocab term: tf times idf. A missing term is 0."""
tally = counts(tokenize(text))
return [tally.get(term, 0) * idf[term] for term in VOCAB]
def dot(left, right):
return sum(x * y for x, y in zip(left, right))
def norm(values):
return math.sqrt(dot(values, values))
def cosine(left, right):
"""1 means the same direction. 0 means no shared weighted term."""
return dot(left, right) / (norm(left) * norm(right))
def euclidean(left, right):
"""Straight-line distance. Longer vectors sit farther out, even on the same topic."""
return math.sqrt(sum((x - y) ** 2 for x, y in zip(left, right)))
def _scored(score_fn, higher_is_better):
idf = idf_weights()
query = vector(QUERY, idf)
rows = []
for doc_id in sorted(DOCS):
rows.append((doc_id, score_fn(query, vector(DOCS[doc_id], idf))))
rows.sort(key=lambda row: row[1], reverse=higher_is_better)
return rows
def rank_cosine():
return _scored(cosine, higher_is_better=True)
def rank_euclidean():
"""Smaller distance is a closer note."""
return _scored(euclidean, higher_is_better=False)
Counting repeats toward document frequency. “jar jar” is one note that contains jar. df stays 1 for that note, not 2. If you add the raw count into df, rare words that are repeated look common.
Treating a high idf as a reason to rank the note. Saffron’s idf is 2. The query did not ask for it, so note 4 is the worst cosine, not the best.
Reading the vector as a sentence. “cumin jar” and “jar cumin” build the same query vector. Order, negation, and phrases are invisible. That is the bag of words.
Its only term is saffron. The query vector is zero on that axis, so the dot product is zero.
Note 1 points more toward the query, so the angle is better. It also sits farther from the query point, because of the extra cumin and the clove. Distance charges for that. Cosine does not.
Nothing beyond the one note. df counts notes, not copies.
No. Both words still have tf 1. The bag of words forgets the order.