FINDING NEEDLES · CHAPTER 02

TF-IDF

Boolean search can tell you that a note contains the words. It cannot tell you which note to open first. A score can.

~14 min read4 notesTested Python

What you'll learn

  • Why a raw word count favors a long note
  • Why a rare word is worth more than a word in half the drawer
  • How TF times IDF turns a note into a vector
  • Why cosine and straight-line distance disagree on two of these notes

Before you start

  • How search works — a match is not a ranking
  • A dot product, and the length of a vector

A match is not an order

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.

How many times, in this note

Four notes. The query is “cumin jar”.

match · TF/IDF · score · BoW

MANIM TF-IDF: matches are not ranks until IDF weights them.
NoteTextRaw counts
1cumin cumin clovecumin 2, clove 1
2clove jarclove 1, jar 1
3cumin jar jarcumin 1, jar 2
4saffronsaffron 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.

How rare the word is in the drawer

Document frequency is the number of notes that contain the word at least once. “jar jar” is still one note. With N = 4:

Termdfidf = log2(N / df)
cumin, clove, jar2log2(4/2) = 1
saffron1log2(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.

Same axes, then the angle

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).

NoteTF-IDF vectorCosineDistance
1(2, 1, 0, 0)0.6321.732
2(0, 1, 1, 0)0.5001.414
3(1, 0, 2, 0)0.9491.000
4(0, 0, 0, 2)02.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.

The ranking you can re-run

tfidf.pycosine 3 > 1 > 2 > 4
"""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)

Mistakes learners make

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.

What to remember

  • TF is the count inside one note. IDF is log2(N / df). Here saffron’s idf is log2(4/1) = 2, and the other three words are 1.
  • The query vector is (1, 0, 1, 0). Note 3 is (1, 0, 2, 0) and wins both rankings.
  • Cosine order is 3, 1, 2, 4 at 0.949, 0.632, 0.500, 0. Distance order is 3, 2, 1, 4 at 1.000, 1.414, 1.732, 2.449.
  • A rare word only helps if the query uses it.

Check yourself

1. Why is note 4’s cosine 0?

Its only term is saffron. The query vector is zero on that axis, so the dot product is zero.

2. Why does distance rank note 2 ahead of note 1, while cosine does the opposite?

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.

3. What would “jar jar” do to jar’s document frequency?

Nothing beyond the one note. df counts notes, not copies.

4. Would “jar cumin” change the query vector?

No. Both words still have tf 1. The bag of words forgets the order.

Go to the source

Keep going