ConceptDBISAI-written · not yet proofread

Term Frequency

Also Term Frequencies · tf

The term frequency tf(w, D) is the number of times word w occurs in document D; it is the first, naive score of the posting of D in the inverted list of w.

Know these firstInverted Index

Formula#

With tf scores, the score of document $D$ for a keyword query $q = w_1 \dots w_m$ is the sum of the posting scores, computed while merging the inverted lists:

\mathrm{score}(D) = \sum_{j=1}^{m} \mathrm{tf}(w_j, D).

In the Vector Space Model with the tf term-document matrix $A$ ( $A_{ij} = \mathrm{tf}(t_i, D_j)$ ) and the 0/1 query vector $q$ , this is $q^T A$ for all documents at once.

Properties#

$\mathrm{tf}(w, D) = 0 \iff w \notin D$ ; only non-zero tf values are stored (one posting each).
Construction: appending the document ID once per occurrence of $w$ (as in the Lecture 1 code) already encodes tf implicitly: $\mathrm{tf}$ is the number of times the ID appears in the list. Counting them gives the $(D, \mathrm{tf})$ postings in the same linear pass (DBIS_VL02 > Implementation advice).
Summing $\mathrm{tf}(w, D)$ over all documents gives the total frequency of $w$ in the collection, the $F_n$ of Zipf’s Law.
Problems of tf as a score (DBIS_VL02 > Scores: tf, df, idf):
- Words that are frequent in many documents regardless of content (of, the) dominate the score sum. Fix: weight by idf, giving tf.idf.
- Longer documents have larger tf without being more relevant, and relevance does not grow linearly with tf. Fix: the saturating, length-normalized $\mathrm{tf}^*$ of BM25.

Example#

Exampletf postings and score sum (lecture example)

university  …, 57 5,  …, 123 2,  …
of          …, 57 14, …, 123 23, …
freiburg    …, 57 3,  …, 123 1,  …
SCORE SUM   …, 57 22, …, 123 26, …

Document 123 gets the higher tf score sum only because it contains of more often.

ExampleInverted index with tf scores (exam WS 23/24, Task 1.1)

$D_1$ = b c a c d c, $D_2$ = b c a c d c b c, $D_3$ = a d a c c b, $D_4$ = c a a c c.

word	postings $(D, \mathrm{tf})$
a	$(D_1, 1), (D_2, 1), (D_3, 2), (D_4, 2)$
b	$(D_1, 1), (D_2, 2), (D_3, 1)$
c	$(D_1, 3), (D_2, 4), (D_3, 2), (D_4, 3)$
d	$(D_1, 1), (D_2, 1), (D_3, 1)$

Sources#

Slides 02, p. 11, Slides 02, p. 18
Slides 11, p. 6, Slides 11, p. 8
DBIS_VL01 > Inverted Index (record ID + count as alternative posting), DBIS_VL02 > Scores: tf, df, idf, DBIS_VL11 > Retrieval as a matrix-vector product
Exams: DBIS Exam WS2324 (not published) Task 1.1

Connections

Prerequisites know first1

Inverted Index

Required by builds on this2

Mentioned in inline links9

BM25
where $\mathrm{tf} = \mathrm{tf}(w, D)$ is the term frequency, $N$ the number of documents, $\mathrm{df}_w$ the number of documents containing $w$ , $\mathrm{DL}$ the length of $D$ and $\mathrm{AVDL}$ the average document length (both in wo… §
Inverted Index
An inverted index is a data structure that maps each distinct term $t$ to a sorted list of documents containing $t$ , called an inverted list (or postings list). Each entry in the list pairs the document identifier with a score (commonly tf… §
TF-IDF
Let $N$ be the number of documents of the collection, $\mathrm{tf}(w, D)$ the term frequency of word (term) $w$ in document $D$ (number of occurrences), and $\mathrm{df}_w$ the document frequency of $w$ (number of documents containing $w$ )… §
A word that occurs often in $D$ is likely important for $D$ . Used alone as a score, tf lets frequent function words (of, the) dominate the score sum, see Term Frequency. §
Vector Space Model
This again corresponse to the term frequencies from Lecture 2 Slide 10 §
Zipf's Law
Frequency here is the collection frequency (sum of the term frequencies over all documents), not the document frequency $\mathrm{df}$ . §
VL01 – Introduction, Inverted Index, Zipf's Law
For Exercise Sheet 1, each inverted list contains a record ID at most once, even if the record contains the word several times. Alternative: store pairs (record ID, count), which Lecture 2 uses for ranking (term frequency). §
VL02 – Ranking and Evaluation
$\mathrm{tf}$ of word $w$ in document $D$ is the number of times $w$ occurs in $D$ . (Slide 11, term frequencies) §
term frequencies — tf as the first, naive posting score §
VL11 – Vector Space Model, Word Embeddings
Each row corresponds to a word, each column to a document. A non-zero entry is the score of that word in that document; the lecture uses tf scores, ES11 uses BM25 scores. §
term frequencies — tf entries of the running example; the dot product reproduces the tf score sum of Lecture 2 §
Inverted Index and Ranking
Term Frequency — number of occurrences of a word in a document; the naive posting score §
| tf | $\mathrm{tf}$ | none | frequent words (of) dominate | §

Search in these mentions →