ConceptDBISAI-written · not yet proofread

TF-IDF

Also tf.idf · tfidf · Inverse Document Frequency · idf

tf.idf is the score of a word w in a document D, tf(w, D) · log2(N / df_w): the term frequency weighted by the inverse document frequency, so that words occurring in many documents count little.

Know these firstTerm Frequency Inverted Index

Formula#

Term Frequency (tf)#

\mathrm{tf}(w, D) = \text{number of occurrences of } w \text{ in } D.

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.

Inverse Document Frequency (idf)#

\mathrm{idf}_w = \log_2 \frac{N}{\mathrm{df}_w}

$N$ : total number of documents in the collection.
$\mathrm{df}_w$ : number of documents containing $w$ . In an Inverted Index this is simply the length of the inverted list of $w$ .

idf is a proxy for the rarity of a word: the more documents contain $w$ , the smaller $\mathrm{idf}_w$ . A word in every document gets $\mathrm{idf} = \log_2 1 = 0$ ; a word in half the documents gets $\mathrm{idf} = 1$ . The $\log_2$ damps the effect: without it, small differences in $\mathrm{df}$ would have too much influence.

Term-document matrix and ranking#

Arranging the tf.idf scores of all terms and documents gives the term-document matrix $A$ of the Vector Space Model, with rows = terms, columns = documents:

A_{ij} = \text{tf.idf}(t_i, D_j).

For a query vector $q$ (1 for each query term, 0 otherwise), the score of document $D_j$ is the dot product

\mathrm{score}(D_j) = q^T A_{:,j} = \sum_i q_i \, A_{ij},

which is the same as summing the posting scores while merging the inverted lists of the query words. Documents are ranked by descending score. $A$ is typically sparse.

Properties#

$\text{tf.idf}(w, D) = 0$ if $w \notin D$ (since $\mathrm{tf} = 0$ ).
$\text{tf.idf}(w, D) = 0$ if $w$ occurs in every document ( $\mathrm{idf} = \log_2 1 = 0$ ), i.e. such a word does not influence the ranking at all.
The idf part is fine; the tf part has two problems (DBIS_VL02 > tf.idf):
1. Length: longer documents tend to have larger tf, without being more “about” $w$ .
2. Linearity: doubling tf makes the document only a little more “about” $w$ , not twice as much.
BM25 fixes both by replacing $\mathrm{tf}$ with a saturating, length-normalized $\mathrm{tf}^*$ and keeps the same idf factor.

Example#

ExampleLecture example: university of freiburg

$N = 2^{20}$ , $\mathrm{df}_{university} = 2^{14}$ , $\mathrm{df}_{of} = 2^{19}$ , $\mathrm{df}_{freiburg} = 2^{10}$ , so $\mathrm{idf}_{university} = 6$ , $\mathrm{idf}_{of} = 1$ , $\mathrm{idf}_{freiburg} = 10$ .

word	tf in 57	tf.idf in 57	tf in 123	tf.idf in 123
university	5	$5 \cdot 6 = 30$	2	$2 \cdot 6 = 12$
of	14	$14 \cdot 1 = 14$	23	$23 \cdot 1 = 23$
freiburg	3	$3 \cdot 10 = 30$	1	$1 \cdot 10 = 10$
score sum	22	74	26	45

With tf alone, document 123 wins only because it contains of more often; with tf.idf, document 57 wins.

Exampletf.idf matrix (exam WS 21/22, Task 1.1)

$D_1$ = bla bla bla, $D_2$ = bli blu blo, $D_3$ = bla blo, $D_4$ = blu blu; $N = 4$ . $\mathrm{df}$ : bla 2, bli 1, blu 2, blo 2, so $\mathrm{idf}_{bli} = \log_2 4 = 2$ and all other idf values are $\log_2 2 = 1$ .

	$D_1$	$D_2$	$D_3$	$D_4$
bla	3	0	1	0
bli	0	2	0	0
blu	0	1	0	2
blo	0	1	1	0

Query “bla bli”, $q = (1, 1, 0, 0)^T$ : $q^T A = (3, 2, 1, 0)$ , ranking $D_1, D_2, D_3, D_4$ .

Sources#

Slides 02, p. 11 (tf), Slides 02, p. 12 (df, idf), Slides 02, p. 13 (tf.idf), Slides 02, p. 14 (problems)
DBIS_VL02 > Scores: tf, df, idf, DBIS_VL02 > tf.idf
DBIS_VL11 > Vector Space Model: documents as vectors (term-document matrix)
Exams: DBIS Exam WS1617 (not published) Task 1.1–1.3, DBIS Exam WS2122 (not published) Task 1.1–1.2

Connections

Required by builds on this1

BM25

Mentioned in inline links6

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… §
Term Frequency
Words that are frequent in many documents regardless of content (of, the) dominate the score sum. Fix: weight by idf, giving tf.idf. §
Zipf's Law
Consequences for the Inverted Index: a few words (the, of) have very long inverted lists, most words very short ones. Hence ordering the lists by length before intersecting pays off, and frequent words need a low weight in ranking, which t… §
VL02 – Ranking and Evaluation
The tf.idf score of $w$ in $D$ is $\mathrm{tf} \cdot \mathrm{idf}_w$ (Slide 13). In the example above: §
TF-IDF — tf weighted by $\mathrm{idf} = \log_2(N/\mathrm{df})$ to discount common words §
Inverted Index and Ranking
TF-IDF — tf weighted by $\log_2(N/\mathrm{df})$ so that common words count little §
| tf.idf | $\mathrm{tf} \cdot \log_2(N/\mathrm{df})$ | common words weigh little | tf grows linearly and with document length | §

Search in these mentions →